面向兩段鎖并發(fā)控制的RDMA優(yōu)化技術(shù)

李婧瑤，張倩，趙展浩，盧衛(wèi)，張孝，杜小勇

中國人民大學(xué) 信息學(xué)院，北京100872

由于單機(jī)系統(tǒng)在計(jì)算能力和存儲容量上的限制，特別是擴(kuò)展能力的不足，已經(jīng)不能滿足互聯(lián)網(wǎng)各類應(yīng)用場景對海量數(shù)據(jù)分析和處理的要求，分布式系統(tǒng)得到了產(chǎn)業(yè)和學(xué)術(shù)屆的重視。特別是分布式數(shù)據(jù)庫系統(tǒng)，由于支持分布式事務(wù)，在銀行、電商等關(guān)鍵任務(wù)領(lǐng)域得到了廣泛應(yīng)用。然而，基于兩階段封鎖協(xié)議[1]的分布式系統(tǒng)受限于事務(wù)調(diào)度器的CPU 低利用率[2]和通信開銷所造成的瓶頸，其系統(tǒng)性能亟待提升。多進(jìn)程、多線程、協(xié)程等技術(shù)在一定程度上緩解了這個(gè)問題，但并沒有使其得到根本解決。最優(yōu)化數(shù)據(jù)分區(qū)模型以最小化通信需求[3-4]為目標(biāo)，然而，實(shí)踐證明不管是靜態(tài)的還是動態(tài)的分區(qū)管理方法，在復(fù)雜多變的應(yīng)用場景下，都不能完全避免集群中不同機(jī)器間的高通信成本[5]。

基于無限帶寬（infiniband，IB）高速網(wǎng)絡(luò)的遠(yuǎn)程直接數(shù)據(jù)存?。╮emote direct memory access，RDMA）技術(shù)為解決這一問題提供了新思路。相關(guān)工作[6]指出RDMA 能在更有效利用CPU 的同時(shí)降低通信延遲，針對性緩解分布式數(shù)據(jù)庫系統(tǒng)中的現(xiàn)存問題。RDMA提供雙邊、單邊兩類原語，利用預(yù)編程的網(wǎng)卡（RDMA network interface card，RNIC）和成對創(chuàng)建的隊(duì)列對（queue pair，QP）繞開傳統(tǒng)TCP/IP協(xié)議棧和操作系統(tǒng)內(nèi)核，直接訪問遠(yuǎn)端內(nèi)存。常用的操作包括單邊讀、寫、CAS和雙邊發(fā)送、接收等，其中單邊操作直接作用于遠(yuǎn)端內(nèi)存而無需遠(yuǎn)端CPU 的參與，返回的結(jié)果被寫入預(yù)先指定的內(nèi)存塊中，以提供高吞吐和低延遲，從而有效提升系統(tǒng)性能。RDMA 各原語特性及在分布式系統(tǒng)中的應(yīng)用被廣泛研究：如分析多情境下RDMA 系統(tǒng)的性能瓶頸，并提供了一些優(yōu)化方案[7]；設(shè)計(jì)結(jié)合RDMA的鍵值存儲模式[8]；提出基于RDMA的存算分離和共享內(nèi)存架構(gòu)[6,9-10]；將RDMA和已有并發(fā)控制算法如OCC、NO WAIT、WAIT DIE等結(jié)合，結(jié)合實(shí)驗(yàn)探究了最優(yōu)實(shí)現(xiàn)方式[11-13]等。其中一些工作設(shè)計(jì)了分布式系統(tǒng)在RDMA下的鎖機(jī)制[11-13]，然而它們或者僅提供排他鎖而不適應(yīng)高沖突負(fù)載，或者提供多種鎖但招致高昂的加解鎖開銷，或者加鎖協(xié)議不通用而需要較多的架構(gòu)更改，且都缺乏對沖突程度不同的多樣負(fù)載的考慮。為了更合理地設(shè)計(jì)新硬件下的分布式系統(tǒng)鎖機(jī)制，使其在保證操作原子性、數(shù)據(jù)一致性的基礎(chǔ)上受益于高性能網(wǎng)絡(luò)并盡量消除通信瓶頸，本文作出了如下貢獻(xiàn)：

（1）基于RDMA，對兩種常用的兩段鎖算法NO WAIT、WAIT DIE 進(jìn)行了優(yōu)化，提出單邊讀寫鎖和單邊排他鎖兩類加解鎖優(yōu)化策略。

（2）提出使用RDMA 單邊原語進(jìn)行加解鎖操作時(shí)的原子性問題，并提供了保障原子性的解決方案。

（3）進(jìn)行了大量實(shí)驗(yàn)，結(jié)果表明，基于RDMA 優(yōu)化的NO WAIT和WAIT DIE算法相較于傳統(tǒng)的TCP/IP有最高5.3倍和10.6倍的性能提升。另外，本文提出的兩種加解鎖策略各自在低、高沖突負(fù)載下具有相對優(yōu)越性。

1 遠(yuǎn)程直接數(shù)據(jù)存取

1.1 基本原理

遠(yuǎn)程直接數(shù)據(jù)存取（即RDMA）利用預(yù)編程的網(wǎng)卡（RNIC）和無限帶寬網(wǎng)絡(luò)（InfiniBand），可以繞過操作系統(tǒng)內(nèi)核對遠(yuǎn)端計(jì)算機(jī)內(nèi)存進(jìn)行直接訪問。與傳統(tǒng)的TCP/IP通信協(xié)議相比，RDMA具有速度快、時(shí)延低的優(yōu)勢。RDMA 原語分為單邊和雙邊兩類：單邊操作包括讀（Read）、寫（Write）、原子操作（如compare and swap，CAS；fetch and add，F(xiàn)AA）；雙邊操作包括發(fā)送、接收（Send/Receive）。

RDMA通過服務(wù)器間的隊(duì)列對完成通信。在一臺服務(wù)器上，隊(duì)列對總是被成對創(chuàng)建，包括發(fā)送隊(duì)列和接收隊(duì)列，此外還有用于接收遠(yuǎn)端消息反饋的完成隊(duì)列。在處理遠(yuǎn)程數(shù)據(jù)讀寫請求時(shí)，其首先被封裝為工作隊(duì)列元素（work queue element，WQE）并放入發(fā)送隊(duì)列中，由RNIC遵循先進(jìn)先出的原則異步處理。每一個(gè)WQE 都關(guān)聯(lián)到特定的注冊內(nèi)存空間。以雙邊寫原語為例，本地發(fā)送隊(duì)列的WQE指向存放待寫數(shù)據(jù)的內(nèi)存塊，通過RNIC形成的本端和遠(yuǎn)端內(nèi)存的直接連接，將數(shù)據(jù)寫入遠(yuǎn)端接收隊(duì)列的WQE關(guān)聯(lián)的內(nèi)存塊。相比雙邊原語，RDMA 單邊原語能夠進(jìn)一步繞開遠(yuǎn)端CPU，從而僅在請求端CPU 的參與下操作遠(yuǎn)端內(nèi)存數(shù)據(jù)，以提供更快速高效的遠(yuǎn)程讀寫。因此，對于CPU密集型應(yīng)用，單邊原語相對于雙邊原語效率更優(yōu)。然后，RNIC會輪詢完成隊(duì)列以得到失敗或成功的操作結(jié)果。最后，操作結(jié)果被返回到預(yù)指定的內(nèi)存塊，如RDMA Read返回讀取的指定數(shù)據(jù)元組，RDMA CAS返回比較當(dāng)時(shí)的目標(biāo)數(shù)據(jù)值等。

1.2 RDMA相關(guān)工作進(jìn)展

RDMA 協(xié)議基于高速帶寬InfiniBand，雙邊原語繞開內(nèi)核和單邊原語避免遠(yuǎn)端CPU參與的特性為分布式系統(tǒng)架構(gòu)的優(yōu)化帶來了新的可能：包括存算分離[6,9]和共享內(nèi)存[10]等。一方面，RDMA被廣泛應(yīng)用在分布式事務(wù)處理中：如利用RDMA 單邊周期性協(xié)調(diào)時(shí)鐘，以達(dá)到時(shí)間戳的全局一致[14]；通過不可靠雙邊RPC 實(shí)現(xiàn)內(nèi)存數(shù)據(jù)庫[15]；結(jié)合RDMA 和硬件事務(wù)內(nèi)存（hardware transactional memory，HTM）轉(zhuǎn)移并發(fā)控制邏輯[16]，并在此基礎(chǔ)上進(jìn)一步支持多副本以保證高可用[17]等。另一方面，RDMA和現(xiàn)有并發(fā)控制算法的結(jié)合受到了廣泛研究。OCC被劃分為了執(zhí)行、驗(yàn)證、日志、提交四個(gè)階段，在批處理等優(yōu)化下分階段探究了基于RDMA單邊或雙邊原語的最優(yōu)實(shí)現(xiàn)[11]。另一工作設(shè)計(jì)數(shù)據(jù)鎖表以支持基于RDMA的多級粒度加鎖，包括讀寫鎖和意向鎖[12]。它利用RDMA 單邊寫信息到遠(yuǎn)端，遠(yuǎn)端執(zhí)行加鎖并反饋，以此來取代RDMA雙邊操作并保障操作原子性。然而，此種加鎖方式雖然基于單邊原語，但事實(shí)上需要遠(yuǎn)端CPU參與，且需要管理環(huán)形共享內(nèi)存區(qū)，導(dǎo)致加鎖開銷較大，占事務(wù)總開銷的約70%，且這個(gè)比例甚至隨著節(jié)點(diǎn)的增加進(jìn)一步上升。此外，DSLR（decentralized and starvationfree lock management with RDMA）算法[13]實(shí)現(xiàn)了基于RDMA的Lamport面包店加解鎖算法，以在保證去中心化的基礎(chǔ)上避免饑餓等待。但它可能導(dǎo)致死鎖，依賴超時(shí)控制完成死鎖檢測。與現(xiàn)有工作不同，本文針對常用的死鎖預(yù)防型2PL算法NO WAIT、WAIT DIE設(shè)計(jì)了雙邊和單邊排他鎖（mutex lock，M lock）、讀寫鎖（mutex/shared lock，M/S lock）這兩種高效的加解鎖策略，并比較了它們在不同沖突程度負(fù)載下的優(yōu)劣，提供了更全面實(shí)用的參考。

1.3 RDMA原語特性

圖1展示了使用不同傳輸方式，包括基于以太網(wǎng)或InfiniBand 的TCP/IP 協(xié)議（TCP/IP over Ethernet，IPoEth；TCP/IP over InfiniBand，IPoIB）和RDMA 單邊讀寫原語時(shí)的吞吐量、延遲隨著傳輸消息大小的變化情況。在同一消息大小下，IPoIB得益于網(wǎng)絡(luò)優(yōu)勢，優(yōu)于IPoEth，而RDMA單邊總是提供最優(yōu)的吞吐量和延時(shí)。因此，在新硬件基礎(chǔ)上，進(jìn)一步設(shè)計(jì)基于RDMA原語的算法對于分布式系統(tǒng)有著積極的意義。

圖1 各傳輸方式基準(zhǔn)分析Fig.1 Microbenchmark analysis for different communication methods

2 基于RDMA的兩段鎖機(jī)制

兩段鎖是應(yīng)用最廣泛的并發(fā)控制協(xié)議之一，通過加鎖和解鎖協(xié)調(diào)事務(wù)間的沖突操作。它規(guī)定事務(wù)從第一次釋放鎖開始便不能再獲取鎖，由此將其劃分為獲取鎖的生長階段和釋放鎖的衰減階段。根據(jù)避免死鎖的方式不同，可分為NO WAIT、WAIT DIE[1]等。前者在加鎖沖突時(shí)直接回滾，后者判斷若加鎖事務(wù)時(shí)間戳小于所有持鎖事務(wù)時(shí)間戳則等待，否則回滾。嚴(yán)格的兩段鎖協(xié)議進(jìn)一步要求在事務(wù)提交或回滾后才釋放鎖。本文定義鎖機(jī)制為提供不同鎖類型和沖突處理方式的加解鎖策略，并基于嚴(yán)格的兩段鎖協(xié)議和傳統(tǒng)讀寫鎖相容矩陣，設(shè)計(jì)了基于RDMA單、雙邊原語的NO WAIT讀寫鎖、NO WAIT排他鎖、WAIT DIE 讀寫鎖、WAIT DIE 排他鎖四類鎖機(jī)制，以加速操作，提升系統(tǒng)性能。

2.1 雙邊原語實(shí)現(xiàn)

與傳統(tǒng)TCP/IP 網(wǎng)絡(luò)傳輸方式相比，RDMA 雙邊過程并不涉及系統(tǒng)內(nèi)核，傳輸效率相對高效。因此可以在原始基于TCP/IP 的并發(fā)控制算法之上，通過建立可靠連接隊(duì)列對（reliable connected queue pairs,RC QPs）來使用RDMA 雙邊原語Send 和Recv 傳輸事務(wù)的讀寫請求，而非基于TCP/IP 協(xié)議的請求以減少通信開銷。RC QPs 在創(chuàng)建時(shí)是一一對應(yīng)的：一個(gè)發(fā)送隊(duì)列發(fā)出的消息只能由對應(yīng)創(chuàng)建的接收隊(duì)列接收到。工作線程產(chǎn)生事務(wù)遠(yuǎn)程讀寫請求時(shí)，可利用已創(chuàng)建的發(fā)送隊(duì)列發(fā)送消息到遠(yuǎn)端接收隊(duì)列中，由于一個(gè)服務(wù)器中總會接收到來自其他多個(gè)服務(wù)器中多個(gè)隊(duì)列的消息，接收線程需要輪詢多個(gè)接收隊(duì)列來對不同來源的消息進(jìn)行處理。

由于RDMA 基于工作隊(duì)列（WQE）機(jī)制進(jìn)行消息的異步傳輸，產(chǎn)生Send 請求的工作線程無須等待Send 的消息被對方接收到便可發(fā)起新的Send 請求，隊(duì)列對中可同時(shí)存在多個(gè)未完成的WQE 等待。當(dāng)發(fā)送隊(duì)列或接收隊(duì)列滿時(shí)，工作線程會等待接收隊(duì)列中的Recv請求被消費(fèi)后再產(chǎn)生新的Send請求，因此當(dāng)分布式事務(wù)負(fù)載大、消息通信非常頻繁時(shí)，發(fā)送隊(duì)列和接收隊(duì)列的容量一定程度上也會影響系統(tǒng)性能。通過多次測試，本文選擇較大的隊(duì)列容量，以使得在大多數(shù)情況下消息的傳輸效率都相對最佳。因?yàn)椴淮嬖陬~外通信開銷，在兩段鎖算法的雙邊和TCP/IP實(shí)現(xiàn)中，總是提供讀寫鎖以提高讀并發(fā)度。

2.2 單邊原語實(shí)現(xiàn)

在雙邊基礎(chǔ)上，RDMA 單邊操作能夠繞開遠(yuǎn)端CPU以獲得更低的單次操作延時(shí)。故在次數(shù)相同的情況下，單邊原語往往更受青睞。然而，實(shí)踐中單邊的特性也帶來了一些問題。首先，盡管單次表現(xiàn)占優(yōu)，但是某些并發(fā)控制算法下的復(fù)雜操作可能需要多次單邊，從而造成了額外開銷；其次，由于單邊操作僅依賴于本地而隔絕了遠(yuǎn)端CPU，固有元數(shù)據(jù)結(jié)構(gòu)不能滿足便捷存取的需求；最后，傳統(tǒng)分布式系統(tǒng)中采用線程鎖保障加解鎖操作原子性的方法已不再可行，如何在保留單邊優(yōu)良性質(zhì)的基礎(chǔ)上保證算法的正確性對其設(shè)計(jì)提出了新的挑戰(zhàn)。

2.2.1 元數(shù)據(jù)

遠(yuǎn)端CPU在RDMA單邊通過RNIC和DMA（direct memory access）直接訪問遠(yuǎn)端內(nèi)存的過程中是無感的，因此需要重新定義元數(shù)據(jù)結(jié)構(gòu)以便于數(shù)據(jù)讀寫。元數(shù)據(jù)結(jié)構(gòu)如表1所示。鎖信息和數(shù)據(jù)相鄰，遠(yuǎn)端或本地讀寫數(shù)據(jù)之前都需要首先判斷鎖沖突情況。由于RDMA原子操作僅支持8 Byte大小，為減少通信往返次數(shù)并便于保障原子性，鎖位總是64 bit。僅使用排他鎖時(shí)鎖位為零即無鎖，非零有鎖。其中WAIT DIE 使用加鎖事務(wù)開始時(shí)間戳ts 作為鎖信息，以便在加鎖失敗時(shí)比較時(shí)間戳大小來判斷是否回滾。區(qū)分讀寫鎖時(shí)，鎖位最低位存儲鎖類型信息，第二位及更高位存儲鎖數(shù)量信息。區(qū)分讀寫鎖的WAIT DIE 的鎖信息中進(jìn)一步包含加鎖事務(wù)的時(shí)間戳數(shù)組。這里采用長度為N=4 的定長數(shù)組以便于實(shí)現(xiàn)單邊讀寫，第N+1 個(gè)并發(fā)讀事務(wù)將回滾。實(shí)驗(yàn)驗(yàn)證由此引發(fā)的回滾占總回滾事務(wù)的比例不超過1%，對回滾率的影響可忽略不計(jì)。

表1 元數(shù)據(jù)結(jié)構(gòu)Table 1 Metadata structure

2.2.2 原子性

基于TCP/IP的遠(yuǎn)程數(shù)據(jù)加解鎖通常由接收消息的遠(yuǎn)端CPU 采用線程鎖保障操作原子性，RDMA 單邊需要重新考慮原子性問題。首先，單邊原語中的原子操作如CAS、FAA，有RNIC 底層機(jī)制提供原子性保障。然而，RDMA CAS和本地CPU CAS相互之間不能保障原子性。因此本地也將采用RDMA CAS來保證算法正確性，這可能造成一定的性能損失[11,16]。一些正交優(yōu)化引入先進(jìn)硬件特征HTM或?yàn)榻鉀Q這一矛盾提供了可能，將作為本文的未來工作。

為了在支持讀寫鎖的同時(shí)保障原子性，基于表1數(shù)據(jù)結(jié)構(gòu)，NO WAIT 算法首先RDMA Read 讀鎖信息，解碼并判斷是否沖突，并在不沖突時(shí)利用RDMA CAS 將之前讀到的鎖信息置換為重新編碼的新鎖。此時(shí)，若CAS失敗則兩次單邊之間原子性被破壞，需重試讀到加鎖的過程。支持讀寫鎖的WAIT DIE 需要額外在每次讀時(shí)驗(yàn)證鎖位和時(shí)間戳數(shù)組中的鎖個(gè)數(shù)相同，以保證修改鎖位和時(shí)間戳數(shù)組操作間的原子性，防止讀到不一致的中間狀態(tài)。事實(shí)上，高速單邊通信下出現(xiàn)原子性問題的頻率一般較低：第3.2.2小節(jié)中實(shí)驗(yàn)驗(yàn)證平均每個(gè)事務(wù)因?yàn)樵有员黄茐亩鴮?dǎo)致的重試在大多數(shù)情況下不到一次，因此不會顯著影響分布式事務(wù)處理性能。

2.2.3 RDMA鎖機(jī)制

算法1 和算法2 給出了單邊RDMA 與不同鎖機(jī)制的結(jié)合方式。針對2PL 兩個(gè)階段分別考慮讀或?qū)憙煞N操作類型所涉及的加解鎖操作。為便于理解，僅展示訪問遠(yuǎn)端數(shù)據(jù)情形，且僅涉及加解鎖相關(guān)操作。本地類似，只是采用本地直接讀寫取代RDMA讀寫。注意，偽碼中以CAS（a,b）來代表當(dāng)目標(biāo)值為a時(shí)置其為b的操作。實(shí)際上，具體數(shù)據(jù)總是在加鎖成功后遠(yuǎn)端RDMA Read 得到，如有要提交的修改則在解鎖時(shí)一并寫回，以減少單邊次數(shù)，節(jié)省網(wǎng)絡(luò)開銷。

對于不區(qū)分讀寫鎖，僅支持排他鎖的情況，讀集和寫集元素的加解鎖相關(guān)步驟是一致的：RDMA CAS 直接加鎖（算法1，第11 行和第27 行），RDMA Write 置零解鎖（算法2，第19 行）。只是不同鎖機(jī)制的沖突處理方式有所差異。NO WAIT協(xié)議通過鎖沖突時(shí)立即回滾當(dāng)前事務(wù)以避免死鎖。WAIT DIE 在鎖沖突時(shí)并不立即回滾，而是通過比較時(shí)間戳大小來決定是否等待（算法1，第30～32 行）。它以事務(wù)開始時(shí)間戳保序預(yù)防閉環(huán)等待來避免死鎖，僅回滾部分沖突事務(wù)。如果當(dāng)前請求加鎖事務(wù)的開始時(shí)間戳小于持鎖事務(wù)時(shí)間戳?xí)r，則等待，否則回滾?；赥CP/IP的實(shí)現(xiàn)中，等待過程是非阻塞的：在每個(gè)數(shù)據(jù)項(xiàng)上維護(hù)一個(gè)等待隊(duì)列，每逢解鎖判斷其中是否有可執(zhí)行加鎖。然而，RDMA 單邊加鎖時(shí)遠(yuǎn)端是無感的，因此不能執(zhí)行上述流程。此時(shí)重復(fù)發(fā)送CAS 請求以實(shí)現(xiàn)阻塞等待。

在單邊讀寫鎖的加鎖實(shí)現(xiàn)中，NO WAIT 首先RDMA Read讀回鎖信息，本地判斷沖突與否，并在不沖突情況下RDMA CAS 加鎖。如第2.2.2 小節(jié)中有關(guān)原子性的描述，兩次單邊之間可能存在其他事務(wù)對同一數(shù)據(jù)的更改從而破壞原子性，此時(shí)重試讀、本地判斷過程直到事務(wù)沖突回滾或加鎖成功（算法1，第3～9 行）。類似地，讀集元素解鎖順序執(zhí)行讀鎖信息，CAS解鎖和可能的重試操作（算法2，第3～5行）。對于寫集元素，直接RDMA Write 置零解鎖（算法2，第7 行）。WAIT DIE 讀寫鎖的RDMA 單邊實(shí)現(xiàn)因?yàn)橐~外維護(hù)加鎖事務(wù)時(shí)間戳數(shù)組的信息而更加復(fù)雜。它需要在讀時(shí)驗(yàn)證鎖位和時(shí)間戳數(shù)組中的鎖個(gè)數(shù)相同，當(dāng)讀到不一致的中間狀態(tài)時(shí)需要重讀（算法1，第15 行；算法2，第10 行）。在加鎖成功后及讀集元素解鎖前需要同步更新時(shí)間戳數(shù)組，若后續(xù)解鎖失敗要立即寫回原有時(shí)間戳以盡量縮短處于不一致中間狀態(tài)的時(shí)間（算法1，第22 行；算法2，第11～13行）。注意讀寫鎖算法通過支持并發(fā)讀操作提高并發(fā)度，但相比排他鎖算法需要更多次的單邊操作，造成額外開銷。由于寫集僅在鎖信息為0時(shí)允許加鎖，實(shí)現(xiàn)中實(shí)際上簡化了讀和沖突判斷步驟，直接RDMA CAS加鎖即可。

算法1RDMA加鎖算法

輸入：事務(wù)讀請求集R，寫請求集W，鎖機(jī)制C。

輸出：加鎖成功返回Success，否則返回Abort。

算法2RDMA解鎖算法

輸入：事務(wù)讀請求集R，寫請求集W，鎖機(jī)制C。

輸出：無。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)基于MIT開源的多算法分布式并發(fā)控制測試平臺Deneva[18]，引入了其對RDMA單邊和雙邊的支持，從而對本文算法性能進(jìn)行驗(yàn)證。Deneva中，事務(wù)首次訪問的節(jié)點(diǎn)作為協(xié)調(diào)者，按順序完成一系列遠(yuǎn)程或本地操作，并最終提交或回滾。消息隊(duì)列中的遠(yuǎn)程讀寫請求被消息發(fā)送線程封裝并通過TCP/IP發(fā)送至接收端。接收端工作線程輪詢工作隊(duì)列，完成本地讀寫，并向協(xié)調(diào)者返回處理結(jié)果。其中，數(shù)據(jù)遠(yuǎn)程讀寫是非阻塞的：等待遠(yuǎn)程讀寫時(shí)，協(xié)調(diào)節(jié)點(diǎn)暫存當(dāng)前事務(wù)狀態(tài)并繼續(xù)處理下一工作隊(duì)列元素，從而提高處理效率。與此不同，基于RDMA 的兩階段加鎖實(shí)現(xiàn)方法利用其與本地內(nèi)存存取媲美的高帶寬[6]，通過在Deneva開源代碼中將遠(yuǎn)程操作的消息發(fā)送和接收邏輯改為調(diào)用RNIC直接讀寫遠(yuǎn)端內(nèi)存，實(shí)現(xiàn)了第2.2.3 小節(jié)中描述的算法機(jī)制。為引入RDMA，系統(tǒng)初始化時(shí)首先在各節(jié)點(diǎn)線程間成對創(chuàng)建隊(duì)列對，分配注冊內(nèi)存并綁定至相應(yīng)RNIC。圖2展示了注冊內(nèi)存的結(jié)構(gòu)，包括數(shù)據(jù)區(qū)和臨時(shí)區(qū)。數(shù)據(jù)區(qū)存放索引、結(jié)構(gòu)如表1 的并發(fā)控制元數(shù)據(jù)和具體數(shù)據(jù)內(nèi)容，在作為被讀寫站點(diǎn)時(shí)使用；臨時(shí)區(qū)被分配給所在節(jié)點(diǎn)的各線程，用于暫存RDMA讀或CAS的返回結(jié)果，在作為讀寫發(fā)起站點(diǎn)時(shí)使用。一個(gè)典型的遠(yuǎn)端數(shù)據(jù)讀取中，事務(wù)首先將遠(yuǎn)端數(shù)據(jù)區(qū)中的對應(yīng)索引讀取到本地臨時(shí)區(qū)中，然后根據(jù)索引指向地址讀寫遠(yuǎn)端元數(shù)據(jù)進(jìn)行加鎖并發(fā)控制，加鎖成功后方可讀取遠(yuǎn)端數(shù)據(jù)內(nèi)容。

圖2 RDMA注冊內(nèi)存結(jié)構(gòu)Fig.2 Registered data structure for RDMA

性能測試使用YCSB。YCSB（Yahoo!cloud serving benchmark）是雅虎公司開源的數(shù)據(jù)庫服務(wù)器端壓力測試工具。它提供了可調(diào)試參數(shù)如寫操作比例、沖突率等，以進(jìn)行全面的評估。事務(wù)訪問服從Zipf 分布，即少量數(shù)據(jù)獲得大量訪問的長尾分布。分布參數(shù)Theta（又稱Skew Factor）在0 到1 之間，越接近1數(shù)據(jù)訪問沖突越大，用于測試系統(tǒng)在不同沖突率下的性能表現(xiàn)。實(shí)驗(yàn)基于4 臺配置RDMA 的集群，并按照1∶1 的比例分配客戶端和服務(wù)端。每個(gè)節(jié)點(diǎn)配備125 GB 內(nèi)存，2 個(gè)18 核的Intel Xeon Gold 5220 處理器，1 個(gè)RNIC 和ConnectX-5 InfiniBand MT27800。默認(rèn)每個(gè)服務(wù)端8個(gè)并行工作線程，每個(gè)YCSB事務(wù)10個(gè)讀或?qū)懻埱?。?shí)驗(yàn)對比第2章設(shè)計(jì)的基于RDMA原語的算法與Deneva中基于InfiniBand的TCP/IP的算法，以得出硬件本身的性能收益外算法帶來的優(yōu)勢。

3.2 實(shí)驗(yàn)結(jié)果及分析

3.2.1 算法性能比較

為了分析在不同負(fù)載下的表現(xiàn)，圖3 給出了NO WAIT 的四種不同實(shí)現(xiàn)：基于InfiniBand 的TCP/IP（IPoIB）、RDMA 雙邊（two-side）、RDMA 單邊讀寫鎖（M/S lock）和排他鎖（M lock），在寫事務(wù)比例為0.5的測試數(shù)據(jù)集下的吞吐量（單位：TPS）和回滾率隨沖突大小的變化情況。其中，單邊讀寫鎖在讀寫負(fù)載下實(shí)現(xiàn)了相對InfiniBand 上TCP/IP 最高5.3 倍（Theta=0.85）的吞吐提升。得益于繞開遠(yuǎn)端CPU 的特性，RDMA單邊實(shí)現(xiàn)總是優(yōu)于雙邊和IPoIB上的實(shí)現(xiàn)的：在相同沖突程度下帶來更高的吞吐量和更低的回滾率。類似的，RDMA 雙邊實(shí)現(xiàn)避免操作系統(tǒng)內(nèi)核并利用高速網(wǎng)絡(luò)，在不同沖突情況下均優(yōu)于IPoIB上的實(shí)現(xiàn)。然而，區(qū)分讀寫鎖和僅提供排他鎖的兩類單邊實(shí)現(xiàn)的相對優(yōu)劣卻并不絕對，而是跟負(fù)載有關(guān)。在低沖突負(fù)載下，單邊排他鎖相比讀寫鎖有更高的吞吐量。這是因?yàn)閱芜呑x寫鎖在提供更靈活多樣的加鎖機(jī)制的同時(shí)，引入了額外的往返通信開銷（參見第2.2.3小節(jié)算法1、算法2），針對讀集元素的加解鎖總是需要兩次往返（RDMA Read+CAS），而單邊排他鎖僅需要一次單邊通信（RDMA CAS 或Write）。負(fù)載沖突小時(shí)，區(qū)分讀寫鎖帶來的更高讀并發(fā)度所具有的好處不及額外通信開銷所帶來的劣勢，此時(shí)排他鎖算法表現(xiàn)更好。相對的，當(dāng)Theta>0.8，單邊排他鎖算法回滾率大于20%時(shí)，讀寫鎖算法因其更高的讀并發(fā)度而具有相對優(yōu)勢。

圖3 NO WAIT在讀寫數(shù)據(jù)集上的算法性能比較Fig.3 NO WAIT algorithm performance comparison on read-write dataset

為進(jìn)一步驗(yàn)證區(qū)分讀寫鎖算法的優(yōu)越性，圖4給出了以上四種實(shí)現(xiàn)在只讀事務(wù)上的吞吐量和回滾率。只讀負(fù)載的沖突大小對于區(qū)分讀寫鎖的單邊、雙邊和IPoIB 實(shí)現(xiàn)無顯著影響：并發(fā)讀總可以執(zhí)行，回滾率始終為0（為清晰呈現(xiàn)，圖4（b）僅列出單邊回滾率），吞吐量平穩(wěn)。此時(shí)始終有RDMA單邊讀寫鎖優(yōu)于雙邊，雙邊優(yōu)于TCP/IP。不同的是，盡管低沖突負(fù)載時(shí)單邊排他鎖算法依舊最優(yōu)，高沖突讀負(fù)載下的高回滾率使得其性能急速下降。在Theta>0.9 且回滾率大于40%時(shí)單位時(shí)間吞吐量甚至不及Infini-Band上的TCP/IP實(shí)現(xiàn)。

橫向比對圖3（a）和圖4（a）中相同算法的吞吐情況，可見IPoIB和雙邊實(shí)現(xiàn)在只讀負(fù)載下具有相對稍高的吞吐量，而單邊排他鎖和低沖突下的單邊讀寫鎖算法對于寫事務(wù)比例并不敏感，后者甚至性能有所下降。這是因?yàn)橹蛔x負(fù)載節(jié)省了寫回的通信開銷，而單邊讀寫鎖算法因?yàn)樽x相對寫更復(fù)雜，讀負(fù)載比例的增多而增大了復(fù)雜操作比例。

圖4 NO WAIT在只讀數(shù)據(jù)集上的算法性能比較Fig.4 NO WAIT algorithm performance comparison on read-only dataset

圖5 列出了WAIT DIE 在寫事務(wù)比例為0.5 時(shí)的性能評測結(jié)果。類似NO WAIT，幾乎總有單邊優(yōu)于雙邊，雙邊優(yōu)于TCP/IP。其中RDMA 操作依賴其高效性，減小了加鎖時(shí)長，因此在同一沖突水平下往往有更低的回滾率。由于維護(hù)加鎖事務(wù)時(shí)間戳數(shù)組的額外開銷，WAIT DIE 單邊讀寫鎖優(yōu)勢減弱，僅在沖突率極高（Theta>0.9）時(shí)略優(yōu)于單邊排他鎖算法。驗(yàn)證了盡管具有單次高效性，RDMA 單邊原語并不擅長實(shí)現(xiàn)復(fù)雜操作。注意到基于TCP/IP 的WAIT DIE 在沖突率高時(shí)吞吐量下降顯著，在Theta=0.85時(shí)單邊排他鎖實(shí)現(xiàn)了10.6 倍的吞吐量提升。類似NO WAIT，WAIT DIE讀寫鎖在高沖突只讀數(shù)據(jù)集上吞吐量穩(wěn)定，回滾率趨于0，相比排他鎖算法具有更顯著的相對優(yōu)勢，這里不再重復(fù)展示實(shí)驗(yàn)結(jié)果。

圖5 WAIT DIE算法性能比較Fig.5 WAIT DIE algorithm performance comparison

3.2.2 重試情況分析

第2.2.3小節(jié)加解鎖算法均涉及重試操作。重試操作可分為兩類：原子類重試和等待類重試。原子類重試指由于加解鎖過程中原子性被破壞引起的重試操作（算法1，第9 行；算法2，第5 行和第14 行；以及算法1第15行和算法2第10行可能的重讀），而等待類重試是對WAIT DIE算法中等待（WAIT）的具體實(shí)現(xiàn)：通過反復(fù)重試發(fā)送請求，直到加鎖成功或回滾（算法1，第18、25和第31行）。為了測量重試操作對上述算法性能的影響，表2分別統(tǒng)計(jì)了不同鎖機(jī)制的事務(wù)平均重試次數(shù)。由表可見，操作間原子性被破壞所引發(fā)的重試較少。如NO WAIT讀寫鎖機(jī)制下平均每個(gè)事務(wù)原子類重試不到0.2次，對性能影響較小。相比之下等待類重試次數(shù)較多，特別是WAIT DIE 讀寫鎖機(jī)制在高沖突Theta=0.95 時(shí)平均等待重試可達(dá)近12次，這進(jìn)一步解釋了其在圖5（a）中的不高吞吐量。

表2 事務(wù)平均重試次數(shù)統(tǒng)計(jì)Table 2 Number of retry in transaction

4 結(jié)束語

本文提出了基于RDMA的兩段鎖并發(fā)控制優(yōu)化技術(shù)。利用高帶寬、低延時(shí)等特性，本文對兩段鎖算法中加解鎖的實(shí)現(xiàn)進(jìn)行了重新設(shè)計(jì)與優(yōu)化，提出了單邊讀寫鎖和排他鎖這兩種加解鎖策略。利用這兩種策略，本文優(yōu)化并實(shí)現(xiàn)了兩種主流的兩段鎖算法（NO WAIT和WAIT DIE）。實(shí)驗(yàn)結(jié)果顯示，優(yōu)化后的算法相較于基于InfiniBand 上TCP/IP 協(xié)議的算法分別有最高5.3 倍和10.6 倍的性能提升。值得注意的是，通過調(diào)整測試負(fù)載中的事務(wù)沖突率，本文發(fā)現(xiàn)：在高沖突率下，采用單邊讀寫鎖策略時(shí)性能較優(yōu)；而在低沖突率下，采用排他鎖策略性能較優(yōu)。這一現(xiàn)象在只讀數(shù)據(jù)集上更顯著。其中WAIT DIE 讀寫鎖的優(yōu)勢因?qū)崿F(xiàn)復(fù)雜單邊操作而有所減弱。因此，基于負(fù)載中沖突率的高低和讀事務(wù)比例，動態(tài)調(diào)整算法的加解鎖策略，從而適應(yīng)于不同負(fù)載的需要，是未來的一個(gè)研究工作。