raft-moonbit
Raft consensus algorithm implemented in MoonBit.
raft
consensus
distributed
replication
state-machine
moon add Lfan-ke/raft-moonbit@0.5.2
Download zipAuthor
Version
0.5.2
License
Apache-2.0
Repository
Last updated
20 days ago
Downloads
26
README#raft-moonbit
A production-grade Raft consensus library in MoonBit — a faithful, line-by-line port of etcd-io/raft.
▶ Live demo · Docs · API · Quickstart
The project home - a faithful MoonBit port of etcd's raft. Click through to the live, in-browser demo.
Raft keeps a cluster of nodes agreeing on the order of a command log even when nodes crash and the network drops, delays and reorders messages — the foundation of the replicated state machines behind systems such as etcd, TiKV and Consul. This library ports the Go etcd-io/raft (Apache-2.0) to MoonBit, carrying over its protocol core, storage model and test suite; see NOTICE for what is derived and what is new.
It ships two ways to drive one consensus core:
- a synchronous driver (run_election, replicate) that composes the RPC handlers into whole rounds — small and easy to read or embed; and
- a message-driven server (RaftNode) that speaks only in Messages through tick and step, so a real transport — or the bundled deterministic simulator — can drive it exactly the way etcd separates protocol logic from I/O.
#Install
moon add Lfan-ke/raft-moonbit#Quick example
// Drive a five-node cluster through the deterministic simulator.
let cluster = @raft.Cluster::new(["a", "b", "c", "d", "e"], seed=1)
let leader = cluster.run_until_leader(200) // elect a leader
let _ = cluster.propose(b"set x = 1") // replicate a command
let _ = cluster.run_until_committed(2, 200) // wait for commit
cluster.crash(leader.unwrap()) // inject a fault
let _ = cluster.run_until_leader(400) // a new leader takes over
assert_true(cluster.one_leader_per_term()) // safety still holds
assert_true(cluster.committed_agrees())Or run the bundled example — a five-node cluster elects, replicates, loses its leader and re-elects, printing the safety invariants at each step:
git clone https://github.com/Lfan-ke/raft-moonbit && cd raft-moonbit
moon run cmd/examplecluster of 5 nodes, seed 1
elected leader: b
committed 'set x = 1' on a majority
crashed the leader
new leader: c
one leader per term : true
committed prefixes agree : true
safety invariants hold : trueSource: cmd/example/main.mbt. The lower-level Node / RaftNode APIs are used directly in the tests — see raftnode_wbtest.mbt (message-driven) and cluster_wbtest.mbt (synchronous).
New to the library? examples/ is a guided tour in five short, runnable programs - from a first election up to a replicated key-value store:
moon run examples/00-helloworld # elect a leader
moon run examples/01-replicate # propose commands, confirm every node commits
moon run examples/02-fault-tolerance # crash, partition, drop packets - safety holds
moon run examples/03-operations # progress, leadership transfer, compaction
moon run examples/04-kvstore # a replicated key-value store on a StateMachine#Correctness
This is a line-by-line port, and it is verified as one. The porting census (PORTING.md) tracks every upstream Test* function and has no PARTIAL or TODO rows left — every test that does not depend on Go's runtime is ported assertion-for-assertion, with no simplified cases, no skipped table rows and no weakened assertions; each remaining N/A (a goroutine/channel shell, a benchmark, or a Go struct-memory-layout assert) states its MoonBit equivalent.
Three independent methods cross-check behaviour against etcd-io/raft@26647d5:
| Method | What it does |
|---|---|
| Transliteration | The 258 upstream tests ported over. 723 tests pass on the wasm / wasm-gc / js backends, with 100% line and branch coverage (3094/3094 points) and zero warnings under moon check --deny-warn — CI fails the build if either coverage number regresses. |
| Adversarial audit | An audit whose sole instruction is to falsify — to find implemented-but-unwired code: a field nobody fills, a parameter forever default, a method with no caller, an ADT variant never constructed. |
| Differential trace (difftest) | The same scenarios drive etcd's RawNode and this port, compared event-by-event with upstream pinned as a git submodule. Directory restructuring and idiomatic cleanup are held to zero trace drift. |
Together they surfaced 24 correctness defects in the consensus, log and storage layers — safety, liveness, behavioural and accounting — plus 2 default-configuration mismatches, each fixed under a red-then-green regression test that is still in the suite. Several defect classes were then made unrepresentable: narrowing a storage error to a single-variant type turned a whole class of mistaken catch into a compile error, and exhaustive matching flags any never-constructed variant at build time.
#Live demo — real consensus in your browser
#▶ https://lfan-ke.github.io/raft-moonbit/demo.html
Five nodes, five Web Workers. Each worker instantiates its own copy of this consensus core compiled to WebAssembly, ticks on its own wall-clock timer, and talks to peers only by postMessage. The main thread is the network — drop packets, add delay, split the cluster, isolate or crash the leader — and it holds no Raft state of its own. Elections race, messages reorder, nothing about the schedule is deterministic; a panel re-checks the safety invariants (one leader per term, committed prefixes agree) on every frame.
Click Split 2 | 3 and you can watch two nodes lead different terms at once - and Election Safety still holds, because two leaders only contradict Raft if they share a term, and the stale one cannot reach a majority, so it cannot commit. Heal the partition and it steps down.
It is not a JavaScript re-implementation — messages cross the boundary as flat integers, node state is a JSON string read straight out of the wasm module's linear memory, and every transition happens inside the same MoonBit code the tests exercise (worker_driver.mbt). Honest scope: five workers on one machine model concurrency, not a distributed deployment, and a restarted node catches up from the leader since the workers have no persistent storage.
moon build --target wasm --release # -> _build/wasm/release/build/demo/demo.wasm
cp _build/wasm/release/build/demo/demo.wasm docs/raft-moonbit.wasm
python3 -m http.server 8099 --directory docs # then open http://localhost:8099/Workers fetch the wasm, so a file:// URL will not work.
#Features
- Leader election with the Follower / Candidate / Leader roles and the up-to-date-log voting restriction (§5.2, §5.4.1).
- Pre-vote so a partitioned node cannot inflate the cluster term, plus randomized election timeouts and heartbeats off a per-node deterministic PRNG.
- Log replication through AppendEntries: log-matching, conflicting-suffix truncation, and majority commit within the current term (§5.3, §5.4.2). Replies carry a conflict_index hint for one-jump backoff and a reject_index that keeps a reordered rejection from driving a spurious back-off; per-follower Progress (probe / replicate / snapshot) drives repair, including from heartbeat acks.
- Snapshots and log compaction (§7): compact, the InstallSnapshot RPC, and automatic snapshot fallback for a follower whose next entry was already compacted away.
- Membership changes (§4, §6): single-server add/remove and full joint consensus with ConfChangeV2 and auto-leave — C(old,new) needs a majority of both halves, and the leader appends the leave entry itself once it commits. A committed change reconfigures the running node: quorums resize, a leader that removed itself steps down, and an in-flight transfer to a removed target aborts.
- Learners (§4.2.1): non-voting members that receive the log, never campaign and never count toward a quorum, with promotion to voter and learners_next-staged demotion across a joint change.
- Flow control: a sliding-window Inflights limit, a byte cap per batch (MaxSizePerMsg), and a bound on the uncommitted tail (MaxUncommittedEntriesSize).
- raftLog split into stable storage and an unstable tail with in-progress bookkeeping and byte-level pagination, so a caller knows exactly what to persist and what to apply.
- RawNode with Ready / Advance: ask whether there is work, take a batch (entries to persist, HardState/SoftState if changed, messages, committed entries, read states), do it, acknowledge — no threads, no async, exactly as etcd's contract describes.
- Persistence and crash recovery (§5.3): a HardState, an append-only write-ahead log (WalStore) with replay, and an etcd-style MemoryStorage engine. Storage reads report Compacted, Unavailable and SnapOutOfDate as distinct errors, so a caller can tell "send a snapshot" from "wait".
- Linearizable reads in both modes — ReadOnlySafe (fresh quorum round-trip) and lease-based — plus check-quorum, which steps a leader down when it loses a majority and makes followers refuse disruptive votes.
- Leadership transfer (TimeoutNow, §3.10): the target is caught up first, proposals are blocked mid-transfer, and it aborts on timeout, step-down or removal.
- Pluggable StateMachine, Transport, LogStore and RaftStorage traits, with a replicated key-value store as the worked example.
- Deterministic simulation harness (Cluster): a single-seed discrete-time network that drops, delays, reorders, partitions and crashes/restarts nodes, with built-in safety-invariant checks and a suite of scenario and chaos tests.
#Architecture
The code follows the upstream etcd-io/raft package layout so a reader can audit the port package-by-package. The root raft.mbt is a pure facade that re-exports the public surface, so consumers write @raft.X regardless of where a symbol lives.
| Package | Responsibility |
|---|---|
| quorum/ | Majority and joint-configuration vote counting |
| tracker/ | Per-follower Progress (Probe / Replicate / Snapshot) and the Inflights window |
| raftpb/ | On-the-wire types: Entry, Message, RPCs, HardState, Snapshot, ConfState, entry sizing |
| confchange/ | Configurations, joint consensus, ConfChange and the config Changer |
| storage/ | MemoryStorage, the write-ahead log, and the LogStore / RaftStorage traits |
| log/ | RaftLog, the unstable tail, term lookup and bounded slices |
| core/ | The consensus engine: RaftNode / Node step & dispatch, election, replication, snapshots, ReadIndex, leader lease, check-quorum, RawNode / Ready, Config, and the simulator |
| demo/ | The browser bridge: a flat wasm API over Cluster, one Web Worker per node |
#License
Apache-2.0. See LICENSE and NOTICE. A MoonBit port of etcd-io/raft (Copyright 2015 The etcd Authors); the protocol core, storage model and test suite are derived from it. What this port adds is the MoonBit data model — algebraic data types and exhaustive matching in place of Go structs and switches — a deterministic simulation harness with built-in safety-invariant checks, and a WebAssembly browser demo that runs each node in its own Web Worker.
The differential-testing harness lives on the difftest branch.
#AppendEntriesArgs
Arguments for the AppendEntries RPC (Raft §5.3), used by the leader both
to replicate log entries and, with an empty entries, as a heartbeat.
#AppendEntriesReply
Reply to an AppendEntries RPC. success is true when the follower's log
contained a matching entry at prev_log_index and the entries were stored.
On success match_index is the highest index the follower now agrees on, so
the leader can advance its progress without guessing. On rejection
conflict_index is a hint at where the two logs diverge, letting the leader
back off in one jump instead of decrementing nextIndex one entry at a time
(the optimization sketched in Raft §5.3).
#Changer
The Changer drives a configuration through single and joint changes. Each
public operation is transactional: on error the configuration is left
untouched (etcd's checkAndCopy semantics).
#ChangerConfig
The full configuration the Changer maintains: the incoming and outgoing voter
halves (outgoing non-empty iff joint), the learners, and the learners that
will become learners once a joint configuration is left (learners_next).
#Cluster
A deterministic, discrete-time cluster simulator. It owns a set of RaftNodes
and a network that can be told to drop, delay, reorder and partition traffic,
then advanced tick by tick. Because every random choice comes from a single
seeded PRNG, a whole run — elections, replication, failures and all — replays
identically, which is what makes it useful for finding consensus bugs and
pinning them down (the deterministic-simulation approach the task recommends).
#ConfChange
A configuration change carried by a ConfChange log entry: which server is
joining or leaving. It is serialized into the entry's command so every
server applies the same change at the same log position.
#ConfChangeTransition
How a ConfChangeV2 transitions the configuration (etcd's
ConfChangeTransition): Auto applies a batch simply when it safely can
(at most one voter changed) and otherwise enters an auto-leaving joint;
JointImplicit always enters joint and auto-leaves; JointExplicit always
enters joint and waits for an explicit leave.
#ConfChangeType
The kind of a single-server configuration change (Raft §6, §4.2.1).
#ConfChangeV2
A batch configuration change (etcd's ConfChangeV2): several single changes
applied atomically. An empty batch leaves joint consensus. Whether a non-empty
batch is applied simply or via a joint transition — and whether that joint
auto-leaves — is governed by transition (Raft §4.3, joint consensus).
#ConfDriver
A configuration driver: it walks a node's committed log and folds every
committed ConfChange entry into a Membership, tracking how far it has
applied so it never applies a change twice. This is the "configuration
state machine" that runs beside the application state machine.
#ConfState
A membership snapshot as carried by a Raft snapshot (etcd's ConfState).
#Config
The parameters to start a server, collected into one explicit value (etcd's
raft.Config). It gathers what RaftNode::new otherwise takes as a dozen
loose optional arguments, so a caller can build, inspect and validate a
configuration before constructing the node. RaftNode::new remains as a
convenience constructor for callers that just want defaults; from_config
is the validated path.
#ConfigError
Why a configuration was rejected — one variant per etcd Config.validate
branch that applies to this port. Raised by Config::validate /
RaftNode::from_config (etcd returns an error from the same branches).
#DemoReport
The outcome of the introductory demonstration cmd/example runs: a leader is
elected, one command is replicated, the leader is crashed, and a survivor
takes over. Kept as data rather than printed inline so the very run a reader
watches is the run a test asserts against.
#Entry
One command entry in the replicated log.
term is the leader's term — a monotonically increasing logical clock —
at the moment the entry was created. index is the entry's 1-based
position in the log; index 0 is the empty position before the first entry.
entry_type tells the apply loop whether command is an application
command or a membership change. command is the opaque payload handed to
the state machine (or membership decoder) once the entry is committed.
#EntryId
Uniquely identifies a log entry by the term that first appended it and its
index. There is only ever one leader per term and a leader never issues two
entries at the same index, so (term, index) pins an entry down. Mirrors
etcd's entryID.
#EntryType
What a log entry carries. A Normal entry holds an opaque state-machine
command; a ConfChange entry holds a serialized membership change that the
consensus layer applies to the cluster configuration once the entry is
committed (Raft §6). Keeping the kind on the entry lets the apply loop route
each committed entry to the right place.
#FullStatus
The full status of the server (etcd's Status): the basic status, a snapshot
of every tracked follower's replication progress — including the leader's own
entry, fully caught up — and the current configuration as a ConfState.
#HardState
The small piece of durable state Raft must flush before answering any RPC:
the current term, the vote cast in that term, and the commit index. etcd
calls this the HardState; persisting it is what lets a node rejoin without
violating the election-safety or state-machine-safety properties (§5.3).
#HeartbeatArgs
Arguments for the Heartbeat RPC (Raft §5.2): a leader's periodic liveness
beat. It carries no entries — only the leader's commit index (capped at
what the follower is known to hold) so a follower can advance its commit
index between AppendEntries. Modelling it as a distinct message (rather than
an empty AppendEntries) lets the leader treat a heartbeat acknowledgement as
pure liveness, separate from log-matching.
#HeartbeatReply
Reply to a Heartbeat RPC: the follower's term and the read-index context it
is acknowledging (echoed verbatim).
#Inflight
One in-flight AppendEntries message: the index of its last entry and the
total byte size of the entries it carries.
#Inflights
A sliding-window flow controller for the AppendEntries messages a leader has
sent to one follower but not yet had acknowledged. It caps both the number
of outstanding messages (size) and their total byte size (max_bytes),
which is what stops a leader from flooding a lagging follower. Callers check
full before sending, add on each send, and free_le on each ack.
#InstallSnapshotArgs
Arguments for the InstallSnapshot RPC (Raft §7). A leader sends this when a
follower has fallen so far behind that the entries it needs have already
been compacted away. The whole state-machine image up to last_index is
shipped in data; real deployments chunk it, which the offset/done pair
leaves room for.
#InstallSnapshotReply
Reply to an InstallSnapshot RPC. term lets a stale leader discover it has
been superseded.
#LogCompacted
The one way a RaftLog read can fail: the requested index predates the
snapshot baseline and has been compacted away. slice / entries /
must_check_out_of_bounds narrow the storage layer's four-variant
StorageError to this single mode at the boundary — a caller such as
all_entries then handles exactly the failure that can occur, and no wildcard
arm can silently swallow an Unavailable or contract-violating error (etcd
documents that raftLog.slice only ever returns ErrCompacted).
#LogLevel
A severity level, ordered from most to least verbose. Mirrors the five
levels etcd's Logger exposes; Panic additionally aborts.
#LogSlice
A contiguous, well-formed slice of a raft log considered under a specific
leader term. prev is the entry immediately before entries. Mirrors
etcd's logSlice, whose invariants a well-formed append must satisfy:
entries are contiguous after prev, entry terms never regress, and no entry
carries a term newer than the leader term.
#LogStore
Durable storage for a node's persistent state. A real deployment backs
this with a file or a database; the tests use an in-memory implementation.
Keeping it a trait decouples the consensus core from any particular I/O.
#Logger
A pluggable sink for the consensus core's diagnostics (etcd's raft.Logger).
Where etcd's Go interface exposes twelve printf-style methods (a Debug/
Debugf pair per level), a MoonBit caller formats the message with string
interpolation at the call site, so a single log(level, message) carries
every level and the LogLevel enum supplies the level distinction. Keeping
it a trait decouples the core from any particular logging backend, and the
no-op default (NopLogger) keeps a server that wants no logging
allocation-free.
#Membership
The set of servers that currently form the cluster. Raft changes membership
through the log so every server adopts each change at the same point in the
sequence (Raft §6). Two disciplines are supported: single-server changes,
where the old and new majorities always overlap; and joint consensus, where
the cluster passes through a transitional configuration C(old,new) that
needs a majority of both the old and the new voter sets to agree.
members is the incoming configuration C(new). outgoing holds the old
configuration C(old) and is non-empty only while joint is true.
#MemoryStorage
An in-memory RaftStorage. ents[0] is a sentinel whose index and term are
the snapshot baseline, so ents[i] always holds the entry at absolute index
ents[0].index + i. This mirrors etcd's MemoryStorage layout, which keeps
index arithmetic branch-free.
#Message
A routed message: a payload with the ids of the sender and intended
recipient. The step function consumes these and produces more of them; a
transport (real or simulated) is only responsible for delivery.
#Node
A single Raft node: its identity, current role, and the state it holds.
current_term, voted_for and log make up the state a real deployment
must persist to stable storage before replying to any RPC, so the node
recovers correctly after a crash. commit_index and last_applied are
volatile: they are safe to lose and are rebuilt after a restart.
#NopLogger
The default Logger: it discards every message (etcd defaults to a real
stderr logger, but a deterministic simulation and its tests want silence).
A deployment that wants diagnostics supplies its own Logger.
#NopTracer
The default Tracer: it discards every event (matching etcd's default
!with_tla build, where every trace* call is an empty function).
#Payload
The body of a message exchanged between nodes. A heartbeat is modelled as an
Append with no entries, so the same replication path carries both. Keeping
every request paired with its response in one enum lets a transport move
Raft traffic without knowing what any particular message means.
#Persisted
The persistent state a Raft node must save to stable storage before
responding to any RPC (Raft §5.3): the current term, the vote cast in that
term, and the log. It is exactly what a node reloads to recover after a
crash.
#Progress
The leader's view of one follower's replication progress. next_index is
the next log index to send; match_index is the highest index known to be
stored on the follower. recent_active records whether the follower has
answered since the last liveness sweep, which the read-index and lease paths
use to confirm the leader still commands a quorum.
#ProgressState
How the leader is currently replicating to one follower.
Probe sends one AppendEntries at a time until the follower's match point
is found; Replicate streams entries once the logs are known to agree; and
Snapshot means the follower is so far behind that the next thing it needs
has already been compacted, so a snapshot must be shipped first (etcd's
three progress states).
#ProgressStatus
A read-only view of one follower's replication progress, surfaced for status
and monitoring (etcd's tracker.Progress as exposed through Status and
WithProgress). It is a copied value, so reading it never disturbs the
running protocol.
#RaftLog
The raft log (etcd's raftLog): a MemoryStorage of durable entries with an
Unstable in-memory tail layered on top, plus the commit/apply cursors.
committed is the highest index known committed on a quorum; applying and
applied track how far the state machine has been told to apply and has
finished applying. applying_ents_size / max_applying_ents_size bound the
bytes of committed-but-unapplied entries handed out at once, so a burst of
commits cannot force an unbounded apply batch (byte-level pagination).
#RaftNode
A message-driven Raft server: the consensus core (Node) wrapped with
everything a real deployment needs to run it — the peer set and configuration,
per-follower replication progress, election and heartbeat timers with
randomized timeouts, pre-vote, and a deterministic PRNG so tests can replay a
run exactly. It communicates only through Messages: tick and step
return the messages to send, and a transport (real or simulated) delivers
them. This mirrors etcd's raft.Node/Ready split of logic from I/O.
#RaftStatus
A point-in-time snapshot of a server's observable state, for monitoring and
tests. It is a plain value copied out of the node, so reading it never
disturbs the running protocol.
#RaftStorage
Read access to a node's durable log, modelled on etcd's Storage interface.
The consensus core reads entries, terms and the snapshot back through this
trait, which lets the same core run over memory, a file or a database.
The index/term accessors raise StorageError so a compacted index is
reported distinctly from an unavailable one, exactly as etcd's Storage
contract requires.
#RawNode
The goroutine-free driver of a Raft server (etcd's RawNode). The core
RaftNode produces its output — messages to send, entries appended,
commits — as return values of tick/step/propose; RawNode batches
that output into the synchronous Ready/Advance cycle a real deployment runs:
take a Ready, persist its entries and hard state, send its messages, apply
its committed entries, then call advance.
It needs no language-level async: a Ready is a plain value and advance
a plain call. The unstable-vs-stable split that separates entries still to be
written (entries) from committed entries ready to apply
(committed_entries) is kept by a real RaftLog: its storage holds what
the application has persisted, its unstable tail holds what has not.
#ReadIndexResp
The leader's answer to a forwarded ReadIndex (etcd's MsgReadIndexResp): the
commit index the read is anchored at, echoed back with the caller's context to
the server that originated the read. Unlike the request it carries the
leader's term, so it is term-checked like any other reply.
#ReadOnlyOption
How a linearizable read is confirmed (etcd's ReadOnlyOption).
Safe confirms every read with a fresh heartbeat quorum, so it holds even
under unbounded clock drift — etcd's default and recommended setting.
LeaseBased trusts the leader's election lease instead, saving the round
trip at the cost of depending on bounded clock drift; etcd requires
check-quorum to be on when it is selected.
#ReadState
A linearizable-read ticket (etcd's ReadState): the commit index a read must
wait for the state machine to reach, tagged with the caller's opaque context
so a returned index can be matched back to the request that asked for it.
#Ready
The batch of outstanding work the application must handle for one turn of the
state machine (etcd's Ready). The contract is synchronous, not a coroutine:
the caller persists entries/hard_state/snapshot, sends messages,
applies committed_entries, serves read_states, then calls advance.
A field carries work only when there is some: soft_state and hard_state
are Some only on change (expressed as Option, not a sentinel), and the
arrays are empty when idle. must_sync says whether the persist must be a
durable (fsync) write or may be lazily flushed.
#RequestVoteArgs
Arguments for the RequestVote RPC (Raft §5.2), sent by a candidate to
gather votes for the term it is standing in.
#RequestVoteReply
Reply to a RequestVote RPC. term lets a stale candidate discover it has
been superseded; vote_granted is true when the vote was given.
#Role
The role a node plays in the Raft protocol at a given moment.
A node starts as a Follower. On election timeout it becomes a
Candidate and stands for election; if it wins a majority it becomes
the Leader for that term.
#Snapshot
A point-in-time snapshot of the state machine that stands in for the log
prefix up to and including last_index. Raft uses snapshots to bound log
growth and to bring a badly lagging follower up to date in one shot (§7).
#SoftState
The volatile part of a server's state, useful for logging and monitoring but
never persisted (etcd's SoftState). lead is None when no leader is
known. A Ready carries a SoftState only when it has changed, which is why
the leader/role transition is the trigger rather than the current value.
#StateMachine
A replicated state machine: it consumes committed commands in log order.
Implementors decide what each command means. Keeping this pluggable lets the
same consensus core drive a key-value store, a config registry or anything
else.
#StorageAppend
A directive to the local append thread: write these unstable entries (and the
hard state / snapshot, if present) to stable storage, then return resp
(etcd's MsgStorageAppend).
#StorageAppendResp
The acknowledgement a storage thread sends back once a StorageAppend has
been made durable (etcd's MsgStorageAppendResp). It attests the last log
(index, log_term) written and the term the raft node held when the
directive was issued — the two together defeat the ABA race: a response that
arrives after the term has moved on, or after the unstable log at that index
was overwritten, is ignored rather than mistaken for an ack of the new log.
#StorageApply
A directive to the local apply thread: apply these committed entries to the
state machine, then return resp (etcd's MsgStorageApply).
#StorageApplyResp
The acknowledgement a state machine sends back once a StorageApply batch has
been applied (etcd's MsgStorageApplyResp). It carries the applied entries so
the raft node can advance its applied cursor and release their quota; committed
entries are term-independent, so no ABA guard is needed.
#StorageError
The failure modes a RaftStorage can report, one variant per distinguishable
condition so a caller can tell "this index is gone forever" apart from "this
index has not arrived yet" — a distinction etcd draws with distinct sentinel
errors and one the consensus core depends on to decide between sending a
snapshot and simply waiting.
#TraceEvent
One observable transition of the consensus core, surfaced to an external
tracer. These mirror the events etcd's state_trace.go records for its TLA+
conformance harness (traceBecome*, traceCommit, traceReplicate,
trace{Send,Receive}Message, traceConfChangeEvent, traceInitState).
etcd guards the machinery behind a with_tla build tag so a normal build
compiles the no-op variant (state_trace_nop.go); the equivalent here is
that the default NopTracer erases to nothing.
#Tracer
A pluggable observer of the core's state transitions (etcd's TraceLogger).
A single dispatch method mirrors etcd's one-event-at-a-time trace stream;
wrappers below name the individual events. The default NopTracer discards
everything, so an untraced server pays nothing.
#Transport
Pluggable transport for delivering Raft RPCs to a peer, addressed by node
id. A real cluster implements this over TCP, HTTP or gRPC; an in-process
cluster can call the handlers directly. Keeping it a trait decouples the
consensus core from any particular networking stack.
#Unstable
The in-memory tail of the log that has not yet been written to Storage
(etcd's unstable). It holds newly appended entries and, optionally, a
snapshot waiting to be applied, until they are handed to a Ready and their
writes are confirmed. entries[i] sits at absolute log index i + offset.
offset_in_progress (exclusive, >= offset) marks how far the entries have
begun being written; snapshot_in_progress says the snapshot write has
begun. Following etcd, the "in progress" cursors are what let the same
entries be exposed once for persistence and then withheld until stabilized.
The snapshot is an Option rather than a sentinel — its absence is a real
type state, not an index-0 magic value.
#VoteState
The outcome of counting votes against a configuration: still pending (no
majority either way), won (a majority granted), or lost (a majority denied).
#WalRecord
One record in the write-ahead log. A real Raft node appends these to a file
(fsync'd before it replies to any RPC) and replays them in order after a
crash to rebuild exactly the state it had promised (Raft §5.3, §7). A
WalSnapshot marks a compaction baseline; the WalEntry records after it
carry the log tail; WalHardState records the term/vote/commit at the time.
#WalStore
Durable, append-only write-ahead log. Implemented over a file in production;
the in-memory MemWal in the tests is used for tests and single-process
runs.
#committed_index
The committed index of a (possibly joint) configuration. cfg is the
incoming half and cfgj the outgoing half; an empty half is the zero
quorum. A joint configuration can only commit an index that both halves'
majorities agree on, so the result is the smaller of the two (Raft §6).
#demo_report_lines
Render a [DemoReport] as the exact lines cmd/example prints, stopping at
whichever step the run failed to reach.
Parameters:
- report : the outcome to render.
Returns the human-readable transcript, one entry per line.
#demo_run
fn demo_run(ids : Array[String], seed : UInt64, elect_ticks : Int, commit_ticks : Int, reelect_ticks : Int) -> DemoReportRun the introductory simulation and record what happened at each step.
Parameters:
- ids : the servers to simulate.
- seed : fixes the deterministic run.
- elect_ticks : tick budget for the first election.
- commit_ticks : tick budget for committing the first command.
- reelect_ticks : tick budget for the re-election after the crash.
Returns a DemoReport naming the elected leader, whether the command
committed, the successor once the leader is crashed, and the safety
invariants that must survive the succession.
#describe
A multi-line ASCII bar chart of each voter's acknowledged index (etcd's
MajorityConfig.Describe), longest bar for the highest index. Diagnostics
only — it has no bearing on consensus, but makes a quorum's commit state
legible in a dump.
#describe_conf_state
A concise description of a ConfState (etcd's DescribeConfState).
#describe_entries
Each entry described, one per line (etcd's DescribeEntries).
#describe_entry
A concise, human-readable description of an entry for debugging:
term/index Type payload. format renders the payload; when it is None
the default Go %q-style quoting is used. Mirrors etcd's DescribeEntry.
#describe_hard_state
A concise description of a HardState for debugging (etcd's
DescribeHardState): Term:N [Vote:v ]Commit:N, the vote shown only when a
vote was cast.
#describe_snapshot
A concise description of a Snapshot (etcd's DescribeSnapshot).
#entry_encoding_size
The protobuf wire size of one entry, following etcd's proto.Size: each
non-zero field costs a tag byte plus its varint/length-delimited encoding.
Only the byte total matters — it is what limit_size and Storage.Entries
budget against.
#ents_size
The total encoding size of a run of entries.
#hard_state_equal
Whether two hard states are equal in all three durable fields — term, vote,
and commit (etcd's isHardStateEqual). This is the test that keeps a Ready
from carrying a redundant HardState when nothing durable has moved.
#limit_size
The longest prefix of entries whose total encoding size does not exceed
max_size. Always returns at least one entry when the input is non-empty —
so a single oversized entry is still returned — matching etcd's limitSize.
#must_sync
Whether a synchronous durable write is required before replying to any RPC
(etcd's MustSync). The persistent state on every server — currentTerm,
votedFor, and the log — must be flushed when new entries are appended or the
term or vote changed; a bare commit-index bump may be flushed lazily (§5).
#no_limit
let no_limit : UInt64The sentinel used for an unbounded size cap: no entries/slice request is
ever limited by size. Mirrors etcd's noLimit = math.MaxUint64.
#payload_size
The size of an entry's payload: its command bytes only, independent of term
and index. Empty-payload entries (like the no-op a new leader appends) are
zero size, so they do not count against the uncommitted-log quota. Mirrors
etcd's payloadSize.
#payloads_size
The total payload size of a run of entries (etcd's payloadsSize).
#replicate
Drive one replication round from leader to every follower and advance the
commit index once a majority (the leader included) store the last entry.
Returns the resulting commit index.
#run_election
Run one round of leader election synchronously: candidate advances its
term and asks every peer for a vote, counting its own. It becomes leader on
a majority. If a peer reveals a higher term the candidate steps down at once
and the round fails. Returns whether the candidate won.
#run_single_node
Run a single-node Raft group through the Ready/Advance loop over a batch of
client commands, returning the commands the state machine applied, in order.
This is the smallest complete embedding of a RawNode, and it is the live
documentation of the Ready contract: for each command, propose it, then drain
every Ready by running the three steps a real application runs, in order —
persist the entries (store), apply the committed_entries, then
advance. Because persistence happens before application, committed_entries
may cover the same freshly appended entries as entries in one Ready, just
as in etcd. It is the non-test entry point that wires RawNode into a runnable
driver, and a demo or an embedder can call it directly.
#vote_result
The vote outcome for a (possibly joint) configuration. A joint vote is won
only when both halves win, lost as soon as either half loses, and pending
otherwise — the discipline that keeps a membership change from splitting the
cluster's decision (Raft §6).
Source Files
Raft consensus algorithm implemented in MoonBit.
raftconsensusdistributedreplicationstate-machine
0.5.2
Apache-2.0
Updated 20 days ago
26 downloads