lattice_maps/or_map
An observed-remove map (OR-Map) CRDT.
Keys are tracked using an OR-Set with add-wins semantics: concurrent update
and remove of the same key resolves in favor of the update. Each value is
itself a CRDT (specified by CrdtSpec at construction), enabling nested
convergent data structures.
Example
import lattice_maps/crdt
import lattice_core/replica_id
import lattice_counters/g_counter
import lattice_maps/or_map
let map = or_map.new(replica_id.new("node-a"), crdt.GCounterSpec)
|> or_map.update("score", fn(c) {
let assert crdt.CrdtGCounter(gc) = c
crdt.CrdtGCounter(g_counter.increment(gc, 10))
})
Types
An OR-Map (observed-remove map) CRDT.
Keys are tracked using an ORSet(String) which provides add-wins
semantics: if an update and a remove of the same key happen concurrently
on different replicas, the update wins after merging.
Values are stored as the Crdt tagged union so they can be merged
per-key using type-specific logic. The crdt_spec field records which
CRDT type is used for values, enabling auto-creation of default values
for new keys.
pub opaque type ORMapA delta describing changes to an ORMap.
Carries only the touched keys and their value-CRDT deltas, plus the
key-set delta from the underlying ORSet. The crdt_spec and
replica_id are included so apply_delta can validate and route the
merge correctly.
An ORMapDelta is structurally a sparse ORMap: it can be applied to
any remote ORMap of the same crdt_spec via apply_delta. Multiple
deltas can also be combined into a single delta via merge_deltas
before transmission.
pub opaque type ORMapDeltaValues
pub fn apply_delta(
map: ORMap,
delta: ORMapDelta,
) -> Result(ORMap, crdt.MergeError)Apply a delta to a map, producing a new map.
Returns Error(TypeMismatch(...)) if the delta and map have different
crdt_spec values. Otherwise reconstructs the delta as a sparse
sparse state, so only the keys carried by the delta need value/bound work.
Idempotent and commutative: applying the same delta twice, or applying deltas in any order, yields the same final state.
pub fn delta_from_json(
json_string: String,
) -> Result(ORMapDelta, json.DecodeError)Decode an ORMapDelta from a JSON string produced by delta_to_json.
pub fn delta_to_json(delta: ORMapDelta) -> json.JsonEncode an ORMapDelta as a self-describing JSON value.
Format mirrors to_json for ORMap but uses "type": "or_map_delta".
Use delta_from_json to decode.
pub fn empty_delta(map: ORMap) -> ORMapDeltaReturn the empty/identity delta for a map.
apply_delta(m, empty_delta(m)) returns m unchanged. Useful as the
starting accumulator when folding multiple delta-producing operations.
pub fn from_json(
json_string: String,
) -> Result(ORMap, json.DecodeError)Decode an ORMap from a JSON string produced by to_json.
Supports both v1 (no remove_bounds) and v2 (with remove_bounds) formats. v1 maps are decoded with empty remove_bounds, meaning no value compaction is possible until new removes are performed.
Returns Error if the string is not valid JSON, does not match the
expected format, or contains an unknown crdt_spec string.
pub fn get(map: ORMap, key: String) -> Result(crdt.Crdt, Nil)Get the CRDT value at key.
Returns Ok(crdt) if the key is active in the OR-Set.
Returns Error(Nil) if the key has never been added, or has been removed
and not re-added.
pub fn keys(map: ORMap) -> List(String)Return the list of all active keys (those present in the OR-Set).
Order is not guaranteed.
pub fn merge(
a: ORMap,
b: ORMap,
) -> Result(ORMap, crdt.MergeError)Merge two OR-Maps.
The OR-Set key trackers are merged with add-wins semantics: if a key was
concurrently updated on one replica and removed on another, the key
survives in the merged result. CRDT values are merged per-key using
crdt.merge for type-specific convergence.
Returns Error(TypeMismatch(...)) if the two maps have different
crdt_spec values (e.g., one holds counters and the other holds sets).
pub fn merge_deltas(
a: ORMapDelta,
b: ORMapDelta,
) -> Result(ORMapDelta, crdt.MergeError)Combine two deltas into a single delta.
Useful for transport layers that batch unacked deltas before
transmission: instead of sending N small deltas, merge them once and
send the join. Equivalent under apply_delta to applying both deltas
individually in either order.
Returns Error(TypeMismatch(...)) if the two deltas have different
crdt_spec values.
pub fn new(
replica_id: replica_id.ReplicaId,
crdt_spec: crdt.CrdtSpec,
) -> ORMapCreate a new empty OR-Map for the given replica with the specified CRDT type.
The crdt_spec determines what type of CRDT is auto-created when update
is called on a key that does not yet exist in the map.
pub fn prune(
map: ORMap,
stable_vv: version_vector.VersionVector,
) -> ORMapPrune tombstones for keys and compact removed values whose removal is causally stable.
Delegates to or_set.prune to remove tombstones from the internal key
tracker. Then, for each removed key that has a recorded causal bound, if
the pruned version vector dominates that bound, the key’s CRDT value is
discarded (the removal is stable and no concurrent re-add can reference
the old value).
Only call this with a version vector representing events that have been seen by all replicas (causally stable), otherwise zombie updates might be incorrectly ignored.
pub fn remove(map: ORMap, key: String) -> ORMapRemove a key from the OR-Map.
Removes the key from the OR-Set (marking it inactive). The underlying CRDT value is retained until prune determines the removal is causally stable. A causal bound is recorded so prune can later decide when it is safe to discard the value.
State-only convenience wrapper around remove_with_delta — the produced
delta is discarded. See remove_with_delta for the delta-state variant
that also returns a small payload suitable for incremental sync (e.g.
over websockets).
pub fn remove_with_delta(
map: ORMap,
key: String,
) -> #(ORMap, ORMapDelta)Remove a key and return both the new map and a delta capturing the remove.
The delta carries the OR-Set tombstones from or_set.remove_with_delta
and the recorded causal bound, which together let any remote replica
retract the key while preserving add-wins semantics for concurrent adds.
pub fn to_json(map: ORMap) -> json.JsonEncode an ORMap as a self-describing JSON value.
The nested OR-Set (key_set) and CRDT values are double-encoded as JSON
strings so they can be decoded using the existing from_json APIs.
Format: {"type": "or_map", "v": 2, "state": {"replica_id": "...", "crdt_spec": "...", "key_set": "...", "values": [...], "remove_bounds": {...}}}
The encoded value can be restored with from_json.
pub fn update(
map: ORMap,
key: String,
f: fn(crdt.Crdt) -> crdt.Crdt,
) -> ORMapApply a function to the CRDT value at key, auto-creating it if absent.
If the key does not exist, a default value is created from crdt_spec
and passed to f. The key is added to the OR-Set, marking it active.
The return value of f replaces (or sets) the value for that key.
See update_with_delta for the delta-state variant that also returns a
small payload suitable for incremental sync (e.g. over websockets).
pub fn update_with_delta(
map: ORMap,
key: String,
f: fn(crdt.Crdt) -> crdt.Crdt,
) -> Result(#(ORMap, ORMapDelta), crdt.MergeError)Apply a function to the value at key and return both the new map and a
delta capturing the touched key.
The callback f receives the current value (or a default if absent) and
returns the new value. The delta contains that per-key CRDT value, which is
sparse at the map level and safe to apply to any replica of the same spec.
or_map.update_with_delta(map, "score", fn(c) {
let assert crdt.CrdtGCounter(gc) = c
crdt.CrdtGCounter(g_counter.increment(gc, 5))
})
Returns Error(TypeMismatch(...)) if the returned value does not match the
map’s crdt_spec.