藏在一切之下的問題：達成一致
到現在你已經知道分散式系統困難的地方在哪：沒有共用時鐘、沒有共用記憶體、訊息花費的時間無法預測還可能憑空消失，而機器會遭遇部分失效——有些死了、有些還在跑，而且沒人確定是哪些。幾乎每一個有趣的分散式任務，剝開來看，其實都是同一個看似簡單、卻穿著不同外衣的問題：一群機器有沒有辦法對「單一個值」達成一致，即使它們只能透過一個不可靠的網路彼此低語？那個問題就叫做共識。
想像一個董事會的成員散落在世界各地，只能靠寄信溝通——而那些信有時遲到、有時順序顛倒、有時整封弄丟。他們必須敲定「正好一個」決定：「會議在星期二」。每個人各自挑一天是不夠的；他們必須挑「同一天」，一旦決定就不再改變，並且即使沒有任兩人在同一瞬間說過話，最後也要彼此吻合。共識就是那套協定——一份把眾多分歧意見變成「一個眾人都遵守的決定」的食譜。
任何一套誠實的共識協定，我們都需要它具備三個性質。一致性：沒有任兩台正確的機器決定出不同的值。有效性：被決定的值必須是某台機器真的提議過的（你不能對沒人提過的垃圾達成一致）。終止性：每台正確的機器最終都會做出決定，而不是永遠等下去。要在一個充滿失效、又會丟訊息的網路上同時守住這三點，遠比聽起來困難——而且背後有一個著名又發人深省的原因。
為什麼達成一致是真的困難
麻煩在於：你永遠無法把一台「很慢」的機器和一台「死掉」的機器區分開來。當你寄出一封信、卻等不到回音，是收件人當機了，還是回信只是還躺在郵路上？在一個非同步網路上，你無法區分「當機」和「很慢」——這正是分散式運算的謬誤之一（延遲不為零、網路並不可靠）。一個叫做 FLP 的定理把這件事講得很精確：只要有一台機器「可能」當機，在一個完全非同步的系統裡，就沒有任何共識協定能保證它「總是」會終止。總有某種倒楣的訊息時序會把它卡住。
實用的共識協定——Paxos，以及更好教的 Raft——把工作做完的方式，是先解決一個你在第四篇導覽的協調世界裡已經見過的、較小的問題：領導者選舉。與其讓每個人和每個人爭吵（那是一片混亂），機器們先選出「單一個」領導者。領導者提議值；其他人，稱為追隨者，只負責投票接受或拒絕。只要嚴格多數的機器同意，那個值就被決定了。把每個決定都繞經一個領導者、再以多數決撐腰，就把那團糾纏的「人人對人人」問題變成可處理的東西。
為什麼非得要多數——超過一半——而不是隨便任兩台機器就好？因為同一群體裡的任兩個多數，必定至少有一台機器重疊。那個重疊就是祕密的黏著劑：它保證了一個「不知道前一個決定」的群體無法做出新決定，因為至少有一台機器同時在兩個群體裡、而它記得。多數決，就是一個分散式系統如何在當機與選舉之間維持一致、又完全不需要它根本沒有的共用記憶體的辦法。
CAP 定理：一個你無法迴避的抉擇
現在假設你的服務分散在大洋兩岸的機器上，而兩岸之間的海底電纜被切斷了。兩半各自仍能和自己這邊的使用者對話，但彼此之間無法對話。這就是網路分區——系統裂成了再也無法交換訊息的孤島。一個在西岸的客戶寫入一個新值；一個在東岸的客戶讀取。應該發生什麼事？CAP 定理說，在分區期間你面對的是一個無可迴避的抉擇，而把背後的原因看清楚很值得。
CAP 點名了三樣你或許都想要的東西：一致性（每次讀取都看到最近一次的寫入——所有機器顯示同一個值）、可用性（每個請求都拿得到回答，絕不出錯也絕不卡住），以及分區容忍性（即使網路裂開系統仍持續運作）。這個定理真正的內容，比那句流行口號「三選二」更鋒利。分區是網路的事實，不是一個你能關掉的選項——所以 P 其實沒得商量。誠實的說法是：當分區發生時，你必須在 C 與 A 之間二選一。你無法同時擁有兩者。
把斷纜的例子走一遍。要維持一致，每個被孤立的一半都必須拒絕任何它無法安全回答的請求——西岸如果無法確認東岸會看到這筆寫入，就不能接受它，於是回傳一個錯誤。那犧牲了可用性。要維持可用，每一半就用自己本地的副本照樣回答——但現在西岸有新值、東岸供應舊值，兩者不一致。那犧牲了一致性。沒有第三道門：在斷纜的情況下，你要嘛說「不行」（一致但不可用），要嘛冒著「過期」的風險（可用但不一致）。
靠複製做到容錯
為什麼要費這麼大的勁？因為一個分散式系統存在的全部意義，就是在個別機器不運作時仍能持續運作。單一台伺服器是一個單點故障：它一死，你的服務就跟著陪葬。解藥是複製——把同一份資料的副本保存在好幾台機器上，這樣任何一台壞掉都還撐得住。如果你存了三份資料副本，兩台機器都著火了，第三台仍能服務每一次讀取。這是用廉價、不可靠的零件搭起來的容錯，和 RAID 把磁碟做鏡像是同一種精神，只是攤開到整台整台的電腦上。
但複製立刻又把共識拖回來，因為「被允許各自漂移」的副本比沒用還糟——一個讀取者一旦落到錯的副本上，就拿到錯的答案。標準的解藥是狀態機複製：把每個副本都當成一台完全相同的機器，從相同的狀態出發，按完全相同的順序套用完全相同的一串更新。如果它們全都從相等出發、全都按相同順序處理相同的操作，它們就會永遠保持相等。唯一困難的部分，是隔著網路對「那個順序」達成一致——而那，正是共識，每筆更新跑一次。
排序與共識，悄悄地屬於同一個問題家族，這就是為什麼第四篇導覽的邏輯時鐘與「先發生於」關係在這裡很重要：它們讓每個副本都有一套一致的方式，去推理事件的順序，而不需要共用時鐘。把這些拼起來，一個容錯的服務通常長這樣：一小群副本、一個被選出的領導者、每筆更新都漏斗般地穿過共識好讓所有副本以相同順序套用它，並且要求多數才能提交——於是這個服務能挺過任何「少數」當機，而且永遠不會忘記一個已提交的決定。
把它拼起來：一筆已提交的寫入，逐步走過
讓我們追蹤一筆寫入，穿過一個由五台機器組成、以共識撐腰的複製服務。五是常見的選擇，因為多數是三，所以系統能容忍同時兩台失效、仍能推進。看看領導者選舉、多數決投票，與複製是如何全部喀地一聲扣在一起、成為單一個機制的。
- 一個客戶端把「set X = 7」送給領導者。（如果客戶端猜錯、聯絡到的是追隨者，它會被告知目前的領導者是誰、然後改向過去。）
- 領導者把這筆更新附加到自己的日誌上，標為「已提議、尚未提交」，接著把這個提議寄給全部四個追隨者。
- 每個收到的追隨者把同一筆條目附加到自己的日誌上、放在相同的位置，並回覆領導者「已確認」。
- 一旦領導者聽到多數的回覆——它自己加上另外兩個、總共三個——這筆寫入就被提交了。一個多數絕不會被未來的多數推翻，因為這兩個多數必定重疊在一台「記得這筆條目」的機器上。
- 領導者告訴追隨者「條目已提交」，他們把它套用到自己那份 X 的副本上，領導者再回答客戶端「完成」。即使領導者現在當機，從存活者中選出的新領導者，已經在多數的日誌裡擁有這筆條目，所以它絕不會遺失。
Client Leader (L) Followers (F1..F4) | | | |---- set X = 7 ------->| | | |-- propose(X=7) -------->| (append to log) | |<------- ack ------------| | | ... wait for a | | | MAJORITY (3 of 5) ... | | | [committed!] | | |-- commit(X=7) --------->| (apply X=7) |<------ done ----------| | 5 machines -> majority = 3 -> tolerates 2 failures
整個階段就在這一個動作裡。沒有共用時鐘或記憶體，所以機器純粹靠傳遞訊息來協調；訊息可能很慢或弄丟，所以我們從不信任單一個回覆、總是要求多數；機器會遭遇部分失效，所以我們保留副本、並在舊領導者沉默時選出新的；而當網路本身分區時，CAP 逼我們有意識地抉擇，這個服務要用可能過期的資料來回答，還是拒絕到它能確定為止。分散式系統不是魔法——它是小心翼翼的「達成一致」，一次一封誠實的訊息，一點一滴搭起來的。