共計 4358 個字符，預計需要花費 11 分鐘才能閱讀完成。

本文丸趣 TV 小編為大家詳細介紹“LevelDB 的整體架構是怎樣的”，內容詳細，步驟清晰，細節處理妥當，希望這篇“LevelDB 的整體架構是怎樣的”文章能幫助大家解決疑惑，下面跟著丸趣 TV 小編的思路慢慢深入，一起來學習新知識吧。

一個比喻

LevelDB 有點類似于建筑，分為地基和地面兩部分，也就是磁盤和內存，而地基又好比地殼結構分了很多層級，不同層級的數據還會定期從上往下移動 —— 沉積作用。如果磁盤底層的冷數據被修改了，它又會再次進入內存，一段時間后又會被持久化刷回到磁盤文件的淺層，然后再慢慢往下移動到底層，周而復始就好比地球水循環。

內存結構

LevelDB 的內存中維護了 2 個跳躍列表，一個是只讀的 rtable，一個是可修改的 wtable。跳躍列表在我的另一本書《Redis 深度歷險》中有詳細講解，這里就不再細致重復說明。簡單理解，跳躍列表就是一個 Key 有序的 Set 集合，排序規則由全局的「比較器」決定，默認是字典序。跳躍列表的查找和更新操作時間復雜度都是 Log(n)。

跳躍列表是由多個層次的鏈表構成，其中最底層的鏈表存儲了所有的 Key，它們是有序的。普通鏈表并不支持快速二分查找，但是跳躍鏈表的特殊結構可以讓最底層的鏈表以近似二分查找算法的效率定位到指定節點。簡單理解就是跳躍列表同時具備了有序數組的快速定位能力和鏈表的高效增刪能力。但是它會付出一定的代價，在實現上有一定的復雜度。

如果跳躍列表只存 Key，那 Value 存哪里呢？答案是 Value 也存在跳躍列表的 Key 中。跳躍列表中存儲的 Key 比較特殊，它是一個復合結構字符串，它同時包含了鍵值對的 Key 和 Value。

其中 sequence 為全局自增序列號，LevelDB 遇到一個修改操作，全局序列號自動加一。LevelDB 中的 Key 存儲了多個版本的 Value。LevelDB 使用序列號來標記鍵值對的版本，序列號越大，對應的鍵值對越新。

type 為數據類型，標記是 Put 還是 Delete 操作，只有兩個取值，0 表示 Delete，1 表示 Put。

internal_key = key + sequence + type
Key = internal_key_size + internal_key + value_size + value

如果是刪除操作，后面的 value_size 字段值 為 0，value 字段值是空的。我們要將 Delete 操作等價看成 Put 操作。同時為了節省存儲空間，internal_key_size 和 value_size 都要采用 varint 整數編碼

如果跳躍列表中同一個 key 存在多個修改操作，也就是說有多個「復合 Key」，那么這幾個「復合 Key」肯定會挨在一起按照 sequence 值排序的。當 Get 操作到來時，它會在跳躍列表中定位到 key 所在的位置，選擇這幾個同樣的 key 中 seq 最大的「復合 Key」，提取出其中的 value 值返回。

待 Put 和 Delete 操作日志寫到日志文件后，其鍵值對合并成「復合 Key」插入到 wtable 的指定位置中

待 wtable 的大小達到一個閾值，LevelDB 將它凝固成只讀的 rtable，同時生成一個新的 wtable 繼續接受寫操作。rtable 將會被異步線程刷到磁盤中。Get 操作會優先查詢 wtable，如果找不到就去 rtable 中去找，rtable 如果還找不到，再去磁盤文件里去找。

因為 wtable 要支持多線程讀寫，所以訪問它是需要加鎖控制。而 rtable 是只讀的，它就不需要，但是它的存在時間很短，rtable 一旦生成，很快就會被異步線程序列化到磁盤上，然后就會被置空。但是異步線程序列化也需要耗費一定的時間，如果 wtable 增長過快，很快就被寫滿了，這時候 rtable 還沒有完成序列化，而 wtable 急需變身怎么辦？這時寫線程就會阻塞等待異步線程序列化完成，這是 LevelDB 的卡頓點之一，也是未來 RocksDB 的優化點。

圖中還有個日志文件，記錄了近期的寫操作日志。如果 LevelDB 遇到突發停機事故，沒有持久化的 wtable 和 rtable 數據就會丟失。這時就必須通過重放日志文件中的指令數據來恢復丟失的數據。注意到日志文件也是有兩份的，它和內存的跳躍列表正好對應起來。當 wtable 要變身時，日志文件也會跟著變身。待 rtable 落盤成功之后，只讀日志文件就可以被刪除了。

磁盤結構

LevelDB 在磁盤上存儲了很多 sst 文件，sst 表示 Sorted String Table，文件里所有的 Key 都會有序的。每個文件都會對應一個層級，每個層級都會有多個文件。底層的文件內容來源于上一層，最終它們都會來源于 0 層文件，而 0 層的文件又來源于內存里的 rtable 序列化。一個 rtable 會被序列化為一個完整的 0 層文件。這就是我們前面所說的「下沉作用」

從內存的 rtable 序列化成 0 層 sst 文件稱之為「Minor Compaction」，從 n 層 sst 文件下沉到 n+1 層 sst 文件稱之為「Major Compaction」。之所以這樣區分是因為 Minor 速度很快耗費資源少，將 rtable 完整地序列化為一個 sst 文件就完事了。而 Major 會涉及到多個文件之間的合并操作，耗費資源多，速度慢。層級越深的文件總容量越大，在 LevelDB 源碼里有一個層級容量公式，容量和層級呈指數級關系。而通常每個 sst 文件的大小都差不多，區別就成了每一層的文件數量不一樣。

capacity = level   0   10^(level+1) M

每個文件里面的 Key 都是有序的，也就是說它內部的 Key 取值會有一個確定的范圍。0 層文件和其它層文件有一個明顯的區別那就是其它層內部的文件之間范圍不會重疊，它們按照 Key 的順序嚴格做了切分。而 0 層文件的內容是直接從內存 dump 下來的，所以 0 層的多個文件的 Key 取值范圍會有重疊。

當內存出現讀 miss 要去磁盤搜尋時，會首先從 0 層搜尋，如果搜不到再去更深層次搜尋。

如果是其它層級，搜尋速度會很快，因為可以根據 Key 的范圍快速確定它可能會位于哪個文件中。但是對于 0 層，因為文件 Key 范圍會重疊，所以它可能存在于多個文件中，那就需要對這多個文件進行搜尋。正因如此，LevelDB 限制了 0 層文件的數量，如果數量超出了默認的 4 個，就需要「下沉」到 1 層，這個「下沉」操作就是 Major Compaction。

所有文件的 Key 取值范圍、層級和其它元信息會存儲在數據庫目錄里面的 MANIFEST 文件中。數據庫打開時，讀取一下這個文件就知道了所有文件的層級和 Key 取值范圍。

MANIFEST 文件也有版本號，它的版本號體現在文件名上如 MANIFEST-000361。每一次重新打開數據庫，都會生成一個新的 MANIFEST 文件，具有不同的版本號，然后還需要將老的 MANIFEST 文件刪除。

數據庫目錄中還有另外一個文件 CURRENT，它里面的內容很簡單，就是當前 MANIFEST 的文件名。LevelDB 首先讀取 CURRENT 文件才知道哪個 MANIFEST 文件是有效文件。在遇到斷電時，會存在一個小概率中間狀態，新舊 MANIFEST 文件共存于數據庫目錄中。

我們知道 LevelDB 的數據庫目錄不允許多進程同時訪問，那它是如何防止其它進程意外對這個目錄文件進行讀寫操作呢？仔細觀察數據庫目錄，你還會發現一個名稱為 LOCK 的文件，它就是控制多進程訪問數據庫的關鍵。當一個進程打開了數據庫時，會在這個文件上加上互斥文件鎖，進程結束時，鎖就會自動釋放。

還有最后一個不那么重要的操作日志文件 LOG，它記錄了數據庫的一系列關鍵性操作日志，例如每一次 Minor 和 Major Compaction 的相關信息。

多路歸并

Compaction 是比較耗費資源的操作，為了不影響線上的讀寫操作，LevelDB 將 Compaction 工作交給一個單一的異步線程來完成。如果工作量巨大，這個單一的異步線程也會有點吃不消。當異步線程吃不消的時候，線上內存的讀寫操作也會收到影響。因為只有 rtable 沉到磁盤里了，wtable 才可以變身。只有 wtable 變身了，才會有新的 wtable 被創建來容納后續更多的鍵值對。總之就是一環套一環，環環相扣。

下面我們來研究一下 Compaction。Minor Compaction 很好理解，就是內容空間有限，所以需要將 rtable 中的數據 dump 到磁盤 0 層文件。那為什么需要從 0 層文件 Compact 下沉到 1 層文件呢？因為 0 層文件如果過多，就會影響查找效率。前面我們提到 0 層文件之間的 Key 范圍會有重疊，所以單個 Key 可能存在于多個文件中，IO 讀次數將會被文件的數量放大。通過 Major Compaction 可以減少 0 層文件的數量，提升讀效率。那是不是只需要下沉到 1 層文件就可以了呢？那 LevelDB 究竟是什么原因需要這么多層級呢？

假設 LevelDB 只有 2 層（0 層和 1 層），那么時間一長，1 層肯定會累計大量的文件。當 0 層的文件需要下沉時，也就是 Major Compaction 要來了，假設只下沉一個 0 層文件，它不是簡簡單單地將文件元信息的層數從 0 改成 1 就可以了。它需要繼續保持 1 層文件的有序性，每個文件中的 Key 取值范圍要保持沒有重疊。它不能直接將 0 層文件中的鍵值對分散插入或者追加到 1 層的所有文件中，因為 sst 文件是緊湊存儲的，插入操作肯定涉及到磁盤塊的移動。再說還有刪除操作，它需要干掉 1 層文件中的某些已刪除的鍵值對，避免它們持續占用空間。

那 LevelDB 究竟是怎么做的呢？它采用多路歸并算法，將相關的 0 層文件和 1 層 sst 文件作為輸入，進行多路歸并，生成多個新的 1 層 sst 文件，再將老的 sst 文件干掉，同時還會生成新的 MANIFEST 文件。對于每個 0 層文件，它會根據 Key 的取值范圍搜尋 1 層文件中和它的范圍有重疊部分的 sst 文件。如果 1 層文件數量過多，每次多路歸并涉及到的文件數量太多，歸并算法就會非常耗費資源。所以 LevelDB 同樣也需要控制 1 層文件的數量，當 1 層容量滿時，就會繼續下沉到 2 層、3 層、4 層等。

非 0 層的多路歸并資源消耗要少一些，因為單個文件的 Key 取值范圍有限，能覆蓋到下一層的文件數量有限，參與多路歸并的輸入文件就少了很多。但是這個邏輯有個漏洞，那就是上下層的文件數量有 10 倍的差距，按照平均范圍間隔來算，意味著上層平均一個文件的取值范圍會覆蓋到下一層的 10 個文件。所以說非 0 層的多路歸并資源消耗其實也不低，Major Compaction 就是一個比較消耗資源的操作。

讀到這里，這篇“LevelDB 的整體架構是怎樣的”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注丸趣 TV 行業資訊頻道。