本文為哈佛大學(xué)DASLab自研的CrimsonDB存儲系列文章第二篇,完整的系列文章列表見http://daslab.seas.harvard.edu/projects/crimsondb-demo/#publications
CrimsonDB第一篇 Monkey: Optimal Navigable KeyValue Store
與第一篇類似上枕，本文在 Monkey的數(shù)學(xué)基礎(chǔ)之上烁兰，通過建模的方式對LSM 的時間復(fù)雜度和寫放大度進行了建模分析拨扶，通過權(quán)衡時間復(fù)雜度和寫放大割坠，提出了lazy compaction的設(shè)計方案蕴侧。本文的核心啟發(fā)來源于最底層的數(shù)據(jù)量最多，因此主要得查詢開銷來自與最底層涤妒。第一篇文章提到上層的數(shù)據(jù)需要的bloom filter內(nèi)存空間很小渣触，因此上層的數(shù)據(jù)查詢大部分可以通過bloom filter進行優(yōu)化。那么是否可以通過降低上層的compaction來減少io放大呢蟋字，延時上層compact會由于overloap帶來部分的查詢放大稿蹲，但是這些放大和降低io的開銷相比起來某些時候是可以忽略的，因此可以通過動態(tài)調(diào)節(jié)compaction來達到時間復(fù)雜度和io寫放大的平衡鹊奖。
空間放大
在分析空間放大之前苛聘，再次簡單介紹下tiering compaction和leveling compaction。level層內(nèi)部不存在overlap忠聚，tiering層內(nèi)部則可能存在overlap设哗。因此對于tiering，極端情況下 如果每一個run之間都存在overlap两蟀，那么空間放大為O(T),网梢。對于leveling，由于層內(nèi)部不存在overlap垫竞，層級之間的數(shù)據(jù)層T倍增長澎粟，因此極端情況下L(n-1)的數(shù)據(jù)都被更新了，此時leveling的空間放大為N(1/T).
IO 放大
通過對點查和scan進行建模復(fù)雜度分析欢瞪，發(fā)現(xiàn)主要的查詢開銷來自于最底層活烙。因為最底層的entry數(shù)量最多，同時基于第一篇提到的遣鼓，上層的run可以通過設(shè)置bloom filter來優(yōu)化查詢啸盏，因此可以通過延時上層run的compaction來減少io的開銷，通過犧牲一定的查詢開銷來大幅降低merge io骑祟，上層的查詢開銷大部分可以被 bloom filter所處理因此相比于減小IO放大帶來的收益這個開銷可以忽略不計回懦。
通過delay compaction來降低merge的IO 開銷，其實就是在tiering與leveling兩種策略之間進行權(quán)衡次企。rocksdb默認(rèn)的compaction策略是L0 使用了tiering怯晕，其他level使用了leveling。本文則更近一步缸棵，在除掉最底層level的層級進行進行compaction策略的權(quán)衡舟茶。
Lazy leveling
lazy leveling的思想是在1到L-1層使用tiering ，在L層使用leveling堵第。通過該策略可以保證在1到L-1層每層之內(nèi)最多包含T-1個run吧凉，在L層最多包含1個run，因此空間放大依然是O(1/T). 與第一篇提到的一樣踏志，Dostoevsky 每一層的FPR也是指數(shù)遞增的阀捅。
通過下面的建模分析可以發(fā)現(xiàn)，lazy leveling在降低merge IO的同時并不會給查詢帶來額外大的開銷
Fluid LSM-Tree
lazy leveling的思想是L 層使用leveling针余，其他層使用tiering饲鄙。將該模式進行抽象可以得出如下通用式子,其中K 表示1到L-1 層的run數(shù)量， Z 表示L層的run數(shù)量.
- K = 1 and Z = 1 give leveling.
- K = T ? 1 and Z = T ? 1 give tiering.
- K = T ? 1 and Z = 1 give Lazy Leveling
通過該式子盡心建脑惭悖可以得出如下的復(fù)雜度分析
具體哪一層如何選擇K和Z 則需要根據(jù)具體的負(fù)載進行計算權(quán)衡傍妒。
總結(jié)
在所有的領(lǐng)域都不可能存在完美的方案，每一個方案都是對不同功能點之間的取舍摸柄。功能點之間的關(guān)聯(lián)幾乎都可以抽象成類似存儲CAP的選擇颤练。本文的核心在于根據(jù)實際建模分析，在不同功能點之間抽象出通用模型驱负，并根據(jù)負(fù)載特征對模型進行迭代選擇最優(yōu)的參數(shù)解嗦玖。
