分布式事務(wù)是分布式數(shù)據(jù)庫最難攻克的技術(shù)之一，分布式事務(wù)為分布式數(shù)據(jù)庫提供一致性數(shù)據(jù)訪問的支持，保證全局讀寫原子性和隔離性，提供一體化分布式數(shù)據(jù)庫的用戶體驗。

[[282776]]

本文主要分享分布式數(shù)據(jù)庫中的時鐘解決方案及分布式事務(wù)管理技術(shù)方案。混合邏輯時鐘(HLC)可以實現(xiàn)本地獲取，避免了中心時鐘的性能瓶頸和單點故障，同時維護了跨實例的事務(wù)或事件的因果(happen before)關(guān)系。

本次的分享主要圍繞以下兩個方面：

• 時鐘方案
• 分布式事務(wù)管理

一、時鐘方案

1、數(shù)據(jù)庫為什么需要時鐘

數(shù)據(jù)庫歸根結(jié)底是為了將每一個事務(wù)進行排序。在單機上情況下，事務(wù)排序可以非常簡單的實現(xiàn)，但是在分布式下如何進行事務(wù)排序?

數(shù)據(jù)庫通過事務(wù)對外提供數(shù)據(jù)相關(guān)操作的ACID。數(shù)據(jù)庫對事務(wù)順序的標識決定了事務(wù)的原子性和隔離性。原子性指一個事務(wù)是完整的，既發(fā)生或不發(fā)生，代表每個事務(wù)都是獨立的。隔離性指事務(wù)之間是相互隔離的。時鐘有各種方式來標識一個事務(wù)的順序，如Oracle每一個日志都有日志序列號LSN，事務(wù)ID，以及時間戳。

目前許多商業(yè)和開源數(shù)據(jù)庫產(chǎn)品都支持MVCC，MVCC通過支持數(shù)據(jù)的多版本，允許讀寫相同數(shù)據(jù)，實現(xiàn)并發(fā)，在讀多寫少的場景下極大的提升了性能。

多版本出現(xiàn)之后，其本身就隱含了事務(wù)的順序。當一個事務(wù)開始之后，需要確定哪個版本的數(shù)據(jù)是可見的和不可見的，所以這就涉及到了多體系，多版本和版本回收等問題。

一個很經(jīng)典的場景，淘寶或天貓的購物場景，有一條商品記錄，用戶每買一個商品，就是對商品數(shù)量記錄做一次扣減。商品記錄版本會變的一個非常長，把所有的版本都保存起來是不合理的，否則整個存儲容量就不斷增加。那如何進行版本回收?在回收的時候也需要有順序，確定應(yīng)該回收哪些版本?

2、分布式數(shù)據(jù)庫下的時鐘

分布式數(shù)據(jù)庫下的時鐘和單機數(shù)據(jù)庫下的時鐘有什么區(qū)別?

首先，單機數(shù)據(jù)庫的排序非常簡單，通過日志序列號或事務(wù)ID就可以表示事務(wù)的順序。在分布式數(shù)據(jù)庫下，因為數(shù)據(jù)庫運行在多臺服務(wù)器上，每個數(shù)據(jù)庫實例有獨立的時鐘或日志(LSN)，每一個本地的時鐘不能反映全局的順序。

服務(wù)器之間會有時鐘偏移，最理想情況是一個分布式數(shù)據(jù)庫部署100個節(jié)點，100個節(jié)點的時鐘是完全同步的。但實際情況下，在機房做越軌需要做時鐘校對，因為服務(wù)器和服務(wù)器之間時鐘點有快慢之差，所以分布式數(shù)據(jù)庫下的時鐘無法做全局設(shè)置的反映。

3、時鐘解決方案

時鐘解決方案有很多，如使用統(tǒng)一的中心節(jié)點，或者使用獨立的服務(wù)器產(chǎn)生分布式時鐘。

還有一種解決方案是邏輯時間，Lamport時鐘是邏輯時鐘。邏輯時鐘指的是沒有任何一個中心節(jié)點來產(chǎn)生時間，每一個節(jié)點都有自己本地的邏輯時間。

比如有十個Oracle數(shù)據(jù)庫，每個節(jié)點有自己的LSN，如果節(jié)點的事務(wù)比較多，事務(wù)ID跑的就比較快。如果節(jié)點事務(wù)比較少，事務(wù)ID就跑得比較慢。

下圖展示了目前主流的幾種時鐘解決方案，其中TIDB是國人的驕傲，TIDB使用的是中心時鐘。除此之外，Postgres-XL使用了GTM，也屬于中心時鐘。Oracle使用的是邏輯時鐘SCN。Cockraoch DB 是模仿Spanner做的分布式數(shù)據(jù)庫，使用的是混合邏輯時鐘。

還有最知名的Google Cloud Spanner，Spanner對硬件依賴比較高，使用的是Truetime。Truetime本質(zhì)上是一個原子鐘，通過原子鐘授時確保兩個服務(wù)器之間時鐘偏移在很小的范圍之內(nèi)。 

4、邏輯時鐘

邏輯時鐘在分布式環(huán)境下如何實現(xiàn)?如下圖，有A、B和C，3個節(jié)點，每個節(jié)點會有自己的邏輯時間，邏輯時間可以簡單的理解為單調(diào)遞增的自然數(shù)，0、1、2、3...。事務(wù)開始后加1，新事務(wù)開再加1。

整個分布式環(huán)境下，三個節(jié)點完全獨立，相互之間沒有關(guān)系。如果事務(wù)跨多個節(jié)點，涉及到多個節(jié)點交互，產(chǎn)生一個事務(wù)的時候，本地時鐘要加1。發(fā)message出去的時候，要把message的主體發(fā)出去，還要將本地的時間發(fā)給另一個節(jié)點。收到一個message節(jié)點后要處理這條消息，從收到的消息里面將對時間和本地的邏輯時間做一個取值，取最大的值設(shè)為本地時間。

如果A節(jié)點發(fā)布較快，第一個事務(wù)完成以后，要做第二個事務(wù)，這時與B節(jié)點有交流，A加1，然后將時鐘帶到B節(jié)點，B節(jié)點直接從0跳到2。如此就在兩個時鐘之間建立了聯(lián)系，通過建立聯(lián)系，將兩個節(jié)點之間的邏輯時鐘拉平，這時候就構(gòu)建它們之間的happen before的關(guān)系，代表A節(jié)點的事務(wù)是在B節(jié)點的新事務(wù)開始之前完成的。

分布式數(shù)據(jù)庫中，如果兩個事務(wù)沒有操作同樣的節(jié)點，則兩個事務(wù)是無關(guān)的事務(wù)。無關(guān)的事務(wù)可以認為是沒有先后順序的。但是當一個事務(wù)橫跨多個節(jié)點的時候，將多個節(jié)點之間的關(guān)系建立起來，就變成有關(guān)系的事務(wù)，構(gòu)建的是事務(wù)間的因果序。

所謂因果序，如果同樣來了兩個事務(wù)，一個事務(wù)操作AB節(jié)點，另外一個事務(wù)操作BC節(jié)點，因為它們在B節(jié)點上建立了一個聯(lián)系。通過B節(jié)點的關(guān)系，將事務(wù)的順序維護起來。 

純邏輯時鐘可以起到因果一致性和因果序的能力。那邏輯時鐘最大的問題是什么呢?

最極端的情況下，節(jié)點和節(jié)點之間永遠不產(chǎn)生聯(lián)系，兩個節(jié)點之間的邏輯時鐘的差距會越來越大。這時如果兩個節(jié)點之間做查詢或者備份，需要強制將它們建立關(guān)系，那么兩節(jié)點之間的gap會變得非常大。

5、混合時鐘

雖然機器和機器之間物理時鐘有偏移，但如果有NTP校準或者Google的Truetime這種時鐘服務(wù)器話，其物理時鐘的差距是非常小的。

混合時鐘把分布式下的時鐘切成兩部分，上半部分用物理時鐘來填充，下半部分用邏輯時鐘來填充。填充在一起變成了一個HLC時鐘，既混合邏輯時鐘。它既有物理時鐘的部分，又有邏輯時鐘的部分。由于物理時鐘服務(wù)器之間的差距不會特別大，所以可以比較物理時鐘大小。而物理時鐘又有一定的偏差，在一定的偏差范圍內(nèi)，可以使用邏輯時鐘做校準。

下圖是混合邏輯時鐘的一個示例。當發(fā)送一個消息的時候，首先應(yīng)該把邏輯時鐘的物理時鐘部分與當前的時鐘做一個比較。如果當前的物理時鐘是4點，新事務(wù)產(chǎn)生后，因為物理時鐘沒變，新事務(wù)加在邏輯時鐘的部分(加1)。

如果物理時鐘從4點變成4：01，則將物理時鐘推進。物理時鐘如果不推進，就加邏輯時鐘。如果物理時鐘發(fā)生了變化就把物理時鐘往上推進，將邏輯時鐘部分置零。 

6、HLC和中心時鐘的差別

基于中心時鐘的方案的時間是通過事務(wù)ID來判斷的，從而為所以事物排序。分布式數(shù)據(jù)庫中，需要消除中心節(jié)點。一種方法是純邏輯時鐘，但邏輯時鐘之間無法比較大小。另一種方法是混合邏輯時鐘(HLC)，它為數(shù)據(jù)庫定義了一類因果關(guān)系的事務(wù)。

混合邏輯時鐘沒有中心節(jié)點，用本地的物理時間加上邏輯時間。本地產(chǎn)生的事務(wù)不保序，但是如果事務(wù)跨了節(jié)點，其因果聯(lián)系是有順序的。

如下圖T1，T2和T3代表提交時間，T1是一個分布式事務(wù)，T2是一個單機事務(wù)，T3是一個分布式事務(wù)。因為T1 是一個分布式事務(wù)，在數(shù)據(jù)庫節(jié)點上進1是比進2先執(zhí)行，所以在整個時鐘里面，進1小于進2，進1也小于進3。通過這種方式，將有關(guān)系的事務(wù)的順序排好。 

7、中心式 VS. 分布式 VS. Truetime

如下圖，中心式時鐘的優(yōu)點一目了然，它可以保證全局一致的時間。

分布式數(shù)據(jù)庫下的時鐘的優(yōu)點是無中心化的性能和無HA瓶頸，因為不需要中心的授時服務(wù)。分布式數(shù)據(jù)庫下的時鐘主要有兩個能力，第一個能力是可以做到計算和存儲的水平擴展。

另外，因為分布式數(shù)據(jù)庫把一個業(yè)務(wù)的workload拆分到了不同的機器上，從而單點故障帶來的影響減小了。把核心數(shù)據(jù)庫拆成了幾百份，任何一個單點數(shù)據(jù)庫故障帶來的整個系統(tǒng)可用性的下跌是非常小的。

這說明了為什么現(xiàn)在的分布式和互聯(lián)網(wǎng)+結(jié)合在一起比較火，一個很重要的原因是分布式降低了單點故障對業(yè)務(wù)帶來的的可用性的影響。

不僅僅是互聯(lián)網(wǎng)公司，包括金融類的銀行也想往分布式走，一個方面是為了解決容量和擴展性的問題，另外一方面也是為了解決高可用問題。

中心式的缺點是會有單點的single point of failure。分布式時鐘雖然消除了單點的影響，但是時鐘是不可以排序的，無法實現(xiàn)真正的外圍一致性。外圍一致性指的是每兩個事務(wù)都可以排序。而分布式時鐘只能對有關(guān)聯(lián)的事務(wù)進行排序，實現(xiàn)因果順序。

Google的Truetime的優(yōu)點是保證全局一致時間，簡化應(yīng)用開發(fā)。缺點首先是需要專有的硬件，如果Truetime的原子鐘授時的話，也會有一定的時鐘偏差，這個時鐘偏差物理上無法克服。Google Spanner的paper中可以發(fā)現(xiàn)每一個事務(wù)的提交都要等待一段時間，就是要等這段時鐘偏差。 

二、分布式事務(wù)管理

1、兩階段提交

分布式事務(wù)管理是為了保證全局讀寫原子性和隔離性。一個事務(wù)要跨兩個節(jié)點，這時候存在失敗的可能性。假如一個節(jié)點成功一個節(jié)點失敗，那么看到的結(jié)果就是不一致的，這喪失了事務(wù)的原子性。

還有一種是兩個節(jié)點上都提交成功，但是因為兩個節(jié)點本身的時間不一樣，導致提交的時間也不一樣。如果用MVCC去讀這個事務(wù)，能看到一半，另一半可能看不到，這樣就無法保證事務(wù)的原子性。

對于事務(wù)的原子性問題，目前相關(guān)技術(shù)已經(jīng)非常成熟，既兩階段提交。如果要保證一個分布式事務(wù)成功或者失敗，可以利用兩個階段提交技術(shù)，先做一個prepare事務(wù)，如果所有的prepare都可以，再做commit。

2、其它分布式事務(wù)管理技術(shù)

常見的分布式事務(wù)管理技術(shù)分為三類。

第一類是兩個階段提交技術(shù)，包含prepare階段和commit階段。

第二類基于MVOCC，其中FOUNDATION DB是蘋果開源的分布式數(shù)據(jù)庫，使用的是MVOCC，可以理解為OCC(optimistic concurrency control)。OCC指在事務(wù)提交時檢查是否有沖突，基于沖突有設(shè)置沖突檢測算法和權(quán)重算法，最后選擇毀掉或者提交哪個事務(wù)。對于鎖，在事前和在更新的時候加鎖，提交的時候檢查沖突。在沖突不劇烈的情況下，因為沒有加鎖開銷，整個吞吐非常高。在沖突劇烈的情況下，大量的abort事務(wù)會反復(fù)回滾。

第三類技術(shù)主要針對確定性事務(wù)，如FAUNA技術(shù)。

美國的一位教授提出了確定性事務(wù)，并基于確定性事務(wù)模型創(chuàng)辦了一家公司，創(chuàng)建了一個分布式數(shù)據(jù)庫(FAUNA)。確定性事務(wù)指事務(wù)是完整的，而不是交互型的。

比如，在淘寶這種互聯(lián)網(wǎng)企業(yè)處理的都是非確定性事務(wù)。非確定性事務(wù)只begin事務(wù)，select事務(wù)等，每個操作都是交互的，既APP需要跟DataBase做交互。

如果站在數(shù)據(jù)庫的視角，數(shù)據(jù)庫永遠無法預(yù)測下一條語句，這類事物是非確定性的。確定性事務(wù)是把一個事務(wù)所有的邏輯一次性寫好，然后發(fā)送給DataBase。DataBase收到事務(wù)的時候，清楚這個事務(wù)需要操作哪些表，讀取哪些記錄并進行哪些操作。從數(shù)據(jù)庫的視角來說事務(wù)是完全確定的。拿到一個確定性事務(wù)，可以事先將這些事務(wù)排好序。兩個事務(wù)之間如果操作相同的記錄，就排個先后，如果不操作相同的記錄，就并發(fā)的發(fā)出去。

使用這種方式可以做到既不用加鎖，也不用在事后提交的時候做沖突檢測。但是它的要求是事務(wù)不能是交互型的。

3、HLC和兩階段提交

混合邏輯時鐘(HLC)格式如下。如果有64個字節(jié)，首先預(yù)留5字節(jié)保證兼容性，在做系統(tǒng)設(shè)計的話，通常需要預(yù)留一些字節(jié)或以防出現(xiàn)一些問題時沒東西可用。中間再留43字節(jié)做物理時鐘。后面的16字節(jié)做邏輯時鐘。如果時鐘精確到毫秒級，43字節(jié)的物理時鐘意味著279年，表示數(shù)據(jù)庫不斷運行，279年不掛，一般來說這不太可能。

如果物理時鐘到天級，一天才能變一位，那物理時鐘就失去了意義。16字節(jié)是65536，65536意味著一毫秒內(nèi)可以發(fā)起65536個事務(wù)，。一般開始和結(jié)束的時候都要消耗兩個時鐘，除以二，既一毫秒內(nèi)可處理3萬多的事務(wù)，單節(jié)點一秒內(nèi)可以做到3千多萬事務(wù)。 

4、HLC時鐘偏移的問題

HLC和事務(wù)的吞吐有關(guān)系，因為它有物理時鐘，能夠展示不同的節(jié)點之間的時鐘差。如果真的出現(xiàn)了時鐘偏移怎么辦?

下圖提供了一個簡單的公式。沒有偏差的情況下，理論上節(jié)點可以做到3千萬的TPS，當然在工程上是做不到的。

如果兩個節(jié)點時鐘之間偏移量是5毫秒，那么在5毫秒之內(nèi)只能通過邏輯時鐘去彌補。如果原來6萬個邏輯時鐘在1毫秒內(nèi)就能做完，現(xiàn)在則需要5毫秒，導致整個事務(wù)的吞吐下降了600萬。所以時鐘偏移會導致peakTPS大幅下降。

下圖給出了幾種解決方案。比較簡單的是允許設(shè)置最大時鐘偏移，如果整個機房或者集群中兩個節(jié)點之間最大偏移超過了100毫秒，就把該異常節(jié)點清除。目前來看，機房都有NTP授時服務(wù)，所以發(fā)生如此大時鐘偏移的概率非常小。另一種方式是不清除異常節(jié)點，但是可以允許邏輯時鐘overflow到物理時鐘部分，使邏輯時鐘更大，這樣可以允許更多的事務(wù)在當前時鐘內(nèi)發(fā)生。