連薛超,劉 維,王清帥,張 蓉

（1.華東師范大學 數(shù)據(jù)科學與工程學院,上海 200062;2.工業(yè)和信息化部電子第五研究所,廣州 511300）

0 引 言

從NoSQL到NewSQL[1],分布式數(shù)據(jù)庫雖然取得了長足的進展,在解決事務一致性和可擴展性上都有很大的進步,但是還存在著一些尚未解決的問題,當前分布式數(shù)據(jù)庫的吞吐主要被3 個因素限制:①消息傳遞的額外開支;② 網(wǎng)絡的帶寬;③資源競爭[2].

遠程直接數(shù)據(jù)存取(remote direct memory access,RDMA)技術可以緩解消息傳遞的額外開支和網(wǎng)絡的帶寬[3].但是,RDMA 技術尚未被大規(guī)模運用.在一般的分布式場景下,消息延遲比單機場景的延遲要長得多,進一步增大了沖突的概率.例如,以太網(wǎng)中單次小消息傳遞的延遲約為 35 μs,不考慮磁盤和網(wǎng)絡延遲的情況下,事務的延遲為 10～ 60 μs[4-5],網(wǎng)絡延遲已經(jīng)成了短事務延遲的主要瓶頸,而短事務又是聯(lián)機事務處理(online transactional processing,OLTP)的主要類型之一.長消息延遲惡化了分布式數(shù)據(jù)庫的沖突,已經(jīng)有研究指出,事務的沖突概率和訪問單個記錄的延遲成指數(shù)級關系[2].一方面,當負載的沖突很大的時候,系統(tǒng)中大量的事務最終都會回滾,在無效的操作上浪費了大量的資源.另一方面,由于大量事務都在競爭同一數(shù)據(jù)項,花費在等待資源上的時間也會變長.兩個因素共同作用,導致整個系統(tǒng)在高沖突負載下較差的性能.

對于目前流行的無共享架構(gòu)而言,在邏輯上,往往有一個無狀態(tài)的事務組件層用于計算,另一個數(shù)據(jù)組件層用于存儲數(shù)據(jù)和事務狀態(tài)[6],如TiDB[7],CockroachDB[8],Spanner[9],FoundationDB[10]等.這樣的架構(gòu),在高沖突的場景下,可能由于檢測沖突的時間太長導致高沖突,進而導致低吞吐.例如,對于樂觀的并發(fā)控制協(xié)議Percolator[11]來說,事務在提交和讀取數(shù)據(jù)時需要在存儲層檢測沖突,而在那之前事務可能已經(jīng)進行了多次網(wǎng)絡 I/O(input/output),這樣就造成,實際發(fā)生沖突的時間和檢測到?jīng)_突的時間被拉長.

為了解決這個問題,本文基于 FoundationDB 的事務處理架構(gòu),設計了一套面向高沖突的事務處理系統(tǒng)原型,通過定期從存儲事務狀態(tài)的節(jié)點獲取沖突信息,在發(fā)生高沖突現(xiàn)象時,收集高沖突數(shù)據(jù)集.監(jiān)視節(jié)點會根據(jù)高沖突數(shù)據(jù)集改變整個集群的事務策略,同時選定一個計算節(jié)點作為后續(xù)處理高沖突事務的計算節(jié)點,實現(xiàn)了對沖突的有效檢測.在高沖突的事務策略中,采用了類似MOCC(mostly-optimistic concurrency control)[12]的樂觀事務模型結(jié)合悲觀事務模型的方式進行處理,可以提前檢測到事務的沖突,縮短了浪費在消息延遲上的時間.同時由于高沖突事務都被放在了一個節(jié)點,本文采用了更激進的緩存策略來改善讀操作的延遲.實驗證明,本文所提出的這套框架可以有效緩解計算節(jié)點無狀態(tài)的分布式數(shù)據(jù)庫系統(tǒng)在高沖突情況下的性能問題.

1 相關工作

FoundationDB[10]是一款開源的事務鍵值存儲系統(tǒng),它采用了樂觀的并發(fā)控制協(xié)議,是 Apple,Snowflake 等公司云基礎架構(gòu)的重要組成部分.和很多無共享架構(gòu)的數(shù)據(jù)庫一樣,因為計算節(jié)點無狀態(tài),所以在高沖突的情況下,吞吐和延遲會受到更多的影響.事務模型分為樂觀的事務模型和悲觀的事務模型:樂觀的事務模型在獲取資源前無需獲取鎖,通過事務提交之前的驗證來保證事務隔離級別的正確性;悲觀的事務模型在獲取資源前需要獲取鎖,一般通過二階段鎖(two-phase locking,2PL)等并發(fā)控制協(xié)議來保證事務隔離級別的正確性.其他無共享架構(gòu)的數(shù)據(jù)庫,有些采用了樂觀的事務模型,如v3.08 之前的TiDB[7](TiDB 在v3.08 之后也支持了悲觀的事務模型)、CockroachDB[8];有些則采用了悲觀的事務模型,如 Spanner[9]等.這些架構(gòu)的數(shù)據(jù)庫都有著類似的問題,面對高沖突負載,無狀態(tài)的計算節(jié)點,導致沖突檢測的鏈路過長,從而造成更差的性能.

在單機數(shù)據(jù)庫中,已經(jīng)有很多的方法嘗試解決高沖突的問題.對于樂觀的事務處理來說,MOCC[12]針對熱點鍵值采用預先加鎖的方式避免一些不必要的回滾,為了解決加鎖時可能導致的死鎖問題,使用了一種非2PL 的加鎖方式來按照鍵值大小獲取鎖,不符合加鎖順序的鎖就釋放掉.對于悲觀的事務處理,Bamboo[13]通過提前釋放鎖來縮短持有鎖的時間,為了解決讀取臟數(shù)據(jù)可能會導致的級聯(lián)回滾問題,Bamboo 記錄了讀臟數(shù)據(jù)時的依賴信息.IC3[14]也是一種悲觀事務處理的協(xié)議,它對事務進行靜態(tài)分析,將事務分割為原子的子事務,每一個子事務完成后,子事務的更新就變得可見,通過這種方式讓事務獲得了更多的并發(fā)度.

在分布式數(shù)據(jù)庫的事務處理中,也有不少試圖解決高沖突問題的方法.Calvin[15]采用了確定性并發(fā)控制的方式從源頭上消除了沖突,為鎖請求進行了一個全局的定序.DLV(distributed lock violation)[16]對二階段鎖加二階段提交(2PL+two-phase commit,2PC)的分布式事務,采用了類似于 Bamboo的提前釋放鎖的做法,將這一點應用在了分布式的環(huán)境下,并對釋放鎖的時機進行了更細的區(qū)分.Chiller[3]則是一個以事務分區(qū)的方式來解決2PL+2PC 的高沖突問題的架構(gòu),對事務日志進行靜態(tài)分析后,對事務內(nèi)的一部分操作進行重排序,通過這樣的分區(qū)工具來重新分區(qū),讓涉及高沖突記錄的鎖被放在同一個分區(qū)內(nèi),從而使之可以提前釋放.

2 高沖突情況下無共享架構(gòu)數(shù)據(jù)庫面臨的問題

本章以TiDB[7]為例介紹當前無共享架構(gòu)數(shù)據(jù)庫在高沖突情況下普遍面臨的問題.TiDB 的架構(gòu)分為計算節(jié)點 TiDB 和存儲節(jié)點 TiKV,其并發(fā)控制協(xié)議是基于 Percolator[11]的.Percolator 的事務分為執(zhí)行和提交兩個階段: 在執(zhí)行階段,所有的寫入都保存在本地;在提交階段,先進行預寫入,將之前本地寫入的記錄所對應的鎖寫入存儲,并選擇一個寫入操作作為主鍵,用來保證原子性,所有的預寫入都完成以后,再對主鍵進行提交.沖突的檢測僅發(fā)生在事務執(zhí)行階段中的讀取操作和事務提交階段的預寫入操作,s是事務的開始時間戳,c是事務的結(jié)束時間戳.

當進行讀取操作時,事務會檢查 TiKV 上是否已經(jīng)寫入了[0,s]的鎖,如果存在這樣的鎖,就會嘗試清除這個鎖;如果清除失敗,事務就會回滾.

當進行預寫入操作時,事務會檢查 TiKV 上是否已經(jīng)存在c[s,+∞)的提交數(shù)據(jù)以及是否已經(jīng)存在任意時間戳寫入,即c或者s屬于[0,+∞)的鎖.

然而在發(fā)生沖突之前可能已經(jīng)發(fā)生了多次遠程過程調(diào)用(remote procedure call,RPC)(每訪問一次 TiKV 都是一次 RPC),而這么多 RPC 的時延是不可忽略的,也就是說,事務從執(zhí)行到檢測沖突的鏈路是很長的.

如圖1 所示,假設有兩個事務分別為事務1 和事務2,它們可能在同一個TiDB 節(jié)點,也可能不在同一個 TiDB 節(jié)點,這兩個事務均會讀取和寫入一個相同的記錄x.事務1 已經(jīng)完成了執(zhí)行階段和預寫入操作,正在執(zhí)行提交操作;事務2 已經(jīng)完成了執(zhí)行階段,正在進行預寫入操作,但是在預寫入時,它會發(fā)現(xiàn)x這個記錄已經(jīng)被事務1 上鎖,由于發(fā)生了沖突,事務2 就會回滾.事務2 在回滾之前,該事務已經(jīng)進行了兩輪 RPC,一輪是讀取x這個記錄,一輪是預寫入.

圖1 TiDB 的事務沖突示例Fig.1 Example of TiDB transaction conflict

每個事務讀取的記錄數(shù)量有限,可以預料到的是,在高沖突和讀取更多記錄的情況下,會有更多的事務受到影響,更多的資源被浪費.如果有辦法能夠提前在計算層就檢測到?jīng)_突,根據(jù)檢測到的沖突,提前對會回滾的事務進行回滾,就可以有效降低時延并提高系統(tǒng)的吞吐.

3 高沖突處理架構(gòu)

本文設計的高沖突處理架構(gòu)由兩部分組成: 第一部分是高沖突檢測,負責檢測高沖突并啟動高沖突處理;第二部分是高沖突處理,負責對高沖突事務的處理.這個架構(gòu)在本文開發(fā)的原型系統(tǒng)中進行驗證,下面按照原型系統(tǒng)的架構(gòu)、高沖突檢測、高沖突處理策略3 個小節(jié)來介紹本文的工作.

3.1 原型系統(tǒng)的架構(gòu)

本文基于 FoundationDB[10]實現(xiàn)了一個高沖突處理架構(gòu)的原型系統(tǒng).FoundationDB 在屬于無共享架構(gòu)的前提下有著更小的代碼量,模塊復雜度低,便于進行技術驗證和原型系統(tǒng)開發(fā).在實現(xiàn)上,使用了FoundationDB 的協(xié)程框架flow 和網(wǎng)絡通信框架fdbrpc,參考了 FoundationDB 的并發(fā)控制協(xié)議和整體架構(gòu),因為本文主要關注的是分布式數(shù)據(jù)庫的高沖突問題,所以去掉了其中的持久化和高可用部分,這一點和文獻[17]類似.原型系統(tǒng)架構(gòu)如圖2 所示.整體架構(gòu)分為兩層: 第一層是計算層,其中的事務處理節(jié)點負責與客戶端交互.沖突檢測節(jié)點按照訪問的鍵范圍進行分區(qū),負責檢測事務的沖突.第二層是存儲層,其中的存儲節(jié)點也按照訪問的鍵范圍進行分區(qū),負責處理讀請求.控制節(jié)點負責時間戳的分發(fā),集群的初始化,控制事務處理策略等任務.本文的主要貢獻在圖2 中紅色區(qū)域的兩個模塊,其余部分主要是參考FoundationDB 而來,為了減少不必要的工作量,對FoundationDB 的設計進行了一定的簡化.

當客戶端發(fā)起一個請求以后,客戶端會從控制節(jié)點或者本地緩存里獲取集群信息,選擇一個事務處理節(jié)點作為交互的節(jié)點,發(fā)送事務 ID 和參數(shù).事務處理節(jié)點收到事務 ID 和參數(shù)以后,就啟動一個協(xié)程服務這個事務,這樣一個事務的生命周期就開始了,每個事務從開始到提交的生命周期如下所示,并與圖2 對應.

(1)事務處理節(jié)點從控制節(jié)點處獲取讀時間戳.

(2)執(zhí)行事務: ①讀操作根據(jù)讀時間戳從所對應的存儲節(jié)點讀取數(shù)據(jù);② 寫操作暫時先保存在本地的緩沖區(qū)中.

(3)提交事務: ①事務處理節(jié)點從控制節(jié)點處獲取寫時間戳;② 將事務的讀寫集發(fā)送到?jīng)_突檢測節(jié)點處檢測沖突,如果有其他事務修改了本事務讀取的值,那么就會回滾,如果沒有回滾,就會更新沖突檢測節(jié)點處鍵值的寫時間戳為當前事務的寫時間戳;③確認所有的沖突檢測節(jié)點均已提交以后,發(fā)送當前事務的日志給對應存儲節(jié)點,等待存儲節(jié)點完成日志的應用后,事務提交.

FoundationDB 的并發(fā)控制協(xié)議還要求,存儲節(jié)點和日志節(jié)點嚴格按照時間戳順序處理事務,前一個事務沒有完成,后一個事務就不能啟動,因此 FoundationDB 只有讀寫沖突而沒有寫寫沖突.本文也參照 FoundationDB 實現(xiàn)了類似的機制.

3.2 高沖突檢測

沖突檢測節(jié)點使用跳表來保存鍵范圍到寫時間戳的映射.用跳表的上層節(jié)點會保存下層節(jié)點寫時間戳的最大值,用這樣的方式,可以更快地檢測沖突.同時,為了減少不必要的網(wǎng)絡 I/O,每次的事務沖突檢測都是用批的方式完成.

高沖突檢測包含了兩個問題: 第一個問題是檢測并發(fā)現(xiàn)系統(tǒng)當前處于高沖突狀態(tài);第二個問題是收集高沖突的數(shù)據(jù)項集合.對于第一個問題,檢測事務的回滾率即可,事務的回滾率可以直接從事務處理節(jié)點得到,但是事務處理節(jié)點無法得到高沖突的數(shù)據(jù)項集合,因而需要從沖突檢測節(jié)點處檢測高沖突并在一小段時間內(nèi)收集高沖突的數(shù)據(jù)項集合.對于沖突檢測節(jié)點來說,時刻維護一個高沖突的數(shù)據(jù)項集合,對內(nèi)存和中央處理器(central processing unit,CPU)資源的消耗無疑都比較高,因此,本文選擇了和 E-Store[17]類似的做法,只在回滾率達到一定閾值時,才會啟動記錄高沖突的數(shù)據(jù)項.為了防止假陽性(即實際上只有很少的事務),本文也同時限制了事務負載載荷的下限閾值.

在啟動高沖突檢測以后,沖突檢測節(jié)點內(nèi)的跳表就會在進行檢測沖突時發(fā)送當前產(chǎn)生沖突的鍵給后臺協(xié)程,后臺協(xié)程在收集完畢以后,取占據(jù)訪問熱度一定比例的鍵作為高沖突數(shù)據(jù)項集合,即

式中:Ak表示采樣時間內(nèi)某個鍵的訪問頻數(shù);K表示采樣時間內(nèi)所有鍵的集合;H表示高沖突數(shù)據(jù)項的集合.本文在根據(jù)采樣時間內(nèi)訪問頻數(shù)排序的鍵中選擇排序靠前的鍵,使得H的訪問頻數(shù)占數(shù)據(jù)庫總訪問頻數(shù)的比例超過閾值λ.確定H的方式為: 先將所有的鍵按照采樣時間內(nèi)訪問頻數(shù)從高到低進行排序,再從高到低依次選擇鍵加入H,直到H中鍵的訪問頻數(shù)之和占所有鍵訪問頻數(shù)之和的比例大于或等于λ.本文設置λ為采樣時間內(nèi)的回滾率P與觸發(fā)收集高沖突數(shù)據(jù)項回滾率的閾值θ的差值,即λP-θ.這樣設置λ的原因是: 第一,隨著P的增大,λ也會增大,這樣在沖突更高時,可以確保將高沖突數(shù)據(jù)項都收集到H中;第二,P減去θ以后,可以避免H中包含一些較低沖突的鍵,減少對非高沖突負載的影響.通過設置θ,系統(tǒng)可以在有效處理高沖突負載和避免對非高沖突負載影響之間取得一個平衡,經(jīng)過測試,本文將θ設置為0.05.

沖突檢測節(jié)點會每隔一段時間發(fā)送一個高沖突狀態(tài)請求給控制節(jié)點,里面包含了當前的高沖突數(shù)據(jù)項集合,直到高沖突現(xiàn)象被消除.為了避免不必要的重復發(fā)送,本文設計了一個簡單的機制,比較每次高沖突數(shù)據(jù)項集合的數(shù)量變化,如果數(shù)量變化大于一定的閾值,該機制就會發(fā)送新的高沖突數(shù)據(jù)項集合給控制節(jié)點;否則,就不發(fā)送.

3.3 高沖突處理策略

整個系統(tǒng)的并發(fā)控制會有兩種策略: 一個是高沖突處理策略;一個是正常策略.當使用高沖突處理策略時,控制節(jié)點會隨機選取一個事務處理節(jié)點,作為高沖突處理節(jié)點,控制節(jié)點隨后將所有的高沖突事務都交給這個高沖突處理節(jié)點處理,這樣就可以在這個事務處理節(jié)點進行預先加鎖和本地緩存等操作.

如圖3 所示,控制節(jié)點在收到?jīng)_突檢測節(jié)點發(fā)來的高沖突狀態(tài)請求以后,會對內(nèi)部的全局變量S加 1,系統(tǒng)通過S來識別當前的并發(fā)控制是高沖突處理策略還是正常策略.在對內(nèi)部的S加1 以后,控制節(jié)點會向所有的事務處理節(jié)點請求更新事務處理節(jié)點處的S,控制節(jié)點完成這個過程以后,本次的狀態(tài)就改變完畢.客戶端也會維護一個S,當客戶端向事務處理節(jié)點發(fā)送請求時,客戶端的S可能已經(jīng)過期,這時就需要從控制節(jié)點處更新S并獲取可能需要的高沖突數(shù)據(jù)項集合.從高沖突狀態(tài)變回低沖突狀態(tài)也是類似的,操作變?yōu)閺氖聞仗幚砉?jié)點發(fā)送請求,因為事務處理節(jié)點可以知道當前有多少個事務命中了高沖突數(shù)據(jù)項集合,當事務命中高沖突數(shù)據(jù)項集合的數(shù)量低于一定閾值以后,就可以向控制節(jié)點發(fā)送請求,改變系統(tǒng)的并發(fā)控制策略.

圖3 狀態(tài)變化Fig.3 State transition diagram

3.3.1 預先加鎖

事務處理節(jié)點會區(qū)分高沖突事務和普通事務,對于高沖突事務,在正常的執(zhí)行流程之外,還額外增加了預處理的流程.預處理的流程和 MOCC[12]類似,都是提前加鎖,讀鎖在事務執(zhí)行階段就獲取,而寫鎖要等到提交階段才會獲取.第一個不同之處是,本文的設計,只允許寫者等待讀者,而不允許讀者等待寫者.這一點是因為,當事務1 讀到了事務2 正在獲取寫鎖的記錄時,事務1 的讀時間戳一定比事務2 的寫時間戳要小,那么事務1 在后續(xù)沖突檢測節(jié)點驗證時就一定會回滾,因此無須等待事務1 完成.第二個不同之處是,本文的設計還限制了同一時間允許獲取同一記錄讀鎖的數(shù)量,以免產(chǎn)生鎖顛簸的現(xiàn)象,這一點和 MySQL 里的批最大依賴集優(yōu)先算法[18]類似,如算法1 所示.

第三個不同之處是,MOCC[12]為了解決死鎖的問題,會在加鎖時,直接釋放掉不符合加鎖順序的鎖.在本文的設計里,僅僅在獲取寫鎖時才會觸發(fā)這個機制,讀和讀之間是不會發(fā)生沖突的,讀和寫會發(fā)生的沖突,如算法2 所示.由于加鎖機制不允許讀者等待寫者,沖突的依賴只可能是寫指向讀的.獲取新的讀鎖不會引發(fā)死鎖,可以在獲取讀鎖時,保留不符合加鎖順序的鎖.

3.3.2 本地緩存

除了預先加鎖之外,高沖突處理節(jié)點還可以維護一個本地緩存,在事務處理節(jié)點緩存所有高沖突數(shù)據(jù)項.為了便于實現(xiàn),本文采用了寫穿透策略,即同步寫入遠程存儲和本地緩存,當事務提交時,不僅需要提交到遠程存儲,而且需要寫入本地緩存.并發(fā)控制策略變換前后可能會導致最近的更新寫入了舊的本地緩存中,為了保證寫入和讀取本地緩存在并發(fā)控制策略變換前后的緩存一致性,本文還在本地緩存和事務的數(shù)據(jù)結(jié)構(gòu)中也維護了S,分別用于標記本地緩存創(chuàng)建時的S和每個事務在開始執(zhí)行前記錄當前事務處理節(jié)點的S.當高沖突處理節(jié)點的事務在嘗試讀取本地緩存時,可能會發(fā)現(xiàn)自己的S和本地緩存的S不一致,那么就不會讀取本地緩存中的數(shù)據(jù).同時,對于已經(jīng)讀取了之前本地緩存,但尚未完成執(zhí)行或提交的事務,高沖突處理節(jié)點會在提交時檢查該事務讀取本地緩存的S,如果和本地緩存記錄的S不一致,事務就會回滾.

3.3.3 客戶端路由策略

客戶端在將事務路由到不同的處理節(jié)點時,會使用兩種不同的路由策略.第一種路由策略是非高沖突的路由策略,在這種路由策略下,客戶端在發(fā)送事務時按照均勻分布隨機將事務發(fā)送給一個事務處理節(jié)點.第二種路由策略是高沖突路由策略,當客戶端使用高沖突路由策略時,會根據(jù)事務 ID 和事務的輸入來確定事務是否可能訪問高沖突數(shù)據(jù)項,如果有可能訪問到,那么客戶端就發(fā)送一個高沖突事務請求給所對應的高沖突處理節(jié)點,非高沖突事務則會隨機均勻發(fā)送到事務處理節(jié)點中.為了負載均衡,客戶端還會減少發(fā)送到高沖突事務處理節(jié)點的非高沖突事務.需要注意的是,當前客戶端確定一個事務是否為高沖突事務的方法是較為簡單的,即根據(jù)事務的參數(shù)來計算訪問集,判斷這些鍵是否屬于高沖突的數(shù)據(jù)項集合,進而判斷該事務是否屬于高沖突事務.對于一些無法通過計算來得到訪問集的事務,目前還無法處理,未來可以考慮通過對事務日志進行機器學習等方式來計算事務的訪問集.

4 實驗分析

4.1 集群環(huán)境及測試負載

(1)集群環(huán)境.本系統(tǒng)部署在 6 個節(jié)點上,其中 3 個節(jié)點的配置為 4vCPU 16 GB 的內(nèi)存,CPU型號為 Intel Xeon Platinum(Cooper Lake)8369;另外 3 個節(jié)點的配置為 4vCPU 8 GB,CPU 型號為Intel Xeon(Ice Lake)Platinum 8369B.3 個存儲節(jié)點分別部署在 3個4vCPU 16 GB 節(jié)點上,3 個沖突檢測節(jié)點均部署在 1個4vCPU 8 GB 的節(jié)點上,3 個事務處理節(jié)點和 1 個控制節(jié)點均部署在 1 個4vCPU 8 GB 的節(jié)點上,客戶端部署在 1個4vCPU 8 GB 節(jié)點上.集群環(huán)境將存儲節(jié)點和事務處理節(jié)點分開,以模擬無共享架構(gòu)數(shù)據(jù)庫里計算節(jié)點到存儲節(jié)點的網(wǎng)絡開銷.為了模擬無共享架構(gòu)分布式數(shù)據(jù)庫沖突檢測鏈路過長的問題,將事務處理節(jié)點和沖突檢測節(jié)點也部署在不同的機器上.為了避免客戶端對系統(tǒng)造成影響,客戶端被單獨部署在一個機器上.

(2)測試負載.本實驗的測試負載為The Yahoo! Cloud Serving Benchmark(YCSB)[19],YCSB 是一套由互聯(lián)網(wǎng)公司開發(fā)的模擬大規(guī)模服務的負載,本文采用YCSB 的理由是YCSB 事務結(jié)構(gòu)簡單,可以更直接地觀測高沖突事務對系統(tǒng)的影響,其他事務負載,如TPC-C,可能會有更多復雜因素(如算子的執(zhí)行效率等)影響實驗的結(jié)果,給解釋實驗現(xiàn)象與沖突處理方案的關系造成困難.本文實現(xiàn)了YCSB 的評測標準,為了滿足測試高沖突負載的需求,本文對負載進行了改造,在實驗里所使用的事務負載包含10 條結(jié)構(gòu)化查詢語句(structured query language,SQL),每條SQL 語句有均等的概率成為一個簡單的讀操作或者更新操作,更新操作會更新對應鍵的值為相同長度的新值,所有 SQL 語句訪問的記錄均按照相同的分布產(chǎn)生.實驗加載了 50 萬條數(shù)據(jù),每條數(shù)據(jù)包含 10 個列,每個列的長度為1 000 個字節(jié).沖突檢測節(jié)點和存儲節(jié)點均按照鍵范圍均勻分割所有的鍵.本文通過改變負載的偏斜來模擬高沖突負載,采用Zipf 分布來模擬數(shù)據(jù)的偏斜,Zipf 參數(shù)越大,負載的沖突強度就越大.

4.2 高沖突處理策略的有效性

本節(jié)通過實驗檢驗高沖突處理策略的有效性,YCSB 負載的Zipf 參數(shù)從0.50 到1.05 之間變化,實驗結(jié)果如圖4 所示,所有的實驗數(shù)據(jù)為負載穩(wěn)定后1 min 的平均值.一般來說,Zipf 參數(shù)大于0.70 就可以被認為是高沖突的負載.Zipf 參數(shù)大于0.70 的實驗結(jié)果顯示本文設計的高沖突處理策略對吞吐率都有一定的提升,當Zipf 參數(shù)為1.05 時,吞吐相對基線的比例最多提升了84%;當Zipf 參數(shù)小于等于0.70 時,啟用了高沖突處理策略的實驗組和基線的實驗組相比則幾乎沒有差別.

圖4 高沖突處理策略的有效性Fig.4 High-contention-strategy effectiveness

對實驗結(jié)果進一步分析,可以發(fā)現(xiàn),預先加鎖對吞吐的提升有一個先升后降的趨勢,大約當Zipf 參數(shù)為0.90 時,達到峰值,這一現(xiàn)象是由于目前將所有的高沖突事務都交給一個事務處理節(jié)點處理,隨著沖突的升高,高沖突事務的量也隨之增大.可能由于沖突的不斷增強,導致高沖突事務處理節(jié)點成為新的瓶頸.本地緩存對吞吐的提升則是在Zipf 參數(shù)為 0.90 時達到低谷,隨后又隨著沖突的升高而增大.這個低谷的出現(xiàn)可能是由于預先加鎖會提前回滾掉一些事務,這些提前被回滾的事務就會執(zhí)行更少的讀操作,隨著預先加鎖效果的提升,提前回滾的事務的量也會增大,這些提前被回滾的事務會執(zhí)行更少的讀操作,那么由于本地緩存帶來的性能提升就會逐漸降低.當Zipf 參數(shù)大于0.90 時,隨著 Zipf 參數(shù)的增大,高沖突事務的量也不斷增大,盡管預先加鎖回滾了一些事務,仍然有更多事務的讀操作需要經(jīng)過本地緩存讀取,促進本地緩存的性能也隨之提升.

4.3 高沖突檢測的有效性

為了檢驗高沖突檢測的有效性,本文設計了本節(jié)實驗來驗證高沖突檢測模塊的有效性.首先在0 至20 s 執(zhí)行的均勻分布負載,然后在20 至40 s 執(zhí)行 Zipf 參數(shù)為0.99 的高沖突負載,最后在40 至60 s 執(zhí)行均勻分布負載,實驗結(jié)果如圖5 所示.

圖5 高沖突檢測的有效性Fig.5 High-contention-detection effectiveness

對實驗結(jié)果進行分析,可以發(fā)現(xiàn),在第20 秒加入了高沖突負載以后,如果不考慮第27 秒出現(xiàn)的異常(這一異常應該是由正常的網(wǎng)絡抖動和協(xié)程的不確定性導致的,3 種對比方法都會出現(xiàn)類似的抖動),對于預先加鎖來說,在第23 秒時就已經(jīng)獲得了比基線更好的吞吐,在第26 秒左右達到約為2 400 TPS的穩(wěn)定吞吐,比基線高約20%.如果額外開啟了本地緩存,在第24 秒時取得了比基線更好的吞吐,同時在第 27 秒左右達到了約為2 900 TPS 的穩(wěn)定吞吐,比基線高約45%.因此,高沖突策略從檢測沖突到生效的時延為3～ 4 s,而達到穩(wěn)定吞吐所需的時間為6～ 7 s.這說明,本文設計的高沖突檢測模塊,可以在較短的時間內(nèi)檢測出沖突,并啟動高沖突策略.

4.4 預先加鎖對回滾事務延遲的影響

在4.3 節(jié)中,預先加鎖的原理是提前回滾掉一些可能會產(chǎn)生沖突的事務,進而達到提高吞吐的效果.本節(jié)通過實驗驗證這一結(jié)論,YCSB的Zipf 參數(shù)在 0.50到1.05 之間變化,統(tǒng)計回滾事務從開始到執(zhí)行失敗的平均延遲,實驗結(jié)果如圖6 所示.

圖6 預先加鎖對回滾事務延遲的影響Fig.6 Effects of pre-locking on abort transaction latency

可以發(fā)現(xiàn)當Zipf 參數(shù)大于等于0.80 時,回滾事務的延遲都有一定的下降,延遲降低最大的值是24%,預先加鎖的吞吐相比基線的吞吐更好,這說明了預先加鎖策略可以有效縮短回滾事務的延遲,進而增大系統(tǒng)整體的吞吐.

4.5 本地緩存對讀操作延遲的影響

本節(jié)實驗在 Zipf 參數(shù)為 0.70 到1.05 的條件下進行,分別統(tǒng)計穩(wěn)定以后單個讀操作通過 RPC 返回的延遲和通過本地緩存返回的延遲,實驗結(jié)果如圖7 所示.當Zipf 參數(shù)大于等于0.85 時,本地緩存讀的延遲均在通過RPC 返回延遲的12%以內(nèi),這一點說明了本地緩存可以有效縮短讀操作的延遲.同時,如圖4 所示,和單純的預先加鎖相比,本地緩存對于系統(tǒng)的吞吐有一定提升,這說明了本地緩存可以縮短高沖突數(shù)據(jù)項的延遲,進而提升系統(tǒng)的吞吐.當Zipf 參數(shù)為0.70 和0.80 時,出現(xiàn)了一些延遲很高的異常點,使得本地緩存讀的延遲相較于遠程讀并無明顯優(yōu)勢,這一現(xiàn)象應該是由于當Zipf 參數(shù)較小時,沖突強度不大,大量算力用于執(zhí)行非高沖突事務,導致對本地緩存的更新操作無法及時同步,進而導致本地緩存的讀操作被阻塞.

圖7 本地緩存對讀操作延遲的影響Fig.7 Local cache effect on read operation latency

5 結(jié) 語

本文提出了無共享架構(gòu)數(shù)據(jù)庫由于沖突檢測鏈路過長在高沖突負載下可能會成為系統(tǒng)瓶頸的問題,針對這一問題,設計并實現(xiàn)了一套沖突檢測與高沖突處理的框架,針對分布式數(shù)據(jù)庫在高沖突負載下可能出現(xiàn)的性能瓶頸,本文提出了包含兩個高沖突處理的策略: 一是用預先加鎖來提前對一些高沖突事務進行回滾,從而縮短了沖突檢測鏈路的長度;二是用本地緩存來縮短高沖突數(shù)據(jù)項的讀操作延遲,避免了高沖突數(shù)據(jù)項頻繁RPC 對性能的影響.為了檢測沖突,本文設計了高沖突檢測模塊,可以快速發(fā)現(xiàn)沖突并應用高沖突處理策略.在策略上的主要創(chuàng)新在于,首次將MOCC 的這一套預先加鎖方案應用于分布式數(shù)據(jù)庫領域,適配了原型系統(tǒng)的并發(fā)控制協(xié)議,并加入了本地緩存等策略.通過實驗證明,本文所提出的高沖突處理原型系統(tǒng)架構(gòu),可以有效改善高沖突負載下系統(tǒng)的性能.

本文工作還存在一些尚未探討的問題,如選取事務處理節(jié)點時是否可以考慮負載均衡以達到更好的效果.在分布式數(shù)據(jù)庫領域,負載均衡一直是一個很熱的研究話題,大量研究工作試圖在系統(tǒng)運行過程中完成實時調(diào)度.本文的處理方法可以和現(xiàn)有的負載均衡技術相結(jié)合,達到更好的效果.又如當選擇高沖突處理節(jié)點時,僅選擇了一個事務處理節(jié)點,該節(jié)點可能就會成為新的瓶頸.將高沖突數(shù)據(jù)項分散到多個事務處理節(jié)點,可以改善系統(tǒng)的可擴展性,隨之而來的分布式事務開銷也是不可忽略的,這就需要在分布式事務和負載均衡之間取得一個平衡,很多工作都是針對這一問題展開的,本文的處理方法可以和現(xiàn)有的相關工作結(jié)合,以達到更好的效果.