الگوریتمهای اجماع توزیعشده: درک عمیق Raft برای هماهنگی سرورها

مسئله اجماع در سیستمهای توزیعشده: چگونه از سروری که کرش میکند یک کلِ جاودانه بسازیم؟

در سیستمهای توزیعشده حیاتی مانند etcd (مغز متفکر Kubernetes)، CockroachDB، TiKV و HashiCorp Consul، دادهها باید روی چندین سرور فیزیکی تکثیر شوند تا در صورت سوختن دیسک یا قطع کابل شبکه یک دیتاسنتر، سیستم بدون از دست دادن داده به کار خود ادامه دهد. الگوریتم Raft که توسط Diego Ongaro و John Ousterhout به عنوان جایگزینی قابل درک برای الگوریتم پیچیده Paxos طراحی شد، مسئله اجماع را بر پایه ماشین حالت تکثیرشده (Replicated State Machine) حل میکند: اگر تمام نودها یک دنباله کاملاً یکسان و مرتب از دستورات (Replicated Log) را به ترتیب یکسان اجرا کنند، وضعیت نهایی دیتابیس در تمام سرورها ۱۰۰ درصد یکسان خواهد بود.

الگوریتم Raft کل مسئله اجماع را به سه زیرمسئله مستقل تفکیک میکند:

• ۱. انتخابات لیدر (Leader Election): در هر دوره زمانی منطقی، حداکثر یک نود به عنوان فرمانده کل کلاستر انتخاب میشود.
• ۲. تکثیر گزارش رویدادها (Log Replication): لیدر دستورات کلاینت را دریافت کرده، در لاگ خود مینویسد و به سایر نودها ارسال میکند.
• ۳. ایمنی (Safety): تضمین ریاضی اینکه تحت هیچ شرایطی (تأخیر شبکه، ریاستارت شدن نودها یا پارتیشن شدن شبکه)، دو نود در یک ایندکس یکسان از لاگ، دو دستور متفاوت را Commit نکنند.

ساعت منطقی (CurrentTerm) و مکانیسم انتخابات بدون Split Vote

در یک کلاستر توزیعشده، ساعت فیزیکی سرورها (NTP) میتواند دچار انحراف (Clock Skew) شود؛ بنابراین Raft زمان را به دورههای شمارندهای اکیداً صعودی به نام Term تقسیم میکند. هر سرور در هر لحظه در یکی از سه وضعیت Follower، Candidate یا Leader قرار دارد:

• تمام نودها کار خود را به عنوان Follower آغاز میکنند و منتظر پیام ضربان قلب (Heartbeat در قالب AppendEntries خالی) از سمت لیدر میمانند.
• اگر یک Follower تا پایان بازه Election Timeout هیچ پیامی دریافت نکند، فرض میکند لیدر مرده است؛ بنابراین currentTerm خود را یک واحد افزایش میدهد، وضعیت خود را به Candidate تغییر میدهد، به خودش رأی میدهد و درخواست RequestVote RPC را به تمام نودها میفرستد.
• برای جلوگیری از اینکه چند نود همزمان کاندیدا شوند و آرا بین آنها بشکند (Split Vote)، زمان انتظار هر نود در هر دوره به صورت تصادفی در بازه `[150ms, 300ms]` انتخاب میشود.

مهار پارتیشن شبکه (Split-Brain) و قید ایمنی انتخابات (Election Restriction)

فرض کنید یک کلاستر ۵ نودی داریم ($N=5$) که حد نصاب اکثریت (Quorum) در آن برابر با $\lfloor 5/2 \rfloor + 1 = 3$ نود است. اگر کابل شبکه بین دو دیتاسنتر قطع شود و لیدر قدیمی به همراه ۱ نود دیگر در یک طرف (۲ نود) و ۳ نود دیگر در طرف مقابل ایزوله شوند، چه اتفاقی میافتد؟

• در سمت ۳ نودی، پس از اتمام Election Timeout یک لیدر جدید در Term + 1 انتخاب میشود؛ زیرا به حد نصاب ۳ رأی دسترسی دارد.
• در سمت ۲ نودی، لیدر قدیمی هنوز فکر میکند لیدر است! اما هر دستوری که کلاینت به او بفرستد، هرگز نمیتواند تاییدیه ۳ نود (Quorum) را بگیرد و 따라서 هرگز Commit نمیشود. به محض وصل شدن مجدد شبکه، لیدر قدیمی عدد Term بالاترِ لیدر جدید را دیده، بلافاصله به وضعیت Follower تنزل پیدا میکند و لاگهای تاییدنشدهاش را دور میریزد.

چرا کاندیدای دارای لاگ قدیمی هرگز برنده نمیشود؟

برخلاف سیستمهای قدیمی که پس از انتخاب لیدر سعی میکردند لاگها را ادغام کنند، در Raft جریان داده صرفاً یکطرفه (از Leader به Follower) است. برای اینکه لیدر جدید هیچ داده Commitشدهای را پاک نکند، در مرحله رأیگیری یک شرط سختگیرانه اعمال میشود: یک Follower تنها زمانی به کاندیدا رأی میدهد که لاگِ کاندیدا حداقل به اندازه لاگِ خودِ آن Follower بهروز باشد (مقایسه ابتدا بر اساس lastLogTerm و در صورت تساوی بر اساس طول لاگ lastLogIndex). از آنجا که هر دو اکثریت (Quorum) در یک کلاستر حداقل در یک نود مشترک همپوشانی دارند، نودی که انتخاب میشود تضمینی ۱۰۰ درصدی دارد که حاوی تمام رکوردهای Commitشده قبلی است!

چالش خواندن Stale Read و تضمین Linearizability با تکنیک ReadIndex

بسیاری از مهندسان تصور میکنند که اگر درخواستهای خواندن (GET) را به نود Leader بفرستند، همیشه جدیدترین داده (Linearizable Read) را دریافت میکنند. این تصور اشتباه و خطرناک است! همانطور که در سناریوی Split-Brain دیدیم، ممکن است لیدر فعلی به دلیل پارتیشن شبکه در اقلیت افتاده باشد و در سمت دیگر شبکه لیدر جدیدی انتخاب شده و مقادیر جدیدی نوشته باشد، اما لیدر ایزولهشده هنوز خبر نداشته باشد!

تحمیل کردن یک دور کامل نوشتن در لاگ دیسک برای هر درخواستِ خواندن، سرعت سیستم را نابود میکند. راهحل استاندارد در etcd و TiKV، پروتکل ReadIndex است:

• ۱. هنگام دریافت درخواست خواندن، لیدر ایندکس فعلی آخرین دستور تاییدشده خود (commitIndex) را به عنوان ReadIndex ثبت میکند.
• ۲. لیدر یک دور پیام سبک Heartbeat (بدون نوشتن روی دیسک) به نودها میفرستد تا مطمئن شود که هنوز اکثریت کلاستر او را به عنوان لیدر قبول دارند و لیدر جدیدی در کار نیست.
• ۳. به محض دریافت تاییدیه اکثریت و رسیدن ماشین حالت محلی (lastApplied >= ReadIndex)، مقدار را از حافظه خوانده و با تضمین ۱۰۰ درصدی Linearizability به کلاینت برمیگرداند.

پیادهسازی هسته ماشین حالت و قوانین ایمنی Raft در پایتون

در کد زیر، منطق دقیق و دترمنیستیک نود Raft شامل بررسی شرایط امنیتی RequestVote (مقایسه دوگانه Term و Index لاگ) و AppendEntries (تضمین ویژگی Log Matching Property) پیادهسازی شده است:

from dataclasses import dataclass
from enum import Enum
from typing import List, Optional, Tuple

class NodeRole(Enum):
    FOLLOWER = 'FOLLOWER'
    CANDIDATE = 'CANDIDATE'
    LEADER = 'LEADER'

@dataclass(frozen=True)
class LogEntry:
    term: int
    index: int
    command: str

class RaftConsensusStateMachine:
    """
    Deterministic core of the Raft Consensus Algorithm implementing
    Election Safety, Log Matching Property, and Quorum Commit rules.
    """
    def __init__(self, node_id: str, peers: List[str]):
        self.node_id = node_id
        self.peers = peers
        self.role = NodeRole.FOLLOWER

        # Persistent state on all servers (updated before responding to RPCs)
        self.current_term: int = 0
        self.voted_for: Optional[str] = None
        self.log: List[LogEntry] = [LogEntry(term=0, index=0, command='NOOP_ROOT')]

        # Volatile state on all servers
        self.commit_index: int = 0
        self.last_applied: int = 0

    @property
    def last_log_index(self) -> int:
        return self.log[-1].index

    @property
    def last_log_term(self) -> int:
        return self.log[-1].term

    def _step_down_if_higher_term(self, rpc_term: int) -> None:
        if rpc_term > self.current_term:
            self.current_term = rpc_term
            self.role = NodeRole.FOLLOWER
            self.voted_for = None

    def _is_candidate_log_up_to_date(self, cand_last_idx: int, cand_last_term: int) -> bool:
        """
        Raft Safety Section 5.4.1: Election Restriction.
        Compare last log terms first; if equal, higher index wins.
        """
        if cand_last_term != self.last_log_term:
            return cand_last_term > self.last_log_term
        return cand_last_idx >= self.last_log_index

    def handle_request_vote(
        self,
        term: int,
        candidate_id: str,
        last_log_index: int,
        last_log_term: int
    ) -> Tuple[int, bool]:
        self._step_down_if_higher_term(term)
        if term < self.current_term:
            return self.current_term, False

        can_vote = self.voted_for in (None, candidate_id)
        if can_vote and self._is_candidate_log_up_to_date(last_log_index, last_log_term):
            self.voted_for = candidate_id
            return self.current_term, True

        return self.current_term, False

    def handle_append_entries(
        self,
        term: int,
        leader_id: str,
        prev_log_index: int,
        prev_log_term: int,
        entries: List[LogEntry],
        leader_commit: int
    ) -> Tuple[int, bool]:
        self._step_down_if_higher_term(term)
        if term < self.current_term:
            return self.current_term, False

        self.role = NodeRole.FOLLOWER

        # Log Matching Property Check: must contain entry at prev_log_index matching prev_log_term
        if prev_log_index >= len(self.log) or self.log[prev_log_index].term != prev_log_term:
            return self.current_term, False

        # Conflict resolution: truncate conflicting uncommitted suffix and append new entries
        for entry in entries:
            if entry.index < len(self.log):
                if self.log[entry.index].term != entry.term:
                    self.log = self.log[:entry.index]
                    self.log.append(entry)
            else:
                self.log.append(entry)

        if leader_commit > self.commit_index:
            self.commit_index = min(leader_commit, self.last_log_index)

        return self.current_term, True