摘要：終于來(lái)到了，大家可以看到，它結(jié)合了以及，也就是說(shuō)，它會(huì)讓所有操作按照實(shí)時(shí)的順序依次操作，也就是所有的進(jìn)程會(huì)觀察到完全一致的順序，這也是最強(qiáng)的一致性模型了。

作者：唐劉 @siddontang

有時(shí)候，在跟一些同學(xué)討論 TiKV 事務(wù)模型的時(shí)候，我都提到了 Linearizability，也提到了 Snapshot Isolation，以及需要手動(dòng) lock 來(lái)保證 Serializable Snapshot Isolation，很多時(shí)候，當(dāng)我嘴里面蹦出來(lái)這些名詞的時(shí)候，有些同學(xué)就一臉懵逼了。所以我覺(jué)得有必要仔細(xì)來(lái)解釋一下，順帶讓我自己將所有的 isolation 以及 consistency 這些情況都?xì)w納總結(jié)一遍，讓自己也理解透徹一點(diǎn)。

幸運(yùn)的是，業(yè)內(nèi)已經(jīng)有很多人做了這個(gè)事情，譬如在?Highly Available Transactions: Virtues and Limitations?這篇論文里面，作者就總結(jié)了不同模型是否能滿(mǎn)足 Highly Available Transactions(HATs)。

圖中，紅色圓圈里面的模型屬于 Unavailable，藍(lán)色的屬于 Sticky Available，其余的就是 ?Highly Available。這里解釋下相關(guān)的含義：

Unavailable：當(dāng)出現(xiàn)網(wǎng)絡(luò)隔離等問(wèn)題的時(shí)候，為了保證數(shù)據(jù)的一致性，不提供服務(wù)。熟悉 CAP 理論的同學(xué)應(yīng)該清楚，這就是典型的 CP 系統(tǒng)了。

Sticky Available：即使一些節(jié)點(diǎn)出現(xiàn)問(wèn)題，在一些還沒(méi)出現(xiàn)故障的節(jié)點(diǎn)，仍然保證可用，但需要保證 client 的操作是一致的。

Highly Available：就是網(wǎng)絡(luò)全掛掉，在沒(méi)有出現(xiàn)問(wèn)題的節(jié)點(diǎn)上面，仍然可用。

Unavailable 比較容易理解，這里在討論下 Sticky 和 Highly，對(duì)于 Highly Available 來(lái)說(shuō)，如果一個(gè) server 掛掉了，client 可以去連接任意的其他 server，如果這時(shí)候仍然能獲取到結(jié)果，那么就是 Highly Available 的。但對(duì)于 Sticky 來(lái)說(shuō)，還需要保證 client 操作的一致性，譬如 client 現(xiàn)在 server 1 上面進(jìn)行了很多操作，這時(shí)候 server 1 掛掉了，client 切換到 server 2，但在 server 2 上面看不到 client 之前的操作結(jié)果，那么這個(gè)系統(tǒng)就不是 Sticky 的。所有能在 Highly Available 系統(tǒng)上面保證的事情一定也能在 Sticky Available 系統(tǒng)上面保證，但反過(guò)來(lái)就不一定了。

Jepsen 在官網(wǎng)上面有一個(gè)簡(jiǎn)化但更好看一點(diǎn)的圖

下面，我會(huì)按照 Jepsen 里面的圖，對(duì)不同的 model 進(jìn)行解釋一下。至于為啥選擇 Jepsen 里面的例子，一個(gè)是因?yàn)?Jepsen 現(xiàn)在是一款主流的測(cè)試不同分布式系統(tǒng)一致性的工具，它的測(cè)試用例就是測(cè)試的是上圖提到的模型，我們自然也會(huì)關(guān)心這些模型。另外一個(gè)就是這個(gè)模型已經(jīng)覆蓋了大多數(shù)場(chǎng)景了，理解了這些，大部分都能游刃有余處理了。

如果大家仔細(xì)觀察，可以發(fā)現(xiàn)，從根節(jié)點(diǎn) Strict Serializable，其實(shí)是有兩個(gè)分支的，一個(gè)對(duì)應(yīng)的就是數(shù)據(jù)庫(kù)里面的 Isolation（ACID 里面的 I），另一個(gè)其實(shí)對(duì)應(yīng)的是分布式系統(tǒng)的 Consistency（CAP 里面的 C），在 HATs 里面，叫做 Session Guarantees。

要對(duì) Isolation 有個(gè)快速的理解，其實(shí)只需要看?A Critique of ANSI SQL Isolation Levels?這篇論文就足夠了，里面詳細(xì)的介紹了數(shù)據(jù)庫(kù)實(shí)現(xiàn)中遇到的各種各樣的 isolation 問(wèn)題，以及不同的 isolation level 到底能不能解決。

在論文里面，作者詳細(xì)的列舉了多種異常現(xiàn)象，這里大概介紹一下。

Dirty Write 就是一個(gè)事務(wù)，覆蓋了另一個(gè)之前還未提交事務(wù)寫(xiě)入的值。假設(shè)現(xiàn)在我們有兩個(gè)事務(wù)，一個(gè)事務(wù)寫(xiě)入 x = y = 1，而另一個(gè)事務(wù)寫(xiě)入 x = y = 2，那么最終的結(jié)果，我們是希望看到 x 和 y 要不全等于 1，要不全等于 2。但在 Dirty Write 情況下面，可能會(huì)出現(xiàn)如下情況：

可以看到，最終的值是 x = 2 而 y = 1，已經(jīng)破壞了數(shù)據(jù)的一致性了。

Dirty Read 出現(xiàn)在一個(gè)事務(wù)讀取到了另一個(gè)還未提交事務(wù)的修改數(shù)據(jù)。假設(shè)現(xiàn)在我們有一個(gè)兩個(gè)賬戶(hù)，x 和 y，各自有 50 塊錢(qián)，x 需要給 y 轉(zhuǎn) 40 元錢(qián)，那么無(wú)論怎樣，x + y = 100 這個(gè)約束是不能打破的，但在 Dirty Read 下面，可能出現(xiàn)：

在事務(wù) T2，讀取到的 x + y = 60，已經(jīng)打破了約束條件了。

Fuzzy Read 也叫做 Non-Repeatable Read，也就是一個(gè)還在執(zhí)行的事務(wù)讀取到了另一個(gè)事務(wù)的更新操作，仍然是上面的轉(zhuǎn)賬例子：

在 T1 還在運(yùn)行的過(guò)程中，T2 已經(jīng)完成了轉(zhuǎn)賬，但 T1 這時(shí)候能讀到最新的值，也就是 x + y = 140 了，破壞了約束條件。

Phantom 通常發(fā)生在一個(gè)事務(wù)首先進(jìn)行了一次按照某個(gè)條件的 read 操作，譬如 SQL 里面的?SELECT WHERE P，然后在這個(gè)事務(wù)還沒(méi)結(jié)束的時(shí)候，另外的事務(wù)寫(xiě)入了一個(gè)新的滿(mǎn)足這個(gè)條件的數(shù)據(jù)，這時(shí)候這個(gè)新寫(xiě)入的數(shù)據(jù)就是 Phantom 的了。

假設(shè)現(xiàn)在 T1 按照某個(gè)條件讀取到了所有雇員 a，b，c，這時(shí)候 count 是 3，然后 T2 插入了一個(gè)新的雇員 d，同時(shí)更新了 count 為 4，但這時(shí)候 T1 在讀取 count 的時(shí)候會(huì)得到 4，已經(jīng)跟之前讀取到的 a，b，c 沖突了。

我們有時(shí)候也會(huì)遇到一種 Lost Update 的問(wèn)題，如下：

在上面的例子中，我們沒(méi)有任何 dirty write，因?yàn)?T2 在 T1 更新之前已經(jīng)提交成功，也沒(méi)有任何 dirty read，因?yàn)槲覀冊(cè)?write 之后沒(méi)有任何 read 操作，但是，當(dāng)整個(gè)事務(wù)結(jié)束之后，T2 的更新其實(shí)丟失了。

Cursor Lost Update 是上面 Lost Update 的一個(gè)變種，跟 SQL 的 cursor 相關(guān)。在下面的例子中，RC(x) 表明在 cursor 下面 read x，而 WC(x) 則表明在 cursor 下面寫(xiě)入 x。

如果我們?cè)试S T2 在 ?T1 RC 和 WC 之間寫(xiě)入數(shù)據(jù)，那么 T2 的更新也會(huì)丟失。

Read Skew 發(fā)生在兩個(gè)或者多個(gè)有完整性約束的數(shù)據(jù)上面，還是傳統(tǒng)的轉(zhuǎn)賬例子，需要保證 x + y = 100，那么 T1 就會(huì)看到不一致的數(shù)據(jù)了。

Write Skew 跟 Read Skew 比較類(lèi)似，假設(shè) x + y <= 100，T1 和 T2 在執(zhí)行的時(shí)候都發(fā)現(xiàn)滿(mǎn)足約束，然后 T1 更新了 y，而 T2 更新了 x，然后最終結(jié)果打破了約束，如下：

上面我們介紹了不同的異常情況，下面的表格說(shuō)明了，在不同的隔離級(jí)別下面，那些異常情況可能發(fā)生：

NP - Not Possible，在該隔離級(jí)別下面不可能發(fā)生

SP - Sometimes Possible，在該隔離級(jí)別下面有時(shí)候可能發(fā)生

P - Possible，在該隔離級(jí)別下面會(huì)發(fā)生

鑒于網(wǎng)上已經(jīng)對(duì)不同的 Isolation Level，尤其是 MySQL 的解釋的太多了，這里就簡(jiǎn)單的解釋一下。

Read Uncommitted - 能讀到另外事務(wù)未提交的修改。

Read Committed - 能讀到另外事務(wù)已經(jīng)提交的修改。

Cursor Stability - 使用 cursor 在事務(wù)里面引用特定的數(shù)據(jù)，當(dāng)一個(gè)事務(wù)用 cursor 來(lái)讀取某個(gè)數(shù)據(jù)的時(shí)候，這個(gè)數(shù)據(jù)不可能被其他事務(wù)更改，除非 cursor 被釋放，或者事務(wù)提交。

Monotonic Atomic View - 這個(gè)級(jí)別是 read committed 的增強(qiáng)，提供了一個(gè)原子性的約束，當(dāng)一個(gè)在 T1 里面的 write 被另外事務(wù) T2 觀察到的時(shí)候，T1 里面所有的修改都會(huì)被 T2 給觀察到。

Repeatable Read - 可重復(fù)讀，也就是對(duì)于某一個(gè)數(shù)據(jù)，即使另外的事務(wù)有修改，也會(huì)讀取到一樣的值。

Snapshot - 每個(gè)事務(wù)都會(huì)在各自獨(dú)立，一致的 snapshot 上面對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作。所有修改只有在提交的時(shí)候才會(huì)對(duì)外可見(jiàn)。如果 T1 修改了某個(gè)數(shù)據(jù)，在提交之前另外的事務(wù) T2 修改并提交了，那么 T1 會(huì)回滾。

Serializable - 事務(wù)按照一定順序執(zhí)行。

另外需要注意，上面提到的 isolation level 都不保證實(shí)時(shí)約束，如果一個(gè)進(jìn)程 A 完成了一次寫(xiě)入 w，然后另外的進(jìn)程 B 開(kāi)始了一次讀取 r，r 并不能保證觀察到 w 的結(jié)果。另外，在不同事務(wù)之間，這些 isolation level 也不保證不同進(jìn)程的順序。一個(gè)進(jìn)程可能在一次事務(wù)里面看到一次寫(xiě)入 w，但可能在后面的事務(wù)上面沒(méi)看到同樣的 w。事實(shí)上，一個(gè)進(jìn)程甚至可能看不到在這個(gè)進(jìn)程上面之前的寫(xiě)入，如果這些寫(xiě)入都是發(fā)生在不同的事務(wù)里面。有時(shí)候，他們還可能會(huì)對(duì)事務(wù)進(jìn)行排序，譬如將 write-only 的事務(wù)放到所有的 read 事務(wù)的后面。

要解決這些問(wèn)題，我們需要引入順序約束，這也就是下面 Session Guarantee 要干的事情。

在 HATs 論文里面，相關(guān)的概念叫做 Session Guarantee，主要是用來(lái)保證在一個(gè) session 里面的實(shí)時(shí)性約束以及客戶(hù)端的操作順序。

如果某個(gè)進(jìn)程讀到了一次寫(xiě)入 w1 寫(xiě)入的值 v，然后進(jìn)行了一次新的寫(xiě)入 w2，那么 w2 寫(xiě)入的值將會(huì)在 w1 之后可見(jiàn)。

如果一個(gè)進(jìn)程開(kāi)始了一次讀取 r1，然后在開(kāi)始另一次讀取 r2，那么 r2 不可能看到 r1 之前數(shù)據(jù)。

如果一個(gè)進(jìn)程先進(jìn)行了一次寫(xiě)入 w1，然后在進(jìn)行了一次寫(xiě)入 w2，那么所有其他的進(jìn)程都會(huì)觀察到 w1 在 w2 之前發(fā)生。

如果一個(gè)進(jìn)程先進(jìn)行了一次寫(xiě)入 w，然后后面執(zhí)行了一次讀取 r，那么 r 一定會(huì)看到 w 的改動(dòng)。

PRAM 就是 Pipeline Random Access Memory，對(duì)于單個(gè)進(jìn)程的寫(xiě)操作都被觀察到是順序的，但不同的進(jìn)程寫(xiě)會(huì)觀察到不同的順序。譬如下面這個(gè)操作是滿(mǎn)足 PRAM 的，但不滿(mǎn)足后面說(shuō)的 Causal。

Causal 確定了有因果關(guān)系的操作在所有進(jìn)程間的一致順序。譬如下面這個(gè)：

對(duì)于 P3 和 P4 來(lái)說(shuō)，無(wú)論是先讀到 2，還是先讀到 1， 都是沒(méi)問(wèn)題的，因?yàn)?P1 和 P2 里面的 write 操作并沒(méi)有因果性，是并行的。但是下面這個(gè)：

就不滿(mǎn)足 Cansal 的一致性要求了，因?yàn)閷?duì)于 P2 來(lái)說(shuō)，在 Write 2 之前，進(jìn)行了一次 Read 1 的操作，已經(jīng)確定了 Write 1 會(huì)在 Write 2 之前發(fā)生，也就是確定了因果關(guān)系，所以 P3 打破了這個(gè)關(guān)系。

Sequential 會(huì)保證操作按照一定順序發(fā)生，并且這個(gè)順序會(huì)在不同的進(jìn)程上面都是一致的。一個(gè)進(jìn)程會(huì)比另外的進(jìn)程超前，或者落后，譬如這個(gè)進(jìn)程可能讀到了已經(jīng)是陳舊的數(shù)據(jù)，但是，如果一個(gè)進(jìn)程 A 從進(jìn)程 B 讀到了某個(gè)狀態(tài)，那么它就不可能在讀到 B 之前的狀態(tài)了。

譬如下面的操作就是滿(mǎn)足 Sequential 的：

對(duì)于 P3 來(lái)說(shuō)，它仍然能讀到之前的 stale 狀態(tài) 1。但下面的就不對(duì)了：

對(duì)于 P3 來(lái)說(shuō)，它已經(jīng)讀到了最新的狀態(tài) 2，就不可能在讀到之前的狀態(tài) 1 了。

Linearizability 要求所有的操作都是按照一定的順序原子的發(fā)生，而這個(gè)順序可以認(rèn)為就是跟操作發(fā)生的時(shí)間一致的。也就是說(shuō)，如果一個(gè)操作 A 在 B 開(kāi)始之前就結(jié)束了，那么 B 只可能在 A 之后才能產(chǎn)生作用。

譬如下面的操作：

對(duì)于 P3 和 P4 來(lái)說(shuō)，因?yàn)橹耙呀?jīng)有新的寫(xiě)入，所以他們只能讀到 2，不可能讀到 1。

終于來(lái)到了 Strict Serializable，大家可以看到，它結(jié)合了 serializable 以及 linearizable，也就是說(shuō)，它會(huì)讓所有操作按照實(shí)時(shí)的順序依次操作，也就是所有的進(jìn)程會(huì)觀察到完全一致的順序，這也是最強(qiáng)的一致性模型了。

好了，最后再來(lái)聊聊 TiKV，TiKV 是一個(gè)支持分布式事務(wù)的 key-value database。對(duì)于某個(gè)事務(wù)，TiKV 會(huì)通過(guò) PD 這個(gè)服務(wù)在事務(wù)開(kāi)始的時(shí)候分配一個(gè) start timestamp，以及事務(wù)提交的時(shí)候分配一個(gè) commit timestamp。因?yàn)槲覀兊氖跁r(shí)是通過(guò) PD 這個(gè)單點(diǎn)服務(wù)進(jìn)行的，所以時(shí)間是一定能保證單調(diào)遞增的，也就是說(shuō)，我們所有的操作都能跟保證實(shí)時(shí)有序，也就是滿(mǎn)足 Linearizable。

TiKV 采用的是常用的 MVCC 模型，也就是每個(gè) key-value 實(shí)際存儲(chǔ)的時(shí)候，會(huì)在 key 上面帶一個(gè) timestamp，我們就可以用 timestamp 來(lái)生成整個(gè)數(shù)據(jù)庫(kù)的 snapshot 了，所以 TiKV 是 snapshot isolation 的。既然是 snapshot isolation，那么就會(huì)遇到 write skew 問(wèn)題，所以 TiKV 額外提供了 serializable snapshot isolation，用戶(hù)需要顯示的對(duì)要操作的數(shù)據(jù)進(jìn)行 lock 操作。

但現(xiàn)在 TiKV 并不支持對(duì) range 加 lock，所以不能完全的防止 phantom，譬如假設(shè)最多允許 8 個(gè)任務(wù)，現(xiàn)在已經(jīng)有 7 個(gè)任務(wù)了，我們還可以添加一個(gè)任務(wù)，但這時(shí)候另外一個(gè)事務(wù)也做了同樣的事情，但添加的是不同的任務(wù)，這時(shí)候就會(huì)變成 9 個(gè)任務(wù)，另外的事務(wù)在 scan 的時(shí)候就會(huì)發(fā)現(xiàn)打破了約束。這個(gè)也就是 A Critique of ANSI SQL Isolation Levels 里面提到的 sometimes possible。

所以，TiKV 是 snapshot isolation + linearizable。雖然 TiKV 也可以支持 Read Committed，但通常不建議在生產(chǎn)環(huán)境中使用，因?yàn)?TiKV 的 Read Committed 跟傳統(tǒng)的還不太一樣，可能會(huì)出現(xiàn)能讀到一個(gè)事務(wù)提交到某個(gè)節(jié)點(diǎn)的數(shù)據(jù)，但這時(shí)候在另外的節(jié)點(diǎn)還讀不到這個(gè)事務(wù)提交的數(shù)據(jù)，畢竟在分布式系統(tǒng)下面，不同節(jié)點(diǎn)的事務(wù)提交也是有網(wǎng)絡(luò)延遲的，不可能同時(shí)執(zhí)行。

在分布式系統(tǒng)里面，一致性是非常重要的一個(gè)概念，理解了它，在自己設(shè)計(jì)分布式系統(tǒng)的時(shí)候，就能充分的考慮到底系統(tǒng)應(yīng)該提供怎樣的一致性模型。譬如對(duì)于 TP 數(shù)據(jù)庫(kù)來(lái)說(shuō)，就需要有一個(gè)比較 strong 的一致性模型，而對(duì)于一些不重要的系統(tǒng)，譬如 cache 這些，就可以使用一些比較 weak 的模型。對(duì) TiKV 來(lái)說(shuō)，我們?cè)?Percolator 基礎(chǔ)上面，也一直在致力于分布式事務(wù)的優(yōu)化，如果你對(duì)這方面感興趣，歡迎聯(lián)系我 tl@pingcap.com。

線(xiàn)性一致性和 Raft

TiKV 是如何存取數(shù)據(jù)的