PacificA演算法分析
- 2019 年 10 月 30 日
- 筆記
PacificA演算法是微軟亞洲研究院提出的一種用於日誌複製系統的分散式一致演算法，與其他的一致性演算法相比，PacificA演算法主要用於數據的一致性管理，並另闢蹊徑採用其他一致性組件來進行配置一致性管理。
1. 特點
- 配置管理與數據管理分離：引入額外一致性組件來維護Configuration
- 強一致性：任意時刻讀取到的數據都是最新數據
- 少數派Replica可用時仍可讀寫：每個副本都有全量數據因此只要有一個副本存在即可保證讀寫
- 去中心化的故障檢測：通過節點間的契約機制來進行故障檢測
2. 名詞
- Replica Group：互為副本的一組數據的集合，其中有一個primary，其餘都是secondary
- Configuration: Repica Group的元數據，如副本有哪些，誰是primary等
- Configuration Manager: 配置一致性管理工具
- Serial Number(SN): 代表Update的執行順序，每次update增加1
- Prepared List: Update操作的序列
- Committed List: 已經提交的update序列，是Prepared List的前綴
3. 讀寫流程
3.1 查詢(query)
該演算法中，查詢只能在primary上進行，primary獲取自身的數據，直接返回即可
3.2 更新(update)
更新也是在primary上發起，流程如下
- primary為updateRequest分配一個SN
- primary發送prepare請求到各secondary,請求中包含updateRequest和SN
- 各secondary接收到請求，並將updateRequest和SN加入到PreparedList中，返回ACK給primary
- 當primary收到所有secondary的ack後，則執行該update，並將commit point移動到該commit。
- 返回執行成功
可以看到當一個update執行成功後，primary上對應的數據已經commit，secondary上數據也被加入到了更新隊列中。在這種情況下
- 讀操作讀取的是primary上的commitList,可以拿到更新的數據。
- secondary中雖然數據沒有被commit，但是也被加入到了prepared List中，當主節點掛掉時仍能保證數據不丟失。
- secondary上的數據不能自己commit，而必須由於primary來觸發。這是為了應對由於異常情況導致update沒有執行成功，secondary自主commit導致未更新成功數據被commit，且數據領先與primary。
3.3 Committed Invariant
從讀寫流程可以推導出committed不變式"Committed Invariant"
- Secondary Committed List為Primary committed List的前綴, 即primary commit領先於secondary。
- Primary Committed List為Secondary PreparedList的前綴，即Sencodary擁有primary commit的所有數據（雖然沒有committed）。其實當沒有在進行update操作時，Secondary的PreparedList和Primary的CommittedList是應該是一樣長的。
?這裡想到一個異常情況，當update執行過程中，primary掛掉了，導致更新失敗，secondary已經被prepare了update，這時一個secondary被選為新的primary，將其所有的update commit，那之前失敗的update操作數據不就出現在了數據中，導致與預期不符？
這裡與同事討論了一下，認為pacificA演算法中一個primary或secondary是一個數據實體，不應該是一個執行實體，所以當primary掛掉後，update任務不會執行失敗，而是等待選出新的primary，並在其上commit這個update，保證不會出現數據不一致的情況。
4. 故障檢測和恢復
pacificA通過契約(lease)的方式來進行primary和secondary間的互相檢測。primary會定期(lease period)向各節點請求契約，如果某個節點沒有回復，則說明該節點已經故障，primary會向Configuration Manager請求移除該secondary。 如果過了(grace period), 一個secondary沒有收到primary的請求，則認為primary故障，該secondary會向Configuration請求移除Primary，並將自己設置為primary。這裡要注意
- 當多個secondary均發現primary故障，則按照first win原則，先請求的成為primary
- 當出現網路分區時，primary會要求剔除secondary， secondary要求剔除primary，但由於lease period< grace period，可以保證primary先於secondary發現故障，並將secondary剔除
4.1 secondary故障
當一個scondary故障時，primary在向該secondary發送lease請求時會超時，primary向Configuration Manage發送Reconfiguration請求將該secondary從Configuration中移除
4.2 primary故障
當primary故障時， secondary在超過grace period沒有收到primary的請求，就會向Configuration Manager發送Reconfiguraiont請求
要求將primary從configuration中移除並將自己選為primary。多個secondary競爭成為primary時，遵循first win原則。
當一個secondary被選為primary後 ,它會向所有的secondary發送prepare請求，要求所有的sencodary均以其pareparedList為準進行對齊，當收到所有secondary的ack後，primary將自己的commit point移動到最後，這個時候primary才能對外提供服務。
4.3 網路分區的場景
網路分區場景下，primary認為secondary故障，secondary認為primary故障，但由於lease period小於grace period，所以primary會先與secondary發現故障，並向Congfiguration Manager發送請求移除secondary
4.4 新節點加入
新節點加入時，首先會先成為secondary candidate, 然後追平primary的preparedList,然後申請成為secondary。還有一種情況是之前故障的節點恢復加入，這個時候會復用之前的preparedlist並追平secondary的preparedlist, 然後申請成為secondary。
4.5 Primary Invariant
在pacificA演算法中，要保證primary不變式Primary Invariant，即
- 同一個時刻只有一個副本認為自己是primary
- configuration Manager也認為其是primary。 從前面的故障恢復可以看到pacificA演算法通過lease（契約）機制保證了這個不變式
4.6 Reconfiguration Invariant
重新配置不變式：當一個新的primary在T時刻完成reconfiguration,那麼T時刻之前任意節點（包括原primary）的committedList都是新的primary當前committedList的前綴。
該不變式保證了reconfiguration過程中沒有數據丟失，由於update機制保證了任意的sencondary都有所有的數據，而reconfiguration重新選primary要求新的primary commit其所有的prepareList,因此這個不變式可以得到保證。
5. 演算法總結
PacificA是一個讀寫都滿足強一致的演算法，它通過三個不變式保證了讀寫的primary的唯一性，讀寫的強一致性，故障恢復的可靠性。
它把數據的一致性和配置的一致性分開，使用額外的一致性組件（Configuration Manager）維護配置的一致性，結合lease機制保證了Primary Invariant，使得在同一時刻有且僅有一個primary。 update操作時，要求所有的secondary均prepare當前update，primary commit當前update，保證了Committed Invariant, 使得讀操作可以獲取到最新數據，primary故障時，secondary也有全量的數據。
故障恢復機制保證了當secondary被選為primary時，其commit包含之前primary或secondary的commit，保證了Reconfiguration Invariant，使得在故障恢復後數據不會有丟失。
