in reviewhumanPR #192Memory
hackathon/daksh-orset-memory: OR-Set CRDT memory plugin — concurrent adds survive
[[02 — Conflict-free shared memory under concurrent writers](https://claude.ai/cowork/docs/hackathon/problems/02-memory-crdt-lww.md)](docs/hackathon/problems/02-memory-crdt-lww.md)
Author
@dakshgupta973-create
github profile →- Status
- In review
- Opened on
- Jul 11
- Branch
- hackathon/daksh-orset-memory
Description
The pitch.
## Problem
[[02 — Conflict-free shared memory under concurrent writers](https://claude.ai/cowork/docs/hackathon/problems/02-memory-crdt-lww.md)](docs/hackathon/problems/02-memory-crdt-lww.md)
The problem statement names two suggested plugin shapes: `lww_crdt` and
`or_set`. The LWW-Register half was shipped in an earlier PR; this PR ships
the **OR-Set** half, which covers the case the register *cannot*: an
LWW-Register resolves a concurrent-write race by discarding all but one
winner. For the shared-catalogue pain named in the problem's motivation
(fifty marketplace sellers racing to claim entries under one key), that means
forty-nine writes silently vanish. An observed-remove set keeps them all.
## What this adds
**`nest_plugins_reference/memory/or_set.py`** — a state-based OR-Set CvRDT
implementing the `Memory` protocol (`isinstance(plugin, Memory)` holds):
- `write` = observed-remove of locally-seen elements + add under a fresh
`node_id:counter` tag; local reads behave register-like.
- Concurrent adds from other replicas are never covered by a local remove,
so they **survive the merge** — the defining OR-Set guarantee.
- `read` returns the single live element as-is, or a canonical sorted JSON
array when concurrent elements coexist — deterministic, byte-identical on
every converged replica.
- `cas` is implemented in terms of the set's natural merge semantics.
- `export`/`merge`/`export_all`/`merge_all` replication channel, same shape
as `lww_register`. Merge = union ∪ union: commutative, associative,
idempotent.
- Deterministic by construction: tags are `(node_id, counter)` — no wall
clock, no global RNG. Serialized state is grep-able JSON tagged
`"crdt": "or_set"`.
**Registration** — `("memory", "or_set")` in `nest_core/plugins.py` builtins
and the `nest.plugins.memory` entry point in
`nest-plugins-reference/pyproject.toml`.
**`tests/test_or_set.py`** — 27 tests:
- Protocol conformance + full read/write/cas/subscribe surface.
- The three CRDT algebraic laws on the pure state (commutativity,
associativity, idempotence), plus observed-remove correctness.
- **The discriminating test**: the adversarial
`validate_crdt_convergence` validator **fails against `blackboard` and
passes against `or_set`** under three different delivery orders.
- **The test that fails without this change**: concurrent writes on two
replicas — `or_set` preserves both elements; the companion test pins down
that `lww_register` keeps only one, documenting exactly the gap this
plugin closes. Registry-wiring tests fail without the `plugins.py` line.
- Determinism: same ops → byte-identical export; merge order does not
change bytes. Idempotence under duplicated gossip. Malformed-state
handling via `CrdtStateError`.
## How to run
```bash
pytest packages/nest-plugins-reference/tests/test_or_set.py -v
```
Results on this branch: 27/27 pass; existing `test_lww_register.py`,
`test_plugins.py`, and `test_imports.py` all still pass (74 tests). `ruff
check` and `ruff format --check` clean on all touched files.
## Scope and limits (honest)
- State-based (CvRDT), per the problem's out-of-scope note on CmRDTs.
- Remove tombstones are kept forever; garbage collection is out of scope
here and called out in the module docstring.
- Reuses the existing generic `validate_crdt_convergence` validator rather
than duplicating it — it was written capability-based (export/merge) and
works unchanged for this plugin.Try it
Open PR on GitHubView diffCheckout locally
git fetch origin pull/192/head:pr-192
git checkout pr-192