王 成，葉保留*，梅 峰，盧文達(dá)

（1.計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室（南京大學(xué)），南京210023；2.國網(wǎng)浙江省電力有限公司，杭州310007）

0 引言

遠(yuǎn)程直接內(nèi)存訪問（Remote Direct Memory Access，RDMA）［1］技術(shù)允許通過網(wǎng)絡(luò)把數(shù)據(jù)直接傳入到遠(yuǎn)程系統(tǒng)的存儲(chǔ)區(qū)或者從遠(yuǎn)程系統(tǒng)存儲(chǔ)區(qū)快速讀取數(shù)據(jù)，消除了外部存儲(chǔ)器的內(nèi)容復(fù)制和系統(tǒng)的上下文切換的開銷，能夠?qū)崿F(xiàn)高帶寬和低時(shí)延的數(shù)據(jù)傳輸，為解決分布式鍵值存儲(chǔ)系統(tǒng)數(shù)據(jù)傳輸瓶頸提供了解決思路。一種常用的方法是采用基于RDMA技術(shù)支持的InfiniBand［2］高性能網(wǎng)絡(luò)作為分布式鍵值存儲(chǔ)系統(tǒng)的網(wǎng)絡(luò)環(huán)境，并通過采用IPoIB（Internet Protocol over InfiniBand）模式，可以不需要對(duì)分布式鍵值存儲(chǔ)系統(tǒng)進(jìn)行修改就將其運(yùn)行在InfiniBand高性能網(wǎng)絡(luò)上。然而，這種方式由于模擬以太網(wǎng)的數(shù)據(jù)傳輸，內(nèi)核仍然需要處理數(shù)據(jù)包，將數(shù)據(jù)拷貝到應(yīng)用中，無法充分利用RDMA的性能優(yōu)勢。因此，從更高效率的角度出發(fā)，應(yīng)充分結(jié)合RDMA技術(shù)自身的特點(diǎn)，去構(gòu)建基于RDMA的分布式鍵值存儲(chǔ)系統(tǒng)。

RDMA 技術(shù)提供了send/receive 雙邊原語和read/write 單邊原語。Jia等［3］使用RDMA的雙邊操作加速分布式深度學(xué)習(xí)系統(tǒng)TensorFlow 獲得了6 倍性能的提升；Li 等［4］也使用RDMA加速了另外一個(gè)分布式深度學(xué)習(xí)系統(tǒng)MXNet。與雙邊原語相比，read/write單邊原語不僅可以達(dá)到很大的帶寬吞吐量，而且很少占用CPU 的使用，能夠極大地降低服務(wù)器CPU 的負(fù)載，因此在進(jìn)行系統(tǒng)設(shè)計(jì)時(shí)會(huì)著重考慮使用單邊原語read/write。然而，由于read/write 的遠(yuǎn)端機(jī)器無感知的特性，需要對(duì)傳統(tǒng)鍵值系統(tǒng)put 和get 等基本操作進(jìn)行重新設(shè)計(jì)。針對(duì)get 操作設(shè)計(jì)，Pliaf［5］等系統(tǒng)中，單次get操作可能會(huì)需要過多的read輪數(shù)，影響了系統(tǒng)的整體性能；實(shí)際上，由于hash 沖突的解決方式不同，往往網(wǎng)絡(luò)read 輪數(shù)也就不同，所以如何設(shè)計(jì)高效的hash表是解決這個(gè)問題的關(guān)鍵。針對(duì)put操作設(shè)計(jì)，F(xiàn)ARM［6］、Herd［7］等系統(tǒng)大多采用多個(gè)輪詢線程來監(jiān)聽數(shù)據(jù)的到來。這雖然有利于性能的提高，但極大地耗費(fèi)了CPU 和內(nèi)存資源。Nessie［8］系統(tǒng)僅僅是針對(duì)大的value 提出了完全由客戶端驅(qū)動(dòng)的設(shè)計(jì)模式，使用了RDMA的原子鎖機(jī)制，并不適用于時(shí)延敏感的小尺寸value。Craftscached［9］系統(tǒng)將通信區(qū)中讀區(qū)域和寫區(qū)域進(jìn)行分離，從而避免數(shù)據(jù)寫入時(shí)導(dǎo)致的數(shù)據(jù)損壞，但是這種方式會(huì)花費(fèi)很多時(shí)間解決數(shù)據(jù)同步問題。除此之外，多數(shù)系統(tǒng)設(shè)計(jì)時(shí)總是無法避免數(shù)據(jù)的拷貝操作，對(duì)于數(shù)據(jù)拷貝也需要消耗服務(wù)器的CPU 資源，當(dāng)value 的數(shù)據(jù)尺寸過大時(shí)，拷貝會(huì)嚴(yán)重影響系統(tǒng)的性能。

基于上述分析，本文設(shè)計(jì)并實(shí)現(xiàn)了基于RDMA的高性能、低CPU負(fù)載的鍵值存儲(chǔ)系統(tǒng)Chequer，該系統(tǒng)具備如下幾個(gè)重要特征：首先，為了降低服務(wù)器端負(fù)載，使用read 原語設(shè)計(jì)了鍵值系統(tǒng)的get操作，實(shí)現(xiàn)了服務(wù)器的CPU旁路；其次，為了減少數(shù)據(jù)的拷貝操作，同時(shí)兼顧性能與工作負(fù)載，為get 操作提供了兩種傳輸模式；最后，設(shè)計(jì)了基于線性探測的共享hash表，解決客戶端與服務(wù)器端讀寫競爭問題與客戶端緩存失效問題，以及提高h(yuǎn)ash命中率，減少客戶端的read操作輪數(shù)。在小規(guī)模集群上實(shí)現(xiàn)了Chequer 系統(tǒng)，并采用基準(zhǔn)測試工具對(duì)其性能進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

1 Chequer整體架構(gòu)

本文結(jié)合RDMA 原語的特性，設(shè)計(jì)了基于RDMA 的鍵值存儲(chǔ)系統(tǒng)Chequer［10］，其總體架構(gòu)如圖1 所示，主要由客戶端和服務(wù)器端組成，且數(shù)據(jù)都要經(jīng)過RDMA網(wǎng)絡(luò)進(jìn)行傳輸。

圖1 Chequer整體架構(gòu)Fig.1 Overall architecture of Chequer

在Chequer 系統(tǒng)中，客戶端的主要任務(wù)是負(fù)責(zé)發(fā)起put（key，value）、get（key）、delete（key）、contains（key）等鍵值存儲(chǔ)的基本操作，而服務(wù)器端就是負(fù)責(zé)處理客戶端發(fā)起的基本操作請(qǐng)求。在Chequer 系統(tǒng)客戶端發(fā)起的get 操作中，客戶端可以使用read 原語直接從服務(wù)器端的內(nèi)存里讀取數(shù)據(jù)；而在put 操作中，客戶端可以在直接使用send 原語和使用send+write原語這兩種模式間進(jìn)行選擇。

以下將主要介紹Chequer系統(tǒng)中的兩個(gè)重要模塊：RDMA網(wǎng)絡(luò)模塊和內(nèi)存管理模塊。

1.1 RDMA網(wǎng)絡(luò)模塊

為了讓遠(yuǎn)程服務(wù)器及時(shí)收到消息，并且使遠(yuǎn)程服務(wù)器CPU 負(fù)載降低，在配合Chequer鍵值系統(tǒng)上層的get操作和put操作的前提下，網(wǎng)絡(luò)模塊實(shí)現(xiàn)了read 的讀取數(shù)據(jù)操作，以及send和send+write的發(fā)送數(shù)據(jù)操作。并且，由于RDMA底層網(wǎng)絡(luò)傳輸模式非常復(fù)雜，傳輸接口均被封裝成了類似于TCP/IP socket 的接口以掩蓋其復(fù)雜性。此外，又因?yàn)镽DMA 使能網(wǎng)卡（RDMA-enabled NIC，RNIC）的片上內(nèi)存有限，當(dāng)服務(wù)器端連接過多時(shí)，網(wǎng)絡(luò)性能會(huì)受到影響，降低了網(wǎng)絡(luò)傳輸質(zhì)量。要解決這個(gè)問題，可以采用減少隊(duì)列的創(chuàng)建和使用隊(duì)列復(fù)用的方式。在共享接收隊(duì)列的方式中，它允許工作請(qǐng)求被多個(gè)隊(duì)列對(duì)（Queue Pair，QP）來共享接收。在事件驅(qū)動(dòng)的模式中，當(dāng)傳入的消息來到任何一個(gè)與共享接收隊(duì)列關(guān)聯(lián)的QP，就會(huì)使用共享接收隊(duì)列里的工作隊(duì)列元素（Work Queue Element，WQE）來接收傳入的數(shù)據(jù)。

1.2 內(nèi)存管理模塊

內(nèi)存管理模塊用來負(fù)責(zé)服務(wù)器端的內(nèi)存管理。為了使服務(wù)器申請(qǐng)和釋放內(nèi)存塊的速度得到提高，且盡量避免服務(wù)端成為性能瓶頸，系統(tǒng)實(shí)現(xiàn)了基于Buddy 內(nèi)存管理算法的二級(jí)緩存的內(nèi)存池［11］。如圖2 所示，服務(wù)器首先向第一層快速緩存層申請(qǐng)緩沖區(qū)并釋放緩沖區(qū)；經(jīng)過內(nèi)存池的二級(jí)緩存混合緩存層后，Buddy 內(nèi)存管理層直接向操作系統(tǒng)申請(qǐng)大塊內(nèi)存，且在RDMA 網(wǎng)卡中注冊(cè)這些內(nèi)存，之后使用Buddy 算法管理內(nèi)存。Buddy 算法使得Memory Manager 對(duì)大塊連續(xù)內(nèi)存進(jìn)行管理，它會(huì)調(diào)用mmap 接口向操作系統(tǒng)申請(qǐng)大塊的連續(xù)內(nèi)存，并接收來自上層申請(qǐng)內(nèi)存和釋放連續(xù)內(nèi)存的請(qǐng)求，且可以將大塊的緩沖區(qū)切割成合適大小的緩沖區(qū)反饋給上層。

圖2 內(nèi)存池緩存模塊Fig.2 Module of memory pool caching

2 Chequer系統(tǒng)關(guān)鍵技術(shù)設(shè)計(jì)

由于RDMA 具有高帶寬、低時(shí)延以及輕CPU 負(fù)荷的特點(diǎn)，它通常用于加速一些現(xiàn)有的鍵值存儲(chǔ)系統(tǒng)。然而，僅僅使用RDMA 的send/receive 原語來改寫應(yīng)用的網(wǎng)絡(luò)層并不能充分發(fā)揮RDMA 的優(yōu)勢。本章主要結(jié)合RDMA 的read/write 原語，對(duì)鍵值存儲(chǔ)系統(tǒng)中的get 和put 操作流程進(jìn)行重新設(shè)計(jì)。其中，為了減少數(shù)據(jù)的拷貝，針對(duì)put操作，系統(tǒng)提供了兩種傳輸模式來提升操作的性能，而get操作根本不需要服務(wù)器端的參與。此外，為了減少每次get 操作所需的平均read 輪數(shù)，使get操作得到進(jìn)一步優(yōu)化，系統(tǒng)還設(shè)計(jì)了高效的共享hash表。

2.1 Put操作設(shè)計(jì)

鍵值存儲(chǔ)系統(tǒng)中包含兩個(gè)基本的修改類型操作：put（key，value）和delete（key），這兩種類型的操作需要修改數(shù)據(jù)。在大多數(shù)現(xiàn)有的基于RDMA 設(shè)計(jì)的鍵值存儲(chǔ)系統(tǒng)中，針對(duì)put 操作的設(shè)計(jì)通常會(huì)采用多個(gè)輪詢線程的方式來監(jiān)聽數(shù)據(jù)的到達(dá)。這種多個(gè)輪詢線程的方式雖然有利于性能的提高，但另一方面卻極大地耗費(fèi)了CPU 的資源，因?yàn)榧词箾]有客戶端請(qǐng)求到來，仍然會(huì)有多個(gè)輪詢線程在工作，占用了CPU資源。

除此之外，無論是基于send/receive 消息模式的設(shè)計(jì)，還是帶有輪詢監(jiān)聽的write 設(shè)計(jì)，服務(wù)器都無法避免從通信區(qū)到應(yīng)用的內(nèi)存數(shù)據(jù)拷貝。如果需要拷貝的數(shù)據(jù)量較大，不僅會(huì)造成很大的操作時(shí)延，還會(huì)造成CPU 資源的消耗，嚴(yán)重影響系統(tǒng)的性能。因此，為了減少系統(tǒng)資源的消耗，可適當(dāng)?shù)販p少數(shù)據(jù)的拷貝。例如，如果客戶端已經(jīng)確切地知道value需要存儲(chǔ)在服務(wù)器端內(nèi)存的位置，那么客戶端可以直接使用RDMA的write操作將value寫到客戶端。

然而，為了達(dá)到數(shù)據(jù)的無拷貝目的，客戶端必須得到value 在服務(wù)器端的存儲(chǔ)位置，因此，客戶端需要額外與服務(wù)器進(jìn)行一輪通信。但是這種策略對(duì)于小尺寸的value來說，若以兩輪通信為代價(jià)，其最終需要花費(fèi)的時(shí)間就變成了原來的2倍；然而隨著value的逐漸增大，第一輪客戶端與服務(wù)器的通信時(shí)間也就可以變得越來越忽略不計(jì)。所以，針對(duì)小尺寸的value，為了不影響其性能，本節(jié)將put 操作設(shè)計(jì)為混合模式傳輸。

由于客戶端發(fā)起存儲(chǔ)key-value 的請(qǐng)求中，value 的大小往往不同，大小范圍變化可從1 B到1 MB。因此，為了提高系統(tǒng)的操作性能，在設(shè)計(jì)put操作時(shí)，本節(jié)設(shè)計(jì)了put操作的兩種傳輸模式供客戶端選擇。put 操作的整體設(shè)計(jì)流程如圖3所示。

圖3 put操作流程Fig.3 Operation process of put

put 操作的第一種傳輸模式和傳統(tǒng)的put 操作模式相同。客戶端將key 和value 直接封裝成一條消息，并通過RDMA 的send原語發(fā)送給服務(wù)器端；服務(wù)器端在接收到消息請(qǐng)求后，會(huì)將key和value拷貝到相應(yīng)的hash表和存儲(chǔ)區(qū)。

在put 操作的第二種傳輸模式設(shè)計(jì)中，采用了RDMA 的write 原語。為了避免服務(wù)器端使用輪詢線程監(jiān)聽消息的到來，減少CPU 資源的浪費(fèi)，客戶端與服務(wù)器間需要額外的一輪通信。第二種put 操作的運(yùn)行過程為：客戶端首先通過RDMA 的send 原語發(fā)送key 和value 的長度給服務(wù)器端；服務(wù)器在接收到消息后，會(huì)分配存儲(chǔ)value 的內(nèi)存塊，并將該內(nèi)存塊地址通過send 原語發(fā)送返回給客戶端；最后，客戶端收到value 的內(nèi)存地址，再通過RDMA 的write 原語將value 直接寫入到服務(wù)器的內(nèi)存中。

第一種put操作模式的特點(diǎn)是所有的put操作請(qǐng)求都是由服務(wù)器端處理的。由于服務(wù)器端根本不需要處理get操作，且實(shí)際應(yīng)用場景中的工作負(fù)載基本上是讀密集型的，因此可以根據(jù)需求適當(dāng)分配一點(diǎn)工作給服務(wù)器端。在第二種put 操作模式中，使用到了write 原語，雖然它避免了服務(wù)器對(duì)value 的拷貝操作，但是需要客戶端與服務(wù)器端進(jìn)行兩輪通信，這種策略對(duì)小尺寸的value并不友好。因此，客戶端需要將兩種模式結(jié)合使用：當(dāng)value 的長度小于一定閾值時(shí)，可采用第一種put操作模式；而當(dāng)value 的長度大于或等于一定閾值時(shí)，采用第二種put 操作模式。通過實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)待發(fā)送的value 數(shù)據(jù)小于1 KB時(shí)，第一種put傳輸模式所需要的時(shí)間較少；而當(dāng)value的大小超過1 KB 時(shí)，第二種put 操作傳輸模式更優(yōu)。然而，value 長度的閾值設(shè)置不是固定的，軟件運(yùn)行環(huán)境（比如操作系統(tǒng)不同）及內(nèi)存、CPU等硬件環(huán)境都會(huì)對(duì)閾值的設(shè)置產(chǎn)生影響，所以value 長度的閾值介于512 B 到2 KB 之間。Chequer系統(tǒng)設(shè)置1 KB 作為value 長度的分界點(diǎn)，從而根據(jù)實(shí)際value的大小情況來選擇不同的傳輸模式。

2.2 get操作設(shè)計(jì)

Chequer 鍵值存儲(chǔ)系統(tǒng)中包含兩個(gè)基本的查找類型操作get（key）和contains（key）。傳統(tǒng)的get 類型操作都是在客戶端與服務(wù)器端交互模式下完成的，但服務(wù)器的性能總是有上限的，如果一個(gè)服務(wù)器為多個(gè)客戶端提供服務(wù)，而客戶端向服務(wù)器的請(qǐng)求又過于頻繁，那么服務(wù)器就很容易成為系統(tǒng)的性能瓶頸。

RDMA 的read 原語能夠使遠(yuǎn)端節(jié)點(diǎn)CPU 旁路并讀取數(shù)據(jù)，完全不需要任何服務(wù)器端CPU 的參與。如果Chequer 鍵值系統(tǒng)的客戶端已經(jīng)得知數(shù)據(jù)存儲(chǔ)在何處，那么就可以直接采用read操作進(jìn)行數(shù)據(jù)的讀取。這種方式不僅節(jié)省了服務(wù)器端CPU資源的使用，同時(shí)還提高了客戶端的并發(fā)讀取效率。

當(dāng)使用RDMA 的read原語設(shè)計(jì)get操作時(shí)，客戶端與服務(wù)器端的交互模式隨之需要改變。圖4 為get 操作的整體設(shè)計(jì)流程。在get 操作流程中，客戶端操作主要有三個(gè)步驟：1）客戶端首先通過read 操作獲取對(duì)應(yīng)的key 在服務(wù)器端hash 表上的映射記錄。2）客戶端查詢與key對(duì)應(yīng)的value數(shù)據(jù)是否緩存在本地緩存中：如果value 值被緩存，它就會(huì)被直接返回給客戶端；如果value 值沒有被緩存，就執(zhí)行下一個(gè)步驟。3）客戶端根據(jù)第1）步獲取的value的存儲(chǔ)地址，再次使用read操作從服務(wù)器端讀取value值。

圖4 get操作流程Fig.4 Operation process of get

get 操作完全不會(huì)涉及到遠(yuǎn)端服務(wù)器的CPU。為了允許客戶端發(fā)起RDMA 的read 操作，服務(wù)器端必須公開其hash 表的數(shù)據(jù)結(jié)構(gòu)。服務(wù)器端有兩塊內(nèi)存區(qū)域：第一塊內(nèi)存區(qū)域是固定大小的hash 表；另外一塊內(nèi)存區(qū)域用來存儲(chǔ)value，其中value 的長度是可變的。服務(wù)器端在啟動(dòng)時(shí)會(huì)將這兩塊內(nèi)存區(qū)域注冊(cè)到網(wǎng)卡上，而客戶端在與服務(wù)器端建立連接時(shí)，會(huì)得到服務(wù)器端相關(guān)配置信息和這兩塊內(nèi)存的注冊(cè)信息。之后，客戶端就可以在這兩塊內(nèi)存區(qū)域上執(zhí)行任意的RDMA操作。

由于服務(wù)器端不涉及到get 操作，所以get 操作完全是由客戶端發(fā)起的。而完全由客戶端發(fā)起get 操作存在一定的時(shí)間代價(jià)，客戶端至少需要花費(fèi)兩輪的時(shí)間進(jìn)行讀取操作，這樣才能獲取到key 對(duì)應(yīng)的value 值。但是與傳統(tǒng)的TCP/IP 網(wǎng)絡(luò)相比，即使該策略采用了兩輪讀取操作，這種設(shè)計(jì)模式在性能上仍然有很大的優(yōu)勢。此外，客戶端的并發(fā)訪問速度也得到了進(jìn)一步提高，使得服務(wù)器的整體性能得到了極大的提升。為了進(jìn)一步提高get操作的性能，又在中間的過程里添加了本地緩存。如果在本地緩存中能找到對(duì)應(yīng)的value值，則不需要進(jìn)行遠(yuǎn)端的value值讀取，此時(shí)僅僅只需要進(jìn)行一輪讀取就可以獲得相應(yīng)的數(shù)據(jù)。

在get 操作流程中實(shí)現(xiàn)的緩存方法是最近最少使用（Least Recently Used，LRU）算法，該算法對(duì)訪問熱點(diǎn)數(shù)據(jù)非常高效。一般的LRU 算法是通過數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，但是通過數(shù)組實(shí)現(xiàn)的LRU 算法，其時(shí)間復(fù)雜度并不是非常高效。無論是查詢操作還是刪除操作，通過數(shù)組實(shí)現(xiàn)的LRU 算法的時(shí)間復(fù)雜度都是O(n)的，其中n 為數(shù)組長度。為了提高客戶端緩存查詢的效率，本文設(shè)計(jì)了hashmap 與雙向鏈表相結(jié)合的LRU 結(jié)構(gòu)。Hashmap 用于保證查詢的時(shí)間復(fù)雜度為O(1)，而雙向鏈表保證了元素添加與刪除的時(shí)間復(fù)雜度為O(1)。

如圖5 所示，在LRU 結(jié)構(gòu)中，hashmap 記錄了key 與雙向鏈表的映射關(guān)系。例如，指針p1 記錄在key1 中，它指向雙向鏈表中記錄了key1 和value1 的某個(gè)節(jié)點(diǎn)。Hashmap 是基于哈希表的map接口實(shí)現(xiàn)，其查詢時(shí)間效率為O(1)。由于hashmap是在客戶端本地實(shí)現(xiàn)，所以可以在本地計(jì)算解決各種計(jì)算與hash沖突，使得即使存在hash沖突也不會(huì)太過影響查詢效率。而雙向鏈表用來緩存客戶端前面讀取的key-value 鍵值對(duì)。其中，prev 指針用來指向前一個(gè)節(jié)點(diǎn)，next 指針用來指向下一個(gè)節(jié)點(diǎn)。在雙向鏈表中還包括了一個(gè)頭指針和一個(gè)尾指針，通過使用雙向鏈表，客戶端可以在O(1)的時(shí)間復(fù)雜度內(nèi)刪除節(jié)點(diǎn)或者插入新的節(jié)點(diǎn)。

圖5 LRU結(jié)構(gòu)圖Fig.5 Structure diagram of LRU

2.3 共享hash表設(shè)計(jì)

當(dāng)客戶端發(fā)起get操作時(shí)，它使用RDMA 的read原語讀取hash 表中的每條記錄。而所有的put 操作，不論是兩種put 操作模式的哪種模式，都要在服務(wù)器端進(jìn)行處理，并修改hash表。因此，當(dāng)服務(wù)器端的CPU 寫本地內(nèi)存時(shí)，客戶端可能正在讀取這段內(nèi)存，這種情況就可能會(huì)導(dǎo)致客戶端讀取的信息混亂，這就是所謂的讀-寫競爭問題。

客戶端采用了兩輪操作來讀取value 數(shù)據(jù)。在第一輪中，首先根據(jù)key 的信息獲取value 的內(nèi)存地址，而在第二輪中才根據(jù)內(nèi)存地址開始讀取value。為了提高讀取效率，客戶端在本地緩存第二輪讀取的value，然而客戶端不知道它緩存的value 數(shù)據(jù)是否在服務(wù)器端已經(jīng)被修改。為了確定客戶端緩存的key-value 對(duì)是否無效，可在hash 表的每一條記錄中添加一個(gè)時(shí)間戳，當(dāng)服務(wù)器端接收到來自的客戶端put 操作或者delete 操作請(qǐng)求時(shí)，為對(duì)應(yīng)的key 生成時(shí)間戳并存儲(chǔ)在hash 記錄中。而當(dāng)客戶端進(jìn)行g(shù)et 操作時(shí)，在第一輪讀取到key 相關(guān)信息以后，客戶端會(huì)在本地緩存中查找對(duì)應(yīng)的key，如果在本地查詢到的key 對(duì)應(yīng)時(shí)間戳與第一輪讀取到的時(shí)間戳相同，那么本地緩存就不是無效的。否則客戶端需要進(jìn)行第二輪的read 操作來獲取最新的value，并及時(shí)更新本地LRU 緩存中key的時(shí)間戳和value值。

圖6顯示了設(shè)計(jì)的hash記錄數(shù)據(jù)結(jié)構(gòu)。其中，in_use表示當(dāng)前的記錄是否為空，key 是實(shí)際的鍵，value pointer 指向存儲(chǔ)value 的內(nèi)存地址，checksum1 是value 的校驗(yàn)和，time stamp 是時(shí)間戳，checksum2 就是整個(gè)記錄的校驗(yàn)和。其中，指針指向存有value 值的內(nèi)存地址，value 字符串的長度在前面，實(shí)際的value 值在后面；客戶端使用checksum1 和checksum2 來確定read 讀取的數(shù)據(jù)是否存在讀-寫競爭。如果發(fā)生checksum 不一致，表明服務(wù)器端正在修改內(nèi)存中的數(shù)據(jù)，此時(shí)客戶端會(huì)反復(fù)嘗試通過read操作獲取數(shù)據(jù)，直到獲取的數(shù)據(jù)正確為止。

hash表的命中率往往決定了系統(tǒng)的讀取性能。這是因?yàn)殡S著命中率的提高，get的讀取輪數(shù)也會(huì)隨之降低。最理想情況下，get操作在單輪就可以讀取到正確信息。為了實(shí)現(xiàn)這一點(diǎn)，就必須避免hash 沖突，然而在現(xiàn)實(shí)中hash 沖突總是會(huì)發(fā)生。在Herd 系統(tǒng)［7］中，每種操作雖然只需要一輪，但是CPU會(huì)采用輪詢的方式時(shí)刻監(jiān)聽消息的到來，降低了CPU 的效率，而需要實(shí)現(xiàn)的目標(biāo)是系統(tǒng)在保持高性能的同時(shí)降低CPU的負(fù)載。

圖6 hash 記錄結(jié)構(gòu)設(shè)計(jì)Fig.6 Design of hash record structure

經(jīng)過比較，最后選擇了線性探測hash 方式。這是因?yàn)榫€性探測與結(jié)合RDMA的read特性得到了進(jìn)一步的優(yōu)化。在線性探測hash 中，將固定數(shù)量的連續(xù)的桶定義為塊。結(jié)合RDMA 的read 能夠讀取連續(xù)內(nèi)存的能力，在一輪中就讀取到這個(gè)塊。當(dāng)?shù)谝粋€(gè)桶不滿足且存在hash 沖突時(shí)，線性探測會(huì)查詢當(dāng)前塊中第一個(gè)桶的下一個(gè)桶。如果在當(dāng)前塊所有的桶中都沒有查詢到，就讀取另外一個(gè)塊。正是通過這種預(yù)取的方式，可以使得hash表的命中率大大提高。

3 系統(tǒng)實(shí)現(xiàn)與實(shí)驗(yàn)分析

實(shí)現(xiàn)了Chequer 系統(tǒng)的C 語言版本。為了減少頻繁的內(nèi)存注冊(cè)操作，服務(wù)器需要提前預(yù)先注冊(cè)一大塊內(nèi)存，而內(nèi)存管理模塊會(huì)負(fù)責(zé)該塊內(nèi)存的申請(qǐng)與釋放。Hash 表中的校驗(yàn)和采用CRC64 循環(huán)冗余校驗(yàn)的方式，速度快，幾乎不消耗CPU資源。最后，通過異步的方式將所有的put 和delete 操作的日志同步到本地磁盤。

有關(guān)集群配置的詳細(xì)信息參見表1。在實(shí)驗(yàn)中，搭建了3個(gè)配備了RDMA網(wǎng)卡的節(jié)點(diǎn)，每臺(tái)機(jī)器的配置信息完全相同，并且這3 臺(tái)機(jī)器都通過交換機(jī)互連。實(shí)驗(yàn)中的測試數(shù)據(jù)集由YCSB（Yahoo！Cloud Serving Benchmark）［12］基準(zhǔn)測試工具生成。YCSB 可以根據(jù)實(shí)際的工作負(fù)載構(gòu)造出各種可變長度的鍵值對(duì)。此外，對(duì)于key的訪問也可以實(shí)現(xiàn)長尾zipf分布。在所有的實(shí)驗(yàn)中，value 的長度大小從16 B 到256 KB 不等，并且應(yīng)用測試使用了兩種混合類型的工作負(fù)載。一種是10%的puts 操作加90%的gets 操作，另外一種是50%的puts 操作加50%的gets操作。

表1 集群節(jié)點(diǎn)的配置信息Tab.1 Configuration information of nodes in cluster

為了便于性能比較，實(shí)現(xiàn)了一個(gè)簡易版本的Chequermessage，它僅僅使用了RDMA 的send/receive 模式來傳輸數(shù)據(jù)。Chequer-message 的客戶端使用send 操作將鍵值系統(tǒng)的put請(qǐng)求或者get請(qǐng)求打包發(fā)送給服務(wù)器端，服務(wù)器處理后，會(huì)再次通過send模式將最終結(jié)果發(fā)送給客戶端。

圖7 展示了10%的puts 操作加90%的gets 操作工作負(fù)載下的實(shí)驗(yàn)結(jié)果，圖8 展示了50%的puts 操作加50%的gets 操作工作負(fù)載下的實(shí)驗(yàn)結(jié)果。對(duì)比圖7 和圖8 可以發(fā)現(xiàn)，Chequer不論在何種工作負(fù)載、何種value 大小下，都獲得了很高的性能。在value 為64 B 的情況下，Chequer 的吞吐量是Chequer-message的2倍多；而在value大小為64 KB的情況下，Chequer 的吞吐量是Chequer-message 的1.3 倍多。這是因?yàn)殡S著value的增大，系統(tǒng)開銷主要花費(fèi)在網(wǎng)絡(luò)傳輸上。

圖7 90%gets+10%puts工作負(fù)載下的服務(wù)器吞吐量Fig.7 Throughput of server under workload of 90%gets+10%puts

圖8 50%gets+50%puts工作負(fù)載下的服務(wù)器吞吐量Fig.8 Throughput of server under workolad of 50%gets+50%puts

4 結(jié)語

隨著處理器性能的逐漸增強(qiáng)，分布式系統(tǒng)遇到了網(wǎng)絡(luò)瓶頸，RDMA 技術(shù)可以帶來很好的網(wǎng)絡(luò)性能優(yōu)化。本文設(shè)計(jì)了一種基于RDMA 的鍵值存儲(chǔ)系統(tǒng)Chequer，具有高性能、低CPU負(fù)載、可靈活擴(kuò)展的特性?；赗DMA提供的原語，本文重新設(shè)計(jì)了鍵值存儲(chǔ)系統(tǒng)的put 操作和get 操作流程，以達(dá)到高性能、低負(fù)載的特性，并結(jié)合read特性設(shè)計(jì)了基于線性探測的共享hash表，從而進(jìn)一步優(yōu)化了get操作性能。與采用傳統(tǒng)設(shè)計(jì)方式實(shí)現(xiàn)的RDMA鍵值存儲(chǔ)系統(tǒng)相比，在value為64 B時(shí)Chequer 有著2 倍以上性能的提升，而在value 為64 KB 時(shí)Chequer 有著1.3 倍以上性能的提升。與現(xiàn)有工作基于RDMA 的鍵值存儲(chǔ)系統(tǒng)相比，Chequer 會(huì)使用更少的CPU資源。

本文在進(jìn)行Chequer 系統(tǒng)設(shè)計(jì)時(shí)，主要考慮了系統(tǒng)性能與利用率，未來還將考慮結(jié)合多副本備份機(jī)制進(jìn)一步提升其可用性［13-14］。