分布式事務是分布式數據庫最難攻克的技術之一，分布式事務為分布式數據庫提供一致性數據訪問的支持，保證全局讀寫原子性和隔離性，提供一體化分布式數據庫的用戶體驗。
分布式事務是分布式數據庫最難攻克的技術之一，分布式事務為分布式數據庫提供一致性數據訪問的支持，保證全局讀寫原子性和隔離性，提供一體化分布式數據庫的用戶體驗。
【資料圖】
[[282776]]
本文主要分享分布式數據庫中的時鐘解決方案及分布式事務管理技術方案。混合邏輯時鐘(HLC)可以實現本地獲取，避免了中心時鐘的性能瓶頸和單點故障，同時維護了跨實例的事務或事件的因果(happen before)關系。
本次的分享主要圍繞以下兩個方面：
時鐘方案分布式事務管理一、時鐘方案
1、數據庫為什么需要時鐘
數據庫歸根結底是為了將每一個事務進行排序。在單機上情況下，事務排序可以非常簡單的實現，但是在分布式下如何進行事務排序?
數據庫通過事務對外提供數據相關操作的ACID。數據庫對事務順序的標識決定了事務的原子性和隔離性。原子性指一個事務是完整的，既發生或不發生，代表每個事務都是獨立的。隔離性指事務之間是相互隔離的。時鐘有各種方式來標識一個事務的順序，如Oracle每一個日志都有日志序列號LSN，事務ID，以及時間戳。
目前許多商業和開源數據庫產品都支持MVCC，MVCC通過支持數據的多版本，允許讀寫相同數據，實現并發，在讀多寫少的場景下極大的提升了性能。
多版本出現之后，其本身就隱含了事務的順序。當一個事務開始之后，需要確定哪個版本的數據是可見的和不可見的，所以這就涉及到了多體系，多版本和版本回收等問題。
一個很經典的場景，淘寶或天貓的購物場景，有一條商品記錄，用戶每買一個商品，就是對商品數量記錄做一次扣減。商品記錄版本會變的一個非常長，把所有的版本都保存起來是不合理的，否則整個存儲容量就不斷增加。那如何進行版本回收?在回收的時候也需要有順序，確定應該回收哪些版本?
2、分布式數據庫下的時鐘
分布式數據庫下的時鐘和單機數據庫下的時鐘有什么區別?
首先，單機數據庫的排序非常簡單，通過日志序列號或事務ID就可以表示事務的順序。在分布式數據庫下，因為數據庫運行在多臺服務器上，每個數據庫實例有獨立的時鐘或日志(LSN)，每一個本地的時鐘不能反映全局的順序。
服務器之間會有時鐘偏移，最理想情況是一個分布式數據庫部署100個節點，100個節點的時鐘是完全同步的。但實際情況下，在機房做越軌需要做時鐘校對，因為服務器和服務器之間時鐘點有快慢之差，所以分布式數據庫下的時鐘無法做全局設置的反映。
3、時鐘解決方案
時鐘解決方案有很多，如使用統一的中心節點，或者使用獨立的服務器產生分布式時鐘。
還有一種解決方案是邏輯時間，Lamport時鐘是邏輯時鐘。邏輯時鐘指的是沒有任何一個中心節點來產生時間，每一個節點都有自己本地的邏輯時間。
比如有十個Oracle數據庫，每個節點有自己的LSN，如果節點的事務比較多，事務ID跑的就比較快。如果節點事務比較少，事務ID就跑得比較慢。
下圖展示了目前主流的幾種時鐘解決方案，其中TIDB是國人的驕傲，TIDB使用的是中心時鐘。除此之外，Postgres-XL使用了GTM，也屬于中心時鐘。Oracle使用的是邏輯時鐘SCN。Cockraoch DB 是模仿Spanner做的分布式數據庫，使用的是混合邏輯時鐘。
還有最知名的Google Cloud Spanner，Spanner對硬件依賴比較高，使用的是Truetime。Truetime本質上是一個原子鐘，通過原子鐘授時確保兩個服務器之間時鐘偏移在很小的范圍之內。
4、邏輯時鐘
邏輯時鐘在分布式環境下如何實現?如下圖，有A、B和C，3個節點，每個節點會有自己的邏輯時間，邏輯時間可以簡單的理解為單調遞增的自然數，0、1、2、3…。事務開始后加1，新事務開再加1。
整個分布式環境下，三個節點完全獨立，相互之間沒有關系。如果事務跨多個節點，涉及到多個節點交互，產生一個事務的時候，本地時鐘要加1。發message出去的時候，要把message的主體發出去，還要將本地的時間發給另一個節點。收到一個message節點后要處理這條消息，從收到的消息里面將對時間和本地的邏輯時間做一個取值，取最大的值設為本地時間。
如果A節點發布較快，第一個事務完成以后，要做第二個事務，這時與B節點有交流，A加1，然后將時鐘帶到B節點，B節點直接從0跳到2。如此就在兩個時鐘之間建立了聯系，通過建立聯系，將兩個節點之間的邏輯時鐘拉平，這時候就構建它們之間的happen before的關系，代表A節點的事務是在B節點的新事務開始之前完成的。
分布式數據庫中，如果兩個事務沒有操作同樣的節點，則兩個事務是無關的事務。無關的事務可以認為是沒有先后順序的。但是當一個事務橫跨多個節點的時候，將多個節點之間的關系建立起來，就變成有關系的事務，構建的是事務間的因果序。
所謂因果序，如果同樣來了兩個事務，一個事務操作AB節點，另外一個事務操作BC節點，因為它們在B節點上建立了一個聯系。通過B節點的關系，將事務的順序維護起來。
純邏輯時鐘可以起到因果一致性和因果序的能力。那邏輯時鐘最大的問題是什么呢?
最極端的情況下，節點和節點之間永遠不產生聯系，兩個節點之間的邏輯時鐘的差距會越來越大。這時如果兩個節點之間做查詢或者備份，需要強制將它們建立關系，那么兩節點之間的gap會變得非常大。
5、混合時鐘
雖然機器和機器之間物理時鐘有偏移，但如果有NTP校準或者Google的Truetime這種時鐘服務器話，其物理時鐘的差距是非常小的。
混合時鐘把分布式下的時鐘切成兩部分，上半部分用物理時鐘來填充，下半部分用邏輯時鐘來填充。填充在一起變成了一個HLC時鐘，既混合邏輯時鐘。它既有物理時鐘的部分，又有邏輯時鐘的部分。由于物理時鐘服務器之間的差距不會特別大，所以可以比較物理時鐘大小。而物理時鐘又有一定的偏差，在一定的偏差范圍內，可以使用邏輯時鐘做校準。
下圖是混合邏輯時鐘的一個示例。當發送一個消息的時候，首先應該把邏輯時鐘的物理時鐘部分與當前的時鐘做一個比較。如果當前的物理時鐘是4點，新事務產生后，因為物理時鐘沒變，新事務加在邏輯時鐘的部分(加1)。
如果物理時鐘從4點變成4：01，則將物理時鐘推進。物理時鐘如果不推進，就加邏輯時鐘。如果物理時鐘發生了變化就把物理時鐘往上推進，將邏輯時鐘部分置零。
6、HLC和中心時鐘的差別
基于中心時鐘的方案的時間是通過事務ID來判斷的，從而為所以事物排序。分布式數據庫中，需要消除中心節點。一種方法是純邏輯時鐘，但邏輯時鐘之間無法比較大小。另一種方法是混合邏輯時鐘(HLC)，它為數據庫定義了一類因果關系的事務。
混合邏輯時鐘沒有中心節點，用本地的物理時間加上邏輯時間。本地產生的事務不保序，但是如果事務跨了節點，其因果聯系是有順序的。
如下圖T1，T2和T3代表提交時間，T1是一個分布式事務，T2是一個單機事務，T3是一個分布式事務。因為T1 是一個分布式事務，在數據庫節點上進1是比進2先執行，所以在整個時鐘里面，進1小于進2，進1也小于進3。通過這種方式，將有關系的事務的順序排好。
7、中心式 VS. 分布式 VS. Truetime
如下圖，中心式時鐘的優點一目了然，它可以保證全局一致的時間。
分布式數據庫下的時鐘的優點是無中心化的性能和無HA瓶頸，因為不需要中心的授時服務。分布式數據庫下的時鐘主要有兩個能力，第一個能力是可以做到計算和存儲的水平擴展。
另外，因為分布式數據庫把一個業務的workload拆分到了不同的機器上，從而單點故障帶來的影響減小了。把核心數據庫拆成了幾百份，任何一個單點數據庫故障帶來的整個系統可用性的下跌是非常小的。
這說明了為什么現在的分布式和互聯網+結合在一起比較火，一個很重要的原因是分布式降低了單點故障對業務帶來的的可用性的影響。
不僅僅是互聯網公司，包括金融類的銀行也想往分布式走，一個方面是為了解決容量和擴展性的問題，另外一方面也是為了解決高可用問題。
中心式的缺點是會有單點的single point of failure。分布式時鐘雖然消除了單點的影響，但是時鐘是不可以排序的，無法實現真正的外圍一致性。外圍一致性指的是每兩個事務都可以排序。而分布式時鐘只能對有關聯的事務進行排序，實現因果順序。
Google的Truetime的優點是保證全局一致時間，簡化應用開發。缺點首先是需要專有的硬件，如果Truetime的原子鐘授時的話，也會有一定的時鐘偏差，這個時鐘偏差物理上無法克服。Google Spanner的paper中可以發現每一個事務的提交都要等待一段時間，就是要等這段時鐘偏差。
二、分布式事務管理
1、兩階段提交
分布式事務管理是為了保證全局讀寫原子性和隔離性。一個事務要跨兩個節點，這時候存在失敗的可能性。假如一個節點成功一個節點失敗，那么看到的結果就是不一致的，這喪失了事務的原子性。
還有一種是兩個節點上都提交成功，但是因為兩個節點本身的時間不一樣，導致提交的時間也不一樣。如果用MVCC去讀這個事務，能看到一半，另一半可能看不到，這樣就無法保證事務的原子性。
對于事務的原子性問題，目前相關技術已經非常成熟，既兩階段提交。如果要保證一個分布式事務成功或者失敗，可以利用兩個階段提交技術，先做一個prepare事務，如果所有的prepare都可以，再做commit。
2、其它分布式事務管理技術
常見的分布式事務管理技術分為三類。
第一類是兩個階段提交技術，包含prepare階段和commit階段。
第二類基于MVOCC，其中FOUNDATION DB是蘋果開源的分布式數據庫，使用的是MVOCC，可以理解為OCC(optimistic concurrency control)。OCC指在事務提交時檢查是否有沖突，基于沖突有設置沖突檢測算法和權重算法，最后選擇毀掉或者提交哪個事務。對于鎖，在事前和在更新的時候加鎖，提交的時候檢查沖突。在沖突不劇烈的情況下，因為沒有加鎖開銷，整個吞吐非常高。在沖突劇烈的情況下，大量的abort事務會反復回滾。
第三類技術主要針對確定性事務，如FAUNA技術。
美國的一位教授提出了確定性事務，并基于確定性事務模型創辦了一家公司，創建了一個分布式數據庫(FAUNA)。確定性事務指事務是完整的，而不是交互型的。
比如，在淘寶這種互聯網企業處理的都是非確定性事務。非確定性事務只begin事務，select事務等，每個操作都是交互的，既APP需要跟DataBase做交互。
如果站在數據庫的視角，數據庫永遠無法預測下一條語句，這類事物是非確定性的。確定性事務是把一個事務所有的邏輯一次性寫好，然后發送給DataBase。DataBase收到事務的時候，清楚這個事務需要操作哪些表，讀取哪些記錄并進行哪些操作。從數據庫的視角來說事務是完全確定的。拿到一個確定性事務，可以事先將這些事務排好序。兩個事務之間如果操作相同的記錄，就排個先后，如果不操作相同的記錄，就并發的發出去。
使用這種方式可以做到既不用加鎖，也不用在事后提交的時候做沖突檢測。但是它的要求是事務不能是交互型的。
3、HLC和兩階段提交
混合邏輯時鐘(HLC)格式如下。如果有64個字節，首先預留5字節保證兼容性，在做系統設計的話，通常需要預留一些字節或以防出現一些問題時沒東西可用。中間再留43字節做物理時鐘。后面的16字節做邏輯時鐘。如果時鐘精確到毫秒級，43字節的物理時鐘意味著279年，表示數據庫不斷運行，279年不掛，一般來說這不太可能。
如果物理時鐘到天級，一天才能變一位，那物理時鐘就失去了意義。16字節是65536，65536意味著一毫秒內可以發起65536個事務，。一般開始和結束的時候都要消耗兩個時鐘，除以二，既一毫秒內可處理3萬多的事務，單節點一秒內可以做到3千多萬事務。
4、HLC時鐘偏移的問題
HLC和事務的吞吐有關系，因為它有物理時鐘，能夠展示不同的節點之間的時鐘差。如果真的出現了時鐘偏移怎么辦?
下圖提供了一個簡單的公式。沒有偏差的情況下，理論上節點可以做到3千萬的TPS，當然在工程上是做不到的。
如果兩個節點時鐘之間偏移量是5毫秒，那么在5毫秒之內只能通過邏輯時鐘去彌補。如果原來6萬個邏輯時鐘在1毫秒內就能做完，現在則需要5毫秒，導致整個事務的吞吐下降了600萬。所以時鐘偏移會導致peakTPS大幅下降。
下圖給出了幾種解決方案。比較簡單的是允許設置最大時鐘偏移，如果整個機房或者集群中兩個節點之間最大偏移超過了100毫秒，就把該異常節點清除。目前來看，機房都有NTP授時服務，所以發生如此大時鐘偏移的概率非常小。另一種方式是不清除異常節點，但是可以允許邏輯時鐘overflow到物理時鐘部分，使邏輯時鐘更大，這樣可以允許更多的事務在當前時鐘內發生。
