基于Hadoop 平臺的快速日志挖掘方法?

昂 鑫 徐 建 張 宏

（南京理工大學(xué)計算機科學(xué)與工程學(xué)院 南京 210094）

1 引言

隨著互聯(lián)網(wǎng)和電子商務(wù)的不斷發(fā)展，越來越多的人選擇網(wǎng)上購物，這些用戶訪問、交易的過程和系統(tǒng)狀態(tài)都會以日志的形式記錄下來。顯然這些日志數(shù)據(jù)是異構(gòu)的，且數(shù)量巨大，并且，其中蘊含著很多有價值的信息。比如，通過挖掘Web 日志，可以統(tǒng)計分析出服務(wù)器在不同時段的用戶訪問量，訪問者IP 地址的分布情況，訪問網(wǎng)頁的時間等，然后給用戶定向推送相關(guān)產(chǎn)品信息和廣告。再比如，可通過日志分析某網(wǎng)站訪問量是否異常，進而判斷是否有黑客攻擊或者非法鏈接請求等，所以，日志挖掘是非常有意義的工作。然而，一個可接受的日志標準還沒有被開發(fā)，因此，如何快速解析來自不同系統(tǒng)的日志數(shù)據(jù)是一個極具挑戰(zhàn)性的問題。

目前已知的日志模式發(fā)現(xiàn)方法主要分為兩大類：基于正則表達式的日志匹配方法，基于聚類算法的日志模式識別。許多公司開發(fā)了日志分析工具，如：Splunk，Sumo Logic，loggly，LogEntries 等，還有一些開源軟件包也被用于日志分析，如Elastic-Search［1］，OSSIM［2］等。這些工具和軟件包大多使用正則表達式來匹配日志數(shù)據(jù)，僅支持監(jiān)督匹配，不適用于大量異構(gòu)日志。此外，正則表達式的編寫過程復(fù)雜、容易產(chǎn)生沖突的特點給日志分析工作帶來了很大的困難。尤其，過度泛化的正則表達式規(guī)則降低了日志數(shù)據(jù)的處理效率。Vaarandi［3］開發(fā)了簡單的日志文件聚類工具SLCT。SLCT 本質(zhì)上是基于頻繁單詞的聚類算法，即具有相同頻繁單詞的日志會被聚集在一起。SLCT 利用了日志中單詞的高度傾斜分布的特點進行聚類，該特點也被很多日志挖掘聚類算法應(yīng)用。Makanju 等［4～6］在日志數(shù)據(jù)分析方面開展了一系列工作。在文獻［6］中，作者提出了IPLoM，這是一種迭代的日志聚類算法，實驗證明了該算法優(yōu)于其他日志聚類算法，比如上文提到的SLCT。但是IPLoM 易生成小的、沒有統(tǒng)計意義的簇碎片，簇質(zhì)量也難以控制。尤其是，IPLoM假設(shè)等長的日志具有相同格式，使得它不適合在大量異構(gòu)日志中使用。C.Xu 等［7］提出了一種無自定義參數(shù)的聚類Web日志的算法，然而該算法的時間復(fù)雜度為O（n3），其中n 是日志的數(shù)量，不能擴展到大數(shù)據(jù)集。Xia Ning 等［8］研究了一種無監(jiān)督的HLAer 框架，該框架用于自動解析異源日志數(shù)據(jù)，對異構(gòu)日志具有健壯性，由于運行需要大量的內(nèi)存開銷，所以也不可擴展。以上的算法或工具的共同問題在于：無法擴展到大量異構(gòu)日志數(shù)據(jù)集中。

近年來，Hadoop 平臺在處理大數(shù)據(jù)集上表現(xiàn)出了優(yōu)異的性能，MapReduce 是Hadoop 平臺的計算框架。李洋等［9］研究了基于Hadoop 與Storm 的日志實時處理系統(tǒng)，實驗證明了在四個節(jié)點的集群環(huán)境下提取相同頻繁項集的運行時間比單機大約減少了一半。吳潔明等［10］提出了一種基于Hadoop的Web 應(yīng)用日志挖掘算法，該算法能準確進行日志模式發(fā)現(xiàn)，并在效率方面較單節(jié)點模式有著極大的提升。許抗震等［11］研究了基于Hadoop的網(wǎng)絡(luò)日志挖掘方案的設(shè)計，實驗表明了Hadoop 集群擁有良好的計算擴展性，通過增加節(jié)點的方式，且不需進行很多復(fù)雜的配置就能解決海量日志數(shù)據(jù)的處理問題。

因此，本文提出了基于Hadoop 平臺的快速日志模式發(fā)現(xiàn)方法，該方法在分布式平臺下，通過掃描一次日志，就可快速將日志聚類并提取相應(yīng)的日志模式。本文主要工作概述如下：1）描述一個完整的日志模式發(fā)現(xiàn)的框架；2）描述在Hadoop 平臺下進行日志聚類和模式發(fā)現(xiàn)算法；3）將本文提出的日志模式發(fā)現(xiàn)方法與HLAer進行對比實驗。

2 快速的日志模式發(fā)現(xiàn)

日志來源于特定的用于系統(tǒng)監(jiān)測或狀態(tài)感知的組件，通常是基于特定模板產(chǎn)生的，因此具有明確的格式，當然產(chǎn)生于不同組件的日志格式不盡相同。本文所提出的快速的日志模式發(fā)現(xiàn)方法就充分考慮了產(chǎn)生日志消息的模板是有限的，不同的日志消息可能源于相同的模板，它們之間存在相關(guān)性的這一特性。這顯然有別于傳統(tǒng)的聚類方法，它們將每個樣本都視為獨立對象，并不考慮相互之間的關(guān)系。下文首先通過一個實例闡述日志數(shù)據(jù)的特性，而后設(shè)計用于快速日志模式發(fā)現(xiàn)的框架，在此基礎(chǔ)上提出一種分布式的日志聚類和模式發(fā)現(xiàn)方法。

2.1 日志實例和特性分析

圖1 給出了一個jenkins 可持續(xù)集成系統(tǒng)的日志作為示例用于闡述日志特性。與文檔，網(wǎng)頁等同樣采用自然語言的數(shù)據(jù)相比，日志數(shù)據(jù)具有以下特點：

1）日志數(shù)據(jù)的語法結(jié)構(gòu)弱。為了記錄應(yīng)用程序或系統(tǒng)的運行狀態(tài)，日志通常是簡短的，且不遵循標準的語法結(jié)構(gòu)，因此NLP解析器無法在日志中識別有意義的語法。

2）日志的詞匯量有限，但詞匯統(tǒng)計呈偏斜分布，某些詞出現(xiàn)的頻率高，有長尾現(xiàn)象。

3）基于模板生成日志。由于日志記錄從源代碼生成，具有明確的格式，使得日志數(shù)據(jù)比其他文本數(shù)據(jù)更容易聚類。

4）類型相同的日志會有冗余。日志記錄的冗余是日志數(shù)據(jù)與傳統(tǒng)文本數(shù)據(jù)的主要差異，當日志記錄用于管理時，相同類型的日志會重復(fù)多次出現(xiàn)，因此，可以對相同類型的日志數(shù)據(jù)進行下采樣，以減少內(nèi)存和CPU使用的負擔，也可提高日志分析的效率。

圖1 jenkins可持續(xù)集成系統(tǒng)的日志

圖2 日志模式發(fā)現(xiàn)框架

2.2 框架

圖2 給出了日志模式發(fā)現(xiàn)的框架，聚焦于分布式日志模式發(fā)現(xiàn)組件。首先，通過flume和kafka等構(gòu)成的日志匯集組件將分布式環(huán)境中的日志匯聚到Hadoop 平臺。然后，對日志進行預(yù)處理，采用聚類方法將相似的日志聚集在一起，再利用日志模式識別方法提取每個簇的模式。最后，將這些模式傳遞給故障預(yù)測模型等應(yīng)用。本質(zhì)上，產(chǎn)生的日志模式是將原始日志的特征空間進行了降維，且保留了關(guān)鍵特征。最后，根據(jù)模型的預(yù)測效果，重新選取參數(shù)迭代進行日志聚類、模式識別、模型訓(xùn)練等操作，以獲得最佳效果。本文將重點闡述分布式日志模式發(fā)現(xiàn)部分。

2.3 分布式的日志模式發(fā)現(xiàn)方法

日志數(shù)據(jù)具有明確的格式，在大量異構(gòu)日志源的情況下，相同日志源的日志很相似，大多只是同類型字段的數(shù)值不同，在高維空間中，會形成完全分離和高度密集的區(qū)域。因此，我們可以充分利用這個性質(zhì)，先將日志數(shù)據(jù)預(yù)處理，再采用One-Pass日志聚類方法，只掃描一次日志就可將所有日志準確聚類，而不必像傳統(tǒng)聚類算法一樣，需要多次迭代尋找簇中心。最后，對于每個簇，順序合并日志以生成日志模式。

2.3.1 標記和類型檢測

首先通過空格分隔每條日志數(shù)據(jù)來進行預(yù)處理，然后，定義一組類型，如date，time，IP，number和URL 等，再用正則表達式匹配日志和定義的類型，并用類型值替換實際值。例如，用date 替換2018-07-09，用IP 替換192.168.1.115。雖然這個步驟不是強制性的，但是，經(jīng)過預(yù)處理，日志的相似性度量更加準確。否則，兩條日志會因為同類型字段的數(shù)值不同獲得低相似性。因此，為避免產(chǎn)生多余的日志模式，需要進行標記化和類型檢測。

2.3.2 日志的相似性度量

其次，給出日志的相似性度量方法，如果簡單地從兩條日志的第一個單詞開始按順序比較是否相同，那么就忽略了日志原來的模板。為了完全捕獲日志的結(jié)構(gòu)和內(nèi)容的相似性，需要先對齊日志，再計算相似度。這里采用Smith Waterman［12］算法，它利用動態(tài)規(guī)劃的思想從兩條日志的第一個單詞開始向后遞歸地比較，直到最后一個單詞結(jié)束，期望獲得最大的相似性得分，以此可將日志對齊，并用一個得分矩陣記錄當前位置日志對齊的最高分數(shù)。得分函數(shù)如式（1）：

其中，L1（i）表示第一條日志的第i個單詞，L2（j）表示第二條日志的第j個單詞。S1表示第一條日志的第i個單詞與第二條日志的第j個單詞對齊；S2表示第二條日志的第j 個單詞與間隙對齊，相當于在第一條日志的第i個單詞后面添加了一個間隙；同理，S3表示第一條日志的第i個單詞與間隙對齊。如此向前迭代并更新得分矩陣，最終通過回溯得分矩陣得到對齊的日志，回溯的路徑長度就是對齊后日志的長度。對齊時，為了減少添加間隙，設(shè)定單詞與間隙匹配的得分為0。對齊后兩條日志長度相同，將Sim歸一化可得相似度，歸一化表達式如式（2）：

其中Align（L1）表示對齊后的第一條日志。

現(xiàn)在，我們還要定義match 函數(shù)。如果只考慮單詞是否相同，而不考慮語義相似性是不準確的。例如，在日志中，單詞“mistake”和“error”的含義是相似的，不考慮語義相似性的情況下，相似性度量結(jié)果為0，顯然是不合理的。YH Wang 等［13］使用Word2Vec 模型來計算詞向量用于口語檢測，Word2Vec 是用神經(jīng)網(wǎng)絡(luò)把one-hot 形式的詞向量映射為分布式詞向量，分布式詞向量隱含了詞語的信息，兩個向量夾角的余弦值可以表示詞語的相關(guān)性。于是，這里采用Google 訓(xùn)練好的Word2Vec 模型獲得兩個單詞的詞向量，若詞向量夾角的余弦值大于閾值MinSim，得分為1，否則為0。match 函數(shù)定義如式（3）：

其中Vec（L1（i））表示第一條日志第i 個詞向量，Vec（L2（j））表示第二條日志的第j個詞向量。

于是，日志間的距離可定義為

2.3.3 日志聚類

接著，闡述基于One-Pass 的日志聚類過程。定義參數(shù)MaxDistance 來表示簇中任何日志數(shù)據(jù)與簇中心之間的最大距離。因此，同一簇中任意兩條日志之間的最大距離為2 倍的MaxDistance。算法從第一條日志數(shù)據(jù)開始，逐個處理所有日志，直到最后一條。每個簇都有一個簇中心，它也是該簇的第一個成員。當任意新的日志和簇中心之間的距離小于等于MaxDistance 時，則將它插入該簇中，若與所有簇中心都不相似，就創(chuàng)建一個新簇并將其作為該簇的中心。

由于內(nèi)存中的每個簇只需保留一個簇中心，因此可以用少量的內(nèi)存來處理大量日志。One-Pass聚類算法的時間復(fù)雜度為O（n），其中n 為日志總數(shù)。由于相同簇的日志數(shù)據(jù)相似度極高，而且大多由同一應(yīng)用程序的同一段代碼生成，因此在準確聚類的前提下，算法忽略了大量的日志。當參數(shù)MaxDistance 較小時，使用One-Pass 聚類算法可以生成高密度的日志簇。One-Pass 聚類算法對日志數(shù)據(jù)的順序（通常是時間順序）具有很強的依賴性，尤其是在聚類的早期，當每個模式的第一條日志出現(xiàn)時，就會形成一個簇，這樣，短時間內(nèi)易形成多個簇，而剩余的日志將必須與多個簇中心進行比較。然而，來自同一應(yīng)用程序的日志數(shù)據(jù)往往同時出現(xiàn)多條，這樣更有利于One-Pass聚類。

One-Pass 可以在map-reduce 框架下并行執(zhí)行。在map 函數(shù)中，對于每條日志，創(chuàng)建一個鍵值對，鍵為固定值（可以為1），這是為了最終在reduce函數(shù)合并成一個日志列表，列表中的每條日志都是一個簇中心。值是經(jīng)過預(yù)處理的日志列表（初始大小為1，只有一條日志）。在reduce 函數(shù)中，合并兩個日志列表，具體來說，把包含日志多的的列表作為基本列表，然后將另一列表中的日志逐條與基本列表中的每條日志對比，當日志與基本列表中所有日志都不相似時則可作為新的簇中心添加到基本列表中，否則，忽略該日志。最后，基本列表即為合并結(jié)果。由于需要為每條日志創(chuàng)建一個鍵值對，因此map-reduce實現(xiàn)的空間復(fù)雜度是O（n），n是日志總數(shù)。

Reduce函數(shù)：

2.3.4 日志的模式發(fā)現(xiàn)

最后，給出完整的日志模式發(fā)現(xiàn)算法，將簇中的所有日志生成一個模式。我們可以先合并兩條日志，再推廣到一組日志。由于之前聚類時將每條日志依次與所有簇中心對齊，再度量距離，以確定其所屬的簇。為了避免當前日志的對齊影響后續(xù)日志的度量，所以，度量距離后，簇中心和對比的日志都應(yīng)當還原。那么，在合并兩條日志時，仍然需要先采用Smith Waterman 算法對齊日志，對齊后，兩條日志的長度相同。然后，將它們按序匹配對應(yīng)位置的字段，并生成模式。若兩個字段完全相同，那么取其中一個作為模式當前位置的字段，如果兩個字段類型相同，則取該類型作為模式當前位置的字段，否則取通配符作為模式當前位置的字段，具體算法偽代碼如下。

由于簇中日志高度聚集的特性，合并的順序不會影響模式生成的結(jié)果。因此，我們可以從簇的第一條日志開始，將它依次與第二、第三，直到最后一條日志合并，最終生成該簇的日志模式。這同樣可以采用map-reduce 框架并行合并日志。由于日志模式發(fā)現(xiàn)是在聚類之后進行的，因此我們知道每條日志的所屬簇。在map函數(shù)中，為每條日志創(chuàng)建一個鍵值對，鍵是日志的簇編號，值是日志本身。在reduce 函數(shù)中，將來自同一個簇的兩條日志合并。reduce 階段的最終輸出是每個簇的日志模式。如果忽略map-reduce 框架的開銷，在m 個機器上完全并行運行該算法，時間復(fù)雜度為，其中n是日志數(shù)，t為每個日志的平均單詞數(shù)。

3 實驗

3.1 實驗環(huán)境及數(shù)據(jù)

本文完成了三個實驗。因為HLAer 能非常準確地發(fā)現(xiàn)日志模式，所以，實驗一是將HLAer 框架作為標準，驗證本文算法的準確性。HLAer 使用OPTICS［14］算法聚類日志和UPGMA［15］算法生成日志模式。OPTICS 是基于分層的聚類算法，有兩個參數(shù)：∈和MinPts。它確保最終的簇至少有MinPts個對象，并且簇中任意兩個對象之間的最大距離小于等于∈。OPTICS 需要為每條日志計算MinPts 個最近鄰，時間復(fù)雜度為O（n2），它是高度精確的聚類算法，可以在高維空間中找到任意形狀和密度的簇。UPGMA 是一個自下而上的層次聚類算法，通過找到合并日志的最佳順序，從而合并日志生成日志模式。如果有n 條日志，每條日志平均有t 個字段，則UPGMA 的時間復(fù)雜度為O（n2t2）。由于HLAer是單機算法，為了保證比較公平性，實驗中，我們的算法也在相同配置的單機上運行。實驗環(huán)境為Windows 7，64 位操作系統(tǒng)，內(nèi)存8GB，硬盤500GB，CPU 為Inter（R）Core（TM）i5-4570 @3.20GHZ。采用四個不同的日志集，D1：2000 條Hadoop 集群日志，D2：2000 條jenkins 可持續(xù)集成系統(tǒng)的日志，D3：10000 條企業(yè)web 系統(tǒng)日志。D4：10000條企業(yè)計費系統(tǒng)日志。

實驗二比較在單機與分布式平臺下運行本文算法的時間，實驗采用三個節(jié)點，每個節(jié)點的環(huán)境為Ubuntu16.04 操作系統(tǒng)，內(nèi)存8GB，硬盤500GB，CPU 為Inter（R）Core（TM）i5-4570 @3.20GHZ。實驗數(shù)據(jù)是按照時間順序依次選取2000 條、5000 條和10000條Hadoop集群日志，以確保實驗有效性。

實驗三比較在不同個數(shù)的節(jié)點下運行算法的時間，實驗環(huán)境與實驗二相同，實驗數(shù)據(jù)是10000條Hadoop集群日志。

實驗中為了保證模式發(fā)現(xiàn)的準確性，默認將參數(shù)MaxDistance設(shè)定為0.1，MinSim設(shè)定為0.7。

3.2 評價指標

3.2.1 聚類的準確性

給定n 條日志數(shù)據(jù)S=｛L1，L2，…，Ln｝，利用OPTICS 算法進行聚類，得到r 個簇X=｛X1，X2，…，Xr｝，運行One-Pass 聚類算法，得到s 個簇Y=｛Y1，Y2，…，Ys｝。OPTICS每個簇的日志條數(shù)為a=｛a1，a2，…，ar｝，One-Pass 算法每個簇的日志條數(shù)為b=｛b1，b2，…，b｝s，記其中i∈1,...,r, j∈1,...,s，表示被放入在X 中第i 個類且在Y 中第j 個類的日志條數(shù)，那么，聚類的準確性定義為

3.2.2 模式發(fā)現(xiàn)的準確性

我們通過OPTICS 和One-Pass 對日志數(shù)據(jù)進行聚類，然后給每個簇用UPGMA 和順序合并的模式發(fā)現(xiàn)算法分別生成一個模式。我們逐個字段比較兩個算法生成的模式。模式發(fā)現(xiàn)的準確性定義為

其中，Acci是第i 個簇的模式發(fā)現(xiàn)的準確度，是兩個算法在第i個簇上生成的兩個模式之間匹配成功的字段占所有字段的比率，Sizei是第i 個簇中的日志數(shù)量。

3.3 實驗結(jié)果及分析

為了驗證本文提出的One-Pass 聚類算法和順序合并日志生成模式的準確性，快速以及內(nèi)存高效，利用上述日志集做出了相關(guān)實驗。

1）由表1可見，基于One-Pass思想的日志聚類和順序合并的模式發(fā)現(xiàn)方法與HLAer的OPTICS及UPGMA 相比，在D1，D2 兩個2000 條的日志集上聚類準確率高達98%以上，模式發(fā)現(xiàn)的準確率也在97%以上，在D3，D4 兩個10000 條日志集上聚類準確率在96%左右，模式發(fā)現(xiàn)的準確率在94%左右，且內(nèi)存開銷遠遠低于HLAer，運行時間大約是HLAer 的10%。說明本文提出的算法準確、快速、內(nèi)存高效。

2）由表2 可見，在不同規(guī)模的日志集上，采用三個節(jié)點搭建的Hadoop 分布式集群運行算法。當只有2000 條日志時，執(zhí)行算法本身所需的時間不長，由于Map-Ruduce框架的開銷，分布式環(huán)境相比單機來說，在運行時間上優(yōu)勢不明顯；隨著數(shù)據(jù)量的增大，分布式環(huán)境在執(zhí)行效率上體現(xiàn)出了優(yōu)勢。

3）由圖3 可見，在相同規(guī)模的日志集上，隨著節(jié)點數(shù)目的增加，算法的執(zhí)行效率也得到了相應(yīng)的提高。但是，當節(jié)點數(shù)目超過8 個以后，執(zhí)行效率提高的越來越少，由此可見，為了最大化資源利用率，需根據(jù)數(shù)據(jù)集的大小選擇合適的節(jié)點數(shù)目。

表1 單機版的順序日志聚類和模式識別算法與HLAer算法比較

表2 單機與分布式環(huán)境下算法的運行時間（單位：s）

圖3 不同個數(shù)節(jié)點的運行時間

4 結(jié)語

本文針對大量異構(gòu)日志進行聚類和模式發(fā)現(xiàn)的主要挑戰(zhàn)，根據(jù)日志數(shù)據(jù)的特點，提出了一種基于Hadoop 平臺的日志模式發(fā)現(xiàn)方法，在四個不同規(guī)模的日志數(shù)據(jù)集上的實驗結(jié)果表明了該方法在準確聚類和模式發(fā)現(xiàn)的前提下，內(nèi)存開銷和運行時間大大降低。該方法具有無監(jiān)督、可擴展、快速，內(nèi)存高效且準確的特點，可為企業(yè)處理大規(guī)模日志數(shù)據(jù)提供一種可行的解決方案。當然，在預(yù)處理階段，對于大量異構(gòu)日志，該方法仍然需要先驗知識和人工干預(yù)，這個問題有待進一步的研究。