HarperFast / HarperFast/harper
CRDT counters are op-replicated with best-effort dedup; a state-based counter would make merges idempotent
- Dominant language
- JavaScript
- Stars
- 89
- Forks
- 10
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 200
Description
## Problem
Harper's only CRDT operation today is the numeric `add` (`Addition`, and `subtract` as a negative add). It is an **operation-based** CRDT: replication ships the increment (`{__op__:'add', value}`), and each node applies it. An `add` is not idempotent, so correctness depends on applying each increment *exactly once*.
Harper's replication is at-least-once — audit-replay and full-copy both legitimately re-deliver writes — so exactly-once application is enforced after the fact by a stack of dedup guards in `resources/Table.ts`'s out-of-order resequencing walk (the commit callback in `_writeUpdate`). Several of those guards are explicitly documented in-code as best-effort:
- the up-front keyed audit lookup and the depth-cap `isReDeliveredDuplicate` check "can intermittently miss under load" (the #1137 / #1148 lineage);
- the only hard guard is the `additionalAuditRefs` read-your-writes check, which covers a re-delivery only while the ref is still on the record head — a later in-order write drops it, and that case falls back to the best-effort keyed lookup.
When a dedup guard misses, the increment is applied twice. The current safety net is that a subsequent full-copy re-converges the record — i.e. the counter is transiently wrong and self-heals only if/when a full copy runs.
There is a second cost: the resequencing walk is `O(audit-chain-depth)`, capped at `MAX_OUT_OF_ORDER_AUDIT_DEPTH = 1000`, and is the source of the replication full-copy OOM in #1114. Beyond the cap the merge is an approximation until the full-copy lands.
## Root cause
Operation-based replication of a non-idempotent operation requires exactly-once delivery *and* application. Harper's replication doesn't provide that cheaply, so the exactly-once property is reconstructed per-record from the audit log — which is where both the fragility (best-effort dedup) and the cost (`O(depth)` walk, #1114 OOM) come from.
## Proposed direction: a state-based (convergent) counter
Replace the op-replicated counter with a **PN-counter**: each node stores its own contribution, and the record's value is derived from all contributions.
- Each counter field carries a per-node map `{ nodeId -> { added, subtracted } }` (monotonically increasing totals).
- The observable value is `Σ added − Σ subtracted` across nodes.
- Merge is **per-node max** of each total — idempotent, commutative, and associative.
With this shape, re-delivery and out-of-order delivery are no-ops: applying the same node's totals twice is a max against an equal-or-smaller value. That removes the need for the resequencing walk and its dedup guards *for counters*, and eliminates the #1114 OOM contribution from counter history.
## Tradeoffs and open questions (caveat emptor)
- **Storage grows with cluster size** — a counter's footprint is O(nodes) rather than a scalar. For wide clusters with many counters this is non-trivial; may want a compaction/tombstone story for departed nodes.
- **Format + wire change** — the stored representation and the replicated payload both change. Needs a migration from existing scalar counters (probably: treat an existing scalar as node 0's initial `added`).
- **Interaction with the audit log and time-travel** — the audit/`getRecordAtTime` reconstruction path assumes scalar deltas; a state-based counter changes what a historical read reconstructs (see #1413 for the current reverse-reconstruction correctness work).
- **Scope** — this is a design change, not a bug fix. It's worth doing only if we expect counters to matter under real replication churn; if they're rare, hardening the existing dedup may be the better spend.
## Related
- #1114 — full-copy OOM from the per-record audit-chain walk this would remove for counters.
- #928 — CRDT advanced operations (merge/diff/patch); adjacent CRDT surface.
- #1413 — reverse-reconstruction correctness for the *read* path (distinct concern; a state-based counter would change its inputs).
Filed as a design/architecture discussion — the immediate correctness fixes to the existing op-based path are being handled separately.
🤖 Filed by Claude (Opus 4.8) on behalf of Kris.
Contributor guide
Research direction
Start by reading resources/Table.ts, especially the out-of-order resequencing walk and the commit callback in _writeUpdate, then inspect the audit and getRecordAtTime reconstruction paths. Review the related issues #1114, #928, and #1413. Done requires resolving the PN-counter format, migration, wire representation, audit-history behavior, and whether this design is worth implementing.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- javascript, node.js
- Domain
- databases, distributed-systems
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100