有時候朱监，在跟一些同學(xué)討論 TiKV 事務(wù)模型的時候，我都提到了 Linearizability，也提到了 Snapshot Isolation臀玄，以及需要手動 lock 來保證 Serializable Snapshot Isolation，很多時候畅蹂，當我嘴里面蹦出來這些名詞的時候健无，有些同學(xué)就一臉懵逼了。所以我覺得有必要仔細來解釋一下液斜，順帶讓我自己將所有的 isolation 以及 consistency 這些情況都歸納總結(jié)一遍累贤，讓自己也理解透徹一點。

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

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

• Unavailable: 當出現(xiàn)網(wǎng)絡(luò)隔離等問題的時候论巍，為了保證數(shù)據(jù)的一致性烛谊，不提供服務(wù)。熟悉 CAP 理論的同學(xué)應(yīng)該清楚嘉汰，這就是典型的 CP 系統(tǒng)了丹禀。
• Sticky Available: 即使一些節(jié)點出現(xiàn)問題，在一些還沒出現(xiàn)故障的節(jié)點鞋怀，仍然保證可用双泪，但需要保證 client 的操作是一致的。
• Highly Available: 就是網(wǎng)絡(luò)全掛掉密似，在沒有出現(xiàn)問題的節(jié)點上面焙矛，仍然可用。

Unavailable 比較容易理解残腌，這里在討論下 Sticky 和 Highly村斟，對于 Highly Available 來說贫导，如果一個 server 掛掉了，client 可以去連接任意的其他 server蟆盹，如果這時候仍然能獲取到結(jié)果孩灯，那么就是 Highly Available 的。但對于 Sticky 來說逾滥，還需要保證 client 操作的一致性钱反，譬如 client 現(xiàn)在 server 1 上面進行了很多操作，這時候 server 1 掛掉了匣距，client 切換到 server 2面哥，但在 server 2 上面看不到 client 之前的操作結(jié)果，那么這個系統(tǒng)就不是 Sticky 的毅待。所有能在 Highly Available 系統(tǒng)上面保證的事情一定也能在 Sticky Available 系統(tǒng)上面保證尚卫，但反過來就不一定了。

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

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

如果大家仔細觀察芙委，可以發(fā)現(xiàn)，從根節(jié)點 Strict Serializable狂秦，其實是有兩個分支的灌侣，一個對應(yīng)的就是數(shù)據(jù)庫里面的 Isolation（ACID 里面的 I），另一個其實對應(yīng)的是分布式系統(tǒng)的 Consistency（CAP 里面的 C）裂问，在 HATs 里面侧啼，叫做 Session Guarantees。

Isolation

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

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

P0 - Dirty Write

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

+------+-------+-------+-------+-------+
| T1   | Wx(1) |       |       | Wy(1) |
+------+-------+-------+-------+-------+
| T2   |       | Wx(2) | Wy(2) |       |
+------+-------+-------+-------+-------+
| x(0) | 1     | 2     | 2     | 2     |
+------+-------+-------+-------+-------+
| y(0) | 0     | 0     | 2     | 1     |
+------+-------+-------+-------+-------+

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

P1 - Dirty Read

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

+-------+--------+--------+--------+--------+
| T1    | Wx(10) |        |        | Wy(90) |
+-------+--------+--------+--------+--------+
| T2    |        | Rx(10) | Ry(50) |        |
+-------+--------+--------+--------+--------+
| x(50) | 10     | 10     | 10     | 10     |
+-------+--------+--------+--------+--------+
| y(50) | 50     | 50     | 50     | 90     |
+-------+--------+--------+--------+--------+

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

P2 - Fuzzy Read

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

+-------+--------+--------+--------+--------+
| T1    | Rx(50) |        |        | Ry(90) |
+-------+--------+--------+--------+--------+
| T2    |        | Wx(10) | Wy(90) |        |
+-------+--------+--------+--------+--------+
| x(50) | 50     | 10     | 10     | 10     |
+-------+--------+--------+--------+--------+
| y(50) | 50     | 50     | 90     | 90     |
+-------+--------+--------+--------+--------+

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

P3 - Phantom

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

+----------------+-----------+--------------+--------------+--------------+
| T1             | {a, b, c} |              |              | R(4)         |
+----------------+-----------+--------------+--------------+--------------+
| T2             |           | W(d)         | W(4)         |              |
+----------------+-----------+--------------+--------------+--------------+
| Employees      | {a, b, c} | {a, b, c, d} | {a, b, c, d} | {a, b, c, d} |
+----------------+-----------+--------------+--------------+--------------+
| Employee Count | 3         | 3            | 4            | 4            |
+----------------+-----------+--------------+--------------+--------------+

假設(shè)現(xiàn)在 T1 按照某個條件讀取到了所有雇員 a匹耕，b，c荠雕，這時候 count 是 3稳其，然后 T2 插入了一個新的雇員 d驶赏，同時更新了 count 為 4，但這時候 T1 在讀取 count 的時候會得到 4既鞠，已經(jīng)跟之前讀取到的 a煤傍，b，c 沖突了嘱蛋。

P4 - Lost Update

我們有時候也會遇到一種 Lost Update 的問題蚯姆，如下

+--------+-----+---------+---------+
| T1     |     |         | Wx(110) |
+--------+-----+---------+---------+
| T2     |     | Wx(120) |         |
+--------+-----+---------+---------+
| x(100) | 100 | 120     | 110     |
+--------+-----+---------+---------+

在上面的例子中，我們沒有任何 dirty write洒敏，因為 T2 在 T1 更新之前已經(jīng)提交成功龄恋，也沒有任何 dirty read，因為我們在 write 之后沒有任何 read 操作凶伙，但是郭毕，當整個事務(wù)結(jié)束之后，T2 的更新其實丟失了镊靴。

P4C - Cursor Lost Update

Cursor Lost Update 是上面 Lost Update 的一個變種铣卡，跟 SQL 的 cursor 相關(guān)。在下面的例子中偏竟，RC(x) 表明在 cursor 下面 read x煮落，而 WC(x) 則表明在 cursor 下面寫入 x。

+--------+----------+---------+----------+
| T1     | RCx(100) |         | Wx(110) |
+--------+----------+---------+----------+
| T2     |          | Wx(75) |          |
+--------+----------+---------+----------+
| x(100) | 100      | 75      | 110      |
+--------+----------+---------+----------+

如果我們允許 T2 在 T1 RC 和 WC 之間寫入數(shù)據(jù)踊谋，那么 T2 的更新也會丟失蝉仇。

A5A - Read Skew

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

+-------+--------+--------+--------+--------+
| T1    | Rx(50) |        |        | Ry(75) |
+-------+--------+--------+--------+--------+
| T2    |        | Wx(25) | Wy(75) |        |
+-------+--------+--------+--------+--------+
| x(50) | 50     | 25     | 25     | 25     |
+-------+--------+--------+--------+--------+
| y(50) | 50     | 50     | 75     | 75     |
+-------+--------+--------+--------+--------+

A5B - Write Skew

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

+-------+--------+--------+--------+--------+
| T1    | Rx(30) | Ry(10) | Wy(60) |        |
+-------+--------+--------+--------+--------+
| T2    | Rx(30) | Ry(10) |        | Wx(50) |
+-------+--------+--------+--------+--------+
| x(30) | 30     | 30     | 30     | 50     |
+-------+--------+--------+--------+--------+
| y(10) | 10     | 10     | 60     | 60     |
+-------+--------+--------+--------+--------+

Isolation Levels

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

• NP - Not Possible咕娄，在該隔離級別下面不可能發(fā)生
• SP - Sometimes Possible亥揖，在該隔離級別下面有時候可能發(fā)生
• P - Possible，在該隔離級別下面會發(fā)生

鑒于網(wǎng)上已經(jīng)對不同的 Isolation Level圣勒，尤其是 MySQL 的解釋的太多了费变，這里就簡單的解釋一下摧扇。

• Read Uncommitted - 能讀到另外事務(wù)未提交的修改。
• Read Committed - 能讀到另外事務(wù)已經(jīng)提交的修改胡控。
• Cursor Stability - 使用 cursor 在事務(wù)里面引用特定的數(shù)據(jù)扳剿，當一個事務(wù)用 cursor 來讀取某個數(shù)據(jù)的時候，這個數(shù)據(jù)不可能被其他事務(wù)更改昼激，除非 cursor 被釋放庇绽，或者事務(wù)提交。
• Monotonic Atomic View - 這個級別是 read committed 的增強橙困，提供了一個原子性的約束瞧掺，當一個在 T1 里面的 write 被另外事務(wù) T2 觀察到的時候，T1 里面所有的修改都會被 T2 給觀察到凡傅。
• Repeatable Read - 可重復(fù)讀辟狈，也就是對于某一個數(shù)據(jù)，即使另外的事務(wù)有修改夏跷，也會讀取到一樣的值哼转。
• Snapshot - 每個事務(wù)都會在各自獨立，一致的 snapshot 上面對數(shù)據(jù)庫進行操作槽华。所有修改只有在提交的時候才會對外可見壹蔓。如果 T1 修改了某個數(shù)據(jù)，在提交之前另外的事務(wù) T2 修改并提交了猫态，那么 T1 會回滾佣蓉。
• Serializable - 事務(wù)按照一定順序執(zhí)行。

另外需要注意亲雪，上面提到的 isolation level 都不保證實時約束勇凭，如果一個進程 A 完成了一次寫入 w，然后另外的進程 B 開始了一次讀取 r义辕，r 并不能保證觀察到 w 的結(jié)果虾标。另外，在不同事務(wù)之間灌砖，這些 isolation level 也不保證不同進程的順序夺巩。一個進程可能在一次事務(wù)里面看到一次寫入 w，但可能在后面的事務(wù)上面沒看到同樣的 w周崭。事實上，一個進程甚至可能看不到在這個進程上面之前的寫入喳张，如果這些寫入都是發(fā)生在不同的事務(wù)里面续镇。有時候，他們還可能會對事務(wù)進行排序销部，譬如將 write-only 的事務(wù)放到所有的 read 事務(wù)的后面摸航。

要解決這些問題制跟，我們需要引入順序約束，這也就是下面 Session Guarantee 要干的事情酱虎。

Session Guarantee

在 HATs 論文里面雨膨，相關(guān)的概念叫做 Session Guarantee，主要是用來保證在一個 session 里面的實時性約束以及客戶端的操作順序读串。

Writes Follow Reads

如果某個進程讀到了一次寫入 w1 寫入的值 v聊记，然后進行了一次新的寫入 w2，那么 w2 寫入的值將會在 w1 之后可見恢暖。

Monotonic Reads

如果一個進程開始了一次讀取 r1排监，然后在開始另一次讀取 r2，那么 r2 不可能看到 r1 之前數(shù)據(jù)杰捂。

Monotonic Writes

如果一個進程先進行了一次寫入 w1舆床，然后在進行了一次寫入 w2，那么所有其他的進程都會觀察到 w1 在 w2 之前發(fā)生嫁佳。

Read Your Writes

如果一個進程先進行了一次寫入 w挨队，然后后面執(zhí)行了一次讀取 r，那么 r 一定會看到 w 的改動蒿往。

PRAM

PRAM 就是 Pipeline Random Access Memory盛垦，對于單個進程的寫操作都被觀察到是順序的，但不同的進程寫會觀察到不同的順序熄浓。譬如下面這個操作是滿足 PRAM 的情臭，但不滿足后面說的 Causal。

+----+------+------+------+------+------+
| P1 | W(1) |      |      |      |      |
+----+------+------+------+------+------+
| P2 |      | R(1) | W(2) |      |      |
+----+------+------+------+------+------+
| P3 |      |      |      | R(2) | R(1) |
+----+------+------+------+------+------+
| P4 |      |      |      | R(1) | R(2) |
+----+------+------+------+------+------+

Causal

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

+----+------+------+------+------+------+------+
| P1 | W(1) |      |      |      |      |      |
+----+------+------+------+------+------+------+
| P2 |      | W(2) |      |      |      |      |
+----+------+------+------+------+------+------+
| P3 |      |      | R(2) |      | R(1) |      |
+----+------+------+------+------+------+------+
| P4 |      |      |      | R(1) |      | R(2) |
+----+------+------+------+------+------+------+

對于 P3 和 P4 來說俯在，無論是先讀到 2，還是先讀到 1娃惯， 都是沒問題的跷乐，因為 P1 和 P2 里面的 write 操作并沒有因果性，是并行的趾浅。但是下面這個

+----+------+------+------+------+------+------+
| P1 | W(1) |      |      |      |      |      |
+----+------+------+------+------+------+------+
| P2 |      | R(1) | W(2) |      |      |      |
+----+------+------+------+------+------+------+
| P3 |      |      |      | R(2) | R(1) |      |
+----+------+------+------+------+------+------+
| P4 |      |      |      | R(1) |      | R(2) |
+----+------+------+------+------+------+------+

就不滿足 Cansal 的一致性要求了愕提，因為對于 P2 來說，在 Write 2 之前皿哨，進行了一次 Read 1 的操作浅侨，已經(jīng)確定了 Write 1 會在 Write 2 之前發(fā)生，也就是確定了因果關(guān)系证膨，所以 P3 打破了這個關(guān)系如输。

Sequential

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

譬如下面的操作就是滿足 Sequential 的

+----+------+------+------+------+------+------+
| P1 | W(1) |      |      |      |      |      |
+----+------+------+------+------+------+------+
| P2 |      | W(2) |      |      |      |      |
+----+------+------+------+------+------+------+
| P3 |      |      | R(1) |      | R(2) |      |
+----+------+------+------+------+------+------+
| P4 |      |      |      | R(2) |      | R(2) |
+----+------+------+------+------+------+------+

對于 P3 來說灶似，它仍然能讀到之前的 stale 狀態(tài) 1列林。但下面的就不對了：

+----+------+------+------+------+------+------+
| P1 | W(1) |      |      |      |      |      |
+----+------+------+------+------+------+------+
| P2 |      | W(2) |      |      |      |      |
+----+------+------+------+------+------+------+
| P3 |      |      | R(2) |      | R(1) |      |
+----+------+------+------+------+------+------+
| P4 |      |      |      | R(2) |      | R(2) |
+----+------+------+------+------+------+------+

對于 P3 來說，它已經(jīng)讀到了最新的狀態(tài) 2喻奥，就不可能在讀到之前的狀態(tài) 1 了席纽。

Linearizable

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

譬如下面的操作：

+----+------+------+------+------+------+
| P1 | W(1) |      |      |      |      |
+----+------+------+------+------+------+
| P2 |      | W(2) |      |      |      |
+----+------+------+------+------+------+
| P3 |      |      | R(2) | R(2) |      |
+----+------+------+------+------+------+
| P4 |      |      |      | R(2) | R(2) |
+----+------+------+------+------+------+

對于 P3 和 P4 來說纺铭，因為之前已經(jīng)有新的寫入，所以他們只能讀到 2刀疙，不可能讀到 1舶赔。

Strict Serializable

終于來到了 Strict Serializable，大家可以看到谦秧，它結(jié)合了 serializable 以及 linearizable竟纳，也就是說，它會讓所有操作按照實時的順序依次操作疚鲤，也就是所有的進程會觀察到完全一致的順序锥累，這也是最強的一致性模型了。

TiKV

好了集歇，最后再來聊聊 TiKV桶略，TiKV 是一個支持分布式事務(wù)的 key-value database。對于某個事務(wù)诲宇，TiKV 會通過 PD 這個服務(wù)在事務(wù)開始的時候分配一個 start timestamp际歼，以及事務(wù)提交的時候分配一個 commit timestamp。因為我們的授時是通過 PD 這個單點服務(wù)進行的姑蓝，所以時間是一定能保證單調(diào)遞增的鹅心，也就是說，我們所有的操作都能跟保證實時有序纺荧，也就是滿足 Linearizable巴帮。

TiKV 采用的是常用的 MVCC 模型溯泣，也就是每個 key-value 實際存儲的時候，會在 key 上面帶一個 timestamp榕茧，我們就可以用 timestamp 來生成整個數(shù)據(jù)庫的 snapshot 了，所以 TiKV 是 snapshot isolation 的客给。既然是 snapshot isolation用押，那么就會遇到 write skew 問題，所以 TiKV 額外提供了 serializable snapshot isolation靶剑，用戶需要顯示的對要操作的數(shù)據(jù)進行 lock 操作蜻拨。

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

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

小結(jié)

在分布式系統(tǒng)里面院刁，一致性是非常重要的一個概念，理解了它粪狼，在自己設(shè)計分布式系統(tǒng)的時候退腥，就能充分的考慮到底系統(tǒng)應(yīng)該提供怎樣的一致性模型。譬如對于 TP 數(shù)據(jù)庫來說再榄，就需要有一個比較 strong 的一致性模型狡刘，而對于一些不重要的系統(tǒng)，譬如 cache 這些困鸥，就可以使用一些比較 weak 的模型嗅蔬。對 TiKV 來說剑按，我們在 Percolator 基礎(chǔ)上面，也一直在致力于分布式事務(wù)的優(yōu)化澜术，如果你對這方面感興趣艺蝴，歡迎聯(lián)系我 tl@pingcap.com。