基于遠程直接內存訪問的高性能鍵值存儲系統

王 成，葉保留*，梅 峰，盧文達

（1.計算機軟件新技術國家重點實驗室（南京大學），南京210023；2.國網浙江省電力有限公司，杭州310007）

0 引言

遠程直接內存訪問（Remote Direct Memory Access，RDMA）［1］技術允許通過網絡把數據直接傳入到遠程系統的存儲區或者從遠程系統存儲區快速讀取數據，消除了外部存儲器的內容復制和系統的上下文切換的開銷，能夠實現高帶寬和低時延的數據傳輸，為解決分布式鍵值存儲系統數據傳輸瓶頸提供了解決思路。一種常用的方法是采用基于RDMA技術支持的InfiniBand［2］高性能網絡作為分布式鍵值存儲系統的網絡環境，并通過采用IPoIB（Internet Protocol over InfiniBand）模式，可以不需要對分布式鍵值存儲系統進行修改就將其運行在InfiniBand高性能網絡上。然而，這種方式由于模擬以太網的數據傳輸，內核仍然需要處理數據包，將數據拷貝到應用中，無法充分利用RDMA的性能優勢。因此，從更高效率的角度出發，應充分結合RDMA技術自身的特點，去構建基于RDMA的分布式鍵值存儲系統。

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

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

1 Chequer整體架構

本文結合RDMA 原語的特性，設計了基于RDMA 的鍵值存儲系統Chequer［10］，其總體架構如圖1 所示，主要由客戶端和服務器端組成，且數據都要經過RDMA網絡進行傳輸。

圖1 Chequer整體架構Fig.1 Overall architecture of Chequer

在Chequer 系統中，客戶端的主要任務是負責發起put（key，value）、get（key）、delete（key）、contains（key）等鍵值存儲的基本操作，而服務器端就是負責處理客戶端發起的基本操作請求。在Chequer 系統客戶端發起的get 操作中，客戶端可以使用read 原語直接從服務器端的內存里讀取數據；而在put 操作中，客戶端可以在直接使用send 原語和使用send+write原語這兩種模式間進行選擇。

以下將主要介紹Chequer系統中的兩個重要模塊：RDMA網絡模塊和內存管理模塊。

1.1 RDMA網絡模塊

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

1.2 內存管理模塊

內存管理模塊用來負責服務器端的內存管理。為了使服務器申請和釋放內存塊的速度得到提高，且盡量避免服務端成為性能瓶頸，系統實現了基于Buddy 內存管理算法的二級緩存的內存池［11］。如圖2 所示，服務器首先向第一層快速緩存層申請緩沖區并釋放緩沖區；經過內存池的二級緩存混合緩存層后，Buddy 內存管理層直接向操作系統申請大塊內存，且在RDMA 網卡中注冊這些內存，之后使用Buddy 算法管理內存。Buddy 算法使得Memory Manager 對大塊連續內存進行管理，它會調用mmap 接口向操作系統申請大塊的連續內存，并接收來自上層申請內存和釋放連續內存的請求，且可以將大塊的緩沖區切割成合適大小的緩沖區反饋給上層。

圖2 內存池緩存模塊Fig.2 Module of memory pool caching

2 Chequer系統關鍵技術設計

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

2.1 Put操作設計

鍵值存儲系統中包含兩個基本的修改類型操作：put（key，value）和delete（key），這兩種類型的操作需要修改數據。在大多數現有的基于RDMA 設計的鍵值存儲系統中，針對put 操作的設計通常會采用多個輪詢線程的方式來監聽數據的到達。這種多個輪詢線程的方式雖然有利于性能的提高，但另一方面卻極大地耗費了CPU 的資源，因為即使沒有客戶端請求到來，仍然會有多個輪詢線程在工作，占用了CPU資源。

除此之外，無論是基于send/receive 消息模式的設計，還是帶有輪詢監聽的write 設計，服務器都無法避免從通信區到應用的內存數據拷貝。如果需要拷貝的數據量較大，不僅會造成很大的操作時延，還會造成CPU 資源的消耗，嚴重影響系統的性能。因此，為了減少系統資源的消耗，可適當地減少數據的拷貝。例如，如果客戶端已經確切地知道value需要存儲在服務器端內存的位置，那么客戶端可以直接使用RDMA的write操作將value寫到客戶端。

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

由于客戶端發起存儲key-value 的請求中，value 的大小往往不同，大小范圍變化可從1 B到1 MB。因此，為了提高系統的操作性能，在設計put操作時，本節設計了put操作的兩種傳輸模式供客戶端選擇。put 操作的整體設計流程如圖3所示。

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

put 操作的第一種傳輸模式和傳統的put 操作模式相同。客戶端將key 和value 直接封裝成一條消息，并通過RDMA 的send原語發送給服務器端；服務器端在接收到消息請求后，會將key和value拷貝到相應的hash表和存儲區。

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

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

2.2 get操作設計

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

RDMA 的read 原語能夠使遠端節點CPU 旁路并讀取數據，完全不需要任何服務器端CPU 的參與。如果Chequer 鍵值系統的客戶端已經得知數據存儲在何處，那么就可以直接采用read操作進行數據的讀取。這種方式不僅節省了服務器端CPU資源的使用，同時還提高了客戶端的并發讀取效率。

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

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

get 操作完全不會涉及到遠端服務器的CPU。為了允許客戶端發起RDMA 的read 操作，服務器端必須公開其hash 表的數據結構。服務器端有兩塊內存區域：第一塊內存區域是固定大小的hash 表；另外一塊內存區域用來存儲value，其中value 的長度是可變的。服務器端在啟動時會將這兩塊內存區域注冊到網卡上，而客戶端在與服務器端建立連接時，會得到服務器端相關配置信息和這兩塊內存的注冊信息。之后，客戶端就可以在這兩塊內存區域上執行任意的RDMA操作。

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

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

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

圖5 LRU結構圖Fig.5 Structure diagram of LRU

2.3 共享hash表設計

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

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

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

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

圖6 hash 記錄結構設計Fig.6 Design of hash record structure

經過比較，最后選擇了線性探測hash 方式。這是因為線性探測與結合RDMA的read特性得到了進一步的優化。在線性探測hash 中，將固定數量的連續的桶定義為塊。結合RDMA 的read 能夠讀取連續內存的能力，在一輪中就讀取到這個塊。當第一個桶不滿足且存在hash 沖突時，線性探測會查詢當前塊中第一個桶的下一個桶。如果在當前塊所有的桶中都沒有查詢到，就讀取另外一個塊。正是通過這種預取的方式，可以使得hash表的命中率大大提高。

3 系統實現與實驗分析

實現了Chequer 系統的C 語言版本。為了減少頻繁的內存注冊操作，服務器需要提前預先注冊一大塊內存，而內存管理模塊會負責該塊內存的申請與釋放。Hash 表中的校驗和采用CRC64 循環冗余校驗的方式，速度快，幾乎不消耗CPU資源。最后，通過異步的方式將所有的put 和delete 操作的日志同步到本地磁盤。

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

表1 集群節點的配置信息Tab.1 Configuration information of nodes in cluster

為了便于性能比較，實現了一個簡易版本的Chequermessage，它僅僅使用了RDMA 的send/receive 模式來傳輸數據。Chequer-message 的客戶端使用send 操作將鍵值系統的put請求或者get請求打包發送給服務器端，服務器處理后，會再次通過send模式將最終結果發送給客戶端。

圖7 展示了10%的puts 操作加90%的gets 操作工作負載下的實驗結果，圖8 展示了50%的puts 操作加50%的gets 操作工作負載下的實驗結果。對比圖7 和圖8 可以發現，Chequer不論在何種工作負載、何種value 大小下，都獲得了很高的性能。在value 為64 B 的情況下，Chequer 的吞吐量是Chequer-message的2倍多；而在value大小為64 KB的情況下，Chequer 的吞吐量是Chequer-message 的1.3 倍多。這是因為隨著value的增大，系統開銷主要花費在網絡傳輸上。

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

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

4 結語

隨著處理器性能的逐漸增強，分布式系統遇到了網絡瓶頸，RDMA 技術可以帶來很好的網絡性能優化。本文設計了一種基于RDMA 的鍵值存儲系統Chequer，具有高性能、低CPU負載、可靈活擴展的特性。基于RDMA提供的原語，本文重新設計了鍵值存儲系統的put 操作和get 操作流程，以達到高性能、低負載的特性，并結合read特性設計了基于線性探測的共享hash表，從而進一步優化了get操作性能。與采用傳統設計方式實現的RDMA鍵值存儲系統相比，在value為64 B時Chequer 有著2 倍以上性能的提升，而在value 為64 KB 時Chequer 有著1.3 倍以上性能的提升。與現有工作基于RDMA 的鍵值存儲系統相比，Chequer 會使用更少的CPU資源。

本文在進行Chequer 系統設計時，主要考慮了系統性能與利用率，未來還將考慮結合多副本備份機制進一步提升其可用性［13-14］。