PebblesDB讀後感

SOSP2017[1]於10月底在上海舉辦，因為離得比較近，筆者也去參加學習了一下。會議上的大部分文章都相當的務實，有的甚至可以直接輔助工程實踐，比如將要分享的PebblesDB[2]。

10年前Google發表BigTable[3]的論文，推動了基於LSM的KV系統架構的流行，而隨著KV系統的應用面超越NoSQL資料庫走向越來越廣闊的領域，LSM的寫放大問題也越來越成為系統穩定的一個阻礙。在LevelDB/RocksDB這種分層思路上，PebblesDB提出了一種減少寫放大的思路，下面學習並總結，所述以論文為基礎，也有個人觀點，客觀論述請看原文。

雖然LSM的寫放大最近被研究很多，但是就寫放大本身而言，是一個很古老的問題。在計算機體系中，如果相鄰兩層的處理單元不一致或者應用對一致性等有特殊的需求，就很可能出現寫放大問題。比如CPU cache和內存cell，文件系統block和磁碟扇區，資料庫block和文件系統block，資料庫redo/undo，文件系統journal等。文中對寫放大給了一個明確的定義，就是用戶寫入數據和系統寫入數據的反比，比如用戶寫了1M，系統在穩定之後一共向存儲設備寫出10M，那麼放大係數就是10。一些熟知的系統，其放大係數可能超越我們的想像，見下圖1（如無特殊說明，圖片均來自論文[2]）

RocksDB放大係數高達42倍，LevelDB也高達27倍，不看絕對數字，只看趨勢的話，還是符合直覺的，畢竟RocksDB做了不少加速compaction的功能優化。本文的PebblesDB做的不錯，但是仍然超過了10。寫放大意味著更多的讀寫，會造成系統波動，對比如SSD來說會加速壽命衰減，從成本角度說也更加耗電，所以解決寫放大就成了一個很重要的問題。我們看這張圖的時候，理解放大很嚴重就可以了，具體數字不必計較，現實中當然有很多針對具體業務的辦法把放大控制在一定範圍。

作者分析了LevelDB/RocksDB使用的分層結構，認為有一個關鍵問題導致了其寫放大很嚴重，即L0層數據可能跟Lx層全range交疊。圖2很好的說明了這個問題。

圖2顯示，L0文件裡面包含的key同時在L1層的多個文件（甚至全部文件）被包含，所以如果想把L0下推到L1，那麼就需要將整個L0/L1文件內的key讀出來重新排序寫入到L1。典型情況下，L0數據量是L1的1/10，為了這麼點數據量重寫所有數據顯然不划算。L1...Ln道理類似。

思考問題的本質有助於判斷終極解決方案，放大問題的本質是一個系統對「隨時全局有序"的需求有多麼的強烈。所謂隨時，就是任何的寫入都不能導致系統無序；所謂全局，即系統內任意元單位之間都要保持有序。B-Tree系列是隨時全局有序的典型代表，而Fractal tree打破了全局的約束，允許局部無序，提升了隨機寫能力；LSM系列進一步打破了隨時的約束，允許通過後台的compaction來整理排序。在LSM這種依靠後台整理來保序的系統裡面，系統對序的要求越強烈，寫放大越嚴重。

PebblesDB針對寫放大提出的解決方案是弱化全局有序的約束，其將每一層進行分段，每個段稱為一個guard，guard之間沒有重疊的key，且每層的guard之間要求保序，但是guard內部可以無序。這個跟skiplist的思路非常像，所以作者說是從skip list借鑒了思想，見圖3。

圖3看起來確實很像一個skiplist，guard如果在上一層存在，那麼下面所有層都存在；同層相鄰guard之間無交疊（L0數據少，沒有guard）。如前面分析，分層組織結構導致寫放大的原因是Li在下推數據的時候跟整個Li+1是重疊的，所以導致所有Li和Li+1的數據都要重寫，這顯然增加了寫放大。而這裡將Li和Li+1分為多個guard，那麼當Li層數據需要下推的時候，不再是整個Li一起下推，而是可以按照guard為單位來進行，那些基本沒有數據變化的guard就不用下推了。在guard下推的過程中，另外一個屬性進一步減少了寫放大，那就是guard內文件之間不必有序，這樣有些文件可能不需要讀取，直接move過去就可以了。很奇妙！結果當然也不錯，顯著減少了寫放大，見圖4。

圖4顯示，在三個級別的數據規模上，PebblesDB都獲得了較低的放大係數，典型對比甚至降低一倍以上。文中還有非常多方面的對比，學術論文的考慮周全、測試嚴謹是非常值得學習的。

通讀全文來看，該思路減少寫放大還是比較容易理解的，因為削弱了全局序。當然代價就是scan的時候變差了，因為scan天生對序有強烈的依賴，作者提到可以通過提高IO並發等緩解scan性能的下降。文字還提到了guard帶來的其他好處，比如compaction的並行度變大了，每個guard所代表的相鄰層可以獨立進行compaction以及guard的選擇、空guard的處理問題。

[1]. SOSP2017: https://www.sigops.org/sosp/sosp17/program.html

[2]. PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees

[3]. BigTable: http://research.google.com/archive/bigtable-osdi06.pdf

[4]. LevelDB: https://github.com/google/leveldb

[5]. RocksDB: https://github.com/facebook/rocksdb/