Raft — বোঝার জন্য ডিজাইন করা consensus

লক্ষ্য: শুধু “commit rule-এ current-term শর্ত লাগে” মুখস্থ না করে, সেই শর্ত না থাকলে ঠিক কী ভেঙে যায় সেটা code-এ ঘটিয়ে দেখা — majority-held পুরনো-term entry একটা নতুন election-এ কীভাবে মুছে যেতে পারে, আর current-term-entry-র পর কেন সেটা আর সম্ভব না।

# raft_figure8.py -- reproducing the Raft paper's "Figure 8" danger scenario
def append_entries(follower, prev_index, prev_term, entries):
    if prev_index > 0:
        if len(follower) < prev_index or follower[prev_index - 1][0] != prev_term:
            return False
    for offset, entry in enumerate(entries):
        idx = prev_index + 1 + offset
        if len(follower) >= idx and follower[idx - 1][0] != entry[0]:
            del follower[idx - 1:]
        if len(follower) < idx:
            follower.append(entry)
    return True

def is_up_to_date(candidate_log, voter_log):
    """Raft election restriction: candidate must be >= voter by
    (last-term, then last-index)."""
    c_term = candidate_log[-1][0] if candidate_log else 0
    v_term = voter_log[-1][0] if voter_log else 0
    if c_term != v_term:
        return c_term > v_term
    return len(candidate_log) >= len(voter_log)

def advance_commit_index(leader_log, match_indices, current_term, cluster_size, commit_index):
    """match_indices: dict follower -> highest index known replicated
    (leader counts itself as matching its own full log)."""
    majority = cluster_size // 2 + 1
    for n in range(len(leader_log), commit_index, -1):
        count = sum(1 for mi in match_indices.values() if mi >= n)
        if count >= majority and leader_log[n - 1][0] == current_term:
            return n
    return commit_index

def fmt(log):
    return "[" + " ".join(f"({t},{c})" for t, c in log) + "]"

S1, S2, S3, S4, S5 = ([(1, 'x1')] for _ in range(5))
CLUSTER = 5

print("=== (a) S1 leader, term=2 — partially replicates index2=(2,x2) ===")
append_entries(S1, 1, 1, [(2, 'x2')])
append_entries(S2, 1, 1, [(2, 'x2')])       # only S2 gets it before S1 crashes
for n, log in (("S1", S1), ("S2", S2), ("S3", S3), ("S4", S4), ("S5", S5)):
    print(f"  {n}: {fmt(log)}")

print("\n=== (b) S1 crashes. S5 wins election term=3 (votes: S3,S4,S5) ===")
for name, log in (("S3", S3), ("S4", S4)):
    assert is_up_to_date(S5, log), f"{name} should vote for S5"
print("  election-restriction check: S3, S4 both vote YES for S5 (tie on last-term=1, S5 log not shorter)")
append_entries(S5, 1, 1, [(3, 'x99')])      # S5 appends its own entry, only to itself, then crashes
print(f"  S5 (leader,term3): {fmt(S5)}")

print("\n=== (c) S5 crashes. S1 restarts, wins election term=4 (votes: S1,S2,S3) ===")
assert is_up_to_date(S1, S2) and is_up_to_date(S1, S3)
print("  election-restriction check: S2, S3 vote YES for S1 (S1's last term=2 >= theirs)")
ok = append_entries(S3, 1, 1, [(2, 'x2')])  # S1 (term4) replicates the old index2 entry to S3
print(f"  AppendEntries(S1->S3, prevIndex=1, prevTerm=1) accepted={ok}")
match = {"S1": 2, "S2": 2, "S3": 2}         # S1,S2,S3 now all hold index2
committed_wrong = advance_commit_index(S1, match, current_term=4, cluster_size=CLUSTER, commit_index=0)
print(f"  majority (S1,S2,S3) now hold index2 -- but S1.log[2].term=2 != currentTerm=4")
print(f"  advance_commit_index() -> commitIndex stays at {committed_wrong} (NOT advanced to 2)")

print("\n=== (d) DANGER PATH: if S1 crashes right here, and S5 restarts ===")
S2_d, S3_d, S4_d = list(S2), list(S3), list(S4)
assert is_up_to_date(S5, S2_d) and is_up_to_date(S5, S3_d) and is_up_to_date(S5, S4_d)
print("  election-restriction check: S2,S3,S4 vote YES for S5 (S5 last-term=3 > their last-term=2)")
print("  -> S5 wins election term=5 with votes {S2,S3,S4}. S5 now overwrites index2 cluster-wide:")
for name, log in (("S2", S2_d), ("S3", S3_d), ("S4", S4_d)):
    append_entries(log, 1, 1, [(3, 'x99')])
    print(f"    {name}: {fmt(log)}")
print("  the (2,x2) entry a majority held in (c) is GONE from S2 and S3.")
print("  had commitIndex been advanced by count-alone in (c), a committed entry would have vanished!")

print("\n=== (e) SAFE PATH: instead, S1 (term4) replicates its OWN entry before crashing ===")
S1e, S2e, S3e, S4e, S5e = list(S1), list(S2), list(S3), list(S4), list(S5)
append_entries(S1e, 2, 2, [(4, 'x7')])                 # leader appends its own term-4 entry
ok2 = append_entries(S2e, 2, 2, [(4, 'x7')])
ok3 = append_entries(S3e, 2, 2, [(4, 'x7')])
print(f"  AppendEntries(index3=(4,x7)) -> S2 accepted={ok2}, S3 accepted={ok3}")
match_e = {"S1": 3, "S2": 3, "S3": 3}
committed_e = advance_commit_index(S1e, match_e, current_term=4, cluster_size=CLUSTER, commit_index=0)
print(f"  advance_commit_index() -> commitIndex={committed_e} "
      f"(index3.term={S1e[2][0]} == currentTerm=4, majority reached)")
print(f"  Log Matching Property: S1,S2,S3 all match at (index=3,term=4)")
print(f"    -> prefixes identical too: S1[:3]==S2[:3]==S3[:3] : {S1e[:3] == S2e[:3] == S3e[:3]}")
print(f"    -> so index1 AND index2 are retroactively safe as well, as part of the committed prefix")

print("\n  now can S5 still steal the leadership for term=6?")
can_S2 = is_up_to_date(S5e, S2e)
can_S3 = is_up_to_date(S5e, S3e)
can_S4 = is_up_to_date(S5e, S4)
votes = 1 + sum([can_S2, can_S3, can_S4])   # S5 self-vote + whoever agrees
print(f"    S2 votes S5? {can_S2}   S3 votes S5? {can_S3}   S4 votes S5? {can_S4}")
print(f"    S5's best-case vote count = {votes} (needs {CLUSTER//2+1}) -> "
      f"{'could still win!' if votes >= CLUSTER//2+1 else 'cannot win — safe'}")

প্রত্যাশিত output (deterministic, hand-traced):

=== (a) S1 leader, term=2 — partially replicates index2=(2,x2) ===
  S1: [(1,x1) (2,x2)]
  S2: [(1,x1) (2,x2)]
  S3: [(1,x1)]
  S4: [(1,x1)]
  S5: [(1,x1)]

=== (b) S1 crashes. S5 wins election term=3 (votes: S3,S4,S5) ===
  election-restriction check: S3, S4 both vote YES for S5 (tie on last-term=1, S5 log not shorter)
  S5 (leader,term3): [(1,x1) (3,x99)]

=== (c) S5 crashes. S1 restarts, wins election term=4 (votes: S1,S2,S3) ===
  election-restriction check: S2, S3 vote YES for S1 (S1's last term=2 >= theirs)
  AppendEntries(S1->S3, prevIndex=1, prevTerm=1) accepted=True
  majority (S1,S2,S3) now hold index2 -- but S1.log[2].term=2 != currentTerm=4
  advance_commit_index() -> commitIndex stays at 0 (NOT advanced to 2)

=== (d) DANGER PATH: if S1 crashes right here, and S5 restarts ===
  election-restriction check: S2,S3,S4 vote YES for S5 (S5 last-term=3 > their last-term=2)
  -> S5 wins election term=5 with votes {S2,S3,S4}. S5 now overwrites index2 cluster-wide:
    S2: [(1,x1) (3,x99)]
    S3: [(1,x1) (3,x99)]
    S4: [(1,x1) (3,x99)]
  the (2,x2) entry a majority held in (c) is GONE from S2 and S3.
  had commitIndex been advanced by count-alone in (c), a committed entry would have vanished!

=== (e) SAFE PATH: instead, S1 (term4) replicates its OWN entry before crashing ===
  AppendEntries(index3=(4,x7)) -> S2 accepted=True, S3 accepted=True
  advance_commit_index() -> commitIndex=3 (index3.term=4 == currentTerm=4, majority reached)
  Log Matching Property: S1,S2,S3 all match at (index=3,term=4)
    -> prefixes identical too: S1[:3]==S2[:3]==S3[:3] : True
    -> so index1 AND index2 are retroactively safe as well, as part of the committed prefix

  now can S5 still steal the leadership for term=6?
    S2 votes S5? False   S3 votes S5? False   S4 votes S5? True
    S5's best-case vote count = 2 (needs 3) -> cannot win — safe

তিনটা মুহূর্ত মন দিয়ে পড়ুন: (১) (c)-তে commitIndex stays at 0 — majority থাকা সত্ত্বেও, কারণ term-check ব্যর্থ; (২) (d)-তে ঠিক ওই entry পরে সত্যিই মুছে যায় — যদি (c)-তে commit ঘোষণা করা হতো, এই মুহূর্তে সেটা একটা committed-data-loss হতো; (৩) (e)-তে নিজের current-term entry replicate হওয়ার পরেই commitIndex=3 হয়, আর সেই একই মুহূর্তে S5-এর re-election সম্ভাবনা False/False/True — দুইজন ভোটার (S2, S3) এখন S5-কে প্রত্যাখ্যান করে, কারণ তাদের log এখন S5-এর চেয়ে বেশি up-to-date।

নিজে বাড়ান:

1. advance_commit_index-এ current-term শর্তটা মুছে ফেলুন, (c)-তেই commitIndex=2 হয়ে যায় দেখান — তারপর (d) চালিয়ে সেই “committed” entry-টা কীভাবে মুছে গেল সেটা assert দিয়ে ধরুন।
2. ৬ষ্ঠ server S6 যোগ করে cluster-size=6 করুন — majority=4; (e)-তে S1 কয়টা follower-কে replicate করলে commit হবে তা হিসাব করুন।
3. is_up_to_date-এ term-tie-এর ক্ষেত্রে length-tie-ও হলে (দুই log পুরোপুরি সমান) — voter কি vote দিতে বাধ্য, নাকি স্বাধীন? Raft-এর real semantics (once-per-term ভোট) দিয়ে যুক্তি দিন।