Loki 是 Grafana 的開源日誌產品，它基於 index-free 理念設計，這種設計只對日誌的元資訊（標籤）進行輕量級索引，而對日誌內容不做任何索引直接儲存。這種方案有以下優點：
-
日誌寫入輕量：因為沒有對日誌內容構建任何索引，日誌寫入速度非常快，資源使用率非常低，通常可以達到單核 25MB/s 的速度；
-
儲存資料量小：不需要儲存巨大的索引，而其他有倒排索引的系統，索引與日誌的大小比例通常能達到 1:1；
成本從寫入側轉到查詢側：針對日誌寫多讀少的特點，透過比較少的資源快速寫入日誌，然後部署龐大的查詢叢集，利用物件儲存的大吞吐能力（可達幾十 GB/s），進行暴力下載和搜尋；
Loki 的資料是按標籤組織儲存的，同一組相同標籤值的日誌存在同一組檔案中，輸入應用標籤就會排除掉其他應用的資料。因此在日誌總量大但每個應用日誌量比較均衡時，Loki 非常省成本，能達到 ES 的 20%。
但是如果有某個應用日誌量達到 TB 級時，Loki 對這種長板應用的查詢會變得很吃力 [1]，特別對“大海撈針”式的查詢，比如從幾十 TB 日誌中搜索一條 tid 或 requestId。而傳統有倒排索引的系統處理這種查詢耗時通常都小於 1s。
社群也有不少人提出類似問題，Loki 團隊一直在思考好的解決方案，但我們在 2022 年上線了 Loki 後就開始迫切需要解決這個問題。
為此我們經過了幾個階段的探索，可以簡單概括如下：
第一階段：提取 tid 等高基數字段寫入 redis 布隆過濾器
第二階段：研發基於 SSD 儲存的 bloom 索引 BBF 1.0，寫入更多常用查詢欄位
第三階段：設計研發基於 S3 的大規模全文分詞 bloom 索引 BBF 2.0
在思考怎麼加速 tid 這種高基數字段查詢時，最容易想到的思路是減少不必要的資料檢索量，但是我們不能用倒排索引，因為這樣會回到舊系統的思路上，Loki 的優勢也會消失。
要做到比倒排索引更輕量，我很容易想到了布隆過濾器，因此 2022 年下半年我增強了 Loki 的寫入和查詢鏈路，使用 redis bloom-filter 來加速查詢。核心思路是對每十分鐘的時間片建立一個布隆過濾器，將這段時間需要索引的欄位值寫入。查詢時根據關鍵字過濾時間片來縮小搜尋範圍。
布隆過濾器是個機率資料結構，它有一定的誤判率，當它返回存在時有可能不存在，但返回結果不存在則一定不存在，因此可以用它先過濾掉一部分不包含查詢關鍵字的資料。
寫入鏈路的改造包括幾個部分：
1）擴充套件 Loki 寫入資料協議，從日誌內容中提取出相關的欄位放在 attachment 中寫入 Loki；
2）改造 Loki 寫入鏈路，將 attachment 欄位按 bloom-filter 分組後批次寫入過濾器；
我們按每個應用每 10 分鐘建立一個過濾器，過濾器名字格式為：${tenantId}_${app}_202503041910
查詢時，根據欄位和時間先從布隆過濾器查詢，過濾掉不包含對應 value 的時間片，以此減小搜尋的時間範圍：
比如：如果取子查詢的結束時間點按 10 分鐘取整得到“202503041910”，用查詢條件中的關鍵字去名為 “${tenant}_${app}_202503041910” 的 bloom-filter 中過濾，如果關鍵字在該過濾器中不存在，那麼這個子查詢就不需要執行，如果返回存在，則拉取日誌檔案資料進行搜尋。
1）寫入鏈路在加入 attachment 出現異常時，向 redis 中設定 bloom-filter 分片為髒資料的標識，比如：Dirty_myapp_2769901；
2）查詢時如果發現有該標識則降級為全文查詢；
在這個版本上線後，我們隨後又進行了一個版本迭代，將時間片粒度的過濾器最佳化為檔案 id 粒度。寫入時仍然按時間片建立 bloom-filter，然後在寫入欄位值時在每個值後面拼接上所在日誌檔案的 id（Loki 中叫 chunkId），即最終寫入的 key 是:
key + "_" + chunkIdkey + "_" + chunkId查詢時也同樣拼接 chunkId 去過濾，這樣我們的索引過濾的物件從時間片變成了 chunkId，最終過濾後的資料量更小，可能只有幾個 chunk 檔案。
第一階段最佳化後從 20TB 日誌中查詢 tid 的耗時從原來的幾分鐘降低到了 3s 內，搜尋的資料量降到了幾百 MB。
前面實現的 redis 布隆過濾器索引在查詢效能上已經能接近全文索引，滿足常見查詢場景。但帶來的問題是 redis 成本很高，如果要給更多欄位建索引則會因資源成本問題變得不切實際。
於是我想能不能將布隆過濾器儲存在磁碟中？在查詢資料的過程中我從一篇論文 [1] 中找到靈感，因此考慮結合該論文和我們的場景設計一種基於 SSD 的布隆過濾器索引，稱之為 BBF 1.0。
SSD 相比記憶體，I/O 速度上差了一到兩個數量級。但布隆過濾器寫入和查詢的 key 都是明確的，不存在字首字尾讀寫情況，我們可以將布隆過濾器在儲存上設計成多個分片分別儲存：
-
寫入時：透過一個 hash 函式將需寫入的 key 對映到其中的一個分片上寫入，分片在記憶體中緩衝，定期刷盤寫到 SSD 中；
-
查詢時：透過 hash 計算定位到 key 所在的具體分片，然後從 SSD 讀取對應的這個分片即可；
這種分片機制可以有效減少查詢時從 SSD 讀取的資料量，同時採取批次寫入和讀取資料短暫快取的方法，使使用者最終對延時增加無感知。
-
當日志塊刷儲存時，批次寫入其中的所有索引欄位值到對應的布隆過濾器中；
-
寫入布隆過濾器時先根據欄位值 hash 定位到過濾器的某個分片，然後寫入該分片中；
-
查詢時先根據關鍵字的 hash 值定位到分片，只從 SSD 載入該分片到記憶體；
-
判斷時將關鍵字和每個 chunkId 進行拼接後去過濾器分片中過濾，以確定這個 chunk 是否可能包含關鍵字，如果不包含那麼這個 chunk 檔案就不需要查詢；
-
結構：每個過濾器由一個 meta 和多個“子過濾器”組成；
-
儲存：meta 在記憶體快取，用來記錄 shard 數量等元資訊，子過濾器存在 SSD 檔案中，裡面就是布隆過濾器的位陣列；
-
寫入：寫入時過濾器的第一個 hash 函式用來將 field value 對映到某一個“子過濾器”上；
-
查詢：先 field value 處於哪個“子過濾器”上，然後從 SSD 中載入這個“子過濾器”進行過濾即可；
如果布隆過濾器寫入過多的 key 時會導致它的誤判率上升，因此當寫入值數量計數超過預設值時需要擴容，擴容透過建立新的子過濾器並新增字尾實現。
比如：如果 filter name 為 “202308090110_fake_tid_myapp”，key hash 計算 shard 分片值為 1，當寫入字串數量超過預設容量時，新建立同樣大小的 filter，建立後該 key 對應的子過濾器檔案列表如下：
202308090110_fake_tid_myapp_s1202308090110_fake_tid_myapp_s1_1預設情況下以 filter name 作為儲存檔名，以 "default" 作為目錄名；當用戶傳入了 prefix 時，用 prefix 作為目錄名。目錄樹如下所示：
// prefix 使用每 10 分鐘的時間 bucket（202308111210）時./202308111210202308111210_fake_tid_myapp_meta.json202308111210_fake_tid_myapp_s0202308111210_fake_tid_myapp_s0_1202308111210_fake_tid_myapp_s1202308111210_fake_tid_myapp_s1_1 ...202308111210_fake_tid_myapp_s3000202308111210_fake_tid_myapp_s3000_1資料寫入時先在記憶體中構建布隆過濾器，一段時間後寫入 SSD，隨後在有新資料需要繼續寫入時先在記憶體快取資料，然後定期更新寫入，相關動作的時間關係如下圖所示：
-
t0-t1：這裡的 BBF 是按每 10 分鐘的粒度建立的，即 t0-t1 這段時間所有資料寫入同一個 BBF 索引（BBF 索引中有很多分片）；
-
t2：在每個 BBF 所屬的 10 分鐘視窗期過後的一段時間（flush_delay），將 BBF flush 至 SSD 上；
-
t3：如果在 BBF 刷盤後又有新資料請求寫入，則將新資料在記憶體中緩衝一段時間（append_period）後重新載入 BBF 進行批次追加寫入，防止反覆載入和刷盤；
-
max_chunk_age：這是日誌在 Loki Ingester 中快取的最大時長，超過這個時間的日誌塊將會立即刷盤，因此 BBF 索引在最差的情況下會在 max_chunk_age 時間跨度內被多次追加寫入；
以某個資料中心查詢 tid 為例，每天的列舉數量大約 44 億，在容錯率設定為 0.001 時過濾器大小約為 7.5GB[3]，假設 shard 取 100，Buffer 後每個 SSD I/O 處理 10 個查詢請求，這時需要讀取的 SSD 檔案大小為：
7.5GB / 100 / 10 = 7.5MBSSD 讀取速度按 250MB/s 計算，一次查詢需要：30ms。當然我們可以增大分片數量來進一步減少每次載入的資料量。
另外還有叢集管理和容錯設計就不詳細展開，做法大同小異。
BBF 1.0 索引落地後，我們用同等成本支援了比原來大 50 倍的索引容量，使用者體驗到的查詢延遲和 redis 相比無差別。
前面設計的 BBF 1.0 雖然支援了更多欄位寫入，但如果要擴充套件到全文分詞 bloom 索引這種更大規模場景仍然存在問題：
-
SSD 頻寬限制：全文分詞場景下 bloom 索引大小大約是原始日誌的 3%，即 20TB 日誌對應 600GB 的布隆過濾器。假設分片數取 3000，一個查詢分詞後有 10 個 key，那麼一次查詢需要從 SSD 載入的資料量是 600GB / 3000 10 ≈ 18GB，頻寬 250MB 的 SSD 讀取耗時為 18 * 1024/250 = 72 秒。
-
Ingster 記憶體問題：1.0 版本在日誌寫入 Loki 時就把抽取出的相關欄位暫存在 Ingester 元件記憶體中，直到日誌塊刷儲存時才寫入索引（因為直到刷儲存時才能確定日誌塊的 chunkId），在全文分詞場景中，要把所有分詞後的 key 在記憶體中快取顯然太昂貴；
-
跨可用區流量問題：因為我們的寫入鏈路是多可用區隔離部署的，如果要將一個日誌塊中內容的所有分詞寫入不同 BBF 節點負責的不同 shard 中，勢必會有大量的跨區流量，一些雲服務廠商會對跨區流量收取高昂的費用；
另外為了滿足叢集高效能與可擴充套件的要求，我們還有兩個問題要考慮：
-
分詞計算任務協調：多個節點按什麼規則劃分對日誌內容的分詞計算任務；
-
索引的分片管理協調：節點間如何分工協作管理所有分片，根本問題是如何決定誰負責哪些分片的寫入緩衝；
巧合的是這個時候 Loki 團隊也在基於布隆過濾器開發他們的索引，我們先來看看 Loki 團隊的方案：
如上圖所示，Loki 增加了 Bloom compactor 節點，多個 compactor 節點按 stream 分段協調任務分配，每個節點負責一段 stream 中日誌的索引，索引構建中會生成一系列的 Blocks 儲存在 SSD 上。
stream 是多個標籤的唯一組合，Loki 按 stream 組織日誌寫入，比如共有 3 個標籤，他們的值有 100 種組合就會有 100 個 stream
可以看出，社群版本只對資料處理任務進行了並行處理，資料儲存上是簡單的累積，並沒有在減少查詢載入資料量方面做最佳化，因此查詢時需要掛載非常多 SSD 盤來提高吞吐能力，資料達到一定程度就會因為成本問題無法擴充套件。
社群這個方案在試用一段時間後發現規模難以擴充套件，於是將原來的全文 Ngram 分詞方式改成了抽取部分高基數字段放到 structured metadata 中然後進行分詞索引，細心的讀者有沒有發現，社群修改後的方案和我們階段二的非常像。
這種方案的不足細分起來可以羅列如下：
-
資源消耗高：Loki 文件描述索引構建過程大約每核每秒能處理 4MB 資料，對一個每秒 1GB 的叢集，最少需要 256 核，考慮高峰期會更高；
-
索引延時大：根據 Streams 來迴圈構建的缺點是 Streams 量可能非常大，新日誌索引構建的延遲等於一輪 Streams 處理完成的時間；
-
查詢效能差：因為沒有做資料儲存結構的最佳化，每次查詢可能要載入所有 bloom 資料，因此只能做部分欄位級別的索引；
2024 年上半年我在測試社群方案的基礎上對它進行了儲存結構改造，將生成的 Block 進行了類似我們階段二的 Hash 分片式儲存以最佳化查詢速度，經過半年改造後實測查詢速度是沒問題的，但是在合理成本的資源條件下索引寫入速度很慢，每輪延時達到 1 小時以上。於是放棄社群方案回到自己的設計上來。
-
Ingester 在將日誌塊檔案刷儲存時，同時將 chunkId 傳送到 BBF Computer 節點，這部分會有跨區流量，但是因為只發送檔案 id，跨區流量比較小；
-
BBF Computer 節點：BBF Computer 節點主要負責分詞計算任務，接收到 chunkId 後，從 S3 重新拉取日誌檔案進行分詞計算，然後將分詞後的 key 傳送到對應的 BBF Index 節點，傳送規則是先根據 key hash 對映到某個分片，然後根據分片 hash 對映到某個 BBF Index 節點；
-
BBF Index 節點：BBF Index 節點負責 bloom 索引分片的緩衝和儲存，每個節點負責哪些分片是透過 Consul 叢集發現後 hash 計算得到的；
叢集管理主要要解決 BBF Index 叢集的擴容縮容問題，因為 bloom 索引分片是在 BBF Index 記憶體中緩衝的，如果叢集擴容， hash 結果發生改變後可能出現一個分片現在在兩個節點上都有的情況。
叢集縮容後，雖然資料會寫入 S3 儲存，但是因為節點數量發生變化導致對映關係變化，其他節點對分片的管理還是會出現紊亂。
解決辦法是在建立 BBF 所有分片後，記錄當前時間 bucket 的節點列表，寫到 Consul 中。叢集擴容後，新節點只對下一個時間 bucket 新建立的 BBF 生效。
叢集縮容時，先執行下線介面，此時下線的節點不會接受新分片的建立，但是仍然會完成當前負責分片的寫入，直到超出最大時間視窗不會再有該 bucket 的資料寫入方可下線服務。
我們的索引在時間維度上是按時間 bucket 拆分的，比如：每 10 分鐘一個 BBF。理想情況下正在寫入的索引應該聚集在最近一到兩個 bucket 上，但是實際情況可能會出現寫入堆積，或者 Ingester 刷盤資料出現下面的亂序情況：
這可能導致記憶體中 bucket 數量增長得很大，特別在寫入出現堆積後重新恢復時，可能不得不成倍擴容索引節點資源才能追上正常寫入。
要控制 BBF bucket 長度很容易想到用 window 機制，但在實現了本地 window 後，線上試執行發現出現了不同節點 window 元素不一樣的情況，導致寫入速度嚴重下降。
因此將方案升級為基於 Consul 的分散式 window，consul 中儲存的 key 結構如下：
# 當只有一個元素時./window/202503030240/prod-bbf-index-c-1./window/202503030240/prod-bbf-index-c-2./window/202503030240/prod-bbf-index-c-3./window/202503030240/prod-bbf-index-c-4# 當 window 滿了且有多個元素進入候選佇列時./candidate/202503030250./candidate/202503030310-
擴充套件 window 時，每個 BBF Index 節點都會在 /window 下面建立包含節點主機名的 bucket key。
-
縮小 window 時，當某個節點縮小 window 時，只刪除該節點對應的 bucket key，當 bucket 下所有節點都刪除掉時才認為該 bucket 在所有節點都已寫入完成，此時才會刪除該 bucket。如下圖所示：
在 bucket 長度失控與多節點 window 不一致問題都得到解決後，又發現在寫入堆積後一些較早的分片一直搶佔不到 window 空間，出現了飢餓現象。於是我又在 window 基礎上增加了候選佇列，候選佇列每次變更時進行排序，當 window 有空閒空間時，將候選佇列中最小的 bucket 元素取出加入 window，解決排隊等待飢餓問題。
雖然有了完善的 window 和 candidate 機制，但是當寫入 bucket 出現嚴重亂序時，因為每個 bucket 在記憶體中是有最小 buffer 時間的，因此當 window 滿了以後只能等待舊的 BBF 刷盤。為了提高堆積時的寫入速度避免卡在等待 window 空間上，我額外對寫入的 chunkId 進行了整流。
具體做法是批次讀取一批 chunkId，然後按 bucket 分組排序，再按 bucket 順序逐個批次寫入，這樣顯著提高了堆積時可能受 window 容量影響的寫入速度。
這個方案的設計中：
-
讓 Ingester 只發送 chunkId 給 Bloom Computer 節點減少了跨區流量；
-
透過 Computer 節點重新拉取 chunk 進行計算解決了 Ingester 記憶體問題（S3 Get 很便宜）；
-
將計算型的 BBF Computer 和記憶體型的 BBF Index 節點分離的設計使查詢儘量少的受到寫入的影響；
-
同時解決了“分詞計算任務”與“索引寫入任務”的分配協調，並延續了階段二中透過儲存設計的最佳化來減少查詢資料量方案的優點；
-
引入 sticky ring 解決叢集管理問題；
-
引入分散式 window 機制最佳化索引寫入的記憶體控制；
-
使用整流策略提高索引堆積後恢復時的寫入速度；
這個方案上線後，實現了用社群版本 1/5 的資源支援了全文分詞 bloom 索引，索引容量比階段二提升了 30 倍。寫入延時從社群版的大約 1 小時降低到秒級。查詢需要載入的資料量是社群的幾千分之一，耗時與方案二基本一致:
-
400 核查詢器 + 32GB 索引節點：從 20TB 資料中查詢不同頻率的資料 P95 耗時約 3 秒，查詢 7 天共 140TB 資料 P95 耗時約 12 秒；
-
200 核查詢器 + 32GB 索引節點：查詢低頻關鍵字耗時與 400 核相當，查詢高頻與中頻關鍵字時耗時大約增長一倍。表面後續透過最佳化高頻關鍵字索引判斷過程可進一步最佳化效能；
經過 3 年三個大版本的迭代，我們實現了全文分詞的輕量級 Bloom 索引，解決了 Loki 在大規模日誌量下的查詢效能問題。我們的方案與社群方案在部分思路上不謀而合，但在設計上又走出了不同的路徑。
從上面結果可以看出瓶頸其實在索引節點中，適當增加資源可以進一步提升查詢效能。效能部分還可以做的最佳化可能包括：
-
向量化計算提高索引節點判斷速度 ;
-
高頻詞自動降級最佳化 ;
-
支援可配置的多粒度 Bloom 索引，比如：時間片和 chunkId;
[1] Loki Cloud 為了滿足雲服務大客戶的查詢效能要求，就運維了一個高達 50TB 的 Memcached 快取叢集，https://grafana.com/blog/2023/08/23/how-we-scaled-grafana-cloud-logs-memcached-cluster-to-50tb-and-improved-reliability/
[2] 《Buffered Bloom Filters on Solid State Storage》，https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=da6a07944d97723d6c154d76609b5c20a3636f9a
[3] Bloom filter calculator, https://hur.st/bloomfilter/
原文同時發表於：
