第3章: コンセンサス

分散システムでは、複数のサーバーがしばしば共有状態について合意する必要があります——誰がリーダーか、ログにどんなエントリがあるか、トランザクションをコミットすべきかどうか。障害が存在する中でこの合意に到達することがコンセンサスの問題です。コンセンサスは分散コンピューティングにおける最も基本的で困難な問題の一つであり、信頼性の高いプラネタリスケールコンピュータを構築するために正しく実装することが不可欠です。

困難さは分散システムの性質に起因します：メッセージは遅延、並べ替え、または消失する可能性があり、サーバーはクラッシュして再起動する可能性があり、グローバルクロックは存在しません。これらの課題にもかかわらず、コンセンサスアルゴリズムによりサーバーのグループ（アンサンブルまたはクラスタと呼ばれる）は一部のメンバーが障害を起こしても単一の一貫したユニットとして振る舞うことができます。

クォーラムベースのコンセンサス

コンセンサスに対する最も広く使用されるアプローチはクォーラムベースの投票です。重要な洞察は、サーバーの過半数が決定に同意すれば2つの過半数は少なくとも1つのサーバーで重なるということです。この重なりにより一部のサーバーが障害を起こしても決定が失われないことが保証されます。5台のサーバーシステムは2つの障害に耐えられ、3台のシステムは1つの障害に耐えられます。

私たちの実装はDiego OngaroとJohn Ousterhoutによって理解しやすさのために設計されたRaftコンセンサスアルゴリズムに従います。Raftはコンセンサス問題を3つの副問題に分割します：リーダー選挙（単一のリーダーを選ぶ）、ログレプリケーション（リーダーがフォロワーにエントリを配布する）、安全性（コミットされたエントリが失われないことを保証する）。

ロールと状態

consensus/src/member.rs アンサンブルのすべてのメンバーは任意の時点で3つのロールのいずれかにあります：リーダー、フォロワー、または候補者。リーダーはすべてのクライアントリクエストを処理しログエントリをフォロワーにレプリケートします。フォロワーはリーダーからのエントリを受動的に受け入れます。候補者は新しいリーダーになろうとしているフォロワーです。

#[derive(Copy, Clone, Debug, PartialEq)]
pub enum Role {
    Leader,
    Follower,
    Candidate,
}

pub struct Member {
    pub address: Arc<Mutex<String>>,
    pub role: Arc<Mutex<Role>>,
    pub peers: Arc<RwLock<Vec<String>>>,
    pub last_heartbeat: Arc<Mutex<Instant>>,
    pub term: Arc<Mutex<u64>>,
    pub log: Arc<RwLock<Vec<LogEntry>>>,
    pub commit_index: Arc<Mutex<usize>>,
    pub last_applied: Arc<Mutex<usize>>,
    pub state_machine: Arc<Mutex<dyn StateMachine + Send + Sync>>,
}

Member構造体にはコンセンサス参加者が必要とするすべての状態が含まれています。termは各選挙で単調増加する論理クロックで古いリーダーの検出を可能にします。logはすべてのメンバーが合意すべきエントリの順序付きシーケンスです。commit_indexはログのどこまでが過半数にレプリケートされたかを追跡し、last_appliedは状態マシンがどこまで消費したかを追跡します。

consensus/src/lib.rs 各ログエントリは作成されたtermのレコード、アクション識別子、ペイロードを記録します。StateMachineトレイトはアプリケーションがコミットされたエントリをどのように処理するかを定義します：

#[derive(Serializable, Deserializable, Clone, Debug)]
pub struct LogEntry {
    term: u64,
    action: u32,
    payload: String,
}

#[async_trait]
pub trait StateMachine {
    async fn apply(&mut self, action: u32, payload: String);
    async fn handle(&mut self, request: Request) -> Response;
}

メインループ

メンバーのライフサイクルは現在のロールに基づいて動作を切り替えるループです。起動時にメンバーは既存のリーダー（ディスカバリサービスで発見）に連絡してアンサンブルに参加するかリーダーが存在しない場合は最初のリーダーとして新しいアンサンブルを初期化します：

pub async fn run(&self) {
    self.join_ensemble().await;

    loop {
        let current_role = {
            let role_lock = self.role.lock().await;
            *role_lock
        };

        match current_role {
            Role::Follower => self.run_as_follower().await,
            Role::Leader => self.run_as_leader().await,
            Role::Candidate => self.become_candidate().await,
        }
    }
}

リーダー選挙

consensus/src/follower.rs フォロワーはリーダーからのハートビートを監視します。ランダム化されたタイムアウト（1500〜3000ミリ秒）内にハートビートが届かない場合フォロワーはリーダーが障害を起こしたと判断し選挙を開始するために候補者ロールに移行します：

pub async fn run_as_follower(&self) {
    loop {
        let timeout = rand::thread_rng().gen_range(1500..3000);
        tokio::time::sleep(Duration::from_millis(timeout)).await;

        let last_heartbeat = *self.last_heartbeat.lock().await;
        if last_heartbeat.elapsed() >= Duration::from_millis(timeout as u64) {
            warn!("Too long since last heartbeat from leader");
            self.become_candidate().await;
            break;
        }
    }
}

ランダム化されたタイムアウトは重要です。すべてのフォロワーが同じタイムアウトを使用すると全員が同時に選挙を開始して投票が分散しどの候補者も勝てなくなります。ランダム化により、ほとんどの場合単一のフォロワーが最初にタイムアウトし他のフォロワーが開始する前に勝利します。

consensus/src/candidate.rs 候補者はtermをインクリメントし自分自身に投票しすべてのピアに投票を要求します。過半数から投票を受け取ればリーダーになります：

pub async fn become_candidate(&self) {
    let mut term = self.term.lock().await;
    *term += 1;
    drop(term);

    *self.role.lock().await = Role::Candidate;
    self.start_election().await;
}

async fn start_election(&self) {
    let mut votes = 1; // Start with 1 vote for self
    let term = *self.term.lock().await;
    let needed_votes = (self.peers.read().await.len() / 2) + 1;

    let peers = self.peers.read().await.clone();
    for peer in peers.iter() {
        if self.request_vote(peer, term).await {
            votes += 1;
        }
    }

    if *self.role.lock().await != Role::Candidate {
        return; // Role changed during election
    }

    if votes >= needed_votes {
        *self.role.lock().await = Role::Leader;
    }
}

過半数要件（(peers.len() / 2) + 1）はクォーラムベースコンセンサスの核心です。5メンバーのアンサンブルでは3票が必要です。これにより2つの同時選挙が両方とも成功することは不可能です。

設計の議論

Raftのようなコンセンサスアルゴリズムは強い保証を提供します：エントリがコミットされたらサーバーの少数派が障害を起こしても失われません。これらの保証にはコストが伴います。すべての書き込みは確認前に過半数のサーバーにレプリケートされる必要がありレイテンシーが追加されます。読み取り操作も古い読み取りを防ぐためにリニアライズされる必要があります。

タイムアウトの選択はシステム動作にとって重要です。選挙タイムアウトは通常のハートビート遅延が不必要な選挙をトリガーしないほど長く実際のリーダー障害が迅速に検出されるほど短い必要があります。私たちの実装は選挙に1500〜3000ミリ秒、ハートビートに1500ミリ秒を使用しローカルネットワークに適しています。

StateMachineトレイトはコンセンサスプロトコルとアプリケーションロジックのクリーンな分離を提供します。状態の変更を(action, payload)ペアのシーケンスとして表現できるすべてのアプリケーションがこのコンセンサス実装上に構築できます。本番環境ではetcd、ZooKeeper、Consulのようなコンセンサスベースのシステムが分散コーディネーションのバックボーンを形成します。