A CRDT of plain maps, which devices merge in any order without conflict.
A state is a map of collections, each a map of entries, maybe nested by more keys, with the :device that the state belongs to and its :clock. An entry is stamped with :updated-at and :device, and a removed entry is a tombstone with :removed?.
A schema maps the key of each collection to its options:
:depth, the number of keys that lead to each entry
:compact?, to drop its tombstones once every device has seen them
:count-key, the key of a count in each entry, which only grows
{:notes {:depth 1 :compact? true} :listened {:depth 3 :count-key :seconds}}
The registry of devices, under :devices and :retired, needs no schema.
The comments in the code name the source of each part, and where it departs from it:
A CRDT of plain maps, which devices merge in any order without conflict.
A state is a map of collections, each a map of entries, maybe nested by
more keys, with the :device that the state belongs to and its :clock. An
entry is stamped with :updated-at and :device, and a removed entry is a
tombstone with :removed?.
A schema maps the key of each collection to its options:
- :depth, the number of keys that lead to each entry
- :compact?, to drop its tombstones once every device has seen them
- :count-key, the key of a count in each entry, which only grows
{:notes {:depth 1 :compact? true}
:listened {:depth 3 :count-key :seconds}}
The registry of devices, under :devices and :retired, needs no schema.
The comments in the code name the source of each part, and where it
departs from it:
- Shapiro, Preguiça, Baquero and Zawirski, A comprehensive study of
Convergent and Commutative Replicated Data Types, INRIA RR-7506, 2011,
https://inria.hal.science/inria-00555588
- Almeida, Approaches to Conflict-free Replicated Data Types, ACM
Computing Surveys 57(2), 2024, https://arxiv.org/abs/2310.18220
- Johnson and Thomas, The Maintenance of Duplicate Databases, RFC 677,
1975, https://www.rfc-editor.org/rfc/rfc677
- Kulkarni, Demirbas, Madappa, Avva and Leone, Logical Physical Clocks,
OPODIS 2014, https://doi.org/10.1007/978-3-319-14472-6_2
- Almeida, Shoker and Baquero, Delta State Replicated Data Types,
Journal of Parallel and Distributed Computing 111, 2018,
https://arxiv.org/abs/1603.01529(acknowledge state states at)Note in the registry of state at at that its device has merged the
whole states, as the latest stamp of each other device under :seen.
Only whole states count, never the changes that a service sends. The device's entry is only written when :seen grows, so that a sync with nothing new leaves the state as it was.
Note in the registry of `state` at `at` that its device has merged the whole `states`, as the latest stamp of each other device under :seen. Only whole states count, never the changes that a service sends. The device's entry is only written when :seen grows, so that a sync with nothing new leaves the state as it was.
(after state at)The instant to stamp a write to state at at with: at, or the
millisecond after the state's clock when that's later.
The instant to stamp a write to `state` at `at` with: `at`, or the millisecond after the state's clock when that's later.
(as-device state device f)The state that f returns for it, with every write in f made by
device at exactly the instant given, as if merged from that device,
e.g. for the changes that a sync service reports.
The `state` that `f` returns for it, with every write in `f` made by `device` at exactly the instant given, as if merged from that device, e.g. for the changes that a sync service reports.
(at-once state at f)The state that f returns for it, with every write in f stamped as
one write at at, rather than each a millisecond after the last, e.g.
for the writes of an import.
The `state` that `f` returns for it, with every write in `f` stamped as one write at `at`, rather than each a millisecond after the last, e.g. for the writes of an import.
(changes-since state previous)The part of state that isn't in the earlier state previous, or all
of it when previous is nil, e.g. for a service that takes changes
rather than whole states. It holds every entry written or merged since,
however early its stamp.
The part of `state` that isn't in the earlier state `previous`, or all of it when `previous` is nil, e.g. for a service that takes changes rather than whole states. It holds every entry written or merged since, however early its stamp.
(compact schema state at)(compact schema
state
at
{:keys [keep-for] :or {keep-for default-keep-for} :as opts})The state at at without the tombstones of the collections that the
schema marks :compact?, once every device that isn't retired has
merged them and the :keep-for of opts has passed.
The :keep-for is in milliseconds, 30 days by default. A device that stopped syncing holds this back until it's retired, and the tombstones of an author outside the registry stay. A change from such an author with an earlier stamp than a tombstone that was dropped brings its entry back, so the :keep-for should be longer than its changes can be late.
The `state` at `at` without the tombstones of the collections that the `schema` marks :compact?, once every device that isn't retired has merged them and the :keep-for of `opts` has passed. The :keep-for is in milliseconds, 30 days by default. A device that stopped syncing holds this back until it's retired, and the tombstones of an author outside the registry stay. A change from such an author with an earlier stamp than a tombstone that was dropped brings its entry back, so the :keep-for should be longer than its changes can be late.
How long to keep a tombstone that every device has seen, in milliseconds, so that a device that joins later with a state of its own still gets it.
How long to keep a tombstone that every device has seen, in milliseconds, so that a device that joins later with a state of its own still gets it.
(devices state)The devices of state that aren't retired, as a map of id to what each
said of itself.
The devices of `state` that aren't retired, as a map of id to what each said of itself.
(identify state description at)Describe this device in the registry of state at at, with a
description such as its :name and :platform, merged into what it
said before.
Describe this device in the registry of `state` at `at`, with a `description` such as its :name and :platform, merged into what it said before.
(lagging state)The devices of state that aren't retired and haven't merged
everything its device has, as a map of id to the stamp up to which each
has merged everything, or nil. They keep tombstones from being dropped
until they catch up or are retired.
The devices of `state` that aren't retired and haven't merged everything its device has, as a map of id to the stamp up to which each has merged everything, or nil. They keep tombstones from being dropped until they catch up or are retired.
(later a b)The later of the stamped entries a and b. At the same instant, the
greater device id wins, and then the greater printed entry, so that the
winner is the same on every device and platform.
The later of the stamped entries `a` and `b`. At the same instant, the greater device id wins, and then the greater printed entry, so that the winner is the same on every device and platform.
(later-inst a b)The later of the instants a and b, either of which can be nil.
The later of the instants `a` and `b`, either of which can be nil.
(live-by-stamp entries)The keys of the live entries of the map entries, the latest written
first.
The keys of the live entries of the map `entries`, the latest written first.
(live? e)Whether the entry e is there and isn't a tombstone.
Whether the entry `e` is there and isn't a tombstone.
(merge schema a b)Merge the states a and b of two devices by the schema, key by key,
by the shape of each value:
aThe merge is commutative, associative and idempotent, so it's safe to apply in any order and any number of times.
Merge the states `a` and `b` of two devices by the `schema`, key by key, by the shape of each value: - a stamped entry is a last-writer-wins register, and the later entry wins whole, even when it's a tombstone, but in a collection with a :count-key, the higher count wins - a map merges key by key, down to the entries - an instant is a max register - any other value is that of `a` The merge is commutative, associative and idempotent, so it's safe to apply in any order and any number of times.
(problem schema state)A description of what in state breaks the rules below, given the
schema, or nil. A bad value from another device spreads to every
device, where it makes a function throw, or the devices disagree.
A description of what in `state` breaks the rules below, given the `schema`, or nil. A bad value from another device spreads to every device, where it makes a function throw, or the devices disagree. - The state and its collections are maps, and the clock is an instant. - Besides the device and the clock, the state holds only maps, down to stamped entries. - Each entry of a collection has a stamp, which is an instant. - What a device has seen is a map of instants.
(retire state device at)Retire device from state at at. Any device can retire another,
and a retired device can't come back by describing itself again.
Retire `device` from `state` at `at`. Any device can retire another, and a retired device can't come back by describing itself again.
(retired? state device)Whether device is retired in state.
Whether `device` is retired in `state`.
(schema-problem schema)A description of what in schema breaks the rules below, or nil. A bad
schema can make a function throw, or an option do nothing, e.g. one with
a misspelt name.
A description of what in `schema` breaks the rules below, or nil. A bad schema can make a function throw, or an option do nothing, e.g. one with a misspelt name. - The schema is a map of the key of each collection to its options. - The options are a map with a :depth, a whole number from 0. - The only options are :depth, :compact?, :count-key and :ranked?. - No collection is under :device, :clock, :devices or :retired, which the state holds itself.
(stamp-ms e)The stamp of the entry e in milliseconds, 0 for an entry without one.
The stamp of the entry `e` in milliseconds, 0 for an entry without one.
(write state path f at)The state with the entry at path replaced by what f returns for
it, or for nil when there's none. It's stamped at at, or just after
the state's clock when that's later.
The `state` with the entry at `path` replaced by what `f` returns for it, or for nil when there's none. It's stamped at `at`, or just after the state's clock when that's later.
(write-each state writes at)The state with each of the writes, pairs of a path and a function,
made at at with one stamp: the entry at the path is replaced by what
the function returns for it.
The `state` with each of the `writes`, pairs of a path and a function, made at `at` with one stamp: the entry at the path is replaced by what the function returns for it.
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |