閱讀 sosp 2017 《PebblesDB : building key-value stores using fragmented log-structured merge trees》 的筆記。本篇只記錄了論文核心思路，很多細節讀者還是需要閱讀原文。

1. Background

1.1 Basic Introduction

這篇還是研究的 LSM-tree 的優化，主要還是針對 LSM-tree 的老問題，write amplification 做優化。關於 LSM-tree 的基本原理和存在的問題，可以參見之前一篇博文 【FAST 2016】Wisckey-Separating Keys from Values 的第一章節。這裡給出論文中一組關於 LSM-tree 的 write amplification 的數據：

由上圖不難發現傳統的 LSM-tree 存在嚴重的 write amplification。為了解決這個問題，論文作者受 Skiplist 的啟發，設計了一種 Fragmented Log-Structured Merge Trees data structure （FLSM-tree），並開發出了一個 key-value 單機存儲原型 PebblesDB，可以有效的減少 write amplification；由 Figure.1 可以看出， PebblesDB 的 write amplification 遠小於 leveldb 和 rocksdb。

1.2. Write Amplifcation Root Cause

再介紹 FLSM-tree 之前，先來分析下 LSM-tree write amplification 的根本原因，也是論文優化的動機和思路，一句話描述就是：一些 key-value 在某一層中反覆的 compaction ，從而造成被rewrite。下面將通過一個例子著手來解釋，如下圖：

我們知道 level n 往 level n+1 挪動的時候，是通過 Compaction，其大致的過程是，這裡假定 level n 中的 sstable A 要通過 Compaction merge 到 level n+1，那麼就會在 level n+1 找到所有和 level A [min key, max, key] 有交集的 sstable 做歸併排序合併成 level n+1 新的 sstable，（1）例如 Figure 2. 的 t2 時刻， level 0 的 sstable [20, 210] 與 level 1 的兩個 sstable 合併，這個 1，10 ，100 和 200，210，400 被重寫了第一遍；（2）然後在 t4 時刻，發生第二次 Compaction，由於 level 0 的 sstable 和 level 1 的兩個 sstable 又都有交集，這個時候 1，10 ，100 和 200，210，400 又被重寫了第二遍；（3）在 t6 時刻，同理由於由於 level 0 的 sstable 和 level 1 的兩個 sstable 又都有交集，這個時候 1，10 ，100 和 200，210，400 又被重寫了一遍，這個時候已經被重寫了第三遍了。

由上面的例子可見一斑，Compaction 造成了一些 key-value 反覆的 rewrite，從而造成了 LSM-tree 的 write amplification，如果有什麼辦法可以控制一個 key-value 在某一層被 rewrite 的次數就好了，那麼結合 LSM-tree 的層數限制，每個 key-value 最壞情況的 write amplification 都將是有上界的。這也正是後面要介紹 FLSM-tree 能做到的。最終 PebblesDB 通過減少 write amplification 來提高了 throughput，

2. PebblesDB

PebblesDB 受 Skiplist 的啟發，設計了 FLSM-tree，其可以保證 so ensures that data is written exactly once in most levels，是不是很牛。

2.1. Skiplist

既然受 Skiplist 的啟發，那麼我們先來看看 Skiplist ，在剛開始接觸 Skiplist 的時候，並沒有很好的理解 Skiplist 的精妙之處，實際上 Skiplist 有一個很精妙的東西叫 Guard，如下圖，給出了一個邏輯的 Skiplist，

其中最低層的 level 1 存放了所有的數據，並且保持有序，上面的 level 2 和 level 3 上的所有節點其實都是 Guard，那麼什麼是 Guard 呢？其實就是高速通道，也就是索引層，實際上和 B+ tree 很像，其基本結構是一樣的，只是節點插入和刪除的時候，索引的層的選擇有一些差異，Skiplist 是基於一定的隨機選擇策略來選擇索引 Guard，而 B+ 則是一棵有序的搜索樹，通過節點的合併和分裂來實現的，但是本質上是一樣的。

2.2. FLSM-tree

FLSM-tree 借鑒 Skiplist 的 Guard 思想，給 LSM-tree 的每個 level 加了一些 Guard 數據，通過 Guard 來組織數據，儘管很簡單，但是思路很巧妙，下面通過一個例子來說明:

level n 有數據 {1， 20， 45，101， 245}

level n+1有三個guard分別為：1、40、200

那麼 level n 往level n+1 Compaction的時候不會去和其他的 sstable 合併，而是將自己的 sstable 按照 guard 切分成多個 sstable（也就是fragement），合併到 level n+1之後就變成了：

level n+1:

guard: | 1 | 40 | 200 |

| { 1,20 } | { 45,101 } | {245} |

這樣就保證了每次的只有這個 sstable 在往高的那個 level compaction 的時候只會產生一次切分的 rewrite。而且 sstable 按照 guard 來管理，而且不同的 guard 的之間是沒有影響的，所以，可以並發的compaction。

3. Summary

PebblesDB 借鑒 Skiplist 的思路非常的精妙，雖然簡單，但是結合 1.2. 的例子可以看到其明顯的減少了 Write amplification，而一旦減少 write amplification 的，那麼將給 write 的性能有相當的提升。當然還有更多這裡沒有介紹，感興趣的可以詳細的閱讀論文，這裡不再詳細的描述：

  1. guard 的選擇，類似 skiplist ，guard 的選擇是很關鍵的，它是每個 level 的 fragement 是否均衡的關鍵，而 fragement 的均衡性將大大的影響到 read 的性能
  2. 數據是動態的在不同的 level 之間遷移的，那麼 guard 肯定也不是一層不變的，如何 insert/delete 也是一個非常重要問題，而且一旦 guard 發生變化，那麼相應的 fragement 的數據將產生大量的移動和 rewrite，是一筆不小的開銷，處理起來也是相當的不容易
  3. read 的性能問題，由於 Compaction 的時候，sstable 只是簡單地被切分到不同的 fragement ，那麼意味不同的 fragement 的數據被分散在不同的 sstable 文件中，而且這些 sstable 文件相互之間是可能有交集，那麼自然對讀的性能是由影響 ？這其實也是第1、2 個問題需要考慮的

其中在參考文獻 [2] 有個描述覺得非常贊同：系統對序的要求越強烈，寫放大越嚴重

References

[1]. PebblesDB building key-value stores using fragmented log-structured merge tree. cs.utexas.edu/~vijay/pa

[2]. PebblesDB讀後感. zhuanlan.zhihu.com/p/32


推薦閱讀：
查看原文 >>
相关文章