2.6 系統(tǒng)故障根源跟蹤

系統(tǒng)日志分析除了要找出異常和故障的系統(tǒng)日志及事件外，還要找出故障出現(xiàn)的根源。只有當(dāng)系統(tǒng)維護(hù)人員了解故障根源，才能對(duì)癥下藥，徹底解決這個(gè)問(wèn)題。

在實(shí)際的大型企業(yè)信息環(huán)境下，信息平臺(tái)通常架構(gòu)于多層系統(tǒng)之上，且每一層可能也有多個(gè)并行計(jì)算的服務(wù)器。圖2-9顯示了一個(gè)典型的企業(yè)多層信息系統(tǒng)架構(gòu)。這個(gè)架構(gòu)包含了4層服務(wù)器：Web服務(wù)器、應(yīng)用程序服務(wù)器、數(shù)據(jù)庫(kù)引擎和存儲(chǔ)服務(wù)器。前一層的服務(wù)器依賴于后一層。當(dāng)后一層的服務(wù)器出現(xiàn)故障的時(shí)候，前面一層服務(wù)器也可能產(chǎn)生相應(yīng)的故障提示。如圖2-9所示，如果磁盤(pán)陳列存儲(chǔ)發(fā)生故障，其依賴的數(shù)據(jù)庫(kù)引擎會(huì)因?yàn)閿?shù)據(jù)文件無(wú)法讀取而上報(bào)異常。應(yīng)用程序服務(wù)器依賴數(shù)據(jù)庫(kù)系統(tǒng)查詢信息也因此無(wú)法完成，同時(shí)導(dǎo)致Web服務(wù)器的響應(yīng)無(wú)法正常返回。最終表現(xiàn)為給用戶的就是網(wǎng)頁(yè)上的錯(cuò)誤提示。

網(wǎng)頁(yè)上的報(bào)錯(cuò)可能是由這4層服務(wù)器中任意一層出現(xiàn)的故障導(dǎo)致的，在實(shí)際運(yùn)行系統(tǒng)中不可能花大量時(shí)間去排除每一層服務(wù)器上的硬件和軟件問(wèn)題。系統(tǒng)日志可以提供高效且有力的故障根源跟蹤。若知道日志事件A會(huì)觸發(fā)事件B，然后事件B會(huì)觸發(fā)C，以此類推，則從觀察日志數(shù)據(jù)事件發(fā)生的鏈條即可知道故障的根源是由哪個(gè)事件觸發(fā)的。然而，在實(shí)際復(fù)雜和動(dòng)態(tài)的系統(tǒng)內(nèi)，要知道各種系統(tǒng)模塊和日志事件之間的相互依賴關(guān)系并不容易。以企業(yè)存儲(chǔ)系統(tǒng)的配置為例，通常一個(gè)大型應(yīng)用程序要訪問(wèn)的數(shù)據(jù)源都不只包含一個(gè)存儲(chǔ)設(shè)備。比如客戶關(guān)系數(shù)據(jù)會(huì)保存在關(guān)系數(shù)據(jù)庫(kù)內(nèi)，海量歷史操作數(shù)據(jù)會(huì)保存在分布式文件系統(tǒng)（如 HDFS[45]）內(nèi)，多媒體數(shù)據(jù)保存在專用的 EMC 并行存儲(chǔ)設(shè)備里等。不同應(yīng)用程序的數(shù)據(jù)源各自不同，可能有交織，也可能完全獨(dú)立。

實(shí)際大型企業(yè)的應(yīng)用程序和數(shù)據(jù)源部署網(wǎng)絡(luò)通常十分復(fù)雜，而且變化不斷，對(duì)于系統(tǒng)管理員來(lái)說(shuō)，在很多情況下并不是透明的。一個(gè)原因是涉及軟件系統(tǒng)和數(shù)據(jù)的隱私問(wèn)題。現(xiàn)實(shí)世界里很多系統(tǒng)維護(hù)（IT Service）都是外包給第三方企業(yè)來(lái)做的。原企業(yè)不一定愿意公開(kāi)所有的內(nèi)部信息給第三方企業(yè)。另一個(gè)原因是實(shí)際系統(tǒng)維護(hù)流程里很難應(yīng)付時(shí)刻變化的存儲(chǔ)網(wǎng)絡(luò)，即便是原企業(yè)自己的開(kāi)發(fā)人員也只了解和自己相關(guān)的應(yīng)用程序和存儲(chǔ)設(shè)備之間的關(guān)系。不同部門(mén)不同項(xiàng)目組對(duì)存儲(chǔ)設(shè)備的需求千差萬(wàn)別，統(tǒng)一的規(guī)劃和管理反而限制各個(gè)部門(mén)的運(yùn)行效率。很多情況下大型企業(yè)IT 環(huán)境內(nèi)的存儲(chǔ)設(shè)備，對(duì)于管理員來(lái)說(shuō)是一個(gè)黑盒子（如圖 2-10 所示）。除了存儲(chǔ)設(shè)備網(wǎng)絡(luò)外，還有各種通信網(wǎng)絡(luò)和部署網(wǎng)絡(luò)等也有類似的問(wèn)題。因此，在這樣的環(huán)境下如果出現(xiàn)系統(tǒng)故障，追溯故障根源并不是一件容易的事情。本節(jié)將介紹如何通過(guò)數(shù)據(jù)挖掘技術(shù)分析系統(tǒng)運(yùn)行日志，揣測(cè)不同設(shè)備和系統(tǒng)模塊之間的依賴關(guān)系。

2.6.1 日志事件的依賴性挖掘

2.6.1.1 關(guān)聯(lián)、相關(guān)、因果與依賴

在數(shù)理統(tǒng)計(jì)上，隨機(jī)變量具有依賴性和具有相關(guān)性是兩個(gè)不同的概念。依賴性可以理解為在物理上兩個(gè)隨機(jī)變量的取值具有某種內(nèi)在聯(lián)系。這種內(nèi)在聯(lián)系的對(duì)象是觀察的物體，而不是隨機(jī)變量采樣的取值。相關(guān)性則是隨機(jī)變量取值上的某種關(guān)系。確切來(lái)說(shuō)，相關(guān)性就是指這些隨機(jī)變量的聯(lián)合分布具有同高同低的或者對(duì)立相反的現(xiàn)象。有相關(guān)性的兩個(gè)隨機(jī)變量不一定有依賴性，因?yàn)樗鼈円部赡苁怯汕珊蠈?dǎo)致的。有依賴性的隨機(jī)變量也不一定具有相關(guān)性，因?yàn)檫@種依賴關(guān)系并不一定導(dǎo)致兩個(gè)隨機(jī)變量在聯(lián)合概率分布上有特別的表現(xiàn)特征。關(guān)聯(lián)性就是指依賴性，不是獨(dú)立的。因此，關(guān)聯(lián)性并不是指相關(guān)性。因果關(guān)系是這種依賴性的一種具體形式。例如日志事件A的產(chǎn)生導(dǎo)致了日志事件B的發(fā)生。但是現(xiàn)實(shí)世界里面并不只有因果關(guān)系的依賴，也可能有其他關(guān)系的依賴，比如剛提到的兩個(gè)隨機(jī)變量雖同時(shí)產(chǎn)生，但有互相牽制和抵觸的依賴關(guān)系。

事件的相關(guān)性并不代表事件的依賴關(guān)系或者因果關(guān)系。例如在日志數(shù)據(jù)上，事件A和事件B具有相關(guān)性，并不代表事件A引發(fā)事件B，或者事件B引發(fā)事件A。有可能是一個(gè)未知的事件C同時(shí)引發(fā)事件A和B，也可能事件A和事件B的相關(guān)性純屬巧合。本節(jié)涉及的算法都有一個(gè)大前提假設(shè)，那就是具有相關(guān)性的事件很有可能是具備依賴性或者因果性的。因此，通過(guò)找相關(guān)性來(lái)尋找依賴關(guān)系或者因果關(guān)系，是一種縮小搜索范圍的辦法，而并非一種判定依賴和因果的準(zhǔn)則。對(duì)于數(shù)據(jù)挖掘算法來(lái)說(shuō)，能夠分析的僅僅是觀察得到的數(shù)據(jù)。計(jì)算機(jī)的輸入也只能是數(shù)據(jù)，而無(wú)法真正了解數(shù)據(jù)產(chǎn)生的物理規(guī)律，因此也無(wú)法真正判定產(chǎn)生數(shù)據(jù)的隨機(jī)變量是否真的具有關(guān)聯(lián)性。所以在實(shí)際問(wèn)題的分析中，依然需要人工對(duì)找出的結(jié)果做進(jìn)一步的判定。本章后面介紹的各種日志事件的關(guān)聯(lián)和依賴的挖掘算法，都是停留在發(fā)現(xiàn)數(shù)據(jù)分布的表現(xiàn)上，而不是真正對(duì)產(chǎn)生日志的系統(tǒng)模塊之間是否具有依賴性下定論。

2.6.1.2 離散型和連續(xù)性的相關(guān)性

數(shù)據(jù)挖掘中尋找相關(guān)性的辦法大部分都是基于大量事件的觀察。系統(tǒng)日志事件的相關(guān)性分析方法根據(jù)數(shù)據(jù)類型分為兩種：一種是基于時(shí)序數(shù)據(jù)（Time Series）的相關(guān)性；一種是基于離散數(shù)據(jù)的相關(guān)性。在系統(tǒng)日志事件里，有很多系統(tǒng)測(cè)量值，諸如CPU使用率、磁盤(pán)使用率、虛擬內(nèi)存交換速率等，都是很重要的連續(xù)觀察值。值得注意的是，存儲(chǔ)在計(jì)算機(jī)內(nèi)的數(shù)據(jù)都是離散的值。這里指的連續(xù)值是指一個(gè)測(cè)量值的數(shù)據(jù)類型。離散數(shù)據(jù)可以表示一個(gè)事件或者一個(gè)現(xiàn)象是否出現(xiàn)以及它的類別等。例如，當(dāng)Java應(yīng)用程序拋出一個(gè)異常（Exception），這個(gè)觀察現(xiàn)象就可以用離散值來(lái)表示。

相關(guān)性的日志數(shù)據(jù)如圖2-11所示。

圖2-11（a）是一個(gè)典型的時(shí)序數(shù)據(jù)上的相關(guān)性展示。圖2-11（a）中有兩個(gè)時(shí)間序列的數(shù)據(jù)：數(shù)據(jù)庫(kù)服務(wù)器的磁盤(pán)I/O速率和網(wǎng)絡(luò)I/O速率。數(shù)據(jù)庫(kù)的數(shù)據(jù)消費(fèi)者和生產(chǎn)者都來(lái)自于應(yīng)用服務(wù)器，所以大部分?jǐn)?shù)據(jù)庫(kù)服務(wù)器的主要任務(wù)就是讀寫(xiě)硬盤(pán)和傳輸數(shù)據(jù)，因此這兩個(gè)時(shí)序數(shù)據(jù)具有很強(qiáng)的相關(guān)性。當(dāng)數(shù)據(jù)庫(kù)忙碌的時(shí)候，兩個(gè)序列的值同時(shí)變高；當(dāng)數(shù)據(jù)庫(kù)空閑的時(shí)候，兩個(gè)序列的值同時(shí)變低。這種相關(guān)性也常被用來(lái)做異常檢測(cè)的判定。

圖 2-11（b）顯示的是一個(gè)離散型的時(shí)間相關(guān)性。通過(guò)日志抽取可以發(fā)現(xiàn)，數(shù)據(jù)庫(kù)deadlock的日志事件和Web服務(wù)器的500異常錯(cuò)誤事件始終同時(shí)出現(xiàn)，從而可以推斷Web服務(wù)器的500錯(cuò)誤主要是由數(shù)據(jù)庫(kù)deadlock導(dǎo)致的。離散的日志事件可視化到一個(gè)二維坐標(biāo)圖里就是一系列的點(diǎn)，每個(gè)點(diǎn)代表一個(gè)事件的發(fā)生。

2.6.1.3 相關(guān)性的評(píng)估

離散型的日志事件相關(guān)性挖掘目標(biāo)不是挖掘數(shù)值上的相關(guān)性，而是對(duì)事件發(fā)生的時(shí)間前后做相關(guān)性的分析。在數(shù)理統(tǒng)計(jì)與概率論中，相關(guān)性的定義通常是指兩個(gè)或者多個(gè)隨機(jī)變量之間分布的關(guān)系。例如現(xiàn)在有兩個(gè)隨機(jī)變量X和Y，常用的Pearson相關(guān)性度量為：

其中corr(X,Y)表示X和Y的協(xié)方差，σ X、σY是X、Y的標(biāo)準(zhǔn)方差，μX、μY是X、Y的數(shù)學(xué)期望，E(·)表示求數(shù)學(xué)期望。那么為什么Pearson相關(guān)性要這么計(jì)算呢？假設(shè)X和Y的獨(dú)立分布都是已經(jīng)給定的，那么σX和σY都是固定值，唯一可以決定相關(guān)性大小的則是E[(X ?μX)(Y?μY)]。通過(guò)排序不等式，我們知道順序和≥亂序和≥逆序和，反映到（X,Y）的聯(lián)合分布的時(shí)候就是：當(dāng)X和Y同時(shí)取大或取小的時(shí)候，E[(X?μX)(Y?μY)]的值是最大的（順序和），當(dāng)X取大但Y取小的時(shí)候（亂序和）,E[(X?μX)(Y?μY)]則較小。所以，當(dāng)E[(X ?μX)(Y?μY)]較大的時(shí)候，意味著X和Y大多數(shù)時(shí)候是同時(shí)取大取小，因此這個(gè)時(shí)候X和Y就有直觀意義上的相關(guān)性。在離散型的日志事件里，定義的隨機(jī)變量可以看作只有0和1兩個(gè)值，0表示這個(gè)事件沒(méi)有發(fā)生，1表示這個(gè)事件發(fā)生。不同的事件類型用不同的隨機(jī)變量表示，但是取值都只有0和1。傳統(tǒng)的Pearson度量方法在此依然可用。

2.6.1.4 事件依賴挖掘

在數(shù)據(jù)挖掘研究領(lǐng)域，很多事件相關(guān)性挖掘更多是發(fā)現(xiàn)一種關(guān)聯(lián)性的模式（Pattern）。在統(tǒng)計(jì)上，關(guān)聯(lián)性模式的挖掘除了要求不同事件在聯(lián)合分布上的相關(guān)性外，還要求這種觀察現(xiàn)象是頻繁出現(xiàn)的，不是偶然導(dǎo)致的。直觀來(lái)說(shuō)，在對(duì)隨機(jī)變量依賴性的推測(cè)上，頻繁出現(xiàn)的相關(guān)性會(huì)比偶爾出現(xiàn)的相關(guān)性更加可靠。偶爾出現(xiàn)的相關(guān)性很可能就是偶然導(dǎo)致的，而非兩個(gè)實(shí)際變量?jī)?nèi)在物理牽連導(dǎo)致的。

此外，數(shù)據(jù)挖掘與統(tǒng)計(jì)學(xué)里的研究側(cè)重點(diǎn)也有不一樣的地方。數(shù)據(jù)挖掘算法除了關(guān)注挖掘的數(shù)學(xué)模型外，也十分關(guān)注如何快速地在大量高維的數(shù)據(jù)集中找到滿足這個(gè)數(shù)學(xué)模型的參數(shù)。很多現(xiàn)實(shí)的數(shù)據(jù)集通常都是海量數(shù)據(jù)。“快速”在處理海量數(shù)據(jù)的算法中不單單是快幾秒鐘或者幾分鐘的意義，更多是決定了一個(gè)分析任務(wù)能夠順利完成與否。例如一個(gè)O(N log N)算法恰好1 s運(yùn)行完成， N=109，而O(N2)的算法運(yùn)行時(shí)間則是109/log(109)個(gè)1 s，可能需要超過(guò)30多年才能完成。因此，本章后面提到的各種針對(duì)日志數(shù)掘的挖掘算法都涉及算法運(yùn)行效率上的考慮。

最早分析序列數(shù)據(jù)上的事件依賴模式的論文是1995年出版的參考文獻(xiàn)[46]。算法尋找的目標(biāo)就是尋找頻繁出現(xiàn)在一起的事件類型集合。該算法的大致思想是將序列數(shù)據(jù)按照事件分成多個(gè)可以重疊的時(shí)間窗口。如果事件A和事件B經(jīng)常出現(xiàn)在同一個(gè)時(shí)間窗口，則可以認(rèn)定事件A和事件B是頻繁出現(xiàn)的事件類型集合，從而揣測(cè)他們可能具有一定依賴性。其中，頻繁的度量是：

其中?是事件類型集合，S是序列數(shù)據(jù)，ω是時(shí)間窗口的長(zhǎng)度，αω(S,ω)是S所有時(shí)間窗口的集合，|{W∈αω(S,ω),|W|=?}|則表示所有時(shí)間窗口里包含?的子集。算法需要用戶給定一個(gè)閾值minfr。當(dāng)頻率大于或等于這個(gè)閾值的時(shí)候，這個(gè)?才能成為頻繁事件的集合。算法主要解決的問(wèn)題是在事件類型組合很多的情況下，需要計(jì)算的?則會(huì)很多。算法直接利用關(guān)聯(lián)規(guī)則挖掘的 Apriori 性質(zhì)來(lái)做搜索剪枝[32]：若?不是頻繁的，則其超集也不可能是頻繁的。

2.6.1.5 時(shí)間窗口

后來(lái)針對(duì)序列數(shù)據(jù)的研究者提出了不同的改進(jìn)算法。例如，頻繁出現(xiàn)在一起的事件并不意味著有依賴性。例如在日志數(shù)據(jù)里，周期性的狀態(tài)顯示日志事件肯定是頻繁出現(xiàn)的，它可能跟任何一個(gè)頻繁事件形成頻繁事件的集合。但是，它們兩者并沒(méi)有依賴性。因此，通常還需要引入其他指標(biāo)來(lái)判定找出的模式是否真的具有一定意義。人們后來(lái)逐步用lift和Pearson相關(guān)度量等其他指標(biāo)（除去支持度和置信度）來(lái)評(píng)判頻繁集合。此類的改進(jìn)方法與后來(lái)對(duì)關(guān)聯(lián)規(guī)則挖掘算法的改進(jìn)基本沒(méi)有太大區(qū)別。在序列數(shù)據(jù)挖掘中，時(shí)間窗口這個(gè)概念是與普通關(guān)聯(lián)挖掘算法最大的不同之處。參考文獻(xiàn)[46]要求用戶給定這個(gè)時(shí)間窗口的長(zhǎng)度，然后有可能用戶并不知道合適的窗口寬度。如果時(shí)間窗口寬度過(guò)小，有可能會(huì)丟掉真正的依賴性模式；如果時(shí)間窗口過(guò)大，有可能找到大量無(wú)意義的相關(guān)事件模式[47]。

圖2-12顯示的是一個(gè)時(shí)間窗口的寬度過(guò)小的例子。拋開(kāi)時(shí)間窗口，可以明顯看出圖2-12中的事件A和事件B具有一定的相關(guān)性。然而當(dāng)時(shí)間窗口的寬度過(guò)小，任何一個(gè)時(shí)間窗口都無(wú)法同時(shí)包含一個(gè)事件A和一個(gè)事件B，于是按照之前的算法，事件A和事件B的相關(guān)性就會(huì)被丟失。圖2-13顯示的是一個(gè)時(shí)間窗口的寬度過(guò)大的例子。圖2-13中除了事件A和事件B外，還有其他一些分布在時(shí)間軸上的不相關(guān)事件。然后，w過(guò)大，包含事件A的窗口幾乎都包含了至少一個(gè)其他類型事件。于是按照之前的算法，任意兩個(gè)事件都會(huì)被判定為相關(guān)的。一個(gè)極端的例子就是當(dāng)?無(wú)窮大的時(shí)候，無(wú)論數(shù)據(jù)內(nèi)的各類事件怎么分布，任意一個(gè)事件類型的集合都會(huì)被判定成為具有相關(guān)性的。

尋找合理時(shí)間窗口的首要問(wèn)題是判定一個(gè)給定的時(shí)間窗口是否合理，其次才是如何尋找。參考文獻(xiàn)[48]介紹一種基于統(tǒng)計(jì)檢驗(yàn)的方法，后來(lái)被很多人采用。參考文獻(xiàn)[48]認(rèn)為單看時(shí)間窗口的寬度是沒(méi)有意義的。時(shí)間窗口是否合理還需要看定義的閾值minfr大小。直觀來(lái)說(shuō)，當(dāng)窗口很大的時(shí)候，無(wú)論兩個(gè)事件是否有依賴性，同時(shí)包含兩個(gè)事件的窗口個(gè)數(shù)都會(huì)增多，因此這個(gè)minfr應(yīng)該設(shè)置得更大一些；當(dāng)窗口很小的時(shí)候，無(wú)論兩個(gè)事件是否依賴，包含兩個(gè)事件的窗口個(gè)數(shù)都會(huì)減小，那么minfr應(yīng)該設(shè)置得更小一些。因此，需要觀測(cè)的是（ω,minfr）這個(gè)兩個(gè)參數(shù)的組合是否合理。

給定一個(gè)時(shí)間窗口，寬度為ω，閾值為minfr。通過(guò)上述算法，我們找到Nco個(gè)時(shí)間窗口同時(shí)包含了事件 A 和事件 B,Nco≥minfr。按照之前的算法邏輯，事件 A和事件B可以被認(rèn)定具有依賴關(guān)系。那么需要驗(yàn)證的就是他們是否真的有統(tǒng)計(jì)意義上的依賴關(guān)系。可以提出一個(gè)相反的假設(shè)：事件A和事件B不是真的具有依賴關(guān)系。那么事件A和事件B其實(shí)是獨(dú)立產(chǎn)生的。在統(tǒng)計(jì)學(xué)家的眼里，世界上任何一個(gè)事件發(fā)生的可能性都是存在的，只是概率多少的問(wèn)題。那么接下來(lái)需要知道的就是基于這個(gè)假設(shè)，找到Nco個(gè)時(shí)間窗口同時(shí)包含了事件A和事件B的概率是多少。如果這個(gè)概率很低，比如小于5%，那么我們就有信心（置信度）否定這個(gè)假設(shè)，從而認(rèn)為事件A和事件B不是獨(dú)立產(chǎn)生的。于是，問(wèn)題轉(zhuǎn)換成如何計(jì)算在事件A和事件B獨(dú)立的情況下，找到 Nco個(gè)時(shí)間窗口同時(shí)包含兩個(gè)事件的概率。要產(chǎn)生兩個(gè)獨(dú)立的事件序列其實(shí)很容易，只需要用兩個(gè)獨(dú)立的隨機(jī)變量不斷模擬生成事件A和事件B即可。但是需要注意的是，針對(duì)事件A和事件B模擬生成的序列數(shù)據(jù)需要保證事件A和事件B的采樣頻率不變。可以用這樣的模擬方法生成很多條由獨(dú)立的事件A和事件B序列組成的序列數(shù)據(jù)，記為S1,…,Sm。對(duì)第i個(gè)模擬數(shù)據(jù)序列，計(jì)算出有Ni個(gè)時(shí)間窗口同時(shí)包含事件A和事件B（在時(shí)間窗口寬度為ω的情況下）。于是得到了一堆數(shù)值N1,…,Nm。這m個(gè)數(shù)值被看作由另外一個(gè)隨機(jī)變量產(chǎn)生的，那么通過(guò)這m個(gè)數(shù)值可以擬合出這個(gè)隨機(jī)變量的概率分布。最后把之前根據(jù)實(shí)際數(shù)據(jù)算出來(lái)的Nco映射到這個(gè)概率分布上，就可以得到在事件 A 和事件 B 獨(dú)立的情況下找到 Nco個(gè)時(shí)間窗口同時(shí)包含了兩個(gè)事件的概率。

如表2-1顯示的就是一個(gè)N1,…,Nm的取值分布例子。如果Nco=20，對(duì)應(yīng)的概率就是20.1%，大于5%，所以我們不能否定這個(gè)假設(shè)的存在。換句話說(shuō)，我們沒(méi)有把握確定事件A和事件B是不是有依賴關(guān)系的，因?yàn)榧幢阍讵?dú)立情況下，出現(xiàn)Nco=20的概率也高達(dá)20.1%。如果Nco=105，對(duì)應(yīng)的概率就只有0.2%。換句話說(shuō)，在獨(dú)立的情況下，不太可能出現(xiàn)Nco=20，所以在l?0.2%=99.8%的置信度情況下，可以認(rèn)為這個(gè)獨(dú)立的假設(shè)是不成立的，即事件A和事件B是存在依賴關(guān)系的。

在實(shí)際計(jì)算的時(shí)候，可能需要產(chǎn)生很多模擬獨(dú)立的序列才能產(chǎn)生完整的N1,…,Nm的概率分布，否則某些整數(shù)取值可能沒(méi)有被覆蓋到，于是出現(xiàn)的次數(shù)都是0，但是這并不代表其概率應(yīng)該是0。參考文獻(xiàn)[48]實(shí)際使用的是X方檢驗(yàn)的方法，計(jì)算一個(gè)統(tǒng)計(jì)變量X2：

其中，N是時(shí)間窗口的個(gè)數(shù)，P是指在事件A和事件B獨(dú)立的情況下，一個(gè)時(shí)間窗口同時(shí)包含A和B的概率。χ2方檢驗(yàn)中X2滿足χ2分布。而χ2分布是已知的，所以只需要計(jì)算出X2的值，然后查χ2分布表就可以知道之前假設(shè)發(fā)生的概率。

還有一些情況不要求兩個(gè)關(guān)聯(lián)的事件同時(shí)在一個(gè)時(shí)間窗口。例如我們描述：“事件B通常都發(fā)生在事件A之后的5~10 s內(nèi)”。那么，這個(gè)時(shí)間窗口并不需要同時(shí)包含事件A和事件B。它只需要包含每個(gè)事件發(fā)生之后的5~10 s即可，然后觀測(cè)初始事件是不是事件A，而不是觀測(cè)整個(gè)連續(xù)10 s內(nèi)是否同時(shí)包含事件A和事件B。如果把時(shí)間窗口設(shè)置成連續(xù)的10 s，雖然能夠同時(shí)包含互相關(guān)聯(lián)的事件A和事件B，但是如上所述，過(guò)寬的時(shí)間窗口會(huì)導(dǎo)致大量的假關(guān)聯(lián)。如果用統(tǒng)計(jì)檢驗(yàn)的辦法，就需要提高閾值minfr，那么這個(gè)閾值并不反映5~10 s這5 s的實(shí)際情況。

如圖2-14所示的時(shí)間窗口除了有寬度參數(shù)ω外，還有一個(gè)位移參數(shù)s。所描述的時(shí)間窗口就是[s,s+ω]，表示事件B會(huì)在事件A之后的s~s+ω個(gè)時(shí)間單位內(nèi)發(fā)生。這里以A→[s,s+ω]B來(lái)表示這種關(guān)系。如果A=B，那么這里的[s,s+ω]就是事件A的發(fā)生周期。之前的各種數(shù)據(jù)挖掘的文獻(xiàn)針對(duì)時(shí)序數(shù)據(jù)和事件數(shù)據(jù)提出了各種不同的事件發(fā)生模式。一個(gè)有趣的現(xiàn)象是，當(dāng)我們對(duì)這里的時(shí)間窗口加以一定約束時(shí)，會(huì)發(fā)現(xiàn)大部分這些事件模式都可以劃歸到一個(gè)簡(jiǎn)單的事件依賴關(guān)系和一個(gè)帶約束的時(shí)間窗口（見(jiàn)表2-2）。

給定一個(gè)時(shí)間窗口的參數(shù)ω，通過(guò)上述統(tǒng)計(jì)檢驗(yàn)的方法可以找到一個(gè)合理的閾值minfr。但是參數(shù)s、ω的取值范圍通常都很大。在最壞的情況下，s和ω的取值個(gè)數(shù)都是O(n2)，其中n是總共數(shù)據(jù)集內(nèi)時(shí)間戳的個(gè)數(shù)[47]。那么s和ω的組合情況個(gè)數(shù)就高達(dá)O(n4)了。顯然，我們不可能一個(gè)一個(gè)去測(cè)試所有的組合情況。通常在系統(tǒng)日志數(shù)據(jù)內(nèi)，記錄的事件集都相當(dāng)龐大。很多生產(chǎn)機(jī)在運(yùn)行的時(shí)候，除了異常事件生成日志外，各種狀態(tài)變化，甚至Web請(qǐng)求都會(huì)引發(fā)日志事件的產(chǎn)生。在這種大數(shù)據(jù)集的情況下，一個(gè)一個(gè)的組合測(cè)試方法是不可行的。參考文獻(xiàn)[49]介紹了一種基于時(shí)間間隔的聚類算法。給定兩個(gè)事件類型A和B，通過(guò)掃描數(shù)據(jù)序列，找到每個(gè)事件A和事件A之后第一個(gè)事件B之間的時(shí)間間隔，記為intervali，其中i是事件A的序號(hào)，i=1,2,…。如果事件A和事件B有關(guān)聯(lián)性，那么其合理的時(shí)間窗口[s,s+ω]必然能夠包含大量的時(shí)間間隔：

一個(gè)直觀的辦法就是通過(guò)對(duì) intervali進(jìn)行聚類分析，找出比較大的聚簇，然后通過(guò)這個(gè)簇中心找到[s,s+ω]。參考文獻(xiàn)[49]引入一個(gè)用戶定義參數(shù) E 來(lái)控制窗口的寬度，其時(shí)間窗口則表示成為[λ-ε,λ+ε]，其中A就是聚類得到的簇中心，E是簇的半徑。參考文獻(xiàn)[49]的方法中時(shí)間窗口的寬度2ε依然是由人為給定的，人可能并不知道合適的E取值。另外，此方法生成的時(shí)間間隔都是計(jì)算每個(gè)事件A和接下來(lái)一個(gè)事件B的時(shí)間間隔。這里依賴的一個(gè)假設(shè)條件就是，如果事件A和事件B有關(guān)聯(lián)性，那么每個(gè)事件A僅僅有可能與下一個(gè)事件B有關(guān)系，而不可能與下面第二個(gè)事件B、第三個(gè)事件B或者第k（k>2）個(gè)事件B發(fā)生關(guān)聯(lián)。如圖2-14所示，與第五個(gè)事件B最近的事件A是第六個(gè)事件A，而不是對(duì)應(yīng)的第五個(gè)事件A。當(dāng)時(shí)間的位移s較大，而事件分布較密集的時(shí)候，這種錯(cuò)開(kāi)的相關(guān)性是很普遍的。

參考文獻(xiàn)[47]介紹了一種無(wú)人工參數(shù)的時(shí)間窗口尋找方法。雖然s和ω的組合個(gè)數(shù)高達(dá)O(n4)，但是通過(guò)有效的數(shù)據(jù)結(jié)構(gòu)，可以避免重復(fù)多次掃描序列數(shù)據(jù)。圖2-15顯示的就是掃描事件A和事件B的一個(gè)有序表（Sorted Table）。這個(gè)表的中間是一個(gè)鏈接表（Linked List），其中每個(gè)節(jié)點(diǎn)的值表示一個(gè)可能的時(shí)間間隔。這里的時(shí)間間隔并不要求是相鄰兩個(gè)事件A和B。在掃描序列數(shù)據(jù)的同時(shí)，算法也記錄下?lián)碛羞@個(gè)時(shí)間間隔Ei的事件A和事件B的序號(hào)（Index），并保存到圖2-15中對(duì)應(yīng)的IAi和IBi數(shù)列中。掃描序列數(shù)據(jù)并生成Sorted Table需要O(n2)的時(shí)間復(fù)雜度。在Sorted Table創(chuàng)建之后，任意一個(gè)可能的時(shí)間窗口[s,s+ω]就可以由圖2-15中E1E2…的一個(gè)子串來(lái)表示，如[s,s+ω]=[20,120]可以表示成E2E3E4。那么，要知道有多少事件A和事件B被[20,120]包含，只需要合并IA2、IA3、IAi和IB2、IB3、IB4。因?yàn)镮Ai和IBi是有序的數(shù)列，可以很快得到合并之后的事件A和事件B的序號(hào)集。在初始化生成這個(gè)Sorted Table的時(shí)候，依然需要進(jìn)行時(shí)間復(fù)雜度為O(n2)的掃描操作。參考文獻(xiàn)[47]針對(duì)此問(wèn)題做過(guò)時(shí)間復(fù)雜度的分析，證明可以將著名的3SUM問(wèn)題[52]劃歸到這個(gè)問(wèn)題。如果這個(gè)問(wèn)題存在時(shí)間復(fù)雜度為O(n2)的解法，那么著名的3SUM問(wèn)題也存在時(shí)間復(fù)雜度為O(n2)的解法。3SUM是一個(gè)十分經(jīng)典的算法問(wèn)題：給定n個(gè)整數(shù)，是否存在3個(gè)數(shù)a、b和c滿足a+b=c?

3SUM問(wèn)題的發(fā)展歷史跟計(jì)算機(jī)科學(xué)的發(fā)展歷史相似。到目前為止，人類還沒(méi)有發(fā)現(xiàn)一個(gè)時(shí)間復(fù)雜度為 O(n2)的算法。所以可以說(shuō)，現(xiàn)在還不存在時(shí)間復(fù)雜度為O(n2)的算法能夠徹底解決序列數(shù)據(jù)中兩個(gè)關(guān)聯(lián)事件的時(shí)間窗口問(wèn)題。當(dāng)然，快速的近似算法還是值得研究和發(fā)現(xiàn)的。另外一個(gè)問(wèn)題是關(guān)于Sorted Table的空間復(fù)雜度的問(wèn)題。完整的Sorted Table空間復(fù)雜度是O(n2)。參考文獻(xiàn)[47]也提出了一個(gè)針對(duì)Sorted Table空間復(fù)雜度的改進(jìn)算法。其實(shí)掃描Sorted Table和構(gòu)建Sorted Table兩個(gè)步驟是可以同時(shí)進(jìn)行的，并不需要等所有的時(shí)間間隔（Time Lag）都填到Sorted Table之后才開(kāi)始掃描。另外一方面，掃描Sorted Table是順序掃描，不需要回溯，所以掃描完前面一部分的時(shí)候，就可以刪除再創(chuàng)建下面一部分的內(nèi)容。因此空間復(fù)雜度可以控制在 O(ωmax·n)以內(nèi)，ωmax是訓(xùn)練可取的最大值。當(dāng) ω>ωmax的時(shí)候，即便所有的事件 A 和事件 B 都被這個(gè)時(shí)間窗口包含，根據(jù)統(tǒng)計(jì)驗(yàn)證也不能把事件 A和事件B判定為具有相關(guān)性。但是，ωmax其實(shí)并不是一個(gè)關(guān)于n的函數(shù)，而是一個(gè)關(guān)于序列數(shù)據(jù)采樣率和統(tǒng)計(jì)驗(yàn)證的p-value的常數(shù)，其具體證明見(jiàn)參考文獻(xiàn)[47]。

圖2-16對(duì)比了參考文獻(xiàn)[49]的聚類算法inter-arrival、時(shí)間窗口窮舉法brute - force、基于Sorted Table的算法STScan 3種方法的實(shí)際運(yùn)行效率。數(shù)據(jù)集是人工產(chǎn)生的，并混入了預(yù)先定義好的幾個(gè)關(guān)聯(lián)事件與時(shí)間窗口。因?yàn)檫@里的正確結(jié)果是人工預(yù)先定義的，所以判定算法的有效性就是直接看找出來(lái)的關(guān)聯(lián)事件與時(shí)間窗口是否和預(yù)定義的一致。其中brute-force*和STScan*利用了ωmax作為ω搜索上界。可以看出inter-arrival明顯比各種算法快幾個(gè)數(shù)量級(jí)，實(shí)際發(fā)現(xiàn)inter-arrival并不能總是找到正確的時(shí)間窗口。

2.6.2 基于依賴關(guān)系的系統(tǒng)故障追蹤

復(fù)雜系統(tǒng)內(nèi)的故障跟蹤方法大多基于系統(tǒng)組件的依賴關(guān)系圖（Dependency Graph）[53-55]。如果用戶對(duì)系統(tǒng)內(nèi)部架構(gòu)十分清楚，依賴關(guān)系圖可以由人工創(chuàng)建。如果系統(tǒng)內(nèi)部十分復(fù)雜且不斷變化，那么可以通過(guò)各種數(shù)據(jù)挖掘算法，根據(jù)日志數(shù)據(jù)來(lái)自動(dòng)創(chuàng)建依賴圖。第2.6.1節(jié)介紹的依賴關(guān)系挖掘，主要涉及系統(tǒng)組件兩兩之間的關(guān)系。當(dāng)把所有找到的兩兩依賴關(guān)系匯總時(shí)，就得到了一個(gè)整體系統(tǒng)的依賴關(guān)系圖。假設(shè)一個(gè)組件出現(xiàn)故障后，其依賴的組件也應(yīng)該出現(xiàn)某種故障，如同Java程序里面的Exception拋出一樣，我們可以根據(jù)一層一層的依賴關(guān)系推測(cè)最深層出現(xiàn)故障的組件，并可以認(rèn)定這個(gè)組件就是故障的根源。實(shí)際系統(tǒng)內(nèi)，一個(gè)組件出現(xiàn)的故障事件可能并非由其依賴的上一層組件的故障導(dǎo)致的，也有可能是上一層的組件某些異常指標(biāo)導(dǎo)致了當(dāng)前組件的故障。我們可以將故障、異常等觀察現(xiàn)象用一個(gè)組件的狀態(tài)的集合來(lái)描述。相互依賴的組件互相的關(guān)系可以由一個(gè)條件概率分布來(lái)表達(dá)。例如node2依賴于node1。假設(shè)我們有2個(gè)狀態(tài){A,B}，那么P(node2=A|node1=B)表達(dá)了當(dāng)node1狀態(tài)是B的時(shí)候，node2狀態(tài)是A的條件概率。在已知的系統(tǒng)依賴圖基礎(chǔ)上，我們就可以創(chuàng)建出貝葉斯網(wǎng)絡(luò)[32]，然后觀察對(duì)出現(xiàn)的某些組件的日志事件數(shù)據(jù)，得到那些組件的當(dāng)前狀態(tài)。當(dāng)故障出現(xiàn)之后，利用其前后的日志數(shù)據(jù)得到該貝葉斯網(wǎng)絡(luò)中某些節(jié)點(diǎn)的當(dāng)前狀態(tài)，再通過(guò)此貝葉斯網(wǎng)絡(luò)估計(jì)其他未觀測(cè)到的組件最有可能的狀態(tài)，即可知道故障根源的組件。