WiscKey: Separating Keys from Values in SSD-conscious Storage

說明

目前越來越多的KV存儲的引擎採用了LSM-tree的結構，如LevelDB（HBase存儲引擎）、RocksDB（Facebook基於LevelDB優化的引擎）、Riak等，LSM-tree的主要架構如下圖所示：

LSM-tree以及基於其實現的存儲引擎有以下特點：

1. 小的隨機寫IO被順序化為大的連續IO；
2. 磁碟上的物理文件（sstable）被分層為多個level，且隨著系統的運行，層級低的數據會向層級高的數據合併。

因為LSM-tree將大量的隨機IO變成了順序IO，因此對HDD此類存儲介質有著比較明顯的性能提升。但同時，此架構也會帶來如下一些問題，最主要的便是IO放大以及IO放大帶來的副作用。

LSM-tree結構之所以帶來IO放大，是因為：

寫入時，除了將數據順序寫入日誌外，還考慮將memtable寫入level 0 的sstable以及由此帶來的sstable合併問題，根據論文作者的計算，在極端情況下，可能帶來的放大係數為10*Level；

讀取時，首先需要查找文件所在的sstable，由於sstable分層，因此該過程要由低向高level逐漸查找，在極端情況下，需要遍歷所有sstable的元數據塊，也帶來了相當程度的讀放大。

而這種IO放大會帶來怎樣的副作用呢？

顯而易見的是IO效率的降低；

對於SSD存儲器件，這种放大還會導致存儲硬體的壽命縮減。

因為SSD優異的隨機IO性能，隨機IO和順序IO的性能比沒有HDD的那樣突出，因此，這種LSM-tree結構帶來的順序IO好處無法彌補IO放大帶來的劣勢。那如何在SSD存儲環境中設計高效的存儲引擎？這是本篇論文關注的重點。

WiscKey

WsicKey便是為了解決該問題而設計的存儲引擎，其主要設計思路是：

對象的key與value分離

其中，元數據包括對象的key以及對象數據的位置，就是一個<key, addr>的二元組；數據則是對象的實際數據，被存儲在value log區域，實際上就是write-ahead log了。

對象的數據是被按照順序追加的方式存儲在value log中，依然滿足順序寫的特點；而對象的元數據則依然使用LSM-tree來存儲，與LevelDB的存儲別無二致，只是只存儲元數據罷了，數據量小了好幾個數量級。

接下來我們分析如此設計有什麼好處？

數據只寫日誌Value Log，避免了數據日誌和sstable的雙寫，提高IO效率；

只將元數據寫入LSM-tree，雖然也會存在IO放大，但是由於數據量很小，總體的放大效果明顯降低。

對於好處2，論文中有一個大概的計算，假設對象的元數據為16B，對象數據大小為1KB，按照LSM的放大係數為10來計算，採用WiscKey設計，寫入的總體放大率約為：

對於讀操作，由於LSM-tree的數據量已經顯著減少，總的sstable文件數量也相應減少，元數據的查找過程也會加快，只是不太好評估這個效率。而且，LSM-tree數據量的減少還能帶來另外一個好處：可以盡量多的緩存元數據，進一步提高元數據檢索的效率。

幾個問題

因為將對象數據和元數據分開存儲，可能會導致以下幾個問題：

• 垃圾回收；
• 數據一致性；
• 讀性能優化。

接下來我們一一闡述，問題是什麼以及WiscKey是如何解決這些問題。

垃圾回收

LevelDB等之類LSM-tree的存儲系統對於對象的刪除只是追加刪除標記，延期至sstable compaction的時候回收那些無效數據。

對於WiscKey的設計，由於元數據和數據分離，回收涉及兩個方面：元數據的回收和數據回收。

元數據回收與LevelDB類似，無需贅言。對象的數據位於Value Log區，如何回收Value Log區的無效對象呢？

如上圖所示，WiscKey設計了一種比較巧妙的思路：log區有兩個指針 head和tail。head指向當前新數據待寫入的位置，而tail則指向當前待回收的位置。

當觸發垃圾回收時，從tail位置讀取一條記錄，並從元數據判斷其是否已經被刪除：

• 如果是，則tail向前移動至下一條記錄；
• 如果不是，則將該記錄寫入至head位置，接下來再將tail移動至下一條記錄。

當然，為了避免垃圾回收過程不會因為異常導致數據丟失，會將head和tail信息持久化，當然，最好的地方便是LSM-tree內了。

當然，由於垃圾回收涉及IO（先讀後寫），因此不建議太頻繁，只有在刪除操作頻率比較高時才觸發該操作。

數據一致性

因為數據和元數據分離存儲，因此，勢必存在數據不一致性，如數據寫入成功但元數據寫入失敗，或者相反。

如果數據存在，但是元數據不存在，那在後續的垃圾回收時數據會被清理。

如果元數據存在，那麼接下來還需要驗證數據有效性。驗證的方法也比較多，如checksum、magic等。如果驗證失敗，那麼會將元數據清除。

數據讀優化

由於數據和元數據分離，數據的讀取先是從LSM-tree讀取元數據，然後再根據位置從Value Log中讀取數據。這樣做的劣勢是會產生隨機IO。

雖然SSD對隨機IO性能有較大的提升，但是較小的隨機IO依然會對性能產生較大影響。但是SSD也有個特性就是可並行的隨機IO也會充分發揮其性能，如下圖：

可以看到，在32個線程並發時，16KB的隨機IO就基本快達到了SSD的帶寬上線。

考慮到SSD的這種特性，WiscKey對range query進行了並發讀的優化，具體的做法是：

1. 對於range query，同時取出多個key的元數據信息<key, address>
2. 將這些<key,address>信息放入隊列，並喚醒預讀線程（默認32個）
3. 預讀線程開始讀數據

參考

• https://www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf
• http://github.com/dgraph-io/badger
• http://github.com/utsaslab/pebblesdb

推薦閱讀：