我在上篇文章Apache Pulsar 的架構(gòu)設(shè)計(jì)中介紹了 Pulsar 存算分離的架構(gòu)，其中 broker 只負(fù)責(zé)計(jì)算，由 BookKeeper 負(fù)責(zé)底層的存儲(chǔ)，我還畫了這樣一張圖說(shuō)明 BookKeeper 讀寫分離的設(shè)計(jì)：

但是再深究下去，memtable具體是以怎樣的格式持久化到磁盤上的呢？又是用什么算法高效查找一條消息的呢？

通過(guò)學(xué)習(xí)相關(guān)資料，我發(fā)現(xiàn) Apache BookKeeper 底層存儲(chǔ)引擎用的是 Facebook 開(kāi)源的 RocksDB，而 RocksDB 又是基于 Google 開(kāi)源的 LevelDB 改造的，而 LevelDB 的核心是一個(gè)叫做 LSM 樹(shù)（Log Structured Merge Tree）的結(jié)構(gòu)。

LevelDB 整個(gè)庫(kù)的代碼只有幾百 KB，所以我去研究了 LSM 樹(shù)的代碼實(shí)現(xiàn)，總結(jié)了這篇文章，帶你了解 LSM 樹(shù)的設(shè)計(jì)原理。

什么是 LSM 樹(shù)呢？如果說(shuō)到 B+ 樹(shù)大家應(yīng)該不陌生，像 MySQL 這樣的關(guān)系型數(shù)據(jù)庫(kù)底層一般用 B+ 樹(shù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)。LSM 樹(shù)其實(shí)就是另一種存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)，常見(jiàn)于日志存儲(chǔ)系統(tǒng)中。

首先，我們先來(lái)聊聊存儲(chǔ)系統(tǒng)。

內(nèi)存數(shù)據(jù)結(jié)構(gòu) vs 磁盤數(shù)據(jù)結(jié)構(gòu)

正如前文學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的框架思維所說(shuō)，一切數(shù)據(jù)結(jié)構(gòu)從根本上講都是增刪查改，但在具體實(shí)現(xiàn)上，磁盤數(shù)據(jù)結(jié)構(gòu)和內(nèi)存數(shù)據(jù)結(jié)構(gòu)會(huì)有比較大的差異。

內(nèi)存數(shù)據(jù)結(jié)構(gòu)你直接 new 一個(gè)出來(lái)就行了，不用關(guān)心這個(gè)結(jié)構(gòu)在內(nèi)存中是如何布局的，這些都由操作系統(tǒng)和編程語(yǔ)言代勞了。

但磁盤就不一樣，考慮到磁盤讀取的操作效率相對(duì)比較低，且每次只能讀取固定大小的磁盤數(shù)據(jù)，你要自己設(shè)計(jì)數(shù)據(jù)的存儲(chǔ)布局，規(guī)定每個(gè)字節(jié)存什么信息，然后基于你設(shè)計(jì)的存儲(chǔ)布局實(shí)現(xiàn)增刪查改的 API，比較枯燥瑣碎。

比如說(shuō)，學(xué)過(guò) MySQL 的話應(yīng)該比較熟悉 B+ 樹(shù)結(jié)構(gòu)，但你肯定不容易看懂 B+ 樹(shù)的代碼。因?yàn)?B+ 樹(shù)是磁盤數(shù)據(jù)結(jié)構(gòu)，雖然原理上可以理解為 BST 的加強(qiáng)版，但考慮到數(shù)據(jù)文件格式的設(shè)計(jì)，真正的代碼實(shí)現(xiàn)非常復(fù)雜。

所以一般來(lái)說(shuō)，我們了解磁盤數(shù)據(jù)結(jié)構(gòu)的原理，了解各個(gè)操作的時(shí)間復(fù)雜度就可以了，沒(méi)必要特別糾結(jié)它的具體實(shí)現(xiàn)。

數(shù)據(jù)可變 vs 數(shù)據(jù)不可變

存儲(chǔ)結(jié)構(gòu)可以粗略分為兩類：數(shù)據(jù)可變的和數(shù)據(jù)不可變的。所謂可變，就是說(shuō)已經(jīng)插入的數(shù)據(jù)還可以原地進(jìn)行修改，不可變就是說(shuō)已經(jīng)插入的數(shù)據(jù)就不能再修改了。

B 樹(shù)是數(shù)據(jù)可變的代表結(jié)構(gòu)（B+ 樹(shù)等衍生結(jié)構(gòu)都?xì)w為 B 樹(shù)一族）。你就想想 BST 吧，數(shù)據(jù)存在節(jié)點(diǎn)上，我們可以隨意插入、刪除、修改 BST 中的節(jié)點(diǎn)。

B 樹(shù)的理論增刪查改性能和 BST 一樣都是 logN，但 B 樹(shù)的實(shí)際寫入效率并不是特別高：

一方面是因?yàn)?B 樹(shù)需要分裂合并等操作保證整棵樹(shù)的平衡性，這里面涉及很多磁盤隨機(jī)讀寫的操作，性能會(huì)比較差；另一方面考慮到并發(fā)場(chǎng)景，修改 B 樹(shù)結(jié)構(gòu)時(shí)需要比較復(fù)雜的鎖機(jī)制保證并發(fā)安全，也會(huì)一定程度影響效率。

綜上，B 樹(shù)的難點(diǎn)在于平衡性維護(hù)和并發(fā)控制，一般用在讀多寫少的場(chǎng)景。

LSM 樹(shù)是數(shù)據(jù)不可變的代表結(jié)構(gòu)。你只能在尾部追加新數(shù)據(jù)，不能修改之前已經(jīng)插入的數(shù)據(jù)。

如果不能修改以前的數(shù)據(jù)，是不是就不能提供刪、查、改的操作 API 呢？其實(shí)是可以的。

我們只需要提供set(key, val)和get(key)兩個(gè) API 即可。查詢操作靠get(key)，增刪改操作都可以由set(key, val)實(shí)現(xiàn)：

如果set的key不存在就是新增鍵值對(duì)，如果已經(jīng)存在，就是更新鍵值對(duì)；如果把val設(shè)置為一個(gè)特殊值（比如 null）就可以代表key被刪掉了（墓碑機(jī)制）。

那么我對(duì)某個(gè)鍵key做了一系列操作后，我只要找到最近一次的操作，就能知道這個(gè)鍵當(dāng)前的值是多少了。

從磁盤的角度來(lái)說(shuō)，在尾部追加的寫入效率非常高，因?yàn)椴恍枰?B 樹(shù)那樣維護(hù)復(fù)雜的樹(shù)形結(jié)構(gòu)嘛。但代價(jià)就是，查找效率肯定比較低，因?yàn)橹荒芡ㄟ^(guò)線性遍歷去查找操作記錄。

后面我會(huì)講講真正的 LSM 樹(shù)如何針對(duì)讀場(chǎng)景進(jìn)行優(yōu)化，但再怎么優(yōu)化，肯定也達(dá)不到 B 樹(shù)的讀取效率。

同時(shí)，LSM 樹(shù)還有一個(gè)明顯弊端就是存在空間放大。在 B 樹(shù)中一個(gè)鍵值對(duì)就占用一個(gè)節(jié)點(diǎn)，我更新這個(gè)鍵 100 次，它還是只占用一個(gè)節(jié)點(diǎn)。但在 LSM 樹(shù)中，如果我更新一個(gè)鍵 100 次，就相當(dāng)于寫入了 100 條數(shù)據(jù)，會(huì)消耗更多空間。

后面會(huì)講到，這個(gè)問(wèn)題的解決方案是壓實(shí)（compact），把操作序列中失效的歷史操作消除掉，只保留最近的操作記錄。

綜上，LSM 樹(shù)的難點(diǎn)在于 compact 操作和讀取數(shù)據(jù)時(shí)的效率優(yōu)化，一般用在寫多讀少的場(chǎng)景。

有序 vs 無(wú)序

可以說(shuō)，存儲(chǔ)結(jié)構(gòu)的有序程度直接決定了該類結(jié)構(gòu)的讀寫性能上限。有序度越高，讀性能越強(qiáng)，但相應(yīng)的，維護(hù)有序性的成本也越高，寫入性能也就會(huì)越差。

你看 B 樹(shù)，作為 BST 的加強(qiáng)版，實(shí)際上是維護(hù)了所有數(shù)據(jù)的有序性，讀取性能必然起飛，但寫入性能你也別抱太大希望。

LSM 樹(shù)不可能向 B 樹(shù)那樣維護(hù)所有數(shù)據(jù)的有序性，但可以維護(hù)局部數(shù)據(jù)的有序性，從而一定程度提升讀性能。

LSM 樹(shù)的設(shè)計(jì)

就我的理解，LSM 樹(shù)其實(shí)不是一種數(shù)據(jù)結(jié)構(gòu)，而是一種存儲(chǔ)方案。這里面涉及三個(gè)重要的數(shù)據(jù)組件：memtable，log，SSTable，正如我在Apache Pulsar 的架構(gòu)設(shè)計(jì)中畫的這幅圖：

其中Journal就是log，Entry Log就是若干SSTable的集合，叫法不同罷了。

memtable是紅黑樹(shù)或者跳表這樣的有序內(nèi)存數(shù)據(jù)結(jié)構(gòu)，起到緩存和排序的作用，把新寫入的數(shù)據(jù)按照鍵的大小進(jìn)行排序。當(dāng)memtable到達(dá)一定大小之后，會(huì)被轉(zhuǎn)化成SSTable格式刷入磁盤持久化存儲(chǔ)。

SSTable（Sorted String Table）說(shuō)白了就是一個(gè)特殊格式的文件，其中的數(shù)據(jù)按照鍵的大小排列，你可以把它類比成一個(gè)有序數(shù)組。而 LSM 樹(shù)，說(shuō)白了就是若干SSTable的集合。

log文件記錄操作日志，在數(shù)據(jù)寫入memtable的同時(shí)也會(huì)刷盤寫入到log文件，作用是數(shù)據(jù)恢復(fù)。比如在memtable中的數(shù)據(jù)還沒(méi)轉(zhuǎn)化成SSTable持久化到磁盤時(shí)，如果突然斷電，那么memtable里面的數(shù)據(jù)都會(huì)丟失，但有l(wèi)og文件在，就可以恢復(fù)這些數(shù)據(jù)。當(dāng)然，等memtable中的數(shù)據(jù)成功轉(zhuǎn)化成SSTable落盤之后，log文件中對(duì)應(yīng)的操作日志就沒(méi)必要存在了，可以被刪除。

LSM 樹(shù)的set寫入過(guò)程并不復(fù)雜：寫入log和memtable，最后轉(zhuǎn)化成一個(gè)SSTable持久化到磁盤就行了。

最關(guān)鍵的應(yīng)該是讀取和 compact 的過(guò)程：SSTable要如何組織，才能快速get到一個(gè)key對(duì)應(yīng)的val呢？如何定期對(duì)所有 SSTable 做 compact 瘦身呢？

其實(shí)有多種方案，其中比較常用的方案是按照層級(jí)組織SSTable：

https://github.com/facebook/rocksdb/wiki/Leveled-Compaction

圖中每個(gè)綠色方塊代表一個(gè)SSTable，若干個(gè)SSTable構(gòu)成一層，總共有若干層，每層能夠容納的SSTable數(shù)量上限依次遞增。

新刷入的SSTable在第 0 層，如果某一層的SSTable個(gè)數(shù)超過(guò)上限，則會(huì)觸發(fā) compact 操作，從該層選出若干SSTable合并成一個(gè)更大的SSTable，移動(dòng)下一層：

https://github.com/facebook/rocksdb/wiki/Leveled-Compaction

每個(gè)SSTable就好比一個(gè)有序數(shù)組/鏈表，多個(gè)SSTable的合并就是前文鏈表雙指針技巧匯總中合并多個(gè)有序鏈表的邏輯。

這樣，越靠上層的數(shù)據(jù)越新，越靠下層的數(shù)據(jù)越舊，且算法保證同一層的若干SSTable的key不存在重疊：

https://github.com/facebook/rocksdb/wiki/Leveled-Compaction

那么假設(shè)給一個(gè)目標(biāo)鍵key27，我們只需要從上到下遍歷層，并在每一層中使用二分查找算法找到鍵區(qū)間包含key27的SSTable，然后用布隆過(guò)濾器快速判斷一下key27是否不存在這個(gè)SSTable中。如果可能存在，由于SSTable中的鍵也是有序的，可以再次運(yùn)用二分查找算法在SSTable中找到鍵對(duì)應(yīng)的值。

這樣，借助 LSM 樹(shù)的層級(jí)結(jié)構(gòu)和SSTable的有序性，就能利用二分搜索提升查找效率，避免線性查找鍵值對(duì)。

以上就是本文的全部?jī)?nèi)容，LSM 樹(shù)的設(shè)計(jì)思路比較易于理解，但實(shí)現(xiàn)起來(lái)還有不少細(xì)節(jié)，如果你對(duì)具體實(shí)現(xiàn)感興趣，我可以推薦一些學(xué)習(xí)資料：

LevelDB 的代碼倉(cāng)庫(kù)：

https://github.com/google/leveldb/issues

RocksDB 的 wiki：

https://github.com/facebook/rocksdb/wiki

審核編輯 ：李倩