不要騙我了，這能有多難嘛！

我的要求不高，只是一個變數而已

故事從一個變數講起。比如初學編程的時候，我們都是從這樣的代碼學起的。

a = 1print(a+1)

這能有多難？變數就是一個原子的容器，裡面「之前」放了什麼，「之後」取出來就是什麼。映射到內存上就是一個內存地址而已。

但是這其實是很難的事情。我們這些被慣壞了程序員是無法理解的。比如，你有這樣的SQL

UPDATE order SET order_status="arrived" WHERE order_id=10234

執行完了之後，訂單狀態應該就是arrived了的。

SELECT order_status FROM order WHERE order_id=10234

如果沒有其他的寫入操作。之後執行SELECT語句，取出來的訂單狀態就應該是arrived。當底層的資料庫不是這樣的行為的時候，我們會憤怒，我們會抓狂。比如我下一個介面取到的訂單的時候會「校驗」一下這個訂單的當前狀態是不是對的。讀不到之前寫入的訂單狀態，這個校驗就過不去。

另外一個對變數的理所當然的假設是，它應該支持我去做帶前提條件的更新。比如

if (amount >= 4) { amount = amount - 4 return SUCCESS} else { return FAILED}

這個例子，我是要給賬戶餘額扣掉4塊錢。如果能夠保證扣完了之後賬戶的餘額不為負數，也就是當前餘額不小於4塊，就扣掉。如果不能保證，就返回失敗。這是一個理所當然應該支持的所謂compare and swap操作嘛，也就是read modify write的操作嘛。

對應成 SQL，我們的期望其實非常低。也不要求什麼多行記錄的事務。要求僅僅是操作一行的時候，這個操作能是原子的。比如這樣的SQL

UPDATE account SET amount = amount - 4 WHERE amount >= 4

對資料庫有這樣的要求高么？一點都不高對不對。這個事情難不難？非常難！但是如果底層的數據不能提供這樣的基本保障，我們這些寫業務代碼的程序員會憤怒，會抓狂。

抽象一下問題

剝離掉具體的業務需求。我們來看本質。第一個需求是要求寫入和讀取要能按照牆上時間進行排序。所有在讀取之前發生的（happens before）寫入都要能夠在之後被讀取到。這個是對讀操作的線性一致性的保證。

第二個需求是要求之前的寫入在CAS操作的時候都可見，而且要求寫入的時候要保證這個時候變數的值仍然是讀取到的那個。這個對寫操作的線性一致性的保證。

總結來說，前面我們給資料庫提的需求就是，我們需要的是linearizable的需求。這個需求過分不過分。參見：Strong consistency models

這個圖的右邊，是講多個變數的問題的，左邊是單變數的問題。Linearizable的讀寫，是我們能給一個「變數」提的最高級別的一致性要求了。你說過分不過分。

我讀書少，你不要騙我

Wait a minute。做為一個變數這麼一點基本的操守都沒有么。比如我作為一個 Java 程序員都知道

volatile int a;a = 1; // thread 1System.out.println(a+1); // thread 2

什麼Linearizability，名詞一套套的。把我都說蒙圈了。你們這些基礎架構的高T們，是不是就會寫PPT啊。

這難道不是java面試題么。通過設置 volatile，可以保證在 thread 1 寫入了 a，在這個時間之後，從任意其他線程去讀 a 都可以讀到之前寫入的值。

而且這個volatile也不是什麼複雜的東西嘛。據說就是把volatile變數的寫入之後加了一條sfence的彙編指令。在讀取之前加了mfence的彙編指令（參見：https://mechanical-sympathy.blogspot.com/2011/07/memory-barriersfences.html）。有什麼難的嘛，兩條CPU指令而已。

至於 CAS，不就是 java.util.concurrent.atomics.AtomicInteger.compareAndSet 么。所有的條件寫入都可以化簡為調用這個函數啊。

據說底層調用的是 lock cmpxchg 這條彙編指令。有什麼難的嘛，一條CPU指令而已。

但是……CPU指令又是如何實現 sfence，mfence 和 lock cmpxchg 的呢？

Welcome to the rabbit hole

帶著這個疑問，我google了半天。找到了兩篇講得比較清楚的介紹：

• Memory Barriers: a Hardware View for Software Hackers（下載：http://www.rdrop.com/~paulmck/scalability/paper/whymb.2010.06.07c.pdf）
• Computer Science Handbook, 2nd Ed 第19章，Bus

Holy shit。我們做業務邏輯開發的程序員真是太naive了。a = 1，然後 print(a+1) 真的不是那麼容易實現的事情。

首先來看一段最簡單的業務邏輯代碼

doX() { a = 1 a = a + 1 b = 2 b = b + 1}

很簡單吧。這個就是沒有任何分支和循環的最簡單的串列邏輯。我們稱這樣的串列的業務邏輯為非concurrent的。

但是業務邏輯落到具體的機制上進行執行，這個執行的過程未必就是「串列」的。也可能是parallel的。也就是 "not concurrent" != "not parallel"。

為什麼？因為CPU的日子也不好過啊。你這要求它做1做2做3做4的，還要求人家特別快，確實很難。CPU找到的討巧的辦法是把 not concurrent 的業務邏輯，parallel 的執行。怎麼做？

a = 1a = a + 1

這一串，和下面的

b = 2b = b + 1

貌似沒有什麼聯繫嘛。一個CPU核內部有多個可以parallel運算的單元。那麼就獨立去算好了。這個就是所謂的CPU亂序執行。

另外再來看一段代碼

a = 0doX() { if (a == 0) { a = a + 1 }}doY() { if (a == 0) { a = a + 2; }}

這段代碼是concurrent的，因為doX和doY是兩個獨立的運算流程，或者叫兩段獨立的業務邏輯。但是 "concurrent" != "parallel"。（參見 https://blog.golang.org/concurrency-is-not-parallelism）concurrency是業務邏輯上的並行。但是具體到實際的執行過程，未必是並行的。比如這樣的一個執行順序

a = 0doX() { if (a == 0) { // 第一步 a = a + 1 // 第三步 }}doY() { if (a == 0) { // 第二步 a = a + 2; // 第四步 }}

按照上面的這樣一個執行順序，即便只有一個CPU核，也可以「同時」執行兩段業務邏輯。但是第一步執行完doX的第一行之後，為什麼能夠跳到doY這個函數里去呢。難道一個函數不是「獨佔」一個cpu核的么？

獨佔cpu核，用parallel去實現concurrent是一種執行方案，但不是唯一的執行方案。編程語言完全可以再doX的第一行執行完之後把狀態保存起來，然後切換到doY執行，然後再切換回來，直接跳到doX的第二行去繼續執行。也就是所謂的「協程」。

按照剛才的執行順序，雖然只有一個CPU核在用非parallel的方式去運算。但是語義上是同時concurrent地跑著兩段業務邏輯。這種concurrency就引起了concurrent object的問題。因為a的狀態同時被doX和doY進行了讀寫。按照給定的執行順序，計算出來的結果是3，既不是1也不是2。也就是所謂的代碼出了並發的bug。

concurrent object 問題不是多核 cpu「搞出來的問題」。根本上是有兩段獨立的業務邏輯共享了狀態引起的。concurrent object 問題本質上是業務邏輯是否完備的問題。即便是單核cpu串列去執行，只要有協程存在，就仍然會有出bug的可能。對於 concurrent object，安全寫入的辦法就是做 CAS。所有寫入帶上一個前提條件，而不是無條件的write。因為concurrency是由多段獨立的業務邏輯引起的，CAS是做為協調手段，本身也是業務邏輯。不用CAS，只有在寫入方只有一個的時候，才是安全的。

對於存粹的 parallelism，比如CPU亂序執行。Intel x86 的 CPU是非常負責任的。基本上你可以認為你的一段串列的業務邏輯，真的就是一行接著一行執行的。大部分情況下做為寫業務代碼的同學，完全不用在意CPU背後搞的這些小動作。但是 arm 之類的 CPU 就沒有那麼負責任，會因為追求parallel執行，破壞掉單個變數的 linearizability 和多個變數的 serializability。

Concurrent Object 的線性一致性讀

既然CPU可以聰明到用亂序執行，自作主張的引入parallelism。然後還可以保證亂序執行不會引起內存可見性方面的問題。既然已經這麼牛b了，為什麼不「順手」把多核執行concurrent的業務邏輯，這種parallelism引起的內存可見性問題也解決了？讓所有的變數都能夠線性一致性讀呢？

a = 0doX() { a = 1;}doY() { print(a);}

對於doX和doY這兩個concurrent的執行流程，只要保證doX「真的」把1寫入到了a的內存地址，doY的時候「真的」從a的內存地址去讀取了值。「線性一致的讀取」不就實現了么？

sfence 和 mfence 乾的事情就是這個。但是為什麼不把所有的內存讀寫都加上 sfence 和 mfence？

原因很簡單。因為多個CPU核去讀寫內存的時候，共享的匯流排是很慢的。如果所有的寫入都要立即回寫到內存里，所有的讀取都要真的從內存里走匯流排調上來，這個速度是很慢的。所以每個CPU核都引入了自己的本地緩存來加速內存的讀寫。

假設每個cpu都有自己的緩存了。那麼我們如何保證讀操作的線性一致性？就是一個變數被更新了之後，所有其他的cpu再去讀這個變數都要讀到新的值。最簡單的實現就是要求更新操作去刷新所有其他CPU的緩存。等所有的CPU緩存都刷新完了之後，才結束這次寫操作。開始執行下一條指令。

按照使用資料庫的經驗，這個實現問題很大啊：

• 可用性：所有的CPU都寫入成功。要是有一個CPU掛了，不是就寫不成功了么。
• 延遲：等所有的CPU更新完自己的緩存。這寫一個變數該多慢啊。sfence的代價也太高了吧。

好在是CPU，而不是資料庫。可用性不是問題。一個CPU掛了，整台機器就異常了是可以接受的。延遲是真正的大問題。如果sfence的延遲這麼高，可能把所有的並發節省下來的時間都浪費掉了。

要降低這個寫操作的延遲，需要知道延遲產生在哪裡：

• 本地cpu cache的爭搶：cache太忙了，導致來不及更新，需要等cache
• 其他cpu cache的爭搶：別的cpu的cache太忙了，不能立即更新，需要等待

就像一個餐館生意太好了，需要叫號是一樣的。

CPU的設計者是怎麼解決cache太忙了，不能及時更新的問題的呢？排隊吧

CPU0發起的一個寫入。需要排兩個隊，一個是在本地的store buffer里，一個是在其他cpu的invalidate queue里。排隊的好處是不需要等cache真的更新了。只要排上了，就可以認為已經寫入了。讀取的時候，cpu會去查這個隊列，以及cache本身，綜合決定值是什麼。也就是把成本部分分攤到了讀取的時候去做。

表面上 a =1，print(a+1) 這樣的簡單內存地址的寫入的讀取，其實在多核cpu層面是用消息傳遞，所有參與者遵守同樣的MESI協議（和你的http handler其實沒啥區別，就是一個響應消息的業務邏輯代碼），來保證內存的一致性。你可以理解為多核CPU之間架了一個RPC網路，給你提供了一個內存地址可以線性讀取的抽象。

Concurrent Object 的線性一致性寫

sfence和mfence聽起來也不是那麼糟糕。就是拿緩存做了點同步的工作而已嘛。lock cmpxchg指令又是如何工作的呢？CAS做為線性一致寫入的基石，這個是如何實現的？

根據 Computer Science Handbook, 2nd Ed 第19章，Bus。這個過程其實是這樣的。

最簡單的實現辦法是把lock cmpxchg做為一個原子來執行。因為system bus保證了只有一個cpu核可以同時拿到執行權。cpu核可以把整個system bus鎖上，然後執行lock cmpxchg，然後再解鎖。可以說就是用一個非常大粒度的悲觀鎖來實現的。但是這樣會造成system bus長時間無法服務於其他的任務。

既然鎖粒度太大，那麼就把鎖的粒度搞小一點。把CAS操作分解為 read & lock，以及 write & unlock 兩個步驟來執行。在system bus上實現address 級別的細粒度的悲觀鎖。

按順序來說，就需要這麼幾個消息往來

1. 對 system bus進行 address lock
2. 對每個其他cpu進行invalidate，等ack，得到最新的值
3. 比對是否等於預期的值，如果符合預期，則做更新
4. 做寫入操作，同時寫入到所有cpu的cache，等ack
5. 對system bus進行 address unlock

所以有意思的地方是linux操作系統提供的悲觀鎖，實際上底層是由樂觀鎖實現的（CAS保護的processor當前排在runqueue里的線程）。而CPU的樂觀鎖，最終還是由system bus的address級別的鎖實現的。

基於這樣的實現，多核CPU就提供了線性一致的寫操作的能力。

擴展到分散式的 Concurrent Object

通過前面的 going down rabbit hole的過程，我們了解了在單機多核非持久化的情況下，實現線性一致的讀取（sfence/mfence），核線性一致的寫入（CAS），是非常不容易的。

那麼把問題擴展到分散式場景下。如果有一個變數，可以多機並發的讀寫，要保證線性一致的讀寫就更困難了。最簡單的一個想法，直接把多核CPU的那一套拿過來不就行了么？有幾個問題：

• 可用性：要求全體都在線，導致總體的可用性是個體的可用性的乘積
• 延遲：延遲取決於最慢的那一次複製交互。
• 持久化：CPU的內存一致性模式不用考慮內存掛了，再恢復的問題。而分散式存儲的要求是不把雞蛋放在一個籃子里。
• 沒有System Bus：CAS指令最終是依賴匯流排實現的Address Lock的。分散式系統下沒有這樣一個共享的硬體來做這個事情。

前三點都好說。無非就是把CPU的內存一致性演算法里的要求所有的CPU都Ack，改成要求多數派應答就可以了。無論是延遲，還是可用性，還是持久化通過拷貝多份，都可以通過這個多數派來解決。而且CPU的內存一致性演算法隨著CPU核數的變多，也開始有了一些變化，比如：http://people.csail.mit.edu/yxy/pubs/tardis.pdf 。在核數越來越多的背景下，降低一致性引起的延遲也變成了有收益的事情。

Paxos和CPU一致性演算法在實現線性一致性讀的區別在於，CPU要求全體ack，而Paxos不要求。這個決定背後的隱藏約束是，CPU的環境下，高可用不是問題，而且讀取的低延遲非常重要。而Paxos的環境下，需要對硬體故障進行容錯，但是讀取的延遲是可以放鬆（如果要求讀到最新的版本，要讀多個節點）。兩者只是根據自己的硬體基礎，做了一些取捨而已。

真正要命的挑戰是第四點。沒有共享的System Bus來實現Address Lock，這個CAS操做如何實現呢？沒有CAS，壓根就沒有辦法對Concurrent Object實現安全的寫入（安全的好意是符合業務邏輯的意思）。回憶一下CPU的CAS的實現，它實際是拆分成兩步來實現的：

• 先讀出來當前是否是有值的，並且同時上鎖
• 如果沒有值，則寫入值，同時釋放鎖

而號稱唯一正確的分散式共識演算法Paxos，恰好也是兩步（這不是巧合）：

• Prepare & Promise：就是把值出來，同時上鎖
• Propose & Accept：寫入值

但是沒有System Bus硬體實現的Address Lock，軟體的共識演算法如何保證Prepare和Accept中間沒有人插入進行執行呢？

State is illusion, Log is reality

我發現最好的理解分散式共識演算法的視角是建立一個正確的世界觀。那就是，state is illusion，log is reality。

給你一個變數a。這個變數a只是一個抽象，所謂a有狀態只是一個幻覺。a背後的變更日誌才是事實。

這樣的一個日誌，有兩個變更的記錄。這個時候a的值就是2。

在2的基礎上，再-3。那麼a的值就變成了-1。

有了這樣的一個日誌，背後就相當於我們有了一個邏輯上的時間的概念。也就是log的每個entry的offset。

有了這樣的一個世界觀之後。那麼就擁有了一個絕對的時間的概念。我們知道，a這個變數的狀態就是從左往右，一個個apply新的變更得到的。offset越小，代表邏輯時間越小。offset越大代表邏輯時間越大。

回到我們的問題。CAS要實現的兩個目標：

• Read & Lock：讀到一個確定性，靜止的歷史。
• Write：在這個歷史的基礎上，寫入我的值。這個寫入要獲得足夠的節點的支持才算成功。

這個要求，落到日誌的模型上。就是去爭搶一個offset。比如

假設你要去寫offset5。這個時候是沒法寫入的。因為副本1和副本3在offset4這個位置上還是空洞。也就是你的歷史還是處在變化中的。在offset5這個位置的值，取決於這兩個洞填上什麼值。怎樣才能讓offset5獲得一個靜止的歷史，從而拿到所謂的讀鎖（當你的歷史都確定了，相當於上鎖了）：

• 等一段時間，等別的寫入者把offset4都給寫完
• 一直等下去也不是辦法，我把offset4填上一個「作廢」的標籤吧。

當offset5之前的offset的所有副本的空洞都填上了。那麼可以確保offset5可以放心的去讀取歷史，根據歷史做判斷，然後寫入offset5這個位置的改動。

其實把「所有副本的空洞」都填上是一個過強的要求了。一個更形象的說法是」把offset5之前的offset的寫入都給攪和黃」，讓這些offset都寫不成功就行。如何才能讓這些offset寫不成功？

• 每個副本的每個offset代表一個洞，這個位置只能寫一次
• 假設總共10個副本，寫入3個就算成功的話
• 那麼把一個offset攪和黃，永遠寫不成功。就是要把8個副本的對應offset的洞填上作廢。這樣就永遠不會有3個洞填上值了。3+8=11 大於10

所以一次安全的CAS寫入過程是：

• 假設總共N份副本
• 要寫入offset I，把I之前所有offset的位置 [0, I-1]，填上R份的作廢。確保過去的歷史呈靜止狀。
• 讀取過去的歷史日誌。判斷當前的offset應該寫什麼值進去。
• 把當前offset I的值，寫入W份副本，才算寫入成功，返回給調用方。
• 要求 R + W > N

這個過程就是 corfu 的連續offset模型。而paxos的區別在於，proposal number（相當於這裡的日誌offset）不一定是連續的。所以paxos實現了一個更有效率的標記」作廢「的過程。就是每個副本有一個當前最大offset的標記。小於這個標記的offset都做為」作廢「來處理。

希望把 Paxos 講清楚了。

總結

如果要求數據100%不丟。要實現線性一致性讀取（SQL提交了，接下來用SQL查詢就可以查到），要實現線性一致性寫入（當行SQL既讀又寫），是非常困難和苛刻的要求的。因為要永遠不lost update，資料庫必須用multi-paxos或者raft，才能實現單行數據的線性一致性（且不說多行數據變更的ACID問題）。

但是如果不要求100%不丟，允許lost update，這個問題就變得非常容易了。只要把寫入都發給一個master，讓master非同步複製日誌就好了。一旦master掛掉，複製過程中的日誌對應的寫入就丟失了。

絕大多數業務都不要求數據100%不丟，單行數據，或者說單個變數的線性一致性讀和寫都是可以做到的，也不是很難。