LevelDB Compaction 引發的 Data Inconsistency

用 LevelDB 的小夥伴請注意，你的 LevelDB 可能存在數據不一致的風險。

最近，我司分散式存儲團隊遇到了一個詭異的問題。現象很簡單，我們發現從 LevelDB 中讀取的數據是一個過期的（Deprecated）數據。例如，我們依次執行了 Put(Key1, Value1)，Put(Key1, Value2)，但是 Get(Key1) 時返回的是 Value1，而不是 Value2。

一開始，我們懷疑是不是自己程序的問題，畢竟 LevelDB 是一個廣泛被採用的項目，如果有這麼嚴重的 Bug，應該早就被修復了才對。但經過反覆的檢查，我們最終還是把懷疑的目標放在了 LevelDB 上。

於是我們瀏覽了 Github 上 LevelDB 項目的所有 Issue，發現了這樣一個問題：

Compaction causes data inconsistency when using snapshots。

順著這個線索，我們對問題進行了驗證，並最終證實了我們遇到的情況是由這個 Bug 引起的。不過很遺憾，這個 Bug 對應的 PR 到目前還沒有被 Merge 到主線。也就是說，大部分正在被使用的 LevelDB 代碼中，都隱藏著這麼一個非常嚴重的 Bug。

在這裡，我們詳細講解一下這個關於 LevelDB Compaction 的 Bug，幫助大家更好的理解 LevelDB 的實現細節。

LevelDB 背景

關於 LevelDB 的基礎背景，有很多文章進行過詳細的介紹，這裡我們只簡單帶過一下。

LevelDB 中，每一個 Record 由 <Key, SN(Sequence Number), ValueType, Value> 四部分組成。SN 是 LevelDB 在寫入數據時生成的一個全局遞增的整數，ValueType 表明這個 Record 是否為有效的 Record。

在 LevelDB 中，Record 分多層保存，從 Level 0 開始到 Level N。除 Level 0 外，每一個 Level 內的 Record 都是有序的，且被分別保存在多個文件中，每個文件被稱作一個 SStable。

Put 的流程

生成一個新的 SN
將 Record 寫入 WAL，用於保證 Crash Consistency
將 Record 寫入內存中的 Memtable

當內存中的 Memtable 超過一定大小時，被 Dump 到 Level 0，作為一個數據文件。

Delete 的過程

在 LevelDB 中，Delete 操作並不是通過直接在文件中刪除一個 Record 的方式來實現的。實際上 Delete 的過程和 Put 的過程相似，也是寫入一個 Record，唯一的區別是，Record 中的 ValueType 為 DELETE。這樣當執行 Get 操作時，如果發現 Record 中的 ValueType 為 DELETE，則認為這個 Record 已經被刪除掉了。而 Record 實際上從文件中被清除是在 Compaction 階段完成的。

Compaction 的流程

以 Level 0 的 Compaction 舉例，當 Level 0 的文件數據超過一定限制時，則會觸發 Compaction：

將 Record 從 Level 0 中讀出，並獲取這組 Record 的 Key Range
掃描 Level 1 中的文件，如果文件的中保存的 Record 和內存中的 Record 的 Key Range 有重疊，則將這個文件中的 Record 也載入到內存，以保證 Level 1 的 Record 在 Compaction 結束後依然是有序的
將所有載入到內存的 Record 按照 <Key, SN> 進行排序
如果發現有相同 Key 的 Record，則只保留 SN 最大的 Record
將排序並清理後的 Record 拆分成多個文件，並寫入磁碟，作為 Level 1 的文件
將 Level 0 和 Level 1 中被 Compaction 的文件從磁碟上刪除

每一層的文件超過一定數量時，都會觸發 Compaction 操作。非 Level 0 層的 Compaction 的流程和 Level 0 層的 Compaction 類似。區別在於，非 Level 0 層進行 Compaction 時，不一定將這一層的所有文件都 Compact 到下一層，而是可以選擇指定的幾個文件，或一個特定的 Key Range 進行 Compaction。

Get 的流程

從 Level 0 層開始逐層掃描，尋找這一層中 Key 相同且 SN 最大的 Record，如果這個 Record 的 ValueType 為有效，則返回這個 Record 的 Value，如果 ValueType 為無效，則意味著這個 Key 已經被刪除了，返回 NotFound 錯誤。

如果在某一層中找到了一個 Key 相同的 Record，則不會再向下一層尋找。

由於每一層的 Record 是有序的，所以 LevelDB 在內存中保存了每個文件的 Key Range，作為索引，這樣可以加速查找的過程。

以上是 LevelDB 最基礎的邏輯。更詳細的介紹，建議參考 leveldb-handbook - leveldb-handbook 文檔，裡面有非常詳細的介紹。

LevelDB Snapshot

在 LevelDB 中，還提供了 Snapshot 的功能。當執行 Snapshot 時，LevelDB 返回一個 Snapshot 對象。通過這個對象，我們可以獲得快照時刻的資料庫內容。

在 LevelDB 中，Snapshot 的實現非常精妙。Snapshot 並不是一個實體，只是記錄了 Snapshot 發生時的 SN。當 LevelDB 中存在未被釋放的 Snapshot 時，Compaction 流程將有所變化。而這裡面的細節是很少被大家注意到的。

帶有 Snapshot 的 Compaction

我們在這裡再回顧一遍 Compaction 流程：

將 Record 從 Level 0 中讀出，並獲取這組 Record 的 Key Range
掃描 Level 1 中的文件，如果文件的中保存的 Record 和內存中的 Record 的 Key Range 有重疊，則將這個文件中的 Record 也載入到內存，以保證 Level 1 的 Record 在 Compaction 結束後依然是有序的
將所有載入到內存的 Record 按照 <Key, SN> 進行排序
如果發現有相同 Key 的 Record，則只保留 SN 最大的 Record
將排序並清理後的 Record 拆分成多個文件，並寫入磁碟，作為 Level 1 的文件
將 Level 0 和 Level 1 中被 Compaction 的文件從磁碟上刪除

按照這種方式進行 Compaction，可以保證除了 Level 0 層外，每一層中相同的 Key 只會出現一次。

Compaction 的一個很重要的目的，就是對 LevelDB 中保存的『無效』 Record 進行清理。然而，當 LevelDB 中存在 Snapshot 時，為了保證 Snapshot 對應的數據可以被訪問到，需要調整對『無效』的定義，避免屬於某個 Snapshot 的 Record 被清理掉。因此 Compaction 流程中的第四步被調整為：

如果發現有相同 Key 的 Record

如果有 Snapshot，則保留大於 Snapshot SN 的所有 Record，以及一個小於 Snapshot SN 的 Record 中，SN 最大的 Record
如果沒有 Snapshot，則只保留 SN 最大的 Record

這樣，Snapshot 時 Record 的狀態，就通過保留最接近 Snapshot SN 的 Record 的方式保存了下來。當通過 Get 操作讀取 Snapshot 時，只會查找 SN 小於 Snapshot SN 的 Record。SN 大於 Snapshot SN 的 Record 都被視為是無效的。

隨著 Compaction 流程的變更，在存在 Snapshot 的情況下，Compaction 的會導致每一層中可能會保存有多個具有相同 Key 的 Record，他們按照 SN 被排序。如果這些 Record 比較多，或者 Value 比較大，則這些 Record 可能會被分別保存在不同的文件中。這就為這個 Bug 埋下了隱患。

Compaction 的 Bug

在 LevelDb 中，觸發 Compaction 的條件有很多。對於非 Level 0 層來說，可能會觸發對某一個單獨文件的 Compaction 操作。

而這裡面的問題在於，當觸發對某個文件的 Compaction 時，LevelDB 只在下一層中查找 Key Range 存在 Overlap 的文件，而忽略了在同一層中，也可能存在有 Key Range Overlap 的情況。例如：

當對 file2 進行 Compaction 時，file1 中的兩個記錄 <k1 sn1>, <k1, sn2> 有可能會被保留下來。這就會導致當 Get(k1) 的請求查詢到 level n 時，會獲取到一個過期的 Record <k1, sn2>。而實際上真正有效的 Record 是被保存在 Level N+1 層。

我們可以通過這段代碼復現這個問題。你也可以在自己的環境上編譯並執行一下看看。

[kyle@localhost test]$ g++ test_leveldb.cc -lleveldb && ./a.out modified=388 modified=236 ... modified=38 modified=368 Value MISMATCH key=2776

解決方法很簡單，在對某個文件做 Compaction 時，先在同層的文件中查找是否有 Key Range Overlap 的情況，如果有的話，則需要把對應的文件也加入到 Compaction 的過程中，例如在上面的例子中，對 file2 的 Compaction 會觸發把 file1 也一起進行 Compaction，這樣就避免了問題發生。

具體代碼可以參考這個 PR。

關於 RocksDB

RocksDB 是源自 LevelDB 的項目，不過貌似 RocksDB 很早就已經把這個問題解決了。至於為什麼沒有 backport 到 LevelDB 就不得而知了。

LevelDB Compaction 引發的 Data Inconsistency