在現實場景中，業務程序輸出的日誌往往規模龐大並且類型紛繁複雜。我們在查詢和查看這些日誌時，平鋪的日誌列表會讓我們目不暇接，難以快速聚焦找到重要的日誌條目。

在觀測雲中，我們在日誌頁面提供了聚類分析功能，可以快速聚合相似的日誌文本，幫助你全覽不同類型的日誌。這個功能背後就由基於 Drain 的改良算法驅動。

快速理解 Drain 算法

根據 logparser 項目提供的 Benchmark 數據和論文原文可知，Drain 在一眾日誌聚類算法中準確度和性能都幾乎是最好的，所以我們選擇基於 Drain 算法來實現產品功能。

在這裏我們嘗試根據 Drain 論文來總結和梳理一下算法的主要邏輯：

1、首先對日誌進行業務預處理，將一些常見的日誌模式替換為佔位符，比如時間、用户 ID、IP 等

2、對預處理的數據進行分詞，並在 Drain 的搜索樹的第一層找到對應單詞數量的子節點

3、再逐個根據日誌中的單詞序列，在下層的前綴搜索樹上找到對應的日誌聚類桶

4、遍歷對應前綴樹指向的日誌聚類桶，分別判斷當前日誌跟對應日誌類的相似度是否達到閾值

• 相似度算法：兩條日誌從左往右，一個一個單詞看相不相同，統計相同單詞的數量，除以日誌長度就得到相似度

5、如果相似則將當前的日誌加入該類別，不相似則創建新的類別並加入到前綴樹中

我們回顧一下上述的處理流程：

1、佔位預處理的目標是為了將日誌中最常見的變量替換為相同的佔位符，來提升相同單詞的比例，以提升最終文本的相似度

2、Drain 第一層的按照單詞數區分的子樹和後續根據前綴樹拆分的子樹目標都是縮小相似度計算的開銷，我們只用跟最可能相似的日誌組來對比計算

相信到這裏，你已經基本理解了 Drain 算法的基本設計思路。這個算法思路總體並不複雜，固定深度的查找樹、簡單的相似度匹配算法都讓算法的運行非常高效。

改良 1：佔位處理後置，並提升處理效率

我們在最初的使用中按照論文的描述給日誌增加了一些常見的日誌模式佔位符，比如：

• 時間： [0-9]{1,}:[0-9]{1,}:[0-9]{1,}.?[0-9]{1,}?
• IPv4： \\d{1,3}\\.\\d{1,3}\\.\\d{1,3}\\.\\d{1,3}
• Hex： 0x[a-f0-9A-F]+
• 數字： -?[0-9]{1,}.?[0-9]*
• ID： [0-9a-f]{4,}

眾所周知，時間在日誌中輸出的格式是可能有非常多種類型的，我這裏只添加了最簡單的一種，還有 IPv6 因為正則表達式的規則過於複雜也還沒加。

在初步添加上述少量的佔位符匹配之後，我們就發現 Drain 算法的匹配效率顯著下降。

在我們內部一個 1w 行的測試數據集上，完成訓練的時間由 80ms 增長到 2.2s，匹配效率降低約 30 倍，通過 CPU Profiler 調用樹可以觀察到性能的主要開銷都在正則表達式的替換上。

那麼不進行佔位處理可以嗎？不可以，這些變量會嚴重影響日誌相似度的判定。

那麼可以換更高效的正則表達式庫嗎？我們嘗試了一些常見的優化方案，但提升的幅度沒有這麼顯著。

我們使用多個正則表達式對全部日誌的每個單詞都進行了一遍正則的匹配，這個的開銷自然是不低的。那這個完整的匹配是必須的嗎？哪些路徑的正則匹配是必須的？

前面我們已經強調過，我們期望的通過佔位處理之後不影響日誌相似度的判斷。那麼我們其實只需要在日誌相似度運算的時候對必要的單詞來做這個正則匹配就好了。

假設當前日誌組的模板變量是：Just A Log Template <Number> ，現在我們有一個日誌 Just A Log Template 123 需要跟這個模板對比相似度，我們在逐個單詞進行對比相似度時，只需要判斷日誌的最後一個單詞是否匹配中 <Number> 佔位符對應的正則表達式，我們不用判斷這個單詞是否能匹配中其他的佔位符，也不用關注其他的單詞是什麼情況，更不必要提前對這個日誌進行完整佔位處理。

Drain 本身通過多層的分桶降低了我們日誌需要判斷的聚類組的數量，另外我們根據日誌組的模板變量確定了需要進行哪種佔位符的判斷，所以實際的匹配開銷經過這兩重剪枝就大大降低了。在剛才提到的數據集下，我們把佔位符的匹配後置，完成訓練的時間就降低到只有 120ms 左右了。

改良 2：提升佔位處理通用性

在通過剪枝解決了匹配效率問題之後我們還關注到當前的佔位處理的邏輯其實不太通用，IPv4、IPv6、超多種時間格式、用户自行輸出的結構體、JSON 文本等等其實結構非常複雜，根據不同的使用習慣不同也難以羅列完整，維護也比較複雜。

我們最終的方案是嘗試將常見的符號比如 :.," 等前後添加空格，在分詞時就可以把這些符號拆分成單獨的單詞，這樣比如一個 IPv4 的地址會被拆分為 <Number>:<Number>:<Number>:<Number> ，一個 IPv6 地址會被拆分為 <ID> 和 : 子元素，時間格式會被拆分為數個 <Number> 和 : 。

按這種邏輯，我們最終只維護了三個基本的佔位元素，分別是：

• 數字： [-+]?[0-9]+
• Hex： 0x[a-f0-9A-F]+
• ID： [a-f0-9A-F]{4,}

這樣除了維護更簡單，常見的佔位格式都不用維護，而且對 JSON 文本的支持也更友好了，可以將其中的 KV 都完全拆分。

改良 3：支持變長日誌聚類

回憶一下 Drain 的處理流程，我們在知道日誌長度的時候就直接劃分子樹了。那麼顯而易見的，Drain 對變長的日誌支持效果都不會太好。

舉個實際點的例子，兩個包含 UA 的請求日誌：

1、[28/Aug/2022:07:01:36 +0800] "GET / HTTP/1.1" 200 "Mozilla/5.0 (Linux; Android 12; PEEM00 Build/RKQ1.211119.001; wv) AppleWebKit/537.36 (KHTML, like Gecko) Version/4.0 Chrome/97.0.4692.98 Mobile Safari/537.36"

2、[28/Aug/2022:07:50:18 +0800] "GET / HTTP/1.1" 200 "Mozilla/5.0 (Linux; Android 9; MI 8 Build/PQ3A.190801.002; wv) AppleWebKit/537.36 (KHTML, like Gecko) Version/4.0 Chrome/87.0.4280.101 Mobile Safari/537.36"

這兩條日誌的長度是不一樣的，一個的手機型號是 PEEM00 一個的手機型號是 MI 8 。所以雖然兩個日誌非常相像，但還是不會被聚合到同一個類別中。

這合理嗎？顯然是不合理的。

所以我們給 Drain 額外增加了一個相鄰長度聚類組的相似度判斷邏輯。同時要注意到，之前我們的相似度判斷算法是逐個單詞匹配的，當這裏單詞數不一樣的時候，中間可能會錯位，導致相似度計算可能會很嚴重偏低，我們原有的算法已經不太適用這種情況了。

常見的文本相似度算法都不限定兩個文本單詞長度必須相等，比如計算歐幾里得距離、曼哈頓距離、明可夫斯基距離、餘弦相似度等。這裏我們最終選用了 minhash 算法，我們可以提前對每個日誌組計算好特徵向量，在判斷匹配時給日誌行計算雅卡爾距離時可以更高效。

同時要注意的是，如果你的數據集是請求日誌這樣的數據，單詞的長度可能都差不多，並且不同的日誌組本身的相似度其實已經很高了。這樣的數據集下，你不能只優先匹配相鄰長度的日誌組，應該優先把前後一定長度範圍的全部日誌組放在一個大池子裏來找到最優解。

總結

經過我們對 Drain 的深入剖析和改良，新算法的流程是這樣的：

1、直接對日誌文本進行分詞，並在 Drain 的搜索樹的第一層找到對應單詞數量的子節點

2、再逐個根據日誌中的單詞序列，在下層的前綴搜索樹上找到對應的日誌聚類桶

3、遍歷對應前綴樹指向的日誌聚類桶，分別判斷當前日誌跟對應日誌類的相似度是否達到閾值

• 相似度算法：兩條日誌從左往右依次對比，如果類別模板中對應位置是佔位符，則使用佔位符對應的正則表達式匹配原始文本，跟原有算法一樣計算相似度

4、如果相似則將當前的日誌加入該類別，不相似則拿出來前後一定範圍長度的全部日誌類別，對比這些日誌於當前的日誌的 minhash 的笛卡爾距離，判斷相似度是否達到閾值

5、如果前面兩種相似度判斷都失敗，則創建新的日誌分類，此時注意需要對現有的日誌進行完整的佔位符替換，最後將創建的新的日誌類別加入前綴搜索樹中

經過如上的處理流程，該算法對於定長、變長、JSON 等格式的日誌聚合表現相比於原版 Drain 都更加優異，同時也能保持極高的匹配效率。