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

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

0 引 言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)事務(wù)處理節(jié)點(diǎn)從控制節(jié)點(diǎn)處獲取讀時(shí)間戳.

(2)執(zhí)行事務(wù): ①讀操作根據(jù)讀時(shí)間戳從所對(duì)應(yīng)的存儲(chǔ)節(jié)點(diǎn)讀取數(shù)據(jù);② 寫(xiě)操作暫時(shí)先保存在本地的緩沖區(qū)中.

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

FoundationDB 的并發(fā)控制協(xié)議還要求,存儲(chǔ)節(jié)點(diǎn)和日志節(jié)點(diǎn)嚴(yán)格按照時(shí)間戳順序處理事務(wù),前一個(gè)事務(wù)沒(méi)有完成,后一個(gè)事務(wù)就不能啟動(dòng),因此 FoundationDB 只有讀寫(xiě)沖突而沒(méi)有寫(xiě)寫(xiě)沖突.本文也參照 FoundationDB 實(shí)現(xiàn)了類似的機(jī)制.

3.2 高沖突檢測(cè)

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

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

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

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

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

3.3 高沖突處理策略

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

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

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

3.3.1 預(yù)先加鎖

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

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

3.3.2 本地緩存

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

3.3.3 客戶端路由策略

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

4 實(shí)驗(yàn)分析

4.1 集群環(huán)境及測(cè)試負(fù)載

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

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

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

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

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

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

4.3 高沖突檢測(cè)的有效性

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

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

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

4.4 預(yù)先加鎖對(duì)回滾事務(wù)延遲的影響

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

圖6 預(yù)先加鎖對(duì)回滾事務(wù)延遲的影響Fig.6 Effects of pre-locking on abort transaction latency

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

4.5 本地緩存對(duì)讀操作延遲的影響

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

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

5 結(jié) 語(yǔ)

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

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