# 3-1 A Majority Consensus Approach to Concurrency Control
## Introduction
- 儲存多副本的好處
- 增加資料的可用性
- 加快資料反應速度
- 於資料存儲節點發起的查詢可以立即返還
- 靠近資料存儲節點發起的查詢可以低延遲返還
- 負載分攤(load sharing)
- 此篇論文探討在資料更新時，如何維護多節點之間相同副本的同步問題。而並不討論資料該更新到哪個節點，以及讀取時應該至少拿多少個副本等問題
- [共識 vs 一致性](https://zhuanlan.zhihu.com/p/35596768)
- 2 種此篇定義的 consistency
- mutual consistency
- 同個副本的多個節點在更新停止後，應該要收斂到一個大家都有相同值的狀態
- internal consistency
- 多個副本在一個資料庫節點裡，彼此之間存在的不變關係
- 範例:
- 節點 A 跟 B 都有 x, y, z，並且各初始化為 1。同時這三種資料保存著一種 internal consistency: `x + y + z = 3`
- 今次有 2 個更新，`Rl: x := -1, y := 3`、`R2: y := -1, z := 3`
- Internal consistency
- 假如 2 個更新都被接受，internal consistency 便被破壞，因為 `x + y + z` 就不再是 3，反而是 1。
- 其中最重要的概念是，R1 跟 R2 都是參照 x, y, z 都還是初始值 1 的情況下所出現的更新行為，假如 R1 先被接受，而 R2 原本的 x, y, z 參照值便已經被改變，因此 R2 必須拒絕
- 在維護 internal consistency 的情況下， R1 跟 R2 只能有一個更新被接受，另外一個則必須被否決，同時告知拒絕通知給更新程序。
- Mutual consistency
- Mutual consistency 也是有可能被破壞，假如 A 接受 R1，B 接受 R2，兩邊的 x, y, z 就是保存不同值。
- 此種會不同節點上的副本產生衝突的狀況，各節點應該都要接受同一種更新行為，要嘛就大家 R1，要嘛就大家 R2
- 兩種分散式架構
- Centralized control
- 所有的更新都是透過一個主節點決定通不通過，並分派更新給底下的節點
- 對於偵測以及解決衝突比較簡單達成
- 主節點壞了就只能等待
- Distributed control (此篇論文演算法設計於此種架構)
- 更新是由多個節點一起決定以及一起寫入
- 就算有多個節點壞掉，只要至少一個存在，整體系統還是可以運行
- 對於解決衝突以及避免死鎖並沒有一個 Trivial 的解法
- 此篇演算法: Majority consensus 概述
- 多個節點對更新請求進行投票決定允不允許
- 如果更新行為所參考的值是該節點目前擁有的(使用時間搓判定)，則該節點可接受此更新，投一票
- 可避免死鎖，維持 internal consistency, mutual consistency
- 即使有節點壞掉，此算法還是可以正常運作

## 分散式資料庫環境
- 此篇論文是假設更新行為是作用於所有節點，部分節點也是可以運作，但不討論
- Database Managing Process (DBMP)
- 每個節點的資料庫都是透過此種 process 進行讀寫操作
- 資料庫是由多個元素(elements)組成，就單純想成 DB 裡的資料就好
- 其中，每個元素會有 儲存的值 以及 一個時間搓
- 時間搓代表當前儲存值被賦予的時間點
- 時間搓作用
- 確保 internal consistency
- 提供 mutual exclusion lock 的特性
- timestamps are used in the procedure followed by a DBMP when it applies an update to its database copy. (?)
- 針對發起請求者，我們稱做 應用行程 (Application Process，往後簡稱 AP)
- 讀取請求
- DBMP 收到 AP 的請求後，從其管理的節點回傳副本
- 更新請求 (一系列步驟)
1. Query Database: AP 會先做副本讀取，拿到基礎參考值和基礎參考值的時間搓
2. Compute Update: AP 拿到參考值後，做本身需要的計算獲得待更新的值
3. Submit Request: AP 將更新值以及原參考值的時間搓送給 DBMP
4. Synchronize Update: 多個 DBMP 參與投票環節，投票準則為檢查請求中的參考值時間搓有沒有跟自己資料副本裡值的時間搓一樣，如果一樣，就投一票
- 時間搓一樣代表本次更新是基於自身擁有的值算出來的
5. Apply Update: 投票通過，DBMP 更新其副本的值與時間搓
6. Notify: 通知 AP 最後的更新結果
- 此篇論文假設各行程之間的通訊都是非常可靠
- 假如接收行程壞了，消息會一直持續等待直到接收行程真的收到，並回傳收到的通知給發送行程為止

## Majority Consensus Algorithm
- 由五大規則組成
- DBMP 之間的通訊機制: 包含 串接、具有 time out 以及重傳機制的串接、廣播(broadcast)
- 投票規則: 每個 DBMP 在考慮更新請求時，所遵循的規則
- 請求解決規則: 多個 DBMP 投完票後，再根據此規則決定更新的最終結果
- 更新規則: 利用此規則將值更新至副本
- 時間搓生成規則: 當 AP 發出更新請求生成時間搓，以及當副本更新時也更新其時間搓
- DBMP 之間的通訊機制
- 廣播 (Broadcast)
- 一個 DBMP 收到更新請求後，廣撥給其他 DBMP 進行投票，其他 DBMP 投完票後，再返回給一開始的 DBMP
- 低延遲，高額外空間
- 串接 (Daisy Chain):
:::info
論文後續研究採用此種通信方式解釋
:::
- 一個 DBMP 收到更新請求後，將請求跟票數傳遞給下個 DBMP，如此循環下去，直到更新請求的投票結果備決定出來
- 高延遲，低額外空間
- 在串接模式下，有兩種暫時停止傳遞下去的狀況:
1. 找不到其他可以被存取並且還沒投過票的 DBMP
- 解法: 前面有提到通信系統會持續等待直到接收行程收到，所以就等到有任意接收行程可以被 access 為止
2. 傳遞更新請求的 DBMP 本身 crash 了
- 解法: 使用 "timeout 和 重傳" 機制
- 而傳給 crashed DBMP 的原 DBMP 發現了 time out 現象，則應該將請求傳給其他正常且沒投過票的 DBMP
- 就算壞掉的 DBMP 回來了，他還是可以接收原本要傳給他的請求，並進行投票，然後再傳遞下去 (多出一個分支)
- 加強系統可靠性
- 單一DBMP投票規則
- 簡易版
- OK: 如果副本本身儲存的值是更新請求使用的參考值時
- REJ: 副本儲存的值已經被修改過，不再是更新請求採用的參考值時
- 副本的值以及更新請求的參考值比較是用兩邊的時間搓檢查
- pending: 當一個更新請求被一個 DBMP 投票 OK，但其他 DBMP 還沒完全投完票時
- 兩個因素需要考量:
1. 本身有 pending 的請求(R1)，此時又有另一個請求過來(R2)
- R1 跟 R2 都是參考目前副本的值，因此會認為 R2 的參考值等於目前的值就投 OK
- 但是等 R1 被寫入後，副本的值變了，R2的參考值就不存在，導致 R2 根本就不應該投 OK
- 解法: R2 必須被延後(defer)，等到 pending 中的 R1 被寫入後，才能再對 R2 進行投票
2. 使用解法一的延遲，便會衍伸出死鎖
- 2 個 DBMP 同時發送更新請求，代表兩個 DBMP 各自會收到對方發的請求，但因為雙方本身也都還有自己的請求被 pending，因此互等對方
- 解法: 引入新的票種 PASS: 當 DBMP 發現此更新請求跟目前 pending 的請求有衝突，發出 PASS 告知後面的 DBMP 可能有死鎖會發生
- defer 以及 PASS 都是針對有 conflict 的請求才需要投的
- 透過優先權決定要投哪個
- 新的請求 < pending 請求: 投 PASS
- 新的請求 > pending 請求，或請求中的參考值比副本裡的值來的新: 投 defer
- 改良版:
- OK: 如果副本本身儲存的值是更新請求使用的參考值時，且請求沒有跟 pending 的請求有 conflit
- REJ: 副本儲存的值已經被修改過，不再是更新請求採用的參考值時
- PASS: 副本本身的值跟請求的值是一樣的，但是請求跟 pending 中的有 conflict，且新請求的優先權比較小
- defer: PASS 的反之
- 請求解決規則
- 大部分的 DBMP 都投 OK，代表此請求可被接受
- 大部分的意思是要過半，這樣兩個群體才會有重疊的
- 兩個部分
- 請求還在持續投票中，其中一個 DBMP 投完票後，4種狀況
- 投OK，且已有大部分的DBMP產生共識 => accept
- 投REJ => reject
- 投PASS，且已不可能有大部分的DBMP產生共識 => reject
- 繼續累積票數
- 請求已經 accept
- 將更新寫入
- 將因為此次更新而延後的其他更新都 reject
- 請求已經 reject
- 針對因為此次更新而延後的其他更新做重新投票
- 在不使用 time out 機制的串接通訊，有一個 DBMP REJ 就代表此請求就只能被拒絕
- 但有使用的情況下，請求走過的 DBMP 路線就會產生多個分支，導致多個 DBMP 可以決定請求的走向
- REJ 的能力就必須被弱化
- 狀況被更改成: 投 REJ，且已不可能有大部分的DBMP產生共識 => reject

- 更新規則
- 此規則是為了讓更新有一定的順序，不亂套
- 更新請求有一個時間搓 Rt，副本內部值的時間搓 Vt
- 假如 Vt < Rt，代表此次更新是新的，可以寫入
- 反之代表此次更新已經過時，忽略

- 時間搓生成規則
- 時間搓具有: 唯一性 以及 單調性(持續增長)
- 時間是紀錄 更新請求被 DBMP 發出的當下
- 時間搓結構: (T, i)
- T 是 DBMP i 所記錄到的機器時間
- 時間搓比大小 T1 = (C1, d1), T2 = (C2, d2):
- T1 = T2 => C1=C2 and d1=d2
- T1 > T2 => (C1 > C2) or (C1=C2 and d1>d2)
- T1 < T2 => (C1 < C2) or (C1=C2 and d1<d2)
- 無法保證每個 DBMP 的機器時間都有一樣的速度，這樣在比大小會有異常狀況(sequencing anomaly)
- 更改 T 的紀錄方式
- time 是 DBMP i 記錄到的自身時間
- Tb 是 DBMP i 發起更新請求 R 中，其參考值所夾帶的時間搓 T

## 演算法驗證
- 5個論證
- 更新請求最終要嘛是被接受或拒絕，不會同時都有
- 不會有死鎖
- 同個副本種類的資料庫最終都會匯聚成相同的值
- 此演算法保證 mutual consistency 以及 internal consistency
- sequencing anomaly 不會發生
- 論證1: 更新請求最終要嘛是被接受或拒絕，不會同時都有
- 單純串接 (請求投票路線只有一種走向)
- 每個 DBMP 根據請求解決規則，決定請求的最終走向。
- 在請求解決規則中有明確定義，因此不會同時接受又拒絕
- 用了 timeout 的串接 (投票路線會因為 timeout 導致產生都個分支)
- 用反證，假設請求同時被接受又拒絕，根據請求解決規則
- 要接受: 要大部分的 DBMP 投 OK
- 要拒絕: 要大部分的 DBMP 投 PASS 或 REJ
- 這樣造成至少有一個 DBMP 投 OK 以及 REJ/PASS，但根據一個 DBMP 的投票規則，此狀況不允許
- 論證2: 不會有死鎖
- 單純串接
- 一個 DBMP 可以有4種決定
- 投OK: 請求傳遞下去，直到所有 DBMP 或是已決定出有沒有大部分共識就會結束
- 投REJ: 此更新請求直接被 reject，結束
- 投PASS: 請求傳遞下去，直到所有 DBMP 或是已決定出有沒有大部分共識就會結束
- 選擇延後投票
- 針對延後投票
- 假設請求Rt是在時間t發出，因此在Rt之前，有R1到Rt-1個有限請求，且優先權是越早的越小
- R1是最小優先度，因此一定不會被延遲，只能是 OK 或 REJ
- 假如有DBMP已經寫入R1，並發出R2。當R2來到那些還沒寫入R1的DBMP，就會先被那些DBMP延遲。
- 而那些還沒寫入R1的DBMP終將會寫入R1，屆時R2就可以重新投票
- R1~Rt-1持續下去，最終Rt成為最小優先度的更新
- 論證3: 所有相同複本最終會收斂
- 根據更新規則，被接受的多個更新會依據其時間搓依序更新
- 並且論文已有假設通訊系統是非常可靠
- 論證4:
- 論證5:
- (好像沒特別說明為什麼行得通)
- 並不是任何兩起以上的更新請求都可以排序，而是有conflict的更新請求才可以排序，也就是都參考共同複本值的多個請求。

## 演算法效能
- 效能標準
- 通訊次數
- 計算量
- 通訊模式採用單純串接
- 做一次更新的通訊次數
1. AP 跟 DBMP 請求要複本值，傳複本值，並請求更新
2. 過半的 DBMP 投票中
3. 投完票，告訴所有 DBMP 投票結果
4. 回傳更新請求結果給 AP
- Best Case (一過半就有共識): n+ceil(n/2)+3
- Worst Case (要全部傳完才有共識): n+(n-1)+3 = 2n+2 = 2(n+1)
- 假設 AP 計算花的成本為 C，一次通訊花的成本為 M，則對於一個沒有被拒絕的更新請求 C0 來說
- C + M * (n+ceil(n/2)+3) <= C0 <= C + M * 2(n+1)
- 左測值我們稱做 C0min，右側值我們稱做 C0max
- 假如更新請求被拒絕一次，我們代號 C1
- C0min + C + 2M <= C1 <= C0max + C + 2nM
- 左側 C + 2M (想成第一個傳遞到請求的 DBMP 直接 REJ)
- 2M 是指 DBMP 告知 AP 請求失敗，以及 AP 重做一次計算後再請求一次更新
- C 是指 AP 的重做一次計算
- 右側 C + 2nM (想成傳到最後一個 DBMP 才 REJ)
- 2nM 是指傳到最後一個 DBMP 之前會先有 n-1 次，最後一個 DBMP 發出 REJ 後，再一路回傳回去，又 n-1 次 (感覺論文解釋怪怪的)
- C 同理
- 假如更新請求被拒絕 k 次，我們代號 Ck
- C0min + k * (C + 2M) <= Ck <= C0max + k * (C + 2nM)

## 記憶體缺失問題
- DBMP 本身會記錄自己投票的行為或是有甚麼是被延遲或是 pending 的請求待投票
- 記憶體缺失指的就是 儲存上述 DBMP 資訊的儲存空間突然壞了，有可能發生
- 他忘記自己已經投過票了，又投一次 OK，導致本來應該沒有大部分共識的變成有大部分共識
- 因為資訊缺失導致重複投票，並且投出跟上次投票不一樣的結果，導致請求變成同時接受又拒絕
- DBMP 本身不會知道自己的儲存壞了，因此只能靠人為觸發 recovery
- 人為觸發修復後，DBMP 就會知道自己原來已經 memory loss 了，這時他會需要補回兩件事
- 從 loss 的時間點開始，將這段時間內遺失的已接受請求補回來
- 從 loss 的時間點開始，對於還沒投出結果，但是自己已經投過票的請求補回來
- 對此，作者提出兩階段 recovery
- 第一階段，要做 recovery 的 DBMP，我們稱做 M，告知其他 DBMP 說我正在做 memory 回復，其他 DBMP 則必須停止傳遞 M 已經投票過的更新請求
- 第二階段，當請求停止傳遞後，M 再去跟其他 DBMP 要上述遺失資訊，要回來後，請求再繼續傳遞下去
- 有可能第二階段的時候，某個 M 去要資料的 DBMP 也 memory loss 了，這時 M 只能重新返回第一階段，重複循環，直到 M 可以從該 DBMP 要到東西為止

## 進一步發展
1. 對於資料版本非常講究的應用，如果副本裡的資料不是最新的，應該怎麼處理?
2. 本篇論文著重在通訊模式是串接的情況下，如果換成其他方法，投票規則以及更新方法可以怎麼變化?
3. 在記憶體缺失的解法中，可以發現每個 DBMP 都要儲存大量的歷史紀錄以供隨時可能需要回復，是用空間成本來取代。是否有其他辦法來降低這個成本?或是因為 memory loss 的狀況幾乎不太會發生，是否可以用更為簡單的方法即可做到 memory recovery?