299
阿裏雲RDS金融數據庫(三節點版) - 理論篇
標簽
PostgreSQL , MySQL , 三節點版 , 金融數據庫 , Raft , 分布式共享存儲版
背景
《阿裏雲RDS金融數據庫(三節點版) - 背景篇》說明了為什麼需要推出金融級數據庫的三節點版本，以及三節點引入的一個世界難題 - 拜占庭將軍問題。
Lamport 在論文 《The Part-Time Parliament》中提出了一種算法Paxos，並使用了大量的數學公式論證了通過Paxos算法解決拜占庭問題的可行性。緊接著在《Paxos Made Simple》論文中，則完全放棄了所有數學符號的證明，使用純英文的邏輯推導。原因是 Lamport 認為 Paxos 很 simple，但也許隻是針對他的頭腦而言。事實是大家理解起來都還是很困難，所以 Raft 就是建立在希望得到一個更易於理解的 Paxos 算法的替代品。把可理解性作為算法的主要目標之一，從論文題目就可看出來《In Search of an Understandable Consensus Algorithm》。
拜占庭將軍的問題和三節點的問題一致，Raft成為了RDS解決三節點一致性、可靠性問題的普世算法。Raft作為RDS 金融數據庫(三節點版)的理論基礎，是高可用、高可靠的根基。
Raft 協議的易理解性描述
在一個由 Raft 協議組織的集群中有三類角色：
1、Leader（領袖）
2、Follower（群眾）
3、Candidate（候選人）
就像一個民主社會，領袖由民眾投票選出。剛開始沒有“領袖”，所有集群中的參與者都是“群眾”，那麼首先開啟一輪大選，在大選期間所有群眾都能參與競選，這時所有群眾的角色就變成了“候選人”，民主投票選出領袖後就開始了這屆領袖的任期，然後選舉結束，所有除領袖的候選人又變回群眾角色服從領袖領導。這裏提到一個概念「任期」，用術語 Term 表達（Term ID是自增的，每一輪成功的選舉都會產生一個新的Term ID，注意所有角色發現了新Term ID時自動服從他，解決了腦裂的問題）。關於 Raft 協議的核心概念和術語就這麼多而且和現實民主製度非常匹配，所以很容易理解。三類角色的變遷圖如下，結合後麵的選舉過程來看很容易理解。
三種角色的轉變說明如下：
1、Follower（群眾）
所有節點一開始都是Follower。
Follower在150ms ~ 300ms的隨機超時時間（Election Timeout）內，如果沒有收到任何Leader發過來的心跳消息，將會轉變為Candidate，給自己投票，同時請求其他人給自己投票，同時重置150ms ~ 300ms的隨機超時時間。
2、Candidate（候選人）
Candidate在150ms ~ 300ms的隨機超時時間內，沒有發生角色變化（即沒有轉換為new Leader的Follower，也沒有獲得足夠的票數轉換為Leader），那麼將重新發起選舉(給自己投票，同時請求其他人給自己投票，同時重置150ms ~ 300ms的隨機超時時間。)
在選舉過程中，Candidate獲得了多數票數，則轉換為new Leader。
Candiate發現了當前任期(自選任期)或更新任期的Leader時(即收到Leader發來的心跳)，轉變為該Leader的Follower。
3、Leader（領袖）
Leader發現了更新任期的Leader時，轉變為新任期Leader的Follower。
客戶端視角事務的三種狀態
不管是三節點還是單節點，都可能會出現這幾種狀態。
1、提交、回滾成功。客戶端正常收到數據庫的事務結束的信號，明確事務成功按要求結束。
2、UNKNOWN。客戶端發出了提交、回滾請求，但是未收到反饋。
3、提交失敗。客戶端收到事務結束失敗的信號，明確事務失敗。
無論是單節點還是多節點，都會有這三種事務狀態的可能存在。
Leader 選舉過程
在極簡的思維下，一個最小的 Raft 民主集群需要三個參與者（如下圖：A、B、C），這樣才可能投出多數票。初始狀態 ABC 都是 Follower，Follower在150ms ~ 300ms的隨機超時時間內，如果沒有收到任何Leader發過來的心跳消息，將會轉變為Candidate，給自己投票，同時請求其他人給自己投票，同時重置150ms ~ 300ms的隨機超時時間。
發起選舉這時有三種可能情形發生。下圖中前二種都能選出 Leader，第三種則表明本輪投票無效（Split Votes），每方都投給了自己，結果沒有任何一方獲得多數票。之後每個參與方隨機休息一陣（Election Timeout）重新發起投票直到一方獲得多數票。這裏的關鍵就是 隨機 timeout，最先從 timeout 中恢複發起投票的一方向還在 timeout 中的另外兩方請求投票，這時它們就隻能投給對方了，很快達成一致。
選出 Leader 後，Leader 通過定期（heart timeout，heart timeout必須小於150ms）向所有 Follower 發送心跳信息維持其統治，每次Follower收到Leader心跳後，重置隨機Election Timeout。
若 Follower 一段時間（Election Timeout）未收到 Leader 的心跳則認為 Leader 可能已經掛了，Follower將發起選主（election）過程。
Leader 節點對一致性的影響
Raft 協議強依賴 Leader 節點的可用性來確保集群數據的一致性。數據的流向隻能從 Leader 節點向 Follower 節點轉移。當 Client 向集群 Leader 節點提交數據後，Leader 節點接收到的數據處於未提交狀態（Uncommitted），接著 Leader 節點會並發向所有 Follower 節點複製數據並等待接收響應，確保至少集群中超過半數節點(quorum based)已接收到數據後再向 Client 確認數據已接收。一旦向 Client 發出數據接收 Ack 響應後，表明此時數據狀態進入已提交（Committed），Leader 節點再向 Follower 節點發通知告知該數據狀態已提交。
步驟4.1成功，客戶端就認為事務提交成功，換句話說事務已經持久化了。
因此4.2如果沒有發送成功，並且此時如果Leader異常，並發生了重新選舉，有沒有風險？New Leader的這筆事務到底是commit還是uncommit?
對於數據庫來說，隻要事務的WAL日誌到位了，那麼就該事務就持久化了，由於Follower已經有了WAL，因此數據庫是不會讓這筆事務丟失的，這也是ACID的D持久化，即用戶看到COMMIT了，那就一定COMMIT了（開啟異步提交遇到異常DOWN庫或DOWN機除外）。
在這個過程中，主節點可能在任意階段掛掉，看下 Raft 協議如何針對不同階段保障數據一致性的。
1. 數據到達 Leader 節點前
這個階段 Leader 掛掉不影響一致性，不多說。
2. 數據到達 Leader 節點，但未複製到 Follower 節點
這個階段 Leader 掛掉，數據屬於未提交(uncommit)狀態，Client 不會收到 Ack 會認為超時事務失敗。Follower 節點上沒有該數據，重新選主後 Client 重試 (重新發起整個事務請求) 重新提交可成功。原來的 Leader 節點恢複後作為 Follower 加入集群重新從當前任期的新 Leader 處同步數據，強製保持和 NEW Leader 數據一致。
（為了達到一致，這裏涉及到OLD Leader rewind的操作。）
3. 數據到達 Leader 節點，成功複製到 Follower 所有節點，但還未向 Leader 響應接收
這個階段 Leader 掛掉，同時數據在 Follower 節點處於未提交狀態（Uncommitted）但保持一致，重新選出 Leader 後可完成數據提交，此時 Client 不知到底提交成功沒有，也就是說客戶端視角事務狀態為UNKNOWN。
但是對於NEW Leader，和OLD Leader的數據是一致的。
如何解決UNKNOWN的事務，後麵的係列文章會講到。
4. 數據到達 Leader 節點，成功複製到 Follower 部分節點，但還未向 Leader 響應接收
這個階段 Leader 掛掉，數據在 Follower 節點處於未提交狀態（Uncommitted）且不一致，Raft 協議要求投票隻能投給擁有最新數據的節點。所以擁有最新數據的節點會被選為 Leader 再強製同步數據到其他 Follower，數據不會丟失並最終一致。
與第三種情況類似，此時 Client 不知到底提交成功沒有，也就是說客戶端視角事務狀態為UNKNOWN。
但是對於NEW Leader，和OLD Leader的數據是一致的。
5. 數據到達 Leader 節點，成功複製到 Follower 所有或多數節點，數據在 Leader 處於已提交狀態，但在 Follower 處於未提交狀態。（實際上就是圖中標注的4.2步驟沒有被執行）
這個階段 Leader 掛掉，重新選出新 Leader 後的處理流程和階段 3 一樣。
這個情況下，Follower實際上已經包含了最新的數據庫WAL日誌，NEW Leader隻要APPLY WAL即可達到事務committed的最終狀態，不會丟失數據，也不會改變客戶端視角對事務提交成功狀態的認知。
6. 網絡分區導致的腦裂情況，出現雙 Leader
網絡分區將原先的 Leader 節點和 Follower 節點分隔開，Follower 收不到 Leader 的心跳將發起選舉產生新的 Leader。這時就產生了雙 Leader，原先的 Leader 獨自在一個區，向它提交數據不可能複製到多數節點所以“永遠提交不成功”
（雖然提交不成功，從數據庫WAL日誌角度來看，依舊可能出現 舊Leader 和 新Leader 存在差異的情況。例如 舊Leader 接收到某些請求，產生了WAL，隻是提交事務的信息由於無法到達多數派，舊Leader是不會向客戶端返回commit ack的，因此向OLD Leader發起事務提交請求的客戶端會超時失敗。）。
客戶端向新的 Leader 提交數據可以提交成功。
網絡恢複後 舊Leader 發現集群中有更新任期（Term）的新 Leader，舊Leader 自動降級為 Follower 並從 新Leader 處同步數據（對於數據庫，可能OLD Leader首先要rewind，然後才能從NEW Leader同步）達成集群數據一致。
一些邏輯定理：
1、永遠不可能存在兩個Term ID相同的Leader，因為同一個Term ID每個角色隻有一票，所以絕對隻有一個Leader得到多數票。
2、如果同時存在兩個Leader，Term ID低的那個，事務提交一定會超時，因為它的Follower一定是不足的，副本數不足，永遠不會返回Client ack。
綜上窮舉分析了最小集群（3 節點）麵臨的所有情況，可以看出 Raft 協議都能很好的應對一致性問題，並且很容易理解。
但是要結合數據庫和Raft，實現金融級零數據丟失和一致性的數據庫多副本產品，會更加複雜，例如rewind，以及UNKNOWN事務的處理（即使是單節點，依舊需要處理unknown事務）。
總結
算法以正確性、高效性、簡潔性作為主要設計目標。
雖然這些都是很有價值的目標，但這些目標都不會達成直到開發者寫出一個可用的實現。
所以我們相信可理解性同樣重要。
Raft 算法是 2013 年發表的，大家在參考[5]上麵可以看到有多少個不同語言開源的實現庫了，這就是算法可理解性的重要性。
阿裏雲RDS金融數據庫(三節點版)以Raft協議為基礎，將重做日誌的複製、選主與Raft進行結合，打造了一個可以同時滿足可用性、可靠性，並保持高性能的金融級的數據庫。
參考
[1]. LESLIE LAMPORT, ROBERT SHOSTAK, MARSHALL PEASE. The Byzantine General Problem. 1982
[2]. Leslie Lamport. The Part-Time Parliament. 1998
[3]. Leslie Lamport. Paxos Made Simple. 2001
[4]. Diego Ongaro and John Ousterhout. Raft Paper. 2013
[5]. Raft Website. The Raft Consensus Algorithm
[6]. Raft Demo. Raft Animate Demo
係列文章
《阿裏雲RDS金融數據庫(三節點版) - 實現篇》
《阿裏雲RDS金融數據庫(三節點版) - 性能篇》
《阿裏雲RDS金融數據庫(三節點版) - 案例篇》
阿裏雲RDS金融數據庫(三節點版)
阿裏雲RDS金融數據庫 - PostgreSQL三節點版(敬請期待)
最後更新：2017-07-12 22:05:51