imported>Yumeto：使用DisamAssist清理消歧義連結：Go（改連結至Go語言）。

2026-03-02T15:25:37Z

新页面

{{NoteTA|G1=IT}}
{{Otheruses|subject2=Raft|Raft (消歧義)}}
'''Raft'''是一种用于替代[[Paxos]]的[[共識機制|共识]]算法。相比于[[Paxos]]，Raft的目標是提供更清晰的逻辑分工使得算法本身能被更好地理解，同时它安全性更高，并能提供一些额外的特性。<ref name="raft">{{Cite web|url=https://raft.github.io/|title=Raft Consensus Algorithm|accessdate=2017-12-31|archive-date=2018-01-20|archive-url=https://web.archive.org/web/20180120122313/https://raft.github.io/|dead-url=no}}</ref><ref name="raft-paper">{{Cite|url=https://raft.github.io/raft.pdf|title=In Search of an Understandable Consensus Algorithm (Extended Version)|accessdate=2017-12-31|authors=Diego Ongaro, John Ousterhout|archive-date=2017-09-05|archive-url=https://web.archive.org/web/20170905163951/https://raft.github.io/raft.pdf|dead-url=no}}</ref>{{Rp|1}}Raft能为在[[计算机集群]]之间部署[[有限状态机]]提供一种通用方法，并确保集群内的任意节点在某种状态转换上保持一致。Raft算法的开源实现众多，在[[Go語言|Go]]、[[C++]]、[[Java]]以及 [[Scala]]中都有完整的代码实现。Raft这一名字来源于"Reliable, Replicated, Redundant, And Fault-Tolerant"（“可靠、可复制、可冗余、可容错”）的首字母缩写。<ref>{{Cite web |url=https://groups.google.com/forum/#!topic/raft-dev/95rZqptGpmU |title=Why the "Raft" name? |accessdate=2020-08-12 |archive-date=2011-01-22 |archive-url=http://arquivo.pt/wayback/20110122130054/https://groups.google.com/forum/#!topic/raft-dev/95rZqptGpmU |dead-url=no }}</ref>

集群内的节点都对选举出的领袖采取信任，因此Raft不是一种[[拜占庭将军问题|拜占庭容错]]算法。<ref name="raft-paper"/>

== 簡介 ==
Raft透過選舉'''領袖'''（{{langx|en|leader}}）的方式做共識演算法。

在Raft叢集（{{langx|en|Raft cluster}}）裡，伺服器可能會是這三種身份其中一個：'''領袖'''（{{langx|en|leader}}）、'''追隨者'''（{{langx|en|follower}}），或是'''候選人'''（{{langx|en|candidate}}）<ref name="raft-paper"/>{{Rp|5}}。在正常情況下只會有一個領袖，其他都是追隨者<ref name="raft-paper"/>{{Rp|5}}。而領袖會負責所有外部的請求，如果不是領袖的機器收到時，請求會被導到領袖<ref name="raft-paper"/>{{Rp|5}}。

通常領袖會藉由固定時間發送訊息，也就是「心跳（{{langx|en|heartbeat}}）」<ref name="raft-paper"/>{{Rp|5}}，讓追隨者知道叢集的領袖還在運作。而每個追隨者都會設計逾時機制（{{langx|en|timeout}}），當超過一定時間沒有收到心跳（通常是150 ms或300 ms<ref name="raft-paper"/>{{Rp|6}}），叢集就會進入選舉狀態。

Raft將問題拆成數個子問題分開解決<ref name="raft-paper"/>{{Rp|1}}，讓人更容易了解：
* 領袖選舉（{{langx|en|Leader Election}}）
* 記錄複寫（{{langx|en|Log Replication}}）
* 安全性（{{langx|en|Safety}}）

=== 領袖選舉 ===

在起始演算法或領袖當機、斷線的時候，就需要選舉出新的領袖。

此時叢集進入新的任期（{{langx|en|term}}）並開始選舉，如果選舉成功則新的領袖開始執行工作，反之則視此任期終止，開始新的任期並開始下一場選舉。

選舉是由候選人發動的。當領袖的心跳逾時的時候，追隨者就會把自己的任期編號（{{langx|en|term counter}}）加一、宣告競選、投自己一票、並向其他伺服器拉票。每個伺服器在每個任期只會投一票，固定投給最早拉票的伺服器。

如果候選人收到其他候選人的拉票、而且拉票的任期編號不小於自己的任期編號，就會自認落選，成為追隨者，並認定來拉票的候選人為領袖。如果有候選人收到過半的選票就當選為新的領袖。如果逾時仍沒有選出新領袖，此任期自動終止，開始新的任期並開始下一場選舉。

Raft每個伺服器的逾時期限是隨機的，這降低伺服務同時競選的機率，也降低因兩個競選人得票都不過半而選舉失敗的機率。

=== 記錄複寫 ===

記錄複寫的責任在領袖身上。

整個叢集有個複寫的狀態機（{{langx|en|state machine}}），可執行外來的指令。領袖接收指令，將之寫入自己記錄中的新指令部分，然後把指令轉發給追隨者。如果有追隨者沒反應，領袖會不斷重發指令、直到每個追隨者都成功將新指令寫入記錄為止。

當領袖收到過半追隨者確認寫入的訊息，就會把指令視為已儲存（{{langx|en|committed}}）。當追隨者發現指令狀態變成已儲存，就會在其狀態機上執行該指令。

當領袖當機時，領袖的某些新指令可能還沒複寫到叢集整體，造成叢集的記錄處於不一致的狀態。新領袖會擔起重返一致的責任，讓每個追隨者的記錄都和它的一致，做法是：和每個追隨者比對記錄，找出兩者一致的最後一筆指令，刪除追隨者之後的指令，把自己之後的指令拷貝給追隨者。這個機制完成時，每個伺服器的記錄就會一致。

=== 安全性 ===

==== Raft的安全性規則 ====

Raft保證以下的安全性：
* '''選舉安全性'''：每個任期最多只能選出一個領袖。
* '''領袖附加性'''：領袖只會把新指令附加（{{langx|en|append}}）在記錄尾端，不會覆寫或刪除已有指令。
* '''記錄符合性'''：如果某個指令在兩個記錄中的任期和指令序號一樣，則保證序號較小的指令也完全一樣。
* '''領袖完整性'''：如果某個指令在某個任期中儲存成功，則保證存在於領袖該任期之後的記錄中。
* '''狀態機安全性'''：如果某伺服器在其狀態機上執行了某個指令，其他伺服器保證不會在同個狀態上執行不同的指令。

前四項保證的原因詳見上述演算法，狀態機安全性則藉由下述選舉流程的限制所達到。

==== 追隨者當機 ====

當某台追隨者當機時，所有給它的轉發指令和拉票的訊息都會因沒有回應而失敗，此時發送端會持續重送。當這台追隨者開機重新加入叢集，就會收到這些訊息，追隨者會重新回應，如果轉發的指令已經寫入，不會重覆寫入。

==== 領袖當機 ====

領袖當機或斷線時，每個已儲存指令必定已經寫入到過半的伺服器中，此時選舉流程會讓記錄最完整的伺服器勝選。其中一個因素是Raft候選人拉票時會揭露自己記錄最新一筆的資訊，如果伺服器自己的記錄比較新，就不會投票給候選人。

==== 逾時期限和可用性 ====

因為Raft啟動選舉是基於逾時，使得逾時期限的選擇至為關鍵。若遵守演算法的時限需求

<blockquote>''廣播時間 << 逾時期限 << 平均故障間隔''</blockquote>

就能達到穩定性。這三個時間定義如下：
* ''廣播時間'' 是單一伺服器發送訊息給叢集中每台伺服器並得到回應的平均時間，需要測量得到。
* ''逾時期限'' 是發動選舉的逾時期限，由部署Raft叢集的人選定。
* ''平均故障間隔'' 是伺服器發生故障之間的平均時間，可以測量或估計得到。

''廣播時間''典型是 0.5ms 到 20ms，''平均故障間隔''通常是用週或月來計算的，所以可以將''逾時期限''設在 10ms 到 500ms。

== 參考文獻 ==
{{Reflist|2}}

== 相關連結 ==
* [[Paxos算法]]
* [[分布式计算]]

== 外部連結 ==
* {{Official|https://raft.github.io/}} {{en}}

[[Category:分散式演算法]]
[[Category:容错计算机系统]]

Raft - 版本历史

imported>Yumeto：​使用DisamAssist清理消歧義連結：Go（改連結至Go語言）。

imported>Yumeto：使用DisamAssist清理消歧義連結：Go（改連結至Go語言）。