分布式事務實現：Spanner

Spanner要滿足的external consistency 是指：后開始的事務一定可以看到先提交的事務的修改。所有事務的讀寫都加鎖可以解決這個問題，缺點是性能較差。特別是對于一些workload中只讀事務 占比較大的系統來說不可接受。為了讓只讀事務不加任何鎖，需要引入多版本。在單機系統中，維護一個遞增的時間戳作為版本號很好辦。分布式系統中，機器和機 器之間的時鐘有誤差，并且誤差范圍不確定，帶來的問題就是很難判斷事件(在本文，事件指分布式事務版本號)發生的前后關系。反應在Spanner中，就是 很難給事務賦予一個時間戳作為版本號，以滿足external consistency。在這樣一個誤差范圍不確定的分布式系統時，通常，獲得兩個事件發生的先后關系主要通過在節點之間進行通信分析其中的因果關系 (casual relationship),經典算法包括Lamport時鐘等算法。然后，Spanner采用不同的思路，通過在數據中心配備原子鐘和GPS接收器來解 決這個誤差范圍不確定的問題，進而解決分布式事務時序這個問題。基于此，Spanner提供了TrueTime API，返回值實際為一個區間[t-ε,t+ε]，ε為時間誤差，毫秒級，保證當前的真實時間位于這個區間。

Spanner是一個支持分布式讀寫事務，只讀事務的分布式存儲系統，只讀事務不加任何鎖。和其他分布式存儲系統一樣，通過維護多副本來提高系 統的可用性。一份數據的多個副本組成一個paxos group，通過paxos協議維護副本之間的一致性。對于涉及到跨機的分布式事務，涉及到的每個paxos group中都會選出一個leader，來參與分布式事務的協調。這些個leader又會選出一個大leader，稱為coordinator leader，作為兩階段提交的coordinator，記作coordinator leader。其他leader作為participant。

數據庫事務系統的核心挑戰之一是并發控制協議。Spanner的讀寫事務使用兩階段鎖來處理。分布式讀寫事務請求到達coordinator leader后，coordinator leader運行兩階段提交協議，將讀寫請求發給participant，pariticpant和coordinator leader開始加讀，寫鎖。最后commit的時候，讀寫鎖解除。

如第一段所述，給事務賦予一個時間戳版本號是這樣一個分布式存儲系統的核心。下面先說如何確定讀寫事務的版本號，再說只讀事務。

前面已經說了兩階段提交過程中兩階段鎖的過程，這里就省略這些，只討論兩階段提交過程中如何確定最后的讀寫事務的時間戳版本號。

讀寫事務 

讀寫事務開始時，coordinator leader 首先調用TrueTime API，獲得一個時間區間[t1-ε1,t1+ε1]，然后給所有的participants發送prepare消息，participants收到 prepare消息后，調TrueTime API返回區間[PB,PE]，然后取PB和這個participants維護的已commit的事務版本號的最大值。記participant維護的已 commit的最大事務時間戳為maxtimestamp,那么將max(maxtimestamp+1, PB)返回給coordinator leader。coordinator leader收集到所有prepare的時間戳后，從中選出一個最大的，記作maxpreparetimestamp，同時coordinator需要再 次調用一次TrueTime API，獲得時間區間[t2-ε2,t2+ε2]，為了保證這個分布式事務的時間戳確實位于這個分布式事務執行過程中的某個點，coordinator leader必須為這個分布式事務選擇一個介于[t1+ε1,t2-ε2]的時間戳。顯然這需要t1+ε1 < t2-ε2.可以看出，Spanner必須等到t1+ε1 < t2-ε2成立之后，才能提交這個事務。另外，這個分布式事務的時間戳還必須滿足一個條件，就是大于maxpreparetimestamp。從B的角度 來看，如果本地已提交事務版本號比要讀的版本號大，就可以讀。這就要保證后面提交的單機事務和分布式事務版本號都要比現在已提交事務的版本號更大。否則， 讀的時候可能會有事務插進來，導致都到的數據可能不是一個快照。

另外，一臺機器在收到快照讀時，有可能需要阻塞。舉個例子，在分布式系統中，即有分布式事務也有單機事務，以A，B，C為例，A為 coordinator leader，B和C為participant，以B為例，假設B當前維護的本機最大的commit時間戳為100，現在從A來了一個分布式事務T1的 prepare請求，B返回了101給A，在這個分布式事務commit之前，B機器來了一個單機事務T2，并且先于T1提交，時間戳為105，而A可能 為這個分布式事務指定的版本號為104. 顯然，如果在T1提交前來了一個大于101比如110的快照讀事務，這個快照讀事務必須被阻塞住直到T1提交才能向客戶端返回結果，因為B不知道T1這個 還未commit的事務最后的時間戳是多少。

只讀事務

一種方法是詢問一邊所有的participants，從所有的commit timestamp中拿出最大的作為時間戳去讀即可。或者調用TrueTime API，將右區間作為只讀事務的版本號即可。

下面說一下兩階段提交的錯誤處理。

兩階段提交協議由于協調者和參與者的故障可能會有嚴重的可用性問題。Spanner的兩階段提交實現基于Paxos協議，每個 participant和coordinator本身產生的日志都會通過Paxos協議復制到自身的Paxos group中，從而解決可用性問題。同樣以A，B，C三份數據為例，他們分別有三個副本，記作(A1，A2，A3)，(B1，B2，B3)， (C1，C2，C3)，每組作為一個Paxos group，內部通過paxos協議保證一致性。假設，A1，B1，C1分別為各自paxos group的leader，A1為coordinator leader。

Prepare階段：A1給B1和C1發送prepare消息后，假設B1掛了，A1等待超時，A1給C1發送rollback。B1后續回滾 分為兩種情況：1. B1在持久化prepare消息之前掛了，B1恢復后可自行回滾 2. 如果B1持久化prepare消息之后掛了，B1自身可以回放日志得知事務未決，主動聯系(A1,A2,A3)。A1給B1，C1發送prepare消息 之后，自己掛了，同樣，A1通過回放日志可以得知。實際上，A1本身掛了之后，A2和A3通過選主協議馬上會選出一個新的leader，不至于影響到可用 性。

Commit階段：A1給B1，C1發送commit消息，B1 commit成功，C1掛了，C1起來后，如果C1之前沒有持久化commit消息，則A1主動要求C1繼續commit。如果C1之前已經持久化了 commit消息，則自己commit。如果C1由于某些原因，始終commit不成功，則由上層業務進行回補操作。