2019DTCC大会分享：分布式数据库全局读一致性
作者簡介：李海翔，網名“那海藍藍”，騰訊金融云數據庫技術專家。中國人民大學信息學院工程碩士企業導師。著有《數據庫事務處理的藝術：事務管理和并發訪問控制》、《數據庫查詢優化器的藝術：原理解析與SQL性能優化》、《大數據管理》，廣受好評。
分享正文：2019年5月8日，騰訊TDSQL團隊為中國數據庫技術大會DTCC帶來了騰訊最新的數據庫核心技術：TDSQL原創的全局讀一致性技術。
騰訊專家工程師李海翔在DTCC上做了主題為“騰訊TDSQL全局讀一致性”的技術內容分享。本次分享，基于數據庫事務處理的核心技術并發訪問控制技術和分布式系統CAP理論中的一致性，TDSQL原創性提出了全面地解決讀一致性的算法，是的分布式事務的一致性和分布式系統的一致性統一在一起。
如下是本次分享的主要內容，從如下八個角度全面分享了全局一致性的前世今生、光輝未來。
數據庫的事務處理技術，解決了什么問題？
分布式事務型數據庫，出現了什么新問題？--讀半已提交數據異常
業界是怎么解決讀半已提交數據異常問題的？
分布式事務型數據庫，解決了讀半已提交數據異常，就一勞永逸了嗎？
TDSQL的事務處理模型
什么是全局一致性？
TDSQL是怎么解決各種數據異常的？
展望未來
數據庫是一個高并發系統，所有的操作，通過事務的語義加以約束。而事務的語義，表現為事務的四個特性，ACID。而一個數據庫系統，其最核心的技術，就是事務處理技術，為了保障ACID，數據庫使用了多種復雜技術，其中，核心技術的核心是并發訪問控制算法。
事務處理技術，有兩個初衷：一是數據正確性，二是并發高效率。
數據庫的操作，把SQL語句的語義簡化后，只有讀操作和寫操作兩種。并發操作，就是讀寫操作的并發，組合后分為四種：讀讀、讀寫、寫讀、寫寫。其中，讀寫、寫讀、寫寫三種會產生多種“數據異?，F象”。常見的數據異常如圖1，發生了這些數據異常，就不能保證上述的數據準確性。
圖1 事務型數據庫系統的常見數據異常
這么多數據異常（圖1列出11種），會帶來什么問題呢？其表現，是在數據項上，出現了邏輯上不應該出現的“不一致性”現象。說不一致，抽象難理解，看不出其危害，所以我們用“臟讀數據異常”舉個簡單例子：
一個騙子T2轉帳1000元給事務T1，事務T1檢查自己的賬戶，入賬了1000元，然后事務T1把一件衣服賣給了騙子T2，之后騙子T2拿到衣服后回滾了轉賬1000元的操作，然后逃之夭夭了。事務T1既沒有拿到錢還丟失了衣服，損失很大。所以要避免這樣的異常發生。
所以，數據庫的事務處理機制，就是要避免商業交易（并發的交互行為）出現各種使交易任何一方受損的事情發生。
于是，事務型數據庫提出了多種并發訪問控制算法（如圖2）和其他相關技術，確保商業交易正常。用數據庫的術語講，就是確保ACID四個特性。圖2中的多種算法，在單機事務隔離級別的可串行化隔離級別，能夠確保圖1中的各種數據異常不會發生。（小問題，請思考：分布式事務型數據庫中的并發訪問控制算法，能否確保圖1中的各種數據異常不會發生呢？）
圖2 事務型數據庫的常見并發訪問控制算法
二??、分布式事務型數據庫，出現了什么新問題？--讀半已提交數據異常
在金融支付等業務場景中，對賬業務，是支付體系中最重要的一環，也是保證交易、資金安全的最后一道防線。涉及金融的業務，一定要對賬。
使用數據庫做對賬，如圖3，有兩個物理的節點，Na和Nb分別有兩個賬戶X和Y（X和Y也代表賬戶余額），現在第一個寫事務，要從X賬戶向Y賬戶轉賬10元，當此寫事務在Na節點完成提交，但Nb節點尚沒有提交（如網絡延遲發生、或Nb節點負載重尚沒有能執行事務的提交操作）。此時，另外一個分布式事務讀事務要做對賬操作，其在Na節點讀到了已經提交的“X-10”的值，而在Nb節點讀到的是“Y”（未提交的不能讀），則總賬為“X-10+Y”，這個就是數據不一致，因為總賬目少了10元錢。數據庫系統據不能容忍這種事情發生。
圖3 分布式事務型數據庫的讀半已提交數據異常
對于任何一個分布式事務型數據庫，如果基于封鎖并發訪問機制實現并發事務的可串行化調度，是不會存在這里所討論的問題的。其原因在于：一旦Na節點寫完畢數據，則表明Nb節點至少在Y賬戶這個數據項上施加了寫鎖，而新的對賬讀事務是不能讀取Y數據項的值的，其只能等待，因此不會發生對賬不平的問題。騰訊TDSQL就是這樣的，換句話說，沒有實現可串行化的數據庫，大概率會存在讀半已提交數據異常（小問題，請思考：為什么這里說大概率呢？答案參見圖4中的2次讀算法）。
但是，如果純粹使用封鎖并發訪問控制機制實現可串行化，事務處理的并發度降低，分布式數據庫的事務處理吞吐量就會底，這違背了事務處理技術的另外一個初衷：高效。所以類似TDSQL的分布式數據庫，用戶通常不使用可串行化隔離級別，原因就在于想要使得數據庫高效。而如OceanBase、Oracle等數據庫，干脆沒有實現可串行化隔離級別，而是直接把出現數據異常的危險拋給了用戶。
現在，我們再來討論一下，TDSQL會不會出現“讀半已提交數據異常”？
TDSQL除了支持可串行化隔離級別外，還支持可重復讀（RR）、讀已提交（RC），但這2個隔離級別，同另外一種并發訪問控制算法、MVCC技術緊密綁定，綁定的原因，是為了提高并發度，使得讀寫、寫讀操作互不影響。就是在MVCC機制下，TDSQL出現了“讀半已提交數據異?！?#xff0c;為什么呢？
因為前述“在Nb節點讀到的是“Y”（未提交的不能讀）”就是Y的舊版本，而不是未提交的新版本，這是MVCC機制決定的（小問題，請思考：是不是所有使用MVCC技術的，都得小心是不是存在“讀半已提交數據異?！崩?#xff1f;是哈，得小心+小心。要不然，賬目不平可就解釋不清楚了）。
其實，業界目前沒有特別好的解決方式。如圖4，典型的解法如下5類：
第一種：全局事務管理器架構。典型的例子如PostgreSQL-XC，其存在一個全局的事務處理節點，用于解決整個分布式系統分為內的所有事務沖突，這樣需要把各個子節點的事務相關信息都發送給全局唯一的事務處理節點，不光通信量大，而且存在單點瓶頸，限制了事務的處理能力。
第二種：TDSQL以封鎖機制實現全局可串行化。前述已經分析過，不再贅述。
第三種：物理時鐘，全序排序事務降低并發度。典型的例子如著名的Spanner。Spanner徹底地解決了所有數據異常，這是通過實現所有以事務為單位的事件全序排序來完成的。換句話說，實現了線性一致性和事務的可串行化隔離。但是，Spanner以Truetime機制全序排序事務的方式，降低了并發度，導致其分布式事務的吞吐量很低，效率甚至低于基于封鎖的并發訪問控制下的可串行化實現（即：以線性一致性串起了事務一致性，所以理論上看，Spanner每秒數百個的事務的吞吐量使得效率低到了極限）。
第四種：混合時間戳機制，實習局部偏序排序。典型的例子如仿Spanner的CockroachDB，通過SSI實現了可串行化解決了事務類型的數據異常，但是不能解決全局讀一致性的問題（需要全局排序才能解決全局讀一致性問題，但混合時鐘機制做不到全局有序）。另外，如果選擇非可串行化隔離級別，則和Spanner一樣，還是可能會出現“讀半已提交數據異?！?。
第五種：特定的解決機制--兩次讀機制。2次讀機制，源自學術界《Scalable atomic visibility with ramp transactions》這篇paper。其核心思想，是在Na和Nb節點第一次分別讀到“X-10”和“Y”這兩個版本后，通過特定算法識別這兩個數據不是出于一個一致的點，所以重新去Nb節點再讀一次，這時，因為一段時間過去了，Nb節點大概率完成提交，讀到的數據很可能是“Y+10”，因而可以保持對賬不出現差錯（X-10+Y+10=X+Y，賬目保持平衡）。但是，兩次讀延遲了事務的執行，降低了整個事務的吞吐量；更重要的是，這種解決問題的方式，只針對“讀半已提交數據異?！?（小問題，請思考：如果有新的數據異常，還需要讀2次數據嗎？）。
圖4 數據庫界對“讀半已提交數據異?！敝髁鞯慕夥?/span>
如標題所言，分布式事務型數據庫，解決了如圖1和圖3提及的各種數據異常之后，是不是就完美了呢？答案是否定的。
一波未平一波又起。
很不幸，圖5有給出了新的數據異常。在《Distributed snapshot isolation: global transactions pay globally, local transactions pay locally》這篇Paper中，稱之為“Cross數據異?！薄?/span>
圖5列出兩類分布式系統下的數據異常，，其中第一類本質上就是“讀半已提交數據異?！?#xff0c;而第二種“Cross數據異?！?#xff0c;其發生的背景，依然可以放到金融對賬的業務背景中來理解。請看圖5右子圖部分，有兩個物理節點，分別執行了本地事務和分布式事務。事務s和t是本地事務，修改了不同的數據項；事務x和事務y是兩個分布式事務，都在讀取數據；兩個分布式數據讀取數據被本地事務影響，讀到了不一致的數據，事務x讀到的是（a0，b1），事務y讀到的是（b0，a1），而數據的一致狀態要么是（a0，b0）要么是（a1，b1）。從業務的角度看，事務x和事務y都發起對賬，結果對出來的結果不僅不同而且還是一個臨時狀態對應的結果，這就是數據異常，對賬業務不能容忍此類事情發生。
數據庫內核層，解決這樣的數據異常，通常的方式，是通過建立事務之間的讀寫依賴關系圖，從中看是否有環存在，如果有則表明數據異常出現，因而需要打破環，即回滾其中某個事務，避免問題出現（小問題，請思考：會不會還有新的數據異常呢？數據異常如果也層出不窮該怎么辦？）。
圖5 新的數據異常—Cross異常圖
先來分享一下TDSQL的事務處理框架，這個框架，可以用圖2來做大的知識背景。
首先，TDSQL第一代的事務處理模型，采取了圖2中的基于封鎖的并發訪問控制協議和MVCC并發訪問控制協議，混合解決并發沖突問題。所以圖6中給出的SS2PL整體就是封鎖的并發訪問控制協議，然后用2PC技術來實現提交階段的原子寫操作。這是整體架構。
在具體實現沖突解決的時候，需要結合MVCC和隔離級別，來解決各種數據異常。這就要區分寫寫沖突、讀寫沖突和寫讀沖突三種具體的情況。
寫寫沖突，通常依靠封鎖機制。原理較為簡單，不再贅述。
讀寫沖突和寫讀沖突，則借助MVCC來避免鎖造成的延遲事務執行的問題，使得后者能繼續繼續，提高了并發度，所以主流的數據庫基本上都實現了MVCC機制。
圖6 TDSQL第一代分布式事務處理架構圖
其次，TDSQL第二代的事務處理模型，新支持了圖7基于OCC（樂觀并發訪問控制技術）和DTS（動態調整時間戳的并發訪問控制技術）的技術，使得TDSQL的分布式事務處理能力產生了質的飛躍（OCC使得并發度提高，DTS使得并發訪問控制算法去中心化），分布式事務處理性能提升數倍，并減少了對中心化時間戳節點的依賴，在分布式事務處理的去中心化的道路上，邁出一大步。
圖7 TDSQL第二代分布式事務處理架構圖
還記得標題四中的小問題不？小問題，請思考：會不會還有新的數據異常呢？數據異常如果也層出不窮該怎么辦？
現在，我們正面來談談，什么是全局讀一致。目的就是一勞永逸的解決各種數據異常。
在單機數據庫時代，數據庫理論中有個“可串行化”技術，對應到了隔離級別中的可串行化隔離級別，因為理論上把所有事務都排序，消除了并發，因而不會再有數據異常產生。
但是，在分布式數據庫時代，為了提高效率不想使用全局事務管理器限制并發，就采用了去中心化的架構設計分布式數據庫；不想使用有額外成本的原子鐘等，但又得解決各種數據異常，因此“可串行化”就不夠用了（“可串行化”的本質就是在排序）。
再加上，分布式系統，存在各種不確定性，如網絡發生分區、瞬間閃斷、延時等，使得發生在分布式系統內的讀和寫事件反序（與發生的順序相反）到達某個節點，這就又為分布式數據庫識別事件之間的先后邏輯關系帶來困難。為了規避這些問題帶來的“邏輯認識上的困擾”，分布式系統中提出各種“一致性”，如線性一致性、因果一致性、單調寫、寫后讀等各種問題（這些問題參見圖8左子圖）。
因此，分布式事務型數據庫其核心要解決的問題就是：同時滿足2個一致。一是分布式讀一致性，二是分布式事務一致性。我們把這兩種一致性，稱為“全局一致性”（注意不是全局讀一致性哦）。
分布式讀一致性（即全局讀一致性），從外部用戶的視角，觀察數據庫內部發生的事件產生的結果之間的順序要與事件發生的實際順序保持一致，不能A事件先于B事件發生，但先不到B事件的結果后才可能看到A事件的影響。這意味著，需要對實際發生的事件進行排序。
而對于分布式事務型數據庫，是從數據庫內核層的角度，保證并發的事務之間，能造成數據異常的情況（讀寫依賴關系圖形成了環）下部分事務被回滾或阻止其發生。及確保事務的可串行化。
如上兩者都被保證的情況下，數據異?？杀欢沤^。Spanner就是從分布式讀一致性中的線性一致性出發，約束了事務使之串行提交而保證無數據異常的，這好比用一根竹簽先后串起了兩種一致性需求（但效率因事務提交需要等待而低下），確保所有的事件全序排序杜絕任何異常。
但是，正式提出一個問題：大問題，請思考：有沒有高效的方式確保全局一致性？
答案是：有。請看下一節，TDSQL的解決技術。
注意本文的概念變化：標題是全局讀一致性，這是引子；但到本節發展成為了全局一致性；概念的變遷，有其內在的因素，請多體會哦。
圖8 全局一致性圖
讓我們回顧一下TDSQL的發展史，TDSQL2017年推出分布式事務處理技術，2018年推出全時態數據庫系統。在全時態數據庫技術中，提出一個“全態數據可見性判斷算法”。
這個算法，初衷意在解決“分布式事務型數據庫中，全態數據在任何時間點上怎么能夠讀到一致的數據”這樣的問題（算法參考騰迅論文《Efficient time-interval data extraction in MVCC-based RDBMS》）。但是，以這個算法為基礎，還可以做到全局一致性。更多技術，請參考VLDB 2019，騰訊論文《A Lightweight and Efficient Temporal Database Management System in TDSQL》。
如圖9左上子圖所示：
初始時刻t0：r11、r21、r31三個初始的數據項分布式在不同的物理節點上，此時這三個數據項處于一個“一致的”狀態。
t1時刻：r11被修改為r12，此時之后，r12、r21、r31三個數據項處于一個“一致的”狀態；虛線表示了他們處于一致狀態。
t2時刻：r21、r31同時被同一個事務修改，分別變為了r22、r32，所以事務提交后，r12、r22、r32這三個數據項處于一個“一致的”狀態。
其他時刻依次類推。
不支持全時態的數據庫，只有當前態，所以DML類操作，只讀取最新數據即可。
支持了全時態的數據庫，需要從歷史上任何一個點出發，找出這個出發點對應的處于一致性狀態的數據。所以怎么標識哪些數據的所有值（當前值、歷史值）和事務之間的關系，是全時態數據庫當初解決的一個問題。
現在，有了如上這個基礎，做到全局一致性，就容易了很多。所用技術如圖9右子圖部分。
寫寫沖突封鎖機制互斥：對于前面我們提到的寫寫沖突，還是依靠封鎖機制解決，避免丟失更新等數據異常發生。
MVCC從新版本到舊版本：基于MVCC，可以使得讀寫和寫讀沖突并發執行，提高了事務處理的效率，不然數據庫系統性能一塌糊涂不可使用。另外，使用MVCC，讀區版本的順序是有講究的，從最新版本開始讀就要求構造版本鏈的時候版本由新到舊。
局部節點處于Prepared狀態：在MVCC背景下，修改可見性判斷算法，當數據在2PC階段所有節點同意提交后，正常情況下事務就一定能夠提交（系統故障發生后可被恢復），這時，數據即對滿足快照的事務可見。
全局事務Committed狀態：設立全局事務提交狀態，當協調器在2PC階段所有節點同意提交后，即可設置事務狀態的全局標志為Committed（注意不是Prepared），然后通知子節點設置各自狀態為Prepared的。只有全局提交標志為Committed，事務讀取到的數據才是合法數據，可參考如圖8中的左下子圖部分，表示了分布式父子事務之間狀態導致可見性的關系。如上2點，避免了前述的讀半已提交數據異常。
異步、批量設置本地事務狀態：協調器上全局事務狀態信息，異步地發給涉及的各個子節點，完成子節點上原子事務狀態的Committed化。這點是性能優化的問題。
全局邏輯時鐘（非跨城/洲分布）：使用全局邏輯時鐘，為事務建立全局一致的快照，即用SI技術（快照技術），確保全局讀一致性。
沖突可串行化：協調器同時判斷是否存在沖突環，以解決Cross類型的數據異常。（小問題，請思考：還有沒有別的辦法解決cross異常？）
如此，TDSQL實現了全局一致性，即達到了外部強一致性和事務一致性的統一。這里介紹了主干流程，為了提高效率，TDSQL又做了很多優化點，以提高事務的吞吐量。
圖9 TDSQL全時態數據庫的核心技術—全態數據可見性判斷算法
但是，再次正式提出一個問題：大問題，請思考：有沒有更高效的方式確保全局一致性？
TDSQL一直走在探索分布式事務處理的道路上，走過的路充滿挑戰（圖10）。團隊同時享受到了戰勝挑戰帶來的“不可言而此處無聲勝有聲的與我心有戚戚焉”樂趣。
前進的途中，TDSQL攜手中國人民大學教育部數據工程和知識工程重點實驗室，采用動態時間戳解決事務沖突并去中心化全局時間戳依賴、用data-drive技術減少事務沖突、用細粒度減少事務沖突等，實現分布式事務處理能力，提升TDSQL分布式事務處理的效率。期待有機會就這些技術進行分享。
圖10 TDSQL分布式事務、分布式一致性處理技術展望
特別感謝中國人民大學教育部數據工程和知識工程重點實驗室，與騰訊TDSQL攜手，共同研發了本文分享的技術。
總結
以上是生活随笔為你收集整理的2019DTCC大会分享：分布式数据库全局读一致性的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 从并发模型看 Go 的语言设计
- 下一篇： 中国移动携手腾讯开展5G联合创新