近年來，以LevelDB和Rocksdb為代表的LSM（Log-Structured Merge-Tree）存儲(chǔ)引擎憑借其優(yōu)異的寫性能及不俗的讀性能成為眾多分布式組件的存儲(chǔ)基石，包括我們近兩年開發(fā)的類Redis大容量存儲(chǔ)Pika和分布式KV存儲(chǔ)Zeppelin，在享受LSM的高效的同時(shí)也開始逐漸體會(huì)到它的不足，比如它在大Value場(chǎng)景下的差強(qiáng)人意以及對(duì)磁盤的反復(fù)擦寫。正如之前的博客庖丁解LevelDB之概覽中已經(jīng)介紹了的LevelDB的設(shè)計(jì)思路，其最大的優(yōu)勢(shì)便是將磁盤的隨機(jī)寫轉(zhuǎn)化為順序?qū)?，但隨著在系統(tǒng)中越來越多的使用SSD，這種設(shè)計(jì)是否仍然能帶來如此大的收益，在SSD統(tǒng)治的世界里是否有更合理的存儲(chǔ)結(jié)構(gòu)。

2016年，F(xiàn)AST會(huì)議發(fā)表了論文WiscKey: Separating Keys from Valuesin SSD-conscious Storage，闡述了一種對(duì)SSD更友好的基于LSM的引擎設(shè)計(jì)方案。

問題

大家知道，LSM Tree是一種對(duì)寫優(yōu)化的系統(tǒng)，將隨機(jī)寫轉(zhuǎn)化為順序?qū)懀瑥亩@得非常優(yōu)秀的寫性能，但一定的LSM也損失了一些東西作為交換，這個(gè)損失就是寫放大，即實(shí)際的磁盤寫跟用戶請(qǐng)求寫的比值，就是說：

LSM Tree 將隨機(jī)寫轉(zhuǎn)化為順序?qū)?，而作為代價(jià)帶來了大量的重復(fù)寫入

那么這種交換是否值得呢，先來看損失，以LevelDB為例，在最壞的情況下：

• 寫放大：10 * Level（Level N-1向Level N的Compact可能涉及多達(dá)10個(gè)Level N-1層文件）

也就是說，這個(gè)寫放大的系數(shù)大概在幾十到幾百之間。那么收獲的呢，通過下表中針對(duì)不同存儲(chǔ)介質(zhì)的寫入測(cè)試數(shù)據(jù)，可以看出在傳統(tǒng)的機(jī)械盤上順序?qū)懙男阅苓h(yuǎn)遠(yuǎn)好于其隨機(jī)寫性能，這個(gè)性能差異接近一千倍。用數(shù)十倍的磁盤帶寬損失換取近千倍的性能提升，在寫入敏感的場(chǎng)景下這種交換的效果毋庸置疑。但不同的是，SSD盤相對(duì)具有較高的隨機(jī)寫能力，與順序?qū)懙牟罹啾旧碇挥惺蹲笥?，并且還可以通過并行IO進(jìn)一步提升，因此這種交換就顯得有些得不償失。同時(shí)，由于反復(fù)的寫入會(huì)帶來SSD的磨損從而降低壽命。

磁盤IO性能

思路

回顧上面的問題，當(dāng)LSM中數(shù)據(jù)的長(zhǎng)度很大時(shí)，這個(gè)問題變得尤為突出，這是因?yàn)椋?/p>

• 數(shù)據(jù)長(zhǎng)度越大，越容易觸發(fā)Compaction，從而造成寫放大；
• 如果把上層文件看做下層文件的cache，大數(shù)據(jù)長(zhǎng)度會(huì)造成這個(gè)cache能cache的數(shù)據(jù)個(gè)數(shù)變少，從而讀請(qǐng)求更大概率的需要訪問下層數(shù)據(jù)，從而造成讀放大；
• 每條數(shù)據(jù)每次Merge需要更多的寫入量

進(jìn)一步分析，LSM需要的其實(shí)是key的有序，而跟value無(wú)關(guān)。所以自然而然的思路是：

Key Value 分離存儲(chǔ)

僅將Key值存儲(chǔ)在LSM中，而將Value區(qū)分存儲(chǔ)在Log中，數(shù)據(jù)訪問就變成了：

• 修改：先append到vLog末尾，再將Key，Value地址插入LSM
• 刪除：直接從LSM中刪除，無(wú)效Value交給之后的垃圾回收
• 查詢：LSM中獲得地址，vLog中讀取

這樣帶來顯而易見的好處：

• 避免了歸并時(shí)無(wú)效的value而移動(dòng)，從而極大的降低了讀寫放大
• 顯著減少了LSM的大小，以獲得更好的cache效果

挑戰(zhàn)

這種思路是否可行呢，分析可知，Key Value分開存儲(chǔ)會(huì)導(dǎo)致以下三種問題，如果能解決或者容忍，那么這種設(shè)計(jì)就是成功的。

1，Key Value分離帶來的Range操作的低效

由于Key Value的分離，Range操作從順序讀變成了順序度加多次隨機(jī)讀，從而變得低效。利用SSD并行IO的能力，可以將這種損失盡量抵消，這正是得益于SSD較強(qiáng)的隨機(jī)訪問性能。

2，被用戶刪除或者過期版本的Value的空間回收

Compaction過程需要被刪除的數(shù)據(jù)由于只是刪除了Key，Value還保留在分開的Log中，這就需要異步的回收?？梢钥闯鯨SM本身的Compaction其實(shí)也是垃圾回收的思路，所以通過良好設(shè)計(jì)的Value回收方式其實(shí)并不會(huì)過多的增加系統(tǒng)的額外負(fù)擔(dān)。離線回收比較簡(jiǎn)單，掃描整個(gè)LSM對(duì)Value Log進(jìn)行mark and sweep，但這相當(dāng)于給系統(tǒng)帶來了負(fù)載帶來了陡峭的波峰，WiscKey論文又提出來了巧妙的在線回收方式：

其中head的位置是新的Block插入的位置，tail是Value回收操作的開始位置，垃圾回收過程被觸發(fā)后，順序從Tail開始讀取Block，將有效的Block插入到Head。刪除空間并后移Tail?？梢钥闯?，這里的回收方式由于需要將有效的數(shù)據(jù)重新Append，其實(shí)也帶來了寫放大，這就需要很好的權(quán)衡空間放大和寫放大了，WiscKey建議系統(tǒng)根據(jù)刪除修改請(qǐng)求的多少?zèng)Q定觸發(fā)垃圾回收的時(shí)機(jī)。

3，Crash Consistency

正式由于Key，Value的分離帶來了不可避免的在程序Crash發(fā)生時(shí)不一致的情況，WiscKey需要像標(biāo)準(zhǔn)的LSM一樣提供如下保證：

• key-value的原子性：要成功都成功，要失敗都失敗
• 重啟后的順序恢復(fù)

WicsKey給出的解決方案，是在啟動(dòng)時(shí)對(duì)Key， Value進(jìn)行檢查：

• Key成功寫入，Value沒有，則從LSM中刪除Key，并返回不存在
• Key沒有成功寫入，Value寫入，返回不存在，并在后續(xù)的垃圾回收中清楚Value。

優(yōu)化

• Value-Log Write Buffer: 給vLog維護(hù)一個(gè)緩存，來將短value合并為長(zhǎng)value來提高磁盤吞吐
• Optimizing the LSM-tree Log：去掉LSM的Log，并周期性的更新Value Log的head值進(jìn)LSM。crash后的恢復(fù)僅需要從head開始遍歷所有的vLog同樣能保證上面提到的Crash Consistency

總結(jié)

通過上面的介紹，可以看出WiscKey并不是一個(gè)全方位的解決方案，其不得不面對(duì)Key Value分離帶來的不一致和處理效率的下降，這種增加的負(fù)擔(dān)會(huì)在小Value的場(chǎng)景下尤為明顯。所以WiscKey針對(duì)的僅僅是Value長(zhǎng)度遠(yuǎn)遠(yuǎn)大于Key的情況。我們的Zeppelin向上支持的S3需求很契合這樣一種場(chǎng)景，所以WiscKey也是我們未來在引擎層的一種發(fā)展方向。

最后抒情一下，WiscKey不完美，但他啟示我們?cè)谟布娴默F(xiàn)在，人們做到的還遠(yuǎn)遠(yuǎn)不夠，還有更多的潛力和寶藏等待去發(fā)掘，屬于LevelDB和RocksDB的容光可能會(huì)逐漸褪去，但人類對(duì)更好的存儲(chǔ)的追求永不停歇，而我們工程師所要做的就是追逐先行者的腳步，搭建起連接未來和現(xiàn)實(shí)的橋梁。

參考

WiscKey: Separating Keys from Valuesin SSD-conscious Storage

Datastructures for external memory

庖丁解LevelDB之概覽

Qihoo360 Zeppelin

Qihoo360 Pika