【摘要】

隨著微秒級(jí)NVMe存儲(chǔ)的蓬勃發(fā)展，Linux內(nèi)核存儲(chǔ)棧的開(kāi)銷(xiāo)幾乎是存儲(chǔ)訪(fǎng)問(wèn)時(shí)間的兩倍，已經(jīng)成為性能瓶頸。作者提出XRP——一個(gè)允許應(yīng)用通過(guò)在NVMe驅(qū)動(dòng)的eBPF hook運(yùn)行用戶(hù)定義的存儲(chǔ)函數(shù)(如索引查找)的框架，它可以安全地繞過(guò)內(nèi)核大部分存儲(chǔ)棧。為了保持文件系統(tǒng)的語(yǔ)義，當(dāng)用戶(hù)注冊(cè)的eBPF函數(shù)被調(diào)用時(shí)，XRP向它的NVMe驅(qū)動(dòng)hook傳遞了一小部分內(nèi)核的狀態(tài)。作者測(cè)試了兩個(gè)KV存儲(chǔ)——BPF-KV，一個(gè)簡(jiǎn)單的B+樹(shù)KV存儲(chǔ)，和WiredTiger，一個(gè)流行的LSM樹(shù)的存儲(chǔ)引擎，并證明了它們從XRP中可以獲得極大的帶寬和延遲收益。

【背景和動(dòng)機(jī)】

1、動(dòng)機(jī)實(shí)驗(yàn)配置

2、軟件開(kāi)銷(xiāo)成為存儲(chǔ)性能瓶頸

如下圖，像3D-Xpoint這樣的新介質(zhì)和低延遲NAND可以讓新的NVMe設(shè)備表現(xiàn)出個(gè)位數(shù)微秒級(jí)延遲和1e6(十萬(wàn))級(jí)別的IOPS。從訪(fǎng)問(wèn)一代快速NVMe設(shè)備開(kāi)始，軟件開(kāi)銷(xiāo)占比就達(dá)到15%，到現(xiàn)在訪(fǎng)問(wèn)最新的NVMe設(shè)備時(shí)，軟件開(kāi)銷(xiāo)占比達(dá)到50%。

作者進(jìn)一步對(duì)內(nèi)核軟件開(kāi)銷(xiāo)進(jìn)行分解，其中使用了O_DIRECT繞過(guò)了page cache。如下表，開(kāi)銷(xiāo)最大的層是文件系統(tǒng)層(ext4)，其次是塊設(shè)備層(bio)和kernel crossing(上下文切換)，整體軟件開(kāi)銷(xiāo)占比達(dá)到48.6%。

那么，為什么不直接繞過(guò)內(nèi)核呢?

這種辦法并非靈丹妙藥：這意味著把存儲(chǔ)設(shè)備的訪(fǎng)問(wèn)完全暴露給應(yīng)用，同時(shí)應(yīng)用必須實(shí)現(xiàn)自己的文件系統(tǒng)——這意味著沒(méi)有保證數(shù)據(jù)孤立的機(jī)制，不同應(yīng)用無(wú)法共享同一個(gè)設(shè)備的空間。此外，用戶(hù)態(tài)應(yīng)用也無(wú)法接受中斷——這意味著當(dāng)I/O并非性能瓶頸時(shí)，CPU資源會(huì)被浪費(fèi)，利用率低下。而且當(dāng)多個(gè)polling的線(xiàn)程共享一個(gè)CPU時(shí)，CPU競(jìng)爭(zhēng)+缺乏同步機(jī)制會(huì)導(dǎo)致所有polling的線(xiàn)程的尾端延遲巨大，帶寬巨低。

3、BPF簡(jiǎn)介

BPF(Berkeley Packet Filter)是一個(gè)允許用戶(hù)把一個(gè)簡(jiǎn)單的函數(shù)注入內(nèi)核執(zhí)行的接口。Linux中實(shí)現(xiàn)的BPF框架叫eBPF。函數(shù)在注入前，需要經(jīng)過(guò)幾秒鐘的檢驗(yàn)(verification)，隨后這個(gè)eBPF函數(shù)就可以被正常調(diào)用了。

BPF的潛在優(yōu)勢(shì)

當(dāng)一個(gè)請(qǐng)求需要進(jìn)行多次I/O查找(resubmission)時(shí)，BPF可以避免內(nèi)核態(tài)和用戶(hù)態(tài)之間的數(shù)據(jù)遷移。例如，查找B樹(shù)的索引時(shí)，需要先從根節(jié)點(diǎn)查起，直到找到葉子節(jié)點(diǎn)。而這一過(guò)程若使用多個(gè)系統(tǒng)調(diào)用，則每一次系統(tǒng)調(diào)用都要遍歷整個(gè)內(nèi)核存儲(chǔ)棧。而若使用BPF函數(shù)，可以把剛剛的查找函數(shù)注入NVMe驅(qū)動(dòng)層，這樣只有第一次查找需要遍歷整個(gè)內(nèi)核存儲(chǔ)棧，之后的查詢(xún)結(jié)果只需要返回驅(qū)動(dòng)層即可。二者的對(duì)比如下圖：

B-Tree Lookup from User Space

B-Tree Lookup With an In-Kernel Function

其他數(shù)據(jù)結(jié)構(gòu)(LSM樹(shù))、其他操作(范圍查詢(xún)、迭代、計(jì)算統(tǒng)計(jì)數(shù)據(jù))也可以從這種機(jī)制中獲益。這些操作的特點(diǎn)是有大量“中間“(或者說(shuō)”備用“)的I/O操作，而對(duì)用戶(hù)而言只需要最后的單個(gè)結(jié)果或者I/O返回的一小部分對(duì)象。

除了在NVMe驅(qū)動(dòng)層，BPF函數(shù)也可以放在其他層，如系統(tǒng)調(diào)用。下圖是普通的系統(tǒng)調(diào)用和兩個(gè)使用BPF函數(shù)分發(fā)(或者重發(fā))I/O操作時(shí)的不同路徑。

作者在21年HotOS上的文章中比較了BPF函數(shù)在這兩個(gè)不同地方時(shí)獲得的性能收益，如下表，比較的基準(zhǔn)是read()系統(tǒng)調(diào)用。

當(dāng)CPU達(dá)到飽和態(tài)后，在NVMe驅(qū)動(dòng)層重發(fā)I/O請(qǐng)求帶來(lái)的提升最終轉(zhuǎn)化為1.8x-2.5x的帶寬增大。(具體增大多少取決于工作集中線(xiàn)程的數(shù)目)

擴(kuò)展：線(xiàn)程的數(shù)目如何影響帶寬的提升呢?

當(dāng)CPU未飽和時(shí)，線(xiàn)程越多，提升越小。而CPU飽和后，提升更加明顯。下圖6個(gè)線(xiàn)程后CPU飽和。

BPF函數(shù)越靠近底層，性能提升越大。所以，XRP的重發(fā)hook放在NVMe驅(qū)動(dòng)層。

前文提到的都是同步I/O，那么異步I/O的表現(xiàn)如何呢?

Linux內(nèi)核新提出的io_uring可以實(shí)現(xiàn)批量下發(fā)異步I/O，一定程度上攤銷(xiāo)了用戶(hù)態(tài)陷入內(nèi)核態(tài)的開(kāi)銷(xiāo)。然而每一個(gè)I/O請(qǐng)求依然要穿過(guò)整個(gè)內(nèi)核存儲(chǔ)棧。事實(shí)上，io_uring和BPF I/O重發(fā)可以相互補(bǔ)充：

io_uring可以高效地批量下發(fā)I/O請(qǐng)求，而每個(gè)I/O請(qǐng)求觸發(fā)不同的I/O鏈，eBPF函數(shù)處理這樣的I/O鏈。下圖是和只使用io_uring相比，使用io_uring+BPF hook時(shí)的帶寬提升。

注：I/O Chain Length指初始I/O和重發(fā)的I/O總數(shù)(如，B-樹(shù)的深度);batch size指在每個(gè)io_uring調(diào)用中打包的系統(tǒng)調(diào)用數(shù)。

【設(shè)計(jì)挑戰(zhàn)與原則】

1、挑戰(zhàn)1：地址轉(zhuǎn)化和安全

以索引查詢(xún)?yōu)槔?，XRP會(huì)處理一個(gè)讀I/O請(qǐng)求，然后調(diào)用BPF函數(shù)解析下一個(gè)塊的偏移量。然而，對(duì)NVMe層而言，這個(gè)偏移量沒(méi)有任何意義——因?yàn)樗狈ξ募獢?shù)據(jù)，所以不知道這個(gè)偏移量對(duì)應(yīng)的塊號(hào)。開(kāi)發(fā)者確實(shí)可以把塊的物理地址也編進(jìn)去，但是這樣一來(lái)，BPF函數(shù)可以訪(fǎng)問(wèn)設(shè)備上的任何塊——而有些塊用戶(hù)沒(méi)有訪(fǎng)問(wèn)權(quán)限。

2、挑戰(zhàn)2：并發(fā)訪(fǎng)問(wèn)

在NVMe驅(qū)動(dòng)層的XRP無(wú)法看到page cache層的寫(xiě)。若有的寫(xiě)操作修改了數(shù)據(jù)結(jié)構(gòu)的layout(如指針指向的下一塊)，而與此同時(shí)，若有一個(gè)讀請(qǐng)求在訪(fǎng)問(wèn)這一部分，XRP可能會(huì)訪(fǎng)問(wèn)到錯(cuò)誤的數(shù)據(jù)。這些可以通過(guò)鎖解決，但是在NVMe驅(qū)動(dòng)層訪(fǎng)問(wèn)鎖開(kāi)銷(xiāo)過(guò)高。

觀(guān)察：大多數(shù)盤(pán)上的數(shù)據(jù)結(jié)構(gòu)是穩(wěn)定的。

許多存儲(chǔ)引擎(B樹(shù)、LSM樹(shù))的文件相對(duì)穩(wěn)定。有些數(shù)據(jù)結(jié)構(gòu)不會(huì)就地更新盤(pán)上數(shù)據(jù)，如當(dāng)LSM樹(shù)寫(xiě)它的索引文件(SSTable)時(shí)，在它們被刪除前，這些文件都是不可修改的。這樣同步就不用那么費(fèi)勁了。有些B樹(shù)的實(shí)現(xiàn)雖然實(shí)現(xiàn)了就地更新，他們的文件的extent基本上穩(wěn)定。作者使用YCSB在MariaDB上運(yùn)行TokuDB 24小時(shí)，使用B樹(shù)，發(fā)現(xiàn)文件的extent平均每159秒改變一次，所以可以在NVMe驅(qū)動(dòng)層緩存文件系統(tǒng)元數(shù)據(jù)。

3、設(shè)計(jì)原則

一次只處理一個(gè)文件的鏈?zhǔn)街匕l(fā)

不支持遍歷需要鎖的數(shù)據(jù)結(jié)構(gòu)

用戶(hù)定義的cache(不支持page cache)

慢路徑回調(diào)：若XRP的遍歷失敗了，應(yīng)用要試著重新試一次，或者使用系統(tǒng)調(diào)用來(lái)分發(fā)I/O請(qǐng)求。

【XRP的設(shè)計(jì)與實(shí)現(xiàn)】

本論文中，XRP基于Linux的eBPF和ext4文件系統(tǒng)。

1、修改NVMe驅(qū)動(dòng)中的中斷控制器：實(shí)現(xiàn)重發(fā)I/O

當(dāng)NVMe請(qǐng)求完成時(shí)，設(shè)備向主機(jī)發(fā)送中斷，進(jìn)入中斷處理器，此時(shí)XRP通過(guò)bio調(diào)用BPF函數(shù)，訪(fǎng)問(wèn)元數(shù)據(jù)摘要，進(jìn)行地址轉(zhuǎn)化，最后準(zhǔn)備下一個(gè)NVMe請(qǐng)求，并重發(fā)，把請(qǐng)求放入NVMe提交隊(duì)列(SQ)中。

具體重發(fā)的次數(shù)是由NVMe請(qǐng)求注冊(cè)的特定BPF函數(shù)決定的。例如查找一個(gè)數(shù)狀的結(jié)構(gòu)，那么遇到中間節(jié)點(diǎn)時(shí)BPF函數(shù)會(huì)重發(fā)，直到遇到葉子節(jié)點(diǎn)時(shí)終止。目前的XRP實(shí)現(xiàn)中，對(duì)重發(fā)次數(shù)沒(méi)有硬限制。如果需要實(shí)現(xiàn)，可以在I/O請(qǐng)求描述器中增加一個(gè)重發(fā)計(jì)數(shù)器。這個(gè)計(jì)數(shù)器既不能被用戶(hù)訪(fǎng)問(wèn)，也不能被XRP的BPF函數(shù)訪(fǎng)問(wèn)，所以即使多個(gè)BPF函數(shù)執(zhí)行重發(fā)，計(jì)數(shù)器也不會(huì)超量。

BPF函數(shù)的上下文以請(qǐng)求為單位的，而元數(shù)據(jù)摘要?jiǎng)t所有核和中斷控制器共享，它的同步訪(fǎng)問(wèn)由RCU(read-copy-update)控制。

1.1 BPF hook

BPF的每個(gè)類(lèi)型對(duì)應(yīng)對(duì)應(yīng)一種程序，XRP引入了新的BPF類(lèi)型——BPF_PROG_TYPE_XRP。它的簽名如下：

任何符合這個(gè)簽名的BPF程序都可以被這個(gè)hook調(diào)用。下一部分會(huì)展示一個(gè)具體的符合該簽名的BPF程序。

BPF_PROG_TYPE_XRP程序的上下文有五個(gè)域：

每個(gè)BPF上下文都為一個(gè)NVMe 請(qǐng)求所私有，因此使用BPF上下文時(shí)不需要鎖。而且，由用戶(hù)提供一個(gè)scratch緩沖區(qū)，而非使用BPF map，避免了進(jìn)程和函數(shù)不得不調(diào)用bpf_map_lookup_elem來(lái)訪(fǎng)問(wèn)scratch buffer。

1.2 BPF Verifier

BPF的寄存器分為scalar和pointer兩種，其中pointer有不同的類(lèi)型，如PTR-TO-MEM，指向一塊固定大小的內(nèi)存區(qū)域。在XRP上下文中，data和scratch的類(lèi)型是PTR TO MEM，而剩下的是scalar。BPF Verifier會(huì)根據(jù)數(shù)據(jù)類(lèi)型檢測(cè)寄存器的數(shù)據(jù)，防止訪(fǎng)問(wèn)區(qū)域外的數(shù)據(jù)。

此外，作者還實(shí)現(xiàn)了XRP類(lèi)型對(duì)應(yīng)的is_valid_acces()函數(shù)，可以檢測(cè)對(duì)上下文的訪(fǎng)問(wèn)是否正確以及返回上下文域的值的類(lèi)型。1.3 元數(shù)據(jù)摘要

中斷控制器并沒(méi)有文件以及邏輯地址到物理地址的轉(zhuǎn)換的概念。作者在此實(shí)現(xiàn)了“元數(shù)據(jù)摘要“，即一個(gè)中斷控制器與文件系統(tǒng)之間的接口，這樣，文件系統(tǒng)就可以和中斷控制器共享地址映射了從而支持基于eBPF的盤(pán)上重發(fā)。

元數(shù)據(jù)摘要包括兩個(gè)部分，如下圖：

更新函數(shù)：當(dāng)?shù)刂酚成浔桓聲r(shí)，由文件系統(tǒng)調(diào)用

查詢(xún)函數(shù)：由中斷控制器調(diào)用，返回給定偏移和長(zhǎng)度的地址映射。同時(shí)也實(shí)現(xiàn)了訪(fǎng)問(wèn)控制。

這兩類(lèi)函數(shù)的實(shí)現(xiàn)方式多種多樣，例如在本文中，作者實(shí)現(xiàn)了ext4的extent狀態(tài)樹(shù)的緩存，因此元數(shù)據(jù)摘要中包括了這個(gè)狀態(tài)樹(shù)的版本號(hào)。同時(shí)使用RCU進(jìn)行并發(fā)控制——查詢(xún)函數(shù)可以很快而且無(wú)鎖。當(dāng)extent更新的同時(shí)還有查找在進(jìn)行，extent的版本號(hào)會(huì)更新。查找到的數(shù)據(jù)在返回BPF函數(shù)前會(huì)進(jìn)行二次查詢(xún)，若發(fā)現(xiàn)版本號(hào)不一致，則放棄本次操作。

不過(guò)，一般應(yīng)用不會(huì)允許查找與更新同一塊區(qū)域同時(shí)進(jìn)行，所以若發(fā)生這種情況要么是應(yīng)用代碼出錯(cuò)，要么是惡意應(yīng)用。

當(dāng)然，也可以不實(shí)現(xiàn)extent狀態(tài)樹(shù)緩存——這樣update函數(shù)什么也不用做。但是，此時(shí)查詢(xún)需要先獲得自旋鎖，會(huì)變慢很多。

目前的XRP只支持ext4文件系統(tǒng)。但如f2fs等的元數(shù)據(jù)摘要也可以輕易實(shí)現(xiàn)。

1.4 重發(fā)NVMe請(qǐng)求

為了避免調(diào)用kmalloc的開(kāi)銷(xiāo)，XRP重用舊的NVMe請(qǐng)求結(jié)構(gòu)，在重發(fā)時(shí)僅僅修改physical sector和block address。

不過(guò)，重發(fā)的I/O請(qǐng)求只能抓取和舊I/O請(qǐng)求一樣多的物理段。如果BPF函數(shù)返回了多個(gè)指針(next_addr)，而NVMe請(qǐng)求不支持這多物理段的抓取，那么XRP會(huì)拋棄這個(gè)請(qǐng)求。

2、同步控制

BPF目前僅支持自旋鎖，而且同時(shí)只能獲得一個(gè)鎖，且在結(jié)束前必須釋放這個(gè)鎖。用戶(hù)應(yīng)用也無(wú)法直接訪(fǎng)問(wèn)這個(gè)鎖，必須經(jīng)過(guò)系統(tǒng)調(diào)用bpf()來(lái)讀寫(xiě)鎖保護(hù)的區(qū)域。因此，需要在多個(gè)讀和寫(xiě)之間同步的復(fù)雜的修改無(wú)法在用戶(hù)態(tài)實(shí)現(xiàn)。

用戶(hù)也可以使用BPF的原子操作自己實(shí)現(xiàn)自旋鎖，這樣用戶(hù)和BPF程序都可以直接獲得這個(gè)鎖。但是，BPF函數(shù)不能一直等待鎖被釋放——無(wú)法通過(guò)verifier。

另一種實(shí)現(xiàn)同步的方式是用RCU，XRP BPF程序在NVMe中斷控制器中實(shí)現(xiàn)，這本身就是不可搶占的，所以它們已經(jīng)在RCU的讀關(guān)鍵區(qū)了。

3、和Linux調(diào)度器的交互

進(jìn)程調(diào)度器：

作者觀(guān)察到，超低延遲存儲(chǔ)和Linux的CFS調(diào)度器存在沖突，例如當(dāng)I/O密集進(jìn)程和計(jì)算密集進(jìn)程共享一個(gè)核時(shí)，I/O密集進(jìn)程產(chǎn)生的中斷可能打斷計(jì)算密集進(jìn)程的運(yùn)行，導(dǎo)致計(jì)算密集進(jìn)程被餓死。最壞的情況下，計(jì)算密集進(jìn)程只能獲得34%的CPU時(shí)間。而當(dāng)使用較慢的設(shè)備時(shí)，則不存在這個(gè)問(wèn)題。XRP進(jìn)一步加劇了這個(gè)問(wèn)題——產(chǎn)生多個(gè)鏈?zhǔn)街袛唷Ｗ髡甙堰@一問(wèn)題留給未來(lái)的工作解決。

I/O調(diào)度器：

XRP bypass了Linux的I/O調(diào)度器。不過(guò)，noop調(diào)度器目前已經(jīng)是NVMe設(shè)備的默認(rèn)I/O調(diào)度器。而若需要保證公平，它們?cè)谟布?duì)列中有仲裁機(jī)制。

【案例分析】

如下圖，應(yīng)用可以通過(guò)調(diào)用這些函數(shù)來(lái)使用XRP。

bpf_prog_load：一個(gè)已有的函數(shù)。用于加載BPF_PROG_TYPE_XRP類(lèi)型的BPF函數(shù)到驅(qū)動(dòng)中。

read_xrp：用戶(hù)可以用它把一個(gè)特定的BPF函數(shù)應(yīng)用到一個(gè)具體的請(qǐng)求上。

在這一部分中將介紹兩個(gè)案例，以表明應(yīng)用應(yīng)該做什么樣的修改來(lái)使用XRP。

1、BPF-KV

BPF-KV是作者構(gòu)造的一個(gè)簡(jiǎn)單的KV存儲(chǔ)，它用來(lái)存儲(chǔ)小對(duì)象并且提供優(yōu)秀的讀性能。其中，BPF-KV的索引結(jié)構(gòu)是B+樹(shù)，而對(duì)象存儲(chǔ)在一個(gè)無(wú)序的日志(log)中。簡(jiǎn)單起見(jiàn)，BPF-KV使用固定大小的key(8B)和value(64B)。索引和日志一起被放在一個(gè)大文件里。索引節(jié)點(diǎn)(index node)使用簡(jiǎn)單的頁(yè)結(jié)構(gòu)(每個(gè)index node就是一個(gè)頁(yè))：頭+key+value;葉子節(jié)點(diǎn)包含一個(gè)指向下一個(gè)葉子節(jié)點(diǎn)的文件偏移量。對(duì)象的大小固定(64B)，所以對(duì)象可以在log中被就地更新，新插入的項(xiàng)會(huì)被附加在log后面，它們的索引一開(kāi)始存儲(chǔ)在內(nèi)存的哈希表中，而當(dāng)哈希表滿(mǎn)后，BPF-KV會(huì)將其和盤(pán)上的B+樹(shù)文件混合。

1.1 緩存

為了減少查找時(shí)的I/O數(shù)量，BPF-KV把頭k層B+樹(shù)索引緩存到內(nèi)存中。當(dāng)object足夠多時(shí)，不可能在內(nèi)存中緩存全部的索引。若BPF-KV用于存儲(chǔ)10 billiion 64B對(duì)象，index node的大小是512B(和Optane SSD的訪(fǎng)問(wèn)粒度匹配)，因此，每個(gè)中間節(jié)點(diǎn)可以存儲(chǔ)31的指向孩子的指針。因此，10 billion的object需要8層index。

注：

設(shè)B+樹(shù)有n層，則葉子節(jié)點(diǎn)層有

個(gè)指向object的指針，而object有 個(gè)，解得n=8.

把6層放到DRAM里面已經(jīng)很貴了(14GB)，更別說(shuō)7層(436GB)或更多了。所以，為了支持更多的key，在每次查詢(xún)中，BPF-KV會(huì)需要至少3~4個(gè)I/O(包括最終的I/O)。

除此之外，BPF-KV還有一個(gè)LRU對(duì)象緩存，里面存儲(chǔ)了最近最常使用的key-value對(duì)。

當(dāng)查詢(xún)一個(gè)object時(shí)，先查找LRU對(duì)象緩存，若沒(méi)找到，則在hash表中查找index，若沒(méi)找到，則在前k層緩存的index中查找。若遇到了不在內(nèi)存中index，則在磁盤(pán)中查詢(xún)。

1.2 BPF函數(shù)

下圖是在BPF-KV中使用的BPF函數(shù)，此處忽略了最終步(查詢(xún)log)的部分。struct node地能夠以了B+樹(shù)的index node的layout(大小為512B)。BPF函數(shù)bpfkv_bpf首先從scratch中提取目標(biāo)key，然后搜索當(dāng)前節(jié)點(diǎn)找到要讀的下一個(gè)節(jié)點(diǎn)。

1.3 接口修改

作者把read()系統(tǒng)調(diào)用換成了read_xrp()，在調(diào)用read_xrp之前，BPF-KV會(huì)先分配scratch空間，計(jì)算開(kāi)始查詢(xún)的offset。

1.4 范圍查詢(xún)

BPF-KV支持返回一些object的范圍查詢(xún)。在scratch中，存儲(chǔ)了BPF函數(shù)的狀態(tài)(查詢(xún)的范圍)和已接受的object。scratch最多頓出32個(gè)72 byte的key-value對(duì)。第一次調(diào)用時(shí)，函數(shù)找到具有開(kāi)始key的葉子節(jié)點(diǎn)，隨后把葉子節(jié)點(diǎn)存在scratch中，隨后在緩存中葉子節(jié)點(diǎn)中查找，當(dāng)葉子節(jié)點(diǎn)讀完后，函數(shù)提交下一個(gè)葉子節(jié)點(diǎn)的查找，依次類(lèi)推。當(dāng)找到范圍末端/查完整個(gè)index集/scratch空間滿(mǎn)了之后，函數(shù)返回。

1.5 統(tǒng)計(jì)計(jì)算(Aggregation)

BPF-KV支持如SUM、MAX和MIN的統(tǒng)計(jì)計(jì)算。這個(gè)計(jì)算是基于返回查詢(xún)的，在范圍查詢(xún)的上層設(shè)置了一個(gè)bit標(biāo)識(shí)是否要統(tǒng)計(jì)計(jì)算。計(jì)算后的值存在scratch中。

2 WiredTiger

WiredTiger是MongoDB默認(rèn)的KV存儲(chǔ)。其使用LSM樹(shù)組織數(shù)據(jù)：數(shù)據(jù)被分到不同的層，每一層都有一個(gè)單獨(dú)的文件，每個(gè)文件中使用B-樹(shù)索引(頁(yè)大小為512B)，而KV對(duì)存在樹(shù)的葉子節(jié)點(diǎn)中。這些文件是只讀的，更新和插入都會(huì)先寫(xiě)入內(nèi)存的buffer中，buffer滿(mǎn)之后，數(shù)據(jù)會(huì)寫(xiě)入一個(gè)新的文件。作者修改了大約500行代碼，包括buffer分配、擴(kuò)展函數(shù)簽名和封裝XRP系統(tǒng)調(diào)用。XRP加速磁盤(pán)讀，不會(huì)影響更新和插入。

2.1 BPF函數(shù)

WiredTiger安裝了和BPF-KV中類(lèi)似的BPF函數(shù)，不同點(diǎn)在于查找下一個(gè)node的指針時(shí)，WiredTiger的BPF函數(shù)把原有的for循環(huán)換成解析WiredTiger的B樹(shù)節(jié)點(diǎn)頁(yè)的端口。

2.2 緩存

WiredTiger使用LRU鏈表把一部分內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)緩存在cache中。當(dāng)查詢(xún)一個(gè)新的KV對(duì)時(shí)，WiredTiger把整個(gè)查詢(xún)路徑(包括葉子節(jié)點(diǎn))緩存下來(lái)。為了遵從WiredTiger的語(yǔ)義，上文中提到的BPF函數(shù)額外返回了所有查詢(xún)的節(jié)點(diǎn)，這樣WiredTiger就可以緩存它們了。這些查詢(xún)到的節(jié)點(diǎn)會(huì)放在scratch里，當(dāng)scratch滿(mǎn)了后，BPF函數(shù)直接返回。WiredTiger把這些節(jié)點(diǎn)加入cache后，它再次調(diào)用read_xrp，繼續(xù)查詢(xún)。

scratch的大小是4KB，所以它一共可以存6個(gè)查到的512B大小的節(jié)點(diǎn)(預(yù)留了1KB存必要的元數(shù)據(jù))。

2.3 接口修改

作者把普通的read系統(tǒng)調(diào)用全部換成了read_xrp。WiredTiger的緩存策略保證了未緩存的節(jié)點(diǎn)沒(méi)有已緩存的兒子，所以可以放心調(diào)用read_xrp返回剩余的讀路徑上的節(jié)點(diǎn)。如果read_xrp失敗了，WiredTiger會(huì)調(diào)用舊的查詢(xún)辦法。data和scratch會(huì)事先分好以避免分配和釋放緩沖區(qū)的開(kāi)銷(xiāo)。WiredTiger同時(shí)只處理一個(gè)請(qǐng)求，以避免并發(fā)。

【評(píng)估測(cè)試】

Baselines：

(a) XRP

(b) SPDK

(c) read()

(d) io_uring syscalls

1、在存儲(chǔ)場(chǎng)景下使用BPF的開(kāi)銷(xiāo)有多大?

1.1 延遲

在本實(shí)驗(yàn)中，作者執(zhí)行了

次隨機(jī)讀操作。為了關(guān)注查詢(xún)盤(pán)上數(shù)據(jù)的開(kāi)銷(xiāo)，作者關(guān)閉了內(nèi)存的緩存(緩存對(duì)象和緩存index)。平均延遲的對(duì)比如下表，最左一列的I/O數(shù)不包括獲得最終要的數(shù)據(jù)的最后一次I/O。

1)因?yàn)閄RP省去了大部分軟件棧的開(kāi)銷(xiāo)，相比read()，XRP的性能更好。而且，可以看到每增加一次index I/O，XRP的延遲增加3.5~3.9μs——約等于設(shè)備的延遲，側(cè)面證明XRP幾乎實(shí)現(xiàn)了重發(fā)請(qǐng)求的最優(yōu)性能。

注意，重發(fā)request是同步的，所以io_uring和read的表現(xiàn)差不多。

2)SPDK的性能比XRP要好，因?yàn)樵诘谝淮蜪/O時(shí)，XRP依然要穿過(guò)整個(gè)I/O棧。但是XRP不需要使用polling，進(jìn)程可以繼續(xù)利用CPU完成其他事情。下圖是99和99.9的尾端延遲隨著線(xiàn)程數(shù)的增加的變化。

當(dāng)線(xiàn)程數(shù)超過(guò)9之后，SPDK的99.99尾端延遲劇烈增加，因?yàn)樗鼈兊木€(xiàn)程使用輪詢(xún)，無(wú)法高效共享CPU。作者還測(cè)試了請(qǐng)求延遲大于等于1ms的占比，如下圖：

當(dāng)線(xiàn)程數(shù)為7時(shí)，SPDK有0.03%的請(qǐng)求延遲大于1ms，而當(dāng)線(xiàn)程數(shù)達(dá)到24時(shí)，這個(gè)比例達(dá)到0.28%。而其他幾個(gè)機(jī)制，這個(gè)比例一直低于0.01%。

1.2 帶寬(注意單位是KOPs)

如下圖，當(dāng)index深度增加時(shí)，XRP的帶寬提升和標(biāo)準(zhǔn)的系統(tǒng)調(diào)用相比更高了。

下圖是當(dāng)index深度分別為3和6時(shí)，隨著線(xiàn)程數(shù)提升的帶寬變化?？梢?jiàn)當(dāng)I/O和XRP函數(shù)被擴(kuò)展到多個(gè)核時(shí)，XRP的帶寬提升相比標(biāo)準(zhǔn)系統(tǒng)調(diào)用并沒(méi)有下降。此外，當(dāng)線(xiàn)程數(shù)超過(guò)9后，XRP的帶寬和SPDK相等甚至更高。

2、XRP擴(kuò)展到多線(xiàn)程場(chǎng)景下表現(xiàn)如何?

現(xiàn)在的存儲(chǔ)應(yīng)用常常使用大量線(xiàn)程訪(fǎng)問(wèn)存儲(chǔ)設(shè)備，因此XRP也需要在多線(xiàn)程下表現(xiàn)良好。在本實(shí)驗(yàn)中，作者進(jìn)行了一次open loop實(shí)驗(yàn)，負(fù)載量和Intel設(shè)備的最大帶寬一致(5M IOPS)，如下圖，index深度為6時(shí)，XRP(內(nèi)部是io_uring)和SPDK在BPF-KV中的帶寬隨線(xiàn)程數(shù)的變化。

當(dāng)使用6個(gè)線(xiàn)程時(shí)，SPDK和XRP都可以達(dá)到硬件允許的最大帶寬。而線(xiàn)程數(shù)增多后，SPDK的帶寬開(kāi)始下滑。因?yàn)镾PDK的輪詢(xún)線(xiàn)程必須等到Linux CFS調(diào)度(6ms)后才能被迫放棄CPU，而XRP的空閑線(xiàn)程可以主動(dòng)放棄CPU，讓CPU做有意義的工作。

下圖是12個(gè)線(xiàn)程時(shí)，隨著負(fù)載的變化，帶寬和延遲之間的關(guān)系變化?？梢?jiàn)SPDK中平均延遲和尾端延遲都比XRP增長(zhǎng)更快。

3、XRP在范圍查詢(xún)的場(chǎng)景下表現(xiàn)如何?

每次范圍查詢(xún)時(shí)，都先執(zhí)行一次index檢索找到第一個(gè)對(duì)象，之后遍歷葉子節(jié)點(diǎn)找到后面的對(duì)象。樹(shù)的深度為6，盡管XRP一次只能檢索32個(gè)對(duì)象，但由下圖可見(jiàn)和read相比，XRP提高的延遲很穩(wěn)定。

4、XRP可以加速真實(shí)世界的KV存儲(chǔ)嗎?

作者使用YCSB產(chǎn)生負(fù)載，在WiredTiger中評(píng)估了XRP的性能。作者使用了YCSB A、YCSB B、YCSB C、YCSB D、YCSB E、YCSB F六種不同的負(fù)載，每種負(fù)載運(yùn)行的時(shí)間接近。A、B、C、F中有10M個(gè)操作，D中有50M個(gè)，E中有3M個(gè)。

baseline：

pread()

read_xrp()

configure：

key-value中key和value都16B，總大小為46GB。KV對(duì)一共有10^9對(duì)。當(dāng)cahce塊滿(mǎn)時(shí)，WiredTiger會(huì)把頁(yè)剔除。使用2個(gè)剔除線(xiàn)程。

4.1 帶寬

大部分工作集中，XRP有穩(wěn)定的帶寬提升，其中最大提升1.25倍。緩存越大，XRP的提升越小。因?yàn)閃iredTiger僅花費(fèi)63%的時(shí)間在I/O操作上，所以相比BPF-KV，XRP對(duì)WiredTiger的提升更小。此外，在YCSB D和YCSB E中，XRP的提升不明顯。YCSB D中，最新插入的對(duì)象總是最常被訪(fǎng)問(wèn)，所以大部分訪(fǎng)問(wèn)都在cache中完成了。而YCSB E的大多數(shù)操作是遍歷和插入，在遍歷場(chǎng)景下，XRP只能在獲取遍歷的初始KV對(duì)時(shí)有收益，因?yàn)槭Ｏ碌腒V對(duì)一般在同一個(gè)葉子節(jié)點(diǎn)里或者只需要一次額外的I/O就可以獲得下一個(gè)葉子節(jié)點(diǎn)。

作者進(jìn)一步探究了負(fù)載的偏移對(duì)XRP性能的影響。如下圖是調(diào)整TCSB C中Zipfian分布的不同常數(shù)和均勻分布的性能提升對(duì)比，可見(jiàn)負(fù)載偏移越大，XRP的提升越小(注，正常這個(gè)常數(shù)>0.99后說(shuō)明負(fù)載偏移程度非常大了)。

4.2 尾端延遲

作者讓每個(gè)YCSB ABCDF的每個(gè)線(xiàn)程以20kop/s的速率下發(fā)負(fù)載，而YCSB E以5kop/s的速率下發(fā)負(fù)載。如下圖，XRP最多可以減少40%的尾端讀延遲(YCSB E是scan延遲)。和帶寬類(lèi)似，隨著cache size大小增大，XRP的尾端延遲減少下降了。

致謝

感謝本次論文解讀者，來(lái)自華東師范大學(xué)的碩士生俞丁翠，主要研究方向?yàn)楦咝阅艽鎯?chǔ)優(yōu)化。