Raft Cluster Pre-Vote Protocol

Written early in the pluggable Raft cluster-bus work — the design was still forming. This is mainly a learning note while I tried to implement Raft Pre-Vote in Redis/Valkey Cluster V2. It has since merged; this is also a retrospective.

Original issue

This is Valkey’s attempt at the pre-vote problem in a pluggable Raft protocol — an interesting engineering piece.

First study §9.6 of Diego Ongaro’s PhD thesis:

*Preventing disruptions when a server rejoins the cluster One downside of Raft’s leader election algorithm is that a server that has been partitioned from the cluster is likely to cause a disruption when it regains connectivity. When a server is partitioned, it will not receive heartbeats. It will soon increment its term to start an election, although it won’t be able to collect enough votes to become leader. When the server regains connectivity sometime later, its larger term number will propagate to the rest of the cluster (either through the server’s RequestVote requests or through its AppendEntries response). This will force the cluster leader to step down, and a new election will have to take place to select a new leader. Fortunately, such events are likely to be rare, and each will only cause one leader to step down. If desired, Raft’s basic leader election algorithm can be extended with an additional phase to prevent such disruptions, forming the Pre-Vote algorithm. In the Pre-Vote algorithm, a candidate only increments its term if it first learns from a majority of the cluster that they would be willing to grant the candidate their votes (if the candidate’s log is sufficiently up-to-date, and the voters have not received heartbeats from a valid leader for at least a baseline election timeout). This was inspired by ZooKeeper’s algorithm, in which a server must receive a majority of votes before it calculates a new epoch and sends NewEpoch messages (however, in ZooKeeper servers do not solicit votes, other servers offer them). The Pre-Vote algorithm solves the issue of a partitioned server disrupting the cluster when it rejoins. While a server is partitioned, it won’t be able to increment its term, since it can’t receive permission from a majority of the cluster. Then, when it rejoins the cluster, it still won’t be able to increment its term, since the other servers will have been receiving regular heartbeats from the leader. Once the server receives a heartbeat from the leader itself, it will return to the follower state (in the same term). We recommend the Pre-Vote extension in deployments that would benefit from additional robustness. We also tested it in various leader election scenarios in AvailSim, and it does not appear to significantly harm election performance.* 

Below is a translation / walkthrough:

Background: preventing disruption when a server rejoins

#

One downside of Raft leader election: when a server that was partitioned away regains connectivity, it can disrupt the cluster.

While partitioned, the server receives no heartbeats. It soon increments its term and starts elections (no leader heartbeat → keep ++term, time out, re-elect), even though it cannot collect a majority.

Later, when connectivity returns, that larger term propagates (via RequestVote, or via AppendEntries responses).

After the disconnected node rejoins, consider two cases:

1. It sends RequestVote to other followers; they raise their term and stop answering the current leader.
2. Same via AppendEntries replies to the leader — the leader steps down.

This forces the current leader to step down, and a new election must choose a new leader.

You might think: even with a huge term, its log is stale — how much damage? But the code compares term first: if peer term is higher, raise your own term, then check log freshness. Result: your term goes up, you still reject the vote on log grounds → widespread term inflation, old leader forced down, new election, terms jump.

Logical clock is the first criterion — why not check log freshness first in RequestVote?

The thesis has these rules:

Figure 2 global rules (higher priority than RequestVote-local rules)

#

This rule does not distinguish RequestVote / AppendEntries, nor whether a vote was granted. It is iron law — but why?

If you refuse a vote without raising term, you break “old leader must be obsolete”

#

Suppose we allowed: log not fresh → return immediately, term unchanged.

Follower F：term = 5
过期 Leader L：term = 5（多数派其实已失联，但 L 自己不知道）
捣乱者 C：  term = 6，log 很旧

F receives C’s RequestVote: log stale → deny, term stays 5. L keeps heartbeating at term 5; F still accepts.

Looks better for availability, but conflicts with the thesis goals:

• Once any election signal at term 6 appears, all nodes should treat “epoch 6 has begun”; a term-5 leader is no longer legitimate.
• Safety proofs rely on term as a cluster-wide monotonic logical clock: a node that has seen term T never treats a leader with term < T as valid.

If some nodes rise to 6 while others stay at 5 due to “log-first deny”, you get term-view split, inconsistent AppendEntries / RequestVote behavior, and broken proof assumptions.

Simply: the global logical clock must come first.

Typical Go teaching code looks like:

// 我是follower,当有candidate想让我投票的时候，我该如何处理？
// 这个视角应该就是我看args,然后填reply即可
// 在相同任期下，你才能进行投票的操作
func (rf *Raft) RequestVote(args *RequestVoteArgs, reply *RequestVoteReply) {
	rf.mu.Lock()
	defer rf.mu.Unlock()

	// 任期比我更小，不能给你投票
	if args.Term < rf.currentTerm {
		reply.Term = rf.currentTerm
		reply.VoteGranted = false
		return
	}

	// 任期比我更大，我先升级一下自己
	if args.Term > rf.currentTerm {
		rf.currentState = follower
		rf.currentTerm = args.Term
		rf.votedFor = -1 // 清理一下本次term的投票

		rf.persist()
	}

	// 任期和我相同(包括刚升级结束的)
	// 我投票了，但是本来就没给你投
	if rf.votedFor != -1 && rf.votedFor != args.CandidateId {
		reply.Term = rf.currentTerm
		reply.VoteGranted = false
		return
	}

	// 处理log,是否够新,这里我们先看Term,然后看Log
	// 实际工程有预投票的实现，比较有意思，我们这里暂时不管
	if !rf.isLogUpToDate(args.LastLogIndex, int(args.LastLogTerm)) {
		reply.Term = rf.currentTerm
		reply.VoteGranted = false
		return
	}

	// ok
	rf.votedFor = args.CandidateId

	// 因为进行了一次投票所以需要持久化
	rf.persist()
	// 这次选票成功，也认为是一次压制
	rf.lastRPC = time.Now()
	reply.VoteGranted = true
	reply.Term = rf.currentTerm
}

Fortunately such events are rare, and each causes only one leader to step down. If desired, basic Raft election can add an extra phase to prevent this disruption — the Pre-Vote algorithm.

In Pre-Vote, a Candidate increments its term only after learning that a majority would grant it a vote (candidate log sufficiently fresh, and voters have not heard from a valid leader for at least one baseline election timeout — i.e. the leader is probably dead, otherwise why vote?).

That baseline timeout should not be randomized; a fixed value is best.

Inspired by ZooKeeper: a server must win a majority before computing a new Epoch and sending NewEpoch (though ZooKeeper servers do not solicit votes; others offer them).

Pre-Vote stops a partitioned server from disrupting the cluster on rejoin. While partitioned, lacking majority permission, it cannot raise its term.

Note: it cannot raise the term at all — not “raise but fail to affect others”.

On rejoin it still cannot raise term, because others keep receiving leader heartbeats. Once it hears a heartbeat from the leader itself, it returns to Follower (same term).

For deployments needing extra robustness, Pre-Vote is recommended.

AvailSim testing suggested it does not significantly hurt election performance (some cost, but small — whether to ship still needs evaluation).

After understanding the problem, look at how code is organized. Any Raft system needs answers to:

In this repo:

1. How are RPCs invoked?
2. Where are log / server / Raft member structs and role states defined?
3. Where are AppendEntries / RequestVote defined?
4. Where are election triggers and heartbeats?
5. Where is randomized timeout defined? etc.

Raft architecture analysis

#

How do we communicate?

#

Inside Redis/Valkey we do not use a stock RPC framework. Cluster bus TCP + custom binary header + text message (RPC is nothing magical here).

Here “RPC” = send/receive one bus message on a clusterLink:

Outbound:

Messages travel on port 16379.

业务逻辑 → wireNewMsg("AE"|"VOTE_REQ"|...) → wireFinishMsg → clusterRaftSendMsg
         → clusterLinkSendBlock → TCP 写出

Example:

// 比如在总线上发送一个sds消息,如果发送失败,就直接free sds
static void clusterRaftSendMsg(clusterLink *link, sds msg) {
    if (!link || !link->conn) {
        sdsfree(msg);
        return;
    }
    size_t len = sdslen(msg);
    clusterMsgSendBlock *block = clusterAllocMsgSendBlock(len);
    memcpy(block->data, msg, len);
    sdsfree(msg);
    clusterLinkSendBlock(link, block);
    clusterMsgSendBlockDecrRefCount(block);
    RAFT_STATE()->stats_bytes_sent += len;
}

Broadcast uses clusterRaftBroadcast / clusterRaftBroadcastAppendEntries, walking server.cluster->nodes and sending to each peer with a link.

Inbound:

The event loop reads TCP → clusterReadHandler, first the header, then checks memory, and once the full packet is in memory dispatches the handler.

1. Read at least RCVBUF_MIN_READ_LEN bytes
2. clusterCurrentBus->validateMessageHeader() — under Raft check "RAFT" magic + big-endian totlen
3. After the full packet: clusterCurrentBus->processMessage(link)
4. Raft path: clusterRaftProcessMessage, dispatch by first token to clusterRaftProcess* handlers

cluster_link.c:

        if (rcvbuflen >= RCVBUF_MIN_READ_LEN) {
            uint32_t totlen = clusterCurrentBus->validateMessageHeader(link->rcvbuf);
            if (totlen && rcvbuflen == totlen) {
	            // 分派给对应的方法进行处理
                if (clusterCurrentBus->processMessage(link)) {

Another path: When a follower receives certain client messages it forwards them to the leader.

e.g. writes?

How are structs defined?

#

Because this is a log-replicated state machine, how is the log defined:

// 存在哪些entry类型？
enum raftEntryType {
	RAFT_ENTRY_NODE_JOIN = 1, /* Add a node 增加一个节点 */ 
    RAFT_ENTRY_NODE_FORGET = 2, /* Remove a node 移除一个节点 */
    RAFT_ENTRY_SLOT_CHANGE = 3, /* Slot ownership 占有一个slot */
    RAFT_ENTRY_SET_REPLICA_OF = 4, /* Replication topology 复制拓扑 */
    RAFT_ENTRY_FAILOVER = 5, /* Failover (manual or automatic) 故障转移 */
    RAFT_ENTRY_NODE_INFO = 6, /* IP, port, hostname, etc. 一些节点信息 */
    RAFT_ENTRY_NODE_FAIL = 7, /* Node failure detected 挂了 */
    RAFT_ENTRY_NODE_RECOVER = 8, /* Node recovery detected 节点恢复 */
    ......
};


typedef struct {
    uint64_t term;  // 任期
    uint64_t index; // 日志索引
    uint8_t type; /* enum raftEntryType 当前条目的基本类型 */
    sds data; /* Space-separated command arguments 空格隔开的传参 */ 
}
raftLogEntry;

Roles for a Raft node:

enum raftRole {
    RAFT_ROLE_JOINER = 0, /* Stepped down singleton waiting to be added to a cluster */
    RAFT_ROLE_FOLLOWER = 1,
    RAFT_ROLE_CANDIDATE = 2,
    RAFT_ROLE_LEADER = 3,
};

JOINER is an intermediate state: singleton waiting to join a cluster.

Global / protocol state (persistent + leader-side volatile, etc.):

/* --------------------------------------------------------------------------
 * Protocol-specific state (stored in clusterState.protocol_data)
 * -------------------------------------------------------------------------- */

typedef struct {
    /* Persistent Raft state */
    uint64_t current_term;
    char voted_for[CLUSTER_NAMELEN]; /* All zeros = none */

    /* Volatile Raft state */
    enum raftRole role;
    uint64_t commit_index;
    uint64_t last_applied;

    /* Log */
    raftLogEntry ** log;
    uint64_t log_count;
    uint64_t log_alloc;

    /* Pending proposals waiting for commit. */
    list * pending_proposals; /* list of raftPendingProposal */

    /* Pending MEET callbacks waiting for NODE_JOIN commit. */
    list * pending_meets; /* CLUSTER MEET commands waiting for OK reply */
    list * deferred_meets; /* Inbound MEET messages deferred until size > 1 */

    /* NODE_INFO divergence detection. */
    sds my_last_committed_info;
    mstime_t last_node_info_check;

    /* Election */
    int votes_received;
    mstime_t election_timeout; /* Randomized timeout */
    mstime_t last_heartbeat; /* Last time we heard from leader */
    mstime_t last_repl_offsets_broadcast; /* Last REPL_OFFSETS broadcast */
    mstime_t joiner_since; /* When we became a joiner (for timeout) */

    /* Leader identity */
    char leader[CLUSTER_NAMELEN]; /* All zeros = unknown */

    /* Manual failover state (on the replica side) */
    mstime_t mf_end; /* Timeout for manual failover, 0 = not in progress */
    void * mf_ctx; /* blockedAsyncHandle for the CLUSTER FAILOVER client */
    void( * mf_callback)(void * ctx,
        const char * error);

    /* Automatic failover state (on the replica side) */
    mstime_t failover_time; /* When to propose FAILOVER based on rank, 0 = inactive */

    /* Message stats for CLUSTER INFO */
    long long stats_module_messages_sent;
    long long stats_module_messages_received;
    long long stats_publish_messages_sent;
    long long stats_publish_messages_received;
    uint64_t stats_bytes_sent;
    uint64_t stats_bytes_received;
    uint64_t stats_pubsub_bytes_sent;
    uint64_t stats_pubsub_bytes_received;
    uint64_t stats_module_bytes_sent;
    uint64_t stats_module_bytes_received;
}
clusterRaftState;

Familiar classic members.

Per-peer Raft state on each node:

typedef struct {
    uint64_t next_index;
    uint64_t match_index;   // 记录日志的复制进度 论文5.3
    mstime_t last_ack_time; /* Last time we received AE_ACK from this peer 用于NODE_FAIL的检测，超过固定时间认为就会下线 */
    unsigned int pending_fail_change: 1; /* NODE_FAIL or NODE_RECOVER in flight */
}
clusterNodeRaftData;

Here, one Valkey process is one server.

Note: AE means AppendEntries, not “ae event loop”.

AppendEntries / RequestVote

#

Where are those classic RPCs?

No separate .proto or function-pointer table; message types are string constants, dispatched with strcasecmp in clusterRaftProcessMessage (lines ~2026–2047):

AE message format:

 * Header line: AE <leader-id> <term> <prev-log-idx> <prev-log-term> <commit> <count>
 * Entry lines: <term> <type> <data>

String transport + parse. If count == 0, the message is a heartbeat.

Next we implement Pre-Vote. Principles are on the issue page; not repeated here.

Engineering details

#

When a candidate’s election times out

#

After a successful pre-vote, if the machine partitions while remaining Candidate, term inflation can still happen; on return it brings a high term as Candidate. So every formal election timeout should restart Pre-Vote.

Core of Pre-Vote

#

Pre-Vote’s core is the intermediate pre-candidate state: in that state current_term does not inflate unboundedly — the new term is not persisted.

stateDiagram-v2
    [*] --> Follower
    Follower --> PreCandidate: election timeout
    PreCandidate --> Candidate: majority PRE_VOTE grants
    PreCandidate --> Follower: pre-vote timeout (no quorum)
    Candidate --> Leader: majority VOTE grants
    Candidate --> Follower: election lost / higher term seen
    Leader --> Follower: step down (higher term)
    Follower --> Candidate: TIMEOUT_NOW (leader transfer)
    note right of PreCandidate
        term NOT incremented
    end note
    note right of Candidate
        term incremented
    end note

This is the mermaid we put on the PR page. Pre-Vote adds a PRE_CANDIDATE state that splits “probe whether we can win” from “really bump term and start a formal election”:

So under partition, repeated timeouts / failed pre-votes bounce PRE_CANDIDATE ↔ FOLLOWER, and term does not stack up from failed elections — exactly the §9.6 disruption Pre-Vote prevents.

Test scripts

#

Testing here has real depth — systemic test thinking we often lack, and especially important in the AI-coding era.

cd /home/ada/Project/valkey

# 确保二进制最新
make -C src valkey-server -j$(nproc)

# 单测（用不同 baseport 避免 21111 段冲突）
./runtest --single tests/unit/cluster/cluster-raft-prevote.tcl --baseport 21200
./runtest --single tests/unit/cluster/cluster-raft-proto.tcl --baseport 21300

1. Reusability
2. Effectiveness
3. Coverage If you want confidence in your code, learn how to test first.

Overall test architecture:

flowchart TB
    subgraph CI["CI 两条流水线"]
        A["test-cluster-raft job<br/>./runtest --cluster-raft --single tests/unit/cluster"]
        B["codecov job<br/>make lcov → 全量 runtest + gtest"]
    end

    subgraph BlackBox["黑盒测试层 (Tcl)"]
        P["cluster-raft-proto.tcl<br/>伪造 peer + TCP cluster bus"]
        E["cluster-raft-prevote.tcl<br/>3 真实节点 + SIGSTOP"]
        R["cluster-raft.tcl<br/>quorum freshness"]
    end

    subgraph Server["valkey-server 进程"]
        EP["epoll 读 cluster bus fd"]
        PARSE["RAFT 帧解析 → argv[]"]
        DISPATCH["clusterRaftProcessMsg()"]
        RAFT["cluster_raft.c pre-vote 状态机"]
    end

    A --> P & E & R
    B --> P & E & R
    P -->|"socket :port+10000"| EP
    E -->|"Redis 协议 CLUSTER INFO / pause_process"| RAFT
    EP --> PARSE --> DISPATCH --> RAFT

Protocol black box: deny PRE_VOTE while leader lease is active

#

sequenceDiagram
    participant Tcl as Tcl fake peer
    participant Bus as cluster bus :port+10000
    participant S as valkey-server (singleton leader)

    Tcl->>Bus: HELLO
    Bus->>Tcl: HI
    Note over S: leader=自己, last_heartbeat 新鲜<br/>lease 有效
    Tcl->>Bus: PRE_VOTE_REQ term+1 log 0/0
    Bus->>S: clusterRaftProcessPreVoteRequest()
    S->>S: clusterRaftCanGrantVote() → 0 (lease)
    Bus->>Tcl: PRE_VOTE current_term 0
    Note over S: current_term 不变

Protocol black box: grant PRE_VOTE without lease

#

sequenceDiagram
    participant Tcl1 as fake candidate1
    participant Tcl2 as fake candidate2
    participant S as valkey-server

    Tcl1->>S: VOTE_REQ term+1
    Note over S: step down → follower, leader=""
    Tcl2->>S: PRE_VOTE_REQ term+2 log 0/0
    S->>S: CanGrantVote() → 1 (无 leader + log OK)
    S->>Tcl2: PRE_VOTE term+2 1
    Note over S: current_term 仍为 vote_term，未 inflate

Protocol black box: reject stale candidate log

#

flowchart TD
    A["AE 写入 NODE_JOIN<br/>receiver last_log ≥ 1"] --> B["VOTE_REQ step-down<br/>清 leader lease"]
    B --> C["PRE_VOTE_REQ log 0/0<br/>(stale)"]
    C --> D["CanGrantVote: candidate_last_term < my_last_term"]
    D --> E["PRE_VOTE deny, term 不变"]

Protocol black box: pre-vote timeout, no quorum → no term inflate (critical)

#

sequenceDiagram
    participant FakeL as Tcl fake leader (inbound)
    participant S as valkey-server (follower)
    participant FakeP as Tcl listen (outbound link)

    FakeL->>S: AE term=2, NODE_JOIN x2
    Note over S: role=follower, term=2, cluster_size=2
    S->>FakeP: HELLO (outbound node->link)
    FakeP->>S: HI
    Note over FakeL: 停止 AE → last_heartbeat 过期
    S->>S: clusterRaftCron → clusterRaftStartPreVote()
    S->>FakeP: PRE_VOTE_REQ term=3
    Note over S: term 仍为 2 ✓
    Note over FakeP: 故意不回复 (无 quorum)
    S->>FakeP: PRE_VOTE_REQ term=3 (第二轮)
    FakeP->>S: PRE_VOTE 3 1 (grant)
    S->>S: pre_votes_received++ → quorum → StartElection()
    S->>FakeP: VOTE_REQ term=3
    Note over S: term=3 ✓

End-to-end black box: Leader failure → pre-vote → election

#

This is a normal election path.

sequenceDiagram
    participant N0 as Node0 (leader)
    participant N1 as Node1
    participant N2 as Node2

    Note over N0,N2: start_cluster 3, term=T
    N0->>N0: pause_process (SIGSTOP)
    Note over N0: 进程冻结，不处理 AE<br/>last_heartbeat 在 N1/N2 过期
    N1->>N2: PRE_VOTE_REQ (经真实 cluster bus)
    N2->>N1: PRE_VOTE grant
    N1->>N1: StartElection, term=T+1
    N1->>N2: VOTE_REQ ...
    Note over N1: 日志含 "Starting Raft pre-vote"

In practice, covering the critical paths is enough.