FAST'20

Teng Zhang, Alibaba Group, Alibaba-Zhejiang University Joint Institute of Frontier Technologies, Zhejiang University; Jianying Wang, Xuntao Cheng, and Hao Xu, Alibaba Group; Nanlong Yu, Alibaba-Zhejiang University Joint Institute of Frontier Technologies, Zhejiang University; Gui Huang, Tieying Zhang, Dengcheng He, Feifei Li, and Wei Cao, Alibaba Group; Zhongdong Huang and Jianling Sun, Alibaba-Zhejiang University Joint Institute of Frontier Technologies, Zhejiang University

FAST最后一篇關(guān)于KV的文章，這是阿里與浙大的一個聯(lián)合實驗室做的通過FPGA優(yōu)化LSM-Tree的compaction開銷的一篇文章，主要是說現(xiàn)在存儲設(shè)備的I/O性能越來越好，這就導(dǎo)致系統(tǒng)性能的瓶頸從IO轉(zhuǎn)移到CPU上，LSM-Tree需要進行耗費大量CPU資源的compaction操作，并且在KV較小的時候CPU開銷更大，與前臺操作競爭CPU資源，從而影響前臺的性能。為了解決這一問題，本文提出通過FPGA這一專用硬件，將compaction操作offload到FPGA上進行，以此來減少compaction爭用前臺操作的CPU資源而帶來的性能問題。

本文的CPU成為瓶頸的背景問題在KVell中也有提到，KVell的做法是干掉了LSM-Tree的結(jié)構(gòu)，換成了內(nèi)存索引+單層存儲的結(jié)構(gòu)。

背景

• 前臺的查詢與事務(wù)操作與后臺的compaction操作之間存在資源爭用，compaction消耗較多的CPU與IO資源，尤其是在讀寫混合的workload下，這種爭用更加明顯。

Compaction thread于throughput的關(guān)系

從上圖可以看到，compaction線程數(shù)在32左右，系統(tǒng)throughput達(dá)到最高，再繼續(xù)增加線程數(shù)反而會使throughput降低，此時compaction線程占用了較高的IO和CPU資源。

因此本文提出通過將compaction移到別的地方做，來緩解CPU資源的壓力

Motivation

當(dāng)前的LSM-Tree based KV store在讀寫混合workload下性能下降的原因：

1. 分散的L0

由于L0的table是直接從memtable dump下來的，所以table之間存在key range的重疊，查找L0需要查找所有的table，當(dāng)compaction較慢的時候，L0的table堆積，使得查找L0耗時更多，而L0又是最新的數(shù)據(jù)，往往熱度較高，因此對讀寫混合workload來說，無疑會影響性能。

2. 瓶頸的轉(zhuǎn)移

compaction操作主要流程為：decode，merge，encode，本文測試了三個階段的開銷：

compaction 開銷的breakdown

從圖中可以看出，當(dāng)KV size較小的時候，消耗CPU資源更多，而當(dāng)KV size超過128B之后，主要的開銷在IO上，即當(dāng)compaction小KV的時候，性能受CPU限制。

設(shè)計實現(xiàn)

本文的實現(xiàn)是集成到阿里另一篇文章提出的一個KV系統(tǒng)——X-engine中的，這篇文章后面再詳細(xì)看看，根據(jù)簡單的描述來看，X-engine也是一個類似LevelDB的LSM-Tree結(jié)構(gòu)，但是在實現(xiàn)上做了一定的優(yōu)化。

本文為了實現(xiàn)FPGA compaction，設(shè)計了幾個主要的部件，分別是Task Queue，Result Queue，Driver和Compaction Unit。其中Task Queue是接受待處理的compaction任務(wù)，Result Queue是接受處理完的comapction結(jié)果。

overall structure

Driver

Driver的主要任務(wù)是構(gòu)建compaction任務(wù)，分發(fā)任務(wù)以及應(yīng)用compaction結(jié)果，分別對應(yīng)三個線程：builder thread，dispatcher thread以及driver thread。

三種線程的協(xié)同工作

builder thread將compaction任務(wù)切分成大小相近的塊，并分別構(gòu)成Compaction task，這是FPGA處理的基本單位，compaction task中包含了compaction的input數(shù)據(jù)。同時builder thread還負(fù)責(zé)檢查result queue中任務(wù)是否完成，如果完成則將新的數(shù)據(jù)install到DB。這也是需要CPU的地方。

Compaction Task的結(jié)構(gòu)

dispatcher thread將task queue中的task分發(fā)到不同的Compaction Unit進行執(zhí)行，分發(fā)的方式是以round-robin的方式進行的。

driver thread是將輸入數(shù)據(jù)傳輸?shù)紽PGA的memory中，并觸發(fā)開始執(zhí)行。

為了將數(shù)據(jù)傳輸?shù)紽PGA，需要使用到PCIe connect，本文定義了兩種數(shù)據(jù)路徑，一個是指令路徑（Instruction Path），主要用于傳輸小的、需要經(jīng)常傳輸?shù)臄?shù)據(jù)（指令）；另一個是compaction數(shù)據(jù)路徑（Compaction Data Path），用于傳輸compaction的數(shù)據(jù)，通過DMA的方式，無CPU參加。

FPGA Driver

Compaction Unit

Compaction是FPGA上compaction操作的邏輯實現(xiàn)，主要結(jié)構(gòu)包括了Decoder、KV Buffer、Merger以及Encoder。

Compaction Unit 結(jié)構(gòu)

Decoder用于將輸入的數(shù)據(jù)進行decode操作，處理之后的數(shù)據(jù)存儲到KV Ring Buffer，Ring Buffer中數(shù)據(jù)超過一半的時候controller觸發(fā)merger開始處理數(shù)據(jù)，同時controller會控制merge處理的速度與decoder處理的速度的平衡，處理完的數(shù)據(jù)寫入output buffer并進行encode。

測試

compaction效率測試

比較對象：單線程compaction，F(xiàn)PGA-offloading compaction

測試方法：4000000KV，手動compaction

compaction性能測試

總體實現(xiàn)2-5倍的性能提升，KV較小的時候offloading開銷相對較大，因此KV越大提升越多。

KV Store性能測試

對比對象：X-Engine

測試工具：DBBench

測試方法：278G數(shù)據(jù)量，70GB cache，8B key， 32B value

對compaction的影響

線程數(shù)與throughput

0-24線程：提升線程數(shù)有效減少L0的數(shù)據(jù)量累計，加快了查找，此時compaction比write慢，增加compaction線程可以提升compaction效率

24-32線程：性能基本不變

32+線程：線程數(shù)增加性能下降，原因：1）線程數(shù)增加增加了資源的爭用；2）過多的線程消耗IO資源

添加FPGA之后的各種參數(shù)對比：除了性能提升之外，能耗也有降低。

兩種方案的各種參數(shù)

Read Ratio對性能的影響

不同read ratio下性能的影響

DBBench

測試項目：fillrandom，seekrandom while writing，read while writing，update random，read random and write random

測試結(jié)果：

DBBench性能

fillrandom提升最多，因為大量寫會觸發(fā)更多comapction

YCSB

YCSB性能對比

總來說：offloading主要還是對寫性能提升比較多