Golang 從零搭建 LevelDB

【導讀】作者介紹了使用 Go 語言從零開始構建 KV 數據庫 LevelDB 的實踐。

如今 KV 數據庫已經成爲工作中必不可少的一種數據存儲模式，首先聯想到的就是高併發的代表 --Redis，其已經征服了各種領域，如高性能緩存、分佈式鎖、熱點數據存儲等。與 Redis 遙相呼應就是持久型 (文件)KV 數據庫 RocksDB，談論 RocksDB 將是一個浩大的工程，而 RocksDB 是基於 LevelDB 改進而成，因此我們直擊它的基礎版，也就是我們今天的主角 LevelDB，它也是文件型 KV 存儲的代表。本文對 LevelDb 的基本實現源代碼地址在文末呈上。

LevelDB

LevelDB 的本質是 Level，也特現在了它的名稱上，即我們通過多層文件結構來達到順序存儲 KV 數據的目的。這句話聽起來可能有一些繞口，拋棄你對它的前置觀念，讓它的架構圖來解釋這句話。

在 API 做 KV 插入時是不能保證順序 (即不按 KEY 排序) 的，但是我們在查找時卻希望是有序的，順序 KEY 最起碼可以用二分進行查找而不是遍歷。LevelDB 最重要的就是在 SST 上做文章，將插入時的無序演變爲有序，最後讓二分查找變爲現實，後面讓我們對各個部分逐一擊破。

LevelDB 中一次完整的數據插入過程，首先數據插入 LOG(防止突然的宕機，利於恢復現場) 再插入內存 MemTable，在一定條件時內存 MemTable 會演變爲內存 Immutable MemTable，而內存 Immutable MemTable 的數據是不可變，同時 New 一個新的 MemTable 繼續接 API 傳來的數據。接下來 Immutable MemTable 的數據將會被固化到 SST 中。SST 的文件從 level 0 開始一路升級打怪直到 Level TopN，每次 Level 升級其實也就是多個低 Level 的 SST 文件進行聚合操作。而數據在 SST 中的文件內將會是有序的。這將便於查找。因此在 LevelDB 中，數據有可能存在 MemTable--> Immutable MemTable --> SST 之中，同時表明了數據流的流向過程。

在 LevelDB 中是沒有數據刪除的概念，最起碼 API 是不可以主動刪除數據，只能是追加一條 KEY-DELETE 記錄，當查找時會發現 KEY-DELETE 了，視爲 KEY 不存在。這也是爲什麼 LevelDB 適合寫多讀少的場景，因爲其採用的日誌追加的形式，正常的 DELETE 需要先 GET 再 DELETE，而 LevelDB 的 DELETE 只需要 APPEND 即可。

瞭解了 LevelDB 的大致內部工作原理，來具體看內部各個模塊的內容吧。

LevelDB API

LevelDB 真的很簡單，實現四個基本 API 即可:GET、PUT、DELETE、Iterator 。按照之前的解釋，其中的 PUT 和 DELETE 其實又是一個接口，因此本質上只有 3 個接口即 PUT/GET/Iterator。而這三個 API 的背後則是需要所有數據存儲的模塊都實現這四個接口，這樣才能整個系統玩得轉。

定義 KV 數據在 LevelDB 中的存儲格式，使用 Type 字段來表明這是刪除 or 插入一個新 Key

MemTable

爲了簡單實現，我們拋棄了 LOG 步驟，直接將數據插入 MemTable，這對整體 DB 無其他影響。Log 只是爲了數據先落盤確保出現宕機狀況可以恢復數據。

在 MemTable 中依舊需要實現GET、PUT、Iterator四個接口。而 MemTable 的真實結構爲 SkipList(跳錶)，其擁有鏈表和數組的優勢，便於尋找與插入 (畢竟 LevelDB 是沒有刪除操作的)。下圖展示的是一個 skiplist 的插入過程。跳錶的另一個經典場景就是遊戲裏面的拍賣行排序，在 Redis 中也有經典的使用場景。

MemTable 和 SkipList 的結構如下代碼所示，其中 Node 的 key 即 LevelDB 的數據元素 (InternalKey).

• 在執行插入 (PUT/DELETE) 時按照預設的 comparator 進行跳錶元素大小比較去確定插入位置。比較 InternalKey.UserKey，當相同時 seq 越大表示數據越新。

• 在執行 GET 時也按照大小比較去尋找有沒有對應的 KEY 即可。

• Iterator 就更簡單了，按如上動圖將 level0 層直接按鏈表遍歷一邊即可。

因此在 MemTable 中，我們將數據做到了跳錶內順序排列。

Immutable MemTable

Immutable MemTable 其實與 MemTable 是一個東西，只是介於 MemTable 和 SST 文件之間的中間產物，在真正固化爲 SST 文件之前不阻塞 API 繼續寫入而已。

SST

首先來看一下 SST 文件的文件結構，SST 是分 level 的，level 越高表示單個 SST 文件越大，內部包含的數據也就越多。同時 level 0 是由 Immutable MemTable 轉換而來，一個 Immutable MemTable 固化爲一個 level 0 的 SST 文件，因此 level 0 的 SST 文件之間是未排序的，但單個 SST 文件內部是排序的。從 level 1 開始都是由第一級的多個 SST 文件聚合而來，在聚合過程中就會保證其順序性，因此自 level 1 開始，同 level 的 SST 文件之間是有排序的。這也不難理解。

• Data Block(s) 存儲一系列排序的 KV 值, 數據存儲內容和格式表示在圖中 (/ 是爲了分割方便理解，並非真正存在，正在內容就是一堆緊挨着的二進制碼)

• Meta Block(s) 存儲對應 Data Block 的過濾信息，如布隆過濾器的值，加速 Key 的查找

• MetaIndex Block 存儲 Meta Block 的索引信息

• Index Block 存儲 Data Block(s) 的索引信息, 包含每個 Data Block 的最小 Key 和 offset 以及整個 Block 的 length

• Footer 存儲指向 MetaIndex、Index Block 的索引信息，固定長度

讀取 SST: 按照如圖的結構和如上的解釋，對單個 SST 文件的讀取 (disk 文件 --> 內存結構)應該先移動文件遊標到最後，讀取出 Footer，因爲 footer 是固定長度，很容易根據內容構建出 footer 對應的結構體。然後再根據 Footer 的內容移動遊標讀取 MetaIndex 和 Index Block，再根據對應的信息去讀取對應的 Data/Index Block。這樣一個完整的 SST 文件就被恢復成內存中的結構化對象。

可能聽起來還是有一些雲裏霧裏，但是基本思路就是 SST 內容是分 Block 的，

1. 先讀取 Footer 獲得到 MetaIndex 和 Index Block 索引所在 offset 和 length，

2. 根據 Index Block 的 offset 和 length 可以將 Index Block 構建出來

3. 再根據 Index Block 的內容去分 Block 讀取 Data Block 並依次構建

不如通過一個示例來實操一下讀取過程，示例爲某個 sst 文件只存了 key 爲 123，value 爲 456 的值。使用 od 讀取後的結果如下。

• 先讀取 Footer， 根據下文 Footer 的結構體也就是 Footer 會 Encode 爲 4 個 unit32，也就是佔 16 位，直接遊標讀取最後的 16 位 (綠色標出) 然後還原(小端寫入方法)，得到 MetaIndex 的值爲 0 和 0，IndexHandle 的 offset 爲 27，length 爲 32。

• 因爲忽略 MetaIndex 的實現，直接將遊標設爲 offset27，並讀取後面的 32 長度，得到紅色部分。Block 的部分其實就是緊密的寫 Key，最後寫 Block 中含有多少 Key 的個數 (uint32)，因此先讀取最後的 4 位，得到只寫了 1 個 key。然後再讀取 key 即可。單個 key 也是按照寫入方式依次讀取的，因爲 seq(uint64)，type(int8) 是固定長度可以直接讀取，而 key 和 value 則是用戶自定義的不能直接讀取，因此先讀取一個 len(key)和 len(value)，根據長度再分別讀取真正的字符串。所以 value 爲 00 00 00 00 1b 00 00 00，這個 value 是作爲 index 而寫入的，表明了對應的 data block 塊的 offset 爲 0， length 爲 27(1b)。

• 這時候可以去按照 index block 的內容真正讀取 data block 了，讀取方式和讀取 index block 是一致的，這次讀取出來的 value 則是真正的用戶寫入的 value。seq: 01 00 00 00 00 00 00 00 , type: 01 , lenkey: 03 00 00, key: 31 32 33, lenvalue: 03 00 00, value: 34 35 36, number of key: 01 00 00。

構造 SST-Data Block: 按照 Immutable MemTable 中已排序的 kv 依次插入，寫成 Byte 流暫存在內存中，等達到一個 Block 的限制時 flush 到磁盤，並記錄最小 Key、offset 和 length 作爲 Index Block 中的一項。其實就是把上述讀取過程反轉一遍即可。

構造 SST-Meta Block / MetaIndex Block: 爲了儘可能的簡化 LevelDB 以幫助理解，此文沒有實現 MetaBlock 和 MetaIndecBlock，如果按照布隆過濾的方法來算，每一個 MetaBlock 將是一個根據對應 DataBlock 中 key 來構造的布隆過濾表 (256 字節長度的 01 值, 假設)。那麼在讀取數據可以先通過布隆過濾器過濾一下來判斷此 datablock 是否有可能存在此 key，最終來決定是否讀取此 DataBlock(因爲讀取文件的成本很高，所以設計一個過濾器來減少不必要的讀取，加快查詢速度)

構造 SST-Index Block: 伴隨着 DataBlock 的寫入，不斷積累 Data Block 的索引信息，信息包含每個 DataBlock 的最小 Key 和起始 offset 以及 length

構造 SST-Footer: 當內容都寫完之後，添加一個固定類型值的 Footer 用於表明 Index Block 的 offset 和 length,(還應包含 MetaIndex Block 的 offset 和 length)。這樣在讀取時，就可以直接定位到 Index Block。實際操作中 offset 和 length 都是用 uint32 的值來存儲，因此是可以將文件遊標移到最後 - len(uint32)*2 來讀取 Footer 的。

• SST 文件的 GET: 根據上文對 SST 文件的構造以及讀取方式，在某個 SST 文件中 GET 一個 key 需要先讀取 Footer，然後根據 Index Block 中的 key 來判斷目標 Key 是否在 DataBlock 中，因爲 SST 文件是按照 Key 大小順序排列的，同時 IndexBlock 中存儲着每個 DataBlock 的最小值，因此可以作爲第一層的判斷依據。當目標 key 恰好位於此 DataBlock 中時，還有 MetaIndex 中的布隆過濾器再進行依次過濾，其次纔是真正的讀取整個 DataBlock 內容，因此查詢效率變得更高。

• SST 文件的 PUT: SST 文件都是由 Immutable MemTable 一次性轉變而來，如上文的各類 Block 構造過程。並無單獨的 PUT 接口

• SST 文件的 Iterator: 遍歷接口則是根據 IndexBlock 中的 offset 和 length 將每一個 DataBlock 內容讀取並返回。

Version

上文講了 SST 的單個文件，但沒有講到 SST 的 Level 信息。整個 DB 需要對 SST 文件進行管理，包括各層級的文件 (s) 以及升級 (聚合、merge、Level 上升) 等信息，所以有了 Version 這個模塊，Version 是一個一步步向前的演進的模塊，同時整個 DB 架構圖中的 current 文件就是指向 Manifest，而 Manifest 存儲的就是對應的最新的 Version 信息。

在 Version 中很重要的一個過程就是將多個 Level N 的 SST 文件聚合然後變成更大的 Level N+1 的文件，在聚合過程中也是要完成排序操作的。因爲 Immutable MemTable 會變成 Level 0 的 SST 文件，也就是說 Level 0 的 SST 文件只會文件內部有序，而文件與文件之間無序。這一點需要注意。但是 Level 1 開始，因爲都是聚合而來的，文件與文件之間也是有序樂的。即上圖的 SST37 的 Key 都會小雨 SST38 內的 Key。

因此當低 Level 的文件向上合併時，會選取一個或多個高 Level 的文件進行 merge，視低 Level 的文件最小與最大 Key 的跨度來決定，如果橫跨兩個高 Level 文件則需要兩個高 Level 文件參與。這將會產生一個新的更大的高 Level 文件。之後將高 Level 文件加入到 Version 中，將之前的參與 Merge 的低 Level 與高 Level 文件移除，並將 Version 向前移動一步。SST 文件 Level 的升級過程便完成了。

過程說起來簡單，但實際上選取得到低 Level 中 SST 文件的跨度以及高 Level 的 SST 文件選擇也是有技巧的，但是合併過程中就像多個隊列一樣，因爲文件內部都是有序的，我們只需要做多路歸併即可。最後的到的大 size 的高 Level 文件，這樣一層層合併上去，Level 越高則文件 Size 也越大，但是得益於內部有序，以及 Index 的幫助，在查找時會快速的跨過絕大多數不需要的 DataBlock。

總結

其實通過上文的講解，對 LevelDB 的整個系統運轉過程大致有了一個簡單的思路，但這也只是最簡版，而且也有一些 BUG 存在，比如遍歷過程中，同一個 Key 如果先插入後 Delete 可能會被遍歷出來兩次，而這就需要更嚴格的邏輯來確保數據的準確性。但本文的着眼點在於 LevelDB 的整體思路，並不侷限於某個具體的 case。LevelDB 不像內存的數據庫，可以原地修改，爲了數據的 Merge 需要將多個 SST 文件讀取並重新輸出一次，其成本是很高的。而讀取的時候爲了加速讀取，設計了 Index Block 的布隆過濾器 (也可以其他方法替換，滿足對應接口即可)，減少真正對大文件的讀取。

希望通過本文可以幫助你對 LevelDB 有一個整體的宏觀認識。對 Level 的含義有了自己的解讀，對文件存儲的讀取學會了一個新的技巧 (遊標的移動設計、index 的讀取設計)。

列舉一個更高級的實現或者思考：

1. MetaIndex 使用布隆過濾器，即使 Key 的大小落在此 DataBlock 內，布隆過濾器可以先過濾一遍，通過了布隆過濾器才表示有可能存在，如果沒通過則一定不在。

2. 數據壓縮，本文都是明文存儲的數據有風險也浪費空間降低效率，那麼需要合理的壓縮算法來壓縮文件

3. 數據的校驗，即使壓縮完了，如何保證一個 sst 文件讀取出來是正確的呢，如果中間缺少了一個字節應該如何處理，那麼數據的校驗工作則是必須考慮的

4. 數據庫先寫 Log 來保存記錄是一種默認的行業潛規則，也是一個災後重建的恢復依據。

本文代碼 github 地址：https://github.com/zhaozy93/leveldb_golang

轉自：

zhuanlan.zhihu.com/p/107912389

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/TPo1HoUluVBJpfbp-YZedg