基于RDMA高速網(wǎng)絡(luò)的高性能分布式系統(tǒng)

魏星達(dá)，陳榕，陳海波

上海交通大學(xué)并行與分布式系統(tǒng)研究所，上海 200240

1 引言

對(duì)于分布式系統(tǒng)而言，如何加速網(wǎng)絡(luò)通信一直以來都是一個(gè)非常重要的問題。例如此前的研究[1]指出，將一個(gè)單機(jī)鍵值存儲(chǔ)系統(tǒng)應(yīng)用到基于客戶機(jī)—服務(wù)器（client-server）模式的分布式環(huán)境中，即便使用了批量處理（batching）等優(yōu)化技術(shù)，仍然會(huì)造成大幅的性能下降。分布式系統(tǒng)依賴網(wǎng)絡(luò)通信完成節(jié)點(diǎn)間的協(xié)作，因此通信開銷很大程度上決定了應(yīng)用程序的整體性能。傳統(tǒng)的網(wǎng)絡(luò)協(xié)議棧（如TCP/IP）并不是針對(duì)高性能應(yīng)用場(chǎng)景設(shè)計(jì)的，因此難以提供高效的通信支持，系統(tǒng)調(diào)用和內(nèi)存復(fù)制等操作都會(huì)帶來巨大的性能開銷。

遠(yuǎn)程直接內(nèi)存訪問（remote direct memory access，RDMA）技術(shù)是一種最早應(yīng)用于高性能計(jì)算領(lǐng)域的網(wǎng)絡(luò)通信協(xié)議，當(dāng)前已在數(shù)據(jù)中心逐漸普及[2-3]。RDMA允許用戶程序繞過操作系統(tǒng)內(nèi)核，直接和網(wǎng)卡交互進(jìn)行網(wǎng)絡(luò)通信，從而提供高帶寬和極小時(shí)延。此外，RDMA還提供了one-sided原語（one-sided primitive），即網(wǎng)卡可以在沒有遠(yuǎn)端節(jié)點(diǎn)幫助的情況下，由網(wǎng)卡直接發(fā)起和完成對(duì)遠(yuǎn)程內(nèi)存的讀寫請(qǐng)求，在提升CPU利用率的同時(shí)，為分布式系統(tǒng)的設(shè)計(jì)提供了更多的可能。從系統(tǒng)軟件設(shè)計(jì)的角度而言，可以直接將RDMA視為一種更快的網(wǎng)絡(luò)，并通過模擬TCP/IP的方式（即IBoIP模式）直接加速現(xiàn)有應(yīng)用。然而這樣無法完全利用RDMA提供的性能優(yōu)勢(shì)。近幾年來，學(xué)術(shù)界以及工業(yè)界提出了一系列基于RDMA的分布式系統(tǒng)[4-11]，探索了如何通過對(duì)現(xiàn)有系統(tǒng)的再設(shè)計(jì)充分發(fā)揮出RDMA的硬件性能，實(shí)現(xiàn)數(shù)量級(jí)的性能提升。下面首先對(duì)RDMA技術(shù)進(jìn)行簡(jiǎn)要介紹，并進(jìn)一步從RDMA優(yōu)化技術(shù)、遠(yuǎn)程過程調(diào)用實(shí)現(xiàn)、分布式鍵值存儲(chǔ)系統(tǒng)、分布式事務(wù)處理系統(tǒng)等方面介紹當(dāng)前領(lǐng)域的研究進(jìn)展以及筆者在這些領(lǐng)域中的一些工作。

2 RDMA概述

RDMA網(wǎng)絡(luò)協(xié)議允許用戶程序繞過操作系統(tǒng)內(nèi)核直接進(jìn)行網(wǎng)絡(luò)通信。這樣既避免了用戶空間到系統(tǒng)空間的復(fù)制開銷，也可以省去進(jìn)入內(nèi)核處理的開銷，極大地降低了網(wǎng)絡(luò)時(shí)延，并且提高了吞吐量。此外，RDMA技術(shù)還提供了新的網(wǎng)絡(luò)原語，網(wǎng)卡可以繞過處理器直接處理對(duì)服務(wù)器內(nèi)存的讀寫請(qǐng)求。網(wǎng)卡提供了對(duì)遠(yuǎn)程內(nèi)存的讀（read）、寫（write）和原子（atomics）操作，可以極大地提升遠(yuǎn)程服務(wù)器的CPU使用效率。圖1展示了使用不同網(wǎng)絡(luò)架構(gòu)讀取服務(wù)器端內(nèi)存中數(shù)據(jù)的操作流程。圖1（a）展示了如何利用RDMA的one-sided特性來減少服務(wù)器端的開銷，服務(wù)器的網(wǎng)卡使用直接內(nèi)存存取（direct memory access，DMA）讀取用戶需要的內(nèi)存數(shù)據(jù)，并返回給用戶。圖1（b）展示了如何利用RDMA的消息原語（send/recv）來加速數(shù)據(jù)傳遞過程?？蛻舳丝梢灾苯影l(fā)送請(qǐng)求給網(wǎng)卡，網(wǎng)卡使用direct請(qǐng)求讀回，并發(fā)送給遠(yuǎn)端服務(wù)器。這樣節(jié)省了用戶程序進(jìn)入內(nèi)核以及內(nèi)存復(fù)制的開銷。圖1（c）展示了使用傳統(tǒng)網(wǎng)絡(luò)消息機(jī)制（TCP/IP）處理讀寫請(qǐng)求的過程。可以看到，用戶程序首先進(jìn)入操作系統(tǒng)內(nèi)核，將請(qǐng)求復(fù)制到內(nèi)核的緩沖區(qū)，內(nèi)核再給網(wǎng)卡發(fā)送請(qǐng)求。服務(wù)端接收到用戶請(qǐng)求后，讀取內(nèi)存內(nèi)容，再以相同的步驟將讀取的內(nèi)存發(fā)回給客戶端。

圖1 RDMA與傳統(tǒng)網(wǎng)絡(luò)的對(duì)比

表1總結(jié)了RDMA支持的3種操作。send/recv操作支持傳統(tǒng)消息通信的方法：一臺(tái)機(jī)器可以用send操作給另一臺(tái)機(jī)器發(fā)送消息，同時(shí)它可以用recv操作接收其他機(jī)器發(fā)送給它的消息。一臺(tái)機(jī)器可以利用write請(qǐng)求對(duì)其他機(jī)器的內(nèi)存進(jìn)行寫操作，使用read請(qǐng)求進(jìn)行讀操作。atomics操作包括原子比較再替換（compare and swap，CAS）以及讀再增加（fetch and add，F(xiàn)AD）操作。這里筆者區(qū)分了read/atomics操作和send/write操作，這是由于send/write操作不需要返回遠(yuǎn)端服務(wù)器端的狀態(tài)，而read/atomics操作需要將遠(yuǎn)端服務(wù)器的內(nèi)存內(nèi)容返回（CAS操作會(huì)將比較的值返回給用戶程序）。

RDMA使用預(yù)先建立好的連接對(duì)（queue pair，QP）完成網(wǎng)絡(luò)通信。一個(gè)連接擁有兩個(gè)隊(duì)列（queue）：一個(gè)發(fā)送隊(duì)列和一個(gè)接收隊(duì)列。發(fā)送隊(duì)列記錄著需要網(wǎng)卡發(fā)送的請(qǐng)求，接收隊(duì)列記錄其他網(wǎng)卡的請(qǐng)求以及發(fā)送隊(duì)列中請(qǐng)求完成的事件。RDMA支持創(chuàng)建多種不同種類的連接，每種連接支持不同的RDMA請(qǐng)求種類，表1總結(jié)了不同種類的QP以及其所支持的操作類型。可靠連接（reliable connection，RC）支持RDMA的所有操作類型。不可靠連接（unreliable connection，UC）只支持send/recv操作和write操作，而不可靠數(shù)據(jù)報(bào)（unreliable datagram，UD）只支持send/recv操作。RC的QP有可靠性的保證，請(qǐng)求的完成狀態(tài)會(huì)被返回給用戶，因此RC的QP是最為常用的RDMA連接。然而，在特定場(chǎng)景中其他QP可以用來提升系統(tǒng)的性能。

表1 RDMA的連接模式以及支持的操作

當(dāng)前流行的RDMA實(shí)現(xiàn)主要有3種：InfiniBand、RoCE和iWARP。InfiniBand是針對(duì)RDMA特性設(shè)計(jì)的，較早出現(xiàn)在高性能計(jì)算領(lǐng)域，并且近幾年開始在數(shù)據(jù)中心得到普及[4-5]。RoCE和iWARP可以在傳統(tǒng)以太網(wǎng)環(huán)境中實(shí)現(xiàn)RDMA的特性。

3 RDMA研究進(jìn)展

目前學(xué)術(shù)界對(duì)RDMA在分布式場(chǎng)景中的應(yīng)用主要涉及兩個(gè)方面：一是如何更加高效地配置和使用RDMA技術(shù)本身；二是如何利用RDMA特性加速現(xiàn)有系統(tǒng)。

3.1 RDMA優(yōu)化技術(shù)

現(xiàn)有的RDMA優(yōu)化工作主要集中在如何優(yōu)化網(wǎng)卡資源的使用上?，F(xiàn)有網(wǎng)卡一般使用DMA對(duì)內(nèi)存數(shù)據(jù)進(jìn)行操作。除了使用DMA對(duì)數(shù)據(jù)進(jìn)行讀取以外，網(wǎng)卡還需要使用DMA讀取元數(shù)據(jù)，比如QP的信息以及和用戶態(tài)內(nèi)存相關(guān)的信息，一般被稱為內(nèi)存注冊(cè)（memory registration，MR）。這些元數(shù)據(jù)的DMA操作會(huì)顯著地影響RDMA的使用性能，網(wǎng)卡會(huì)使用自帶的內(nèi)存來緩存QP和MR的信息。然而網(wǎng)卡的內(nèi)存大小比較有限，通常無法緩存所有的元數(shù)據(jù)。因此用戶程序需要仔細(xì)地管理QP和MR創(chuàng)建的數(shù)量和使用方式。

MR記錄了用戶態(tài)虛擬內(nèi)存地址到物理內(nèi)存的頁表。為了減少網(wǎng)卡需要注冊(cè)的頁表的數(shù)量，F(xiàn)aRM[4]使用了2 GB的物理頁對(duì)RDMA進(jìn)行注冊(cè)，從而顯著地減少了網(wǎng)卡需要存儲(chǔ)的虛擬內(nèi)存翻譯項(xiàng)（page translation entry）。當(dāng)需要注冊(cè)大量?jī)?nèi)存時(shí)，該方法能夠顯著提升系統(tǒng)的性能。

對(duì)于RC和UC模式的QP來說，一個(gè)客戶端線程需要使用不同的QP與不同服務(wù)器進(jìn)行鏈接。這樣當(dāng)服務(wù)器數(shù)量和客戶端線程數(shù)量上升的時(shí)候，通常一臺(tái)機(jī)器會(huì)建立許多QP，從而造成網(wǎng)卡緩存的缺失。QP的操作是線程安全的，因此FaRM[4]讓線程之間共享QP，以減少需要?jiǎng)?chuàng)建的QP的總數(shù)量。由于共享QP需要額外的同步開銷[8]，F(xiàn)aRM利用群組來減少同步開銷。

當(dāng)一臺(tái)機(jī)器運(yùn)行多個(gè)RDMA應(yīng)用時(shí)，應(yīng)用需要建立單獨(dú)的MR，而運(yùn)行多個(gè)應(yīng)用時(shí)會(huì)注冊(cè)大量MR，造成網(wǎng)卡資源緊張。LITE[12]利用一個(gè)內(nèi)核層管理RDMA內(nèi)存注冊(cè)。所有的應(yīng)用進(jìn)入內(nèi)核發(fā)送RDMA請(qǐng)求，內(nèi)核負(fù)責(zé)監(jiān)測(cè)應(yīng)用RDMA請(qǐng)求的讀寫權(quán)限。這樣一臺(tái)機(jī)器只需要一個(gè)MR即可注冊(cè)所有的內(nèi)存，極大地減少了在網(wǎng)卡上建立的MR的數(shù)量。

此外，應(yīng)用需要使用內(nèi)存映射I/O（memory-mapped I/O，MMIO）給網(wǎng)卡發(fā)送請(qǐng)求，而MMIO通常有比較大的開銷?？突仿〈髮W(xué)的研究人員提出，多個(gè)RDMA請(qǐng)求可以被批量提交給網(wǎng)卡，這樣只需要一個(gè)MMIO就能發(fā)送多個(gè)請(qǐng)求給網(wǎng)卡，其他請(qǐng)求的內(nèi)容網(wǎng)卡可以使用DMA自行讀取[7]。doorbell batching技術(shù)能夠更好地利用網(wǎng)卡和處理器間的PCIe帶寬，同時(shí)減少了發(fā)送端的處理器開銷，因此具有更好的性能。需要注意的是，只有一個(gè)QP的請(qǐng)求才能夠以doorbell batching的方式發(fā)送給網(wǎng)卡。

3.2 遠(yuǎn)程過程調(diào)用實(shí)現(xiàn)

遠(yuǎn)程過程調(diào)用（remote procedure call，RPC）[6]是分布式計(jì)算中最基礎(chǔ)的機(jī)器間的交互方式。一臺(tái)機(jī)器可以像調(diào)用一個(gè)本地函數(shù)一樣調(diào)用遠(yuǎn)端機(jī)器的函數(shù)。高效實(shí)現(xiàn)RPC的核心是實(shí)現(xiàn)一個(gè)消息傳輸機(jī)制：調(diào)用方（客戶端）需要將調(diào)用的函數(shù)以及參數(shù)發(fā)送給處理方（服務(wù)器端），而服務(wù)器端需要通過消息傳輸機(jī)制將函數(shù)執(zhí)行的結(jié)果返回給調(diào)用方。

RDMA的QP直接提供send/recv接口實(shí)現(xiàn)RPC通信，然而send/recv操作在網(wǎng)卡端需要復(fù)雜的邏輯進(jìn)行處理，通常性能沒有直接使用RDMA one-sided操作好[4]。最近學(xué)術(shù)界和工業(yè)界提出了一系列基于RDMA的對(duì)RPC通信的優(yōu)化。

FaRM[4]使用one-sided RDMA write發(fā)送消息，服務(wù)器通過輪詢內(nèi)存內(nèi)容來接收消息。FaRM利用RDMA提供的緩存一致性和順序?qū)懙奶匦员ＷC服務(wù)器能完整地收到消息。使用FaRM消息機(jī)制的吞吐量相比傳統(tǒng)網(wǎng)絡(luò)（TCP/IP），最高能有一個(gè)數(shù)量級(jí)的提升。Herd[11]優(yōu)化了RPC在非對(duì)稱環(huán)境下的性能。非對(duì)稱環(huán)境指的是一個(gè)服務(wù)器需要和多個(gè)客戶端進(jìn)行交互的環(huán)境。Herd在客戶端使用one-sided RDMA write發(fā)送消息，這是因?yàn)閛ne-sided操作的接收端（in-bound）性能最好。Herd使用基于UD的send/recv操作從服務(wù)器端向客戶端回復(fù)，這是由于UD的QP的連接數(shù)比RC的QP少，從而具有更好的可擴(kuò)展性和發(fā)送端（out-bound）性能。FaSST[8]進(jìn)一步將基于UD的send/recv操作應(yīng)用到一個(gè)對(duì)稱的場(chǎng)景中，利用doorbell batching對(duì)UD提升比較大的特性，F(xiàn)aSST RPC對(duì)發(fā)送方具有更好的性能。這對(duì)于一些發(fā)送消息不大的場(chǎng)景（如事務(wù)處理場(chǎng)景）非常有效?；趏ne-sided RDMA write的消息存在接收方的輪詢開銷隨著機(jī)器數(shù)增加而增加的問題，這是由于每臺(tái)發(fā)送方在接收方這里都需要有一個(gè)獨(dú)立的緩存來存儲(chǔ)消息。Octopus[9]提出的RPC實(shí)現(xiàn)了使用RDMA one-sided write-with-IMM操作來發(fā)送消息，通過在接收方產(chǎn)生一個(gè)write完成事件，不同服務(wù)器的寫請(qǐng)求事件可以被接收方一次性地獲取，從而避免了不必要的輪詢。Su M等人[10]提出了一種新的思路——遠(yuǎn)程獲取范式（remote fetching paradigm，RFP）來實(shí)現(xiàn)消息傳輸，服務(wù)器將請(qǐng)求的回復(fù)緩存在本地內(nèi)存中，客戶端使用one-sided RDMA read來讀取消息。這樣盡可能地利用了RDMA的性能，因?yàn)镽DMA out-bound的性能比in-bound的性能差。

3.3 分布式鍵值存儲(chǔ)系統(tǒng)優(yōu)化

內(nèi)存鍵值存儲(chǔ)（key-value store）是分布式系統(tǒng)的一個(gè)重要組件。它可以作為一個(gè)單獨(dú)數(shù)據(jù)庫，也可以作為一個(gè)緩存層來加速基于磁盤的存儲(chǔ)系統(tǒng)[13]。鍵值數(shù)據(jù)庫被廣泛部署在大規(guī)模網(wǎng)絡(luò)服務(wù)商，如Amazon[14]和Facebook[15-16]等。鍵值數(shù)據(jù)庫一般提供兩種操作：Get(key)操作是指給定一個(gè)數(shù)據(jù)的key(鍵)，返回?cái)?shù)據(jù)的值；Put(key,value)操作將key對(duì)應(yīng)的數(shù)據(jù)值更新為value。

鍵值數(shù)據(jù)庫的操作都是簡(jiǎn)單的讀寫操作，因此可以有效地利用RDMA。Pliaf[17]使用one-sided讀操作來實(shí)現(xiàn)Get操作，從而達(dá)到高性能和高處理器利用率。直接使用read操作有一個(gè)問題，即一個(gè)Get/Put的查找通常需要進(jìn)行多次內(nèi)存讀操作，造成多次網(wǎng)絡(luò)通信。為了減少查詢的網(wǎng)絡(luò)通信次數(shù)，Pliaf利用Cuckoo Hash表[18]作為其底層的索引實(shí)現(xiàn)。Pliaf的Put操作發(fā)送給服務(wù)器處理，同時(shí)使用自驗(yàn)證（selfverifying）數(shù)據(jù)結(jié)構(gòu)來確保one-sided讀操作讀回的數(shù)據(jù)在有并發(fā)的Put操作的情況下是一致的。FaRM-KV[4]使用了一個(gè)優(yōu)化過的Hopscotch[19]Hash表來同時(shí)達(dá)到比較好的存儲(chǔ)利用率和單詞查找需要的讀操作。Herd[11]利用Herd-RPC優(yōu)化鍵值存儲(chǔ)系統(tǒng)。通過優(yōu)化，RPC可以擁有與read操作相似或者比read操作更好的性能，并且RPC有更少的網(wǎng)絡(luò)傳輸次數(shù)。因此一個(gè)為鍵值存儲(chǔ)優(yōu)化過的RPC比基于多次onesided讀操作的查詢操作有更好的性能。Cell[20]提供了一種可以用one-sided讀操作實(shí)現(xiàn)Get的B樹方案，從而使鍵值存儲(chǔ)系統(tǒng)支持范圍搜索（range query）。雖然B樹的查找需要多個(gè)RDMA read，使用RDMA read在服務(wù)器負(fù)載比較高的情況下仍然能夠獲得性能優(yōu)勢(shì)。

3.4 分布式事務(wù)處理系統(tǒng)優(yōu)化

許多電子商務(wù)系統(tǒng)依賴在線事務(wù)處理（on-line transaction processing，OLTP）作為后端支持。在分布式事務(wù)處理中，事務(wù)需要給多臺(tái)機(jī)器發(fā)送消息進(jìn)行數(shù)據(jù)同步，同時(shí)服務(wù)器需要一直處理事務(wù)請(qǐng)求。如何高效地處理事務(wù)中的網(wǎng)絡(luò)請(qǐng)求對(duì)系統(tǒng)性能的影響非常重要。

FaRM[5]利用一個(gè)混合的處理方式來執(zhí)行事務(wù)，如數(shù)據(jù)讀取和驗(yàn)證步驟使用RDMA read操作執(zhí)行，其余的操作使用FaRM RPC[4]實(shí)現(xiàn)。FaSST[8]使用一個(gè)針對(duì)RDMA優(yōu)化過的RPC庫來支持事務(wù)處理。Zamanian E等人[21]提出了一個(gè)新的基于RDMA的執(zhí)行架構(gòu)——NAM（networkattached-memory），在NAM架構(gòu)中客戶端在大部分情況下只用RDMA和服務(wù)器交互。他們?cè)贜AM架構(gòu)中優(yōu)化了快照隔離（snapshot isolation，SI）協(xié)議[22]，從而使得基于SI的分布式事務(wù)處理系統(tǒng)能夠借助RDMA擴(kuò)展到大規(guī)模集群中。

3.5 其他利用RDMA的系統(tǒng)

除了鍵值存儲(chǔ)系統(tǒng)和事務(wù)處理系統(tǒng)外，還有許多根據(jù)RDMA特性設(shè)計(jì)的系統(tǒng)。GraM[23]利用一個(gè)對(duì)多核和RDMA感知的通信棧來優(yōu)化分布式圖分析系統(tǒng)。Octopus[9]是一個(gè)基于RDMA的分布式文件系統(tǒng)，利用RDMA來加速文件系統(tǒng)的文件讀取修改操作，同時(shí)使用基于RDMA優(yōu)化的RPC方法來管理文件系統(tǒng)的元數(shù)據(jù)。DrTM+B[24]是一個(gè)高效的在線數(shù)據(jù)遷移系統(tǒng)，利用RDMA read進(jìn)行數(shù)據(jù)遷移，由于read操作繞過了處理器，數(shù)據(jù)遷移的過程基本不影響正常請(qǐng)求的處理。最后，還有一系列使用RDMA技術(shù)來加速一致性協(xié)議實(shí)現(xiàn)的工作[25-26]。APUS[26]使用基于RDMA的一致性（consensus）協(xié)議將用戶的請(qǐng)求進(jìn)行備份，在不修改服務(wù)器程序的情況下提供高效的可用性。

4 RDMA的應(yīng)用

4.1 分布式鍵值存儲(chǔ)系統(tǒng)：DrTM-KV

DrTM-KV[27]是一個(gè)基于one-sided RDMA操作的高效鍵值存儲(chǔ)系統(tǒng)，能夠?yàn)榉植际绞聞?wù)處理系統(tǒng)提供數(shù)據(jù)存儲(chǔ)支持。在事務(wù)處理系統(tǒng)中，處理器的計(jì)算資源被大量地用在請(qǐng)求處理上，因此提高服務(wù)器處理器的利用率非常重要。

4.1.1 Cluster hashing

DrTM-KV使用Hash表來索引鍵值數(shù)據(jù)庫，數(shù)據(jù)會(huì)根據(jù)數(shù)據(jù)鍵（key）來Hash到對(duì)應(yīng)的內(nèi)存地址，快速找到數(shù)據(jù)所在的位置。DrTM-KV只使用RDMA read和write操作實(shí)現(xiàn)Get和Put操作，這樣就減少了處理器對(duì)數(shù)據(jù)查詢的開銷。這在事務(wù)處理的場(chǎng)景中非常重要，因?yàn)槭聞?wù)處理場(chǎng)景是一個(gè)處理器密集的應(yīng)用場(chǎng)景。DrTM-KV的設(shè)計(jì)考慮了減少單次Get和Put操作所需要的內(nèi)存讀寫次數(shù)，以減少對(duì)應(yīng)的網(wǎng)絡(luò)通信次數(shù)。傳統(tǒng)的基于鏈表的Hash結(jié)構(gòu)使用鏈表來存儲(chǔ)具有相同Hash的數(shù)據(jù)值，以解決Hash沖突（Hash collision）問題。這樣一次查找操作可能需要多次內(nèi)存訪問才能夠找到所需的數(shù)據(jù)值。這種情況對(duì)于基于RDMA的實(shí)現(xiàn)不是很友好，因?yàn)槎啻卧L問對(duì)應(yīng)了多次RDMA read請(qǐng)求。即使RDMA比傳統(tǒng)網(wǎng)絡(luò)快一個(gè)數(shù)量級(jí)，one-sided請(qǐng)求仍然比內(nèi)存訪問慢一個(gè)數(shù)量級(jí)[4]。這使得發(fā)送多次one-sided請(qǐng)求的效率低于發(fā)送一個(gè)網(wǎng)絡(luò)消息讓服務(wù)器幫忙處理的效率[11]。此外，為了減少每次Get以及Put操作所需的one-sided RDMA操作次數(shù)，DrTM-KV使用聚集（clustering）來減少有Hash沖突的情況下所需的one sided操作次數(shù)。整個(gè)Hash表基于傳統(tǒng)的鏈?zhǔn)紿ash表的結(jié)構(gòu)。為了支持使用RDMA的查詢，DrTM-KV將RDMA注冊(cè)的區(qū)域分為兩個(gè)部分：索引結(jié)構(gòu)和數(shù)據(jù)部分。每個(gè)索引部分的bucket記錄了數(shù)據(jù)的鍵和其對(duì)應(yīng)的值（在數(shù)據(jù)部分的地址）。

在DrTM-KV中，一個(gè)Get/Put操作首先通過Hash函數(shù)找到key所在的索引部分的bucket。如果在bucket中找到了key，那么可以直接從bucket中的地址讀取數(shù)據(jù)的值。否則，需要遍歷下一個(gè)bucket中的數(shù)據(jù)。為了減少每個(gè)查詢bucket鏈的次數(shù)，DrTM-KV將多個(gè)鍵聚集到一個(gè)bucket中，這樣有效地減少了鏈表的長(zhǎng)度。將數(shù)據(jù)和索引分開會(huì)造成讀取索引內(nèi)容的不一致問題，在查找完數(shù)據(jù)地址到數(shù)據(jù)讀取內(nèi)容期間，數(shù)據(jù)的地址可能會(huì)被修改。這將導(dǎo)致查找時(shí)讀取的數(shù)據(jù)地址和實(shí)際數(shù)據(jù)的位置不對(duì)應(yīng)。DrTM-KV使用一個(gè)校驗(yàn)機(jī)制使得Get/Put操作可以檢測(cè)出數(shù)據(jù)不一致的情況。數(shù)據(jù)會(huì)記錄一個(gè)額外的校驗(yàn)碼，這個(gè)校驗(yàn)碼也會(huì)存儲(chǔ)在索引的bucket中。為了節(jié)省空間，bucket中只存儲(chǔ)校驗(yàn)碼的14個(gè)bit，通常情況下這樣足夠檢測(cè)出不一致的情況[4]。在插入或刪除數(shù)據(jù)時(shí)，bucket和數(shù)據(jù)的校驗(yàn)碼會(huì)被更新。這樣DrTM-KV通過檢測(cè)校驗(yàn)碼是否一致來檢測(cè)數(shù)據(jù)是否被刪除。

4.1.2 基于數(shù)據(jù)位置的緩存

經(jīng)過Cluster hashing的優(yōu)化，DrTMKV能夠有效地減少Get/Put操作需要查找索引的RDMA read次數(shù)。然而在最優(yōu)情況下，DrTM-KV仍然需要2次RDMA read操作將數(shù)據(jù)的值讀回：一次查找索引，一次讀取數(shù)據(jù)的值。為了能夠?qū)崿F(xiàn)一次RDMA操作便能將數(shù)據(jù)讀取回來，DrTM-KV在每臺(tái)機(jī)器上使用了一個(gè)緩存來緩存數(shù)據(jù)鍵對(duì)應(yīng)的值的地址。這樣，當(dāng)數(shù)據(jù)的地址被緩存在本地時(shí)，本地機(jī)器可以直接使用一次RDMA read操作將數(shù)據(jù)讀回。需要注意的是，DrTM-KV并不緩存數(shù)據(jù)的值，而只緩存數(shù)據(jù)的地址，這樣不需要進(jìn)行數(shù)據(jù)值的同步。否則，每次數(shù)據(jù)的更新都需要將其他機(jī)器緩存的值更新，這在分布式環(huán)境下具有非常大的開銷。

DrTM-KV的緩存在數(shù)據(jù)被插入或者刪除時(shí)才需要更新。為了檢測(cè)數(shù)據(jù)被刪除或插入的情況，DrTM-KV的緩存也借助校驗(yàn)碼來檢測(cè)機(jī)器緩存的位置是否失效。緩存中同樣存儲(chǔ)著數(shù)據(jù)的校驗(yàn)碼，當(dāng)從緩存中的位置讀回的數(shù)據(jù)校驗(yàn)碼和緩存中的校驗(yàn)碼不一致時(shí)，緩存被認(rèn)為無效。這時(shí)應(yīng)用需要重新利用RDMA遍歷索引把數(shù)據(jù)讀回。

通常不需要很大的緩存就能夠記錄很多數(shù)據(jù)的位置。首先，地址的大小通常比數(shù)據(jù)的大小小很多；其次，在真實(shí)應(yīng)用場(chǎng)景中數(shù)據(jù)的訪問模式都是不均勻分布的，也就是說某一小部分?jǐn)?shù)據(jù)被訪問的頻率會(huì)比其他數(shù)據(jù)高很多。這樣經(jīng)常被訪問的數(shù)據(jù)可以被緩存起來。DrTM-KV利用傳統(tǒng)的緩存驅(qū)逐（eviction）機(jī)制（如LRU）來控制緩存的大小。

4.2 分布式圖數(shù)據(jù)查詢系統(tǒng)：Wukong

圖2 Wukong的系統(tǒng)架構(gòu)

Wukong[28]是一個(gè)高效的分布式資源描述框架（resource description framework，RDF）圖查詢系統(tǒng)。RDF是一種描述網(wǎng)絡(luò)資源的框架，被廣泛用來描述網(wǎng)絡(luò)中的數(shù)據(jù)集，例如Google公司的knowledge graph[29]。圖2展示了Wukong的架構(gòu)。RDF的數(shù)據(jù)集被劃分后，部署在多臺(tái)機(jī)器中，其中每臺(tái)機(jī)器的每個(gè)核都共享這個(gè)圖。一個(gè)用戶請(qǐng)求需要訪問多臺(tái)機(jī)器的數(shù)據(jù)。Wukong針對(duì)RDMA的特性進(jìn)行了一系列的優(yōu)化來加速在RDF上的查詢。首先，Wukong利用一個(gè)對(duì)RDMA和RDF友好的數(shù)據(jù)庫來存儲(chǔ)RDF數(shù)據(jù)，這樣RDF圖能通過RDMA高效地進(jìn)行查詢。其次，Wukong利用RDMA優(yōu)化圖查詢的規(guī)劃，使用全歷史剪枝（full-history pruning）的方法優(yōu)化查詢的步驟。最后，Wukong利用RDMA擴(kuò)展了傳統(tǒng)分布式執(zhí)行的fork-join模式，提出了in-place模式，并采用in-place和fork-join混合的方法來優(yōu)化執(zhí)行。

4.2.1 RDMA友好的數(shù)據(jù)存儲(chǔ)

圖查詢系統(tǒng)一般使用鍵值數(shù)據(jù)庫來存儲(chǔ)RDF圖。Wukong使用DrTM-KV[27]作為其底層的鍵值存儲(chǔ)系統(tǒng)，這樣Wukong可以直接利用DrTM-KV的許多針對(duì)RDMA的優(yōu)化，例如cluster Hashing和基于位置的緩存。

傳統(tǒng)的RDF存儲(chǔ)使用圖頂點(diǎn)的ID作為數(shù)據(jù)的鍵，然而這會(huì)造成很多冗余的數(shù)據(jù)傳輸：因?yàn)橐粋€(gè)頂點(diǎn)會(huì)有很多條邊，這些邊都會(huì)被劃分到這個(gè)頂點(diǎn)的數(shù)據(jù)中。這樣直接利用頂點(diǎn)ID查詢圖會(huì)讀取很多不需要的邊。在數(shù)據(jù)量很大時(shí)，RDMA的性能會(huì)急劇下降，因?yàn)檫@時(shí)網(wǎng)絡(luò)的帶寬會(huì)成為制約因素。Wukong采用更細(xì)粒度的劃分方式，將圖頂點(diǎn)的ID和邊的方向作為數(shù)據(jù)庫的鍵。這樣一次查詢只需要返回需要的點(diǎn)和邊，極大地減少了單個(gè)查詢所需要的數(shù)據(jù)傳輸量。

4.2.2 全歷史剪枝方法

一個(gè)對(duì)RDF的查詢通常會(huì)檢索到很大一部分圖數(shù)據(jù)，因此適當(dāng)?shù)貙?duì)要檢索的圖的空間進(jìn)行剪枝會(huì)極大地提升查詢的效率。傳統(tǒng)的方法通常使用單步剪枝法，然而這樣帶來的并發(fā)性并不高，下一步查詢需要等到當(dāng)前查詢的結(jié)果完成之后才能進(jìn)行。Wukong基于RDMA的一個(gè)非常有趣的觀察是：RDMA網(wǎng)絡(luò)read操作發(fā)送1 byte和2 KB時(shí)，請(qǐng)求完成的時(shí)延幾乎相同。Wukong可以發(fā)送更多的消息用來方便剪枝操作，卻不會(huì)帶來網(wǎng)絡(luò)性能的明顯下降。因此Wukong使用全歷史剪枝技術(shù)，在跨機(jī)器查詢時(shí)，將查詢的歷史完整地發(fā)送給對(duì)方機(jī)器。這樣，在每臺(tái)機(jī)器執(zhí)行查詢的時(shí)候，所有任務(wù)可以依照歷史信息進(jìn)行獨(dú)立剪枝，通過異步執(zhí)行來提高查詢的并發(fā)性。

4.2.3 RDMA友好的執(zhí)行模式

在傳統(tǒng)分布式計(jì)算中，當(dāng)查詢涉及多臺(tái)機(jī)器時(shí)，服務(wù)器利用一個(gè)fork-join的模式來計(jì)算：服務(wù)器發(fā)送請(qǐng)求給所有涉及的機(jī)器進(jìn)行計(jì)算（fork），然后再匯總結(jié)果（join）。fork-join模式是一種自然的分布式計(jì)算方式，然而fork-join計(jì)算的時(shí)延與參與處理機(jī)器的負(fù)載情況非常相關(guān)。此外，總時(shí)延是由參與處理的最慢的機(jī)器決定的，容易造成較長(zhǎng)的尾時(shí)延（long tail latency）[30]。長(zhǎng)尾效應(yīng)在實(shí)際應(yīng)用場(chǎng)景中對(duì)系統(tǒng)的性能影響非常大，有研究表明渲染一個(gè)用戶頁面通常可能會(huì)存在幾千個(gè)子請(qǐng)求[17]。

Wukong利用RDMA來減少長(zhǎng)尾效應(yīng)對(duì)圖查詢處理時(shí)延的影響，在可能的情況下，Wukong會(huì)利用RDMA read操作繞過處理器進(jìn)行圖查詢。這被稱為in-place執(zhí)行模式。當(dāng)查詢可以直接用RDMA onesided操作處理時(shí)，這個(gè)請(qǐng)求的時(shí)延基本恒定，不會(huì)被服務(wù)器處理器的負(fù)載所影響。同時(shí)one-sided操作相比等價(jià)的消息處理，具有更低的時(shí)延。雖然使用inplace模式可以完全繞過處理器，但是它只能處理比較簡(jiǎn)單的讀數(shù)據(jù)請(qǐng)求，無法處理復(fù)雜的請(qǐng)求，比如聚合（join）等。因此，Wukong采取的是一種混合的模式，即當(dāng)請(qǐng)求在一臺(tái)機(jī)器上涉及的數(shù)據(jù)比較多時(shí)，Wukong采用fork-join模式來執(zhí)行，否則，采用in-phace模式執(zhí)行。Wukong同時(shí)使用RDMA write操作來加速fork-join模式下的消息傳輸。

5 未來方向

隨著硬件技術(shù)的發(fā)展，最新的RDMA網(wǎng)卡已經(jīng)可以達(dá)到200 GB的帶寬，并且one-sided操作的時(shí)延可以低至600 ns。同時(shí)，RDMA網(wǎng)卡開始支持更多的one-sided操作。Mellanox的Connect-X5網(wǎng)卡提供了新的NVMeF（NVMe over fabrics）特性，使得RDMA one-sided操作可以直接操作固態(tài)存儲(chǔ)設(shè)備。這讓RDMA可以直接用來加速分布式的日志系統(tǒng)。同時(shí)學(xué)術(shù)界提出了一系列針對(duì)RDMA one-sided操作的新特性[31-32]。例如，Sabres[31]使用了原子的one-sided read操作，這個(gè)操作可以用來加速基于one-sided read的鍵值存儲(chǔ)系統(tǒng)。這些更加高效的硬件給新的分布式系統(tǒng)設(shè)計(jì)帶來新的挑戰(zhàn)，因?yàn)榫W(wǎng)絡(luò)將不再是性能的瓶頸。

除了利用RDMA網(wǎng)卡來加速現(xiàn)有分布式系統(tǒng)以外，現(xiàn)有系統(tǒng)開始使用多種硬件結(jié)合來進(jìn)一步地獲取性能提升。由于RDMA支持更加通用的網(wǎng)絡(luò)操作，onesided操作只支持簡(jiǎn)單的讀寫語義，這樣直接用來實(shí)現(xiàn)系統(tǒng)（如鍵值存儲(chǔ)）會(huì)帶來不必要的開銷。KV-direct[33]利用可編程網(wǎng)卡將鍵值存儲(chǔ)數(shù)據(jù)庫操作直接下陷到網(wǎng)卡中，在KV-direct中鍵值數(shù)據(jù)庫的性能只被網(wǎng)絡(luò)或者PCIe限制。隨著摩爾定律增長(zhǎng)變得緩慢，未來的分布式系統(tǒng)將更加依賴于定制化的硬件來獲得新的性能提升。

6 結(jié)束語

本文介紹了如何利用新型快速網(wǎng)絡(luò)RDMA來優(yōu)化典型的分布式系統(tǒng)。首先介紹了如何利用RDMA來優(yōu)化消息傳輸機(jī)制，從而對(duì)分布式系統(tǒng)進(jìn)行通用的優(yōu)化，并進(jìn)一步介紹了在多個(gè)領(lǐng)域基于RDMA技術(shù)的優(yōu)化工作，包括鍵值存儲(chǔ)系統(tǒng)和事務(wù)處理系統(tǒng)等，展示了如何基于RDMA特性來進(jìn)行系統(tǒng)的重新設(shè)計(jì)。