Consistency & anti-entropy

marekvs is eventually consistent, but bounded-eventually: the requirement is that stale records never live for long. This page is the mechanism and the math behind the 15 s worst-case, milliseconds-typical staleness bound the overview promises.

Anti-entropy (AE) runs in two layers, log-first with Merkle as a backstop. Both run only between home replicas — interest replicas get their bound from connection-scoped leases (replication) and never participate in AE.

#Layer 1 — sequence-cursor catch-up

Every node persists applied_seq[origin_node] in the meta CF, updated as ReplBatches are applied (each batch carries the origin's first_seq). On (re)connect to a peer, a node sends ResumeFrom{origin: self, seq}; if the peer's replication ring still holds that seq, it replays from there.

This is the log-first resume: it covers restarts and brief blips at near-zero cost, and it is exact — no digests, no scanning. Merkle exchange only runs when the log has already rolled past the gap.

#Layer 2 — per-partition Merkle exchange

Per owned partition, a 2-level digest:

• 256 leaf buckets: bucket = xxh3_64(ikey) & 0xFF.
• Bucket digest = XOR-fold of xxh3(ikey ‖ hlc ‖ value_hash) over the bucket's records. XOR is commutative, so no sorting is needed. Digests are content-aware (value_hash = xxh3(stored bytes)), not just version-aware.
• Root = xxh3 over the 256 bucket digests.

Buckets are dirty-marked by the commit hook (a bit set, nothing else) and recomputed lazily by prefix scan at sync time on the shard thread. A bucket is ~1/256 of a partition (≈1/1M of the keyspace), so scan cost is bounded and the hook never needs old values.

#Round protocol

Every ae_round = 5 s (plus jitter), each node walks its owned partitions in rotation and, for each, picks a random other owner (pairwise, Dynamo-style):

for each owned pid this round:
    peer = random other member of owners(pid)
    → MerkleRoot{pid, root}
    if roots differ:
        ← MerkleBuckets{pid, [256 × u64]}
        → per differing bucket: BucketKeys{pid, bucket, [(ikey_hash, hlc, value_hash)]}
        ↔ push/pull ReplOps for keys whose hlc or content differs or that are missing

Runs on the bulk connection, lz4-framed. Steady-state cost is one 12-byte root per (pid, round-participation) — tens of KB/s per node even on a 50-node cluster. Repair cost is proportional to the actual diff, which per-element keys keep minimal.

#Staleness bound

A committed write can be missing on some home only if its replication push failed (peer down, ring overrun, or membership-view divergence). Then:

staleness ≤ AE rotation delay + round exchange time
rotation delay ≤ ae_round × ceil(owned_pids / ae_partitions_per_round)

Owned pids shrink with cluster size (≈ 4096 × N / n), so the bound is sized for the worst supported small cluster:

• n ≥ 24: all owned pids fit in one round → bound ≈ 2 × ae_round + 1 s ≈ 11 s.
• n = 3 (floor): with a per-round cap the design restores ≤ 2 rounds for any cluster size, holding the bound.

Published bound: 15 s worst case (2 rounds + exchange + margin); typical: replication-push latency, single-digit milliseconds. The single knob to tighten it is ae_round, and cost scales linearly.

For interest replicas, the bound is ≤ the home bound plus push latency while connected; after a disconnect it is bounded by liveness detection plus revalidation on the next read. The pathological ceiling (a wedged-open connection) is the 60 s lease timer.

#Tombstone lifecycle & GC safe point

A delete is never a raw storage delete at write time — it is an envelope with the tombstone flag set (and, for element removes, the observed dots). GC works off the storage engine's per-key TTL:

• Every tombstone carries ondaDB per-key TTL = gc_grace = 1 h, so the engine purges it automatically at the safe point — no sweep needed.
• Safety invariant. A replica partitioned or down longer than gc_grace may hold data whose covering tombstone was already purged elsewhere; merging it back would resurrect the delete.

The rejoin gate is enforced. An alive:last heartbeat persists while the node is Active/Leaving. After an absence longer than gc_grace, the node stays Joining while its data-bearing home partitions synchronize with their pre-outage co-owners. Stale extras are dropped locally without replication; only after synchronization does the node regain normal push eligibility.

Interest replicas cannot resurrect by construction: they never push AE, and lease-gated reads revalidate against homes.

#TTL convergence

• Deadlines are absolute milliseconds, set once at the origin, shipped in the envelope, never recomputed per hop. Every replica evaluates now ≥ deadline locally → identical convergence modulo NTP-level skew.
• An expiry is an implicit tombstone with hlc = HLC(deadline, 0): any stale pre-expiry version loses the merge against expiry, so no expiry messages are needed and replicas can't disagree for longer than skew.
• EXPIRE / PERSIST / EXPIREAT are ordinary LWW envelope writes and replicate like any write.

#Idle expiry and cold data cleanup

Each shard discovers TTLs only in its own partitions, with a quantum of at most 128 records, eight partitions and a 2 ms elapsed-time target. One iterator step or storage commit can exceed that target; the elapsed budget is checked between processed records. Discovery also runs between foreground jobs, so busy clients cannot starve it.

A completed partition with no TTLs parks without opening more expiry iterators. Partitions with future TTLs wait for their earliest deadline. Committed writes, replication, bootstrap and local range deletion invalidate the affected partition; restart requires fresh discovery. Wall-clock changes are rechecked within one second. This preserves expiry while eliminating repeated scans of persistent data.

Cold data remains available for stranded-record anti-entropy after ownership loss. Cleanup requires the configured retention delay (15 minutes by default), a healthy full owner set, no active rejoin, and clean proof exchanges (three by default, configured with MAREKVS_COLD_PURGE_CLEAN_ROUNDS) for the current data generation and membership epoch. A feature-negotiated request nonce binds each reply to its peer and request; stale, duplicate and prior-boot replies cannot authorize deletion. Older peers continue ordinary replication and anti-entropy, but cannot supply cleanup proofs until upgraded.

The final eligibility check, bounded empty probe and local range delete run on the owning shard under a stable placement view. An already empty partition emits no new range tombstone. Clean proofs are rebuilt after restart.

Observe marekvs_expiry_iterators_total and marekvs_expiry_records_total to check that discovery settles. marekvs_db_range_fragments counts catalogued SST fragments only; the separate memtable and range-cache memory gauges expose in-memory range tombstones and retained fragment snapshots. See Testing for deterministic CI regressions and disposable benchmarks.

#HLC discipline

The full layout is in the data model; the rules that matter for convergence:

• One process-wide HLC (an atomic u64). Local event: max(prev + 1, wall << 16). Receive: max(local, remote) + 1.
• The receive rule runs at the replication apply point (apply_op in marekvs-repl): every ingested record's HLC is observed before it is merged. This is load-bearing. Without it, a node with a lagging wall clock that reads a value and then overwrites it stamps the overwrite below the value it causally read, and the overwrite loses LWW everywhere.
• LWW total order is (hlc, origin); equal pairs denote the identical write.
• A remote HLC more than max_clock_drift = 5 s ahead of local wall clock is clamped with a loud log. NTP is assumed on k8s nodes; the receive-max rule keeps causally-related updates ordered even under skew.

#Defaults table

This is the single source of truth for every tunable — other pages reference it and never restate values.

The Where set column is the current-vs-planned oracle:

• env VAR — startup environment variable (restart to change) → implemented.
• const (crate) — compile-time constant (rebuild to change) → implemented.
• manifest — the k8s pod spec → implemented.
• design — a design target not yet implemented; the Notes column says what the code does instead. These rows are marked Planned and collected in the callout below the table.

Runtime = adjustable on a live node without a restart. CONFIG SET applies three live keys — requirepass, lua-time-limit (alias busy-reply-threshold), and loglevel — and accepts-but-ignores everything else. All runtime changes are ephemeral: the env is the source of truth again after a restart (CONFIG REWRITE is a no-op; the k8s manifest is the durable config).

#Where to go next

• How writes are pushed before AE ever runs: Replication.
• Join, leave, and failure detection: Cluster membership.
• The guarantees this all backs: Overview.