作者：李海翔，騰訊TEG數據庫技術專家

一個是全球領先的科技公司，一個是中國數據庫基礎學術研究的搖籃，近日，中國人民大學-騰訊協同創新實驗室正式舉行揭牌儀式。據了解，雙方已聚焦在數據庫基礎研究領域進行了多年的前沿產學研合作，以及數據庫人才合作培養計劃，在推進數據庫安全可控的同時面向未來大規模多場景數字化時代進行前沿創新研究儲備，其中實驗室輸出的包括“全時態數據庫系統”等多項成果相繼被VLDB等國際頂會收錄，同時申請獲得了多項國家技術專利。

在本次實驗室揭牌亮相的同時，騰訊與中國人民大學研究團隊還開源公布了一項最新合作研究成果——3TS騰訊事務處理技術驗證系統。

Tencent Transaction ProcessingTestbed System（簡稱3TS），是騰訊公司自研金融級分布式數據庫TDSQL團隊與中國人民大學數據工程與知識工程教育部重點實驗室，聯合研制的面向數據庫事務處理的驗證系統。該系統旨在通過設計和構建事務（包括分布式事務）處理統一框架，并通過框架提供的訪問接口，方便使用者快速構建新的并發控制算法；通過驗證系統提供的測試床，可以方便用戶根據應用場景的需要，對目前主流的并發控制算法在相同的測試環境下進行公平的性能比較，選擇一種最佳的并發控制算法。目前，驗證系統已集成13種主流的并發控制算法，提供了TPC-C、Sysbench、YCSB等常見基準測試。3TS還進一步提供了一致性級別的測試基準，針對現階段分布式數據庫系統的井噴式發展而造成的系統選擇難問題，提供一致性級別判別與性能測試比較。

3TS系統旨在深度探索數據庫事務處理相關理論與實現技術，其核心理念是：開放、深度、進化。開放，秉承開源之心，共享知識、共享技術；深度，踐行系統化鉆研之精神，對于事務處理技術的本質問題進行研究，不破樓蘭終不還；進化，路漫漫其修遠兮，吾將上下而求索，不斷前行，不斷推進。

1、3TS 整體架構

?

作為一個事務處理技術相關的框架，3TS致力于探索的本質問題主要包括：

?

• 世界上有多少種數據異常？數據異常的體系化研究方法如何建立？

• 為什么并發訪問控制算法會有很多種？各種并發訪問控制算法之間，有沒有的本質的關聯關系？

• 單機事務型數據庫分布式化后，哪些方面（可用性？可靠性？安全性？一致性？擴展性？功能？性能？架構？……）會受到影響？

• 有哪些新技術，會影響著且如何影響著分布式事務型數據庫系統？

• 分布式事務型數據庫系統的評價、評測體系應該如何建立？

在代碼層面，如上的每一類研究問題，都有對應的子系統。如首期開源的包括3TS-DA子系統混合3TS-Deneva子系統。

?

2、3TS-DA，數據異常子系統

?

3TS-DA數據異常子系統，位于src/3ts/da路徑下，其項目結構如下圖所示：

• History Creator：負責生成history，輸出給算法執行驗證。

• CCA Group：CCA即并發訪問控制算法（Concurrent access control algorithm），可以對傳入的history進行異常檢測，并返回異常檢測結果。

• Outputter：負責將各個CCA對當前history的檢測結果輸出到文件中。

?

3TS-DA子系統當前功能：

?

• 測試數據生成：支持三種history的生成方式，遍歷生成、隨機生成、從文本讀取。

• 算法添加：提供統一的算法接口，能夠較便捷地添加新的并發算法，同時框架本身內置有多種算法，包括：可串行化、沖突可串行化、SSI、WSI、BOCC、FOCC等。

• 測試指標：框架提供多種測試指標，包括：算法回滾率、真回滾率、假回滾率、執行時間等。

• 異常擴展：框架實現了數據異常擴展算法，能夠擴展生成無限多的數據異常history，供算法進行測試

3、3TS-Deneva，并發算法框架

?

Devena[1]是MIT開源的一個分布式內存數據庫并發訪問控制算法的評估框架，原始代碼位于https://github.com/mitdbg/deneva。它可以在受控環境下研究并發控制協議的性能特性。該框架提供了Maat、OCC、TO、Locking（No Wait、 Wait Die）、Calvin等主流算法。3TS-Deneva是騰訊在Deneva基礎上對原有系統的改進，包括多個層面。其中在算法層面，增加了更多的并發訪問控制算法，包括：可串行化、沖突可串行化、SSI、WSI、BOCC、FOCC、Sundial、Silo等。

3.1 基礎架構

Devena使用了自定義的引擎以及其它一些設置，可以在這個平臺上部署和實現不同的并發控制協議，以進行一個盡量公平的評估。該系統的架構，如圖1所示，主要包括兩大模塊：

• 客戶端實例，作為事務的發起者。客戶端中的每個線程負責發起事務請求，并將發起的事務請求放到消息隊列中，按序發送給服務端具體執行。客戶端與服務端實例是全連接的拓撲結構，一般部署在不同的機器上；

• 服務端實例，具體執行事務中的各類操作。不同服務端實例中存有數據，數據使用一致性哈希進行索引，從而形成服務端IP與所存數據的全局分區映射表，通過控制分區映射在測試期間不會修改的方法，保證該映射表是所有節點都可以準確獲取的。客戶端與服務端實例、服務端與服務端實例間的通信使用TCP/IP協議。每個服務端實例內部可被細分為四個模塊：

• • 輸入消息隊列，暫存由客戶端/其他服務端發來的消息；

  • 執行引擎，分配多個工作線程來對消息隊列中的消息進行解析并實際執行，采用一個核綁定一個線程的資源調度方式；

  • 并發控制模塊，工作線程在執行事務操作的過程中，要維護特定并發控制協議要求的信息，并執行協議規定的流程，從而保證所指定的并發控制協議生效；

  • 數據存儲模塊，負責管理本實例中的數據，將數據都放在內存中。

?

圖1? Deneva系統架構圖

?

在3TS中，對Deneva進行改進。改進后的代碼位于contrib/deneva路徑下，其內部項目結構如圖2所示：

圖2 Deneva實現框架圖

• Deneva整體上分為Server和Client兩種節點。

• Client用于生成并向server發送要執行的負載query。Server用于協調執行Client發來的負載query。

• Client和Server共有模塊：

• • MsgQueue：消息隊列，存儲了要發送的msg。

  • MsgThread：消息發送線程，循環從MsgQueue中取出msg發送出去。

  • InputThread：消息接收線程，接收Server/Client發來的信息。

• Client上專有模塊：

• • ClientQueryQueue：客戶端的query隊列，存儲了測試開始前生成query列表。

  • ClientThread：客戶端線程，循環從ClientQueryQueue取出query，通過MsgThread和MsgQueue發送給Server。

• Server上專有模塊

• • WorkQueue：服務端的待處理msg隊列， InputThread接收到msg后，會將其放入WorkQueue。

  • WorkThread：服務端的執行線程，從WorkQueue取msg出來執行處理，在執行完畢后，會生成返回msg，同樣通過MsgThread和MsgQueue發送出去。

?

3.2事務執行流程

?

在Deneva中，如圖3所示，一個事務的執行流程為：

1）客戶端首先發起一個事務請求（由多個操作組成），并將事務放到ClientQueryQueue中。ClientThread會從隊列中取出事務請求存入消息隊列MsgQueue。之后，消息發送線程會從MsgQueue中取出某一事務的操作集合，封裝為一個Request，發送到某一服務端（通過第一個操作所訪問的數據確定），作為這個事務的協調節點；

2）Request到達服務器后，服務器先對請求進行解析，并把這一事務的所有操作作為一個元素，放到工作隊列（WorkQueue）中。工作隊列中放置的有來自客戶端的新事務和已經開始執行的事務的遠程操作，后者在隊列中比前者優先級更高。工作線程池中的線程輪詢工作隊列并處理事務中的操作。當某一工作線程處理當前事務的操作時，其首先對事務進行初始化，然后按順序執行讀寫操作，并最終提交或者回滾；

• 執行事務的過程中有兩種情況會導致事務進入等待，一是等待某一資源上的排他鎖釋放；二是需要訪問遠程服務端中的數據。當遠程訪問其他服務端中的數據需要的等待時，遠程服務端將返回WAIT指令給當前協調節點，協調節點會暫存當前事務的等待狀態并調度當前工作線程執行其他事務的操作，從而避免了工作線程的阻塞。當某一等待事務可以繼續執行時，基于工作隊列的優先級調度策略，它將由第一個可用的工作線程繼續執行；

• 并發控制協議所要求的額外操作會嵌入在事務執行過程中，包括讀寫操作、驗證操作、提交/回滾操作等。

3）當協調節點完成某一事務的操作后，他會將事務執行結果放入消息隊列，然后由消息發送線程通知客戶端當前事務的執行結果。

圖3? Deneva事務執行流程圖

4、分布式事務概述

?

文獻[15]對分布式事務定義為：

A distributed transaction is a database transactionin which two or more network hosts are involved. Usually, hosts providetransactional resources, while the transaction manager is responsible forcreating and managing a global transaction that encompasses all operationsagainst such resources. Distributed transactions, as any other transactions,must have all four ACID (atomicity, consistency, isolation, durability)properties, where atomicity guarantees all-or-nothing outcomes for the unit ofwork (operations bundle).

分布式事務以分布式系統為物理基礎，實現了事務處理的語義要求，即也要在分布式系統上滿足ACID特性。所以分布式數據庫的分布式事務處理，同樣要遵循單機數據庫系統下的事務相關理論，確保每個事務符合ACID的要求，采用分布式的并發訪問控制技術來處理分布式系統下的數據異常現象，實現分布式的事務ACID特性。

分布式事務處理機制的基本技術，以單機數據庫系統中的事務處理技術為基礎，但也有些不同，諸如如何處理分布式數據異常、如何做到分布式架構下的可串行化，如何做到跨節點的原子提交，如何做好存在網絡分區或有較高延時下事務的響應等。

3TS框架，是一個分布式環境，這些內容，都將在3TS中得到實現和驗證。

?

5、3TS提供的并發訪問控制算法

?

3TS中目前集成了十三種并發few你控制算法，主要包括：

?

（1）兩階段封鎖協議（2PL：No-Wait，Wait-Die）

（2）時間戳排序協議（T/O）

（3）多版本并發控制協議（MVCC）

（4）樂觀并發控制協議（OCC、FOCC、BOCC）

（5）優化的樂觀并發控制協議（MaaT、Sundial、Silo）

（6）確定性并發控制協議（Calvin）

（7）基于快照隔離的并發控制協議（SSI、WSI）

下面依次對這些并發控制協議進行簡要介紹：

?

5.1 兩階段封鎖協議（2PL）

??

兩階段封鎖協議（Two-phase Locking, 2PL）是目前最廣泛應用的并發控制協議。2PL依靠讀寫操作發生時獲取共享鎖或排他鎖的方式，來對事務間的沖突操作進行同步。根據Bernstein和Goodman的描述[2]，2PL對鎖的獲取有如下兩條規則：1）同一個數據項上不能同時存在兩個互相沖突的鎖；2）一個事務在釋放了任意一個鎖之后，不能再獲取鎖。第二條規則規定了事務中的鎖操作分為了兩個階段：生長階段（growing phase）和衰減階段（shrinking phase）。在生長階段中，事務將為其需要訪問的所有記錄獲取鎖。讀取操作獲取共享鎖，寫入操作獲取互斥鎖。共享鎖是不沖突的，互斥鎖與共享鎖或其他互斥鎖沖突。一旦某一事務釋放了其中任意一個鎖，事務便進入2PL的第二階段，稱為衰減階段。進入此階段后，事務就不允許獲取新的鎖。

3TS實現了直到事務提交或終止后才釋放鎖的嚴格2PL（Strict 2PL）協議。根據避免死鎖方法的不同，3TS中實現的2PL包括兩種：2PL（No-Wait）和2PL（Wait-Die），其實現遵循了[2,3]中對這兩種協議的描述：

?

5.1.1 2PL（No-Wait）

?

該協議規定，當事務嘗試加鎖時發現鎖沖突，則回滾當前正在請求鎖的事務。被回滾的事務已持有的鎖都將被釋放，從而允許其他事務獲得鎖。No_Wait機制可以避免死鎖，因為事務間的等待不會成環。但是，并非每次出現鎖沖突都會導致死鎖，因此回滾率可能較高。

?

5.1.2 2PL（Wait-Die）

?

Rosenkrantz[3]提出2PL（Wait-Die），用事務開始時間戳作為優先級，來保證鎖的等待關系與時間戳順序一致。只要事務時間戳比當前擁有鎖的任何事務小（舊），當前事務需要等待；否則，當前事務需要回滾。對于任意兩個沖突事務Ti和Tj，該協議使用時間戳優先級來決定是否讓Ti等待Tj，如果Ti優先級更低（時間戳更小）那么Ti需要等待，否則Ti回滾。因而鎖等待圖里不會構成環，該方法可以避免死鎖的發生。該算法是TO和Locking技術的融合。

但是，利用2PL的原理實現的分布式事務處理機制，要么避免死鎖（回滾率大），要么需要解決死鎖的問題（資源死鎖和通信死鎖）。在分布式系統中解決死鎖的代價會很大（單機系統上解決死鎖的代價已經很大，基于多進程或多線程架構的現代數據庫系統，解決死鎖操作可能導致系統幾乎停止服務。如MySQL5.6、5.7版本中對同一個數據項并發更新，死鎖檢測操作機會導致系統幾乎停止服務）。

不僅是死鎖檢測會消耗巨大資源，鎖機制本身帶來的弊端一直為人詬病。文獻[5]認為封鎖機制的弊端如下（對這些弊端的清晰認識，促使文獻[5]的作者設計了OCC，Optimistic Concurrency Control，樂觀并發訪問控制）：

1. ?封鎖機制開銷大：為保證可串行性，加鎖協議對于不改變數據庫完整性約束的只讀事務，需要加讀鎖互斥并發寫操作，以防止別人修改；對于可能造成死鎖的加鎖協議還需要忍受死鎖預防/死鎖檢測等機制帶來的開銷。

2. ?封鎖機制復雜：為了避免死鎖，需要定制各種復雜的加鎖協議（如什么時候加鎖、什么時候才能釋放鎖，怎么保證嚴格性等）。

3. ?降低系統的并發吞吐量：

a)??在等待I/O操作的一個事務持鎖，將大幅降低系統整體的并發吞吐量。

b)??事務回滾完成前，加鎖事務回滾時必須持有鎖，直到事務回滾結束，這也將降低了系統整體的并發吞吐量。

另外，使用鎖的機制進行互斥操作，對于操作系統而言，會引發耗時的內核態操作而使得鎖機制的效率低下。這意味著基于操作系統的鎖機制的帶有事務處理語義的2PL技術更加不可采用（但也有一些技術在不斷改進基于封鎖協議的并發訪問控制算法）。

?

5.2 時間戳排序協議（T/O）

???

時間戳排序協議（TimestampOrdering, T/O）在事務開始時，為事務分配時間戳，并按照時間戳的順序對事務進行排序[2]。當某一操作的執行會違背事務之間已經規定的順序時，當前操作所在的事務會被回滾或進入等待狀態。

3TS中的T/O算法實現遵循[2]中第4.1節的描述，可詳細參考該文獻獲得更多內容。如下圖，給出了一個基本的T/O算法的實現。

圖4 T/O算法

?

5.3 多版本并發控制協議（MVCC）

?

多版本并發訪問控制 (Multi-version ConcurrencyControl, MVCC) 是目前的數據庫管理系統普遍采用的并發訪問控制技術，其首先在 1978 年由 David Patrick Reed [4]提出，其主要思路是將一個邏輯數據項擴充為多個物理版本，將事務對數據項的操作轉換為對版本的操作，從而提高事務處理的并發度，并可以提供讀寫互不阻塞的能力。

?

Multi version concurrent access control，多版本并發訪問控制技術，簡稱MVCC技術。

1970年MVCC技術被提出，1978年的[4]《Naming andsynchronization m a decentralized computer system》進一步描述，之后在1981年文獻[16]詳細描述了MVCC技術，但是其描述的MVCC技術是基于時間戳的MVCC。

Multiversion T/O

：For rw synchronization the basic T/Oscheduler can be improved using multiversiondata items [REED78]. For each data item x there is a set of R-ts'sand a set of (W-ts, value) pairs, called versions. The Rts's of x record thetimestamps of all executed dm-read(x) operations, and the versions record thetimestamps and values of all executed dm-write(x) operations. (In practice onecannot store R-ts's and versions forever; techniques for deleting old versionsand timestamps are described in Sections 4.5 and 5.2.2.)

之后，MVCC技術被大量使用并衍生出多種版本。

2008年，文獻[13]發表，提出“SerializableSnapshot Isolation”技術實現基于MVCC的可串行化隔離級別。這使得PostgreSQL V9.1使用該技術實現了可串行化隔離級別。

2012年，文獻[14]發表，提出“Write-snapshotIsolation”技術通過驗證讀寫沖突實現基于MVCC的可串行化隔離級別，相較于依靠檢測寫寫沖突的方式提高并發度（某種寫寫沖突是可串行化的）。該文作者基于HBase做了系統實現。

2012年，文獻[17]在PostgreSQL實現了SSI技術。該文獻不僅講述了序列化快照的理論基礎、PostgreSQL對于SSI技術的實現方式，還提出了為支持只讀事務而實現的“Safe Snapshots”、“Deferable Transaction”，因為避免讀-寫沖突造成事務回滾的影響而對被回滾的事務采取“safe retry”策略，以及兩階段提交對選取回滾讀-寫沖突的事務的影響等重要話題。

文獻[19]較為系統地討論了MVCC技術涉及地四個方面，分別是：并發訪問控制協議、多版本存儲、舊版本垃圾回收、索引管理，另外討論了MVCC的多種變體的原理，實現多種變體（MV2PL、MVOCC、MVTO等）后在OLTPworkload上測試評估各個變體的效果。[18]則對于MVCC的舊版本垃圾回收進行了詳細討論。

?

3TS中，主要基于[2]中第4.3節的描述，結合T/O算法實現了MVCC。因此，事務間仍然使用開始時間戳進行排序，與傳統T/O算法不同的是，MVCC利用多版本的特性，可以減少T/O中的操作等待開銷。MVCC中的操作執行機制如下（用ts代表當前事務的時間戳）：

1.?? 讀操作

a)?? 如果ts大于prereq中所有事務的時間戳，且在writehis（當前數據項的版本鏈）中存在一個版本，其wts大于ts且小于pts，則當前版本可以返回，且將當前事務的時間戳存入readhis。如果writehis不存在對應的時間戳，則將當前事務的時間戳存入readreq。主要原因為：

如果在預寫事務和讀操作之間存在一個已經提交的寫，那么代表當前讀操作讀到的數據是已經提交寫事務寫入的，滿足時間戳排序，可以讀到該版本；

讀操作的時間戳比當前未完成的寫事務的時間戳大，應該讀到新數據，所以要等待；

b)?? 否則，當前讀操作通過時間戳讀到最新可見版本，并將當前事務的時間戳存入readreq；

2.?? 寫操作

a)?? 如果ts小于readhis中所有事務的時間戳，且在writehis中存在一個時間戳在rts和ts之間，可以正常預寫數據。如果writehis中不存在符合條件的版本，那么當前事務回滾；

b)?? 將當前寫操作暫存在prereq_mvcc中；

3.?? 提交操作

a)?? 將當前事務時間戳和寫入的新版本插入writehis；

b)?? 從prereq中把當前事務的寫操作刪除；

c)?? 繼續執行readreq中滿足時間戳順序的讀事務；

?

更多并發訪問控制算法，待續…...敬請持續關注！

?

致謝

特別感謝騰訊TDSQL團隊與中國人民大學數據工程與知識工程教育部重點實驗室對本項工作的支持和幫助，感謝趙展浩、劉暢、趙泓堯等同學為本文做出貢獻。

?

Reference

[1] Rachael Harding, Dana Van Aken, Andrew Pavlo, Michael Stonebraker: AnEvaluation of Distributed Concurrency Control. Proc. VLDB Endow. 10(5): 553-564(2017)

[2] ??? Philip A. Bernstein, NathanGoodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv.13(2): 185-221 (1981)

[3] Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II:System Level Concurrency Control for Distributed Database Systems. ACM Trans.Database Syst. 3(2): 178-198 (1978)

[4] D. P. Reed. Naming and synchronization in a decentralized computersystem. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA,1978.

[5] H. T. Kung, John T. Robinson: On Optimistic Methods for ConcurrencyControl. ACM Trans. Database Syst. 6(2): 213-226 (1981)

[6] Theo H?rder: Observations on optimistic concurrency control schemes.Inf. Syst. 9(2): 111-120 (1984)

[7] Hatem A. Mahmoud, Vaibhav Arora, Faisal Nawab, Divyakant Agrawal, AmrEl Abbadi: MaaT: Effective and scalable coordination of distributedtransactions in the cloud. Proc. VLDB Endow. 7(5): 329-340 (2014)

[8] Xiangyao Yu, Yu Xia, Andrew Pavlo, Daniel Sánchez, LarryRudolph, Srinivas Devadas:

Sundial: Harmonizing Concurrency Control and Caching in a Distributed OLTPDatabase Management System. Proc. VLDB Endow. 11(10): 1289-1302 (2018)

[9] Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, Samuel Madden:Speedy transactions in multicore in-memory databases. SOSP 2013: 18-32

[10] Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, PhilipShao, Daniel J. Abadi: Calvin: fast distributed transactions for partitioneddatabase systems. SIGMOD Conference 2012: 1-12

[11] Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J.O'Neil, Patrick E. O'Neil: A Critique of ANSI SQL Isolation Levels. SIGMODConference 1995: 1-10

[12] Alan D. Fekete, Dimitrios Liarokapis, Elizabeth J. O'Neil, Patrick E.O'Neil, Dennis E. Shasha: Making snapshot isolation serializable. ACM Trans.Database Syst. 30(2): 492-528 (2005)

[13] Michael J. Cahill, Uwe R?hm, Alan D. Fekete: Serializable isolationfor snapshot databases. SIGMOD Conference 2008: 729-738

[14] Maysam Yabandeh, Daniel Gómez Ferro: A critique of snapshotisolation. EuroSys 2012: 155-168

[15] https://en.wikipedia.org/wiki/Distributed_transaction

[16] P. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control andRecovery in Database Systems. Addison–Wesley, 1987.

[17] D. R. Ports and K. Grittner, “Serializable snapshot isolation inpostgresql,” PVLDB, vol. 5, no. 12, pp. 1850–1861, 2012.

[18] J.B?ttcher, et al., ScalableGarbage Collection for In-Memory MVCC Systems, in?VLDB,2019

[19] Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, Andrew Pavlo:An EmpiricalEvaluation of In-Memory Multi-Version Concurrency Control. Proc. VLDBEndow. 10(7): 781-792 (2017)

[20] D. Lomet andM. F. Mokbel, “Locking key ranges with unbundled transaction services,” VLDB,pp. 265–276, 2009.

[21] Jinwei Guo, PengCai, Jiahao Wang, Weining Qian, Aoying Zhou: Adaptive Optimistic Concurrency Controlfor Heterogeneous Workloads. PVLDB 12(5): 584-596 (2019)

[22] X. Yu, A. avlo, D. Sanchez, and S.Devadas, “Tictoc: Time traveling optimistic concurrency control,” in Proceedingsof SIGMOD, vol. 8, 2016, pp. 209–220.

[23] Rudolf Bayer,Klaus Elhardt, Johannes Heigert, Angelika Reiser:Dynamic Timestamp Allocation forTransactions in Database Systems. DDB 1982: 9-20

騰訊技術官方交流微信群已經開放

進群添加微信：journeylife1900

（備注：騰訊技術）

總結

以上是生活随笔為你收集整理的腾讯与中国人民大学开源最新研究成果：3TS腾讯事务处理技术验证系统的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。