劉文欣 蔡鵬

摘要：大數(shù)據(jù)時代，存儲計(jì)算架構(gòu)分離的單寫多讀場景已無法滿足海量數(shù)據(jù)的高效讀寫需求;另一方面， 多個計(jì)算節(jié)點(diǎn)同時提供寫服務(wù)還會引起計(jì)算節(jié)點(diǎn)間的緩存不一致.已有的研究采用全局有序的事務(wù)日志 來進(jìn)行沖突檢測，并通過廣播和回放事務(wù)日志維護(hù)整個系統(tǒng)的數(shù)據(jù)一致性.但該類方案由于是在每個寫節(jié) 點(diǎn)維護(hù)全局寫日志，可擴(kuò)展性較差.針對這些問題，提出了一個基于分區(qū)的并發(fā)控制方案：通過分區(qū)的方式 降低每個寫節(jié)點(diǎn)需要維護(hù)的事務(wù)日志，以有效提升系統(tǒng)的擴(kuò)展能力.基于此想法，在MySQL上實(shí)現(xiàn)了分區(qū) 多主插件，并通過實(shí)驗(yàn)驗(yàn)證了該解決方案對系統(tǒng)性能的影響.

關(guān)鍵詞：多主數(shù)據(jù)庫;分區(qū);并發(fā)控制

中圖分類號：TP392?????? 文獻(xiàn)標(biāo)志碼：A?????? DOI： 10.3969/j.issn.1000-5641.2021.05.008

Partition-based concurrency control in a multi-master database

LIU Wenxin， CAI Peng

（School of Data Science and Engineering， East China Normal University， Shanghai 200062， China）

Abstract： In the era of big data， the single-write multi-read process with separate storage and computing architectures can no longer meet the demands for efficient reading and writing of massive datasets. Multiple computing nodes providing write services concurrently can also cause cache inconsistencies. Some studies have proposed a global ordered transaction log to detect conflicts and maintain data consistency for the whole system using broadcast and playback of the transaction log. However， this scheme has poor scalability because it maintains the global write log at each write node. To solve this problem， this paper proposes a partition-based concurrency control scheme， which reduces the transaction log maintained by each write node by partitioning， and effectively improves the systems overall expansion ability.

Keywords： multi-master database; partition; concurrency control

0引 言

隨著云計(jì)算與大數(shù)據(jù)的發(fā)展，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫已無法滿足金融市場業(yè)務(wù)的需求，越來越多的 用戶開始選擇云數(shù)據(jù)庫.計(jì)算存儲分離架構(gòu)是當(dāng)下大多商業(yè)云數(shù)據(jù)庫的解決方案.在此架構(gòu)下，數(shù)據(jù) 庫分為存儲層和計(jì)算層兩個部分：多個存儲節(jié)點(diǎn)共同組成一個共享存儲層為計(jì)算層提供可靠的持久 化存儲服務(wù);計(jì)算層則由多個計(jì)算節(jié)點(diǎn)組成，每個計(jì)算節(jié)點(diǎn)運(yùn)行一個單獨(dú)的數(shù)據(jù)庫進(jìn)程.計(jì)算節(jié)點(diǎn)緩 存一部分?jǐn)?shù)據(jù)用于服務(wù)用戶的讀寫請求，當(dāng)緩存無法命中時，計(jì)算節(jié)點(diǎn)會遵循替換策略將需要的數(shù)據(jù) 從存儲層讀入緩存.大多云數(shù)據(jù)庫的計(jì)算節(jié)點(diǎn)目前僅支持一寫多讀的架構(gòu)，即計(jì)算層只存在一個計(jì)算節(jié)點(diǎn)擁有數(shù)據(jù)的讀寫權(quán)限，其余計(jì)算節(jié)點(diǎn)都僅擁有讀權(quán)限.

為實(shí)現(xiàn)集群中寫節(jié)點(diǎn)的擴(kuò)展，數(shù)據(jù)庫領(lǐng)域曾嘗試?yán)面i機(jī)制實(shí)現(xiàn)同一時間僅有一個節(jié)點(diǎn)擁有數(shù) 據(jù)的寫權(quán)限并通過網(wǎng)絡(luò)傳遞數(shù)據(jù)頁的方法實(shí)現(xiàn)多主之后提出基于日志的沖突檢測或是確定性數(shù) 據(jù)庫的解決方法.另一方面，為提高系統(tǒng)吞吐量，現(xiàn)存在部分系統(tǒng)選擇將數(shù)據(jù)庫進(jìn)行分區(qū)，但因此引 入了跨分區(qū)事務(wù)這一·問題，導(dǎo)致需要在滿足事務(wù)ACID （Atomicity， Consistency， Isolation， Durability） 特性與限制事務(wù)僅能夠訪問一個分區(qū)這兩個條件中取舍.

對于存儲計(jì)算分離的架構(gòu)，實(shí)現(xiàn)多個寫節(jié)點(diǎn)的一大難點(diǎn)在于各寫節(jié)點(diǎn)緩存中數(shù)據(jù)的一致性維護(hù). 如上所述，數(shù)據(jù)庫讀取數(shù)據(jù)會先從緩存讀取，這樣的機(jī)制便導(dǎo)致對于某個數(shù)據(jù)各寫節(jié)點(diǎn)中緩存的版本 并不相同的情況出現(xiàn).為解決這種情況，現(xiàn)有提出基于全局事務(wù)日志進(jìn)行沖突檢測的方法通過為每 個事務(wù)分配唯一的全局事務(wù)號，并以此事務(wù)號維護(hù)事務(wù)間的可串行化調(diào)度，在各個節(jié)點(diǎn)上根據(jù)事務(wù)調(diào) 度順序回放與本地緩存數(shù)據(jù)相關(guān)的事務(wù)日志以更新各節(jié)點(diǎn)本地緩存.但在這樣的解決方法下，隨著寫 節(jié)點(diǎn)數(shù)量的增加，事務(wù)數(shù)量增長導(dǎo)致日志規(guī)模急劇上升，在每個寫節(jié)點(diǎn)上維護(hù)全局事務(wù)日志并依序檢 查每條事務(wù)無疑會產(chǎn)生較多不必要的網(wǎng)絡(luò)及計(jì)算存儲資源的消耗.

綜上所述，為了在計(jì)算存儲分離架構(gòu)的云數(shù)據(jù)庫中實(shí)現(xiàn)寫性能的擴(kuò)展，本文基于MySQL設(shè)計(jì)并 實(shí)現(xiàn)多主分區(qū)事務(wù)插件.本文的主要貢獻(xiàn)如下.

（1）設(shè)計(jì)分區(qū)算法.基于數(shù)據(jù)訪問信息對事務(wù)進(jìn)行分區(qū)，各分區(qū)內(nèi)設(shè)計(jì)獨(dú)立的驗(yàn)證器，并維護(hù)分區(qū) 獨(dú)立的日志記錄.

（2）設(shè)計(jì)事務(wù)序號的分配.通過事務(wù)序號實(shí)現(xiàn)可能有數(shù)據(jù)訪問沖突的事務(wù)間的串行化，以事務(wù)序 號為驗(yàn)證基礎(chǔ)的并發(fā)控制維護(hù)數(shù)據(jù)一致性.

（3）通過實(shí)驗(yàn)對比全局事務(wù)日志的解決方案，論證分區(qū)方法對多主數(shù)據(jù)庫性能的影響.

本文后續(xù)內(nèi)容：第1章介紹多主數(shù)據(jù)庫相關(guān)工作;第2章介紹本文提出的基于分區(qū)的多主數(shù)據(jù)庫 架構(gòu);第3章闡述分區(qū)算法的具體實(shí)現(xiàn);第4章說明跨分區(qū)并發(fā)控制的設(shè)計(jì);第5章通過實(shí)驗(yàn)驗(yàn)證本 文方案對系統(tǒng)性能的影響;第6章總結(jié)全文.

1相關(guān)工作

云數(shù)據(jù)庫發(fā)展初期，大多實(shí)現(xiàn)方法僅是為傳統(tǒng)的關(guān)系型數(shù)據(jù)庫添加云存儲，如今各大廠商逐漸推 出基于存儲計(jì)算分離架構(gòu)的云數(shù)據(jù)庫.亞馬遜率先推出計(jì)算存儲分離的云數(shù)據(jù)庫產(chǎn)品Aurora：6-'提出 “日志即數(shù)據(jù)庫”的思想.其認(rèn)為由于日志中已包含有數(shù)據(jù)的信息，故僅通過日志就可以恢復(fù)出數(shù)據(jù)， 可以僅向存儲層傳輸Redo日志，減少網(wǎng)絡(luò)I/O （Input/Output），并在存儲層回放Redo日志生成數(shù)據(jù) 頁供計(jì)算層讀取;同時由寫節(jié)點(diǎn)向讀節(jié)點(diǎn)廣播日志，讀節(jié)點(diǎn)通過回放日志更新緩存，以此實(shí)現(xiàn)節(jié)點(diǎn)緩 存的一致.阿里云的PolarDB同樣沿用存儲計(jì)算分離的架構(gòu)，通過寫節(jié)點(diǎn)廣播日志流幫助其余節(jié)點(diǎn)緩 存的更新，PolarDB的設(shè)計(jì)在計(jì)算層做的改動較少，其主要通過自研的分布式文件系統(tǒng)PolarFS[8]以 及存儲引擎X-Engine[9]更好地利用高性能硬件的特性以實(shí)現(xiàn)存儲層的優(yōu)化.隨后，微軟推出的 Socrates[10]以及華為推出的Taurus[11]在計(jì)算層依舊沿用一寫多讀的設(shè)計(jì)，但存儲層的設(shè)計(jì)各有特色.

迄今為止，大多數(shù)的商用云數(shù)據(jù)庫只提供一寫多讀的配置，即僅實(shí)現(xiàn)了讀性能的擴(kuò)展，而寫性能 的擴(kuò)展還沒有很好的實(shí)踐方案.目前已實(shí)現(xiàn)的多主解決方案，如Oracle RAC[1]和DB2 pureScale[2]，這 二者的設(shè)計(jì)思想都是利用鎖機(jī)制和數(shù)據(jù)頁的網(wǎng)絡(luò)傳輸實(shí)現(xiàn)數(shù)據(jù)的一致性.不同的是，pureScale通過全 局鎖管理器和全局緩存池實(shí)現(xiàn)，各個實(shí)例通過RDMA與二者通信;而Oracle RAC則是將鎖管理器分 布在各個實(shí)例，并通過在實(shí)例間構(gòu)建高速內(nèi)聯(lián)網(wǎng)絡(luò)實(shí)現(xiàn)緩存融合.無論是集中式還是分布式的鎖管理 方法，頻繁的鎖申請與數(shù)據(jù)頁的傳輸都會限制整個系統(tǒng)的擴(kuò)展性和吞吐量.

為消除鎖的“瓶頸”，微軟提出了一款日志結(jié)構(gòu)的共享存儲數(shù)據(jù)庫模型Hyder[3]，其架構(gòu)分為3 層——事務(wù)層、索引層、存儲層.當(dāng)本地事務(wù)執(zhí)行完成后會將更新打包廣播至存儲層的日志末尾，所 有服務(wù)器都會依據(jù)此日志有序進(jìn)行回放，包括一開始執(zhí)行事務(wù)的服務(wù)器，并在回放日志的過程中進(jìn)行 沖突檢測（meld）.同時，Hyder認(rèn)為沖突檢測階段是此系統(tǒng)的一大“瓶頸”.Bernstein等為此做了進(jìn)一 步探究，提出了并行化meld加速沖突檢測過程[12]，以及通過數(shù)據(jù)庫分區(qū)將meld算法本身并行化[13]的 方法.

2系統(tǒng)架構(gòu)

本文設(shè)計(jì)了如圖1所示的多主數(shù)據(jù)庫架構(gòu)：沿用現(xiàn)有云數(shù)據(jù)庫存儲計(jì)算分離的架構(gòu)，將數(shù)據(jù)庫分 為存儲層與計(jì)算層兩個部分;每個計(jì)算節(jié)點(diǎn)上運(yùn)行有獨(dú)立的MySQL進(jìn)程，這些計(jì)算節(jié)點(diǎn)會將日志和 數(shù)據(jù)頁寫到遠(yuǎn)程的共享存儲上;通過分區(qū)算法將數(shù)據(jù)庫劃分至若干個分區(qū)，分區(qū)內(nèi)的所有計(jì)算節(jié)點(diǎn)都 擁有本分區(qū)數(shù)據(jù)的讀寫權(quán)限;每個分區(qū)內(nèi)有獨(dú)立的事務(wù)日志以及驗(yàn)證器，故同一分區(qū)內(nèi)的計(jì)算節(jié)點(diǎn)間 的緩存一致性可依靠分區(qū)內(nèi)部有序的事務(wù)日志和驗(yàn)證機(jī)制實(shí)現(xiàn).

由于每兩個分區(qū)間的數(shù)據(jù)并不存在沖突，故兩個分區(qū)間的事務(wù)可以并發(fā)執(zhí)行.但在實(shí)際應(yīng)用環(huán)境 中無法實(shí)現(xiàn)所有事務(wù)都僅訪問一個分區(qū)，仍然會存在部分事務(wù)訪問多個分區(qū)的情況.為避免復(fù)雜的分 區(qū)并發(fā)控制，本文設(shè)計(jì)了一個邏輯分區(qū)，用來處理所有的跨分區(qū)事務(wù)，即將單分區(qū)事務(wù)路由到該事務(wù) 所訪問的分區(qū)執(zhí)行，而訪問多個分區(qū)的事務(wù)則會路由至邏輯分區(qū)執(zhí)行.此設(shè)計(jì)下，兩個單分區(qū)之間 依舊不存在數(shù)據(jù)沖突，因此可以并發(fā)執(zhí)行;沖突只會存在于單分區(qū)與邏輯分區(qū)之間，故通過邏輯分區(qū) 與各單分區(qū)之間的并發(fā)控制便可以維護(hù)數(shù)據(jù)的一致性.

3分區(qū)算法

3.1動態(tài)分區(qū)

將數(shù)據(jù)庫分區(qū)是提高系統(tǒng)吞吐量的有效方法之一.但常用的靜態(tài)分區(qū)方法在時變負(fù)載下并不能 發(fā)揮很好的作用.為應(yīng)對動態(tài)負(fù)載變化，本文提出了結(jié)合以頁為單位的數(shù)據(jù)訪問并查集運(yùn)行分區(qū)算法

來實(shí)現(xiàn)動態(tài)分區(qū).

本文提出的多主場景下的分區(qū)意味著以頁為單位，將經(jīng)常需要同時訪問的數(shù)據(jù)頁放置在同一個 分區(qū)內(nèi)，同時各個分區(qū)內(nèi)部署有若干擁有該分區(qū)數(shù)據(jù)讀寫權(quán)限的計(jì)算節(jié)點(diǎn).除實(shí)際物理劃分出的分區(qū) 外，本文設(shè)計(jì)了一個邏輯分區(qū)，用來處理訪問多個分區(qū)的跨分區(qū)事務(wù).分區(qū)內(nèi)計(jì)算節(jié)點(diǎn)間通過其共同 維護(hù)的分區(qū)事務(wù)日志實(shí)現(xiàn)數(shù)據(jù)一致性，分區(qū)間跨分區(qū)事務(wù)與其相關(guān)單分區(qū)事務(wù)間的并發(fā)控制則由跨 分區(qū)并發(fā)控制維護(hù).具體的并發(fā)控制方法將在第4章中詳細(xì)介紹.

集群初始化時，將所有數(shù)據(jù)頁劃分至同一個單分區(qū);運(yùn)行過程中由計(jì)算節(jié)點(diǎn)異步地將記錄的數(shù)據(jù) 訪問信息發(fā)送至分區(qū)統(tǒng)籌節(jié)點(diǎn);分區(qū)統(tǒng)籌節(jié)點(diǎn)收集一批次內(nèi)的事務(wù)訪問信息后，運(yùn)行分區(qū)算法重新劃 分分區(qū)，并將分區(qū)結(jié)果返回至各節(jié)點(diǎn)實(shí)現(xiàn)分區(qū)的重組.由于動態(tài)調(diào)整分區(qū)后會觸發(fā)分區(qū)的拆分與合并， 可能造成部分計(jì)算節(jié)點(diǎn)需要同步新增數(shù)據(jù)之前的日志記錄.這無疑是一個會影響系統(tǒng)性能的變動，故 分區(qū)的調(diào)整不應(yīng)太過頻繁.這一限制通過在分區(qū)統(tǒng)籌節(jié)點(diǎn)處設(shè)置定時機(jī)制觸發(fā)分區(qū)算法來實(shí)現(xiàn).同時， 當(dāng)一個分區(qū)負(fù)載較大時，事務(wù)數(shù)量會增多，可能會導(dǎo)致該分區(qū)吞吐量有所下降.但因負(fù)載均衡問題不 是本文的論述重點(diǎn)，此分區(qū)算法保證不會加劇負(fù)載不均衡現(xiàn)象，不構(gòu)成系統(tǒng)“瓶頸”，故本文不再過多 討論負(fù)載均衡問題.

3.2分區(qū)算法

本文提出的基于數(shù)據(jù)訪問信息的分區(qū)算法見算法1. “輸入”中，Origin_partition是當(dāng)前數(shù)據(jù)庫的 分區(qū)情況，每個分區(qū)包含若干數(shù)據(jù)頁;txn_set是分區(qū)與事務(wù)間的映射，表示某個分區(qū)下的事務(wù)集合; data_access_info是所有事務(wù)的數(shù)據(jù)訪問信息集合.算法1中集群的產(chǎn)生利用了并查集這一數(shù)據(jù)結(jié)構(gòu)， 屬于同一集合中的數(shù)據(jù)頁被歸為同一個分區(qū).算法1將事務(wù)分區(qū)劃分為兩大步驟：①對原分區(qū)進(jìn)行拆 分;②將拆分后的分區(qū)合并.算法1代碼部分，collections表示數(shù)據(jù)集合，若干數(shù)據(jù)頁共同構(gòu)成一個集 合;single—trx[p]表示分區(qū)p下的單分區(qū)事務(wù)集.

算法1分區(qū)算法

輸人：當(dāng)前數(shù)據(jù)庫分區(qū)情況origm_partition;事務(wù)與其所訪問分區(qū)的映射txn_set;事務(wù)的數(shù)據(jù)訪問信息集合

輸出：分區(qū)重新劃分結(jié)果new_partition

//分區(qū)拆分階段 1： For k* origin_partition do 2：?? For single_trx[p] do

3：????? 隨機(jī)選取p分區(qū)下的單分區(qū)事務(wù)T

4：????? If T訪問的數(shù)據(jù)不存在于其他集合then

5：????? 將T所訪問的數(shù)據(jù)合并至同一集合collection

6：????? 將集合 collection 加人新分區(qū) new_partition

7：????? End if

8：????? End? for

9：????? For?? T = single_trx[p]?????? do

10：?? If T訪問的數(shù)據(jù)集合數(shù)=0 then

11：?? 將T所訪問的數(shù)據(jù)合并至同一集合collection

12：?? 將集合 collection?? 加人新分區(qū)???? new_partition

Else if T訪問的數(shù)據(jù)集合數(shù)=1 then

14：?? 將T所訪問的數(shù)據(jù)合并至該集合

15：?? End if

16：?? End for

17： End for

//分區(qū)合并階段

18： For all data_access_info do

19：統(tǒng)計(jì)集合兩兩之間的共同訪問次數(shù)至count數(shù)組

20： End for

21： Repeat

22：以共同訪問次數(shù)升序與降序交替的規(guī)律合并集合

23： Until跨分區(qū)事務(wù)的比例低于《

3.2.1分區(qū)拆分階段

根據(jù)輸入的數(shù)據(jù)訪問信息data_access_info構(gòu)建并查集，每個數(shù)據(jù)頁最開始僅屬于單獨(dú)的一個集 合.拆分步驟以分區(qū)為單位進(jìn)行，僅處理各分區(qū)內(nèi)的單分區(qū)事務(wù)，故可以在各個分區(qū)間并行執(zhí)行.

首先在分區(qū)內(nèi)隨機(jī)選擇任一單分區(qū)事務(wù)，將其所訪問的數(shù)據(jù)合并至同一集合，并將此集合添加至 new_partition作為新分區(qū)之一;若該事務(wù)所訪問的數(shù)據(jù)中已有部分?jǐn)?shù)據(jù)存在于其他新分區(qū)中，則跳 過這個事務(wù)不做任何操作，直至遍歷視個此分區(qū)單事務(wù).由于事務(wù)選擇的隨機(jī)性，訪問次數(shù)較多的數(shù) 據(jù)大概率將會被分散至不同集合，這樣的方式下有效避免了頻繁訪問的數(shù)據(jù)匯聚在同一集合的現(xiàn)象 出現(xiàn).一次遍歷以后，每個原單分區(qū)已包含有若干新分區(qū)，但仍存在有部分離散數(shù)據(jù)不屬于任何新分區(qū).

接下來開始第二次遍歷，此次遍歷依舊只訪問單分區(qū)事務(wù)，獲取事務(wù)的數(shù)據(jù)訪問集，若是該事務(wù) 訪問的新分區(qū)數(shù)目不超過1個，則將剩余數(shù)據(jù)合并至該新分區(qū)，否則不做任何操作.可以發(fā)現(xiàn)，在此步 驟中僅涉及獨(dú)立的數(shù)據(jù)與新分區(qū)之間的合并，并不存在新分區(qū)之間的合并，此步驟結(jié)束后將原有的單 分區(qū)拆分成為若干個新分區(qū).

3.2.2 分區(qū)合并階段

上述步驟完成了對原有單分區(qū)的拆分，接下來通過一次遍歷所有事務(wù)完善記錄現(xiàn)有新分區(qū)間的 共同訪問次數(shù).為避免分區(qū)合并后導(dǎo)致大量負(fù)載集中在同一分區(qū)內(nèi)，合并時按照訪問次數(shù)升序和降序 交替的順序合并分區(qū)，若次數(shù)相同，則優(yōu)先合并組合中有新分區(qū)內(nèi)僅存在單獨(dú)數(shù)據(jù)或是原本屬于同一 個分區(qū)的兩個新分區(qū)，合并步驟持續(xù)至事務(wù)遍歷完畢或是跨分區(qū)事務(wù)比例達(dá)到預(yù)設(shè)閾值《.

3.3邏輯分區(qū)

邏輯分區(qū)作為架構(gòu)中較為特殊的一部分，需要處理跨分區(qū)事務(wù)，并維護(hù)全局事務(wù)日志，事務(wù)執(zhí)行 開銷較單分區(qū)事務(wù)而言更大，因此邏輯分區(qū)內(nèi)事務(wù)執(zhí)行時延將是系統(tǒng)整體吞吐量的一大影響因素，故 減小跨分區(qū)事務(wù)執(zhí)行時延是系統(tǒng)設(shè)計(jì)時必須考慮的問題.

算法1中提到，分區(qū)算法控制跨分區(qū)事務(wù)比例不高于a （a的取值視網(wǎng)絡(luò)情況和集群規(guī)模等因素 設(shè)置）.因此集群中大部分事務(wù)被劃分至各單分區(qū)并發(fā)執(zhí)行，同時各分區(qū)將事務(wù)日志異步發(fā)送至邏輯 分區(qū)，以至于邏輯分區(qū)能夠不斷更新，維護(hù)較為完整的全局事務(wù)日志，保證在執(zhí)行跨分區(qū)事務(wù)時不會 因等待日志空洞而產(chǎn)生大量延時.

為保證沖突事務(wù)間的有序，跨分區(qū)事務(wù)的執(zhí)行需要同其他分區(qū)溝通最新事務(wù)序號.為了減少網(wǎng)絡(luò) 傳輸，本文設(shè)計(jì)將序號溝通控制在一次網(wǎng)絡(luò)交互中，由邏輯分區(qū)發(fā)起，其他物理單分區(qū)在收到邏輯分 區(qū)的序號更新信息后返回本分區(qū)最新事務(wù)序號.同時邏輯分區(qū)需要維護(hù)每條跨分區(qū)事務(wù)對應(yīng)單分區(qū) 的最新事務(wù)序號以保證串行化，這類信息的維護(hù)對邏輯分區(qū)而言也存在一定的資源占用，但由于跨分 區(qū)事務(wù)的比例較低，且此信息以較為簡單的映射關(guān)系存在，事務(wù)完成后便可以刪除此事務(wù)相關(guān)信息.

4并發(fā)控制

本文沿用事務(wù)日志的思想由于分配有全局唯一且遞增的事務(wù)序號的事務(wù)形成的事務(wù)日志包含 了所有事務(wù)的提交順序和數(shù)據(jù)修改操作，故通過掃描事務(wù)日志就可以檢測出跨節(jié)點(diǎn)事務(wù)之間的沖突， 并通過日志的回放實(shí)現(xiàn)緩存的更新.不同于上述設(shè)計(jì)，由于維護(hù)全局事務(wù)日志帶來的資源開銷隨節(jié)點(diǎn) 數(shù)量的線性增長，本文提出不再維護(hù)全局事務(wù)日志，而是選擇在每個分區(qū)內(nèi)設(shè)計(jì)獨(dú)立的分區(qū)事務(wù)日志 和驗(yàn)證器.

屬于同一分區(qū)的寫節(jié)點(diǎn)通過分區(qū)事務(wù)日志即可以實(shí)現(xiàn)分區(qū)內(nèi)的數(shù)據(jù)一致性，由于分區(qū)規(guī)模的限 制，分區(qū)事務(wù)日志較全局事務(wù)日志而言輕量很多.由于數(shù)據(jù)的不相交性，兩個訪問不同單分區(qū)的事務(wù) 可以在不破壞數(shù)據(jù)一致性的前提下并發(fā)執(zhí)行，而訪問多個分區(qū)的事務(wù)將會被路由至邏輯分區(qū)執(zhí)行，因 此邏輯分區(qū)與其余單分區(qū)之間可能存在數(shù)據(jù)沖突，即存在一條事務(wù)日志出現(xiàn)在多個分區(qū)獨(dú)立日志中 的情況，故需要在邏輯分區(qū)與各單分區(qū)之間引入跨分區(qū)并發(fā)控制，保證可能存在沖突的兩個事務(wù)間的 相對順序在任一分區(qū)日志內(nèi)都是一致的.

4.1事務(wù)序號

本文設(shè)計(jì)為每條事務(wù)分配全局唯一的事務(wù)序號，依賴事務(wù)序號的順序性進(jìn)行沖突檢測確定事務(wù) 提交與否.事務(wù)序號由3部分組成：事務(wù)所屬分區(qū)P;事務(wù)所屬分區(qū)序號S-TSN，表示事務(wù)在分區(qū)內(nèi)部 的順序位置;跨分區(qū)事務(wù)序號M-TSN，表示此事務(wù)對應(yīng)的跨分區(qū)事務(wù)序號.

事務(wù)序號的比較規(guī)則：先比較M-TSN;再比較S-TSN.分區(qū)序號P用來區(qū)分事務(wù)所屬分區(qū)，不同 分區(qū)下的單分區(qū)事務(wù)由于可并發(fā)，因此其序號不具有可比性.同一分區(qū)內(nèi)的單分區(qū)事務(wù)擁有遞增的S- TSN，而單分區(qū)事務(wù)的M-TSN的變化依賴于分區(qū)間交流，即邏輯分區(qū)下有跨分區(qū)事務(wù)執(zhí)行時就會通 知其他單分區(qū)置其M-TSN+1;邏輯分區(qū)尸。下的事務(wù)S-TSN統(tǒng)一置為0，其通過遞增的M-TSN表示 事務(wù)順序.例如，事務(wù)序號TSN（J＼） = [0， 0， 3] < TSN（jy = [1， 5， 3]，代表在串行化序列中，事務(wù) 先于事務(wù)^提交;而TSN（J＼） = [0， 0， 3] > TSN（rO） = [1， 4， 2]代表事務(wù)晚于事務(wù)rO提交.

為防止長事務(wù)以及申請序號時的信息傳遞導(dǎo)致的時延影響，事務(wù)在開始執(zhí)行時就會發(fā)起序號請 求，分配的序號不會直接分配給發(fā)起請求的事務(wù)，而是分配給計(jì)算節(jié)點(diǎn)本身，待此節(jié)點(diǎn)上有事務(wù)完成 后直接從節(jié)點(diǎn)的序號列表中獲取序號，同時設(shè)置定時機(jī)制，及時將等待過長時間的序號置為無效序號. 4.2跨分區(qū)并發(fā)控制

由于需要通過事務(wù)日志實(shí)現(xiàn)沖突檢測，故沖突檢測的必要條件在于事務(wù)日志的傳輸，事務(wù)日志生 成后將會傳輸至所有與之相關(guān)的分區(qū)日志，即對應(yīng)單分區(qū)與邏輯分區(qū)下的日志記錄，并通過事務(wù)序號 的比較在日志中維護(hù)串行化順序.事務(wù)的沖突檢測同時依賴于事務(wù)日志的完整性，故對于日志中存在 的空洞部分設(shè)計(jì)補(bǔ)全機(jī)制向相關(guān)節(jié)點(diǎn)請求日志傳輸.

分區(qū)驗(yàn)證器通過事務(wù)日志中的串行化順序與事務(wù)序號提供的信息，對比事務(wù)讀寫數(shù)據(jù)與沖突域 中各事務(wù)的修改數(shù)據(jù)之間的交集確定事務(wù)是否因存在數(shù)據(jù)訪問沖突需要回滾.例如，TSN（T） = [2， 3， 1]表示在事務(wù)r之前存在2條單分區(qū)事務(wù)和1條跨分區(qū)事務(wù)，故事務(wù)r在沖突檢測階段便需要對比 沖突域中的所有事務(wù)寫集合確定事務(wù)是否可以提交.

4.3基于時間順序的事務(wù)執(zhí)行示例

接下來通過圖2示例說明具體的并發(fā)控制過程.圖2中左側(cè)表示事務(wù)時間線以及各事務(wù)訪問的分區(qū)，右側(cè)表示各分區(qū)上的事務(wù)執(zhí)行情況以及每個事務(wù)的事務(wù)序號.按照時間線依次處理各事務(wù)有如下 過程.

由于事務(wù) T1和事務(wù) T2都是單分區(qū)事務(wù)，故二者被分配到相應(yīng)分區(qū)八及慫上執(zhí)行.本地樂觀執(zhí) 行完成后獲取事務(wù)序號，以乃序號[2， 1， 0]為例，在此事務(wù)之前有0個本分區(qū)事務(wù)和0個跨分區(qū)事務(wù)， 沒有日志空洞需要等待，可以直接提交;^同上所述，事務(wù)執(zhí)行完成后將事務(wù)日志發(fā)送到及分區(qū)內(nèi) 其他服務(wù)器回放.

事務(wù)巧為訪問Pi和戶3的跨分區(qū)事務(wù)，因此巧被分配到邏輯分區(qū)戶0上執(zhí)行，事務(wù)序號為[0， 0， 1]，表示其是第一個跨分區(qū)事務(wù)，邏輯分區(qū)通知相關(guān)單分區(qū)置M-TSN為1，同時單分區(qū)以本分區(qū)最新 事務(wù)序號為返回信息，即在一次消息傳遞后二^者都獲得對方最新事務(wù)序號信息.r3本地樂觀執(zhí)行完成 后進(jìn)入驗(yàn)證階段，根據(jù)其他單分區(qū)傳回的信息可知戶1上最新事務(wù)序號為[0， 0， 0]，慫上最新事務(wù)序號 為[3， 1，0]，故需要等待事務(wù)序號為[3， 1，0]的事務(wù)日志到來后空洞被補(bǔ)全.在此空洞補(bǔ)全的過程中， 可并行檢測在此事務(wù)沖突域是否存在數(shù)據(jù)訪問沖突，若發(fā)現(xiàn)沖突可直接回滾而不需要等待空洞補(bǔ)全 結(jié)果;若沖突檢測后發(fā)現(xiàn)乃與^沖突則需要回滾乃，并將事務(wù)無效標(biāo)記轉(zhuǎn)發(fā)至其他分區(qū)，無效標(biāo)記 即代表此事務(wù)空洞不需要被回放.

八為訪問^的單分區(qū)事務(wù)，獲取事務(wù)序號[1，1，1]，M-TSN為1是由于跨分區(qū)事務(wù)乃的執(zhí)行. 八本地樂觀執(zhí)行完成后需要等待跨分區(qū)事務(wù)[0， 0， 1]的日志或無效標(biāo)記到來.r5分配至執(zhí)行，同 上，驗(yàn)證階段需等待事務(wù)序號為[2， 1，0]及[3， 1，0]事務(wù)日志到來.此時，雖然八還未執(zhí)行完成，但是 由于訪問數(shù)據(jù)不沖突，所以巧不需要等待八的事務(wù)日志到來.隨后3個單分區(qū)事務(wù)r6、r7、巧分 配到各自分區(qū)執(zhí)行，本地樂觀執(zhí)行完成后進(jìn)入空洞補(bǔ)全和沖突檢測階段.

r9訪問分區(qū)^和分區(qū)八，申請事務(wù)序號一次消息傳遞后，獲得A及八分區(qū)上最新的事務(wù)序號， 分別為[1，1，1]和[2， 2， 2]. r9在本地樂觀執(zhí)行完畢后，檢查空洞，發(fā)現(xiàn)事務(wù)r7的日志仍未到來，所以 需要繼續(xù)等待空洞補(bǔ)全完成沖突檢測.

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

5.1實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)基于15臺Linux服務(wù)器組成的集群環(huán)境，每臺Linux服務(wù)器有相同的軟件和硬件配置： Intel（R） Xeon（R） Silver 4110 CPU @ 2.10 GHz; 128 GB 內(nèi)存;10 GB/s 以太網(wǎng);CentOS Linux release 7.8.2003操作系統(tǒng).為便于控制數(shù)據(jù)訪問沖突率，實(shí)驗(yàn)選用短事務(wù)負(fù)載，每條事務(wù)僅包含1條更新 語句.

5.2系統(tǒng)吞吐量分析

第一組實(shí)驗(yàn)，集群中節(jié)點(diǎn)數(shù)量由單節(jié)點(diǎn)擴(kuò)展至15個節(jié)點(diǎn)，由多個計(jì)算節(jié)點(diǎn)執(zhí)行短事務(wù)負(fù)載，測試 本文分區(qū)方案對系統(tǒng)吞吐量的影響.實(shí)驗(yàn)分區(qū)算法處理后，將數(shù)據(jù)劃分至3個分區(qū)，并通過短事務(wù)更 新語句控制事務(wù)訪問的分區(qū)數(shù)量，對比在有跨分區(qū)事務(wù)負(fù)載與無跨分區(qū)事務(wù)負(fù)載下全局事務(wù)日志與 分區(qū)方案的擴(kuò)展性.由于單節(jié)點(diǎn)情況下事務(wù)僅在單個計(jì)算節(jié)點(diǎn)執(zhí)行，其中也并不涉及事務(wù)日志的傳遞， 故分區(qū)算法下節(jié)點(diǎn)數(shù)量從3個節(jié)點(diǎn)開始實(shí)驗(yàn).全局事務(wù)日志方案下，單節(jié)點(diǎn)系統(tǒng)吞吐量可做線性擴(kuò)展 的參考值.

5.2.1無跨分區(qū)事務(wù)負(fù)載

圖3是不存在事務(wù)訪問多個分區(qū)的情況下，即無跨分區(qū)事務(wù)負(fù)載下，全局事務(wù)日志與分區(qū)方案的 系統(tǒng)總吞吐量對比.圖3中，橫坐標(biāo)表示集群中的節(jié)點(diǎn)數(shù)量;縱坐標(biāo)表示系統(tǒng)總的吞吐量，用每秒傳輸 的事務(wù)數(shù)量（Transactions Per Second， TPS）表示（后續(xù)圖4亦如此）.

從圖3可以看出，集群節(jié)點(diǎn)數(shù)量不超過5個計(jì)算節(jié)點(diǎn)時，系統(tǒng)吞吐量在兩種解決方案下并無太大 差異.但隨著節(jié)點(diǎn)數(shù)量的增長，全局事務(wù)日志的解決方案下系統(tǒng)的吞吐量增長明顯減緩，可以預(yù)見，隨 著節(jié)點(diǎn)數(shù)量的進(jìn)一步增長，系統(tǒng)吞吐量可能會到達(dá)“瓶頸而分區(qū)策略下，系統(tǒng)吞吐量隨節(jié)點(diǎn)數(shù)量的 增長基本保持線性增長，隨著節(jié)點(diǎn)數(shù)量的增長，二者差距越發(fā)明顯.

5.2.2有跨分區(qū)事務(wù)負(fù)載

圖4是存在少量事務(wù)訪問多個分區(qū)的情況下，即有跨分區(qū)事務(wù)負(fù)載下，全局事務(wù)日志與分區(qū)方案 的系統(tǒng)總吞吐量對比.

從圖4可以看出，集群數(shù)量不超過5個節(jié)點(diǎn)的情況下，兩種解決方案下系統(tǒng)的吞吐量仍并無太大 差異.隨著節(jié)點(diǎn)數(shù)量的增長，全局事務(wù)日志的解決方案下吞吐量增長依舊處于減緩趨勢，分區(qū)算法下 系統(tǒng)的吞吐量表現(xiàn)較無跨分區(qū)事務(wù)而言，同全局事務(wù)日志方案的差距有所減小，但還是保持增長趨勢.

5.3日志等待時延分析

從第一組實(shí)驗(yàn)可以看出，全局事務(wù)日志的方案在節(jié)點(diǎn)較多時系統(tǒng)性能有很大折損.第二組實(shí)驗(yàn)的 目的是探究產(chǎn)生這一現(xiàn)象的原因.

圖5以全局事務(wù)日志與分區(qū)方案下無跨分區(qū)事務(wù)產(chǎn)生的場景做對比，從圖中可以看出，隨著節(jié)點(diǎn) 數(shù)量的增多，全局事務(wù)日志的方法下等待事務(wù)空洞補(bǔ)全的時延越來越大.究其原因，是因?yàn)槿质聞?wù) 日志的解決方案下，每條事務(wù)的提交需要等待本地維護(hù)的全局事務(wù)日志空洞補(bǔ)全后才可能提交，而隨 著節(jié)點(diǎn)數(shù)量增加，產(chǎn)生的全局日志規(guī)模急劇增長，事務(wù)需要等待的空洞規(guī)模也越來越大，故等待日志 傳遞的時延也在線性增長.而在分區(qū)場景下，每個分區(qū)維護(hù)有獨(dú)立的日志記錄和驗(yàn)證器，隨著節(jié)點(diǎn)數(shù) 量的增多，雖然全局日志的規(guī)模也在急劇增長，但由于分區(qū)僅維護(hù)了部分僅屬于此分區(qū)的事務(wù)日志， 所以其分區(qū)內(nèi)事務(wù)日志空洞的規(guī)模增長并不隨節(jié)點(diǎn)數(shù)量線性增長，故日志等待時延較全局事務(wù)日志 而言增長更為緩慢.

6結(jié) 語

在大數(shù)據(jù)時代，存儲計(jì)算架構(gòu)分離的單寫多讀場景已無法滿足海量數(shù)據(jù)的高效讀寫需求.另一方 面，多個計(jì)算節(jié)點(diǎn)同時提供寫服務(wù)會引起計(jì)算節(jié)點(diǎn)間的緩存不一致問題.針對全局事務(wù)日志回放的方 法，本文給出了基于數(shù)據(jù)訪問圖的分區(qū)方法，通過收集一批次的事務(wù)信息對數(shù)據(jù)進(jìn)行動態(tài)分區(qū)，引入 邏輯分區(qū)處理跨分區(qū)事務(wù)，并在邏輯分區(qū)與物理單分區(qū)之間設(shè)計(jì)跨分區(qū)并發(fā)控制方法以維護(hù)數(shù)據(jù)一 致性.通過實(shí)驗(yàn)證明，較全局事務(wù)日志的方法，隨著計(jì)算節(jié)點(diǎn)數(shù)量的增長，分區(qū)方法下的系統(tǒng)擴(kuò)展性表 現(xiàn)更優(yōu).

[參考文獻(xiàn)]

[1]HAYAT Z， SOOMRO T R. Implementation of oracle real application cluster [J]. Review of Computer Engineering Studies， 2016， 3（4）： 81-85.

[2]CHONG R F， LIU C. DB2 Essentials： Understanding DB2 in a Big Data World [M]. [S.l]： IBM Press， 2013.

[3]BERNSTEIN P A， REID C W， DAS S. Hyder - A transactional record manager for shared flash [C]// CIDR 2011， 5th Biennial Conference

on Innovative Data Systems Research. CIDR， 2011： 9-20.

[4]THOMSON A， DIAMOND T， WENG S C， et al. Calvin： Fast distributed transactions for partitioned database systems [C]// Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM， 2012： 1-12.

[5]衛(wèi)孝賢，劉文欣，蔡鵬.多主云數(shù)據(jù)庫的全局事務(wù)日志[J].華東師范大學(xué)學(xué)報（自然科學(xué)版），2020（5）： 10-20.

[6 ] VERBITSKI A， GUPTA A， SAHA D， et al. Amazon aurora： Design considerations for high throughput cloud-native relational databases [C]// Proceedings of the 2017 ACM International Conference on Management of Data. ACM， 2017： 1041-1052.

[7 ] VERBITSKI A， GUPTA A， SAHA D， et al. Amazon aurora： On avoiding distributed consensus for I/Os， commits， and membership changes [C]// Proceedings of the 2018 International Conference on Management of Data. ACM， 2018： 789-796.

[8 ] CAO W， LIU Z J， WANG P， et al. PolarFS： An ultra-low latency and failure resilient distributed file system for shared storage cloud database [J]. Proceedings of the VLDB Endowment， 2018， 11（1（2）： 1849-1862.

[9 ] HUANG G， CHENG X T， WANG J Y， et al. X-engine： An optimized storage engine for large-scale E-commerce transaction Processing[C] // Proceedings of the 2019 International Conference on Management of Data. ACM， 2019： 651-665.

[10]ANTONOPOULOS P， BUDOVSKI A， DIACONU C， et al. Socrates： The new SQL server in the cloud [C]// Proceedings of the 2019 International Conference on Management of Data. ACM， 2019： 1743-1756.

[11]DEPOUTOVITCH A， CHEN C， CHEN J， et al. Taurus database： How to be fast， available， and frugal in the cloud [C]// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. ACM， 2020： 1463-1478.

[12]BERNSTEIN P A， DAS S， DING B L， et al. Optimizing optimistic concurrency control for tree-structured， log-structured databases [C]// Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM， 2015： 1295-1309.

[13]BERNSTEIN P A， DAS S. Scaling optimistic concurrency control by approximately partitioning the certifier and log [J]. IEEE Data Eng Bull， 2015， 38： 32-49.

（責(zé)任編輯：李藝）