rgoussu.dev
rgoussu@goussu: ~/library/system-design/exercises
❯ ~/library/system-design/exercises cat raft-with-gossip-glomers-subject.md

Implement Raft with Gossip Glomers — subject

# The full work statement for the Gossip Glomers ladder — the Maelstrom message environment, each rung's workload contract, and the Raft assignment stated as requirements, runnable offline.

Subjectsaved 2026-08-08source #exercise#raft#consensus#distributed-systems#gossip#maelstrom#subject

Brief

You are writing the node software for a small distributed system whose network is actively hostile: messages are delayed, duplicated, and dropped, and the test harness deliberately partitions the cluster while checking your answers for consistency. The harness is Maelstrom (Jepsen's workbench). You climb a ladder of workloads — each one a distributed-systems pattern — and the top rung is a linearizable key-value store backed by your own Raft implementation.

Instructions

1. The Maelstrom environment

Your node is any executable. Maelstrom launches N copies of it and speaks JSON to each:

  • Transport — one JSON object per line on stdin (messages in) and stdout (messages out). Anything for humans goes to stderr; a stray print to stdout corrupts the protocol.
  • Message shape — {"src": "<node-id>", "dest": "<node-id>", "body": {…}}. Every body has a type; requests carry a unique msg_id; replies echo it back as in_reply_to and use the <type>_ok reply type (errors use type error with a numeric code and text).
  • Init — the first message every node receives is {"type": "init", "node_id": "n1", "node_ids": ["n1","n2",…]}. Store both, reply init_ok. Node ids start with n; client ids with c.
  • Inter-node RPC — nodes message each other with the same envelope. There is no delivery guarantee: build your own retry (with timeout) and make handlers idempotent, because retries mean duplicates.
  • Maelstrom services — the harness also exposes key-value stores as pseudo-nodes you can RPC (lin-kv, seq-kv) with read / write / cas operations; rung 4 uses one.

Run a workload as maelstrom test -w <workload> --bin <your-binary> --node-count <n> --time-limit <s> [--rate <ops/s>] [--nemesis partition] and pass when it prints "Everything looks good!".

2. The ladder — one contract per rung

  1. Echo — handle {"type":"echo","echo":<any>} → reply echo_ok with the same echo field. This rung exists only to prove your stdin/stdout/reply plumbing.
  2. Unique IDs — handle {"type":"generate"} → generate_ok with an id that is globally unique across all nodes for the whole run, without any inter-node communication. The workload runs with partitions and demands total availability — derive ids from what a node already knows (its node id + a local counter, or timestamp + node id + sequence). Ids may be any JSON value.
  3. Broadcast — three sub-stages against the broadcast workload:
    • Handle {"type":"topology","topology":{…}} (a suggested neighbor map — you may use it or ignore it) → topology_ok; {"type":"broadcast","message":<int>} → broadcast_ok; {"type":"read"} → read_ok with messages: every value this node has ever seen, in any order, duplicates ignored. Gossip each new value to other nodes so every node eventually reads every value.
    • Survive partitions (--nemesis partition): retry unacknowledged gossip until it lands; dedupe on receipt. Values injected during a partition must appear everywhere once it heals.
    • Tune for efficiency on 25 nodes: first ≤ 30 messages per operation, then ≤ 20, while keeping median propagation latency within the workload's stated bounds (below ~1 s median / 2 s max, then ~1 s / 2 s with the lower message budget) — batch, and trade topology fan-out against hops.
  4. Grow-only counter — workload g-counter, partitions on. Handle {"type":"add","delta":<non-negative int>} → add_ok and {"type":"read"} → read_ok with the counter's value. The counter is eventually consistent: reads may lag while partitioned but must converge to the true sum once healed. Build it on the seq-kv service (cas-loop per node key, sum on read) or as CRDT-style per-node counters gossiped and merged with max.
  5. Kafka-style log — workload kafka: replicated append-only logs. {"type":"send","key":<log>,"msg":<int>} → send_ok with the assigned integer offset; offsets within one key are monotonically increasing and never reused. {"type":"poll","offsets":{<key>:<from>}} → poll_ok with msgs: for each key, [[offset, msg], …] from the requested offset on, in order, no committed gaps. {"type":"commit_offsets","offsets":{…}} → commit_offsets_ok; {"type":"list_committed_offsets","keys":[…]} → the last committed offset per key. Start on the linearizable lin-kv service, then multi-node with sane performance.
  6. Totally-available transactions — workload txn-rw-register. Handle {"type":"txn","txn":[["r",<key>,null],["w",<key>,<value>],…]} → txn_ok with the same list, reads filled in with the value seen (or null). The system must stay totally available under partition — never block, never refuse — which caps you at weak isolation: first pass Read Uncommitted (no dirty writes: the checker rejects two transactions' writes interleaving per key), then Read Committed (never expose a value from an uncommitted or aborted transaction — replicate whole transactions atomically).

3. The Raft assignment

Rung 7: make workload lin-kv pass — a linearizable key-value store (read / write / cas operations from clients, where cas compares the current value with from and sets to only on match, erroring on mismatch or missing key) — with partitions enabled, by implementing Raft yourself. Requirements, not the paper:

  • State — every node persists (in memory here) currentTerm, votedFor, and a log of {term, command} entries (1-indexed); volatile commitIndex and lastApplied; leaders track per-follower nextIndex and matchIndex.
  • Leader election — nodes start as followers. A follower that hears nothing from a valid leader within a randomized election timeout (spread the range wide enough that split votes are rare; hundreds of ms against Maelstrom's latencies) increments its term, votes for itself, and requests votes from all peers. A vote is granted at most once per term, and only to a candidate whose log is at least as up-to-date (higher last term wins; equal terms → longer log wins). A majority of votes makes a leader; a message bearing a higher term makes anyone step down to follower and adopt that term.
  • Log replication — clients' operations go to the leader (non-leaders reply with a "not the leader" error or proxy). The leader appends to its own log and sends append-entries RPCs carrying the previous entry's index and term; a follower rejects the RPC if its log disagrees at that position, and the leader backs nextIndex down and retries until logs match, then overwrites the follower's conflicting suffix. Heartbeats are empty append-entries on a timer well under the election timeout.
  • Commit — the leader advances commitIndex to the highest index replicated on a majority whose entry is from the leader's current term; committed entries are applied to the KV state machine in log order, exactly once, and only then answered to the client.
  • Safety under partition — at most one leader per term; a deposed leader's unreplicated entries are discarded, never applied; committed entries survive any minority partition and leader change; two nodes never apply different commands at the same log index. cas correctness is the observable proof: it only ever succeeds against the true committed value.

Constraints

  • Any language; only a JSON library is assumed. Do not use a Raft/consensus library — the consensus code is the exercise. Maelstrom's provided language demos may be read for plumbing, not copied for logic.
  • Never write non-protocol output to stdout.
  • Handlers must tolerate duplicate delivery at every rung from 3 up.
  • Rungs are completed in order; each must pass before the next starts.

Acceptance

One check per exercise milestone, all via the Maelstrom CLI:

  1. Echo — maelstrom test -w echo --bin <node> --node-count 1 --time-limit 10 passes.
  2. Unique IDs — -w unique-ids --node-count 3 --rate 1000 --time-limit 30 --availability total --nemesis partition passes: zero duplicate ids under partition.
  3. Broadcast — -w broadcast --node-count 5 --time-limit 20 --rate 10 passes; then the same with --nemesis partition; then --node-count 25 --rate 100 with reported msgs-per-op ≤ 30, and finally ≤ 20, latencies within the stated bounds.
  4. Grow-only counter — -w g-counter --node-count 3 --rate 100 --time-limit 20 --nemesis partition passes: final reads equal the sum of all acknowledged deltas.
  5. Kafka-style log — -w kafka --node-count 2 --concurrency 2n --time-limit 20 --rate 1000 passes: no lost writes, per-key order preserved, committed offsets honored.
  6. Transactions — -w txn-rw-register --node-count 2 --concurrency 2n --rate 1000 --time-limit 20 --availability total --nemesis partition passes, first with --consistency-models read-uncommitted, then read-committed.
  7. Raft — -w lin-kv --node-count 3 --concurrency 2n --rate 100 --time-limit 60 --nemesis partition passes: Maelstrom's linearizability checker finds no violation; kills/partitions during the run produce re-elections, not lost acknowledged writes.

Related