姜天洋 張廣艷 李之悅

(清華大學(xué)計算機(jī)科學(xué)與技術(shù)系 北京 100084)

(北京信息科學(xué)與技術(shù)國家研究中心(清華大學(xué)) 北京 100084)

(ty-jiang18@mails.tsinghua.edu.cn)

事務(wù)指一個有限的操作序列[1],是數(shù)據(jù)庫或其他系統(tǒng)的一個執(zhí)行邏輯單元.事務(wù)具有ACID(atomicity, consistency, isolation, durability)[2]的特性:事務(wù)中的所有操作必須全部執(zhí)行或全部不執(zhí)行(原子性);確保系統(tǒng)從一個一致的狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€一致的狀態(tài)(一致性);多個事務(wù)并發(fā)執(zhí)行時不互相影響執(zhí)行結(jié)果(隔離性);已提交事務(wù)對系統(tǒng)的修改將被永久保存(持久性).事務(wù)支持應(yīng)用通過數(shù)據(jù)庫等系統(tǒng)來處理各種復(fù)雜的業(yè)務(wù)邏輯,對于在線交易和實時分析等領(lǐng)域有著重要作用.

數(shù)據(jù)庫系統(tǒng)在不同發(fā)展階段提供不同程度的事務(wù)支持.以O(shè)racle[3],SQL Server[4]為代表的關(guān)系型數(shù)據(jù)庫[5]為用戶提供嚴(yán)格的事務(wù)支持,用戶通過結(jié)構(gòu)化查詢語言SQL對數(shù)據(jù)進(jìn)行一系列事務(wù)操作.以Redis[6],MongoDB[7]等為代表的NoSQL數(shù)據(jù)庫[8]放松了對事務(wù)的支持,實現(xiàn)了數(shù)據(jù)讀寫的高性能以及數(shù)據(jù)增長時的可擴(kuò)展.然而,因為只提供弱一致性保證,NoSQL數(shù)據(jù)庫往往難以滿足聯(lián)機(jī)事務(wù)處理(online transaction processing, OLTP)[9]等應(yīng)用的需要.以Spanner[10],CockroachDB[11]為代表的新興NewSQL數(shù)據(jù)庫[12]設(shè)計了適應(yīng)更高計算、網(wǎng)絡(luò)和存儲能力的并發(fā)控制協(xié)議,在提供海量數(shù)據(jù)存儲管理能力的同時,實現(xiàn)了滿足OLTP等應(yīng)用的嚴(yán)格事務(wù)支持.

內(nèi)存事務(wù)處理是NewSQL數(shù)據(jù)庫系統(tǒng)的核心.早期的硬盤事務(wù)指內(nèi)存緩存事務(wù)執(zhí)行的部分?jǐn)?shù)據(jù)以及保留必要的元數(shù)據(jù),硬盤存儲所有事務(wù)執(zhí)行的數(shù)據(jù),其特點(diǎn)是事務(wù)執(zhí)行延遲高、并發(fā)程度低.內(nèi)存事務(wù)指內(nèi)存存儲所有事務(wù)執(zhí)行需要的數(shù)據(jù),硬盤等持久性介質(zhì)通過存儲日志等方式來保證事務(wù)的持久性.內(nèi)存事務(wù)并發(fā)控制協(xié)議主要為單機(jī)多核及分布式場景設(shè)計,顯著縮短了事務(wù)的執(zhí)行時間.計算、網(wǎng)絡(luò)、存儲等基礎(chǔ)設(shè)施的能力提升,促使NewSQL數(shù)據(jù)庫提供高性能、可擴(kuò)展、持久化的內(nèi)存事務(wù)支持.例如2020年“雙11”,阿里巴巴公司的云數(shù)據(jù)庫PolarDB每秒事務(wù)處理峰值達(dá)到1.4億次[13].

為了聚焦于內(nèi)存事務(wù),研究人員將數(shù)據(jù)庫中事務(wù)處理部分分離,形成內(nèi)存事務(wù)系統(tǒng)進(jìn)行單獨(dú)研究.內(nèi)存事務(wù)系統(tǒng)主要包括并發(fā)控制層、索引層和存儲層3個層次[14].其中,并發(fā)控制層是內(nèi)存事務(wù)的核心,也是本文主要討論內(nèi)容.并發(fā)控制協(xié)議通過合理安排并發(fā)執(zhí)行的多個內(nèi)存事務(wù)中的數(shù)據(jù)讀寫操作的順序,避免事務(wù)的執(zhí)行結(jié)果相互影響,在保證多個內(nèi)存事務(wù)之間隔離性的同時,實現(xiàn)事務(wù)處理的高效率.并發(fā)控制協(xié)議設(shè)計,需要結(jié)合事務(wù)系統(tǒng)的數(shù)據(jù)布局、網(wǎng)絡(luò)架構(gòu)和上層應(yīng)用的業(yè)務(wù)模式,廣義上的并發(fā)控制協(xié)議還包括內(nèi)存事務(wù)的持久化方案.

使用場景的變遷和設(shè)備工藝的發(fā)展使得傳統(tǒng)并發(fā)控制協(xié)議面臨諸多挑戰(zhàn)：1)數(shù)據(jù)訪問熱點(diǎn)的存在使得多核架構(gòu)中的并發(fā)控制協(xié)議必須通過跨核通信才能發(fā)現(xiàn)并解決事務(wù)沖突,而處理器核數(shù)和內(nèi)存規(guī)模的增長使得跨核訪問的延遲明顯上升,如何在解決事務(wù)沖突的前提下減少跨核通信對并發(fā)控制協(xié)議設(shè)計是一個挑戰(zhàn).2)并發(fā)控制協(xié)議往往通過集中式鎖管理器、集中式時間戳分配器等集中控制點(diǎn)來協(xié)調(diào)解決事務(wù)和數(shù)據(jù)的沖突,這些集中的協(xié)調(diào)環(huán)節(jié)容易成為分布式系統(tǒng)的性能瓶頸,使得系統(tǒng)在規(guī)模不斷增長的數(shù)據(jù)中心集群里面臨擴(kuò)展性難題.3)原有事務(wù)管理基于磁盤或固態(tài)盤進(jìn)行異步持久化,面對速度快1到2個數(shù)量級的非易失內(nèi)存(non-volatile memory, NVM)[15]時,異步持久化方案已不再適用,如何將持久化操作加入并發(fā)控制協(xié)議中,使得并發(fā)控制協(xié)議適應(yīng)NVM的性能特點(diǎn),是保證事務(wù)系統(tǒng)性能和可用性的一個挑戰(zhàn).

研究人員從增強(qiáng)擴(kuò)展性、利用新硬件加速事務(wù)處理、減少事務(wù)中止次數(shù)、保證持久性等多條技術(shù)路線出發(fā),對內(nèi)存事務(wù)的并發(fā)控制協(xié)議進(jìn)行了探索.1)通過重構(gòu)時間戳分配機(jī)制、緩存熱點(diǎn)數(shù)據(jù)等技術(shù),逐步解決了系統(tǒng)擴(kuò)展中的瓶頸問題.2)結(jié)合計算能力的提升和新興網(wǎng)絡(luò)技術(shù)來改進(jìn)并發(fā)控制協(xié)議,縮短了事務(wù)的執(zhí)行時間.3)通過采用更加靈活的提交策略以及數(shù)據(jù)的多版本技術(shù)在不同場景中降低事務(wù)中止概率,提升了事務(wù)系統(tǒng)的吞吐率.4)內(nèi)存事務(wù)利用非易失內(nèi)存和多副本技術(shù),提高了持久性保證的實現(xiàn)效率,并增強(qiáng)了事務(wù)系統(tǒng)的容錯能力.

本文從內(nèi)存事務(wù)中并發(fā)控制協(xié)議所面臨的機(jī)遇與挑戰(zhàn)出發(fā),梳理了最近10年內(nèi)存事務(wù)相關(guān)的研究工作.首先,從處理策略、版本控制、沖突解決3個維度,分類闡述了現(xiàn)有內(nèi)存事務(wù)的并發(fā)控制協(xié)議.接著從性能、擴(kuò)展性、持久性等方面論述并比較了代表性的并發(fā)控制協(xié)議,并通過實驗比較了部分并發(fā)控制協(xié)議的性能,總結(jié)了內(nèi)存事務(wù)并發(fā)控制協(xié)議優(yōu)化的技術(shù)思路.最后,指出了內(nèi)存事務(wù)中并發(fā)控制協(xié)議的未來研究方向,并對相關(guān)的綜述工作進(jìn)行了總結(jié).

1 內(nèi)存事務(wù)中并發(fā)控制協(xié)議的機(jī)遇與挑戰(zhàn)

內(nèi)存事務(wù)系統(tǒng)架構(gòu)一般包括3層,從上至下依次為并發(fā)控制層、索引層、存儲層，如圖1所示.并發(fā)控制層包含事務(wù)的并發(fā)控制協(xié)議,是內(nèi)存事務(wù)處理的核心.對于單機(jī)事務(wù)系統(tǒng),并發(fā)控制層維護(hù)了事務(wù)的讀寫集合、數(shù)據(jù)的鎖、版本號、讀寫時間戳等信息.對于分布式事務(wù)系統(tǒng),并發(fā)控制層還需要引入網(wǎng)絡(luò)通信,通過遠(yuǎn)程過程調(diào)用(remote procedure call, RPC)等技術(shù)去讀寫遠(yuǎn)端的數(shù)據(jù)及元數(shù)據(jù)信息.事務(wù)進(jìn)入系統(tǒng)后,并發(fā)控制協(xié)議會根據(jù)實時并發(fā)、有讀寫依賴關(guān)系的其他事務(wù),確定該事務(wù)讀寫數(shù)據(jù)的時機(jī),以確保事務(wù)并發(fā)執(zhí)行時的隔離性,并追求事務(wù)處理的高性能.

Fig. 1 Architecture of in-memory transaction system圖1 內(nèi)存事務(wù)系統(tǒng)架構(gòu)

在并發(fā)控制層之下,索引層為事務(wù)提供數(shù)據(jù)所在的位置信息.在分布式場景中,索引層可以通過靜態(tài)Hash、一致性Hash等分布式索引方式,也可以通過元數(shù)據(jù)服務(wù)器動態(tài)地維護(hù)數(shù)據(jù)分布表等中心化索引方式,幫助事務(wù)找到數(shù)據(jù)所在的服務(wù)器.在單臺數(shù)據(jù)服務(wù)器上,索引層則利用Hash表、B+樹這2種在內(nèi)存事務(wù)系統(tǒng)中使用最廣泛的數(shù)據(jù)結(jié)構(gòu),查找數(shù)據(jù)在對應(yīng)服務(wù)器上的具體位置.

找到了數(shù)據(jù)的具體位置,內(nèi)存事務(wù)系統(tǒng)在存儲層對數(shù)據(jù)進(jìn)行讀寫操作.存儲層綜合包括了內(nèi)存、硬盤等多種介質(zhì)構(gòu)成的存儲空間,可以被組織成塊存儲或?qū)ο蟠鎯Φ炔煌问?

1.1 發(fā)展機(jī)遇

關(guān)于事務(wù)的研究一直是計算機(jī)系統(tǒng)領(lǐng)域一個熱點(diǎn)問題.針對事務(wù)的并發(fā)控制協(xié)議與實現(xiàn)在20世紀(jì)80年代就有了大量的學(xué)術(shù)研究[16-17],Oracle,MySQL[18],SQL Server等關(guān)系型數(shù)據(jù)庫的興起帶動了事務(wù)從學(xué)術(shù)研究走向工業(yè)應(yīng)用.近10年新興網(wǎng)絡(luò)、存儲技術(shù)的出現(xiàn)帶給了并發(fā)控制協(xié)議新的機(jī)遇,具體可歸納為2點(diǎn):

1) 網(wǎng)絡(luò)能力的提升降低了分布式事務(wù)的集群通信開銷

由于數(shù)據(jù)分布式地存放在集群的不同節(jié)點(diǎn)內(nèi),分布式事務(wù)必須通過網(wǎng)絡(luò)通信讀寫遠(yuǎn)端節(jié)點(diǎn)的數(shù)據(jù).傳統(tǒng)網(wǎng)絡(luò)通信存在內(nèi)核調(diào)用棧復(fù)雜、緩沖區(qū)拷貝頻繁等問題,網(wǎng)絡(luò)通信時間更多耗費(fèi)在了服務(wù)器端而非鏈路上.新興的數(shù)據(jù)平面開發(fā)套件(data plane development kit, DPDK)[19]和遠(yuǎn)程直接內(nèi)存訪問(remote direct memory access, RDMA)[20-21]技術(shù)都聚焦于繞過復(fù)雜的系統(tǒng)調(diào)用來實現(xiàn)簡單高效的網(wǎng)絡(luò)通信,它們具有的低延遲和高吞吐率特性可以幫助分布式事務(wù)減少網(wǎng)絡(luò)通信開銷.

同時,RDMA技術(shù)提供的新型網(wǎng)絡(luò)原語,也給進(jìn)一步加速分布式事務(wù)帶來了機(jī)遇.RDMA提供的遠(yuǎn)程讀寫、遠(yuǎn)程原子操作可以在遠(yuǎn)端CPU不參與的前提下,繞過內(nèi)核直接讀寫遠(yuǎn)端內(nèi)存.這種做法不僅降低了本地事務(wù)操作獲取遠(yuǎn)端數(shù)據(jù)的延遲,還降低了遠(yuǎn)端CPU的負(fù)載,因此提升了事務(wù)系統(tǒng)的整體吞吐率.遠(yuǎn)程原子操作甚至能幫助并發(fā)控制協(xié)議實現(xiàn)部分復(fù)雜的邏輯,在完全沒有遠(yuǎn)端CPU的參與下解決事務(wù)間的沖突.

2) 新型存儲硬件的出現(xiàn)加速了數(shù)據(jù)持久化并減少了事務(wù)沖突

傳統(tǒng)內(nèi)存事務(wù)的持久化需要借助固態(tài)盤或磁盤,它們讀寫粒度大、延遲高,事務(wù)的批量持久化策略會帶來崩潰后大量事務(wù)重試的風(fēng)險,進(jìn)而影響恢復(fù)速度,事務(wù)的持久化完成時間通常明顯落后于事務(wù)在內(nèi)存中的完成時間.非易失內(nèi)存能提供字節(jié)粒度的數(shù)據(jù)訪問,訪存時延接近DRAM內(nèi)存,且掉電后數(shù)據(jù)不丟失.在目前的計算機(jī)存儲層級結(jié)構(gòu)中,它可以作為內(nèi)存或塊設(shè)備工作,從而有效加速內(nèi)存事務(wù)的持久化.

此外,硬件事務(wù)內(nèi)存技術(shù)(hardware transactional memory, HTM)的發(fā)展有助于從硬件角度解決事務(wù)訪存競爭并減少事務(wù)沖突.作為一個典型實例,Intel公司的受限事務(wù)內(nèi)存(restricted transactional memory, RTM)[22]使用一級緩存跟蹤讀寫集,并依賴緩存一致性檢測數(shù)據(jù)競爭.RTM的效率比軟件實現(xiàn)的并發(fā)控制協(xié)議更高,卻存在讀寫集大小受限、不支持網(wǎng)絡(luò)I/O等不足.研究人員可以思考如何利用RTM實現(xiàn)高效的分布式事務(wù)并發(fā)控制協(xié)議.

1.2 面臨的技術(shù)挑戰(zhàn)

網(wǎng)絡(luò)和存儲技術(shù)的進(jìn)步以及使用場景的變遷也讓內(nèi)存事務(wù)中并發(fā)控制協(xié)議的發(fā)展面臨新的挑戰(zhàn),主要包括3個方面:

1) 多核場景中大量跨NUMA節(jié)點(diǎn)的通信增加了事務(wù)的延遲

隨著處理器技術(shù)的發(fā)展和內(nèi)存規(guī)模的增加,單個高端服務(wù)器可以擁有上百個核心及TB級內(nèi)存.單機(jī)數(shù)據(jù)庫系統(tǒng)在存儲數(shù)據(jù)時往往采用共享內(nèi)存[23]的模式,任何線程都可以自由地訪問所有數(shù)據(jù).事務(wù)在執(zhí)行時會從共享內(nèi)存中讀寫相應(yīng)數(shù)據(jù),并將讀集、寫集寫入共享內(nèi)存中供其他事務(wù)驗證沖突.然而,隨著核數(shù)增多,這種模式造成大量跨NUMA節(jié)點(diǎn)的通信開銷,增加了事務(wù)的延遲.此外,不同線程對熱點(diǎn)數(shù)據(jù)的同步操作也會造成CPU資源的等待浪費(fèi),即使是CAS(compare and swap)等原子指令,在很多線程同時發(fā)起指令的情況下也會導(dǎo)致阻塞.采用硬分區(qū)技術(shù)的事務(wù)系統(tǒng)將數(shù)據(jù)按核劃分,單核內(nèi)執(zhí)行事務(wù)避免了核間通信和數(shù)據(jù)競爭,但一旦遇到難以簡單分區(qū)的負(fù)載,系統(tǒng)就會因為頻繁的跨分區(qū)事務(wù)而出現(xiàn)性能降級.因此,如何在多核場景中減少事務(wù)執(zhí)行時的跨核通信,盡早檢測并避免數(shù)據(jù)競爭,是設(shè)計并發(fā)控制協(xié)議面臨的重要挑戰(zhàn).

2) 分布式系統(tǒng)的集中控制點(diǎn)限制了事務(wù)系統(tǒng)的擴(kuò)展性

分布式數(shù)據(jù)庫的規(guī)模從同機(jī)房單一機(jī)架規(guī)模,逐步擴(kuò)展到異地多數(shù)據(jù)中心,其擴(kuò)展性問題變得更加突出.數(shù)據(jù)庫處理分布式事務(wù)存在很多集中控制點(diǎn),包括集中式鎖管理節(jié)點(diǎn)、集中式時間戳分配節(jié)點(diǎn)等.并發(fā)控制協(xié)議利用這些集中控制點(diǎn)協(xié)調(diào)事務(wù)處理順序,解決事務(wù)讀寫數(shù)據(jù)時產(chǎn)生的沖突等,保證事務(wù)的隔離性等級.所有事務(wù)的執(zhí)行路徑都會包括這些集中控制點(diǎn),因此成為分布式數(shù)據(jù)庫的瓶頸,影響系統(tǒng)的擴(kuò)展性.設(shè)計者需要改進(jìn)事務(wù)處理流程,將事務(wù)的協(xié)調(diào)開銷、數(shù)據(jù)沖突分?jǐn)偟礁鱾€節(jié)點(diǎn),避免單個節(jié)點(diǎn)訪問量過大成為瓶頸.同時,將事務(wù)分散到各個節(jié)點(diǎn)可能造成事務(wù)之間的沖突無法協(xié)調(diào),元數(shù)據(jù)通信不及時會導(dǎo)致系統(tǒng)狀態(tài)的不一致,最終導(dǎo)致事務(wù)中止增多、系統(tǒng)吞吐率降低.如何平衡兩者關(guān)系,合理地減少分布式事務(wù)的集中控制點(diǎn),是設(shè)計者面臨的挑戰(zhàn).

3) 原有協(xié)議難以發(fā)揮新設(shè)備優(yōu)勢來提高持久性保證的實現(xiàn)效率

原有事務(wù)的持久化方案為固態(tài)盤或磁盤設(shè)計,由于磁盤訪存延遲高、訪問粒度大,原有方案采用異步持久化方案,將操作日志批量聚合成塊后發(fā)往磁盤.因此簡單地將磁盤替換為NVM無法發(fā)揮新設(shè)備低延遲、低訪問粒度的特性.在并發(fā)控制協(xié)議中加入持久化、網(wǎng)絡(luò)備份操作來適配NVM的特性,盡可能避免影響事務(wù)原有性能,是一個重要挑戰(zhàn).一方面,由于NVM的訪存性能和DRAM仍有數(shù)倍差距,主存中NVM和DRAM還將并存.并發(fā)控制協(xié)議需要設(shè)計NVM區(qū)域中事務(wù)日志信息的存儲格式,在保證正確處理事務(wù)沖突的前提下加入持久化操作.另一方面,事務(wù)可以將數(shù)據(jù)的修改通過網(wǎng)絡(luò)快速持久化到后備節(jié)點(diǎn)的NVM上,避免主節(jié)點(diǎn)崩潰后數(shù)據(jù)不可用.然而,直接在存儲層應(yīng)用副本技術(shù)會因為割裂并發(fā)控制層和存儲層而增加了通信開銷.

2 內(nèi)存事務(wù)并發(fā)控制協(xié)議的分類

本文從3個維度對內(nèi)存事務(wù)中并發(fā)控制協(xié)議進(jìn)行分類.首先是從事務(wù)處理策略的角度,分為悲觀并發(fā)控制和樂觀并發(fā)控制.悲觀并發(fā)控制要求事務(wù)在執(zhí)行時鎖定數(shù)據(jù),以阻止其他事務(wù)修改數(shù)據(jù),如果鎖定失敗,則該事務(wù)選擇繼續(xù)等待或中止.2階段鎖(2-phase lock, 2PL)是一種常見的悲觀并發(fā)控制,在業(yè)界有著廣泛應(yīng)用.樂觀并發(fā)控制(optimistic concurrency control, OCC)強(qiáng)調(diào)事務(wù)在讀寫時不是鎖定或獨(dú)占數(shù)據(jù),而是在提交階段對讀寫的數(shù)據(jù)進(jìn)行驗證,如果驗證通過則成功提交,否則說明事務(wù)讀寫的數(shù)據(jù)在執(zhí)行階段被其他事務(wù)干擾,該事務(wù)必須中止并回滾.在事務(wù)沖突較少時,OCC的事務(wù)被干擾中止的概率更低,吞吐率表現(xiàn)更加優(yōu)異,而2PL更適合沖突較多的場景.

如圖2所示,2PL在執(zhí)行過程中分為2階段：1)持鎖階段,事務(wù)在執(zhí)行過程中獲取讀寫數(shù)據(jù)所需的鎖,并阻塞其他事務(wù)執(zhí)行;2)放鎖階段,事務(wù)釋放所有已經(jīng)獲得的鎖,將數(shù)據(jù)的修改展示給其他事務(wù).OCC則分為3個階段：執(zhí)行階段、驗證階段、提交階段.事務(wù)在執(zhí)行階段讀取數(shù)據(jù)及相應(yīng)版本號,對于寫請求緩存在本地或當(dāng)前線程的緩沖區(qū);在驗證階段驗證事務(wù)的讀集沒有被其他事務(wù)的寫請求修改,以及事務(wù)的寫集不與其他事務(wù)的寫集沖突;在提交階段修改數(shù)據(jù),并將修改展示給其他事務(wù).

Fig. 2 Executive processes of two concurrency control schemes圖2 2種并發(fā)控制方案的執(zhí)行過程

從數(shù)據(jù)版本控制的角度,并發(fā)控制協(xié)議可以分為單版本并發(fā)控制(1-version concurrency control, 1VCC)和多版本并發(fā)控制(multi-version concurrency control, MVCC)[24].單版本并發(fā)控制的數(shù)據(jù)只維護(hù)數(shù)據(jù)的最新版本,這種方式簡單直接并且易于進(jìn)行內(nèi)存管理.然而,當(dāng)事務(wù)的并發(fā)程度增加,維護(hù)數(shù)據(jù)的多個歷史版本能讓不同事務(wù)分別讀取對應(yīng)時間點(diǎn)的數(shù)據(jù),減少了事務(wù)之間的沖突,增加了系統(tǒng)的吞吐率.同時,為每個數(shù)據(jù)維護(hù)多個歷史版本會給系統(tǒng)增加額外的內(nèi)存開銷,定期回收、整合數(shù)據(jù)的不同版本給系統(tǒng)增添了CPU開銷.

根據(jù)數(shù)據(jù)競爭的解決方式,并發(fā)控制協(xié)議又可以分為基于鎖、基于時間戳、混合使用3種類型.鎖是處理數(shù)據(jù)競爭最直接有效的方式,對于“寫-寫”數(shù)據(jù)沖突的事務(wù)可以通過互斥鎖來解決,“讀-寫”數(shù)據(jù)沖突的事務(wù)可以借助讀寫鎖來解決.但是,鎖的使用會降低事務(wù)的并發(fā)率,例如2PL為了滿足可串行化的隔離等級,要求事務(wù)在提交前獲得所有相關(guān)數(shù)據(jù)的鎖,這給事務(wù)并發(fā)處理增添了很多“虛假”的沖突,也增加了系統(tǒng)出現(xiàn)“死鎖”的風(fēng)險.基于時間戳的協(xié)議通過給事務(wù)分配開始時間戳、提交時間戳以及數(shù)據(jù)版本的時間戳,確定事務(wù)之間正確執(zhí)行必須存在的依賴關(guān)系,縮小了事務(wù)處理中由鎖保護(hù)的臨界區(qū)的長度,提高了并發(fā)程度.通?；跁r間戳的協(xié)議需要2次驗證來確定事務(wù)能否提交,這給處理“寫-寫”沖突帶來較大開銷,因為一旦事務(wù)中止,回滾事務(wù)需要很多額外操作.因此,研究人員提出了利用時間戳解決“讀-寫”沖突、利用鎖解決“寫-寫”沖突的混合并發(fā)控制協(xié)議.

以上3種分類是依據(jù)并發(fā)控制協(xié)議的實現(xiàn)方式.不同協(xié)議實現(xiàn)的隔離等級亦不相同,本文涉及的協(xié)議包括3種隔離等級[25]：快照隔離性(snapshot isolation)、可串行化(serializability)、嚴(yán)格可串行化(strict serializability).更低的隔離等級對于應(yīng)用編程不友好,因此本文不作討論.快照隔離性要求事務(wù)的讀操作看到數(shù)據(jù)庫中一個一致的版本快照,事務(wù)的寫操作只要在讀到快照時間點(diǎn)后不與并發(fā)的寫沖突即可成功提交.因此快照隔離性會出現(xiàn)“寫偏斜”的異常.可串行化保證了并發(fā)事務(wù)的執(zhí)行結(jié)果一定和某個串行化順序的執(zhí)行結(jié)果一致,也可以理解為事務(wù)的讀寫從結(jié)果上看在同一時間點(diǎn)發(fā)生;嚴(yán)格可串行化是最強(qiáng)的隔離級別,在可串行化基礎(chǔ)上要求,從物理時間上看,如果事務(wù)A在事務(wù)B開始之前已經(jīng)提交,那么在可串行化序中事務(wù)A必須先于事務(wù)B.從實現(xiàn)方式看,基于鎖的并發(fā)控制協(xié)議利用鎖保護(hù)臨界區(qū)解決沖突,天然地具備了滿足嚴(yán)格可串行化的特性：后發(fā)生的事務(wù)要么看到已經(jīng)提交的修改,要么看到其他事務(wù)持鎖而阻塞;基于時間戳的并發(fā)控制則受制于分布式時鐘的精度誤差,必須通過不確定性等待等額外操作實現(xiàn)嚴(yán)格可串行化.然而,兼顧嚴(yán)格可串行化和事務(wù)系統(tǒng)性能并不容易,根據(jù)SNOW理論[26],當(dāng)并發(fā)控制中同時處理只讀事務(wù)和讀寫事務(wù)時,為實現(xiàn)嚴(yán)格可串行化,只讀事務(wù)的讀請求要么需要一次以上的信息交互,要么需要阻塞、等待等操作,這影響了事務(wù)的執(zhí)行延遲.因此,部分并發(fā)控制協(xié)議選擇提供可串行化隔離等級,以換取性能的提升.

表1列舉了近10年提出的19個內(nèi)存事務(wù)系統(tǒng),并對其并發(fā)控制協(xié)議進(jìn)行分類.

Table 1 Classification of Cocurrency Control Protocols of In-Memory Transaction Systems表1 內(nèi)存事務(wù)系統(tǒng)并發(fā)控制協(xié)議分類

3 并發(fā)控制協(xié)議的代表性工作

內(nèi)存事務(wù)系統(tǒng)從不同技術(shù)路線出發(fā),對并發(fā)控制協(xié)議進(jìn)行了很多探索.本節(jié)整理了最近10年具有代表性的內(nèi)存事務(wù)系統(tǒng)及其并發(fā)控制協(xié)議,按照技術(shù)路線可以分為4類:消除事務(wù)擴(kuò)展瓶頸、利用新硬件加速事務(wù)處理、降低事務(wù)中止概率、高效保證事務(wù)持久性.

3.1 消除事務(wù)擴(kuò)展瓶頸

擴(kuò)展性是內(nèi)存事務(wù)系統(tǒng)興起面臨的主要難題.基于傳統(tǒng)中心化架構(gòu)的事務(wù)系統(tǒng)難以滿足高并發(fā)、瞬時暴漲的業(yè)務(wù)需求,同時計算、網(wǎng)絡(luò)能力的提升又推動了事務(wù)系統(tǒng)架構(gòu)的變革.減少傳統(tǒng)架構(gòu)中的集中控制點(diǎn)、分?jǐn)傌?fù)載熱點(diǎn)成為消除事務(wù)擴(kuò)展瓶頸的主要手段.

1) 改進(jìn)全局時間戳分配方法

為了實現(xiàn)嚴(yán)格可串行化的隔離等級,并發(fā)的事務(wù)在決定執(zhí)行順序時依賴物理時間對照,事務(wù)在開始和提交時需分配對應(yīng)時間戳,多版本事務(wù)系統(tǒng)中每個數(shù)據(jù)版本也需要時間戳加以區(qū)分.但是,分布式場景中節(jié)點(diǎn)之間物理時鐘的誤差只經(jīng)過松散的同步則遠(yuǎn)大于數(shù)據(jù)傳輸?shù)难舆t,傳統(tǒng)事務(wù)系統(tǒng)采用時間發(fā)號器統(tǒng)一全局物理時間.系統(tǒng)在時鐘服務(wù)器上維護(hù)時間發(fā)號器,所有節(jié)點(diǎn)在事務(wù)開始、提交以及新數(shù)據(jù)版本寫入時,都向時鐘服務(wù)器請求獲取時間戳. 時鐘服務(wù)器收到請求后,原子地將發(fā)號器加1并返回該請求,因此每個請求得到了全局唯一、和物理時間序吻合的全局時間戳.

上述做法顯然會使時間發(fā)號器成為整個系統(tǒng)的瓶頸. Google提出的地理上分布數(shù)據(jù)庫Spanner[10]雖然是一個基于硬盤事務(wù)的分布式數(shù)據(jù)庫,但其技術(shù)被廣泛應(yīng)用于之后的內(nèi)存事務(wù)系統(tǒng)中．Spanner采用了新的物理時鐘同步方案TrueTime,每個節(jié)點(diǎn)維護(hù)全局統(tǒng)一的物理時鐘,避免獲取時間戳?xí)r在關(guān)鍵路徑上向集中式時鐘服務(wù)器發(fā)送請求.TrueTime通過周期性地向時鐘服務(wù)器發(fā)送網(wǎng)絡(luò)數(shù)據(jù)包,獲得本地時鐘和時鐘服務(wù)器的時鐘偏移.每次本地請求獲取時間戳?xí)r,返回一個時間區(qū)間,代表當(dāng)前時間點(diǎn)可能的時間范圍[L,U],區(qū)間長度的一半即為時鐘誤差.系統(tǒng)將時間戳分配給事務(wù)或數(shù)據(jù)版本時,將U作為當(dāng)前時間戳,在休眠U-L時間后分配給對應(yīng)對象并對系統(tǒng)中的其他節(jié)點(diǎn)可見,以保證該時間戳可見后不存在任何節(jié)點(diǎn)能獲得比U更小的時間戳,實現(xiàn)全局時間戳分配的單調(diào)增長.Spanner在地理上分布的數(shù)據(jù)中心場景中借用GPS實現(xiàn)了這一方案,時鐘誤差為7 ms.但是,對于分布式事務(wù),保證嚴(yán)格可串行化需要增加高達(dá)7 ms的執(zhí)行延遲,這會降低系統(tǒng)吞吐率,影響用戶體驗.FaRM v2[36]是Microsoft提出的一個基于RDMA的分布式計算平臺,它延用Spanner的方法,在單個數(shù)據(jù)中心中應(yīng)用RDMA技術(shù)加速時鐘同步的網(wǎng)絡(luò)傳輸,將時鐘誤差降低到10 μs.

除了同步物理時鐘,研究者們還關(guān)注如何增強(qiáng)時間發(fā)號器的可擴(kuò)展性.布朗大學(xué)提出的分布式數(shù)據(jù)庫NAM-DB[33]沒有取消集中式的時間發(fā)號器,它通過RDMA提供的遠(yuǎn)程讀寫原語優(yōu)化了時間發(fā)號器的可擴(kuò)展性.NAM-DB將原本時間發(fā)號器的單一變量擴(kuò)展成N個變量,每個變量代表一個節(jié)點(diǎn),整個變量組構(gòu)成一個時鐘向量.某節(jié)點(diǎn)請求獲得一個數(shù)據(jù)版本時間戳?xí)r,只需遠(yuǎn)程修改時間發(fā)號器對應(yīng)的變量即可,而為事務(wù)獲得開始時間戳?xí)r,需要遠(yuǎn)程讀取整個向量時鐘.節(jié)點(diǎn)通過比較單個變量和整個向量時鐘,就可以獲得正確的邏輯順序.讀取、修改遠(yuǎn)端時間發(fā)號器變量可以利用RDMA提供的遠(yuǎn)程讀寫原語實現(xiàn),該原語繞過了遠(yuǎn)端CPU,直接讀寫遠(yuǎn)端內(nèi)存,這將瓶頸從CPU端轉(zhuǎn)移到網(wǎng)卡端,提升了時間發(fā)號器的擴(kuò)展性. 實驗結(jié)果顯示該發(fā)號器可以支持到500臺服務(wù)器的集群規(guī)模.但是,NAM-DB的缺點(diǎn)是只能實現(xiàn)快照隔離性,不能實現(xiàn)可串行化和嚴(yán)格可串行化的隔離等級.

瑞士聯(lián)邦理工學(xué)院提出的Clock-SI[47]同樣是一個實現(xiàn)了快照隔離性的時鐘同步方案,它沒有一個中心化的時間發(fā)號器,每個節(jié)點(diǎn)都可以作為事務(wù)的協(xié)調(diào)者記錄時間戳,所有的節(jié)點(diǎn)之間采用松散同步時鐘(loosely synchronized clock)同步物理時間,即不借助額外的時鐘同步技術(shù)同步節(jié)點(diǎn)之間的物理時間.Clock-SI通過精心設(shè)計事務(wù)協(xié)議來避免松散同步時鐘的不一致性影響事務(wù)快照讀的正確性.Clock-SI的協(xié)議規(guī)定,當(dāng)一個事務(wù)讀取一個遠(yuǎn)端節(jié)點(diǎn)的數(shù)據(jù)時,會提前獲取本地時間戳T作為事務(wù)的快照時間戳,并將T和遠(yuǎn)端節(jié)點(diǎn)正在提交或已經(jīng)提交的事務(wù)的時間戳比較,只有當(dāng)T大于這些事務(wù)的時間戳?xí)r,才會返回讀請求.通過推遲讀請求的返回,Clock-SI借助一個完全分布式的時鐘實現(xiàn)了支持快照隔離性的事務(wù)系統(tǒng).雖然Clock-SI實現(xiàn)在硬盤事務(wù)系統(tǒng)上,但其引入的分布式時間發(fā)號器的做法也可以遷移到內(nèi)存事務(wù)中.Clock-SI的缺點(diǎn)是讀阻塞的時間取決于節(jié)點(diǎn)之間的時鐘偏移,如果時鐘偏差過大會降低只讀事務(wù)的性能.

DST[37]是上海交通大學(xué)提出的一個分布式時鐘方案,它發(fā)現(xiàn)目前的并發(fā)控制協(xié)議如OCC或2PL已經(jīng)通過數(shù)據(jù)間的沖突給出了一個事務(wù)之間可串行化的順序,它通過在并發(fā)控制協(xié)議中捎帶傳輸這個順序,維護(hù)了一個可擴(kuò)展的分布式時間戳.具體做法是,DST為每個事務(wù)在開始時分配一個本地時間戳,當(dāng)該事務(wù)在訪問遠(yuǎn)端數(shù)據(jù)時,同時獲取遠(yuǎn)端數(shù)據(jù)的時間戳,最后取遠(yuǎn)端時間戳和本地時間戳的最大值為該事務(wù)的提交時間戳.這種方案保證了一個事務(wù)如果讀寫其他事務(wù)的修改,就會被串行化到這些事務(wù)之后.文獻(xiàn)[37]的作者將DST分別部署在OCC和2PL這2種協(xié)議上,通過DST使原有協(xié)議支持了數(shù)據(jù)的多版本機(jī)制,進(jìn)而支持了一致的快照讀,并控制快照讀獲取的數(shù)據(jù)的滯后時間不超過2倍的集群中最大物理時鐘偏移.

Silo[40]是麻省理工學(xué)院設(shè)計的基于多核機(jī)器的內(nèi)存數(shù)據(jù)庫,較早地提出了通過減少時間戳分配次數(shù)、分批處理事務(wù)的方式解決該問題.Silo以40 ms為1個時間片分配1個時間戳,不同時間片之間的事務(wù)保證嚴(yán)格可串行化,同一時間片內(nèi)的事務(wù)保證可串行化,但無法顯式地表達(dá)執(zhí)行順序.如果用戶要求嚴(yán)格可串行化,Silo支持推遲事務(wù)的完成時間以滿足該性質(zhì).通過這樣的權(quán)衡,Silo降低了時間發(fā)號器的競爭,提升了系統(tǒng)的吞吐率. 表2對以上5種時間戳分配技術(shù)進(jìn)行了總結(jié)對比.

2) 減少熱點(diǎn)數(shù)據(jù)競爭

熱點(diǎn)數(shù)據(jù)在分布式系統(tǒng)中廣泛存在,如何減少熱點(diǎn)數(shù)據(jù)競爭、實現(xiàn)負(fù)載均衡是事務(wù)內(nèi)存設(shè)計普遍面臨的問題.緩存是解決熱點(diǎn)數(shù)據(jù)競爭的常見手段,通過緩存讀寫數(shù)據(jù)既降低訪存延遲,也減少熱點(diǎn)數(shù)據(jù)的訪問量.在內(nèi)存事務(wù)中利用緩存需要注重保證緩存一致性.麻省理工學(xué)院提出的分布式內(nèi)存并發(fā)控制協(xié)議Sundial[35]將并發(fā)控制和緩存結(jié)合,利用緩存來降低遠(yuǎn)程訪問的開銷.Sundial對于每個數(shù)據(jù)對象引入了租約機(jī)制,在數(shù)據(jù)從遠(yuǎn)端緩存到本地的同時獲得一個租約的期限,協(xié)議保證租約期限內(nèi)數(shù)據(jù)的有效性.緩存協(xié)議要求節(jié)點(diǎn)對數(shù)據(jù)的修改以寫通過的方式更新,即節(jié)點(diǎn)更新本地緩存的同時需要對遠(yuǎn)端數(shù)據(jù)進(jìn)行修改.租約的引入避免了傳統(tǒng)緩存協(xié)議中由于數(shù)據(jù)不斷更新而產(chǎn)生頻繁的緩存無效,提升緩存命中率的同時減少了節(jié)點(diǎn)間的通信次數(shù).DrTM是一個結(jié)合RDMA和HTM的分布式事務(wù)處理系統(tǒng)[30],它在應(yīng)用緩存技術(shù)時充分考慮了RDMA技術(shù)延遲低、繞過遠(yuǎn)端CPU的特點(diǎn).DrTM在讀寫遠(yuǎn)端數(shù)據(jù)時通過RDMA的遠(yuǎn)程讀寫原語完成查找索引、讀寫數(shù)據(jù)的操作.在分布式系統(tǒng)中維護(hù)緩存一致性需要較大開銷,相比熱點(diǎn)數(shù)據(jù),熱點(diǎn)的索引結(jié)構(gòu)更容易被多節(jié)點(diǎn)頻繁訪問成為瓶頸.同時RDMA遠(yuǎn)程訪問比普通網(wǎng)絡(luò)帶寬更高,DrTM選擇緩存數(shù)據(jù)存放位置而不是數(shù)據(jù)本身,降低了熱點(diǎn)數(shù)據(jù)的查找開銷并保證了數(shù)據(jù)對于所有節(jié)點(diǎn)的透明性,充分利用了RDMA技術(shù)的帶寬優(yōu)勢.

Table 2 Comparison of Timestamp Allocation Techniques表2 時間戳分配技術(shù)對比

除了使用緩存,還可以將數(shù)據(jù)競爭分?jǐn)偟讲煌墓?jié)點(diǎn)或線程上.多核內(nèi)存數(shù)據(jù)庫Doppel[41]通過本地維護(hù)熱點(diǎn)數(shù)據(jù)的副本實現(xiàn)多核之間的負(fù)載分?jǐn)?Doppel對于數(shù)據(jù)的更新記錄在本地線程綁定的內(nèi)存中,避免跨NUMA節(jié)點(diǎn)訪問引起的開銷.當(dāng)有事務(wù)想要讀取這些數(shù)據(jù)時,Doppel會推遲這些讀請求,在收集讀請求數(shù)目達(dá)到閾值后,對分散在各線程上的數(shù)據(jù)進(jìn)行歸并整合,并返回這些讀請求.需要注意的是,Doppel需要數(shù)據(jù)的更新操作滿足交換律時,才能支持事務(wù)進(jìn)行數(shù)據(jù)熱點(diǎn)的負(fù)載分?jǐn)?

Bamboo[46]是一個基于傳統(tǒng)2階段鎖優(yōu)化的并發(fā)控制協(xié)議.對于熱點(diǎn)數(shù)據(jù)的持鎖更新會阻塞其他事務(wù)的執(zhí)行,而2階段鎖要求事務(wù)在釋放任何數(shù)據(jù)的鎖之前必須獲得事務(wù)執(zhí)行需要的所有數(shù)據(jù)的鎖,這進(jìn)一步加劇了熱點(diǎn)數(shù)據(jù)上的沖突和阻塞.Bamboo允許事務(wù)在2階段鎖過程中對于數(shù)據(jù)提前釋放鎖,即允許某些事務(wù)讀取尚未提交的“臟數(shù)據(jù)”.同時為了保證可串行化的隔離等級,Bamboo會利用鎖表記錄這種數(shù)據(jù)間的依賴,當(dāng)事務(wù)中止時對相關(guān)事務(wù)進(jìn)行級聯(lián)中止.但是,級聯(lián)中止會使事務(wù)之間產(chǎn)生長依賴鏈,一旦出現(xiàn)會造成大量事務(wù)回滾,對于吞吐影響巨大.Bamboo通過理論分析指出了級聯(lián)中止的劣勢和提前放鎖的增益之間的臨界點(diǎn),并說明當(dāng)數(shù)據(jù)庫系統(tǒng)內(nèi)數(shù)據(jù)規(guī)模遠(yuǎn)大于系統(tǒng)正在運(yùn)行事務(wù)數(shù)量和事務(wù)訪存規(guī)模時,Bamboo的方案會取得性能優(yōu)勢.

3.2 利用新硬件加速事務(wù)處理

網(wǎng)絡(luò)、存儲能力的提升幫助分布式內(nèi)存事務(wù)的延遲達(dá)到了亞微秒級別.面對新型硬件及技術(shù),設(shè)計更適合的并發(fā)控制協(xié)議及事務(wù)系統(tǒng)架構(gòu)、最大程度發(fā)揮它們的性能優(yōu)勢是系統(tǒng)設(shè)計者的當(dāng)務(wù)之急.

1) 改進(jìn)并發(fā)控制協(xié)議及事務(wù)系統(tǒng)架構(gòu)

Fig. 3 Transaction processing in FaRM圖3 FaRM的事務(wù)處理流程

傳統(tǒng)的并發(fā)控制協(xié)議為事務(wù)調(diào)度者設(shè)計了復(fù)雜的調(diào)度協(xié)議.FaRM是Microsoft提出的一個基于RDMA的分布式計算平臺[27-28],提供基于分布式事務(wù)的共享內(nèi)存讀寫接口,它簡化了協(xié)議并將RDMA技術(shù)運(yùn)用到并發(fā)控制中.FaRM事務(wù)的執(zhí)行分為執(zhí)行和提交階段,圖3包括1個事務(wù)調(diào)度者C,3個事務(wù)參與者P1,P2,P3以及備份節(jié)點(diǎn)B1,B2,B3.在執(zhí)行階段,事務(wù)調(diào)度者C遠(yuǎn)程讀取參與者P1,P2,P3的數(shù)據(jù),并執(zhí)行事務(wù)的相應(yīng)邏輯,將數(shù)據(jù)的修改保存在本地.在提交階段,FaRM對事務(wù)的寫集數(shù)據(jù)通過遠(yuǎn)程過程調(diào)用向數(shù)據(jù)所在節(jié)點(diǎn)P1,P2申請鎖并同時驗證相應(yīng)讀集的數(shù)據(jù),在獲得所有寫集的鎖后,向包含數(shù)據(jù)僅屬于讀集的節(jié)點(diǎn)P3發(fā)送請求,驗證讀集數(shù)據(jù)是否被修改.如果數(shù)據(jù)版本一致,則事務(wù)可以繼續(xù),調(diào)度者將數(shù)據(jù)的修改依次發(fā)送給各備份節(jié)點(diǎn)(B1,B2)及主節(jié)點(diǎn)(P1,P2),并提交給上層應(yīng)用.FaRM讀取數(shù)據(jù)使用了RDMA的read原語,避免在關(guān)鍵路徑上引入遠(yuǎn)端CPU,節(jié)省了遠(yuǎn)端CPU開銷,發(fā)揮了RDMA的優(yōu)勢.

布朗大學(xué)的研究者分析了已有內(nèi)存事務(wù)架構(gòu)的不足：shared-nothing架構(gòu)為了避免網(wǎng)絡(luò)通信,節(jié)點(diǎn)之間不共享數(shù)據(jù),這難以滿足目前真實應(yīng)用涉及數(shù)據(jù)眾多、數(shù)據(jù)訪問特征變化頻繁的特點(diǎn);shared-memory架構(gòu)需要成熟的緩存一致性協(xié)議,這是一般事務(wù)系統(tǒng)不具備的,另外事務(wù)管理模塊往往希望能對內(nèi)存數(shù)據(jù)進(jìn)行全方位的管理,而shared-memory只能提供有限的接口.因此他們提出了適用于RDMA網(wǎng)絡(luò)的NAM架構(gòu)[48].NAM架構(gòu)分離了計算節(jié)點(diǎn)和存儲節(jié)點(diǎn),計算節(jié)點(diǎn)負(fù)責(zé)事務(wù)的執(zhí)行邏輯,存儲節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的存儲、響應(yīng)讀寫數(shù)據(jù)的請求.相比于之前的架構(gòu),存儲層可以獨(dú)立于計算節(jié)點(diǎn)支持更大規(guī)模的擴(kuò)展,且存儲層可以嵌入負(fù)載平衡策略動態(tài)支持?jǐn)?shù)據(jù)遷移.NAM架構(gòu)在存儲節(jié)點(diǎn)之間交互數(shù)據(jù)時使用RDMA單邊操作,減少了存儲層的CPU使用率.

2) 充分發(fā)揮RDMA性能特性

RDMA技術(shù)的迅速發(fā)展促進(jìn)了更多關(guān)于內(nèi)存事務(wù)通信優(yōu)化的研究.研究發(fā)現(xiàn)在分布式場景中使用RDMA進(jìn)行通信,網(wǎng)卡管理的通信鏈路越多,網(wǎng)卡的緩存命中率就越低,通信延遲越高,吞吐率越低.因此,卡內(nèi)基梅隆大學(xué)的Kalia等人[31]提出在節(jié)點(diǎn)較多的數(shù)據(jù)中心中,使用RDMA的UD模式代替常用的RC模式.UD模式可以利用較少的通信鏈路實現(xiàn)任意節(jié)點(diǎn)之間的通信,網(wǎng)卡吞吐率不受節(jié)點(diǎn)擴(kuò)展的影響.UD模式的局限在于底層無擁塞控制邏輯,但是他們聲稱在實際數(shù)據(jù)中心的測試中丟包的現(xiàn)象根本不會出現(xiàn).所以他們設(shè)計了分布式事務(wù)系統(tǒng)FaSST,采用RDMA的UD send原語代替RC read/write,以FaRM的并發(fā)控制協(xié)議為基礎(chǔ)設(shè)計了分布式內(nèi)存事務(wù)系統(tǒng),在OLTP負(fù)載下吞吐率達(dá)到FaRM的1.87倍.然而,僅從性能的角度考慮RDMA技術(shù)的應(yīng)用不夠全面,內(nèi)存占用、CPU使用率等指標(biāo)同樣應(yīng)該納入系統(tǒng)的評價中,而后兩者更能得益于RDMA提供的獨(dú)特的單邊原語操作.

DrTM+H是上海交通大學(xué)提出的一個混合分布式事務(wù)系統(tǒng)[34],嘗試在事務(wù)運(yùn)行的每個階段都選擇最適合的RDMA操作來縮短事務(wù)的執(zhí)行時間.DrTM+H以O(shè)CC為并發(fā)控制協(xié)議,將事務(wù)的運(yùn)行分為執(zhí)行、驗證、日志記錄和提交4個階段.RDMA的操作包括單邊操作RDMA read/write、單邊原子操作RDMA CAS和雙邊操作RDMA send(即RPC調(diào)用,遠(yuǎn)端CPU配合執(zhí)行相應(yīng)讀寫并返回結(jié)果).在執(zhí)行階段,采用單邊操作RDMA read和雙邊操作RDMA send結(jié)合的方式更加高效,當(dāng)本地緩存了遠(yuǎn)端數(shù)據(jù)位置時,通過單邊操作可以在一個往返時延中獲取數(shù)據(jù),反之,則應(yīng)該盡早讓遠(yuǎn)端CPU介入尋找數(shù)據(jù);在驗證階段,使用RDMA read和RDMA CAS更合適,因為需要驗證的數(shù)據(jù)位置之前往往已經(jīng)被緩存了;在記錄日志階段,簡單的記錄日志操作可以直接由RDMA write完成,無需引入遠(yuǎn)端CPU;在提交階段,雙邊操作可以通過捎帶信息的方式合并請求和回復(fù)的信息,減少通信次數(shù),因此比單邊操作更適合本階段.

3.3 降低事務(wù)中止概率

事務(wù)在并發(fā)執(zhí)行中由于數(shù)據(jù)競爭會產(chǎn)生資源等待.為了避免資源的循環(huán)等待導(dǎo)致的死鎖,大部分并發(fā)控制協(xié)議會在資源競爭時中止某個事務(wù)以保證其他事務(wù)的順利執(zhí)行,被中止的事務(wù)則會在等待一段時間后重新發(fā)起該事務(wù).事務(wù)頻繁中止不僅會影響系統(tǒng)的吞吐率,還可能出現(xiàn)事務(wù)“饑餓”的問題.減少事務(wù)的中止概率對于內(nèi)存事務(wù)系統(tǒng)十分重要.

1) 采取更加靈活的提交策略

傳統(tǒng)基于時間戳的內(nèi)存事務(wù)系統(tǒng)會在事務(wù)的提交階段獲取提交時間戳并驗證事務(wù)是否能提交,一旦發(fā)現(xiàn)數(shù)據(jù)不一致,則事務(wù)中止.這種確定性的事務(wù)執(zhí)行流程造成了很多“虛假”沖突,實際上系統(tǒng)可以為并發(fā)的事務(wù)確定可串行化順序.圖4有2個事務(wù)A,B和2個數(shù)據(jù)x,y,縱軸代表了邏輯時間.事務(wù)B在事務(wù)A讀x后寫x并成功提交.在事務(wù)B提交后,事務(wù)A寫y并準(zhǔn)備提交,系統(tǒng)發(fā)現(xiàn)此時x已經(jīng)被B修改過,驗證失敗,事務(wù)A被中止.實際上,系統(tǒng)可以將事務(wù)A的提交時間點(diǎn)提前到時刻1,即在串行化順序中先完成事務(wù)A后完成事務(wù)B,避免了事務(wù)A的中止.麻省理工學(xué)院提出的新型樂觀并發(fā)控制協(xié)議TicToc[42]利用了這個特點(diǎn),標(biāo)記了每個數(shù)據(jù)的有效時間區(qū)間.事務(wù)在執(zhí)行階段會獲得相應(yīng)數(shù)據(jù)的有效時間區(qū)間.當(dāng)事務(wù)進(jìn)入提交階段,事務(wù)會對所有獲得的有效時間區(qū)間求并集,若并集不為空,則可以選擇并集內(nèi)任一時間作為提交時間點(diǎn)順利提交,否則需要進(jìn)一步驗證.TicToc通過在事務(wù)提交階段靈活確定事務(wù)提交時間點(diǎn)降低了事務(wù)的中止率.此外,TicToc還使用邏輯時間代替物理時間標(biāo)記有效時間區(qū)間,避免了使用時間發(fā)號器帶來的擴(kuò)展性問題.實驗顯示TicToc相比傳統(tǒng)基于樂觀并發(fā)控制協(xié)議的事務(wù)系統(tǒng)降低了3.3倍的事務(wù)中止率.TicToc靈活地選取了事務(wù)的提交時間,本質(zhì)上是通過弱化事務(wù)提供的隔離等級來降低事務(wù)中止率.

Fig. 4 An example of transaction executing using TicToc圖4 TicToc中事務(wù)執(zhí)行例子

香港大學(xué)提出的地理上分布的事務(wù)系統(tǒng)DAST[38]側(cè)重通過推后提交時間解決事務(wù)的延遲問題.跨地域事務(wù)由于涉及多個數(shù)據(jù)中心,一旦中止重試延遲增加明顯;本地域事務(wù)的執(zhí)行,由于跨地域事務(wù)執(zhí)行時間長,會被阻塞導(dǎo)致延遲上升.因此,DAST提出了一種靈活的提交策略,通過推后跨地域事務(wù)的提交時間避免其重試.跨地域事務(wù)先通過一個準(zhǔn)備階段,讓事務(wù)的參與者獨(dú)立地預(yù)估該事務(wù)在本節(jié)點(diǎn)的提交時間,事務(wù)選取預(yù)估提交時間的最大值作為真實提交時間.預(yù)估時間保證了跨地域事務(wù)不會因為生成過小的時間戳導(dǎo)致中止.對于本地域事務(wù),生成對應(yīng)的邏輯時間戳,支持其在跨地域事務(wù)執(zhí)行之前穿插執(zhí)行,以避免其被跨地域事務(wù)阻塞.通過這2個技術(shù),DAST最高降低了跨地域事務(wù)70.4%的尾延遲以及本地域事務(wù)93.2%的尾延遲.

2) 提供多版本避免事務(wù)中止

單版本的樂觀并發(fā)控制協(xié)議被廣為詬病的問題是頻繁的事務(wù)中止.對于只讀事務(wù),單版本協(xié)議往往需要2次讀取讀集的數(shù)據(jù),才能正確提交事務(wù).多版本協(xié)議對于一個數(shù)據(jù)維護(hù)了多個歷史版本,處理只讀事務(wù)時,讀取小于只讀事務(wù)提交時間戳的最新版本的數(shù)據(jù)就可以滿足數(shù)據(jù)的一致性.因此,多版本協(xié)議通過支持讀取歷史版本降低事務(wù)中止率,對讀密集的負(fù)載更友好.

Hekaton[39]是早期多版本技術(shù)在內(nèi)存數(shù)據(jù)庫中的重要嘗試,它通過3階段提交實現(xiàn)了多版本并發(fā)控制協(xié)議.Hekaton避免了數(shù)據(jù)上的鎖結(jié)構(gòu)(如自旋鎖),采用原子指令CAS保證數(shù)據(jù)一致.在數(shù)據(jù)布局上,數(shù)據(jù)按線程物理地劃分,每個線程作為事務(wù)執(zhí)行主體,維護(hù)事務(wù)的狀態(tài)及日志信息.對于每個數(shù)據(jù)版本,Hekaton維護(hù)了它的開始時間和結(jié)束時間.然而,Hekaton維護(hù)多版本時采用的鏈表結(jié)構(gòu)降低了緩存命中率,并產(chǎn)生了較大的存儲和計算開銷.同時,Hekaton在讀取未提交事務(wù)修改的數(shù)據(jù)時采取的預(yù)測讀策略引入了事務(wù)級聯(lián)中止的問題.

Cicada是卡內(nèi)基梅隆大學(xué)設(shè)計的多核內(nèi)存數(shù)據(jù)庫[43],針對傳統(tǒng)多版本事務(wù)系統(tǒng)提出了一些解決方案.①盡力而為地將事務(wù)最頻繁訪問的數(shù)據(jù)版本緩存在固定位置,增加版本遍歷的一次命中率.②采取了“早中止”策略,通過維護(hù)更多數(shù)據(jù)版本信息,在事務(wù)執(zhí)行和驗證階段盡早判斷事務(wù)是否會由于沖突中止.③通過自學(xué)習(xí)的方式確定事務(wù)中止后的重試時間避免事務(wù)頻繁重試導(dǎo)致的中止率的提升.Cicada在多核場景中相比其他系統(tǒng)取得了3倍的吞吐率提升,但是其仍存在部分問題.Cicada的時間戳分配方案使得事務(wù)的執(zhí)行無法滿足嚴(yán)格的物理時間序,甚至?xí)霈F(xiàn)一個線程讀不到本線程已提交事務(wù)的情況.

然而,在分布式場景中多版本并發(fā)控制協(xié)議并不是主流實現(xiàn).這是因為頻繁地比較、修改數(shù)據(jù)的版本號等信息會增加節(jié)點(diǎn)之間的交互次數(shù),相比于多核間的跨核訪問,網(wǎng)絡(luò)通信開銷更大,如何在分布式場景中簡化多版本并發(fā)控制協(xié)議,是系統(tǒng)設(shè)計者亟待解決的難題.

3) 在硬件事務(wù)內(nèi)存中減少事務(wù)中止次數(shù)

DrTM嘗試在基于硬件事務(wù)內(nèi)存的分布式事務(wù)系統(tǒng)中降低事務(wù)的中止概率.RTM作為英特爾的硬件事務(wù)內(nèi)存產(chǎn)品,通過CPU的私有緩存追蹤事務(wù)讀寫集,將事務(wù)的支持下沉到硬件層面.然而,RTM對于分布式事務(wù)的支持非常局限,因為網(wǎng)絡(luò)I/O會中止本地RTM正在執(zhí)行的事務(wù).為了減少分布式事務(wù)執(zhí)行的中止率,DrTM采用2PL協(xié)議,通過RDMA將遠(yuǎn)程的讀寫集數(shù)據(jù)加鎖并搜集到本地,再通過RTM執(zhí)行本地事務(wù),最后將遠(yuǎn)程的修改通過RDMA寫回.這種方式可以避免RTM執(zhí)行事務(wù)時需要訪問遠(yuǎn)端數(shù)據(jù)而中止事務(wù).更進(jìn)一步,DrTM+R[32]針對DrTM中存在的讀寫集必須在事務(wù)執(zhí)行前提前確定的問題,基于OCC修改了分布式事務(wù)協(xié)議,在執(zhí)行階段確定讀寫集,在提交階段進(jìn)行驗證提交.此外,還有一些工作針對RTM讀寫集大小受限的問題進(jìn)行了探索,提出了拆分讀寫集、只用RTM保護(hù)元數(shù)據(jù)等方法.這些工作都從降低硬件事務(wù)內(nèi)存中止率的角度出發(fā)優(yōu)化內(nèi)存事務(wù).

4) 中止后保證透明性避免重試事務(wù)再次中止

FaRM v2分布式事務(wù)系統(tǒng)聚焦于為事務(wù)使用者提供透明性的保證.成功提交的事務(wù)往往能保證讀取數(shù)據(jù)的一致性,但是中止的事務(wù)卻無法滿足這一點(diǎn).在樂觀并發(fā)控制協(xié)議中,大部分事務(wù)的中止源于版本驗證失敗,這表示事務(wù)在中止后向上層應(yīng)用提供的是不一致的讀數(shù)據(jù).用戶難以通過不一致的數(shù)據(jù)判斷事務(wù)中止的具體原因,很可能造成之后重試的事務(wù)再次中止,加重系統(tǒng)不必要的負(fù)擔(dān).FaRM v2將FaRM的單版本協(xié)議改進(jìn)為多版本協(xié)議,在事務(wù)的開始階段分配時間戳,事務(wù)讀取數(shù)據(jù)時依據(jù)該時間戳,在所讀數(shù)據(jù)的歷史版本中尋找舊于該時間戳的最新版本數(shù)據(jù),保證事務(wù)讀到系統(tǒng)在該時間戳的快照.即使事務(wù)在執(zhí)行階段提前中止或在提交階段因為驗證失敗而中止,事務(wù)所讀到的數(shù)據(jù)都能保持一致性.FaRM v2這種分布式多版本事務(wù)系統(tǒng)和Cicada這種單機(jī)多版本數(shù)據(jù)庫的最大區(qū)別在于：前者是在分布式OCC協(xié)議基礎(chǔ)上進(jìn)行延伸,通過多版本支持一致的快照讀和透明性；后者是以時間戳為并發(fā)控制協(xié)議的核心,利用時間戳標(biāo)記多個數(shù)據(jù)版本,以解決數(shù)據(jù)間的沖突.

3.4 高效保證事務(wù)持久性

實現(xiàn)內(nèi)存事務(wù)的持久性需要事務(wù)將數(shù)據(jù)的修改記錄在持久性介質(zhì)中.磁盤或固態(tài)盤作為持久性介質(zhì),已經(jīng)無法匹配內(nèi)存事務(wù)的執(zhí)行速度,難以提供高速的持久化解決方案;在分布式場景中,并發(fā)控制協(xié)議也需要協(xié)調(diào)各個節(jié)點(diǎn)所持久化的數(shù)據(jù),保證機(jī)器損壞、掉電后數(shù)據(jù)的持久性和系統(tǒng)的可用性.

1) 利用NVM為單機(jī)事務(wù)保證持久性

傳統(tǒng)基于硬盤的內(nèi)存事務(wù)持久化方案無法滿足如今上層應(yīng)用的性能需求,NVM的出現(xiàn)和相關(guān)產(chǎn)品的問世給單機(jī)事務(wù)的持久化帶來了機(jī)遇.NVM具有延遲低、支持字節(jié)粒度尋址、掉電不易失的特性,但直接用NVM替換內(nèi)存是不可取的.持久化數(shù)據(jù)到NVM上需要調(diào)用持久化指令(如CLFLUSHOPT,CLWB指令)將數(shù)據(jù)從CPU緩存刷寫到NVM,再通過內(nèi)存柵欄指令(如SFENCE)保證指令順序執(zhí)行,2種指令的序列化操作增加了開銷.數(shù)據(jù)的持久化可以采用日志寫的方法,包括撤銷日志(undo log)和重做日志(redo log),保證日志持久化到NVM.清華大學(xué)提出的持久化事務(wù)架構(gòu)DUDETM[44]結(jié)合2種日志的特點(diǎn),將事務(wù)的持久化拆解為執(zhí)行、持久、再現(xiàn)3個獨(dú)立步驟,異步批量處理完成持久化,減少了持久化指令和內(nèi)存柵欄指令這2種指令次數(shù),提升持久化事務(wù)吞吐率.但是,DUDETM中存在再現(xiàn)線程不可擴(kuò)展的問題.針對這一問題,上海交通大學(xué)提出的持久化事務(wù)內(nèi)存Pisces[45]采用雙版本并發(fā)控制,將數(shù)據(jù)的日志作為一個臨時副本,減少維護(hù)多版本存在的空間和查找開銷.此外,Pisces采用3階段提交協(xié)議,將事務(wù)的提交劃分成持久化、并發(fā)提交、寫回3階段,讓數(shù)據(jù)更新的持久化在提交第1階段完成,并發(fā)提交階段事務(wù)原子地獲取提交時間戳進(jìn)行提交,在寫回階段事務(wù)將持久化的數(shù)據(jù)更新日志寫回數(shù)據(jù)原地.

加州大學(xué)默塞德分校的研究者們針對基于NVM的內(nèi)存事務(wù)性能進(jìn)行了優(yōu)化,提出了ArchTM[49]. 利用NVM實現(xiàn)事務(wù)持久性的方法有2種,記錄日志和異地更新,前者會寫2倍的數(shù)據(jù)增加對NVM的負(fù)載,后者由于元數(shù)據(jù)更新產(chǎn)生的隨機(jī)小寫請求不符合NVM擅長的訪存特性. 因此,ArchTM提出了將元數(shù)據(jù)更新放置于內(nèi)存中,將事務(wù)的更新以異地寫的方式保存在NVM中的策略. 為了保證持久性,ArchTM在每個數(shù)據(jù)上都標(biāo)記了其版本對應(yīng)的事務(wù)序號,用于事務(wù)系統(tǒng)的崩潰恢復(fù);為了將事務(wù)系統(tǒng)對NVM的寫聚合成NVM擅長的順序?qū)?ArchTM設(shè)計了全局空閑空間隊列和后臺定期整理碎片的機(jī)制,將一起到來的空間分配請求盡量分配到連續(xù)NVM空間,提高事務(wù)性能.

2) 利用副本為分布式事務(wù)保證持久性

在分布式場景中,副本是保證數(shù)據(jù)持久性最常見的手段.相比文件系統(tǒng)、鍵值存儲的副本策略,事務(wù)系統(tǒng)的持久化對一致性的要求更高,很多要求在事務(wù)執(zhí)行過程中完成持久化操作.Spanner借助Paxos共識協(xié)議實現(xiàn)了多個副本數(shù)據(jù)的強(qiáng)一致性,并將持久化時間隱藏在分配時間戳的休眠時間中.FaRM采用主從備份的方案,每個節(jié)點(diǎn)組利用f+1個節(jié)點(diǎn)容納f個錯誤.如圖3中,在提交階段先將事務(wù)的修改提交給各備份節(jié)點(diǎn),當(dāng)收到所有的確認(rèn)消息后,再提交給數(shù)據(jù)的主節(jié)點(diǎn),完成事務(wù)的持久化.在事務(wù)提交到所有備份節(jié)點(diǎn)后,FaRM要求事務(wù)必須在一個主節(jié)點(diǎn)成功提交后才能向上層提交,這是為了保證在每個節(jié)點(diǎn)組都出現(xiàn)f個錯誤后已提交的事務(wù)仍能順利恢復(fù).如果提前向上層提交事務(wù),恢復(fù)后可能丟失事務(wù)已經(jīng)通過驗證階段的信息,進(jìn)而中止已提交的事務(wù).

與前2例不同,華盛頓大學(xué)通過獨(dú)特的思路解決事務(wù)持久化問題.他們認(rèn)為在事務(wù)系統(tǒng)保證強(qiáng)一致性的前提下,再使用共識協(xié)議保證副本的一致性是一種過度的保護(hù),會影響系統(tǒng)的吞吐率.他們提出的事務(wù)并發(fā)控制協(xié)議TAPIR[29]基于弱一致性的副本協(xié)議,每個節(jié)點(diǎn)組沒有中心化的協(xié)調(diào)者.客戶端作為事務(wù)的協(xié)調(diào)者,將事務(wù)的讀發(fā)送到節(jié)點(diǎn)組中距離最近的節(jié)點(diǎn)上,寫緩存在本地,在提交階段再分發(fā)給節(jié)點(diǎn)組中的所有節(jié)點(diǎn).在事務(wù)的提交階段,TAPIR利用時間戳作為依據(jù),要求副本節(jié)點(diǎn)對事務(wù)的操作順序達(dá)成共識.通過這樣的協(xié)議,在常規(guī)路徑下,TAPIR將Spanner中事務(wù)執(zhí)行的至少2個往返時延(Spanner中操作由事務(wù)調(diào)度者發(fā)送給事務(wù)參與者,再由事務(wù)參與者發(fā)送給備份節(jié)點(diǎn))減少到1個往返時延(直接由事務(wù)調(diào)度者發(fā)送給所有事務(wù)參與者及備份節(jié)點(diǎn)).

3.5 實驗驗證

為了展示不同并發(fā)控制協(xié)議對于內(nèi)存事務(wù)性能的影響,本節(jié)以開源數(shù)據(jù)庫Deneva[14]為例進(jìn)行了性能實驗.Deneva數(shù)據(jù)庫采用以太網(wǎng)傳輸,為適配新興網(wǎng)絡(luò)技術(shù),我們重構(gòu)了Deneva的網(wǎng)絡(luò)傳輸層,使用基于Infiniband網(wǎng)絡(luò)的RDMA技術(shù)進(jìn)行消息通信.我們使用4臺服務(wù)器測試了數(shù)據(jù)庫常用的YCSB[50]和TPC-C[51]兩種負(fù)載.

圖5展示了5種并發(fā)控制協(xié)議在YCSB負(fù)載中隨偏移因子變化的系統(tǒng)吞吐,偏移因子越大代表數(shù)據(jù)的沖突越密集.在數(shù)據(jù)訪問較均衡時,5種協(xié)議的性能相近.當(dāng)數(shù)據(jù)沖突初步增加后,基于時間戳的5種并發(fā)控制協(xié)議TIMESTAMP和MVCC性能優(yōu)異,這得益于它們在執(zhí)行過程中避免了持鎖的臨界區(qū),允許事務(wù)在不違反隔離等級的前提下以對應(yīng)的時間戳插入串行化序列中.當(dāng)數(shù)據(jù)沖突進(jìn)一步升級后,事務(wù)中止率上升,系統(tǒng)吞吐下降,各種并發(fā)控制協(xié)議的性能表現(xiàn)趨同.

Fig. 5 Throughput when varying the skew factor in YCSB圖5 YCSB中偏移因子變化下的吞吐性能

圖6展示了各種協(xié)議執(zhí)行TPC-C負(fù)載中2種事務(wù)new_order和payment的性能.這2種事務(wù)都包含對數(shù)據(jù)條目的讀—修改—寫,且執(zhí)行周期長.OCC的驗證由于執(zhí)行周期長而導(dǎo)致頻繁失敗,2PL由于持鎖時間長會阻塞其他事務(wù)的執(zhí)行,因此這2種協(xié)議性能低下;TIMESTAMP和MVCC在這種場景中表現(xiàn)優(yōu)異.

Fig. 6 Throughput of two kinds of transactions in TPC-C圖6 TPC-C中2種事務(wù)的吞吐性能

3.6 小 結(jié)

最近10年內(nèi)存事務(wù)的并發(fā)控制協(xié)議,都聚焦于性能、擴(kuò)展性、持久性這3個維度,從不同技術(shù)路線入手對并發(fā)控制協(xié)議進(jìn)行了探索.這些工作主要遵循2條設(shè)計思路:1)利用新型技術(shù)、設(shè)備去減少內(nèi)存事務(wù)系統(tǒng)中遇到的瓶頸,包括NAM-DB利用RDMA優(yōu)化中心時鐘、DrTM利用RTM實現(xiàn)高效的分布式事務(wù).它們充分分析并發(fā)控制協(xié)議中所遇到的瓶頸環(huán)節(jié),借助新技術(shù)提供的優(yōu)勢解決相關(guān)問題.2)使用已有技術(shù)去解決新場景中的相應(yīng)問題,包括Sundial利用緩存緩解熱點(diǎn)數(shù)據(jù)沖突、Cicada提供多版本減少事務(wù)中止次數(shù)等.隨著網(wǎng)絡(luò)、存儲能力的提升,原有的事務(wù)處理模型和事務(wù)系統(tǒng)變得低效,在并發(fā)控制協(xié)議里使用一些更加適應(yīng)當(dāng)前場景的技術(shù)可以取得較好的效果.此外,還有少量工作依據(jù)上層應(yīng)用或負(fù)載,對并發(fā)控制協(xié)議進(jìn)行針對性的優(yōu)化.

根據(jù)第1節(jié)提到的內(nèi)存事務(wù)并發(fā)控制協(xié)議目前面臨的3個挑戰(zhàn),現(xiàn)有技術(shù)的應(yīng)對方案可以進(jìn)行如下總結(jié).單機(jī)多核數(shù)據(jù)庫中跨分區(qū)事務(wù)不可避免地產(chǎn)生大量跨NUMA節(jié)點(diǎn)的訪問,降低事務(wù)中止概率(3.3節(jié))減少了事務(wù)中止后的重試次數(shù),降低了事務(wù)跨NUMA節(jié)點(diǎn)訪問次數(shù).這不僅減少了本事務(wù)的延遲,還通過減少跨核訪問次數(shù)減輕了該事務(wù)對其他資源競爭事務(wù)的沖突.分布式事務(wù)受集中控制點(diǎn)和數(shù)據(jù)熱點(diǎn)的制約難以擴(kuò)展,現(xiàn)有技術(shù)通過改進(jìn)時間戳分配(3.1.1節(jié))、并發(fā)控制協(xié)議及事務(wù)框架(3.2.1節(jié))將集中控制點(diǎn)移出事務(wù)的關(guān)鍵路徑,通過緩存、聚合請求、提前放鎖(3.1.2節(jié))和使用新硬件(3.2.2節(jié))等方式增加熱點(diǎn)數(shù)據(jù)的并發(fā).針對現(xiàn)有協(xié)議難以發(fā)揮新設(shè)備優(yōu)勢來保證高效的持久性,研究者從單機(jī)事務(wù)和分布式事務(wù)2個維度出發(fā),分別結(jié)合非易失內(nèi)存和副本重新設(shè)計并發(fā)控制協(xié)議并進(jìn)行相應(yīng)優(yōu)化(3.4節(jié)).

4 未來研究方向

隨著業(yè)務(wù)需求和使用場景的進(jìn)一步變化,內(nèi)存事務(wù)中一些問題會變得更加突出.結(jié)合本文提出的內(nèi)存事務(wù)面臨的挑戰(zhàn),其未來的研究熱點(diǎn)方向包括3點(diǎn)：

1) 設(shè)計感知負(fù)載特征的并發(fā)控制協(xié)議.短期內(nèi)服務(wù)器單機(jī)多核的架構(gòu)不會發(fā)生革命性的變動,跨NUMA節(jié)點(diǎn)的通信開銷仍是一個不可忽視的問題.目前已有不少工作從并發(fā)控制層面嘗試減少熱點(diǎn)數(shù)據(jù)的同步操作和跨NUMA的訪問,但是結(jié)合OLTP等上層負(fù)載特征優(yōu)化數(shù)據(jù)布局的思路還缺乏實踐.目前內(nèi)存事務(wù)系統(tǒng)多數(shù)采用物理分區(qū)的方式平均劃分?jǐn)?shù)據(jù),避免共享內(nèi)存的引入.這種方式減少了核間競爭,但帶來了多核、多節(jié)點(diǎn)負(fù)載不均的問題.面對不同負(fù)載,內(nèi)存事務(wù)系統(tǒng)應(yīng)當(dāng)支持更靈活的數(shù)據(jù)分布策略,針對負(fù)載熱點(diǎn)進(jìn)行相應(yīng)數(shù)據(jù)的動態(tài)遷移.如何在該場景中權(quán)衡遷移帶來的性能增益和一致性開銷,是研究者面臨的挑戰(zhàn).更進(jìn)一步,研究者可以結(jié)合負(fù)載特征設(shè)計混合、自適應(yīng)的并發(fā)控制協(xié)議,根據(jù)負(fù)載變化調(diào)整協(xié)議解決沖突的方式,如自適應(yīng)地使用鎖或時間戳解決沖突.2PL適合沖突頻繁的負(fù)載,OCC在短事務(wù)、較少沖突場景中性能更佳,MVCC適合讀事務(wù)主導(dǎo)的負(fù)載,系統(tǒng)可以結(jié)合各自協(xié)議特點(diǎn)適應(yīng)不同負(fù)載.

2) 解決地理上分布系統(tǒng)中事務(wù)的擴(kuò)展性問題.數(shù)據(jù)庫的擴(kuò)展性問題一直是研究者面臨的重要挑戰(zhàn),在初步解決了單核到多核、單機(jī)到分布式的擴(kuò)展性問題后,地理上分布數(shù)據(jù)庫的擴(kuò)展性受到了更多關(guān)注.容災(zāi)需求的發(fā)展迫使數(shù)據(jù)庫支持多地備份,而在單機(jī)或單個數(shù)據(jù)中心場景中,核間通信和網(wǎng)絡(luò)通信的開銷已經(jīng)減小,但是跨地域的網(wǎng)絡(luò)通信仍存在較大開銷.因此,地理上分布的數(shù)據(jù)庫不能接受集中控制點(diǎn)的設(shè)計,也難以在多次信息交互的協(xié)議中提供低延遲.Spanner為地理上分布的場景提出了一個解決方案,但存在跨地域交互過多、依賴物理硬件等不足,所以減少事務(wù)執(zhí)行時跨地域的網(wǎng)絡(luò)交互更加重要.未來的研究路線可以從3方面入手：①進(jìn)一步耦合并發(fā)控制協(xié)議和副本協(xié)議,從協(xié)議角度減少跨地域的交互,將關(guān)鍵路徑上的同步交互改為異步交互;②通過合理的數(shù)據(jù)布局減少跨地域事務(wù)的數(shù)量,利用多副本的讀寫帶寬,在保證一定程度一致性的前提下,靈活切換數(shù)據(jù)分布,多節(jié)點(diǎn)同時提供服務(wù);③通過NVM等高速存儲器件代替?zhèn)鹘y(tǒng)持久化介質(zhì),在跨地域事務(wù)執(zhí)行時提供持久化保證,加速事務(wù)的處理及災(zāi)后恢復(fù)進(jìn)程.

3) 探索內(nèi)存事務(wù)的服務(wù)質(zhì)量保證方法.在用戶追求事務(wù)系統(tǒng)高吞吐率、低延遲的同時,長久以來用戶也關(guān)注著事務(wù)的服務(wù)質(zhì)量.用戶難以接受小部分事務(wù)阻塞時間過長,內(nèi)存事務(wù)系統(tǒng)的長尾延遲問題亟待解決.長尾延遲的原因包括事務(wù)由于請求不到資源的頻繁中止、事務(wù)重試頻率過高造成沖突加劇、事務(wù)在熱點(diǎn)數(shù)據(jù)上競爭過多等.并發(fā)控制協(xié)議可以合理地調(diào)整節(jié)點(diǎn)執(zhí)行本地事務(wù)和服務(wù)其他節(jié)點(diǎn)的數(shù)據(jù)請求的順序,提前預(yù)測可能出現(xiàn)的耗時操作并優(yōu)先執(zhí)行,來降低內(nèi)存事務(wù)的長尾延遲.

5 相關(guān)工作

數(shù)據(jù)庫及系統(tǒng)研究者針對近年來興起的內(nèi)存事務(wù)進(jìn)行了廣泛的研究,形成了一些關(guān)于并發(fā)控制協(xié)議的綜述文章.針對多核場景,中國人民大學(xué)的研究[52]以PostgreSQL的優(yōu)化技術(shù)為依托,著重分析多核架構(gòu)對內(nèi)存事務(wù)的影響,從鎖管理、日志管理、緩沖區(qū)管理等多方面描述適配多核場景的新興技術(shù);新加坡國立大學(xué)的研究[53]從協(xié)議設(shè)計、數(shù)據(jù)存儲、垃圾回收和索引管理等角度比較了現(xiàn)有的單機(jī)多版本并發(fā)控制協(xié)議,并在同一框架內(nèi)實現(xiàn)驗證;華東師范大學(xué)的研究[54]對比了現(xiàn)有內(nèi)存事務(wù)并發(fā)控制協(xié)議和傳統(tǒng)基于磁盤協(xié)議的差異,以O(shè)ceanBase為例從并發(fā)控制和日志恢復(fù)2個角度分析現(xiàn)有技術(shù).針對分布式場景,Deneva[14]針對分布式事務(wù),選取多個經(jīng)典的并發(fā)控制協(xié)議進(jìn)行總結(jié)對比,通過實驗指出不同負(fù)載下性能最優(yōu)的協(xié)議;分布式事務(wù)中分區(qū)策略會影響并發(fā)控制協(xié)議的性能,印度浦那工程學(xué)院的研究[55]總結(jié)了各種分區(qū)策略,并對比了不同協(xié)議采用不同分區(qū)策略的效果.

相比以上綜述,本文結(jié)合硬件發(fā)展趨勢,分析了多核架構(gòu)、機(jī)器規(guī)模、新型器件對內(nèi)存事務(wù)帶來的挑戰(zhàn),著重對比分析了單機(jī)事務(wù)和分布式事務(wù)的不同優(yōu)化策略.優(yōu)化內(nèi)存事務(wù)的技術(shù)思路在單機(jī)和分布式場景是相通的,但實踐方式卻大不相同,本文將這些技術(shù)匯總比較,指出研究者面對不同應(yīng)用場景使用技術(shù)時的考慮,為之后系統(tǒng)設(shè)計者進(jìn)一步優(yōu)化提供參考.

6 總 結(jié)

為了應(yīng)對內(nèi)存事務(wù)中并發(fā)控制協(xié)議所面臨的機(jī)遇與挑戰(zhàn),研究者主要采用如下技術(shù)思路來開展研究工作：1)通過改進(jìn)全局時間戳分配方法、減少熱點(diǎn)數(shù)據(jù)競爭等方法來消除事務(wù)系統(tǒng)的擴(kuò)展瓶頸.2)通過改進(jìn)并發(fā)控制協(xié)議、選取恰當(dāng)?shù)腞DMA原語等方法來利用新硬件加速事務(wù)處理.3)通過采取更加靈活的提交策略、提供多版本避免事務(wù)中止、在硬件事務(wù)內(nèi)存中減少事務(wù)中止次數(shù)、實現(xiàn)事務(wù)透明性避免重試事務(wù)再次中止等方法來降低事務(wù)中止概率.4)利用非易失內(nèi)存和副本來高效保證單機(jī)和分布式事務(wù)的持久性.

結(jié)合業(yè)務(wù)應(yīng)用場景和硬件工藝的發(fā)展趨勢,內(nèi)存事務(wù)中并發(fā)控制協(xié)議的未來研究預(yù)期將聚焦如下方向:設(shè)計感知負(fù)載特征的并發(fā)控制協(xié)議、解決地理上分布的場景中事務(wù)系統(tǒng)的擴(kuò)展性問題,以及保證內(nèi)存事務(wù)的服務(wù)質(zhì)量等.

作者貢獻(xiàn)聲明：姜天洋負(fù)責(zé)調(diào)研文獻(xiàn)、撰寫全文并完成相關(guān)實驗；張廣艷負(fù)責(zé)確定論文思路、設(shè)計文章框架并討論修改全文；李之悅負(fù)責(zé)實現(xiàn)代碼并協(xié)助分析實驗結(jié)果.