Eurosys'20

Eran Gilad Yahoo Research, Israel Edward Bortnikov Yahoo Research, Israel Anastasia Braginsky Yahoo Research, Israel Yonatan Gottesman Yahoo Research, Israel Eshcar Hillel Yahoo Research, Israel Idit Keidar Technion and Yahoo Research, Israel Nurit Moscovici?Outbrain, Israel Rana Shahout?Technion, Israel

本文是雅虎研究發(fā)表在Eurosys 2020上的文章，主要針對KV應(yīng)用場景中的Spatial Locality的負(fù)載特征，設(shè)計(jì)了一個新的KV Store?，F(xiàn)在的KV Store作為底層存儲引擎，通常Key是多個屬性組合起來的值，某些主屬性的熱點(diǎn)訪問會導(dǎo)致KV Store中某個key range的數(shù)據(jù)成為訪問熱點(diǎn)，也就是所說的Spatial Locality。這個問題在FAST 2020上的RocksDB workload分析的文章中也有提到。本文針對這個Spatial locality特征，提出LSM-Tree不適用于這種場景，然后重新設(shè)計(jì)了一個新的結(jié)構(gòu)并實(shí)現(xiàn)了EvenDB。

背景

Spatial locality

KV Store常作為應(yīng)用或者其他存儲系統(tǒng)的底層存儲引擎，上層應(yīng)用的數(shù)據(jù)在被轉(zhuǎn)換成KV格式的時候，key往往會由多個屬性組成，所以多個key也可能會有相同的前綴，比如一個表的數(shù)據(jù)，在存儲到KV之后可能table-id就會作為key的一個前綴，這個表的所有數(shù)據(jù)前綴都相同。這樣的影響是上層應(yīng)用出現(xiàn)訪問熱點(diǎn)的時候，底層KV store可能熱點(diǎn)會集中在某個key range內(nèi)，也就是spatial locality。而數(shù)據(jù)熱點(diǎn)現(xiàn)象在KV workload中也很常見，下圖是本文做的一個統(tǒng)計(jì)，統(tǒng)計(jì)的是一個移動app數(shù)據(jù)分析平臺的trace，橫軸是app id，可以看到大約1%的app占了約94%的數(shù)據(jù)訪問。

spatial locality

LSM-Tree的不適應(yīng)

對于這種擁有spatial locality的workload，本文認(rèn)為現(xiàn)在最常使用的LSM-Tree結(jié)構(gòu)不再適用，主要的理由有三點(diǎn)：

• LSM-Tree中主要按照時間順序組織數(shù)據(jù)，會導(dǎo)致同一個key range的數(shù)據(jù)分散到不同的SST內(nèi)；
• LSM-Tree的compaction會消耗大量的帶寬并產(chǎn)生讀寫放大；
  • 寫放大縮短SSD這類存儲設(shè)備的壽命；
  • compaction會將冷數(shù)據(jù)不斷地進(jìn)行讀寫；
• 熱數(shù)據(jù)會被flush到盤上，降低了數(shù)據(jù)訪問效率。

EvenDB設(shè)計(jì)

EvenDB的設(shè)計(jì)核心思想是對于前綴相同的數(shù)據(jù)以chunk為單位進(jìn)行組織，并以chunk為單位進(jìn)行緩存或者寫盤。

Design Goal

• 針對spatial locality優(yōu)化；
• 減小寫放大；
• 針對熱點(diǎn)數(shù)據(jù)可以完全存儲到內(nèi)存的應(yīng)用場景；
• 支持快速恢復(fù)。

結(jié)構(gòu)

overall structure

EvenDB的組織數(shù)據(jù)的基本單位是chunk，當(dāng)chunk被寫入磁盤的時候成為一個funk（file chunk），被緩存在內(nèi)存中的時候?yàn)橐粋€munk（memory chunk），chunk以鏈表形式組織并通過index將key映射到對應(yīng)的chunk，每個chunk代表一個key range。

Funk

funk是chunk在磁盤上的存儲形式，由一個SSTable文件和一個log組成，新數(shù)據(jù)追加到log中并通過compaction合并到SST中。當(dāng)log大小達(dá)到閾值之后，觸發(fā)rebalance進(jìn)行合并。由于log中查找數(shù)據(jù)是順序查找，比較慢，所以每個funk有一個bloom filter用來減少不必要的log查找。

Munk

munk是chunk緩存到內(nèi)存中的形式，數(shù)據(jù)通過一個數(shù)組鏈表來組織，數(shù)據(jù)首先根據(jù)前綴劃分到各個數(shù)組中，前綴按照大小排序，然后同一個數(shù)組下標(biāo)下的數(shù)據(jù)通過鏈表組織。新數(shù)據(jù)插入的時候先追加到log中，然后就追加到對應(yīng)前綴的鏈表里面。查找的時候，首先在數(shù)組中進(jìn)行二分查找，然后再在鏈表中順序查找。

Reorganization

• munk rebalance：對munk數(shù)據(jù)進(jìn)行組織；
• funk rebalance：頻率較低（因?yàn)閒unk都是冷數(shù)據(jù)）；
• split：創(chuàng)建新的chunk。

加速磁盤訪問

對于沒有被cache的chunk的訪問，本文提出兩點(diǎn)優(yōu)化措施：

• 緩存單個KV的row cache

當(dāng)某些chunk只有少量KV是訪問熱點(diǎn)，緩存整個chunk就沒必要了，所以EvenDB也設(shè)計(jì)了一個KV為單位的row cache來緩存單個kv（rocksdb里面也有）。

• bloom filter減少log訪問

Concurrency and atomic scan

EvenDB支持原子的scan操作，并發(fā)控制通過一個簡化的multi-version實(shí)現(xiàn)。get操作不需要鎖和等待，put操作需要等待rebalance操作，scan可能需要等待put操作。

EvenDB中有一個全局的version number，被稱為Global Version。這個version是針對scan的并發(fā)控制，put操作不需要修改。

對于scan，在執(zhí)行scan之前需要創(chuàng)建一個snapshot，此時會訪問global version并將其增加1。put操作將不允許修改version小于global version的KV數(shù)據(jù)。

對于舊版本的管理，EvenDB通過一個Pending Operation Array來記錄每個活躍中的線程。當(dāng)Array中的version不再被訪問的時候就表明對應(yīng)的舊版本數(shù)據(jù)可以被刪除了。

對于不同操作的同步，put于scan之間可能存在的競爭通過Pending Operation Array處理，put與rebalance的競爭通過rebalance lock來處理。

基本操作

EvenDB中所有的操作之前都需要先定位key所在的chunk，這個操作通過內(nèi)存中的index來進(jìn)行。

put

1. 通過index定位chunk；
2. 獲取rebalance lock；
3. 獲取global version，將要修改的key在po中注冊；
4. 寫數(shù)據(jù)到log，如果有munk則更新munk；
5. 如果key在row cache中，則同時更新row cache（row cache不服務(wù)scan，所以只保存最新的數(shù)據(jù)）；
6. 從po中注銷key并釋放rebalance lock。

對于同一個GV下針對同一個key的多次更新，EvenDB給每個chunk設(shè)置了一個counter，這樣就能通過<GV,counter>對來對每個put操作進(jìn)行排序。

scan

1. 獲取global version并將其加1；
2. 在PO中注冊scan的key range和GV；
3. 等待小于GV的put操作的完成；
4. 讀數(shù)據(jù)；
5. 注銷；

Rebalance

Rebalance可以移除無效數(shù)據(jù)并提升數(shù)據(jù)有序性，當(dāng)munk數(shù)據(jù)超過一定的閾值之后則觸發(fā)Rebalance，Rebalance是在一個新的地方創(chuàng)建，過程中不會動原來的數(shù)據(jù)，避免影響并發(fā)操作。Rebalance操作需要獲取鎖避免與put的競爭，但是不會影響get和scan。

Funk的rebalance會創(chuàng)建新的sst和log。如果funk有對應(yīng)的munk，則只對munk進(jìn)行rebalance，然后再將munk flush成SST即可。

Split

如果munk的數(shù)據(jù)在rebalance的時候數(shù)據(jù)量超過閾值則進(jìn)行split，此時當(dāng)前chunk會被拆分成兩個chunk。

split分成兩個階段進(jìn)行：

階段1:此階段獲取rebalance lock，不允許put

1. 拆分munk；
2. 創(chuàng)建兩個新的chunk并分別引用兩個munk，但是共享同一個funk；
3. 將新的chunk插入chunk list（此時已經(jīng)可以訪問，可以通過舊的chunk訪問到新的chunk）；
4. 更新index。

階段2：拆分funk，此階段釋放鎖，put通過新的munk進(jìn)行服務(wù)。