動機
分散式系統最重要的就是在不同的錯誤情境下達成共識 之後追求performance
串起這一切的就是時間與與之對應的排序
下面就來簡單的整理一下
錯誤
傳訊時可能遺失、out-of-order、重複 接收方可能當機導致不能回 (但recover會知道自己之前做了什麼)
在上面的情況下，分成兩種錯誤
- 拜占庭
- 在同一個情況(狀態)，出來的output可能不同 (可能是sender在搞，也有可能是在中間被改，換言之 資料損壞)
- 拜占庭中的叛徒
- leader可以對不同人送不同的msg
- 不能直接用leader的msg，要參考其他人的
- 拜占庭中的叛徒
- 在同一個情況(狀態)，出來的output可能不同 (可能是sender在搞，也有可能是在中間被改，換言之 資料損壞)
- 非拜占庭
- 在同一個情況(狀態)，出來的output都一樣
- 就算當機，也還是忠誠
- 在同一個情況(狀態)，出來的output都一樣
共識
共識在不同的情況下有不同的目標
- 拜占庭 (拜占庭將軍問題)
- 忠誠的人最後都要做相同的指令
- 如果leader忠誠，所有忠誠的人最後都要接受leader的命令
- 非拜占庭
- 過半數都同意
- 所有人都同意
解法
拜占庭的output可能不同所以分成
- oral messages: 可以被偽造
- signed messages: 不能被偽造簽名&無法改內容(會被抓到)，同時能被任何人驗證
同時所有msg都會
- 寄往正確的地方
- 知道sernder是誰
- 有辦法知道msg沒有寄成
拜占庭 + oral messages
前提: 至少$2m+1$個人忠誠 (m是叛徒數量)
- leader把msg丟給所有人
- 把收到的msg丟給自己與leader以外的人 (timeout當成retreat)
- 根據收集到的msg的多數($2m+1$個)做事
blockchain
在blockchain中，如果有人想做假
- 要巨量的工作量
- 同時要成為最長鏈 (在fork的時候還會讓交易更慢)
拜占庭 + signed messages
前提: 至少$2$個人忠誠
- 收到leader的msg，放到
orders的set中，把該msg加上自己的sign再傳給其他人 - 收到其他msg，如果msg不同，放到
orders的set中，把該msg加上自己的sign再傳給沒有在上面sign的人 - 都收完了，透過某個神祕choice函數從orders中選一個order (如果leader忠誠，應該只會有一個order)
非拜占庭 + 過半數都同意 (consensus)
paxos
非拜占庭 + 所有人都同意 (uniform consensus)
一般這裡都是看uniform consensus的特化問題
atomic commit
所有人都要一起commit或是abort。
只要有節點發生故障，atomic commit就一定會阻塞嗎？
根源就在於Abort和Commit並不是對等的決策
假設有一個節點宕機了，其它節點大可以選擇Abort決策（注意不能選擇Commit），從而讓整個事務Abort掉 在這個過程中，參與分佈式事務的所有節點（包括宕機的這個節點）對於“執行Commit還是Abort”也是達成了共識的（這個共識是Abort）
同步與異步 & 拜占庭與一般共識
拜占庭需要知道timeout，所以需要同步的時間 一般共識不用知道timeout是異步的
2PC & 3PC
- 發transation
- prepare問所有人行不行commit
- 都ok，發commit
- 有人不行，發abort
看起來很簡單，其實有細節 記得，分散式重要的是不能反悔這件事，在2PC有哪邊不能反悔?
只要回了ok，就必須等到master回commit
其他狀況都可以用發abort處理
但這有可能master在發commit之前死亡，這樣所有人都要等
所以有了3PC，與raft的prevote很像，在要大家prepare之前先問有沒有辦法回ok 因為這個不會回了ok這樣就算有人出事也沒差(fail early)
因為prevote已經確認過了大家都ok，這樣如果有人出事都可以直接過。 有人在prevorte，回不能commit就不會到第二階段，就不能動
最後就是看在什麼狀態下能回ok? server已經到了可以跑transation的狀態，同時沒有其他thread(transaction)可以改。 (因為這個會被persist，所以就算crash也沒事)
3PC的優點： 最大優點就是降低了參與者的阻塞範圍，並且能夠在出現單點故障後繼續達成一致。
3PC的缺點: 參與者接收到了PreCommit消息，然後網絡出現問題，參與者和協調者無法通信，這種情況下，參與者依然會執行事務的提交。
時間、排序
我們怎麼意識到時間流逝?
- 做了不同的指令
- 觀察的資料發生變化
有沒有我們無法意識到的時間? 也許有，但對於系統來說永遠有一個，現實時間
所以時間是什麼? 不一致的證據(證明)
而時間嚴格遞增，所以可以比較，就有了排序
順序一致性
- sort過後的所有指令，每個read都要與最近的write一樣 (全域的read/write序)
- 在process中的order要在sort過後的順序中保持 (process中的序)
下面是順序一致性的例子 A –> w1(x) r3(x) –> A // 這是舊的!! C –> w2(x) r3(x) –> C B –> w1(x) r3(x) –> B
線性一致性
在順序一致性的基礎上加一個條件
- 只要時間不overlay，指令之間的在時間上的order都要保持 (全域的時間序)
所以線性一致性可以確保read總是最新的，因此上面的例子不是線性一致
因果一致性
先定義因果關係 (a -> b，他是transitive，aka happen-before)
- 在同一process，a在b之前執行
- a做的write，b做read拿到
因果關係是一種偏序，也就是，不是所有東西都可以排序，像沒有因果關係的東西(async的指令)，就沒有排序也不知道怎麼排序；而現實時間是一種全序，都可以用時間點排序
接著定義因果一致性，在某個process的所有指令與其他process的write，可以sort成
- read拿到的值必須是最近一次的write
- sort要依據因果關係
這邊的重點是在某個process，也就是我們是從process去看而已。 這有什麼結果?
不同process可能看到的排序結果可能不同!!
上圖表達了兩個進程的並發執行過程。它是滿足因果一致性的
站在P1視角，有：
A –> w1(x) B –> w2(x) r1(x) –> B 站在P2視角，有：
B –> w2(x) A –> w1(x) r2(x) –> A
這樣的好處是可以在其他機器死亡時堤供舊資料，反正只要滿足因果關係就好
lamport clock & Strong Clock Condition
lamport clock的定義是如果a與b有因果關係，a的clock必定小於b的clock (偏序)
可以為每一個事件上一個數字，之後嚴格遞增，在synchronize時取最大的+1，就會拿到lamport clock。
同時，clock之間的比較，只有在有因果關係才有意義。 像是兩個併發的指令，比較clock就沒意義。
但這是可以實現全域排序的其中一種方法，因為clock隱含因果關係。 用clock排序後就有順序一致，如果同時符合時間序，就有線性一致。
符合時間序叫Strong Clock Condition 因為lamport clock是系統中的時間，與現實(外界)的時間不同步，所以可能看到新的request拿到比較小的lamport clock
不同步?
- 任意兩個時鐘的運行速率有差異，它們的讀數會漂移得越來越遠
- 時鐘的運行速率跟真實時間的流逝速率可能有差異
gc pause & redlock & fence token: 外界的時間
lamport clock是系統中的時間 Strong Clock Condition是現實或是宇宙的時間
還有其他時間嗎? 如果gc pause發生，變成自己的時間不準了，因為自己的時間與外界的時間不一致 但實際上時間早已流逝!!
所以可以引入下一個時間，在redlock的辯論中叫fence token，其實就是storage的lamport clock
同步時間
NTP可以同步時間，但還是有誤差(還有可能倒退!!)
所以要把誤差也算在時間點中(spanner的truetime)
最終一致性
這個一致性沒有保證任何東西，因為我們不確定會有什麼，只知道未來一定會有。
線性一致性和順序一致性屬於safety property（安全性） 而最終一致性屬於liveness property（活性）
safety：它表示「壞事」永遠不會發生 liveness：它表示「好事」最終會發生
通常來說，只有當safety和liveness這兩種屬性被同時考慮時，一個系統才能提供有意義的系統保證。 對於系統使用者來說，你必須針對數據不一致的可能性做好補償措施 (compensation)。 這也是最終一致性系統難用的地方
Ref
分布式领域最重要的一篇论文，到底讲了什么？ 基于Redis的分布式锁到底安全吗（上）？ 基于Redis的分布式锁到底安全吗（下）？ 条分缕析分布式：因果一致性和相对论时空 The Byzantine Generals Problem