text: Raft是一種用於替代Paxos的共識演算法。相比於Paxos，Raft的目標是提供更清晰的邏輯分工使得演算法本身能被更好地理解，同時它安全性更高，並能提供一些額外的特性。:1Raft能為在計算機叢集之間部署有限狀態機提供一種通用方法，並確保叢集內的任意節點在某種狀態轉換上保持一致。Raft演算法的開源實現眾多，在Go、C++、Java以及 Scala中都有完整的程式碼實現。Raft這一名字"Reliable, Replicated, Redundant, And Fault-Tolerant"的首字母縮寫。叢集內的節點都對選舉出的領袖採取信任，因此Raft不是一種拜占庭容錯演算法。簡介.Raft透過選舉領袖的方式做共識演演算法。在Raft叢集:5。在正常情況下只會有一個領袖，其他都是追隨者:5。而領袖會負責所有外部的請求，如果不是領袖的機器收到時，請求會被導到領袖:5。通常領袖會藉由固定時間傳送訊息，也就是「心跳，叢集就會進入選舉狀態。Raft將問題拆成數個子問題分開解決:1，讓人更容易瞭解：領袖選舉.在起始演演算法或領袖當機、斷線的時候，就需要選舉出新的領袖。此時叢集進入新的任期並開始選舉，如果選舉成功則新的領袖開始執行工作，反之則視此任期終止，開始新的任期並開始下一場選舉。選舉是由候選人發動的。當領袖的心跳逾時的時候，追隨者就會把自己的任期編號加一、宣告競選、投自己一票、並向其他伺服器拉票。每個伺服器在每個任期只會投一票，固定投給最早拉票的伺服器。如果候選人收到其他候選人的拉票、而且拉票的任期編號不小於自己的任期編號，就會自認落選，成為追隨者，並認定來拉票的候選人為領袖。如果有候選人收到過半的選票就當選為新的領袖。如果逾時仍沒有選出新領袖，此任期自動終止，開始新的任期並開始下一場選舉。Raft每個伺服器的逾時期限是隨機的，這降低伺服務同時競選的機率，也降低因兩個競選人得票都不過半而選舉失敗的機率。記錄複寫.記錄複寫的責任在領袖身上。整個叢集有個複寫的狀態機，可執行外來的指令。領袖接收指令，將之寫入自己記錄中的新指令部分，然後把指令轉發給追隨者。如果有追隨者沒反應，領袖會不斷重發指令、直到每個追隨者都成功將新指令寫入記錄為止。當領袖收到過半追隨者確認寫入的訊息，就會把指令視為已儲存。當追隨者發現指令狀態變成已儲存，就會在其狀態機上執行該指令。當領袖當機時，領袖的某些新指令可能還沒複寫到叢集整體，造成叢集的記錄處於不一致的狀態。新領袖會擔起重返一致的責任，讓每個追隨者的記錄都和它的一致，做法是：和每個追隨者比對記錄，找出兩者一致的最後一筆指令，刪除追隨者之後的指令，把自己之後的指令複製給追隨者。這個機制完成時，每個伺服器的記錄就會一致。安全性.Raft的安全性規則.Raft保證以下的安全性：前四項保證的原因詳見上述演演算法，狀態機安全性則藉由下述選舉流程的限制所達到。追隨者當機.當某臺追隨者當機時，所有給它的轉發指令和拉票的訊息都會因沒有回應而失敗，此時傳送端會持續重送。當這臺追隨者開機重新加入叢集，就會收到這些訊息，追隨者會重新回應，如果轉發的指令已經寫入，不會重覆寫入。領袖當機.領袖當機或斷線時，每個已儲存指令必定已經寫入到過半的伺服器中，此時選舉流程會讓記錄最完整的伺服器勝選。其中一個因素是Raft候選人拉票時會揭露自己記錄最新一筆的資訊，如果伺服器自己的記錄比較新，就不會投票給候選人。逾時期限和可用性.因為Raft啟動選舉是基於逾時，使得逾時期限的選擇至為關鍵。若遵守演演算法的時限需求"廣播時間 « 逾時期限 « 平均故障間隔"就能達到穩定性。這三個時間定義如下："廣播時間"典型是 0.5ms 到 20ms，"平均故障間隔"通常是用週或月來計算的，所以可以將"逾時期限"設在 10ms 到 500ms。
metadata: erhwenkuo/wikipedia-zhtw
metadata: Raft
metadata: https://zh.wikipedia.org/wiki?curid=6001111