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

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

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

摘要：高速的RDMA網(wǎng)絡(luò)設(shè)備已經(jīng)被廣泛部署在現(xiàn)代數(shù)據(jù)中心。RDMA可以從兩方面加速分布式系統(tǒng)：首先可以提供一種快速的消息處理機(jī)制，其次RDMA提供了新的硬件原語(yǔ)。這極大地提升了處理器的利用率以及對(duì)RDMA的使用率，但是需要重新設(shè)計(jì)系統(tǒng)。介紹了RDMA的研究進(jìn)展，概述了近年來(lái)利用RDMA加速分布式系統(tǒng)的工作，包括基于RDMA重新設(shè)計(jì)的系統(tǒng)以及如何更好地利用RDMA的設(shè)計(jì)，并給出了未來(lái)的研究方向。

關(guān)鍵詞：?分布式系統(tǒng)；鍵值存儲(chǔ)系統(tǒng)；圖處理系統(tǒng)；聯(lián)機(jī)事務(wù)處理系統(tǒng)；遠(yuǎn)程過(guò)程調(diào)用

論文引用格式：

魏星達(dá), 陳榕, 陳海波. 基于RDMA高速網(wǎng)絡(luò)的高性能分布式系統(tǒng)[J]. 大數(shù)據(jù), 2018, 4(4): 3-14.

WEI X?D, CHEN R, CHEN H?B. Optimizing distributed systems with remote direct memory access[J]. Big Data Research, 2018, 4(4): 3-14.

1? 引言

?對(duì)于分布式系統(tǒng)而言，如何加速網(wǎng)絡(luò)通信一直以來(lái)都是一個(gè)非常重要的問(wèn)題。例如此前的研究指出，將一個(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é)作，因此通信開(kāi)銷很大程度上決定了應(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ì)帶來(lái)巨大的性能開(kāi)銷。

?遠(yuǎn)程直接內(nèi)存訪問(wèn)（remote direct memory access，RDMA）技術(shù)是一種最早應(yīng)用于高性能計(jì)算領(lǐng)域的網(wǎng)絡(luò)通信協(xié)議，當(dāng)前已在數(shù)據(jù)中心逐漸普及。RDMA允許用戶程序繞過(guò)操作系統(tǒng)內(nèi)核，直接和網(wǎng)卡交互進(jìn)行網(wǎng)絡(luò)通信，從而提供高帶寬和極小時(shí)延。此外，RDMA還提供了one-sided原語(yǔ)（one-sided primitive），即網(wǎng)卡可以在沒(méi)有遠(yuǎn)端節(jié)點(diǎn)幫助的情況下，由網(wǎng)卡直接發(fā)起和完成對(duì)遠(yuǎn)程內(nèi)存的讀寫(xiě)請(qǐng)求，在提升CPU利用率的同時(shí)，為分布式系統(tǒng)的設(shè)計(jì)提供了更多的可能。從系統(tǒng)軟件設(shè)計(jì)的角度而言，可以直接將RDMA視為一種更快的網(wǎng)絡(luò)，并通過(guò)模擬TCP/IP的方式（即IBoIP模式）直接加速現(xiàn)有應(yīng)用。然而這樣無(wú)法完全利用RDMA提供的性能優(yōu)勢(shì)。近幾年來(lái)，學(xué)術(shù)界以及工業(yè)界提出了一系列基于RDMA的分布式系統(tǒng)，探索了如何通過(guò)對(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)程過(guò)程調(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é)議允許用戶程序繞過(guò)操作系統(tǒng)內(nèi)核直接進(jìn)行網(wǎng)絡(luò)通信。這樣既避免了用戶空間到系統(tǒng)空間的復(fù)制開(kāi)銷，也可以省去進(jìn)入內(nèi)核處理的開(kāi)銷，極大地降低了網(wǎng)絡(luò)時(shí)延，并且提高了吞吐量。此外， RDMA技術(shù)還提供了新的網(wǎng)絡(luò)原語(yǔ)，網(wǎng)卡可以繞過(guò)處理器直接處理對(duì)服務(wù)器內(nèi)存的讀寫(xiě)請(qǐng)求。網(wǎng)卡提供了對(duì)遠(yuǎn)程內(nèi)存的讀（read）、寫(xiě)（write）和原子（atomics）操作，可以極大地提升遠(yuǎn)程服務(wù)器的CPU使用效率。圖1展示了使用不同網(wǎng)絡(luò)架構(gòu)讀取服務(wù)器端內(nèi)存中數(shù)據(jù)的操作流程。圖1（a）展示了如何利用RDMA的one-sided特性來(lái)減少服務(wù)器端的開(kāi)銷，服務(wù)器的網(wǎng)卡使用直接內(nèi)存存取（direct memory access， DMA）讀取用戶需要的內(nèi)存數(shù)據(jù)，并返回給用戶。圖1（b）展示了如何利用RDMA的消息原語(yǔ)（send/recv）來(lái)加速數(shù)據(jù)傳遞過(guò)程。客戶端可以直接發(fā)送請(qǐng)求給網(wǎng)卡，網(wǎng)卡使用direct請(qǐng)求讀回，并發(fā)送給遠(yuǎn)端服務(wù)器。這樣節(jié)省了用戶程序進(jìn)入內(nèi)核以及內(nèi)存復(fù)制的開(kāi)銷。圖1（c）展示了使用傳統(tǒng)網(wǎng)絡(luò)消息機(jī)制（TCP/IP）處理讀寫(xiě)請(qǐng)求的過(guò)程。可以看到，用戶程序首先進(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ā)回給客戶端。?

圖1RDMA與傳統(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)行寫(xiě)操作，使用read請(qǐng)求進(jìn)行讀操作。atomics操作包括原子比較再替換（compare and swap，CAS）以及讀再增加（fetch and add，FAD）操作。這里筆者區(qū)分了read/atomics操作和send/write操作，這是由于send/write操作不需要返回遠(yuǎn)端服務(wù)器端的狀態(tài)，而read/atomics操作需要將遠(yuǎn)端服務(wù)器的內(nèi)存內(nèi)容返回（CAS操作會(huì)將比較的值返回給用戶程序）。

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

? ?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可以用來(lái)提升系統(tǒng)的性能。

當(dāng)前流行的RDMA實(shí)現(xiàn)主要有3種：InfiniBand、RoCE和iWARP。InfiniBand是針對(duì)RDMA特性設(shè)計(jì)的，較早出現(xiàn)在高性能計(jì)算領(lǐng)域，并且近幾年開(kāi)始在數(shù)據(jù)中心得到普及。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)卡資源的使用上。現(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)存來(lái)緩存QP和MR的信息。然而網(wǎng)卡的內(nèi)存大小比較有限，通常無(wú)法緩存所有的元數(shù)據(jù)。因此用戶程序需要仔細(xì)地管理QP和MR創(chuàng)建的數(shù)量和使用方式。

MR記錄了用戶態(tài)虛擬內(nèi)存地址到物理內(nèi)存的頁(yè)表。為了減少網(wǎng)卡需要注冊(cè)的頁(yè)表的數(shù)量，FaRM使用了2GB的物理頁(yè)對(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來(lái)說(shuō)，一個(gè)客戶端線程需要使用不同的QP與不同服務(wù)器進(jìn)行鏈接。這樣當(dāng)服務(wù)器數(shù)量和客戶端線程數(shù)量上升的時(shí)候，通常一臺(tái)機(jī)器會(huì)建立許多QP，從而造成網(wǎng)卡緩存的缺失。QP的操作是線程安全的，因此FaRM讓線程之間共享QP，以減少需要?jiǎng)?chuàng)建的QP的總數(shù)量。由于共享QP需要額外的同步開(kāi)銷，FaRM利用群組來(lái)減少同步開(kāi)銷。

當(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利用一個(gè)內(nèi)核層管理RDMA內(nèi)存注冊(cè)。所有的應(yīng)用進(jìn)入內(nèi) 核發(fā)送R DMA請(qǐng)求，內(nèi)核負(fù)責(zé)監(jiān)測(cè)應(yīng)用RDMA請(qǐng)求的讀寫(xiě)權(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通常有比較大的開(kāi)銷。卡耐基梅隆大學(xué)的研究人員提出，多個(gè)RDMA請(qǐng)求可以被批量提交給網(wǎng)卡，這樣只需要一個(gè)MMIO就能發(fā)送多個(gè)請(qǐng)求給網(wǎng)卡，其他請(qǐng)求的內(nèi)容網(wǎng)卡可以使用DMA自行讀取。doorbell batching技術(shù)能夠更好地利用網(wǎng)卡和處理器間的PCIe帶寬，同時(shí)減少了發(fā)送端的處理器開(kāi)銷，因此具有更好的性能。需要注意的是，只有一個(gè)QP的請(qǐng)求才能夠以doorbell batching的方式發(fā)送給網(wǎng)卡。

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

遠(yuǎn)程過(guò)程調(diào)用（remote procedure call，RPC）是分布式計(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ù)器端需要通過(guò)消息傳輸機(jī)制將函數(shù)執(zhí)行的結(jié)果返回給調(diào)用方。

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

FaRM使用one-sided RDMA write發(fā)送消息，服務(wù)器通過(guò)輪詢內(nèi)存內(nèi)容來(lái)接收消息。FaRM利用RDMA提供的緩存一致性和順序?qū)懙奶匦员ＷC服務(wù)器能完整地收到消息。使用FaRM消息機(jī)制的吞吐量相比傳統(tǒng)網(wǎng)絡(luò)（TCP/IP），最高能有一個(gè)數(shù)量級(jí)的提升。Herd優(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進(jìn)一步將基于UD的send/recv操作應(yīng)用到一個(gè)對(duì)稱的場(chǎng)景中，利用doorbell batching對(duì)UD提升比較大的特性，FaSST RPC對(duì)發(fā)送方具有更好的性能。這對(duì)于一些發(fā)送消息不大的場(chǎng)景（如事務(wù)處理場(chǎng)景）非常有效。基于one-sided RDMA write的消息存在接收方的輪詢開(kāi)銷隨著機(jī)器數(shù)增加而增加的問(wèn)題，這是由于每臺(tái)發(fā)送方在接收方這里都需要有一個(gè)獨(dú)立的緩存來(lái)存儲(chǔ)消息。Octopus提出的RPC實(shí)現(xiàn)了使用RDMA one-sided write-with-IMM操作來(lái)發(fā)送消息，通過(guò)在接收方產(chǎn)生一個(gè)write完成事件，不同服務(wù)器的寫(xiě)請(qǐng)求事件可以被接收方一次性地獲取，從而避免了不必要的輪詢。Su M等人提出了一種新的思路——遠(yuǎn)程獲取范式（remote fetching paradigm，RFP）來(lái)實(shí)現(xiàn)消息傳輸，服務(wù)器將請(qǐng)求的回復(fù)緩存在本地內(nèi)存中，客戶端使用one-sided RDMA read來(lái)讀取消息。這樣盡可能地利用了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ù)庫(kù)，也可以作為一個(gè)緩存層來(lái)加速基于磁盤(pán)的存儲(chǔ)系統(tǒng)。鍵值數(shù)據(jù)庫(kù)被廣泛部署在大規(guī)模網(wǎng)絡(luò)服務(wù)商，如Amazon和Facebook等。鍵值數(shù)據(jù)庫(kù)一般提供兩種操作：Get(key)操作是指給定一個(gè)數(shù)據(jù)的key(鍵)，返回?cái)?shù)據(jù)的值；Put(key,value)操作將key對(duì)應(yīng)的數(shù)據(jù)值更新為value。

鍵值數(shù)據(jù)庫(kù)的操作都是簡(jiǎn)單的讀寫(xiě)操作，因此可以有效地利用RDMA。Pliaf使用one-sided讀操作來(lái)實(shí)現(xiàn)Get操作，從而達(dá)到高性能和高處理 器利用率。直接使用read操作有一個(gè)問(wèn)題，即一個(gè)Get/Put的查找通常需要進(jìn)行多次內(nèi)存讀操作，造成多次網(wǎng)絡(luò)通信。為了減少查詢的網(wǎng)絡(luò)通信次數(shù)，Pliaf利用Cuckoo Hash表作為其底層的索引實(shí)現(xiàn)。Pliaf的Put操作發(fā)送給服務(wù)器處理，同時(shí)使用自驗(yàn)證（selfverifying）數(shù)據(jù)結(jié)構(gòu)來(lái)確保one-sided讀操作讀回的數(shù)據(jù)在有并發(fā)的Put操作的情況下是一致的。FaRM-KV使用了一個(gè)優(yōu)化過(guò)的HopscotchHash表來(lái)同時(shí)達(dá)到比較好的存儲(chǔ)利用率和單詞查找需要的讀操作。Herd利用Herd-RPC優(yōu)化鍵 值存儲(chǔ)系統(tǒng)。通過(guò)優(yōu)化，RPC可以擁有與read操作相似或者比read操作更好的性能，并且RPC有更少的網(wǎng)絡(luò)傳輸次數(shù)。因此一個(gè)為鍵值存儲(chǔ)優(yōu)化過(guò)的RPC比基于多次onesided讀操作的查詢操作有更好的性能。Cell提供了一種可以用one-sided讀操作實(shí)現(xiàn)Get的B樹(shù)方案，從而使鍵值存儲(chǔ)系統(tǒng)支持范圍搜索（range query）。雖然B樹(shù)的查找需要多個(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利用一個(gè)混合的處理方式來(lái)執(zhí)行事務(wù)，如數(shù)據(jù)讀取和驗(yàn)證步驟使用RDMA read操作執(zhí)行，其余的操作使用FaRM RPC實(shí)現(xiàn)。FaSST使用一個(gè)針對(duì)RDMA優(yōu)化過(guò)的RPC庫(kù)來(lái)支持事務(wù)處理。Zamanian E等人提出了一個(gè)新的基于RDMA的執(zhí)行架構(gòu)——NAM（networkattached-memory），在NAM架構(gòu)中客戶端在大部分情況下只用RDMA和服務(wù)器交互。他們?cè)贜AM架構(gòu)中優(yōu)化了快照隔離（snapshot isolation，SI）協(xié)議，從而使得基于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利用一個(gè)對(duì)多核和RDMA感知的通信棧來(lái)優(yōu)化分布式圖分析系統(tǒng)。Octopus是一個(gè)基于RDMA的分布式文件系統(tǒng)，利用RDMA 來(lái)加速文件系統(tǒng)的文件讀取修改操作，同時(shí)使用基于RDMA優(yōu)化的RPC方法來(lái)管理文件系統(tǒng)的元數(shù)據(jù)。DrTM+B是一個(gè)高效的在線數(shù)據(jù)遷移系統(tǒng)，利用RDMA read進(jìn)行數(shù)據(jù)遷移，由于read操作繞過(guò)了處理器，數(shù)據(jù)遷移的過(guò)程基本不影響正常請(qǐng)求的處理。最后，還有一系列使用RDMA技術(shù)來(lái)加速一致性協(xié)議實(shí)現(xiàn)的工作。APUS使用基于RDMA的一致性（consensus）協(xié)議將用戶的請(qǐng)求進(jìn)行備份 ，在不修改服務(wù)器程序的情況下提供高效的可用性。

4 RDMA的應(yīng)用

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

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

4.1.1Cluster hashing

DrTM-KV使用Hash表來(lái)索引鍵值數(shù)據(jù)庫(kù)，數(shù)據(jù)會(huì)根據(jù)數(shù)據(jù)鍵（key）來(lái)Hash到對(duì)應(yīng)的內(nèi)存地址，快速找到數(shù)據(jù)所在的位置。DrTM-KV只使用RDMA read和write操作實(shí)現(xiàn)Get和Put操作，這樣就減少了處理器對(duì)數(shù)據(jù)查詢的開(kāi)銷。這在事務(wù)處理的場(chǎng)景中非常重要，因?yàn)槭聞?wù)處理場(chǎng)景是一個(gè)處理器密集的應(yīng)用場(chǎng)景。DrTM-KV的設(shè)計(jì)考慮了減少單次Get和Put操作所需要的內(nèi)存讀寫(xiě)次數(shù)，以減少對(duì)應(yīng)的網(wǎng)絡(luò)通信次數(shù)。傳統(tǒng)的基于鏈表的Hash結(jié)構(gòu)使用鏈表來(lái)存儲(chǔ)具有相同Hash的數(shù)據(jù)值，以解決Hash沖突（Hash collision）問(wèn)題。這樣一次查找操作可能需要多次內(nèi)存訪問(wèn)才能夠找到所需的數(shù)據(jù)值。這種情況對(duì)于基于RDMA的實(shí)現(xiàn)不是很友好，因?yàn)槎啻卧L問(wèn)對(duì)應(yīng)了多次RDMA read請(qǐng)求。即使RDMA比傳統(tǒng)網(wǎng)絡(luò)快一個(gè)數(shù)量級(jí)，one-sided請(qǐng)求仍然比內(nèi)存訪問(wèn)慢一個(gè)數(shù)量級(jí)。這使得發(fā)送多次one-sided請(qǐng)求的效率低于發(fā)送一個(gè)網(wǎng)絡(luò)消息讓服務(wù)器幫忙處理的效率。此外，為了減少每次Get以及Put操作所需的on e-sided RDMA操作次數(shù)，DrTM-KV使用聚集（clustering）來(lái)減少有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操作首先通過(guò)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ù)和索引分開(kāi)會(huì)造成讀取索引內(nèi)容的不一致問(wèn)題，在查找完數(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è)出不一致的情況。在插入或刪除數(shù)據(jù)時(shí)， bucket和數(shù)據(jù)的校驗(yàn)碼會(huì)被更新。這樣DrTM-KV通過(guò)檢測(cè)校驗(yàn)碼是否一致來(lái)檢測(cè)數(shù)據(jù)是否被刪除。

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

經(jīng)過(guò)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ù)讀取回來(lái)，DrTM-KV在每臺(tái)機(jī)器上使用了一個(gè)緩存來(lái)緩存數(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)境下具有非常大的開(kāi)銷。

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

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

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

Wukong是一個(gè)高效的分布式資源描述框架（resource description framework，RDF）圖查詢系統(tǒng)。RDF是一種描述網(wǎng)絡(luò)資源的框架，被廣泛用來(lái)描述網(wǎng)絡(luò)中的數(shù)據(jù)集，例如Google公司的knowledge graph。圖2展示了Wukong的架構(gòu)。RDF的數(shù)據(jù)集被劃分后，部署在多臺(tái)機(jī)器中，其中每臺(tái)機(jī)器的每個(gè)核都共享這個(gè)圖。一個(gè)用戶請(qǐng)求需要訪問(wèn)多臺(tái)機(jī)器的數(shù)據(jù)。Wukong針對(duì)RDMA的特性進(jìn)行了一系列的優(yōu)化來(lái)加速在RDF上的查詢。首先，Wukong利用一個(gè)對(duì)RDMA和RDF友好的數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)RDF數(shù)據(jù)，這樣RDF圖能通過(guò)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混合的方法來(lái)優(yōu)化執(zhí)行。??

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

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

圖查詢系統(tǒng)一般使用鍵值數(shù)據(jù)庫(kù)來(lái)存儲(chǔ)RDF圖。Wukong使用DrTM-KV作為其底層的鍵值存儲(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ù)庫(kù)的鍵。這樣一次查詢只需要返回需要的點(diǎn)和邊，極大地減少了單個(gè)查詢所需要的數(shù)據(jù)傳輸量。

4.2.2 全歷史剪枝方法

一個(gè)對(duì)RDF的查詢通常會(huì)檢索到很大一部分圖數(shù)據(jù)，因此適當(dāng)?shù)貙?duì)要檢索的圖的空間進(jìn)行剪枝會(huì)極大地提升查詢的效率。傳統(tǒng)的方法通常使用單步剪枝法，然而這樣帶來(lái)的并發(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ā)送更多的消息用來(lái)方便剪枝操作，卻不會(huì)帶來(lái)網(wǎng)絡(luò)性能的明顯下降。因此Wukong使用全歷史剪枝技術(shù)，在跨機(jī)器查詢時(shí)，將查詢的歷史完整地發(fā)送給對(duì)方機(jī)器。這樣，在每臺(tái)機(jī)器執(zhí)行查詢的時(shí)候，所有任務(wù)可以依照歷史信息進(jìn)行獨(dú)立剪枝，通過(guò)異步執(zhí)行來(lái)提高查詢的并發(fā)性。

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

在傳統(tǒng)分布式計(jì)算中，當(dāng)查詢涉及多臺(tái)機(jī)器時(shí)，服務(wù)器利用一個(gè)fork-join的模式來(lái)計(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）。長(zhǎng)尾效應(yīng)在實(shí)際應(yīng)用場(chǎng)景中對(duì)系統(tǒng)的性能影響非常大，有研究表明渲染一個(gè)用戶頁(yè)面通常可能會(huì)存在幾千個(gè)子請(qǐng)求。

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

5 未來(lái)方向

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

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

6 結(jié)束語(yǔ)

? 本文介紹了如何利用新型快速網(wǎng)絡(luò)RDMA來(lái)優(yōu)化典型的分布式系統(tǒng)。首先介紹了如何利用RDMA來(lái)優(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特性來(lái)進(jìn)行系統(tǒng)的重新設(shè)計(jì)。

《大數(shù)據(jù)》期刊

《大數(shù)據(jù)（Big?Data?Research，BDR）》雙月刊是由中華人民共和國(guó)工業(yè)和信息化部主管，人民郵電出版社主辦，中國(guó)計(jì)算機(jī)學(xué)會(huì)大數(shù)據(jù)專家委員會(huì)學(xué)術(shù)指導(dǎo)，北京信通傳媒有限責(zé)任公司出版的科技期刊。

關(guān)注《大數(shù)據(jù)》期刊微信公眾號(hào)，獲取更多內(nèi)容

總結(jié)

以上是生活随笔為你收集整理的基于RDMA高速网络的高性能分布式系统的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。