FAST'20

Zhichao Cao, University of Minnesota, Twin Cities, and Facebook; Siying Dong and Sagar Vemuri, Facebook; David H.C. Du, University of Minnesota, Twin Cities

本文主要關(guān)注真實生產(chǎn)環(huán)境下的RocksDB的負(fù)載特征，以及當(dāng)前常用的Benchmark——YCSB能否在測試的時候還原生產(chǎn)環(huán)境的負(fù)載特征展開。主要收集了Facebook中三個使用RocksDB作為底層存儲引擎的組件的trace數(shù)據(jù)，分別是1）UDB：用于MySQL中用來存儲社交圖數(shù)據(jù)，使用RocksDB作為底層存儲；2）ZippyDB：用于存儲分布式對象存儲的元數(shù)據(jù)的分布式KV；3）UP2X：用于存儲AI/ML數(shù)據(jù)的分布式KV。然后根據(jù)收集的數(shù)據(jù)分析到達(dá)RocksDB的各種負(fù)載特征，并與YCSB的測試結(jié)果進(jìn)行對比，得出YCSB并不能準(zhǔn)確代表生產(chǎn)環(huán)境的結(jié)論，而這其中最關(guān)鍵的因素是YCSB沒有考慮到真實負(fù)載所表現(xiàn)出的key space loaclity（我的理解是key range的局部性，即熱點key會按照key range進(jìn)行分布，而不是隨機(jī)分布在整個key空間內(nèi)）。最后根據(jù)收集到的負(fù)載特征進(jìn)行建模，自己構(gòu)建了一個benchmark，達(dá)到了更加準(zhǔn)確地還原生產(chǎn)環(huán)境負(fù)載的目的。

問題背景 & Motivation

1. 現(xiàn)有的關(guān)于真實workload的描述以及分析的工作很少，然而KV Store的性能又跟workload十分相關(guān)
2. 針對KV Store的workload的分析方法與傳統(tǒng)的存儲系統(tǒng)（諸如塊存儲系統(tǒng)或者文件系統(tǒng)）有較大區(qū)別
3. 使用benchmark測試KV Store的性能的時候，并不知道benchmark生成的workload能否代表真實的workload

三個系統(tǒng)的介紹

UDB

UDB是Facebook用來存儲社交圖數(shù)據(jù)（社交關(guān)系圖）的組件，向上提供MySQL接口，UDB上層有讀cache，read miss以及write數(shù)據(jù)都通過UDB處理，數(shù)據(jù)通過MyRocks轉(zhuǎn)換為KV并寫入RocksDB。數(shù)據(jù)主要由object和associations構(gòu)成，分別代表圖的點和邊。

UDB的RocksDB通過6個ColumnFamily來存儲不同類型的數(shù)據(jù)，分別是：

Object：存儲object數(shù)據(jù)

Assoc：存儲associations數(shù)據(jù)

Assoc_count：存儲每個object的association數(shù)

Object_2ry，Assoc_2ry：object和association的secondary index

Non-SG：存儲其他非社交圖數(shù)據(jù)相關(guān)的服務(wù)

ZippyDB

ZippyDB是一個分布式的KV Store，并通過Paxos協(xié)議保證一致性，KV數(shù)據(jù)被分為不同的shard，每個shard通過一個單獨的RocksDB實例進(jìn)行存儲。ZippyDB主要用于存儲上層的對象存儲的元數(shù)據(jù)。

UP2X

UP2X是一個分布式KV Store，在Facebook中主要被用來存儲AI/ML計算的數(shù)據(jù)集，AL/ML的數(shù)據(jù)集的特點是經(jīng)常被Update，如果先Get數(shù)據(jù)再Put則效率很低，所以UP2X主要使用RocksDB的Merge來實現(xiàn)Read-Modify-Write（Merge的實現(xiàn)就是將要修改的數(shù)據(jù)的delta數(shù)據(jù)put進(jìn)去，避免隨機(jī)讀開銷，delta數(shù)據(jù)在compaction的時候會被刪除）

主要的分析工具

• Tracing：收集RocksDB的操作，主要記錄操作類型，CF，key，value，時間戳
• Trace Replaying：通過db_bench回放trace file
• Trace Analyzing：分析workload，但是因為生產(chǎn)環(huán)境的workload涉及隱私不能公布，所以最終輸出內(nèi)容是一些描述，主要包括：1）每個CF內(nèi)KV的操作次數(shù)，操作類型；2）KV size的統(tǒng)計數(shù)據(jù)；3）KV數(shù)據(jù)熱度（Popularity？）；4）key空間的局部性；5）QPS統(tǒng)計
• Modeling and Benchmarking：對workload進(jìn)行建模

workload分析

workload常規(guī)統(tǒng)計分析

查詢操作的組成

結(jié)論：Get在UDB與ZippyDB中占比最多，UP2X最多的操作是Merge

UDB：

UDB query composition

• Get/Put/Iterator是占比最高的操作，而且主要是在Object / Assoc / Non_SG這幾個CF
• Object_2ry中Iterator為主要操作
• 沒有重復(fù)update操作的CF，如Assoc_2ry通過Single_Delete刪除數(shù)據(jù)

ZippyDB：

• 只有一個CF，Get : Put : Delete : Iterator = 78 : 13 : 6 : 3

UP2X：

• Merge : Get : Put = 92.53 : 7.46 : 0.01

KV熱點分布

結(jié)論：UDB和ZippyDB中大部分KV數(shù)據(jù)是冷數(shù)據(jù)

UDB：

KVP access CDF of UDB

上圖是UDB的Get與Put操作的KV數(shù)據(jù)訪問的CDF圖。對于Get，除了Assoc之外，其他CF的數(shù)據(jù)60%或者以上的數(shù)據(jù)都只被訪問了一次。對于Put，超過75%的數(shù)據(jù)都只被訪問一次，Put次數(shù)超過10的數(shù)據(jù)僅占不到2%，所以UDB中的KV數(shù)據(jù)大部分很少被Update。

KVP scan and scan length CDF of UDB

上圖是UDB的Iterator操作的start key統(tǒng)計以及scan length統(tǒng)計，大部分的scan起始key都只被訪問一次，沒有表現(xiàn)出局部性，而scan長度超過65%都只有1次，但也有少部分的scan長度非常長。

Unique key access

上表是統(tǒng)計的UDB在一段時間內(nèi)訪問的unique key的占比，可以看到24小時內(nèi)訪問的key最高不超過3%，而14天內(nèi)訪問的key最高不超過15%，因此對UDB來說，大部分?jǐn)?shù)據(jù)在RocksDB內(nèi)都是冷數(shù)據(jù)。

ZippyDB：

ZippyDB access

對于ZippyDB，大約80%的key只被訪問一次，1%的key被訪問超過100次，因此表現(xiàn)出較好的局部性。約73%的數(shù)據(jù)只被Put一次，訪問次數(shù)超過10次的數(shù)據(jù)僅有0.001%，因此Put的局部性較差。Iterator操作的階梯式增漲主要來源于ZippyDB的作為對象存儲元數(shù)據(jù)存儲的使用場景，當(dāng)上層訪問一個對象的時候需要對元數(shù)據(jù)做scan，那么總是會從這個對象的起始位置開始掃，這個起始key就總會被訪問。

UP2X：

UP2X access

對于UP2X，Get與Merge的訪問次數(shù)分布較廣，并且訪問次數(shù)高的數(shù)據(jù)占比比較大。

QPS

結(jié)論：UDB的部分CF表現(xiàn)出較強(qiáng)的晝夜模式，這跟社交網(wǎng)絡(luò)用戶習(xí)慣相關(guān)，ZippyDB和UP2X沒有表現(xiàn)出這樣的特征

QPS of UDB

KV size分析

結(jié)論：key size通常比較小，value size的大小與具體數(shù)據(jù)類型有關(guān)，key size的標(biāo)準(zhǔn)差較小但是value size較大， UDB平均的value size比其他兩個例子要大

Average KV size

上表是三個使用場景的平均KV size以及KV size的標(biāo)準(zhǔn)差，可以看到三種情況的平均key size都較小，并且標(biāo)準(zhǔn)差都較小，而UDB的value size較大，并且三種情況的value size的標(biāo)準(zhǔn)差都較大。

KV size CDF

上圖是三種使用情況的KV size的CDF圖

UDB：

對于key size，除了Assoc_2ry其他的CF的key size都不超過40B，而Assoc_2ry因為其作為secondary index特殊的構(gòu)成，所以會有超過50B的key存在。value size變化較大，Object這個CF主要用于存儲用戶數(shù)據(jù)，所以value size從16B到10KB都有，而像是Assoc只存儲Object的聯(lián)系，所以value就相對較小只有100-200B左右。Assoc_count只存儲Object的邊的個數(shù)，數(shù)據(jù)格式固定，所以value大小也固定20B。

ZippyDB：

大部分的key size分布于[48, 53]以及[90,91]這兩個范圍內(nèi)，這與其作為Object storage的元數(shù)據(jù)存儲工作場景有關(guān)。對于value size，其分布較為廣泛，存在較大的value，但超過90%的value都只有34B左右。

UP2X：

超過99.99%的Get的key只有9B，merge的key size有6%為9B，94%為17B，17B的key都會被compaction清理掉，所以Get只會訪問到9B的key。

Key space以及訪問模式分析

統(tǒng)計方法：對key按遞增順序編號，然后統(tǒng)計每個key的訪問次數(shù)繪制heat-map，統(tǒng)計key的訪問時間繪制time-series

結(jié)論：heat-map可以看到三種DB的訪問具有較強(qiáng)的key space locality，也就是熱數(shù)據(jù)往往聚集分布在某些key space內(nèi)。UDB的Delete/Single Delete以及UP2X的Merge的time-series表明其訪問具有時間局部性

UDB：

Heat map of UDB

上圖是UDB的Object和Assoc_count的Get操作的heat-map，其中紅線表示不同的MySQL table?？梢钥吹讲糠諱ySQL table訪問熱度較高，而部分基本沒有訪問，表現(xiàn)出較強(qiáng)的key-space locality。

Time series figure of UDB

上圖為UDB的Delete以及Assoc_2ry的SingleDelete的time-series圖，一個明顯的規(guī)律是，當(dāng)個key被刪除的時候，它臨近的key也會很快被刪除。

總結(jié)：KV數(shù)據(jù)訪問并不會隨機(jī)分布在整個key space，而是根據(jù)key-space進(jìn)行區(qū)分，部分key-space訪問熱度較高，這部分?jǐn)?shù)據(jù)占比較小，而部分基本沒有訪問。屬于同一個MySQL table的數(shù)據(jù)物理上也相鄰存儲，部分SST和block具有較高的熱度，可以考慮基于這個優(yōu)化compaction以及cache。

ZippyDB：

ZippyDB access patern

可以看到ZippyDB的訪問具有較為明顯的key-space locality

UP2X：

UP2X access pattern

UP2X的訪問也表現(xiàn)出較強(qiáng)的key-space locality，只有后半段key被訪問，而前半段key基本沒有訪問。merge的time-series表現(xiàn)出來merge每一段時間內(nèi)會集中訪問一個range內(nèi)的key。

建模以及測試

YCSB對比測試

目前YCSB是最常用的一個用于測試NoSQL數(shù)據(jù)庫性能的一個benchmark，YCSB能夠設(shè)置各種參數(shù)來生成不同的workload，但是YCSB生成的workload是否能讓下層的IO符合生產(chǎn)環(huán)境的情況是個問題，所以本文做了測試。

主要對比參數(shù)：block reads，block_cache_hits，read bytes，write_bytes

對比對象：YCSB與真實ZippyDB的trace

YCSB設(shè)置：設(shè)置workload a/b的參數(shù)盡量靠近ZippyDB（YCSB不能設(shè)置compression ratio只能用默認(rèn)設(shè)置）

測試結(jié)果：

• YCSB的block read是真實trace的7.71×
• read byte是真實trace的6.2×
• write bytes是真實trace的0.74×
• block cache hit是真實trace的0.17×

總的來說YCSB測workload相比于真實的trace會造成更大的讀放大以及更小的寫放大，同時cache命中率也更低。其中的主要原因在于忽略了真實workload的key space locality，YCSB中的熱點數(shù)據(jù)隨機(jī)分布在整個key范圍內(nèi)，訪問這些key會造成大量的block讀并且被緩存，而這些block可能僅包含較少的熱數(shù)據(jù)，cache大小有限所以降低了cache命中率。對于put，隨機(jī)的熱點分布使得數(shù)據(jù)在前幾層就被compaction掉，所以造成更小的寫放大，update的數(shù)據(jù)具有key space locality，那么新數(shù)據(jù)會不斷寫入，就數(shù)據(jù)一直往下compact直到新數(shù)據(jù)遇到舊數(shù)據(jù)才會被處理掉。

建模

• 選取key range 大小：sst大小
• 建模
  • 首先將key size，value size以及QPS套到模型里面去
  • 然后處理kv的訪問次數(shù)，訪問順序以及每個range的平均訪問次數(shù)
• 測試：

Prefix_dist：基于建模構(gòu)建的workload

Prefix_random：隨機(jī)將冷熱數(shù)據(jù)分布到各個key-range

All_random：熱數(shù)據(jù)隨機(jī)分布到整個key space

All_dist：熱數(shù)據(jù)集中放置

YCSB對比

根據(jù)實驗結(jié)果，本文對YCSB提出幾條建議：

1）增加基于key range的分布

2）增加throughput的控制

3）增加KV size分布的控制

4）增加compression ratio的設(shè)置

本文又針對UDB的Assoc workload進(jìn)行了建模并與真實workload進(jìn)行了對比：

對UDB的workload的仿真