LevelDB源碼解析3. 基本思路

來自專欄 CodeIt

第一義

在閱讀源碼之前，應該回答這個問題：

源碼的大概框架結構是什麼樣的？

這個問題非常重要。如果有了大概的框架結構，那麼後面在看代碼的時候就心中有數。相當於房子框架已經搭建好了。後面需要看工程師如何堆磚塊與實施工程技術手段。

這是看源碼重要的方法論。

LevelDB能做什麼?

class DB { public: virtual Status Put( const WriteOptions& options, const Slice& key, const Slice& value) = 0; virtual Status Delete( const WriteOptions& options, const Slice& key) = 0; virtual Status Write( const WriteOptions& options, WriteBatch* updates) = 0; virtual Status Get( const ReadOptions& options, const Slice& key, std::string* value) = 0;}

簡單來說，也就是四個介面。

1. Put
2. Delete
3. Write
4. Get

Write與Put的區別在於，Write是批處理寫。比如有兩個{key1: val1, key2: val2}一定要同時寫入，要麼同時寫成功，要麼同時寫失敗。而Put只是支持單項的寫入。(從底層實現上來說，最後都是調用Write介面。因為寫單項的時候，只是相當於批處理裡面只有一個Job，從而實現了統一)。

LevelDB解決的問題

如果只是從簡單的代碼的角度上來講。實現這四個介面的代碼並不難。那麼為什麼LevelDB面臨的問題又是什麼？要解決的問題又是什麼？

假設想完成一個單機版的KV存儲系統。

• 不能只用內存，一個是數據量很大。內存存不下。不能只用內存的另外一個原因是：內存掉電後，內容會丟失，用戶存儲的數據是一定要持久化的。
• 數據持久化也就意味著需要寫到磁碟上。存儲資源空間可以很大，但是速度則會很慢。
• 磁碟的特點是：順序寫與順序讀速度比較快。隨機寫與隨機讀則需要磁碟尋道。因此單位時間內的讀寫(IOPS)比順序的情況要差。一般要下降3倍左右。

這個時候就清楚LevelDB需要解決的問題是什麼樣的了。

• 在以上條件的制約下，如何設計一個可靠的高性能的KV存儲系統。

版本1

在直接去看LevelDB的設計的時候，想大致地整理一下思路。進而可以更好地知道為什麼LevelDB要這麼設計。

知道Why有時候比知道What, How更加重要。

想像一下非常極端的例子。如果極度地追求寫入速度。能多快就多快的情況下。假設磁碟足夠用。那麼每次寫入的數據是以下情況就可以了。

也就是直接採用WAL的工作方式。每次都是只是把要寫的操作扔到磁碟上。但是這樣只是滿足了兩個要求：

1. 數據寫入速度最快
2. 數據持久化

也就是：

class DB { public: virtual Status Put( const WriteOptions& options, const Slice& key, const Slice& value) = 0; virtual Status Delete( const WriteOptions& options, const Slice& key) = 0; virtual Status Write( const WriteOptions& options, WriteBatch* updates) = 0;}

但是這種處理方式是不能服務讀求請的。萬一來了讀請求，立馬就歇菜。通過版本1已經可以支持其中的3個介面了。現在只需要重點考慮如何支持Get請求。

virtual Status Get( const ReadOptions& options, const Slice& key, std::string* value) = 0;

由於寫入的時候是順序的。能夠獲得性能最大的提升。那麼肯定也想讀最好也是可以達到性能最大化。也就是讀的時候，也是順序讀為主。如何實現呢？

版本2

現在知道版本1是肯定不能服務讀請求的。那麼接下來如何支持讀請求呢？

當數據量小的時候，比如客戶的數據只有1MB。也就不用那麼麻煩了。 在版本1的基礎上加上一個內存表。

• 每次WAL寫入到磁碟之後，立馬更新到內存裡面。
• 當發現有讀請求過來的時候，立馬到內存中查找相應的表。

但是，這種方案只能是支持數據量比較小的情況。如果數據量一大。那麼內存肯定是存不下那麼多客戶的Key/Val的。剩下的情況還是需要到磁碟中來進行查找。那麼這個時候，情況就分成了兩種：

1. 內存中可以找到，直接返回。
2. 內存大小總是有限的，數據量大的時候，肯定有一部分是在磁碟上。那麼必須要到磁碟上尋找。

前面的思路實際上是把內存當成了一個狀態機。然後所有狀態的更新操作都是在內存上完成。（更改記錄則是通過WAL LOG持久在磁碟上。如果機器掉電，那麼只需要新的把WAL LOG在內存裡面回放則可）。

現在只需要處理第2種情況就可以了。由於WAL的方式，會導致的情況是，磁碟數據布局如下：

實際上，針對於讀而言。歷史數據作用不是特別大。重要的是當前數據值。

這個時候，除了把內存當成一個狀態機，還可以把內存＋磁碟一起組成一個巨大的狀態機。

從狀態機的角度來考慮就是，WAL記錄了修改操作的每一個歷史記錄。而餘下的內存和磁碟則用來組成一個KV系統的狀態機。這個狀態機的記錄了當前的KV值。並且可以滿足如下目標。

1. 維持數據的有序性：有序性主要是為了查找方便。比如能夠快速地找到key對應的val是多少。
2. 能夠快速地遍歷區間。比如位於aa到cc中間的key/val有哪些。都取出來吧。

其中WAL LOG與內存數據是等價的。如果掉電，WAL與disk block都是存在的。數據的持久性仍然可以得到保證。State Machine由於是有序的。讀取的速度也可以保證。

接下來的問題就是：如何保證有序性？考慮這樣一種演算法：

1. 先寫WAL LOG
2. 然後把WAL LOG裡面的操作更新到內存裡面。
3. 當內存容量不足的時候，把內存裡面的內容與磁碟上的block合併。

這樣的操作如下圖：

但是如果這樣操作，很容易出現合併的時候，合併的寫入就變成了隨機寫。那麼有什麼改進的方法呢？

版本3

考慮到內存裡面的數據都是有序的。那麼在處理的時候可以這樣。

1. 寫WAL LOG
2. 更新內存，即是下圖中的MemTable
3. 當內存size達到一定程度的時候。把Memtable變成不可變的內存塊。
4. 把內存塊與磁碟上的Block。這裡叫做.sst文件進行合併。到這裡內存的合併是順序寫的。
5. 磁碟上的block根據新舊先後分層。總是上面一層的與下面一層的合併。
6. 讀的時候先查內存，內存中沒有的時候，再順次從Level0~LevelN裡面的磁碟塊內容。直到找到Key即返回相應的val。找不到說明不存在，返回NULL。