Data model

Everything marekvs stores lives in the ondaDB data column family as internal key → envelope + payload. This page defines those byte layouts and the merge rules that make replication converge — the machinery behind the published guarantees.

#Partitioning

slot: u16 = crc16_xmodem(userkey) % 16384      // Redis Cluster slot
pid:  u16 = slot >> 2                          // 4 slots per pid → 0..4095

P = 4096 fixed partitions, chosen at cluster creation and never changed. Every internal key begins with the big-endian pid, so one partition is one contiguous ondaDB key range — which makes bootstrap streaming, Merkle digesting, and handoff cheap prefix operations. For collections, pid derives from the user key only (not the field or member), so a whole collection lives in one partition and on one shard thread.

The slot function is the same CRC16 hash Redis Cluster clients compute locally, so a cluster-aware client's slot = CRC16(key) % 16384 and marekvs' own placement agree — see Cluster protocol. This is a data-format change from the earlier xxh3-based partitioning: a cluster migrates through the same upstream-replication path used for Redis→marekvs moves (Cluster protocol).

Redis hash tags are implemented and match Redis exactly: if a key contains {...}, only the bytes inside the first non-empty brace pair are hashed — so rate:{user1}:count and rate:{user1}:window land on the same partition (and therefore the same shard thread). This is what lets a multi-key MULTI block or a Lua script co-locate its keys.

#Internal key layouts

All fields are concatenated with integers big-endian, so memcmp order is key order. klen is a varint length of the user key, so an element key can never collide with a user key that happens to embed another.

string          [pid:u16] [b's'] [userkey]
collection head [pid:u16] [b'M'] [klen] [userkey]
hash field      [pid:u16] [b'h'] [klen] [userkey] [field]
set member      [pid:u16] [b'S'] [klen] [userkey] [member]
zset member     [pid:u16] [b'z'] [klen] [userkey] [member]
zset score idx  [pid:u16] [b'Z'] [klen] [userkey] [score_be:u64] [member]
list element    [pid:u16] [b'q'] [klen] [userkey] [pos:u64]
hll register    [pid:u16] [b'H'] [klen] [userkey] [bucket:u16]
stream entry    [pid:u16] [b'x'] [klen] [userkey] [id_ms:u64] [id_seq:u64]

Per-element keys (hash fields, set/zset members, list elements, HLL registers, stream entries) pay off three ways: a mutation touches O(element) in the LSM, not O(collection); every replicated op is naturally a delta, so one HSET ships one field; and HGETALL / SMEMBERS / ZRANGE become prefix scans that LSM iterators handle well.

The zset score index is a second key per member, maintained in the same ondaDB transaction as the member key: the member key holds the score (the LWW source of truth) and the index key is derived, carrying no payload. The score is encoded as an order-preserving u64, so ZRANGEBYSCORE is a prefix scan over b'Z' keys.

#Envelope

A fixed 19-byte header is prefixed to every stored value:

offset size field
0      1    flags:  bit0 tombstone
                    bit1 collection-head
                    bits 2..5 record type (0 string, 1 hash-field, 2 set-member,
                              3 zset-member, 4 list, 5 stream-entry,
                              6 counter, 7 hll-register, 8 counter-field)
1      8    hlc:    u64 big-endian = [phys_ms:48 | logical:16]
9      2    origin: NodeId (u16)
11     8    ttl_deadline_ms: u64 absolute wall-clock ms; 0 = no TTL
19     …    payload

The origin node writes the envelope once, and replication ships it byte-for-byte with no re-stamping, so every replica agrees on the record's identity. (hlc, origin) is the record version — and, for element adds, its dot.

A collection head key carries its own small payload: the collection type (hash / set / zset / stream / list / HLL), a whole-collection delete clock, and, for streams, the last id and configuration.

#Hybrid logical clock

marekvs timestamps every write with a Kulkarni hybrid logical clock packed into a u64: 48 bits of physical milliseconds since the Unix epoch, plus a 16-bit logical counter (65k events per millisecond per node before it borrows a millisecond).

• Local event: hlc = max(hlc_prev + 1, wall_ms << 16).
• On receive: hlc = max(hlc_local, hlc_remote) + 1.
• A remote HLC more than max_clock_drift (5 s) ahead of local wall clock is clamped and logged loudly — NTP is assumed on the nodes.
• The total order for last-writer-wins is (hlc, origin); the u16 origin breaks exact ties deterministically.

There is one HLC per process (an atomic u64 behind a CAS loop), shared by every shard.

#Merge rules

The apply path — whether the write is a local command or an incoming replication op — always reads the current envelope and merges. A blind overwrite never happens on the replication path. Every merge is commutative, associative, and idempotent, and those laws are enforced by property tests in crates/marekvs-core/tests/merge_laws.rs.

#Every datatype at a glance

The merge is chosen by the record's type, never by the command that wrote it.

Four families cover all of it:

1. LWW register — the higher (hlc, origin) wins. Used where a later write genuinely should erase an earlier one.
2. Observed-remove element — each add carries its own dot, and a remove records the dots it observed. Used where a concurrent add and remove must both mean something.
3. Lattice value — a join that is order- and repetition-independent by construction (counter slots, HyperLogLog register max). Used where every concurrent write must survive, not merely the last one.
4. Structural decomposition — one record per path, field, member or position, so concurrent edits to different parts never contend at all. JSON, protobuf, lists and HyperLogLogs are all this, layered on one of the first three per record.

Families 2 and 3 compose: a counter-valued hash field is an observed-remove element (so HDEL works) whose value is a lattice (so concurrent increments all survive).

#What makes a merge correct here

"Commutative, associative, idempotent" is the textbook answer, and it is necessary but not sufficient. These are the rules a merge in marekvs also has to satisfy — each one is a way convergence can fail while every textbook law still holds.

The stored bytes must converge, not just the value. Anti-entropy compares partitions by hashing the records as stored. Two replicas that agree on what a record means but encode it differently will hash differently, so repair fires, ships the record, re-merges to the same disagreement, and fires again — forever. Everything below follows from this one requirement.

The result must not depend on which side is "incoming". The same merge runs on both nodes with the arguments swapped: node A merges (local A, incoming B) while node B merges (local B, incoming A). Anything derived from the incoming side rather than from both — including which of two record types the result takes — makes the two nodes encode different bytes from identical inputs. The merged type is therefore a deterministic function of both, and the merged version is the symmetric maximum, never "whichever arrived".

A lattice value on an observed-remove element has to be folded across every live contribution. This is the subtle one. When two nodes write concurrently, both contributions survive the merge — that is the whole point of an observed-remove element. But reading only the newest one shows a single node's work and hides the rest. The record converges perfectly while the read loses data, which no merge-law test can catch. Anything whose value is a lattice (counter-valued hash fields today) folds all live contributions on read.

A value that changes constantly must not consume remove-history. An observed-remove element remembers the dots a remove observed, and that memory is capped — 255 entries, oldest evicted. A value updated without bound that spent one entry per write would sit permanently at the cap, and evicting live remove-history is how a deleted item comes back. Counter-valued fields keep one entry per node instead, so the remove-history never grows from incrementing and a hot counter's record stays a fixed size no matter how often it is hit.

Node-local derived state stays out of the comparison. The sorted-set score index is rebuilt locally on each node and never replicated; including it in anti-entropy would make two correct replicas look permanently divergent.

A new record type is not written until every node can read it. Nodes announce their capabilities when they connect, and a type that some peer does not understand stays unwritten until the whole cluster has been upgraded — an older node would otherwise hand a client the raw internal payload. That is what makes a data-format change a rolling upgrade rather than a flag day.

#LWW registers

Strings, hash-field values, zset scores, list elements, and collection heads are last-writer-wins: higher (hlc, origin) wins, equal versions are the same write (a no-op). A tombstone is just a version with the tombstone flag set, so deletes and writes race symmetrically. EXPIRE / PERSIST are LWW writes of the envelope with an unchanged payload.

#Observed-remove elements

Set members, hash fields, and zset members use ORSWOT semantics at per-element granularity. Each element record carries two capped dot lattices:

element payload:
  [nlive u8] nlive × [origin u16][hlc u64][vlen varint][value]   # live adds
  [ncov  u8] ncov  × [origin u16][hlc u64]                       # covered (removed) dots

A local add contributes (dot, value) to live; a remove contributes the dots it observed to covered. Merge is the lattice join — covered' = cov_a ∪ cov_b, live' = (live_a ∪ live_b) \ covered' — and the element is dead when live' is empty. A lagging replica pushing an old add carries the old dot, which covered still holds, so deletes never resurrect; a concurrent add the remove never observed survives.

The caps keep the top-4 live dots and the top-255 covered dots (top-N-of-union is itself commutative, associative, and idempotent, so the caps preserve the merge laws).

#Whole-collection delete

DEL myhash writes one LWW tombstone on the head key with a delete clock. An element is live only if its version is newer than that clock — so a whole collection dies in one op, with no per-element tombstone fan-out. Stale elements are filtered on read and reclaimed by the expiry sweeper and anti-entropy.

#Counters (PN counters)

INCR / DECR / INCRBY / DECRBY on a string key produce a PN-counter record, not a plain string:

• a base register (base_hlc, base_origin, base_value) set by the last explicit SET (or (0,0,0) for a fresh counter), merged LWW;
• per-node delta slots (pos, neg) — each node only grows its own slot, so slots merge by pointwise max. The value is base + Σpos − Σneg.

When two nodes share a base version, their slots join and concurrent increments on different nodes all survive. A different base version (from an explicit SET) wins wholesale — matching Redis's "SET resets the counter". Reads materialize the counter as a decimal string, so GET / STRLEN / TYPE behave normally; APPEND / SETRANGE / GETSET / INCRBYFLOAT freeze it back into a plain string.

HINCRBY is a PN counter too. A hash field stays an observed-remove element — so HDEL and whole-hash DEL behave normally — but its value becomes counter state, and the number you read is the join across every concurrent writer's contribution. Two nodes each doing HINCRBY h f 1 at the same time leave the field at 2.

#HyperLogLog

PFADD / PFCOUNT / PFMERGE store a HyperLogLog decomposed into one record per touched register under a head-gated collection, merged by a one-byte max-lattice: higher rank wins with its own envelope; equal ranks resolve to the lower envelope version, so a duplicate PFADD is a strict no-op — no write, no replication, no anti-entropy churn. Sparse cardinalities materialize only the registers they touch; DEL writes one head tombstone whose delete clock gates old registers, so resurrection safety is identical to sets.

#Streams

XADD generates the entry id at the origin: the millisecond comes from the HLC's physical clock, and the sequence embeds the origin node id (seq = (origin << 20) | local_counter), so ids are cluster-unique without coordination. Merge is a union by id (entries are immutable — a duplicate id is the same entry). XDEL / XTRIM write per-entry LWW tombstones.

#Lists

Lists are per-element position-keyed LWW registers: a list is a collection head (like a set or zset) plus one element record per position.

list element  [pid][b'q'][klen][userkey][pos:u64 BE]   payload = raw value bytes

• Positions. pos is an unsigned u64 whose big-endian key suffix makes memcmp order equal list order. The first element lands at LIST_CENTER = 1<<63; LPUSH allocates head − 1, RPUSH allocates tail + 1, leaving ~2⁶³ of headroom each way. While only the ends are touched, push and pop are O(1) point writes and LRANGE is O(range).
• Elements are plain LWW registers, so every push/pop replicates as one delta through the shared write path — no list-specific merge code, no whole-value shipping.
• The head gates the collection: TTL and the whole-collection delete clock ride the head exactly like a hash or set, and DEL is one head tombstone.
• Interior ops rebuild. LSET overwrites one position in place (O(index)). LINSERT / LREM / LTRIM cannot open room between adjacent integer positions, so they read the live values, tombstone the old positions, and rewrite the sequence compacted from LIST_CENTER (O(n), and rare).

#TTL representation

A Redis TTL is stored as the envelope's absolute ttl_deadline_ms, set once at the origin and shipped verbatim. It is evaluated locally at read time: once now >= deadline, the record is treated as a tombstone whose clock is the deadline, so a stale pre-expiry value loses the merge against expiry and TTL converges cluster-wide without any expiry message. The record also gets an ondaDB per-key TTL of deadline + gc_grace as a compaction backstop.

Because hash fields, set members, and zset members are separate records with their own envelopes, per-member TTL (EXPIREMEMBER, a KeyDB extension) falls out naturally — each element carries its own deadline.

#What a TYPE check reads

Type resolves from the first matching key: a string key reports string; a head key reports its collection type. Writing a string where a hash exists (or vice versa) returns WRONGTYPE from this lookup — one extra point-read per command on the same shard, usually served from the memtable or block cache.