詳解CockroachDB事務處理系統

本文提到的一些術語，比如Serializability和Linearizability，解釋看Linearizability, Serializability and Strict Serializability。

本文中觀點大部分都是參考了CockroachDB多篇官方blog,設計文檔，代碼以及相關資料，相對來說比較瑣碎，而且有些地方沒有交代的太清楚，這裡嘗試將這些資料融合起來。相信看完這篇文章，再看官方文檔會更容易。

介紹

CockroachDB是一個支持SQL，支持分散式事務的ACID的分散式數據，支持ANSI SQL的最高隔離級別Serializability。

在一個分散式系統中，要支持Linearizability比較難，因為不同的機器之間時鐘有誤差，需要一個全局時鐘。TiDB選擇了和Percolator一樣的方案，單點timestamp oracle提供時鐘源。Google Spanner直接搞了一個基於硬體的TrueTime API提供相對來說比較精準的時鐘。CockroachDB沒有原子鐘，也沒有使用單點timestamp oracle，而是基於NTP來盡量同步機器之間的時鐘偏移，NTP誤差能達到250ms甚至更多，並且不能嚴格保證，這導致CockroachDB要保證Linearizability一致性很難，並且性能差。最終雖然CockroachDB支持Linearizability，但是官方不推薦。默認，CockroachDB支持Serializable隔離級別，但是不保證Linearizability。

Serializable

一個真實的資料庫系統同一時刻會有很多並發的事務在執行，如何讓這些事務覺得只有自己運行在資料庫中不受其他事務的任何干擾是一個隔離級別的問題。Serializable就是不受任何干擾，弱一點的隔離級別有Repeatable Read, Read Committed, Read Uncommitted，Snapshot Isolation這些隔離級別多多少少會覺得受到了其他事務的干擾，如Repeatable Read有幻讀問題，Snapshot Isolation有write skew問題，具體不贅述。可以參考a-critique-of-ansi-sql-isolation-levels

要實現一個支持Serializable隔離級別的資料庫挺難的，很多資料庫都不支持Serializable隔離級別，原因有幾個，我覺得最重要的原因是性能不行。Oracle 11g默認隔離級別RC，最高隔離級別Snapshot Isolation，業界一些知名資料庫對隔離級別的支持看When is "ACID" ACID? Rarely. 然而CockroachDB為了實現Serializable，花了大量的功夫。

一個事務通常包含多個讀寫操作，操作不同的行/列。資料庫系統會對系統中的事務進行調度，事務會交叉執行，而不是一個接著一個。

一共三個事務，上圖是資料庫系統對這三個事務的一種調度。那麼這個調度是不是Serializable的？這個有理論支持: serializability graph。這個理論引入了三種衝突，三種衝突都是對於不同的事務操作同一個數據而言：

• RW: W覆蓋了R讀到的值
• WR: R讀到了W更新的值
• WW: W覆蓋了第一個W更新的值

對於任何一個事務調度結果，如果兩個事務存在某種衝突，就在事務之間連上有向邊(後面的事務指向前面的事務)。下圖是上面事務調度的serializability graph:

已經證明如果一個事務調度的serializability graph中不存在環，那麼這個事務調度就是Serializable的。那麼CockroachDB是怎麼做的?

CockroachDB事務處理系統

• 多版本

CockroachDB的事務是Lock-Free的，不需要加任何讀寫鎖，自然就需要維護數據的多個版本，版本通過timestamp來標識。

ACID中的A和I密切相關，都是通過並發控制協議保證的，下面先說明A是如何保證的，然後說明在並發的情況下，I是如何保證的。並發控制協議保證了A和I。

• 原子性

一個分散式事務可能會對多個節點上的數據進行讀寫，如何保證原子性? 大家都知道分散式事務都是2PC，第一階段做Prepare，把需要的讀的數據讀進來(怎麼保證讀到最新的數據，後面會說，這裡先假設能讀到)，計算，最後把計算後的數據寫入各個節點，但是不對外生效，即系統中其他事務暫且讀不到這個數據。這種已經寫入各個節點，但是沒有生效的數據CockroachDB把它叫做write intent，這種write intent和實際的數據存儲在一起，只是外部讀不到而已。

那麼這個事務的狀態存在哪？事實上，在一個事務開始的時候，會往底層存儲系統中寫入一條記錄，這個記錄叫做Transaction Record，record會記錄事務ID，事務狀態，Pending(正在運行)還是Committed，還是Aborted，而write intent里存在key指向這個Transaction Record。提交事務，只需要把Transaction Record中的事務狀態改成Committed即可，回滾事務改成Aborted即可。一旦事務狀態修改成功，就可以返回給客戶端，遺留的write intent會非同步處理：commit時，將write intent的值覆蓋原始值，刪掉write intent，rollback時直接刪掉write intent即可。

隨後客戶端過來讀的時候，如果碰到了write intent(之前說了，write intent是非同步刪除)，就會沿著write intent找到Transaction Record，看看事務的狀態，如果狀態是committed，返回write intent中的值，如果Abort就會返回原始的值。如果是Pending，說明這個事務還在正常跑，遇到了寫寫衝突，如何解決寫寫衝突? 這個牽扯到隔離級別和並發控制協議，看下面。

• 隔離性

之前提到，數據是多版本的，版本通過timestamp來標識。timestamp是讀寫事務/寫事務在事務開始的時候從本機拿到的wall time(實際上是HLC，一種基於物理時鐘的可以捕獲因果關係的邏輯時鐘)，這個timestamp只是這個事務最後commit的候選timestamp而已，不一定是最終的commit的timestamp(根本原因是機器之間存在時鐘offset，後面會講到)，這裡先假定，拿到了一個最終的timestamp。timestamp越大，說明版本越新。這個事務的所有寫入的數據都會打上這個timestamp作為版本標識。在這樣一個系統中，serializability graph大概是下面的樣子：

上面這個圖是無環的。下面這個圖是有環的：

回到Serializability，為了實現Serializability，需要保證事務的調度是無環的。CockroachDB通過在timestamp的反方向避免之前提到的三種衝突，從而在圖中就不會有和timestamp走向一致的邊，進而保證無環。最後，CockroachDB的serializability graph長如下樣子：

CockroachDB保證如下約束:

• RW: W的時間戳只能比R的大，這隻會產生回頭邊(通過在每個節點維護一個Read Timestamp Cache)。
• WR: R只會讀比自己timestamp小的最大的版本，這也只會產生回頭邊。
• WW:第二W的timestamp比第一個W的timestamp大，這也只會產生回頭邊。

也就是說，只要保證一個事務只與timestamp更小的事務衝突，就能保證無環。

• Recoverable

殘酷的是，僅僅保證無環能實現Serializability，同時還需要保持資料庫的一致性，即ACID中的C。考慮如下場景:

T1，T2兩個事務，timestamp(T1) < timestamp(T2)，T1更新A，還沒有提交，T2讀A。這是一個WR衝突，但是由於這個衝突是回頭邊，所以是允許的。為了維護上面提到的RW約束，T2必須讀T1的更新(W的timestamp必須比R大，然而T1比T2小)。然而，T2讀T1對A的更新有什麼問題?

• T2讀T1的更新。如果最後T2 commit，隨後T1回滾，這個會違反T1的原子性：T1沒有寫成功的值被T2讀到了。

CockroachDB使用一種比較苛刻的調度來處理這種場景：所有的操作只能在已經committed的數據上進行！下面講講CockroachDB的這種苛刻的調度是如何保證的，這裡就需要用到前面原子性的知識。

• Strict Scheduling

從上一節以及原子性章節可以得知，一個事務碰到了一個write intent，那麼說明有可能寫write intent的事務還沒有結束(因為write intent是非同步清除的)，這就說明有可能碰到了uncommitted的數據。這時，當前事務會去檢查write intent所在的事務的狀態，如果已經提交了，將write intent覆蓋舊值然後清除write intent即可。如果已經回滾了，那麼直接清除write intent就行。如果是Pending，正在運行呢？這個時候，就要看事務的優先順序了，優先順序低的事務需要abort，事務開始時賦予的優先順序是random的。CockroachDB會保證被abort的事務在restart之後優先順序會提高。

到這裡，CockroachDB如何提供Serializability隔離級別就講完了，注意，這裡的前提是每個事務都被賦予了一個合適的timestamp，什麼叫做合適的 timestamp? 一個分散式讀/讀寫事務需要能讀到最新的已經committed的數據。

• CockroachDB如何為事務賦予時間戳

CockroachDB使用NTP進行時鐘同步，NTP基本能保證機器之間的時鐘offset小於250ms，但是這也不絕對，這受到網路延時，系統load等因素的影響。從前面可以看出，CockroachDB的Serializability依賴於集群內機器之間的時鐘clock在一個範圍ε內。這個範圍可以配置，默認250ms。任何一個時刻，在一台機器上拿到wall time為t，那麼集群中可能存在的最大wall time是t+ε。

一個事務T開始時，先拿一個本地Wall time(實際上是HLC)，記作t,根據NTP定義，集群內機器此刻最大的Wall time為t+ε，如果事務執行過程中讀到的數據對象處於[t,t+ε]之間，我們是不知道這個值到底是在T開始之後才commit的，還是T開始之前就commit的。所以T需要restart，重新設置t為碰到的這個timestamp。

總結

總體來看，CockroachDB的並發控制協議是一個Lock-Free的，不加鎖的，樂觀的協議。對於數據競爭比較強的應用不太適合，需要頻繁的restart事務。並且，NTP這個東西不能總是保證機器之間時鐘誤差在一個範圍內，一旦超過這個範圍，就會違反Serializability。

參考文獻

Serializable, Lockless, Distributed: Isolation in CockroachDBHow CockroachDB Does Distributed, Atomic TransactionsCockroachDB beta-20160829cockroachdb/cockroachLiving Without Atomic ClocksLogical Physical Clocks and Consistent Snapshots in Globally Distributed Databases
推薦閱讀：