最近閱讀了Lanyue Lu等作者于2016年Fast上發(fā)表的《WiscKey: Separating Keys from Values in SSD-Conscious Storage》啄骇。在這里我將文章中的各個章節(jié)的各個內(nèi)容進(jìn)行一些簡略的總結(jié)脆粥。

image.png

paper原文的話大家可以百度or谷歌title瓦侮，然后點開就能下載涵卵。

文章架構(gòu)

在開始分析文章前，我先將目錄架構(gòu)給讀者交代一下击困。

- 一涎劈、摘要

- 二广凸、簡介

- 三、背景以及寫作目的

1 LSM介紹
2 LevelDB介紹
3 讀寫放大介紹
4 快速存儲的硬件介紹

- 四蛛枚、WiscKey

1 設(shè)計思路
2 鍵值對分離
3 設(shè)計挑戰(zhàn)（包括并行查找難度谅海、垃圾回收挑戰(zhàn)、碰撞一致性挑戰(zhàn)）

- 五蹦浦、性能優(yōu)化

1 value日志寫區(qū)塊

2 LSM日志的性能提升

- 六扭吁、評估

1 微性能評估（包括數(shù)據(jù)加載性能、查詢性能盲镶、垃圾回收性能侥袜、碰撞一致性性能、空間放大評估徒河、CPU使用情況）

2 YCSB測評

- 七系馆、相關(guān)工作

- 八、結(jié)論

文章解讀

由于我的水平有限顽照，所以在對文章的理解上或許有些偏差，有不同看法的讀者可以相互交流闽寡。

一代兵、 摘要

摘要交代了wisckey是基于LSM-tree的鍵值對的設(shè)計思想，并將LSM中的建值分離爷狈，并綜合利用了不同硬件設(shè)備的連續(xù)植影、隨機(jī)讀寫特性。最后交代了Wisckey在綜合測試中的優(yōu)勢涎永。

二思币、文章簡要介紹

[x]表示第x段講述了什么什么。

這里[1]首先交代了鍵值對的存儲系統(tǒng)在當(dāng)前生產(chǎn)生活的重要性羡微。之后交代了[2]LSM-tree在“寫”數(shù)據(jù)上的連續(xù)性優(yōu)勢谷饿。（與B樹進(jìn)行比較）

image.png

[3]下一段很明顯的交代了LSM-tree是如何在“寫”操作上具有高性能的。包括連續(xù)寫妈倔、在后臺進(jìn)行排序等博投，以及IO放大問題。

[4]下面交代了HDD（機(jī)械硬盤）對LSM-tree的影響盯蝴。

image.png

于是最好使用連續(xù)讀與寫來操作數(shù)據(jù)毅哗。

[5]第五段講述了三點SSD與HDD的不同。下面我們詳細(xì)說明下捧挺。

①首先是對于SSD來說虑绵，隨機(jī)讀與順序讀的差別沒有那么大。因此LSM-tree會在寫操作的時候就進(jìn)行了大量的IO操作以減少讀的時候的IO操作闽烙。

image.png

②SSD內(nèi)部有高度并行機(jī)制翅睛。所以我們設(shè)計的LSM需要能夠適應(yīng)SSD的機(jī)制。

image.png

③SSD會因為重復(fù)寫而導(dǎo)致?lián)p害。所以LSM中的高寫入會影響SSD的壽命宏所。

image.png

[6]wisckey降低了寫放大酥艳，減少了LSM的大小并且在查詢數(shù)據(jù)的時候能更好的利用cach。

[7]簡單交代了一些key-value分離后的弊端爬骤。

三充石、技術(shù)背景以及設(shè)計動機(jī)

1 LSM介紹

LSM為順序?qū)懀员菳樹要快霞玄。具體的LSM樹我會在其他文章中單獨寫出來骤铃。

最后，文章比較了LSM與B樹坷剧，并交代了LSM多用于寫>讀的系統(tǒng)中惰爬。

image.png

2 LevelDB介紹

在這里文章講述了LevelDB的核心設(shè)計。其包括一個磁盤日志文件惫企、兩個內(nèi)存表撕瞧、七個level0~level6的磁盤存儲表。在后臺狞尔，這些寫入的數(shù)據(jù)都會自行排序丛版。然后從memtable -> immutable memtable -> level0~level6。最后講述了一些合并上的細(xì)節(jié)偏序。

3 讀寫放大介紹

[1]首段講述了讀寫放大問題是LSM中最主要的問題页畦。

LSM-Tree 能將離散的隨機(jī)寫請求都轉(zhuǎn)換成批量的順序?qū)懻埱螅源颂岣邔懶阅堋?/p>

• 讀放大（Read Amplification）研儒。LSM-Tree 的讀操作需要從新到舊（從上到下）一層一層查找豫缨，直到找到想要的數(shù)據(jù)。這個過程可能需要不止一次 I/O端朵。特別是 range query 的情況好芭，影響很明顯。

• 空間放大（Space Amplification）逸月。因為所有的寫入都是順序?qū)懀╝ppend-only）的栓撞，不是 in-place update ，所以過期數(shù)據(jù)不會馬上被清理掉碗硬。
  RocksDB 和 LevelDB 通過后臺的 compaction 來減少讀放大（減少 SST 文件數(shù)量）和空間放大（清理過期數(shù)據(jù)）瓤湘，但也因此帶來了寫放大（Write Amplification）的問題。

• 寫放大恩尾。實際寫入磁盤的數(shù)據(jù)大小和程序要求寫入數(shù)據(jù)大小之比弛说。正常情況下，HDD/SSD 觀察到的寫入數(shù)據(jù)多于上層程序?qū)懭氲臄?shù)據(jù)翰意。原因是在compact的過程中木人，我需要額外的進(jìn)行寫操作以便能夠?qū)?shù)據(jù)從一個level寫入到另一個level信柿，所以這個過程就增加了寫入量。

而這里我們放上我引入的一段對HHD和SSD的讀寫放大說明醒第。

9B2FCB5C-A5D1-4C8A-86D2-15B7505F42D3.png

[2]寫放大在兩個level之間能夠達(dá)到10以上渔嚷。又因為這里有7個level，所以從level1~level6可能會使寫放大達(dá)到50 稠曼。

Since the size limit of Li is 10 times that of Li?1, when merg- ing a file from Li?1 to Li during compaction, LevelDB may read up to 10 files from Li in the worst case, and write back these files to Li after sorting.

[3]這一段講述了讀放大的問題與原因形病。第一個原因就是在LevelDB中進(jìn)行查找操作時需要查找很多個文件。

image.png

第二個原因是在SSTable中查找需要讀取大量的元數(shù)據(jù)霞幅。

image.png

[4]這里作者進(jìn)行了一個實驗漠吻，使用16b的鍵，1kb值分別在1G與100G的系統(tǒng)中做操作司恳。結(jié)果如下圖途乃。

image.png

寫放大的原因是：當(dāng)寫入的數(shù)據(jù)越多，系統(tǒng)在從低level到高level的過程中的compact過程中需要寫更多次扔傅。

讀放大的原因：當(dāng)database越小耍共，索引塊和布隆過濾器可以很好的放入到cach中，當(dāng)變大的時候猎塞，那么就需要不斷的將這些塊放入到cach中划提，消耗了替換的過程。

image.png

4 快速存儲硬件介紹

[1]在SSD中初始隨機(jī)寫的效率還算正常邢享，不過當(dāng)寫入的次數(shù)增加后，效率就會隨之而來降低的很快了淡诗。所以對于SSD來說骇塘，使用LSM能多次進(jìn)行順序?qū)憦亩欣赟SD。

[2]在某些情況下韩容，SSD中的隨機(jī)讀的效率與順序讀幾乎一致款违。

image.png

最后的結(jié)論是，在讀取數(shù)據(jù)量達(dá)到16kb以上的時候群凶，32線程的隨機(jī)讀吞吐量==順序讀插爹。

image.png

四、Wisckey的詳細(xì)介紹

開篇提出LSM更適合于傳統(tǒng)的硬盤请梢，然而對于SSD它并不適合赠尾。之后第二段提出了四個核心觀點：鍵值對分離、使用SSD的并行特性進(jìn)行隨機(jī)查詢毅弧、使用碰撞一致性已經(jīng)垃圾回收機(jī)制去管理log气嫁、移除LSM日志文件。

image.png

1 設(shè)計目標(biāo)

[1]Wisckey可以被部署為關(guān)系型數(shù)據(jù)庫和鍵值對類型數(shù)據(jù)庫够坐。之后又從五點分別介紹Wisckey的設(shè)計目標(biāo)寸宵。

2 鍵值對分離

[1]講述了LSM中最大的性能限制就是compact過程崖面。它會持續(xù)的對文件進(jìn)行后臺排序（需要進(jìn)行大量的IO操作），不過這個過程會對查詢有幫助梯影。

[2]第二段講述了設(shè)計中比較核心的一點巫员，就是只在LSM中存儲key，而value存儲在其他位置甲棍。又因為現(xiàn)在的鍵值對特征就是鍵很小简识，值很大所以這種設(shè)計思路有助于減小寫放大。

image.png

[3]交代了wisckey由于采用了鍵值存儲位分離救军，所以它在lookup的過程中會查詢更少的levelx财异，且更容易放入cach中，所以會更為迅速唱遭。

[4]解釋了Wisckey的存儲模式戳寸。

image.png

[5]先插入value于vlog中，然后再將key插入LSM中拷泽。刪除的時候只刪除LSM中即可疫鹊，剩下的內(nèi)容在垃圾回收的時候刪除。

五司致、挑戰(zhàn)

這里提出了垃圾回收挑戰(zhàn)拆吆、碰撞一致性挑戰(zhàn)的解決辦法。

1 并行范圍查詢

[3]在LevelDB中脂矫，由于鍵值在一起枣耀，所以查詢可以進(jìn)行連續(xù)讀。然而在Wisckey中庭再，這里就需要隨機(jī)讀操作了捞奕。不過根據(jù)我們上面的“SSD中順序、隨機(jī)讀吞吐量比較”我們知道SSD中的并行讀取操作可以在請求量大于16kb的時候與順序讀效率接近拄轻。

不過在這里我不是特別理解這里的“prefetch（預(yù)嚷А）”是如何進(jìn)行的。

image.png

[5]這里應(yīng)該是講述了預(yù)取是如何進(jìn)行的恨搓。如果用戶進(jìn)行一個范圍查詢院促，那么系統(tǒng)會首先把LSM中的key全部找到，并依次將value的地址添加到一個隊列當(dāng)中斧抱。然后后臺就會根據(jù)隊列的值進(jìn)行多線程的查詢操作常拓。

2 垃圾回收機(jī)制

[1]LSM在做刪除操作的時候不會立即清空空間《峁茫空間只會在compact的時候清理墩邀。然而在wisckey中，我們只會清理LSM中的key盏浙，所以對于value來說眉睹，我們并不會進(jìn)行常規(guī)的空間清理操作荔茬。所以這里需要一個特殊的垃圾清除機(jī)制。

[2]交代了一種常用的很笨重的清理方法竹海。這里不做敘述严里。

[3]Wisckey目的是需要一種輕量級并且在線刪除的機(jī)制捷绑。我們在vlog中存儲value的同時也會存儲相應(yīng)的key。

image.png

[4]上圖中head是新加入值的位置，而tail是垃圾釋放空間的起始位置藤韵。兩個指針中間的存儲的包含有效值夹供。

[5]此處詳細(xì)的講述了垃圾回收機(jī)制抚官。首先從tail處讀取一個簡直對猜旬，然后同過查找LSM來檢驗這些value哪些是合法的（沒有被覆蓋或者刪除）。然后會把合法的值加入到log的head處甩卓。最后釋放空間并更新tail的位置鸠匀。

[6]為了避免在垃圾回收的時候出現(xiàn)碰撞從而使數(shù)據(jù)丟失，所以這里需要：在將value加入到vlog后逾柿，回收機(jī)制會調(diào)用fsync()函數(shù)缀棍，（后面的這些步驟就是這個函數(shù)的具體操作）然后用同步方式將這些新的value地址與當(dāng)前tail添加到LSM中（<‘‘tail’’, tail-vLog-offset>），最后釋放vlog中的空間机错。

不過這里我一直對這個crash有些疑問爬范，我們提前將tail和value的地址加入LSM是如何避免數(shù)據(jù)丟失的呢？弱匪？

3 碰撞一致性

其實我在這里不是特別清楚這個碰撞的具體含義青瀑，需要更加清晰一下

[1]給出了一個結(jié)論是，如果一個X值在碰撞中丟失萧诫，那么它后面的值同樣也會丟失狱窘。

[2]碰撞發(fā)送后，Wisckey需要驗證是否value的地址在vlog的有效區(qū)域內(nèi)财搁，然后驗證是否key與value對應(yīng)。如果驗證失敗躬络，那么可以肯定數(shù)據(jù)在碰撞中存在丟失尖奔，然后從LSM中刪除這個key并對用戶進(jìn)行通知。

在vlog中穷当，每個新加入的value都有其對應(yīng)的key的位置提茁，所以上述驗證過程十分容易。

六馁菜、性能最優(yōu)化

感覺這一部分偏重于解釋為何我們這樣設(shè)計會提升性能balabala茴扁，然后穿插講解各個部分是如何工作的。

1 vLog的寫入操作塊

[1]還是在說老事情汪疮，就是對于Wisckey來說峭火，寫小內(nèi)容的操作增多會導(dǎo)致overhead毁习。所以還是要想辦法解決如何避免大量寫入小規(guī)模數(shù)據(jù)的問題。

[2]為了減少overhead的問題卖丸，wisckey采用了一個新的機(jī)制纺且。這里是我個人的理解。

我們在上面提出了稍浆，大量的小規(guī)模value寫入會導(dǎo)致大量的write()函數(shù)調(diào)用载碌。這也會導(dǎo)致插入密集性工作降低系統(tǒng)的效率。所以為了減少write()函數(shù)的調(diào)用衅枫，我們可以在用戶的空間中開辟一片區(qū)域嫁艇，然后將大量數(shù)據(jù)提前寫入到此處，并以此來減少write()的調(diào)用弦撩。

對于讀操作步咪，系統(tǒng)會首先查找這片區(qū)域，這里找不到則再去找vlog孤钦。（不過此處還補(bǔ)充到這種機(jī)制可能會提高crash的幾率歧斟，導(dǎo)致數(shù)據(jù)丟失，這沒辦法了有利有弊emmm）

2 LSM-tree日志文件的性能提升

[1]這里又重申了vlog里面存key的事實偏形。

[2]此處講述了如果在存入vlog后但是還沒來得及存入LSM時發(fā)生了碰撞静袖，需要如何恢復(fù)。傳統(tǒng)方法就是便利所有俊扭，但是很花時間队橙。所以這里在LSM中定期記錄了vLog的head地址<‘‘head’’, head-vLog-offset>。每次恢復(fù)都從記錄處開始萨惑，并按照插入順序進(jìn)行恢復(fù)（以vlog為參照恢復(fù)LSM）捐康。所以這就是為什么我們可以放棄LSM的log。

七庸蔼、實驗部署環(huán)境

講述了Wisckey是基于什么而搭建的解总。

然而這里講述了在垃圾回收機(jī)制運(yùn)行的過程中使用了hole機(jī)制。

這里需要更多的研究姐仅。

image.png

八花枫、性能測試

所有的實驗都是在two Intel(R) Xeon(R) CPU E5-2667 v2 @ 3.30GHz pro- cessors and 64-GB of memory上進(jìn)行的。操作系統(tǒng)是64-bit Linux 3.14掏膏。存儲設(shè)備是500-GB Samsung 840 EVO SSD劳翰，達(dá)到了500 MB/s的順序讀以及400 MB/s的順序?qū)懰俣取?/p>

下面的性能測試均沒有使用壓縮算法。

1 寫入性能

[2]這里對LevelDB和wisckey分別進(jìn)行測試馒疹，并發(fā)現(xiàn)吞吐量會隨著value不斷增加而增加。但是wisckey的上限遠(yuǎn)遠(yuǎn)大于levelDB颖变。

image.png

而后對其原因進(jìn)行了分析生均，得出在LevelDB中听想，時間花費(fèi)在三個方面：①將數(shù)據(jù)寫入log文件、②將數(shù)據(jù)寫入memtable疯特、③等待memtable刷新

image.png

而當(dāng)key-value的規(guī)模比較小時哗魂，會花費(fèi)更多時間。下面是相關(guān)測試漓雅。

image.png

而對于較大的鍵值對來說录别，寫入和排序過程更為迅速。

[3]這里對隨機(jī)寫入進(jìn)行了測試邻吞。

image.png

這里我們能很明顯的看到LevelDB有很低的吞吐量组题，因為帶寬在compact過程中消耗巨大。

而后又介紹了隨機(jī)寫當(dāng)中的寫放大測試抱冷。Wisckey的寫放大在1k之后就降到了1左右崔列，原因是其LSM-tree比LevelDB中的要小的多。

image.png

2 查詢效率

[1]雖然在Wisckey中查詢時需要先查詢LSM再去獲取value的地址旺遮，但是它仍然比LevelDB的效率要高赵讯。其原因歸結(jié)于LSM-tree小、compact操作過程中處理的數(shù)據(jù)小耿眉，也就意味著后臺的讀寫規(guī)模都要小边翼。

image.png

[2]之后對不同系統(tǒng)的隨機(jī)和順序讀寫進(jìn)行了測試工作。

由圖可知在4K前鸣剪，所有的類別均呈現(xiàn)上升趨勢组底。然而對于大于4K的情況，wisckey由于其本身特性所以會大于levelDB筐骇，而在4K以下卻相反债鸡。（這里在前文的對SSD測試的部分中有所介紹）

image.png

[3]此段落交代了在64B處，wisckey-seq要比leveldb-seq慢百分之25的原因铛纬。wisckey需要從key和value兩處進(jìn)行查詢才能獲取到內(nèi)容厌均，所以當(dāng)vlaue變小的時候，這種活動就變的更多了告唆，所以就更占用貸款莫秆。所以還是value較大會更對wisckey更為友好。

3 垃圾回收

[1]垃圾回收測試分三步：

• 使用隨機(jī)寫的方式建立數(shù)據(jù)庫悔详。
• 刪除一部分比例的鍵值對。
• 運(yùn)行系統(tǒng)并進(jìn)行測試惹挟。

[2]如果垃圾回收中的數(shù)據(jù)全部都是丟失的茄螃，那么只會影響百分之十。因為如果全部都不合法连锯，那么數(shù)據(jù)就沒有必要寫入了归苍。

image.png

4 碰撞一致性

是個狠人用狱。

5 空間放大

[1]交代了放大的概念。

[3]WiscKey比WiscKey-GC大的原因就是因為前者沒有進(jìn)行垃圾回收拼弃，所以占用的空間大（包括了多余的value和元數(shù)據(jù)）夏伊。

image.png

[4]交代了一個世界難題。LevelDB中排序和垃圾回收在compact中進(jìn)行了吻氧，所以用寫放大來減小空間放大溺忧。而Wisckey用空間換取時間，減少IO操作盯孙。

image.png

而后面就是一些標(biāo)準(zhǔn)的測試工作鲁森。本文重點講解架構(gòu)已經(jīng)設(shè)計思路，所以這部分就不寫了吧振惰。

這個文章真的是寫了好久好久歌溉，邊理解邊分析。第一篇文章到此結(jié)束骑晶，后期會有更多相關(guān)的文章分析的痛垛。歡迎讀者們指正！