LevelDB源碼解析5. 數據完整性

通過前面一篇文章LevelDB源碼解析4. 架構設計 可以大概了解整體架構的設計。但是實際上還是會有一些疑問。那就是每個文件的作用是拿來作什麼的？這一切主要的目的就是回答這個問題：

每個文件的作用是什麼？

LOG文件

LevelDB裡面有兩種log文件。

• 平時自己寫程序的log.println()的輸出，是放到LOG文件的。比如

$ cat LOG2018/03/17-20:59:10.663121 7fff783bb300 Delete type=3 #1

• WAL LOG文件，或者說binlog。是用來支持事務完整性的。

$ cat 000003.log?JS?)KeyNameExample ValueExample

對於WAL LOG或者說binlog，在不同的軟體裡面有不同的叫法。也有軟體是叫Journal。那麼倒底是什麼？為什麼需要這麼個東西？

事務完整性

數據的完整性是說：當一個數據的狀態要從a=X改變到a=Y的過程中時。要麼成功，要麼失敗。不會出現a=X.5這種中間狀態。

這裡並不去展開講，只是從容易理解的角度去講解這個問題。

假設需要設計一個非常簡單的系統。這個系統要完成的一個任務就是存下。

int a = x;

單變數，用戶可以不停地寫入新的值。也可以查詢當前的值。除了程序的可用性。需要保證的就是數據的完整性。

程序直接跑在內存裡面就不用想了，掉電就沒有了。

這個時候有個辦法就是：

1. 定義個結構體：

struct Operation { int variableToChange; int valueToPut;};

2. 接收到用戶請求a = 34的時候。生成

struct Operation record{variableToChange=a, valueToPut=34};

然後把這個結構體寫入到本地磁碟文件0001.log中。

3. 寫入成功之後，把內存中的變數修改為a = 34。

4. 返回客戶端說修改成功。

在這四步中間的任何一步由於物理原因導致失敗。那麼都會回復客戶端說「更新失敗」。但是一旦回復客戶端「更新成功」，那麼將就是永久更新成功。

如果更新成功之後，掉電關機。當應程序再次啟動的時候。只需要從0001.log中依次讀取每個record就可以把內存中的歷史演變依次進行回放。最終達到最後更新完成的狀態。

問：如果寫WAL LOG的時候，寫到一半關機了。 那麼恢復的時候還會成功么？

答案是：會的。如果寫到一半關機。struct Operation也只寫了一半。那麼想想C語言從文件中讀取一個struct的時候。這個讀取也是會失敗的。這個讀取失敗也不要緊，只是說明最後一次更新沒有成功。數據還是處於舊的狀態。完整性仍然得到了保證。

問：如果WAL LOG寫放完成是成功了。但是更新內存時，掉電關機了。客戶端收不到響應， 最後回放WAL LOG的時候，狀態卻發生了更改，這又怎麼辦？

答：這個其實和事務完整性是沒有關係的。一定要明白事務的完整性說的是：

從狀態x = A改變到x = B的過程中，不會出現任何其他中間狀態。x的最終狀態只會在{A,B}中選擇一個。

對於客戶端的響應則是：

1. 更新成功2. 不響應，因為掉電或者其他物理原因關機。3. 更新失敗任何一個更新操作，都可能是：{2, 3} ==> {A}{1, 2} ==> {B}

LOG對事務的支持

通常意義義上的日誌文件是在LOG中。如果文件名是${number}.log。那麼這種文件在leveldb中就是用來支持事務的。裡面寫入的就是各種各樣的結構體。

圖片出自：Draveness - 簡書

寫流程中的過程就很明了了：這裡我們只考慮最簡單的情況。也就是memtable還有足夠空間的情況下。

1. 先寫WAL LOG，也就是圖中的tablet log。
2. 再更新到內存
3. 返回客戶端說更新成功。

Manifest的事務

前面介紹了Manifest裡面存放的內容，但是並沒有詳細介紹為什麼需要存放那些內容。

通過事務的理解，接下來可以詳細講一下Manifest是如何支持LevelDB的事務的。

首先還是從SSTable合併講起。

為什麼需要合併?

每當WAL LOG寫完就把結果更新到內存裡面供讀者使用。那麼當內存不足的時候怎麼辦？

這裡想像一種最簡單的處理方法。就是每當內存不足的時候。就直接把內存寫到磁碟上。把內存清空。然後內存就足夠使用了。那麼這種處理方法，問題就來了。

• 如果KV裡面的Item特別多，會導致內存塊經常刷寫到磁碟上。這些磁碟塊之間的內容實際上是有相同的。
• 讀取的時候，如果在內存裡面找不到相應的Key，則需要依次去磁碟文件裡面一個一個找。

那麼一種想法就是：當Level0的文件數目 >= N的時候。直接把Level0的文件進行合併。合併的結果如下：

也就是說，數據從Level 0整理到了Level 1。並且Level 1裡面的數據是沒有重合的。當Level 0的文件很多的時候（寫入的key的不斷增多）。那麼Level 1裡面的文件也會增加。

那麼問題也會隨之而來。當Level 1裡面的文件增多的時候。也是需要合併的。也就是形成了如下結構。

現在把思路到回到單次的合併操作。

單次的合併

單次的合併操作順序如下圖所示：

可以看出來，合併過程實際上就是：

{<17, 40>, <12, 19>, <22, 45>} => {12, 45}

為了保證數據的安全性。如果直接基本原來的數據文件做修改。那麼萬一在修改某個文件的時候，掉電了，那麼數據的完整性就無法保證了。因此，這裡需要引入約束：

1. 在合併的時候，不允許修改已有的SSTable文件。只允許生成新的文件。

如果用簡單的代碼描述如下：

const SSTable files{Range1, Range2, Range3};const CompationOperations compact(Range1, Range2, Range3);SSTable newFiles = files + compact;

合併時的事務支持

這個時候，compact可以看成是發起來的更改請求。為了保證數據的完整性，就需要把compact寫WAL LOG。寫入成功之後。再生成newFiles。

1. 如果寫WAL LOG失敗。那麼讀WAL LOG的時候，也不會成功。那麼文件的狀態還是files。2. 如果寫入WAL LOG成功。但是生成newFiles時失敗。那麼系統恢復時:操作如下 - files是沒有更改過的，且一直存在的。生成之後，不會有修改動作。 - compact是寫入到WAL LOG的。寫入成功之後，只需要讀出這個compact，然後再操作一次。 生成newFiles。

而針對SSTable的WAL LOG叫Manifest。

引用

1. Draveness - 簡書

推薦閱讀：