“一個可能出錯的事物與一個不可能出錯的事物之間的主要差別是，當一個不太可能出錯的事物出錯了，通常也就意味着不可修複。” -- Douglas Adams（1992）
我們将讨論分布式環境中錯綜複雜的權衡之道，這很可能會在你設計系統時不得不面對這些艱難的選擇。....
你可能會出于各種各樣的原因，希望将資料庫分布到多台機器上：
可擴充性
如果你的資料量、讀取負載、寫⼊負載超出單台機器的處理能⼒，可以将負載分散到多台計算機上。
容錯/⾼可⽤性
如果你的應⽤需要在單台機器（或多台機器，⽹絡或整個資料中⼼）出現故障的情況下仍然能繼續⼯
作，則可使⽤多台機器，以提供備援。⼀台故障時，另⼀台可以接管。
延遲
如果在世界各地都有⽤戶，你也許會考慮在全球範圍部署多個伺服器，從⽽每個⽤戶可以從地理上最近
的資料中⼼擷取服務，避免了等待⽹絡資料包穿越半個世界。
在具體實作上，⽆共享架構（shared-nothing architecture）因其較高的成本效益，以及強大的功能而被廣泛使用，無共享架構有時稱為⽔平擴充（horizontal scale） 或向外擴充（scale out））。
在這種架構中，運⾏資料庫軟體的每台機器/虛拟機都稱為節點（node）。每個節點隻使⽤各⾃的處理器，記憶體和磁盤。節點之間的任何協調，都是在軟體層⾯使⽤傳統⽹絡實作的。
雖然分布式⽆共享架構有許多優點，但它通常也會給應⽤帶來額外的複雜度，有時也會限制你可⽤資料模型的表達⼒。接下來我們将詳細讨論分布式系統帶來的各種問題，以及問題的解決方案；
适用場景：少資料量，單庫可承載的場景。
目的：
1.擴充性。提高吞吐量
2.降低延遲。通過将資料放在離使用者較近的地方，以便能夠更快的通路資料。
3.高可用。即使部分節點故障停機，也能保持服務正常運作。
上司者&追随者
I.同步複制 vs 異步複制
a.同步複制
優點
從庫保證有與主庫⼀緻的最新資料副本。如果主庫突然失效，我們可以确信這些資料仍然能在從庫上上找到。
缺點
如果同步從庫沒有響應（⽐如崩潰，或其它任何原因），主庫就⽆法處理寫⼊操作。
将所有從庫都設定為同步的是不切實際的：任何⼀個節點的中斷都會導緻整個系統停滞不前。
b.異步複制
即使所有的從庫都落後了，主庫也可以繼續處理
寫⼊。
會出現複制延遲問題，見下文。
通常情況下，基于上司者的複制都配置為完全異步。
c.半同步
隻保證一部分節點是保持與主庫一緻性的資料。
II.設定新從庫
步驟：
1.擷取主庫某時刻一緻性快照。
2.快照複制
3.連結主庫，拉取快照後的資料變更。要求主庫中日志位置精确，如日志序列号，二進制日志坐标。
4.從庫趕上主庫後，就可以正常處理主庫的産生資料變化了。
III.處理節點當機
從庫失效：追趕恢複
主庫失效：故障切換
IV.複制日志的實作
定義：每當上司者将新資料寫⼊本地存儲時，它
也會将資料變更發送給所有的追随者，稱之為複制⽇志（replication log）記錄或變更流
（change stream）。
實作1.基于語句的複制
優點：可讀性較強
缺點：執行依賴于語句的複制會有問題，如：自增主鍵、随機字元串、now()函數，存儲過程等。
實踐：mysql預設使用該模式，并在特定情況下切換至基于日志的複制模式。
實作2.傳輸預寫式日志WAL（Write Ahead Log）
優點：基于追加日志的方式，記錄資料的變更，可以解決以上複制問題。
缺點：1.wal偏底層，通常記錄的是磁盤某分區資料更改；2.資料與存儲耦合性較強；
實踐：PostgreSQL和oracle使用此複制方式。
實作3.基于邏輯日志(Binlog)的複制
優點：資料變更的二進制位元組流，傳輸速度快，且保證資料複制的正确型。
缺點：不可讀。
實踐：mysql的二進制日志使用該方式
實作4.基于觸發器的複制
使用應⽤程式代碼複制
複制延遲問題
最終一緻性：同時對主庫和從庫執⾏相同的查詢，可能得到不同的結果，因為并⾮所有的寫⼊都反映在從庫中。如果停⽌寫⼊資料庫并等待⼀段時間，從庫最終會趕上并與主庫保持⼀緻，這種效應成為最終一緻性。
1.寫後讀：使用者總是可以讀到自己送出的資料。
2.單調性：即使用者在讀取某個時間的資料後，不應再讀取到更早時間點的資料。
3.一緻字首讀：使用者應該将資料視為具有因果意義的狀态。例如：按照正确的順序檢視問題及其答複。
三種流行的複制算法
1.單主複制
用戶端将所有的寫操作發送到單個節點（上司者），該節點将資料更改事件流發送到所有的副本（追随者）。讀操作可以在任何節點執行，但可能會讀取到舊資料。
優點：容易了解，且沒有沖突問題。
2.多主複制
用戶端的将寫操作發送到幾個上司者節點之一，其中任何一個都可以接受寫入。然後由該節點将資料更改事件流發送給其他上司者節點及其跟随者節點。
優點：出現故障節點、網絡中斷和延遲峰值情況下，多主和無主複制更加穩健。但以僅提供弱一緻性為代價。
并發問題
3.無主複制
用戶端發送每個寫入到多個節點，并從多個節點并行讀取，以檢測和糾正具有陳舊資料的節點。
适用場景：資料量⾮常⼤的時候，在單台機器上
存儲和處理不再可⾏，則分區⼗分必要。
此時需要将資料進⾏分區（partitions），也稱為分⽚（sharding） 。
目的：分區的⽬标是在多台機器上均勻分布資料和查詢負載，避免出現熱點（負載不成⽐例的節點）。
分區與複制：
分區通常與複制結合使⽤，使得每個分區的副本存儲在多個節點上。 這意味着，即使每條記錄屬于⼀個分區，它仍然可以存儲在多個不同的節點上以獲得容錯能⼒。
兩種主要的分區⽅法：
鍵範圍分區
核心思想：為每個分區指定⼀塊連續的鍵範圍（從最⼩值到最⼤值），如紙百科全書的卷）。如果知道範圍之間的邊界，則可以輕松确定哪個分區包含某個值。
優點：鍵是有序的，并且分區擁有從某個最⼩值到某個最⼤值的所有鍵。可以進⾏有效的範圍查詢。
缺點：如果應⽤程式經常通路相鄰的主鍵，則存在熱點和偏斜的⻛險。
散列分區
核心思想：散列進⾏分區，通常先提前建立固定數量的分區，為每個節點配置設定多個分區，并在添加或删除節點時将整個分區從⼀個節點移動到另⼀個節點。也可以使⽤動态分區。
優點：可以将将偏斜的資料均勻分布
缺點：散列分區破壞了鍵的排序，使得範圍查詢效率低下
鍵範圍&散列組合分區
兩種⽅法搭配使⽤也是可⾏的，例如使⽤複合主鍵：使⽤鍵的⼀部分來辨別分區，⽽使⽤另⼀部分作為排序順序。
分區與二級索引：分區和⼆級索引之間的互相作⽤。二級索引也需要分區，有兩種分區⽅法：
方法1: 按⽂檔分區（本地索引）。特點：
1.⼆級索引存儲在與主鍵和值相同的分區中。
2.這意味着隻有⼀個分區需要在寫⼊時更新，
3.但是讀取⼆級索引需要在所有分區之間進⾏分散/收集。
方法2: 按關鍵詞Term分區（全局索引）。
特點：
⼆級索引存在不同的分區。輔助索引中的條⽬可以包括來⾃主鍵的所有分區的記錄。
2.當⽂檔寫⼊時，需要更新多個分區中的⼆級索引；
3.但是可以從單個分區中進⾏讀取。
分區再平衡
定義：随着時間的推移，資料庫會有各種變化。如查詢吞吐量增加、資料集大小增加、節點機器故障下線等，此時需要資料和請求從⼀個節點移動到另⼀個節點。 将負載從叢集中的⼀個節點向另⼀個節點移動的過程稱為再平衡（reblancing）。
平衡政策
反面教材：hash mod N
模\(N\)⽅法的問題是，如果節點數量N發⽣變化，⼤多數密鑰将需要從⼀個節點移動到另⼀個節點。使得重新平衡過于昂貴。我們需要⼀種隻移動必需資料的⽅法。
固定數量的分區
⼀種隻移動必需資料的簡單⽅法：建立⽐節點更多的分區，并為每個節點配置設定多個分區。隻有分區在節點之間的移動。分區的數量不會改變，鍵所指定的分區也不會改變。唯⼀改變的是分區所
在的節點。
如果分區⾮常⼤，再平衡和從節點故障恢複變得昂貴。如果分區太⼩，則會産⽣太多的開銷。
當分區⼤⼩“恰到好處”的時候才能獲得很好的性能，如果分區數量固定，但資料量變動很⼤，則難以達到最佳性能。
動态分區
每個分區配置設定給⼀個節點，每個節點可以處理多個分區，就像固定數量的分區⼀樣。當分區增⻓到超過配置的⼤⼩時，拆分⼤型分區将其中的⼀半轉移到另⼀個節點，以平衡負載；與之相反，如果⼤量資料被删除并且分區縮⼩到某個門檻值以下，則可以将其與相鄰分區合并。此過程與B樹頂層發⽣的過程類似（參閱“B樹”）。
動态分區的⼀個優點是分區數量适應總資料量。如果隻有少量的資料，少量的分區就⾜夠了，是以開銷很⼩;如果有⼤量的資料，每個分區的⼤⼩被限制在⼀個可配置的最⼤值【23】
動态分區不僅适⽤于資料的範圍分區，⽽且也适⽤于散列分區。從版本2.4開始，MongoDB同時⽀持範圍和哈希分區，并且都是進⾏動态分割分區。
按節點⽐例分區
Cassandra和Ketama使⽤的第三種⽅法是使分區數與節點數成正⽐——換句話說，每個節點具有固定數量的分區【23,27,28】。在這種情況下，每個分區的⼤⼩與資料集⼤⼩成⽐例地增⻓，⽽節點數量保持不變，但是當增加節點數時，分區将再次變⼩。由于較⼤的資料量通常需要較⼤數量的節點進⾏存儲，是以這種⽅法也使每個分區的⼤⼩較為穩定。
請求路由
分區負載平衡
并⾏查詢執⾏引
擎
事務是⼀個抽象層，允許應⽤程式假裝某些并發問題和某些類型的硬體和軟體故障不存在。各式各樣的錯誤被簡化為⼀種簡單情況：事務中⽌（transaction abort），⽽應⽤需要的僅僅是重試。
弱隔離級别
1.讀已送出Read Commit
兩個保證：
無髒讀
無髒寫
實作讀已送出
防止髒寫
使用行鎖實作：當事務想要修改特定的對象（行或文檔）時，它必須首先獲得該對象的鎖。然後必須持有該鎖直到事務送出或中止；
一次隻有一個事務可以持有任何給定對象的鎖；
如果另一事務想要寫入同一個對象，則必須等到第一個事務送出或中止後才能擷取該鎖并繼續。
防止髒讀
方法一：使用行鎖。但實踐效果并不好，損失了隻讀事務的響應時間，并且可能因為等待鎖導緻連鎖反應進而使整體響應遲緩。
方法二：對于寫入的每個對象，資料庫都會記住舊的已經送出的值，和由目前持有寫入鎖的事務設定的新值；
當事務正在進行時，任何其他讀取對象的事務都會拿到舊值；
隻有當新值送出以後，事務才會切換到讀取新值。
不足：
不可重複讀 nonrepeatable 或讀取偏差 read skew
丢失更新Lost update
2.快照隔離和可重複讀Read Repeatable
一個保證：
可重複讀
不可重複讀問題
描述：事務A在對一個對象寫入期間，另一個事務B分别在事務A送出前、後讀取到不同值的現象。
解決
快照隔離：每個事務都從資料庫的一緻快照（consistent snapshot）中讀取，即事務可以看到事務開始時在資料庫中送出的所有資料，即使這些資料随後被另一個事務更改，每個事務也隻能看到該特定時間點的舊資料。
快照隔離對長時間運作隻讀查詢非常有用，如備份和分析。
實作快照隔離
關鍵原則：讀不阻塞寫，寫不阻塞讀。
多版本并發控制MVCC，multi-version concurrency control：資料庫保留和維護同一個對象在不同時間點的多個送出版本。
PostSQL中MVCC的實作：
當一個事務開始時會被賦予一個唯一的永遠遞增的事務ID，每當事務向資料庫寫入任何内容時，它所寫入的資料都會被标記上寫入者的事務ID。
可見性規則：同時滿足以下2個條件，則可見一個對象：
a。讀事務開始時，建立該對象的事務已經送出。
b。對象未被标記删除或已被标記删除，請求删除的事務在讀事務開始時尚未送出。
3.防止丢失更新Lost update
并發寫入事務可能導緻的問題
解決方案
a。原子寫
許多資料庫提供了原⼦更新操作，從⽽消除了在應⽤程式代碼中執⾏讀取-修改-寫⼊序列的需要。如下在大多數資料庫是并發安全的：
UPDATE counters SET value = value + 1 WHERE key = 'foo';
如果你的代碼需要，那這通常是最好的解決⽅案。
a。實作
方案一：遊标穩定性技術，事務在讀取對象時擷取其上的排他鎖，在更新操作完成之前沒有其他事務可以讀取該對象。通常的實作方式。
方案二：簡單地強制所有的原子操作在單一線程上執行。
b。顯示鎖定
防⽌丢失更新的另⼀個選擇是讓應⽤程式顯式地鎖定将要更新的對象。然後應⽤程式可以執⾏讀取-修改-寫⼊序列，如果任何其他事務嘗試同時讀取同⼀個對象，則強制等待，直到第⼀個讀取-修改-寫⼊序列完成。
FOR UPDATE ⼦句告訴資料庫應該對該查詢傳回的所有⾏加鎖。
c。自動檢測丢失的更新
原⼦操作和鎖是通過強制讀取-修改-寫⼊序列按順序發⽣，來防⽌丢失更新的⽅法。
另⼀種⽅法是允許它們并⾏執⾏，如果事務管理器檢測到丢失更新，則中⽌事務并強制它們重試其讀取-修改-寫⼊序列。
優點：資料庫可以結合快照隔離⾼效地執⾏此檢查。
Oracle可串行化和SQL server快照隔離級别都會自動檢測丢失的更新。
MySQL/InnoDB的可重複讀并不會檢測丢失更新。
d。比較并設定（CAS, Compare And Set）
此操作的⽬的是為了避免丢失更新。
但是，如果資料庫允許 WHERE ⼦句從舊快照中讀取，則此語句可能⽆法防⽌丢失更新（MVCC）
在依賴資料庫的CAS操作前要檢查其是否安
全。
e。沖突解決和複制
多節點情況
防⽌丢失的更新需要考慮另⼀個次元：由于在多個節點上存在資料副本，并且在不同節點上的資料可能被并發地修改，基于鎖或CAS操作的技術不适⽤于這種情況，是以需要采取⼀些額外的步驟來防⽌丢失更新。
⼀種常⻅⽅法是允許并發寫⼊建立多個沖突版
本的值（也稱為兄弟），并使⽤應⽤代碼或特殊資料結構在事實發⽣之後解決和合并這些版本。
另⼀⽅⾯，最後寫⼊為準（LWW）也可解決沖突，但該⽅法很容易丢失更新。
f。寫入偏差和幻讀
I.不同僚務并發寫入相同對象情況
導緻的問題
髒寫，丢失更新
解決方式
通過【鎖】和【原子寫操作】這類手動安全措施。
II.不同僚務并發寫入不同對象情況
寫偏差，幻讀
寫偏差
如果兩個事務讀取相同的對象，然後更新其中⼀些對象（不同的事務可能更新不同的對象），則可能發⽣寫⼊偏差。
導緻寫偏差的幻讀
⼀個事務中的寫⼊改變另⼀個事務的搜尋查詢的結果，被稱為幻讀【3】
較優：使用觸發器，或者物化視圖
次優：使用FOR UPDATE顯示鎖定事務所依賴的所有行。
物化沖突
如果幻讀的問題是沒有對象可以加鎖，也許可以⼈為地在資料庫中引⼊⼀個鎖對象？
例如，在會議室預訂的場景中，可以想象建立⼀個關于時間槽和房間的表。此表中的每⼀⾏對應于特定時間段（例如15分鐘）的特定房間。可以提前插⼊房間和時間的所有可能組合⾏（如接下來的六個⽉）。
現在，要建立預訂的事務可以鎖定（ SELECT FOR UPDATE ）表中與所需房間和時間段對應的⾏。在獲得鎖定之後，它可以檢查重疊的預訂并像以前⼀樣插⼊新的預訂。
請注意，這個表并不是⽤來存儲預訂相關的資訊——它完全就是⼀組鎖，⽤于防⽌同時修改同⼀房間和時間範圍内的預訂。
這種⽅法被稱為物化沖突（materializing conflicts），因為它将幻讀變為資料庫中⼀組具體⾏上的鎖沖突【11】。
不幸的是，弄清楚如何物化沖突可能很難，也很容易出錯。在⼤多數情況下。可序列化 的隔離級别是更可取的方案。
4.可序列化（Serializable）
目标：解決幻讀
實作
方案一：真正的串行化
順序執⾏所有事務使并發控制簡單多了，但資料庫的事務吞吐量被限制為單機單核的速度。
隻讀事務可以使⽤快照隔離在其它地⽅執⾏，但對于寫⼊吞吐量較⾼的應⽤，單線程事務處理器可能成為⼀個嚴重的瓶頸。
最佳實踐
1.每個事務都必須小而快，隻要有一個緩慢的事務，就會拖慢所有事務處理。
II。僅限于活躍資料集可以放入記憶體的情況，因為通路磁盤會很慢。
III。寫入吞吐量必須低到能在單個CPU核上處理，否則事務需要化分支單個分區，且不需要跨分區協調。
IV。跨分區事務是可能的，但是他們的使用成都有很大的限制。
分區
為了擴充到多個CPU核⼼和多個節點，可以對資料進⾏分區。
找到⼀種對資料集進⾏分區的⽅法，以便每個事務隻需要在單個分區中讀寫資料，那麼每個
分區就可以擁有⾃⼰獨⽴運⾏的事務處理線程。在這種情況下可以為每個分區指派⼀個獨⽴的CPU核，事務吞吐量就可以與CPU核數保持線性擴充【47】。
方案二：兩階段鎖定（2PL）
讀阻塞寫，寫阻塞讀。表級别
悲觀鎖
性能如何
性能非常差
變形一：謂詞鎖
它類似于2PL描述的共享/排它鎖，但不屬于特定的對象（例如，表中的⼀⾏），它屬于所有符合某些搜尋條件的對象。
讀阻塞寫，寫阻塞讀。條件比對的資料行級别
性能較差
變形二：索引範圍鎖
又叫間隙鎖next-key locking，大多數2PL資料的實作。近似版的謂詞鎖
這種方法可能會鎖定更大範圍的對象，而不是維持可串性化所必須的範圍。
它可以有效防止幻讀和寫入偏差，開銷也較低，是一個很好的折中選擇。
讀阻塞寫，寫阻塞讀。條件中索引列的級别，如果無索引則是表級别
方案三：可序列化快照隔離（SSI，）
序列化的隔離級别和⾼性能是從根本上互相⽭盾的嗎？可序列化隔離提供了一種選擇，它提供了完整的可序列化隔離級别，但與快照隔離相⽐隻有隻有很⼩的性能損失。
樂觀鎖：即如果存在潛在的危險也不阻止事務，而是繼續執行事務，希望一起都好起來。當一個事務想要送出時，資料庫檢查是否有什麼不好的事情發生（即隔離是否被違反）；如果是，事務将被中止，并且必須重拾。隻有可序列化的事務才被允許送出。
樂觀鎖的優點和缺點：
如果存在很多争用/競争，則表現不佳，因為這會導緻很大一部分事務需要中止。如果系統已經接近最大吞吐量，來自重試事務的額外負載可能會使性能變差。
但是如果有足夠的備用容量，并且事務之間的争用不是太高，樂觀的并發控制技術往往比悲觀的性能要好。
顧名思義SSI基于快照隔離，也就是事務中所有讀取都是來自資料庫的一緻性快照。在快照隔離的基礎上，SSI增加了一種算法來檢測寫入之間的序列化沖突，并确定要中止哪些事務。
性能
中⽌率顯着影響SSI的整體表現。SSI要求同時讀寫的事務盡量短（隻讀⻓事務可能沒問題）。此時性能較好
子主題 4
時鐘錯誤
程序暫停
無上限的網絡延遲
故障與部分失效
單個計算機上的軟體，通常會以⼀種相當可預測的⽅式運⾏，它沒有根本性的不可靠原因。
在分布式系統中，情況有本質上的差別。在分布式系統中，盡管系統的其他部分⼯作正常，但系統的某些部分可能會以某種不可預知的⽅式被破
壞。這被稱為部分失效（partial failure）。
難點在于部分失效是不确定性的
（nonderterministic）：如果你試圖做任何涉及多個節點和⽹絡的事情，它有時可能會⼯作，有時會出現不可預知的失敗。
如果要使分布式系統⼯作，就必須接受部分故障的可能性，并在軟體中建⽴容錯機制。換句話說，我們需要從不可靠的元件建構⼀個可靠的系統。
故障處理必須是軟體設計的⼀部分，并且作為軟體的運維，您需要知道在發⽣故障的情況下，軟體可能會表現出怎樣的⾏為。
不可靠的網絡
真實的網絡環境很不穩定，⽹絡故障時有發生，如果⽹絡故障的錯誤處理沒有定義與測試，武斷地講，各種錯誤可能都會發⽣。
您需要知道您的軟體如何應對⽹絡問題，并確定系統能夠從中恢複。
有意識地觸發⽹絡問題并測試系統響應。
檢測故障
如果你想確定⼀個請求是成功的，你需要應⽤程式本身的積極響應【24】。
逾時與⽆窮的延遲
如果逾時是檢測故障的唯⼀可靠⽅法，那麼逾時應該等待多久？不幸的是沒有簡單的答案。
⽹絡擁塞和排隊
⻓時間的逾時意味着⻓時間等待，直到⼀個節點被宣告死亡。在這段時間内⽤戶可能不得不等待或者看到錯誤資訊。
短暫的逾時可以更快地檢測到故障，但是實際上它隻是經曆了暫時的減速⽽導緻錯誤地宣布節點失效的⻛險更⾼。例如，由于節點或⽹絡上的負載峰值。
更好的⼀種做法是，系統不是使⽤配置的常量逾時，⽽是連續測量響應時間及其變化（抖動），并根據觀察到的響應時間分布⾃動調整逾時。
同步網絡vs異步網絡
電話電路
使用固定的網絡帶寬，傳輸的資料量固定、可預測。可保證的最⼤往返時間。
低請求時浪費帶寬，超過可支援帶寬的高請求時網絡阻塞。
分組交換協定
根據網絡中資料類型及大小的不同，傳輸的資料量也是不可預測的，是動态變化的。
有利于應對突發流量的情況。
不可靠的時鐘
時鐘和時間很重要！因為很多業務場景都依賴于時鐘或時間
分布式系統中，時間是一個比較棘手的事情：
1.因為網絡的傳輸需要時間，故節點間通信是不及時的。
2.每台節點機器都有自己的時鐘，他們不是完全準确的。一組伺服器通常使用“網絡時間協定NTP”在一定程度上同步時鐘。
單調鐘和時鐘
現代計算機中至少有兩種不同的時鐘：即時鐘和單調鐘。
時鐘
也成為挂鐘時間wall-clock time，他根據某個月曆傳回目前的日期和時間。如：
Linux上的clock_gettime(CLOCK_REALTIME)和
Java中的System.currentTimemillis()傳回epoch（即一個特定的時間：1970年1月1日午夜UTC）以來的秒數或毫秒數，不包括閏秒。
時鐘通常與NTP同步，如果本地使用在NTP伺服器之前太遠，則他可能會被重置到先前的時間點，發生時鐘跳回。
因為時鐘跳回和忽略閏秒，使用不用用于測量經過的時間。可以作為一個時間日期的參考值。
單調鐘
單調鐘永續測量持續時間，即間隔時間，這個名字來源于單調鐘保證前進的，而不會像時鐘一樣跳回。如：
Linux上clock_gettime(CLOCK_MONOTONIC) ，和Java中的 System.nanoTime() 都是單調時鐘。
在具有多個CPU插槽的伺服器上，每個CPU可能有⼀個單獨的計時器，但不⼀定與其他CPU同步。明智的做法是不要太把這種單調性保證當回事
單調鐘的絕對值是毫無意義的，因為他可能是任何值。
單調鐘的分辨率相當好：大多數系統中，他們能在幾微秒或更短時間内測量時間間隔。
單調鐘不需要同步。同一機器的不同CPU間，分布式系統的不同節點間。。等
時鐘的不準确性：單調鐘不需要同步，但是時鐘需要根據NTP伺服器或其他外部時間源來設定才能有⽤。但計算機中的⽯英鐘不夠精确：它會漂移（drifts）（運⾏速度快于或慢于預期）。時鐘漂移取決于機器的溫度。
使⽤GPS接收機，精确時間協定（PTP）【52】以及仔細的部署和監測可以實作這種精确度。
暫停程序？
GC暫停
虛拟機挂起
長時間的I/O操作
。。。
代價：如果某個軟體依賴于精确同步的時鐘，那麼結果更可能是悄⽆聲息且⾏蹤渺茫資料的資料丢失，⽽不是⼀次驚天動地的崩潰【53,54】。
知識、真相與謊言
真理由多數所定義
a。分布式系統不能完全依賴于單個節點，因為節點回會是失效，可能會使系統卡死，無法恢複。相反，許多分布式算法都依賴于【法定人數】，即在多個節點之間投票決定減少對某個節點的依賴。
也包括宣告節點死亡的決定，即使一個節點仍然感覺到自己活着，他也必須認為是死的（錯誤的宣告死亡）。個體節點必須遵守法定決定并下台。
b。通常情況下，⼀些東⻄在⼀個系統中隻能有⼀個。如單主複制中的上司者節點、鎖等。
如果⼀個節點繼續表現為“天選者”，即使⼤多數節點已經聲明它已經死了，則在考慮不周的系統中可能會導緻問題。
防護令牌：當使⽤鎖或租約來保護對某些資源的通路時，需要確定⼀個被誤認為⾃⼰是“天選者”的節點不能中斷系統的其它部分。實作這⼀⽬标的⼀個相當簡單的技術就是防護令牌。（fencing）屏蔽令牌保證它是單調遞增，資源僅接受最新的寫入。
- c。請注意，這種機制要求資源本身在檢查令牌⽅⾯發揮積極作⽤，通過拒絕使⽤舊的令牌，⽽不是已經被處理的令牌來進⾏寫操作——僅僅依靠用戶端檢查⾃⼰的鎖狀态是不夠的。
所有的節點都是由你的組織控制的（是以他們可以信任），輻射⽔平⾜夠低，記憶體損壞不是⼀個⼤問題。
制作拜占庭容錯系統的協定相當複雜【84】，部署拜占庭容錯解決⽅案的成本使其變得不切實際。
【算法】可能承擔的事情。以某種方式将我們期望在系統中發生的錯誤形式化。
一緻性保證
最終一緻性：如果你在同⼀時刻問兩個不同副本相同的問題，可能會得到兩個不同的答案。但如果停止向資料庫寫入資料并等待一段不确定時間，那麼最終讀取請求會得到相同的答案。
分布式⼀緻性模型和我們之前讨論的事務隔離級别的層次結構有⼀些相似之處。但它們⼤多是⽆關的問題：事務隔離主要是為了，避免由于【同時執⾏事務⽽導緻的競争狀态】，⽽分布式⼀緻性主要關于，⾯對延遲和故障時，如何【協調副本間的狀态】。
一緻性模型
線性一緻性
最強的一緻性模型之一。
也稱為原⼦⼀緻性（atomic consistency） 【7】，強⼀緻性（strong consistency），⽴即⼀緻性（immediate consistency）或外部⼀緻性（external consistency ）【8】）。
它是⼀個新鮮度的保證（recency guarantee）。
線性⼀緻性背後的基本思想很簡單：使系統看起來好像隻有⼀個資料副本。如果資料庫可以提供隻有⼀個副本的假象（即，隻有⼀個資料副本）。那麼每個用戶端都會有相同的資料視圖，且不必擔⼼【複制】滞後了。
線性⼀緻性的要求是，操作标記的連線總是按時間（從左到右）向前移動，⽽不是向後移動。
要求新鮮性保證：⼀旦新的值被寫⼊或讀取，所有後續的讀都會看到寫⼊的值，直到它被再次覆寫。
應用場景
唯⼀性限制
鎖定和上司選舉
跨信道的時序依賴
實作：
方案一：真的隻⽤⼀個資料副本。
優點：簡單
缺點：節點失效時服務不可用、甚至有資料丢失風險。
方案二：單主同步複制。
它們可能（protential）是線性⼀緻性的 4 。
優點：可靠，單節點失效時，保持服務可用（隻讀）。
缺點：性能低下。
方案三：共識算法。
共識協定包含防⽌【腦裂】和【陳舊副本】的措施。可以安全地實作線性⼀緻性存儲。如zookeeper
線性⼀緻性的代價
面臨的問題：
如果應⽤需要線性⼀緻性：當某些副本因為⽹絡問題與其他副本斷開連接配接，那麼這些副本掉線時不能處理請求。請求必須等到⽹絡問題解決，或直接傳回錯誤。⽆論哪種⽅式，服務都不可⽤（unavailable）。
如果應⽤不需要線性⼀緻性：那麼某個副本即使與其他副本斷開連接配接，也可以獨⽴處理請求（例如多主複制）。在這種情況下，應⽤可以在⽹絡問題前保持可⽤，但其⾏為不是線性⼀緻的。
CAP定理：不需要線性⼀緻性的應⽤對⽹絡問題有更強的容錯能⼒。
CAP有時以這種⾯⽬出現：⼀緻性，可⽤性和分區容忍：三者隻能擇其⼆。這種說法很有誤導性【32】，因為⽹絡分區并不是⼀個選項：不管你喜不喜歡它都會發⽣【38】。
在⽹絡正常⼯作的時候，系統可以提供⼀緻性（線性⼀緻性）和整體可⽤性。發⽣⽹絡故障時，你必須在【線性⼀緻性】和【整體可⽤性】之間做出選擇。
⼀個更好的表達CAP的⽅法可以是⼀緻
的，或者在分區時可⽤【39】。
為了線性一緻性犧牲性能和可用性 vs 或者為了提高性能、可用性而使用弱一緻性。
順序保證
全序
偏序
順序和因果順序
因果順序不是全序的
關系：線性⼀緻性隐含着（implies）因果關系：任何線性⼀緻的系統都能正確定持因果性【7】。
線性⼀緻性簡單、易懂，但可能會損害系統的性能和可⽤性，尤其是在系統具有嚴重的⽹絡延遲的情況下。
在許多情況下，看上去需要線性⼀緻性的系統，實際上需要的隻是因果⼀緻性，而因果⼀緻性可以更⾼效地實作。
序列号順序
我們可以使⽤序列号（sequence nunber）或時間戳（timestamp）來排序事件。時間戳不⼀定來⾃時鐘，它可以來⾃⼀個【邏輯時鐘】（logical clock），這是【⼀個⽤來⽣成辨別操作的數字序列的算法】，典型實作是使⽤⼀個每次操作⾃增的計數器。
這樣的序列号或時間戳是【緊湊的】（隻有⼏個位元組⼤⼩），它提供了⼀個【全序關系】：也就是說每操作都有⼀個唯⼀的序列号，⽽且總是可以⽐較兩個序列号，确定哪⼀個更⼤（即哪些操作後發⽣）。
非因果序列号生成器
适用于主庫不存在情況，可能因為使⽤了多主資料庫或⽆主資料庫，或者因為使⽤了分區的資料庫。
實作方案：
a。每個節點都可以⽣成⾃⼰獨⽴的⼀組序列号。例如有兩個節點，⼀個節點隻能⽣成奇數，⽽另⼀個節點隻能⽣成偶數。
b。将具有⾜夠⾼分辨率的時鐘時間戳附加到每個操作上。
c。可以預先配置設定序列号區塊。例如，節點 A 可能要求從序列号1到1,000區塊的所有權，⽽節點 B 可能要求序列号1,001到2,000區塊的所有權。
問題：⽣成的序列号與因果不⼀緻。
但⽐單⼀主庫的⾃增計數器性能表現要好，并且更具可擴充性。
蘭伯特時間戳
定義：蘭伯特時間戳就是兩者的簡單組合：（計數器，節點ID）。它提供了⼀個【全序】：如果你有兩個時間戳，則計數器值⼤者是更⼤的時間戳。如果計數器值相同，則節點ID越⼤的，時間戳越⼤。
特點：Lamport時間戳【解決了非因果序列号生成器的問題】，它提供了與因果關系⼀緻的總排序。
關鍵思想：每個節點和每個用戶端跟蹤迄今為⽌所⻅到的最⼤計數器值，并在每個請求中包含這個最⼤計數器值。當⼀個節點收到最⼤計數器值⼤于⾃身計數器值的請求或響應時，它⽴即将⾃⼰的計數器設定為這個最⼤值。
缺點：适用于【事後确定勝利者】場景，需要實時确定的場景會有問題。
全序⼴播（total order broadcast）
但是在分布式系統中，讓所有節點對同⼀個全局操作順序達成⼀緻可能相當棘⼿。在上⼀節中，我們讨論了按時間戳或序列号進⾏排序，但發現它還不如單主複制給⼒（如果你使⽤時間戳排序來實作唯⼀性限制，⽽且不能容忍任何錯誤）。
定義：如前所述，單主複制通過選擇⼀個節點作為主庫來确定操作的全序，并在主庫的單個CPU核上對所有操作進⾏排序。
接下來的挑戰是，如果吞吐量超出單個主庫的處理能⼒，這種情況下【如何擴充系統】；以及，如果主庫失效，【如何處理故障切換】。這個問題被稱為全序⼴播。
屬性：全序⼴播通常被描述為在【節點間交換消息的協定】。它要滿⾜兩個安全屬性，即使節點或⽹絡出現故障：
1.可靠傳遞（reliable delivery）
沒有消息丢失，即如果消息被傳遞到⼀個節點，它将被傳遞到所有節點。
2.全序傳遞（totally ordered delivery）*
消息以相同的順序傳遞給每個節點。
應用：
1.資料庫狀态機複制（state machine replication）：如果每個消息都代表⼀次資料庫的寫⼊，且每個副本都按相同的順序處理相同的寫⼊，那麼副本間将互相保持⼀緻。
2.實作可序列化的事務。
3.實作提供【防護令牌】的鎖服務：序列号可以當成防護令牌⽤，因為它是單調遞增的。在ZooKeeper中，這個序列号被稱為 zxid。
全序廣播 vs 線性一緻性存儲
全序廣播是異步的，消息保證以固定的順序可靠地傳送，但是【不能保證消息何時被送達】。
線性一緻性是【新鮮度】的保證，即讀取一定能看見最新的寫入值。
使⽤全序⼴播實作線性⼀緻的存儲：
可以通過将全序⼴播當成僅追加⽇志緻的CAS操作來實作，選擇沖突寫⼊中的第⼀個作為勝利者，并中⽌後來者，以此确定所有節點對某個寫⼊是送出還是中⽌達成⼀緻。
使⽤線性⼀緻性存儲實作全序⼴播：
最簡單的⽅法是假設你有⼀個線性⼀緻的寄存器來存儲⼀個整數，并且有⼀個原⼦⾃增并傳回操作【28】。
該算法很簡單：每個要通過全序⼴播發送的消息⾸先對線性⼀緻寄存器執⾏⾃增并傳回操作。然後将從寄存器獲得的值作為序列号附加到消息中。然後你可以将消息發送到所有節點（重新發送任何丢失的消息），⽽收件⼈将按序列号連續發送消息。
分布式事務與共識
共識是分布式計算中最重要也是最基本的問題之⼀。
現在我們已經讨論了複制（第5章），事務（第7章），系統模型（第8章），線性⼀緻以及全序（本章），我們終于準備好解決共識問題了。
場景
上司選舉
原子送出：在⽀持跨多節點或跨多分區事務的資料庫中，我們必須讓所有節點對事務的結果達
成⼀緻：要麼全部中⽌/復原（如果出現任何錯誤），要麼它們全部送出（如果沒有出錯）。這個共識的例⼦被稱為原⼦送出（atomic commit）問題
原子送出與二階段送出2PC
單節點原子送出
對于在單個資料庫節點執⾏的事務，原⼦性通常由存儲引擎實作。當用戶端請求資料庫節點送出事務時，資料庫将使事務的寫⼊持久化（通常在預寫式⽇志中：參閱“使B樹可靠”），然後将【送出記錄】追加到磁盤中的⽇志⾥。如果資料庫在這個過程中間崩潰，當節點重新開機時，事務會從⽇志中恢複：如果送出記錄在崩潰之前成功地寫⼊磁盤，則認為事務被送出；否則來⾃該事務的任何寫⼊都被復原。
在單個節點上，事務的送出主要取決于資料持久化落盤的順序：⾸先是資料，然後是【送出記錄】。事務送出或終⽌的關鍵決定時刻是磁盤完成寫⼊【送出記錄】的時刻：在此之前，仍有可能中⽌（由于崩潰），但在此之後，事務已經送出，即使資料庫崩潰。是以，是單⼀的裝置（連接配接到單個磁盤驅動的控制器，且挂載在單台機器上）使得送出具有原⼦性。
分布式原子送出
引言：如果⼀個事務中涉及多個節點，僅向所有節點發送送出請求并獨⽴送出每個節點的事務是不夠的。這樣很容易發⽣【違反原⼦性】的情況：送出在某些節點上成功，⽽在其他節點上失敗。
兩階段送出(two-phase commit) 是⼀種⽤于實作跨多個節點的原⼦事務送出的算法，即確定所有節點送出或所有節點中⽌。 它是分布式資料庫中的經典算法。
PS：事務送出必須是不可撤銷的 —— 事務送出之後，你不能改變主意，并追溯性地中⽌事務。這個規則的原因是，⼀旦資料被送出，其結果就對其他事務可⻅，是以其他用戶端可能會開始依賴這些資料。這個原則構成了【讀已送出隔離等級】的基礎，在“讀已送出”⼀節中讨論了這個問題。如果⼀個事務在送出後被允許中⽌，所有那些讀取了已送出卻⼜被追溯聲明不存在資料的事務也必須復原。
兩階段送出
兩階段送出（2PC, twophase commit）算法是解決原⼦送出問題最常⻅的辦法。2PC是⼀種共識算法。
名詞
協調者coordinator/事務管理器transaction manager
a。協調者通常不會出現在單節點事務中。
b。協調者通常在請求事務的相同應⽤程序中以庫的形式實作（例如，嵌⼊在Java EE容器中），但也可以是單ᇿ的程序或服務。
參與者（participate）
正常情況下，2PC事務以應⽤在多個資料庫節點上讀寫資料開始。我們稱這些資料庫節點為參與者。
基本流程
階段 1 : 當應⽤準備送出時，協調者發送⼀個【準備（prepare）請求】到每個節點，詢問它們是否能夠送出，并跟蹤參與者的響。
階段 2 :
a。如果所有參與者都回答“是”，表示它們已經準備好送出，那麼協調者發出【送出（commit）請求】，然後送出真正發⽣。
b。如果任意⼀個參與者回複了“否”，則協調者在階段2 中向所有節點發送【中⽌（abort）請求】。
類比：⻄⽅的傳統婚姻儀式
司儀-> 協調者, 新郎新娘 -> 參與者
系統承諾：
承諾1.當參與者投票“是”時，它承諾它稍後肯定能夠送出（盡管協調者可能仍然選擇放棄）。
參與者收到準備請求時，需要確定在任意情況下都的确可以送出事務。這包括将所有事務資料寫⼊磁盤（出現故障，電源故障，或硬碟空間不⾜都不能是稍後拒絕送出的理由）以及檢查是否存在任何沖突或違反限制。通過向協調者回答“是”，節點承諾，隻要請求，這個事務⼀定可以不出差錯地送出。換句話說，參與者放棄了中⽌事務的權利，但沒有實際送出。
承諾2.⼀旦協調者做出決定，這⼀決定是不可撤銷的。
當協調者收到所有準備請求的答複時，會就送出或中⽌事務作出明确的決定（隻有在所有參與者投贊成票的情況下才會送出）。協調者必須把這個決定寫到磁盤上的事務⽇志中，如果它随後就崩潰，恢複後也能知道⾃⼰所做的決定。這被稱為送出點（commit point）。
⼀旦協調者的決定落盤，送出或放棄請求會發送給所有參與者。如果這個請求失敗或逾時，協調者必須永遠保持重試，直到成功為⽌。沒有回頭路：如果已經做出決定，不管需要多少次重試它都必須被執⾏。如果參與者在此期間崩潰，事務将在其恢複後送出——由于參與者投了贊成，是以恢複後它不能拒絕送出。
兩階段送出協定包含的2個關鍵的“不歸路”點，保證了2PC的原⼦性。
協調者失效
存疑：⼀旦參與者收到了準備請求并投了“是”，就不能再單⽅⾯放棄 —— 必須等待協調者回答事務是否已經送出或中⽌。如果此時協調者崩潰或⽹絡出現故障，參與者什麼也做不了隻能等待。參與者的這種事務狀态稱為【存疑（in doubt）】的 或不确定（uncertain）的。
完成2PC的唯⼀⽅法是等待協調者恢複。這就是為什麼協調者必須在向參與者發送送出或中⽌請求之前，将其送出或中⽌決定寫⼊磁盤上的事務⽇志：協調者恢複後，通過讀取其事務⽇志來确定所有存疑事務的狀态。
三階段送出
兩階段送出被稱為阻塞（blocking）原⼦送出協定，因為存在2PC可能卡住并等待協調者恢複的情況。
三階段送出（3PC）的算法：3PC假定⽹絡延遲有界，節點響應時間有限；在⼤多數具有⽆限⽹絡延遲和程序暫停的實際系統中它并不能保證原⼦性。
在具有⽆限延遲的⽹絡中，逾時并不是⼀種可靠的故障檢測機制，因為即使沒有節點崩潰，請求也可能由于⽹絡問題⽽逾時。出于這個原因，2PC仍然被使⽤，盡管⼤家都清楚可能存在協調者故障的問題。
實踐中的分布式事務
缺點：分布式事務的名聲毀譽參半。一方面它難以實作，另一方面性能損失嚴重，據報告稱Mysql中的分布式事務比單節點事務慢10倍以上。
成本來源：兩階段送出所固有的性能成本，⼤部分是由于崩潰恢複所需的額外強制刷盤（ fsync ）【88】以及額外的⽹絡往返。
XA事務
XA（擴充架構（eXtended Architecture）的縮寫）是跨異構技術實作兩階段送出的标準。
XA不是⼀個⽹絡協定——它隻是⼀個⽤來與事務協調者連接配接的C API。
XA假定你的應⽤使⽤⽹絡驅動或用戶端庫來與參與者進⾏通信（資料庫或消息服務）。如果驅動⽀持XA，則意味着它會調⽤XA API 以查明操作是否為分布式事務的⼀部分 —— 如果是，則将必要的資訊發往資料庫伺服器。驅動還會向協調者暴露回調接⼝，協調者可以通過回調來要求參與者準備，送出或中⽌。
事務協調者需要實作XA API。
存疑持有鎖
為什麼我們這麼關⼼存疑事務？系統的其他部分就不能繼續正常⼯作，⽆視那些終将被清理的存疑事務嗎？
問題在于鎖（locking）。如果要使⽤可序列化的隔離等級，則使⽤兩階段鎖定的資料庫會為事務所讀取的⾏加上共享鎖（參⻅“兩階段鎖定（2PL）”）。當這些鎖被持有時，其他事務不能修改這些⾏。直到存疑事務被解決。
從協調者故障中恢複
理論上，如果協調者崩潰并重新啟動，它應該⼲淨地從⽇志中恢複其狀态，并解決任何存疑事務。然⽽在實踐中，【孤⽴（orphaned）的存疑】事務确實會出現，即⽆論出于何種理由，協調者⽆法确定事務的結果（例如事務⽇志已經由于軟體錯誤丢失或損壞）。
這些事務⽆法⾃動解決，是以它們永遠待在資料庫中，持有鎖并阻塞其他事務。即使重新開機資料庫伺服器也⽆法解決這個問題。
唯⼀的出路是讓管理者⼿動決定送出還是復原事務。
啟發式決策（heuristic decistions）：
許多XA的實作都有⼀個叫做啟發式決策的緊急逃⽣艙⼝：允許參與者單⽅⾯決定放棄或送出⼀個存疑事務，⽽⽆需協調者做出最終決定。要清楚的是，這⾥啟發式是【可能破壞原⼦性】（probably breaking atomicity）的委婉說法，因為它【違背了兩階段送出的系統承諾】。
是以，啟發式決策隻是為了逃出災難性的情況⽽準備的，⽽不是為了⽇常使⽤的。
許多伺服器端應⽤都是使⽤⽆狀态模式開發的（受HTTP的⻘睐），所有持久狀态都存儲在資料庫中，是以具有應⽤伺服器可随意按需添加删除的優點。
但是，當協調者成為應⽤伺服器的⼀部分時，它會改變部署的性質。突然間，協調者的⽇志成為持久系統狀态的關鍵部分—— 與資料庫本身⼀樣重要，因為協調者⽇志是為了在崩潰後恢複存疑事務所必需的。這樣的應⽤伺服器不再是⽆狀态的了。
- 限制3. 由于XA需要相容各種資料系統，是以它必須是所有系統的最⼩公分⺟。例如，它不能檢測不同系統間的死鎖，因為這将需要⼀個标準協定來讓系統交換每個事務正在等待的鎖的資訊。以及無法與SSI 協同⼯作，因為這需要⼀個跨系統定沖突的協定。
- 限制4. 2PC成功送出⼀個事務需要所有參與者的響應。是以，如果系統的任何部分損壞，事務也會失敗。是以，分布式事務⼜有【擴⼤失效】（amplifying failures）的趨勢，這⼜與我
們建構容錯系統的⽬标背道⽽馳。
ii。合法性屬性束腰式為了排除一些無意義的方案。
iii。可終止性引入了【容錯】思想：⼀個共識算法不能簡單地永遠閑坐着等死 ，它必須取得進展。即使部分節點出現故障，其他節點也必須達成⼀項決定。
小結
在本章中，我們從⼏個不同的⻆度審視了關于⼀緻性與共識的話題。我們深⼊研究了：
線性一緻性：最強的一緻性模型，其⽬标是使多副本資料看起來好像隻有⼀個副本⼀樣，并使其上所有操作都原⼦性地⽣效。線性⼀緻性簡單易懂，但性能低下，尤其是在網絡延遲很大的環境中。
因果一緻性：因果⼀緻性為我們提供了⼀個較弱的⼀緻性模型：某些事件可以是并發的，是以版本曆史就像是⼀條不斷分叉與合并的時間線。因果⼀緻性沒有線性⼀緻性的協調開銷，⽽且對⽹絡問題的敏感性要低得多。
即使做到了因果順序，但有些事情也需要通過達成共識才能做出決定。達成共識意味着所有節點⼀緻同意所做決定，且這⼀決定不可撤銷。
通過深⼊挖掘，我們發現很⼴泛的⼀系列問題實際上都可以歸結為共識問題，并且彼此等價。
從這個意義上來講，如果你有其中之⼀的解決⽅案，就可以輕易将它轉換為其他問題的解決⽅案。這些等價問題包括：
線性⼀緻性的CAS寄存器
原⼦事務送出
全序⼴播
鎖和租約
成員/協調服務
單上司者資料庫可以提供線性⼀緻性，唯一性限制，完全有序的複制日志等，但也需要共識算法
針對上司者節點失效或者網絡中斷導緻上司者不可達的異常問題，應對方案有三種：
i。等待上司者節點恢複，接受系統将在這段時間阻塞的事實。但不能達成共識，因為不滿足可終止性。
ii。人工故障切換，故障切換的速度受人類行動速度的限制。
iii。使用共識算法自動選擇一個新的上司者。
如果你發現⾃⼰想要解決的問題可以歸結為共識，并且希望它能容錯，使⽤⼀個類似ZooKeeper的東⻄是明智之舉。像ZooKeeper這樣的⼯具為應⽤提供了“外包”的共識、故障檢測和成員服務。