基于監控數據的M ySQL異常檢測算法

凌 駿，尹博學，李 晟，王 鑫

（1.天津大學計算機科學與技術學院，天津300072；2.百度（中國）有限公司，北京100085）

基于監控數據的M ySQL異常檢測算法

凌 駿1，2，尹博學2，李 晟2，王 鑫1

（1.天津大學計算機科學與技術學院，天津300072；2.百度（中國）有限公司，北京100085）

隨著互聯網數據規模的增長，服務器集群的規模快速擴大，對大規模的集群進行監控和分析成為互聯網行業運維的難點。為此，根據監控統計數據劇烈波動的特點，提出一種M ySQL異常檢測分析算法，采用基于模式的異常檢測方法，無須設置閾值，分段取模式特征值，計算異常點、異常區間和異常程度。實驗結果表明，該算法對于抖動劇烈監控數據的時序序列可以較好地提取數據特征，與基于均值方差的異常檢測算法相比，具有更高的精準度，對監測數據的適用性較強。

異常檢測；監控數據；統計；模式；時間序列

1 概述

基于監控統計數據的異常檢測是對各類系統的大量監控數據進行分析，實現監控自動化、進行預測報警、定位問題的基本方法。隨著系統規模的快速擴增，監控數據的規模也隨之增長。如何結合統計學原理，對大規模的監控數據進行分析，給出系統問題的定位建議，成為一個很有價值的問題。一個可以自動對大規模監控數據進行自動分析，并且可以對問題的定位提供建議的異常檢測模型，可以大大降低運維成本，提高工作效率。

傳統的異常檢測方法主要有：基于分布的方法［1］，基于深度的方法［2-3］，基于聚類的方法［4］，基于距離的方法［5］和基于密度的方法［6-7］。基于分布和深度的方法要求已知數據集的分布，根據觀察結果是否符合分布確定是否為異常數據，顯然對于抖動劇烈的監控數據不可能預知其分布；基于聚類的方法一定程度上可以進行異常分析，由于效率問題一般不用于此場景；基于距離和密度的算法對于內部密度明顯的數據集會遇到問題，或者局部都判斷為異常，或者無法發現。

在經濟學領域，尤其是在證券交易等方面，統計學家建立了自回歸滑動平均模型（Auto-Regressive and Moving Average model，ARMA）［8］等成熟的數學模型對時序數據進行建模，可以很好地擬合季節性趨勢和隨機因素，對某一時刻之后較短的時間段進行預測，并且給出置信區間。但是對于監控數據，數據的抖動非常劇烈，系統故障和人為因素都會導致監控數據的變動，不具備固定的周期性。且當系統發生故障時，無法定位具體的時間點。ARMA等傳統的模型對數據要求較高，且只能預測某一時間點后一小段時間的值。這些模型在擬合較長期的周期性數據時可以達到不錯的效果，而在系統的監控數據方面效果并不理想。

本文提出一種基于監控數據的M ySQL異常檢測算法，該算法基于模式的聚類算法［9-10］，分段取模式特征，結合k最近鄰（k Nearest Neighbor，kNN）［11］算法，計算局部異常因子。

2 基于模式的異常檢測方法

通過等時間間隔收集系統狀態，可以得到系統狀態相關的時間序列。時間序列的異常按照其形式，可以分為序列異常、點異常和模式異常。

在異常檢測領域，所謂模式指的是將數據按照一定規則進行劃分，然后根據數據特性，對每個分片計算相關的統計量，作為此分片的特征值。多維特征值構成一個向量，也稱之為模式，用于描述此分片的主要統計特性：

（1）序列異常。對于大量時間序列，某個序列在均值、方差等特征方面明顯不同于其他序列，稱之為序列異常。

（2）點異常。在某一條時間序列中，部分點明顯偏離整體序列的趨勢，稱之為點異常。

（3）模式異常。對時間序列進行模式化，序列中部分子序列的模式特征明顯不同于絕大多數其他子序列的模式特征，稱之為模式異常。

本文通過對時間序列進行劃分，采集各模式特征，計算并定位異常的模式所在區間，給出模式異常程度。

2.1 監控數據場景分析

M ySQL集群的監控，每隔相等的時間段對系統和數據庫各統計項進行采集，可以獲取到大量的監控數據的時間序列。由于監控數據的多樣性，針對不同的數據特征，需要采用不同的方法進行分析。本文提出的方法主要針對無規律的、劇烈波動的序列進行檢測。無需手動設置閾值，只根據數據本身的特征，找到其中的異常區間，給出異常程度。

2.1.1 線上監控數據特點

異常數據的檢測，針對圖1所示的數據，橫坐標為時間軸，縱坐標為具體的數值，從280時刻開始到350左右，這段數據和其他絕大多數時間段區別較大。針對這種數據，提出了一個算法，找到異常區間并且給出異常程度。

圖1 M ySQL的某個監控項時序圖

如圖1所示異常主要有2點特性：

（1）部分子序列有偏離大多數子序列的趨勢；

（2）異常已經發生，隱藏于序列之中，需要尋找異常模式，給出異常程度。

2.1.2 監控數據歸類分析

不同的監控數據差別很大，本文主要針對M ySQL和系統一共733個指標的監控數據。累計2 d按照固定時間間隔進行采樣，獲取733個時間序列，每個序列由2 056個數值組成，然后進行繪圖和歸類分析。M ySQL系統監控項非常多，這里只針對經常出現異常且較難定位的數據進行實驗，實驗所用的監控項如表1所示。

表1 實驗監控項

通過對比觀察，檢測數據主要分為如圖2～圖4的情形。

圖2 M ySQL的com-begin監控項

圖3 M ySQL的com-change-db監控項

圖4 M ySQL的created-tm p-tables監控項

對于圖2和圖4的情形，序列呈遞增趨勢。圖2呈現階段性抖動，圖4較為平滑。要想體現數據的模式特征，圖2需要的模式長度過長，因而導致模式數量過少，因此基于模式的異常檢測無法適用。圖3是符合此算法典型的數據模式，抖動頻繁且平穩。圖4數據呈現較為平穩的遞增趨勢，通過一次差分操作，便可去除均值變化對特征造成的影響，即可轉化為類似于圖3的數據。本文后續的分析主要針對圖3類型的數據進行分析和實驗。

2.2 基于模式的異常檢測算法

由于監控數據劇烈的波動性，采用線性回歸等方式對數據進行擬合分析效果不盡人意，因此對監控序列進行分段分析，每段作為一個模式，取模式特征進行描述，暫取均值和方差進行實驗。這樣將監控序列分為許多個模式，每個模式用一個特征向量來表示，將模式映射為二維空間上的一個點。由此可以引出模式距離等相關概念。

2.2.1 異常相關統計量

設時間序列為X=＜x1，x2，…，xn＞，通過線性分段方法得到的時間序列表示為：

L（X）=｛L（xi1，xi2），L（xi2，xi3），…，L（xi（n-1），xin）｝其中，L（xi1，xi2）表示連接兩點的直線段。

模式：時間序列可以分為n個子序列，其中每個子序列稱之為一個模式；模式取特征構成特征向量。

規范化處理：由于模式特征可能不在一個數量級，需要對各個特征值進行規范化處理，公式如下：

模式距離：使用規范化后的特征值向量的歐幾里得距離表示為模式距離。

相關系數（k-count）：對每個模式計算其與其他模式的距離，取其中Top k個，然后將這k個模式的k-count計數自增一。認為當前模式可以到達這k個模式，實驗中對k的取值進行多次調試，實驗表明當其為模式數量的1/3時效果最佳。

影響因子：對k-count進行歸一化處理：

異常因子：衡量模式的異常程度，n為某節點的k可達鄰居的數量，則該點的異常因子為：

2.2.2 系統體系結構

系統以監控數據的時序序列作為輸入，將模式映射到特征空間；然后計算各特征向量的距離，根據距離遠近給出，根據設定的過濾條件給出異常區間和異常程度，系統架構如圖5所示。

圖5 異常檢測系統架構

模式特征的選擇和相關計算公式已經確定，模式的選擇方式直接決定了最終結果的精確度。

2.2.3 各類模式選擇算法

模式選擇算法主要有以下3種：

（1）基于固定誤差的模式選擇算法

事先指定額定誤差error和最小模式長度d，第1個模式從起點開始；依次向后擬合，若當前擬合的線段L（xi，xj）經過線性插值之后，和原來的數據擬合誤差達到額定誤差error之后，若j-i＞d，則將L（xi，xj）加入模式集合中；否則繼續向后擬合到分段，到d為止；最終得到模式的集合。

基于固定誤差的方法可以保證擬合誤差，但是對于圖2所示的數據不適用。劇烈的抖動會導致擬合片段過多；很難根據整體的數值特性判斷額定誤差的值，最小模式長度d也沒有理論上的最優值。

（2）基于時態邊緣算子的模式選擇算法

文獻［12］提出了基于時態邊緣算子的異常檢測算法。u表示時態邊緣算子的檢測窗口大小，d表示最短模式長度。利用時態邊緣算子Teo（t，u）與時間序列X=＜x1，x2，…，xn＞做卷積運算，計算時間序列中各點的邊緣幅度，交替取極大值和極小值點，將時間序列分割為各個不等長的子序列。

當設置了合適的u和d值時，效果優于固定長度分段和固定誤差的方法。但是此算法也有必要的適用環境和前提：設置合適的u和d值；數據不可以類似圖2劇烈抖動；對于線上的監控數據，這2個值很難直觀確定，且大部分監控數據均為無規則抖動，因此不適合于監控數據分析。

（3）基于固定長度的模式選擇算法

根據數據量和波動程度，設置模式長度，保證模式可以體現時序序列的特征；由于數據的劇烈抖動性，其他的擬合方式不是很適用。用戶可以根據數據量的大小和數據的抖動特性，很容易地選擇合適的模式長度。樸素的固定分段可以保證模式的代表性和模式的數量，取得更好的效果。

2.3 基于模式的異常檢測算法

針對圖2類似的數據，本文結合kNN聚類算法和基于模式的異常檢測的思想，提出了基于模式的異常檢測算法算法。實驗表明，在數據規模達到一定程度時，可以很好地找到模式差異，定位異常區間。

算法首先將數據進行分段，每d個數據作為一個模式單元，計算每個模式的特征值，構成特征向量。再對每個模式計算求得距離最近的Top K個模式，將該模式加入到這K個模式的相關集合中，最后根據每個模式的相關模式的集合的大小以及和該模式相關的模式的影響因子計算該模式的異常程度。

算法 基于kNN和模式的異常檢測算法

輸入 時間序列X=＜x1，x2，…，xn＞，參數d，n，k

輸出 異常區間（xi，xj），異常程度exceptioni

通過取特征，將各個分段映射為特征向量，并作歸一化處理，可以有效提高算法對數據的適應性。各個特征向量之間的聯系的緊密程度通過getdistance方法計算向量之間的歐幾里得距離來衡量。

2.4 復雜度分析

上述算法獲取Top K個鄰居模式，可以采用基于快速排序的算法或者堆排序的算法，全部進行排序，算法復雜度為O（n×log（n）），但是由于只需要取前K個元素的排序，因此復雜度為O（n×log（k）），對每個模式如此操作，復雜度為O（n2×log（k））；其余操作均為O（n2）的復雜度；綜上所述，算法復雜度為O（n2×log（k）），算法可以在多項式時間內完成計算，給出異常結果。

空間代價主要和模式數量有關，設有m個模式，每個模式需要存儲與其他模式的距離，然后進行Top k運算。主要的內存消耗在模式中的距離列表，總體為O（m2）的空間復雜度。

3 實驗結果與分析

針對上文提出的算法，基于M ySQL和系統的監控數據，與基于均值和方差的異常檢測算法進行了對比實驗，主要進行了環比分析和同比分析。環比分析指從一條監控序列看，某一時刻和其他大部分時刻相比，是否存在異常，用于發現趨勢的異常；同比分析是將2天同一時刻的數據進行對比，比較監控數據的差異，消除人為因素的影響。

硬件環境：雙核四線程i5-3210M CPU，頻率為2.50 GHz，內存為DDR3 1 600 MHz雙通道4 GB× 2。操作系統使用的是Ubuntu 12.04 64位desktop。軟件環境：程序基于Java編寫，IDE為Eclipse Kepler，JDK版本為1.6。數據環境：M ySQL服務器連續兩天的監控數據，每個監控項采集2 056個數據項，構成733個時間序列。模式長度d設置為50，報警閾值k設置為0，連續n報警設置為1。這樣會輸出所有的模式的異常程度。系統針對應用需求，實現了環比分析和同比分析2種功能，并且針對3種模式選擇方式進行了對比實驗。

3.1 應用場景分析

本文系統主要針對大規模的監控數據，運維人員難以定位數據異常所在的情況下，通過環比和同比分析，給出異常區間，方便對問題的快速定位。

3.1.1 環比分析

當監測數據量過大，運維人員不得不查看很長的時間序列，這就對系統提出了環比分析的需求。環比分析根據監控數據的趨勢進行統計分析，找到和絕大多數區間不同的區間，定位問題發生的時間段。采用M ySQL的bytes-received-pt監控項2天的數據進行實驗，此監控項可以很大程度反映用戶的訪問量的變化，如圖6所示。

圖6 監控數據的環比統計分析

從圖6明顯可以看出，對應的區間異常程度明顯高于其他區間，效果較為明顯。

3.1.2 同比分析

由于用戶行為不同時段的差異造成監控數據不同時段差異很大，因此對系統提出了同比分析的需求，對照2天的監控數據，定位異常區間。依然選擇bytes-received-pt監控項2天的數據進行同比分析。

圖7（a）、圖7（b）中的曲線均為2天的系統監控數據的時序序列，按照時間進行對齊。圖7（c）表示其異常程度。

圖7 監控數據的同比分析

可見，若2條曲線差異性決定了柱狀圖的高低，同比分析在此數據上可以取得較好的準確性。

3.2 實驗對比

針對此類監控數據，傳統的異常檢測算法通常采用均值加上k倍標準差設定閾值，根據閾值的偏離程度計算異常程度，進而決定是否報警。由于均值和方法常常不在一個數量級，因此通常也需要先對數據進行歸一化處理，然后再計算均值和方差，給出閾值。

這類算法的適用性有限，而且需要根據不同的數據調整k值。本文提出的算法通過基于模式的異常檢測算法，結合kNN思想，對數據進行了抽象化處理，減少了對數據的依賴，具有更好的適用性，并且效果明顯。

將算法1與基于均值和方差的異常檢測算法進行實驗對比，驗證方法的有效性。固定長度分段，模式長度d為50個、2 056個數據組成時間序列，構成41個模式。數據曲線和異常柱狀圖如圖8所示。

圖8 基于模式和kNN算法的數據分析

后面針對同樣的數據，采用傳統的均值加上k倍標準差的方法進行異常檢測，根據此數據對k進行調整和嘗試，效果如圖9所示。

圖9 樸素異常檢測算法（k=0.1）結果

如圖10所示，k的選擇直接決定了閾值區間的大小，也決定了結果的精確度。但k不是可以直接根據數據趨勢進行經驗選擇的值，需要經過統計分析才能得到最優值；本文算法只需要模式長度一個參數即可，根據曲線圖即可直觀地選擇合適的數值，保證具有一定的代表性即可，具有更好的可用性。

圖10 樸素異常檢測算法（k=0.3）結果

從圖9和圖10的對比可以明顯看出，樸素的異常檢測算法，即使給定優化后的k，異常程度的顯著性和異常區間的范圍不夠精確，相對而言，本文提出的算法精度提高約50%。

4 結束語

本文根據監控統計數據的特點，針對其劇烈抖動的特性，結合基于模式的異常檢測算法和kNN思想，提出了一種新的異常檢測算法。相較于以往的基于均值和方差的異常檢測算法，本文算法在可用性和精確度方面有了一定的提升。后續工作主要包括以下2個方面：（1）本文系統暫時采用均值和方差作為特征值，可以根據不同的數據特征選擇不同的特征值，提高精度；（2）模式長度目前是固定的，可以考慮根據數據特性自動進行模式長度的調優，提高系統的適用性和計算結果的精度。

［1］ Hodge V J，Austin J.A Survey of Outlier Detection Methodologies［J］.Artificial Intelligence Review，2004，22（2）：85-126.

［2］ 李光強，鄭茂儀，鄧 敏.時空數據異常探測方法［J］.計算機工程，2010，36（5）：35-36，39.

［3］ Rousseeuw P J，Hubert M.Robust Statistics for Outlier Detection［J］.Wiley Interdisciplinary Review s：Data Mining and Know ledge Discovery，2011，1（1）：73-79.

［4］ Jiang M F，Tseng S S，Su C M.Two-phase Clustering Process for Outliers Detection［J］.Pattern Recognition Letters，2001，22（6）：691-700.

［5］ He Z，Xu X，Deng S.Discovering Cluster-based Local Outliers［J］.Pattern Recognition Letters，2003，24（9）：1641-1650.

［6］ Esling P，Agon C.Tim e-seriesData Mining［J］.ACM Computing Surveys，2012，45（1）：12-19.

［7］ Breunig M M，Kriegel H P，Ng R T，et al.LOF：Identifying Density-based Local Outliers［J］.ACM Sigmod Record，2000，29（2）：93-104.

［8］ 陳 乾，胡谷雨，路 威.基于距離和DF-RLS的時間序列異常檢測［J］.計算機工程，2012，38（12）：32-35.

［9］ Jin W，Tung A K H，Han J.Mining Top-n Local Outliers in Large Databases［C］//Proceedings of the 7th ACM SIGKDD International Conference on Know ledge Discovery and Data Mining.New York，USA：ACM Press，2001：293-298.

［10］ Papadim itriou S，Kitagawa H，Gibbons P B，et al.LOCI：Fast Outlier Detection Using the Local Correlation Integral［C］//Proceedings of the 19 th International Conference on Data Engineering.Washington D.C.，USA：IEEE Press，2003：315-326.

［11］ Yoon K A，Kwon O S，Bae D H.An Approach to Outlier Detection of Software Measurement Data Using the K-means Clustering Method［C］//Proceedings of the 1st International Symposium on Empirical Software Engineering and Measurement.Washington D.C.，USA：IEEE Press，2007：443-445.

［12］ 肖 輝，馬海兵，龔 薇.基于時態邊緣算子的時間序列分段線性表示［J］.計算機工程與應用，2008，44（19）：156-159.

編輯索書志

MySQL Outlier Detection Algorithm Based on Monitoring Data

LING Jun1，2，Y IN Boxue2，LISheng2，WANG X in1
（1.School of Computing Science and Technology，Tianjin University，Tianjin 300072，China；2.Baidu（China）Co.，Ltd.，Beijing 100085，China）

With the explosive grow th of the data on the Internet，the scale of the server cluster is rapidly expanding. How to carry out large-scale cluster monitoring and analysis becomes a difficult problem in the Internet industry. Therefore，this paper presents a new method for detection and analysis of the monitoring data according to the monitoring jittering data.It adopts pattern-based outlier detection method without setting a threshold，takes the eigenvalues，calculaties the outliers，and obtains the abnormal range and degrees.Experimental results show that the algorithm can extract data features for time sequence of jittering data，and has a higher precision and better applicability than the outlier detection algorithm based on mean-variance.

outlier detection；monitoring data；statistics；pattern；time sequence

凌 駿，尹博學，李 晟，等.基于監控數據的MySQL異常檢測算法［J］.計算機工程，2015，41（11）：41-46.

英文引用格式：Ling Jun，Yin Boxue，Li Sheng，et al.MySQL Outlier Detection Algorithm Based on Monitoring Data［J］. Computer Engineering，2015，41（11）：41-46.

1000-3428（2015）11-0041-06

A

TP393

10.3969/j.issn.1000-3428.2015.11.008

第三屆“百度主題研究”基金資助項目。

凌 駿（1991-），男，碩士研究生，主研方向：RDF圖數據管理，M ySQL數據庫技術；尹博學、李 晟，碩士；王 鑫，副教授、博士。

2014-11-03

2014-12-02 E-m ail：lingjun@tju.edu.cn