FLP 的含义:
- 异步网络: 消息延迟可以是任意长（但没有上限）
- 确定性算法: 给定相同输入，总是产生相同输出
- 结论: 必须放弃其中一个条件
  → 实际方案: 使用随机化算法 或 假设部分同步（有延迟上限但很大）

Raft 节点状态:
- Leader: 处理所有客户端请求
- Follower: 被动响应 Leader 的请求
- Candidate: 正在参与选举

选举流程:
1. 所有节点初始为 Follower
2. Follower 在超时时间内没收到 Leader 心跳 → 变为 Candidate
3. Candidate 发起投票（RequestVote RPC），term + 1
4. 获得多数票的 Candidate 成为新 Leader
5. 新 Leader 发送心跳，确立权威

随机超时:
- 每个节点的选举超时时间随机（如 150ms-300ms）
- 减少多个 Candidate 同时竞选的概率（分裂投票）
- 如果分裂投票 → 等待下一个超时 → 重试

安全性保证:
- 只有拥有最新日志的节点才能当选（投票请求中包含日志信息）
- 每个节点在一个 term 中只投一票（先收到先投）

日志复制流程:
1. Client 发送写请求到 Leader
2. Leader 将条目追加到本地日志
3. Leader 并行发送 AppendEntries RPC 到所有 Follower
4. Leader 等待多数确认（包括自己）
5. Leader 提交条目，应用到状态机
6. Leader 通知 Follower 提交

日志匹配性质:
- 如果两个日志在某个 index 有相同的 term，则它们在该 index 的条目相同
- 如果两个日志在某个 index 有相同的条目，则它们在所有 index < 该 index 的条目相同

日志一致性:
- 如果 Leader 提交了某个条目，则未来的 Leader 日志中一定包含该条目
- 通过投票限制（只有日志最新的节点才能当选）保证

Raft 的安全性（核心不变量）:
1. Election Safety: 一个 term 最多一个 Leader
2. Leader Append-Only: Leader 不会覆盖或删除日志，只追加
3. Log Matching: 同上 index+term → 同内容
4. Leader Completeness: 已提交的条目一定在未来 Leader 的日志中
5. State Machine Safety: 节点应用了某个条目后，不会有其他节点应用不同条目

关键机制:
- AppendEntries 一致性检查: Leader 发送 AppendEntries 时包含 prevLogIndex+prevLogTerm
  Follower 检查本地日志是否匹配 → 不匹配则拒绝
- 投票限制: RequestVote 中，Candidate 的日志必须至少和投票者一样新

Basic Paxos (单值共识):

Phase 1 - Prepare:
1. Proposer 发送 Prepare(n) 到 Acceptor (n 为提案编号)
2. Acceptor 收到后，如果 n 大于之前见过的任何编号:
   → 回复 Promise(n, prev_accepted_value, prev_accepted_number)
   → 承诺不再接受编号 < n 的提案

Phase 2 - Accept:
3. Proposer 收到多数 Promise 后:
   → 如果有 Acceptor 返回了已接受的值 → 使用该值
   → 否则 → 使用自己提议的值
   → 发送 Accept(n, value) 到 Acceptor
4. Acceptor 收到 Accept(n, value):
   → 如果没有收到编号 > n 的 Prepare → 接受该值

Multi-Paxos (多值共识):
- 固定一个 Leader (长期不变的 Proposer)
- 跳过 Phase 1 (因为 Leader 已经获得了长期承诺)
- 直接执行 Phase 2 → 效率接近 Raft

ZAB vs Raft:

相同点:
- 都使用 Leader 模型
- 都通过两阶段提交保证原子性
- 都保证已提交的数据不丢失

不同点:
- ZAB 支持 Leader 主动让位（Raft 只能通过新选举替换）
- ZAB 使用 epoch 而非 term（epoch 只在 Leader 变更时递增）
- ZAB 的恢复协议更复杂（需要保证之前 Leader 的已提交事务被所有 Follower 接收）
- ZAB 支持客户端从 Follower 读取（Raft 默认只从 Leader 读）

import random
import time
from enum import Enum

class NodeState(Enum):
    FOLLOWER = 0
    CANDIDATE = 1
    LEADER = 2

class RaftNode:
    def __init__(self, node_id, peers):
        self.node_id = node_id
        self.peers = peers
        self.state = NodeState.FOLLOWER
        self.current_term = 0
        self.voted_for = None
        self.log = []
        self.election_timeout = random.uniform(0.15, 0.3)
        self.last_heartbeat = time.time()
        self.votes_received = 0

    def tick(self):
        if self.state == NodeState.LEADER:
            self.send_heartbeats()
        elif self.state in (NodeState.FOLLOWER, NodeState.CANDIDATE):
            if time.time() - self.last_heartbeat > self.election_timeout:
                self.start_election()

    def start_election(self):
        self.state = NodeState.CANDIDATE
        self.current_term += 1
        self.voted_for = self.node_id
        self.votes_received = 1  # 投给自己
        self.election_timeout = random.uniform(0.15, 0.3)
        print(f"Node {self.node_id}: Starting election for term {self.current_term}")
        self.request_votes()

    def request_votes(self):
        for peer in self.peers:
            if peer.receive_vote_request(self.current_term, self.node_id, len(self.log)):
                self.votes_received += 1
        if self.votes_received > len(self.peers) // 2:
            self.become_leader()

    def become_leader(self):
        self.state = NodeState.LEADER
        print(f"Node {self.node_id}: Became leader for term {self.current_term}")
        self.send_heartbeats()

    def receive_vote_request(self, term, candidate_id, log_length):
        if term > self.current_term:
            self.current_term = term
            self.voted_for = None
            self.state = NodeState.FOLLOWER
        if term >= self.current_term and (self.voted_for is None or self.voted_for == candidate_id):
            if log_length >= len(self.log):
                self.voted_for = candidate_id
                self.last_heartbeat = time.time()
                return True
        return False

    def send_heartbeats(self):
        for peer in self.peers:
            peer.receive_heartbeat(self.current_term)

    def receive_heartbeat(self, term):
        if term >= self.current_term:
            self.current_term = term
            self.state = NodeState.FOLLOWER
            self.last_heartbeat = time.time()

# 模拟 5 节点集群
nodes = []
for i in range(5):
    node = RaftNode(i, [])
    nodes.append(node)
for node in nodes:
    node.peers = [n for n in nodes if n != node]

# 模拟选举
for node in nodes:
    node.tick()

# 输出:
# Node X: Starting election for term 1
# Node X: Became leader for term 1