leveldb簡介
leveldb，既然是叫做db，顯然和數據庫有關。和一般的關係型數據庫不同，它內部的數據全部以KV也就是key-value形式存儲，並且不支持結構化的SQL進行數據查詢，只支持api調用。也就是說它就是一個典型的我們常說的noSQL數據引擎庫。它最早由
google 開發並且開源， Facebook 在此基礎上進行優化，推出了更普及的RocksDB，後來包括TiDB等多種分佈式noSQL數據庫的底層都是基於leveldb。如果上面這些名詞你都沒聽說過，也沒有關係，對於這些庫而言，上手去用容易，但是瞭解原理難。搞懂了原理再實際上手去用，除了更加簡單之外，也會有更多的體會。
leveldb架構
這是一張leveldb的架構圖，比之前介紹的裸的LSMT的架構圖要複雜一些，但是核心本質是一樣的，我們一個一個來看。
首先上層是MemTable，和Immutable MemTable。MemTable我們都知道，其實 本質上就是一個存放在內存當中的數據結構 。可以是SkipList也可以是紅黑樹或者是其他的平衡樹(在leveldb當中，使用的是SkipList)，我們只需要確定，它是存儲在內存當中的。Immutable MemTable其實也是MemTable，前面的Immutable是不可修改的意思。之前我們說過，當MemTable當中的內容超過某個閾值的時候，我們需要將其中的內容寫成一個SSTable的文件。這個ImmuTable MemTable就是在這個時候用的。
當一個MemTable在開始執行持久化之前，會先轉化成ImmuTable MemTable，可以認為是加上了不可修改的限制。另外，會再新建一個新的MemTable，用於維持服務。之後再將ImmuTable MemTable寫入進SSTable文件。
打個比方，MemTable就好像是收銀臺裡的收銀櫃，當我們一個門店開張，顯然需要有收銀櫃存放顧客付的錢。當收銀櫃快滿的時候，我們需要將裡面的錢存入銀行。但是裡面的錢不少，並且還有顧客在源源不斷地付錢，我們讓它停一會會帶來損失。所以我們把整個收銀櫃一起拿走，為了安全，我們在外面加上一把鎖，鎖起來連同收銀櫃送到銀行。但是收銀臺不能沒有收銀櫃啊，所以我們還需要拿出一個新的收銀櫃給收銀臺去收錢。
在這個例子當中，一開始負責收錢的收銀櫃就是MemTable，加了鎖之後變成了Immutable MemTable。也許不是非常恰當，但是對照一下，應該很容易理解。
其次是.log文件，這個很好理解，之前的LSMT當中也有這個文件，用來存儲發生變更的數據。 類似於數據庫當中的binlog ，用來在系統發生故障重啟時恢復數據。
接著我們來看SSTable，在原始的LSMT當中SSTable是順序存儲的，所以我們在查詢數據的時候才是依次查詢，當發現第一個SSTable當中沒有我們要查詢的內容的時候，就往下查詢下一個文件。而在leveldb當中， SSTable是按照層級存儲的 ，第一層是level0，第二層是level1，以此類推，層級逐漸增高。這也是leveldb得名的原因。
我們之前介紹過SSTable的本質是一個key-value的序列表，並且其中的key是有序的。既然SSTable當中的key是有序的，那麼顯然就有最大值和最小值。我們把最大值和最小值記錄下來就可以在查詢的時候快速判斷，我們要查詢的key它可能在哪些SSTable當中，從而節省時間，加快效率。
這個記錄SSTable文件當中的最小key和最大key的文件就是manifest，除了最小最大key之外，還會記錄SSTable屬於哪個level，文件名稱等信息。我們可以對照下下圖當做一個參考：
最後是Current文件，從名字上來看，Current像是一個指針的名字。的確，Current是一個指針。因為在實際運行當中manifest文件不止一個，因為伴隨著我們的壓縮等操作，都會產生新的manifest。我們需要一個指針記錄下來當前最新的manifest文件是哪一個，方便查找。而且manifest當中的數據量並不小，所以我們不能全部都存放在內存當中，放在文件裡用一個指針引用是最佳選擇。
leveldb的增刪改查
leveldb的寫入
leveldb當中的 寫、刪、改操作和裸的LSMT基本一樣 ，分成以下幾個步驟。
首先，會將變更的數據寫入.log文件當中。這是為了持久化數據，防止系統宕機導致數據丟失。
當寫入.log文件成功之後，寫入MemTable。由於leveldb中的MemTable採用SkipList實現，所以寫入速度也會很快，大約是log(n)的複雜度。如果MemTable容量達到或者超過閾值，會觸發進一步寫入SSTable的操作。在這個寫入當中，首先會將MemTable轉化成Immutable MemTable，之後會新建一個空的MemTable應對後續的請求，當dump指令下達之後，會將Immutable MemTable寫入成SSTable文件進行存儲。
以上的流程和LSMT大同小異，只有一些細微的區別。另外嚴格說起來leveldb不支持修改操作，可以轉化成插入一條新數據，或者是先刪除舊數據再插入，這兩者本質上是一樣的，會在後續數據壓縮的過程當中進行合併。
leveldb的讀取
leveldb的讀操作和LSMT稍稍有所區別，我們結合下面這張圖來詳細看下。
首先，當我們執行查找指令的時候，我們
首先會在MemTable和Immutable MemTable當中進行查找 。這一點很容易理解，因為MemTable和Immutable MemTable都是完善的數據結構，支持快速查找。有些同學可能會覺得奇怪，Immutable MemTable不是寫入文件當中了麼，怎麼還能進行查找。這是因為當MemTable轉化成Immutable MemTable之後到寫入磁盤會有一個等待時間，並不是立即執行的。在執行寫入之前，Immutable MemTable當中可能都會有數據殘留，需要進行查找是必要的。如果在MemTable和Immutable MemTable當中都沒有找到，那麼我們則會讀取磁盤中的數據進行查找。
和裸的LSMT按照順序一個一個查找SSTable不同，leveldb會首先讀取manifest文件，根據manifest文件當中記錄的key的範圍來找到可能出現的SSTable文件。
對於同一個key來說， 可能同時出現在不同level的SSTable當中 ，但是由於leveldb在寫入SSTable的時候遵循越晚寫入的數據越新的原則。也就是說 level序號越小的數據越新 ，所以如果找到了多個值，那麼優先返回上層的結果。
整個leveldb的讀寫可以看得出來是在原本LSMT的基本上加入的優化，並沒有太多難以理解的東西，還是比較簡明直接的。在一些場景當中，我們的內存資源比較充足，並且對於查找有一定的要求，我們可以將manifest緩存在內存當中，這樣可以減少讀取manifest文件的時間，起到加速的作用。但是同時，也帶來了維護緩存的成本，這一點會在之後介紹緩存的文章當中詳細介紹。
leveldb的壓縮策略
最後，我們來看下leveldb的壓縮策略，這也是leveldb的精髓。
Google有一篇 Bigtable: A Distributed Storage System for Structured Data 的論文， 這一篇論文可以認為是leveldb的理論基礎。在BigTable的論文當中，提到了三種壓縮策略。
第一種策略叫做 minor Compaction ，這一種策略非常簡單，就是簡單地把MemTable中的數據導入到SSTable。
第二種策略叫做 major Compaction ，這種策略中會合並不同層級的SSTable文件，也就是說major Compaction會減少level的數量。
最後一種策略叫做 full Compaction ，這一種策略會將所有的SSTable文件合併。
在leveldb當中，實現了前面兩種壓縮策略，minor Compaction和major Compaction，下面我們來詳細研究一下。
minor Compaction
minor Compaction很簡單，剛才說過了其實就是將MemTable也就是SkipList當中的數據寫入到磁盤生成SSTable文件。
我們之前的文章當中介紹過SkipList，它的本質是一個有序的鏈表。而我們想要生成的SSTable也剛好是有序的。所以我們只需要依次遍歷寫入即可。對SkipList感興趣或者是想要複習的同學可以點擊下方的鏈接回顧一下：
分佈式——SkipList跳躍鏈表【含代碼】
根據越晚生成的SSTable level序號越小，層級越高的原則，我們最新生成的SSTable是level0。之後我們要記錄這個新生成的SSTable當中的索引，完成寫入操作。需要注意的是，在這個過程當中，我們 不會對數據進行刪除操作 。原因也很簡單，因為我們並不知道要刪除的數據究竟在哪個level下的SSTable裡，找到並刪除會帶來大量的耗時。所以我們依舊會原封不動地記錄下來，等待後續的合併再處理這些刪除。
另外， 在文件的末尾部分會將key值的信息以索引的形式存儲 。由於我們讀取文件的時候是倒序讀取的，所以優先會讀取到這些索引信息。我們就可以根據讀取到的索引信息快速鎖定SSTable當中的數據而不用讀取整個文件了。
major Compaction
接下來我們來看major Compaction。這也是leveldb分層機制的核心，不然的話插入SSTable也只會都是level0，層次結構就無從談起了。
在詳細介紹之前，我們需要先弄清楚一個洞見。對於leveldb當中其他level的SSTable文件而言，都是通過major Compaction生成的。我們可以保證同一層的SSTable沒有重疊的元素，但是level0不同，level0當中的SSTable是通過minor Compaction生成的，所以是 可能會有重疊的 。
leveldb當中觸發major Compaction的情況並不止一種，除了最常提到的Size Compaction之外還有兩種，一種是manual Compaction，還有一種是seek Compaction。下面來簡單介紹一下。
manual Compaction很好理解，就是 人工手動觸發 ，通過接口調用人為地去觸發它執行Compaction。size Compaction相當於平衡操作，當系統發現某一層的SSTable數量超過閾值的時候會觸發。最後一種是seek Compaction，這一種比較機智，leveldb會記錄每一層level中每一個SSTable文件的miss rate。就是當發現某一個文件當中的數據總是miss，而在下一層的文件當中查找到了值，這個時候leveldb就會認為這個文件不配待在這一層，將它和下一層的數據進行合併，以減少IO消耗。
當然以上三種觸發Compaction的情況當中，最常出現的還是size Compaction，就是 當leveldb發現某一層的SSTable數據或者是大小超過閾值的時候，會執行Compaction操作 。
在major Compaction當中，假設leveldb選擇的是level i的文件進行合併。這個時候需要分情況討論，如果i=0，也就是說我們要合併的是level 0的數據。由於剛才提到的，level 0當中不同文件的數據是存在重疊的，這個時候 需要將所有key值有重疊的文件都納入到待合併的集合當中來 。在挑選待合併集合的時候，leveldb會記錄上一次觸發壓縮時的最大key值，這一次會選擇大於這個key值的文件開始執行壓縮。
也就是說leveldb設計了一種輪流機制， 保證level當中的每一個文件都有被合併的機會 。
當我們level i的文件選擇結束之後，接下來就要從level i+1當中選擇文件進行合併了。選擇的標準也很簡單，我們會將所有和待合併集合中key值有重疊的文件全部挑選出來進行合併。
合併的過程本質上是一個多路歸併的過程，如下圖所示：
由於所有文件當中的key值都是有序的，我們都從它們的頭部開始。對於每一個key我們都會進行判斷，是應該保留還是丟棄。判斷的邏輯也很簡單，對於某一個key而言，如果這個key在更低級的level中出現過，那麼說明有更新的value存在，我們需要進行拋棄。
當Compaction完成之後，所有參與歸併的文件都已經沒有用處了，可以進行刪除。
從本質上來說這個歸併過程和裸的LSMT原理是一樣的，只是增加了層次結構而已。
到這裡還沒有結束，還記得我們有一個記錄所有SSTable索引的 manifest 文件嗎？不論哪一種Compaction的發生，都會改變整個level的結構，所以我們需要在每一次Compaction之後，都會生成一個新的manifest文件，然後將此次Compaction帶來的文件變動記錄進去。最後，將Current指向新生成的manifest。
這樣，我們整個過程就串起來了。
總結
我們回顧一下整個流程，會發現雖然增刪改查以及Compaction的操作增加了許多細節，但是 底層的框架其實還是LSMT 那一套。因為核心的原理是一樣的，所以和純LSMT一樣，leveldb當中的SSTable同樣可以使用布隆過濾器來進行優化，除此之外，還有cache的靈活使用，可以進一步提升查詢的效率。
另外，需要注意的是，leveldb嚴格說起來 只是數據庫引擎，並不是真正的數據庫系統 。基於leveldb我們可以開發出比較完善的數據庫系統，但它本身只提供底層最核心增刪改查服務的基礎。除了基礎功能之外，一個成熟的數據庫系統還需要開發大量的細節以及做大量的優化。目前為止基於leveldb開發的數據庫引擎很多， 但完整的數據庫系統非常少 ，畢竟這需要長久時間開發和積累。
如果我們簡單把分佈式系統分成 分佈式計算系統和分佈式存儲系統 的話，會發現分佈式存儲系統的精華佔了大半。而分佈式存儲系統又可以簡單認為是 底層的數據結構 加上上層解決分佈式帶來的一致性等問題的 共識協議 。而分佈式存儲系統當中常用的底層數據結構無非也就那麼幾種，所以說我們對於這些數據結構的瞭解和學習是以後深入理解分佈式系統的基礎。而一個合格且優秀的系統架構師，解決業務場景當中的分佈式問題是常態，而解決問題的能力的核心，其實就在於對這些底層基礎知識的理解和運用。
閱讀更多 sandag 的文章
