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

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

介紹

CockroachDB是一個支持SQL，支持分布式事務(wù)的ACID的分布式數(shù)據(jù)，支持ANSI SQL的最高隔離級別Serializability。

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

Serializable

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

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

一個事務(wù)通常包含多個讀寫操作，操作不同的行/列。數(shù)據(jù)庫系統(tǒng)會對系統(tǒng)中的事務(wù)進行調(diào)度，事務(wù)會交叉執(zhí)行，而不是一個接著一個。

?

一共三個事務(wù)，上圖是數(shù)據(jù)庫系統(tǒng)對這三個事務(wù)的一種調(diào)度。那么這個調(diào)度是不是Serializable的？這個有理論支持: serializability graph。這個理論引入了三種沖突，三種沖突都是對于不同的事務(wù)操作同一個數(shù)據(jù)而言：

• RW: W覆蓋了R讀到的值

• WR: R讀到了W更新的值

• WW: W覆蓋了第一個W更新的值

對于任何一個事務(wù)調(diào)度結(jié)果，如果兩個事務(wù)存在某種沖突，就在事務(wù)之間連上有向邊(后面的事務(wù)指向前面的事務(wù))。下圖是上面事務(wù)調(diào)度的serializability graph。

已經(jīng)證明如果一個事務(wù)調(diào)度的serializability graph中不存在環(huán)，那么這個事務(wù)調(diào)度就是Serializable的。那么CockroachDB是怎么做的?

CockroachDB事務(wù)處理系統(tǒng)

• 多版本

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

ACID中的A和I密切相關(guān)，都是通過并發(fā)控制協(xié)議保證的，下面先說明A是如何保證的，然后說明在并發(fā)的情況下，I是如何保證的。并發(fā)控制協(xié)議保證了A和I。

• 原子性

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

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

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

• 隔離性

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

frameborder="0" scrolling="no" style="border-width: medium; width: 600px; height: 450px;">

上面這個圖是無環(huán)的。下面這個圖是有環(huán)的：

frameborder="0" scrolling="no" style="border-width: medium; width: 600px; height: 450px;">

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

frameborder="0" scrolling="no" style="border-width: medium; width: 600px; height: 450px;">

CockroachDB保證如下約束:

• RW: W的時間戳只能比R的大，這只會產(chǎn)生回頭邊(通過在每個節(jié)點維護一個Read Timestamp Cache)。

• WR: R只會讀比自己timestamp小的最大的版本，這也只會產(chǎn)生回頭邊。

• WW:第二W的timestamp比第一個W的timestamp大，這也只會產(chǎn)生回頭邊。

也就是說，只要保證一個事務(wù)只與timestamp更小的事務(wù)沖突，就能保證無環(huán)。

• Recoverable

殘酷的是，僅僅保證無環(huán)能實現(xiàn)Serializability，同時還需要保持?jǐn)?shù)據(jù)庫的一致性，即ACID中的C。考慮如下場景:

T1，T2兩個事務(wù)，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使用一種比較苛刻的調(diào)度來處理這種場景：所有的操作只能在已經(jīng)committed的數(shù)據(jù)上進行！下面講講CockroachDB的這種苛刻的調(diào)度是如何保證的，這里就需要用到前面原子性的知識。

• Strict Scheduling

從上一節(jié)以及原子性章節(jié)可以得知，一個事務(wù)碰到了一個write intent，那么說明有可能寫write intent的事務(wù)還沒有結(jié)束(因為write intent是異步清除的)，這就說明有可能碰到了uncommitted的數(shù)據(jù)。這時，當(dāng)前事務(wù)會去檢查write intent所在的事務(wù)的狀態(tài)，如果已經(jīng)提交了，將write intent覆蓋舊值然后清除write intent即可。如果已經(jīng)回滾了，那么直接清除write intent就行。如果是Pending，正在運行呢？這個時候，就要看事務(wù)的優(yōu)先級了，優(yōu)先級低的事務(wù)需要abort，事務(wù)開始時賦予的優(yōu)先級是random的。CockroachDB會保證被abort的事務(wù)在restart之后優(yōu)先級會提高。

到這里，CockroachDB如何提供Serializability隔離級別就講完了，注意，這里的前提是每個事務(wù)都被賦予了一個合適的timestamp，什么叫做合適的 timestamp? 一個分布式讀/讀寫事務(wù)需要能讀到最新的已經(jīng)committed的數(shù)據(jù)。

• CockroachDB如何為事務(wù)賦予時間戳

CockroachDB使用NTP進行時鐘同步，NTP基本能保證機器之間的時鐘offset小于250ms，但是這也不絕對，這受到網(wǎng)絡(luò)延時，系統(tǒng)load等因素的影響。從前面可以看出，CockroachDB的Serializability依賴于集群內(nèi)機器之間的時鐘clock在一個范圍ε內(nèi)。這個范圍可以配置，默認(rèn)250ms。任何一個時刻，在一臺機器上拿到wall time為t，那么集群中可能存在的最大wall time是t+ε。

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

總結(jié)

總體來看，CockroachDB的并發(fā)控制協(xié)議是一個Lock-Free的，不加鎖的，樂觀的協(xié)議。對于數(shù)據(jù)競爭比較強的應(yīng)用不太適合，需要頻繁的restart事務(wù)。并且，NTP這個東西不能總是保證機器之間時鐘誤差在一個范圍內(nèi)，一旦超過這個范圍，就會違反Serializability。

參考文獻(xiàn)

Serializable, Lockless, Distributed: Isolation in CockroachDB

How CockroachDB Does Distributed, Atomic Transactions

CockroachDB beta-20160829

cockroachdb/cockroach

Living Without Atomic Clocks

Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases

原文地址：http://www.cnblogs.com/foxmailed/p/6885368.html

---

.NET社區(qū)新聞，深度好文，微信中搜索dotNET跨平臺或掃描二維碼關(guān)注

總結(jié)

以上是生活随笔為你收集整理的详解CockroachDB事务处理系统的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。