HarperFast / HarperFast/harper

CRDT counters are op-replicated with best-effort dedup; a state-based counter would make merges idempotent

Open
#1,614 0 comments 0 reactions 0 assignees View on GitHub
area:storage enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.