動機

整理常見分散式設計手法

原子性

每一步都是一次到位或是根本沒有做

對時間建模

條件:

  • 時間嚴格遞增

  • 同一個時間下，所有人見到的時間一致

  • lamport clock

    1. clk++
    2. max(其他人的clk, 自己的clk)+1

  • vector clock

    • 紀錄每個人的clk

法定人數 (quorum)

只有在同樣的動作到法定人數的承認才做 (多數決)

這樣可以確保至少每一次的動作至少有一個人是知道前一次操作的

法定人數 + 對時間建模 = read quorum

user拿到許多response，要怎麼確認是最新的? 就是留下時間，這裡通常叫version，但其實就是lamport clock

anti-entropy (recovery)

user拿到最新的結果，可以write回去

提到anti-entropy，可以講到Dynamo

Dynamo是只有法定人數去調整一致性 在衝突處理是用vector-clock之後配合user自己選

在做recovery是用Merkle tree去比對不同node之間的key是不是不同 Merkle tree就是一顆一直hash組成tree node的tree Merkle tree的好處是不用拿所有hash過的資料就可以找出是不是與tree持有的hash不同

像下面的就是只要有root，hash(AB)，hash(C)，資料D，就能確認資料D的版本對不對

write quorum的問題

但如果同時有人拿同一個lamport clock去寫? 所以需要quorum給承諾，這個lamport clock只有我可以用，同時你不能吃<=這個clock的資料 而這個就是2 phase commit

2 phase commit (2PC)

  1. prepare
    • 問大家都ok嗎?
      • 回ok
        • client在回ok前要保證
          • 當下的state是ok的
          • 不論如何，都不會忘記當下的狀態
        • 之後就是等
      • 回abort
        • 就讓所有人abort
  2. commit
    • 讓大家commit

3 phase commit (3PC)

2PC有個問題是如果回ok之後就是等，但

  1. 如果問的人掛了
  2. 有人就是不回

其他人就是等到死

所以3PC加入pre-prepare

  1. pre-prepare
    • 問大家都ok嗎?
      • 回ok
        • client在回ok前要保證
          • 當下的state是ok的
          • 不論如何，都不會忘記當下的狀態
        • 之後就是等
      • 回abort
        • 就讓所有人abort
  2. prepare
    • 問大家都ok嗎?
      • 回ok
      • 自己出事不回
  3. commit
    • 讓大家commit

因為有了pre-prepare的保證，所以其他人可以在回了commit之後等

  1. 問的人
  2. timeout

其中一個觸發來完成commit

租約

每個node想確認其他node有沒有出事的其中一種手段，其實就是timeout

例子

  • 分散式鎖
    • 原子性
    • 對時間建模
      • redlock: wall time
      • zookeeper: file exist (or filename上有id)
      • chubby: lock id
  • paxos
    • 法定人數
    • 對時間建模
    • 2 phase commit
  • raft、zab
    • paxos
    • 租約 (確認leader還活著)
    • 題外話
  • 分散式事務 (事務的法定人數就是所有人，事務的時間就是commit或abort)
    • 2 phase commit