lattice_maps/lww_map
A last-writer-wins map (LWW-Map) CRDT.
Each key maps to a value and a timestamp. On conflict, the entry with the higher timestamp wins. Removal is timestamp-based (tombstone): a remove at timestamp T beats any set at timestamp < T. Keys are strings; values are strings.
Example
import lattice_maps/lww_map
let a = lww_map.new() |> lww_map.set("name", "Alice", 1)
let b = lww_map.new() |> lww_map.set("name", "Bob", 2)
let merged = lww_map.merge(a, b)
lww_map.get(merged, "name") // -> Ok("Bob")
Tombstone Management
Removing a key creates a tombstone that persists until pruned. Use
tombstone_count to monitor growth and prune to reclaim space once all
replicas have synced past a stable timestamp. The embedded
pruned_timestamp ensures that stale entries from unsynced replicas are
automatically rejected during merge (zombie prevention).
Types
A Last-Writer-Wins Map (LWW-Map) CRDT.
Internally stores each key with an Option(String) value and an Int
timestamp. A None value represents a tombstone (removed key). On merge,
the entry with the higher timestamp wins for each key; on ties, the first
argument’s entry is kept as a consistent tiebreak.
Tombstones accumulate until pruned. Use prune with a stable timestamp to
remove them. The embedded pruned_timestamp enables automatic zombie
detection on merge — entries from remote replicas at or below the pruned
threshold are discarded, preventing deleted keys from resurrecting.
pub opaque type LWWMapValues
pub fn from_json(
json_string: String,
) -> Result(LWWMap, json.DecodeError)Decode a LWWMap from a JSON string produced by to_json.
Supports both v1 (no pruned_timestamp, defaults to 0) and v2 formats.
Returns Error if the string is not valid JSON or does not match the
expected format.
pub fn get(map: LWWMap, key: String) -> Result(String, Nil)Get the value for a key.
Returns Ok(value) if the key exists and is not tombstoned.
Returns Error(Nil) if the key is missing or has been removed.
pub fn keys(map: LWWMap) -> List(String)Return all active (non-tombstoned) keys in the map.
Order is not guaranteed.
pub fn merge(a: LWWMap, b: LWWMap) -> LWWMapMerge two LWW-Maps by resolving each key using the highest timestamp.
Tombstones participate in merge: if a tombstone has a higher timestamp than the active entry for a key, the key remains removed after merging. On equal timestamps, a deterministic tie-break is used: tombstones win over active values, otherwise the lexicographically greater value wins.
Merge is commutative, associative, and idempotent (a valid CRDT join).
pub fn prune(map: LWWMap, stable_timestamp: Int) -> LWWMapPrune tombstones at or below the given stable timestamp.
Removes all tombstone entries (keys with None value) whose timestamp is
less than or equal to stable_timestamp. Active entries are never removed.
The pruned_timestamp is updated monotonically to max(current, stable_timestamp).
After pruning, merge automatically detects zombie entries — entries from
remote replicas whose timestamps fall at or below the pruned threshold are
discarded, preventing deleted keys from resurrecting.
The stable_timestamp should ideally represent a point that all replicas
have synced past. Using a conservative (older) value is always safe; using
a value ahead of some replica means that replica’s stale writes will be
silently dropped on merge (which is the correct behavior for pruned history).
Examples
let m = lww_map.new()
|> lww_map.set("a", "alive", 1)
|> lww_map.remove("b", 5)
|> lww_map.remove("c", 15)
let pruned = lww_map.prune(m, 10)
lww_map.tombstone_count(pruned) // -> 1 (only "c" at ts=15 remains)
lww_map.get(pruned, "a") // -> Ok("alive")
pub fn pruned_timestamp(map: LWWMap) -> IntReturn the pruned timestamp.
This is the highest stable timestamp passed to prune. Entries from remote
replicas with timestamps at or below this value are treated as zombies during
merge and discarded. A value of 0 means no pruning has occurred.
pub fn remove(map: LWWMap, key: String, timestamp: Int) -> LWWMapRemove a key at the given timestamp by inserting a tombstone.
If the key already has an entry with an equal or higher timestamp, the remove is rejected and the existing entry wins.
Note: This operation creates a tombstone. Use tombstone_count to monitor
growth and prune with a stable timestamp to remove tombstones once all
replicas have observed them.
pub fn set(
map: LWWMap,
key: String,
value: String,
timestamp: Int,
) -> LWWMapSet a key to a value at the given timestamp.
If the key already has an entry with an equal or higher timestamp, the existing entry is kept (LWW semantics: strictly greater timestamp wins).
pub fn to_json(map: LWWMap) -> json.JsonEncode a LWWMap as a self-describing JSON value.
Entries are encoded as a JSON array where each element has key, value
(nullable string for tombstones), and timestamp fields. The
pruned_timestamp field records the highest stable timestamp passed to
prune, enabling zombie detection after deserialization.
Format: {"type": "lww_map", "v": 2, "state": {"entries": [...], "pruned_timestamp": N}}
The encoded value can be restored with from_json.
pub fn tombstone_count(map: LWWMap) -> IntReturn the number of tombstoned (removed) entries in the map.
Useful for monitoring tombstone growth and deciding when to call prune.
Examples
let m = lww_map.new()
|> lww_map.set("a", "1", 1)
|> lww_map.set("b", "2", 1)
|> lww_map.remove("a", 10)
lww_map.tombstone_count(m) // -> 1