[[408566]]

本文轉(zhuǎn)載自微信公眾號「碼農(nóng)桃花源」，作者冉小龍。轉(zhuǎn)載本文請聯(lián)系碼農(nóng)桃花源公眾號。

近期，閱讀WiscKey論文深有感觸，特寫這篇文章來闡述自己的觀點(diǎn)。

說一句廢話就是：任何軟件的發(fā)展，其實(shí)都依賴于硬件的設(shè)計(jì)和進(jìn)步，所以從這一點(diǎn)來看，LSMtree誕生于上世紀(jì)80年代，在那個(gè)年代，還是機(jī)械硬盤的時(shí)代。所以，可以看的到的是，整個(gè)LSMtree最初的構(gòu)建思想都是基于機(jī)械硬盤的設(shè)計(jì)思路，但是需求是無止境的。WiscKey自我感覺是，在LSMtree的基礎(chǔ)上，基于SSD的設(shè)計(jì)思路所做的一種優(yōu)化，基于這個(gè)思路，我們來簡單分析一下論文中所闡述的觀點(diǎn)。

先闡述幾個(gè)LSMtree的概念：

• Read amplification is the number of I/O’s required to satisfy a particular query
• Write amplification is the amount of data written to storage compared to the amount of data that the application wrote.
• Space amplification is the space required by a data structure can be inflated by fragmentation or requirements for temporary copies of the data.

讀寫放大就不說了，知道LSMtree的人基本都了解，現(xiàn)在說一下空間放大的問題。

空間放大大體上是說：存儲(chǔ)采用的數(shù)據(jù)結(jié)構(gòu)因分裂或臨時(shí)數(shù)據(jù)拷貝造成的磁盤空間占用放大。

LSMtree誕生的那一天起，并不是為了存儲(chǔ)這些大的value的情況。在這種大value的情況下LSMtree的性能會(huì)急速下降，所以，其實(shí)數(shù)據(jù)庫都有自我的一種保護(hù)機(jī)制，來限定每一行value所能夠存儲(chǔ)的最大值。下面是wisckey和LSMtree的對比，可以看到在value較大的時(shí)候，wisckey的性能要遠(yuǎn)遠(yuǎn)大于LSMtree的。

下面是隨機(jī)和排序之后，wisckey和LSMtree的對比：

其次，LSMtree都有這種compaction的操作，在做compaction的時(shí)候，對磁盤IO的壓力是比較大的。再者，LSMtree并不能很好的利用SSD的并行計(jì)算能力，這一點(diǎn)也可以理解。

但是，在當(dāng)下的存儲(chǔ)引擎中，LSMtree還是很受歡迎，從性能的角度來考量，讀寫放大哪怕是空間放大(這三者是不可并存的)我最差的情況也就放大個(gè)10-50倍左右的放大成本，但是我能在性能上帶來將近千倍的速度提升(將隨機(jī)寫轉(zhuǎn)化為順序?qū)?，所以，在性能面前，這些都是可以容忍的。

SSD與SATA的差異

• 順序IO與隨機(jī)IO
• 并行計(jì)算能力
• 大量的重讀寫會(huì)使SSD的壽命降低。

當(dāng)value較大的時(shí)候，LSMtree的表現(xiàn)

• value越大，越容易觸發(fā)compaction
• LSMtree的每一層level都可以簡單理解為其下一層的cache，value越大，cache的效果越差，每次訪問讀取到下層level的概率會(huì)增加。
• 每條數(shù)據(jù)每次merge的時(shí)候，會(huì)造成寫入的量增加。

wisckey誕生的前景

其實(shí)，我們可以仔細(xì)回想一下，在LSMtree中，我們并不需要value是有序的，只要保證key是有序的，就可以滿足我們的需求。所以，我們是否可以考慮將key繼續(xù)存儲(chǔ)在LSMtree中，而將value區(qū)分存儲(chǔ)到log文件中，然后把value的指針一起存儲(chǔ)到LSMtree中，是的，這也是wisckey的思路：分離后的模型大致如下：

此時(shí)，我訪問數(shù)據(jù)的思路是這個(gè)樣子的：

• insert：先append到value log的末尾，再將剛才append的value的地址塞到LSMtree中。
• delete：將key從LSMtree中刪除，當(dāng)compaction的時(shí)候，如果找不到對應(yīng)的key那就在垃圾回收的時(shí)候順便一起將它回收掉就OK。
• select：拿LSMtree中的key+addr直接獲取到value對應(yīng)的地方，拿出來就行。

wisckey key/value分離的優(yōu)勢

首先，key的存儲(chǔ)數(shù)據(jù)量相比原先的存儲(chǔ)模型減少的不僅僅是一個(gè)量級，所以，可以充分發(fā)揮LSMtree的特性。其次，將value分離之后，避免了compaction操作的時(shí)候無效的value移動(dòng)，從而極大的降低了讀寫放大，增加SSD的使用壽命。再者，由于key的存儲(chǔ)量級的減少，cache能起到更好的效果。

可能引發(fā)的問題

之前對range進(jìn)行操作的時(shí)候，只需要順序讀就OK，但是k/v分離之后，可能需要順序讀+多次隨機(jī)讀來達(dá)到目的，論文中提到，這個(gè)可以充分利用SSD的并行能力解決，但是能解決多少有待進(jìn)一步追蹤。

上面也提到，lsmtree中value的delete操作，是依賴于compaction的時(shí)候的GC來操作的，但是k/v分離導(dǎo)致這個(gè)回收是異步的進(jìn)行?；谶@一點(diǎn)，我們來看看wisckey的處理思路：

whiskey優(yōu)化了原有垃圾回收的做法，head指向最新的block插入的位置，tail表示回收value操作開始的那個(gè)位置，GC被觸發(fā)之后，我們從tail開始進(jìn)行掃描，將有效的block移到head的后面，把tail到head的這一段位置清空，重置tail和head標(biāo)記。不難看出，將有效的block后移這個(gè)操作，在某種程度上也帶來了寫放大，但是的確提高了效率，總之是在時(shí)間和空間這兩個(gè)點(diǎn)上進(jìn)行權(quán)衡。wisckey他會(huì)根據(jù)delete這個(gè)操作請求的多少來決定觸發(fā)GC的時(shí)機(jī)。

奔潰一致性。

由于分離操作，一旦出現(xiàn)事故，wisckey如何保證奔潰情況下的一致性問題呢?

• 對key和value的操作都是原子的，總共分為三種情況：
  • key/value都寫入成功，OK這就是我們要的效果。
  • key寫入成功，value寫入失敗，則把LSMtree中的key刪除，返回value不存在。
  • key寫入失敗，value寫入成功，返回不存在，寫入的value在后續(xù)的垃圾回收中回收掉就OK。

如果遇到宕機(jī)重啟，在恢復(fù)的過程中，它是順序恢復(fù)的。

可能存在的問題

• 假如我的value log中存儲(chǔ)的都是一些較短的value，每次都需要和磁盤交互，對磁盤的吞吐量是一種考驗(yàn)。在這里是否可以考慮添加一層緩存結(jié)構(gòu)，將多個(gè)小的value合并之后再寫。
• 待續(xù)

最后，致敬一下國外同行，關(guān)于這篇論文有一篇100頁的slides[1]和PDF[2]，非常詳盡的描述了這篇論文的思路。

參考資料

[1]WiscKey:slides: https://www.usenix.org/sites/default/files/conference/protected-files/fast16_slides_lu.pdf

[2]WiscKey:pdf: https://www.usenix.org/system/files/conference/fast16/fast16-papers-lu.pdf

作者簡介：

Apache Pulsar committer

Apache BookKeeper contributor

Apache Pulsar Go client 作者及國內(nèi)主要維護(hù)者

Apache Pulsar Go Functions 作者及國內(nèi)主要維護(hù)者

Stremnative/pulsarctl 作者及國內(nèi)主要維護(hù)者

streamnative/rop 作者及國內(nèi)主要維護(hù)者

【責(zé)任編輯：武曉燕 TEL：（010）68476606】