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.

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.

#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.