[[434628]]

上次我們分享了采用哈希索引實現(xiàn)的存儲引擎，它總是將寫操作不斷追加到數(shù)據(jù)文件，就跟寫日志一樣。這種日志結構式的存儲引擎，數(shù)據(jù)記錄順序由寫入時間決定，同一鍵的舊記錄由新記錄取代。

SSTable

由于數(shù)據(jù)在寫入時，自動切分成一個個文件。數(shù)據(jù)庫需要在后臺對文件進行合并，以減少文件數(shù)，進而加快查詢。如果待合并文件里的數(shù)據(jù)是有序的，我們就可以采用歸并排序算法來提高合并效率。

雖然這看起來會違背順序寫的原則，但也有辦法解決，我們稍后介紹。

現(xiàn)在，我們將數(shù)據(jù)文件格式改成這樣：①文件中的所有記錄，按照 鍵( key )來排序;②排序保證了每個鍵只在文件中出現(xiàn)一次，不會有重復的舊記錄。姑且將這種格式叫做 排序字符串表( sorted string table )簡稱 SSTable 。

相比普通日志結構式的數(shù)據(jù)文件，SSTable 有幾個明顯優(yōu)勢：

高效合并

如果您學過歸并排序算法，應該知道合并兩個有序序列是一個 既簡單又高效 的操作：

逐個遍歷待合并文件，將最小的鍵拷貝到輸出文件即可。如果同一個鍵在多個文件中出現(xiàn)，則以寫入時間比較新的記錄為準，其他均可丟棄。合并后得到的 SSTable 文件，數(shù)據(jù)也是按鍵排好順序的，而且重復鍵均已去重。

SSTable 文件保存某段時間內寫入的數(shù)據(jù)，一個 SSTable 數(shù)據(jù)跟另一個比較，要么較新，要么較舊。因此可以用這個特性進行去重，重復鍵以較新的 SSTable 為準。

合并時則必須保證 SSTable 是相鄰的，否則就亂套了。假設有三個 SSTable ，按時段依次是 A 、B 、C ，其中 C 最新。如果先將 A 和 C 合并得到 X ，就無法再跟 B 合并了。因為 X 中的數(shù)據(jù)有的來自 A ，有的來自 C ，不好判斷是比 C 新還是比 C 舊。

合并操作非常高效，算法時間復雜度是 ，基本等同于將數(shù)據(jù)從源文件拷貝到目標文件即可。

讀取待合并文件時是 順序讀 ，寫結果文件時又是 順序寫 ，對磁盤非常友好。文件系統(tǒng)可以先預讀待合并數(shù)據(jù)，然后緩存起來;又可以收集待寫入數(shù)據(jù)，然后再批量寫;磁盤 IO 操作便顯著減少。

合并過程對內存要求極低，就算文件遠遠大于可用的物理內存也毫不礙事。

稀疏索引

您可能會這么想，既然 SSTable 數(shù)據(jù)是有序的，查詢時是否可以用 二分查找法 進行搜索呢?

雖然二分查找法的時間復雜度是 ，但對磁盤操作來說還不夠好。由于磁盤非常慢，IO 操作應該盡可能地減少，最好是只執(zhí)行一次 IO 就能拿到數(shù)據(jù)。但二分查找需要執(zhí)行 次 IO 操作，而且每次讀取的位置都不一樣，對磁盤很不友好。

既然不能用二分查找法直接搜索磁盤數(shù)據(jù)，那就只能在內存中維護數(shù)據(jù)索引了。

由于磁盤中的 SSTable 是按鍵排序的，我們可以采用 排序樹(比如紅黑樹)來組織索引，這樣可以支持范圍查詢。舉個例子，查詢鍵在 A 和 B 之間的數(shù)據(jù)，可以先通過排序樹索引，找到第一個大于等于 A 的數(shù)據(jù)的偏移量;再從該位置開始逐個讀取，直到數(shù)據(jù)鍵大于 B 。

實際上，內存索引沒有必要包含全部的鍵，每隔一定距離挑一個鍵即可：

如上圖，索引只包含部分鍵，大概呈均勻分布。當我們查詢 bananas 時，我們查找內存中的索引，并沒有找到該鍵。盡管如此，我們可以確定 bananas 落在 banalize 和 bandboxy 這兩個鍵之間。

因此，只要從 banalize 鍵偏移量開始，不斷遍歷數(shù)據(jù)即可。如果當前 SSTable 包含 bananas ，那我們遍歷少量數(shù)據(jù)后即可找到;如果不包含 bananas ，我們遍歷到第一個比 bananas 大的鍵后即可停止。

稀疏索引一般每隔若干 KB 數(shù)據(jù)才維護一個索引項，內存使用量大大降低，但查詢時卻要讀取更多數(shù)據(jù)。

好在磁盤數(shù)據(jù)是按塊讀取的，就算數(shù)據(jù)不夠一個塊，也得整塊讀取;而且由于磁盤尋址的因素，讀一塊和若干塊的時間差別其實很小。因此，就算查詢時需要多讀一些數(shù)據(jù)，對性能也不會產生太大的負面影響。

節(jié)省磁盤帶寬

由于查詢時可能需要掃描兩個索引項之間的全部數(shù)據(jù)記錄(如上圖陰影部分)，因此可以將它們組織成邏輯數(shù)據(jù)塊，壓縮 之后再寫到磁盤，索引條目則指向每個壓縮塊的開頭。

由于相鄰數(shù)據(jù)條目通常比較相像，至少他們的鍵都有相同的前綴，因此壓縮后的尺寸能顯著降低。這一方面節(jié)約了磁盤空間，另一方面則降低了磁盤 IO 帶寬。

雖然壓縮、解壓縮需要消耗一定的 CPU 資源，好在 CPU 通常不是存儲系統(tǒng)的主要瓶頸，磁盤 IO 才是。

因此，壓縮是一種典型的以時間換空間的技術選擇，通過犧牲 CPU 資源來緩解帶寬資源。在 Web 領域，服務器也經常對數(shù)據(jù)進行壓縮，以節(jié)約帶寬資源，縮短傳輸時間。

LSM樹

SSTable 查詢表現(xiàn)不錯，但數(shù)據(jù)庫寫操作肯定是亂序的，怎樣才能將數(shù)據(jù)排序保存呢?

在磁盤中維護排序結構倒也可行，B樹( b-tree )就可以做到，但太復雜了。

如果是在內存里，事情就簡單多了。眾所周知，我們有很多數(shù)據(jù)結構可供選擇，比如 紅黑樹( red-black tree )和 AVL樹 。這些數(shù)據(jù)結構在亂序插入的前提下，也能支持有序遍歷。

這樣一來，我們可以這么設計：

寫操作到達后，將其保存到內存中的平衡樹結構(比如紅黑樹)。這棵在內存中維護的平衡樹稱為 memtable 。

當 memtable 數(shù)據(jù)增長達到一定閾值(通常是若干 MB )，就將其轉成 SSTable 文件并寫到磁盤。由于 memtable 平衡樹數(shù)據(jù)是按鍵排序，轉寫過程很高效——中序遍歷數(shù)據(jù)并順序寫到磁盤即可。

雖然 memtable 轉寫效率很高，還是會阻塞數(shù)據(jù)庫寫操作，不管時間多短。為了不阻塞寫操作，我們可以分配一個新的 memtable 來寫，然后在后臺慢慢轉寫舊的 memtable (如圖陰影部分)。

那么，數(shù)據(jù)庫讀操作又該如何處理呢?您可能已經想到答案了：我們需要先查詢 memtable ，然后再查詢 SSTable 。再啰嗦一句， SSTable 必須從數(shù)據(jù)最新的那個開始，逐個查詢。

那隨著時間推移，SSTable 中應該會有不少被覆寫或者刪除的無效記錄。這時，數(shù)據(jù)庫可以在后臺對 SSTable 進行合并，以去除無效記錄，節(jié)約磁盤空間。于此同時，合并操作也可以減低 SSTable 個數(shù)，提高查詢效率。

操作日志

這個方案看起來不錯，但您可能也發(fā)現(xiàn)一個問題：如果數(shù)據(jù)庫掛掉了，保存在 memtable 中的寫操作不就丟了嗎?

為了解決這個問題，我們可以在磁盤中維護一個日志文件，來記錄寫操作。每個寫操作除了保存到 memtable 外，還要追加寫到日志文件。這樣就算 memtable 因故障丟失了，也可以通過重放日志文件來重建。

注意到，日志文件中的數(shù)據(jù)是按寫入時間排序的，而不是按照數(shù)據(jù)鍵排序的。不過不要緊，因為日志文件只是為了故障時可以重建 memtable ，一旦 memtable 持久化到 SSTable，對應的日志文件就可以安全釋放了。

查詢優(yōu)化

LSM樹 查詢一個不存在的鍵可能很慢，因為數(shù)據(jù)庫要檢查所有 SSTable ，才能確定待查鍵不存在。如果 SSTable 文件數(shù)量很多，查詢效率肯定要大打折扣。

為了優(yōu)化這類查詢，數(shù)據(jù)庫通常會額外維護一個 布隆過濾器 ( bloom filter )。這樣一來，查詢時先檢查布隆過濾器，如果確定待查鍵不存在，就不必檢查 memtable 和 SSTable 了。

布隆過濾器可以 大致 維護一個集合，而且非常節(jié)約內存。您可以將它當作一個特殊實現(xiàn)的集合，可以查詢一個元素是否在集合內。大致 的意思是布隆過濾器可能會誤判——查詢存在而實際上不存在。但如果查詢不存在，就一定是不存在的，不會誤判。

總結

LSM樹 索引擅長鍵值對存儲場景，在 LevelDB 和 RocksDB 等數(shù)據(jù)庫內部均有應用。它的設計思路很簡單：

采用內存紅黑樹 memtable 保存最近寫入的數(shù)據(jù);

寫 memtable 的同時，將操作日志寫到磁盤，以便故障恢復;

定期將 memtable 數(shù)據(jù)刷到磁盤 SSTable ;

SSTable 數(shù)據(jù)已經有序，配合稀疏索引，支撐高效查詢;

至此，我們已經掌握了三種主流數(shù)據(jù)庫索引技術中的兩種，下節(jié)我們將繼續(xù)聊 B樹 索引。