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

昂 鑫 徐 建 張 宏

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

1 引言

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

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

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

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

2 快速的日志模式發現

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

2.1 日志實例和特性分析

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

1）日志數據的語法結構弱。為了記錄應用程序或系統的運行狀態，日志通常是簡短的，且不遵循標準的語法結構，因此NLP解析器無法在日志中識別有意義的語法。

2）日志的詞匯量有限，但詞匯統計呈偏斜分布，某些詞出現的頻率高，有長尾現象。

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

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

圖1 jenkins可持續集成系統的日志

圖2 日志模式發現框架

2.2 框架

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

2.3 分布式的日志模式發現方法

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

2.3.1 標記和類型檢測

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

2.3.2 日志的相似性度量

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

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

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

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

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

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

2.3.3 日志聚類

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

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

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

Reduce函數：

2.3.4 日志的模式發現

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

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

3 實驗

3.1 實驗環境及數據

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

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

實驗三比較在不同個數的節點下運行算法的時間，實驗環境與實驗二相同，實驗數據是10000條Hadoop集群日志。

實驗中為了保證模式發現的準確性，默認將參數MaxDistance設定為0.1，MinSim設定為0.7。

3.2 評價指標

3.2.1 聚類的準確性

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

3.2.2 模式發現的準確性

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

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

3.3 實驗結果及分析

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

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

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

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

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

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

圖3 不同個數節點的運行時間

4 結語

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