Skip to content

Record history rebuilds each patch entry from scratch, so listing a record's history costs n² audit reads #3569

Closed

Description

@kriszyp

Problem

getHistoryOfRecord, getHistory, read_audit_log and superseded subscription replay rebuild every patch entry on its own, through getRecordAtTime (resources/crdt.ts). Each call walks back from the live record to the entry, and a field whose value it cannot recover by reversal triggers a second walk forward from the record's last full put. Listing a record's history therefore costs about n² audit reads for n patches. A single recent snapshot of a record with a long patch-only history costs n reads.

Fields that take the forward walk: plain fields set by a newer patch (already the case on main), and, after the fix for the #1413 absent-field residue (branch fix/history-absent-fields-at-time), add-only counters whose reversed value is 0 or that have a fractional delta. Those walks are what makes the value exact: 0 cannot be told apart from "absent before the add established it", and float reversal leaves a residue.

Measured on that branch, with the box under load (audit-read counts are exact): one snapshot behind the head costs n+2 audit reads, about 12–15 ms at n=1000 and 45–86 ms at n=5000 on RocksDB. getHistoryOfRecord on 5000 patches takes 143–175 s on LMDB.

Suggested direction

  • History listings: replay each record forward once, oldest first, carrying the folded state across entries, instead of rebuilding every entry from the live record.
  • Single snapshots: settle the unknown keys walking backward from the entry, and stop once each one hits a put, a delete, or a plain set, instead of always replaying from the last put.

Review-Deferral: 6148b771cf8b67ff severity=minor category=performance

🤖 Generated by Claude Opus 5.5 (Claude Code dev-agent); posted via @kriszyp.

Activity

  1. added theissue type on Oct 26, 2026
  2. self-assigned this
    on Nov 5, 2026
  3. kriszyp commented on Nov 12, 2026

    @kriszyp
    MemberAuthor

    Fixed on main by Keep a record's audit history readable after it is evicted (#3504) (9d77c42, v5.4).

    The test was one RocksDB record, written once and then patched 2,880 times. It compared main at 9d77c42 with its parent. Audit reads were counted by instrumenting the audit store. Each run was single, on a shared machine.

    Path Before: wall / CPU After: wall / CPU Before: range / point reads After: range / point reads
    getHistoryOfRecord 68.9 s / 132.0 s 192 ms / 299 ms 8.30M / 16.59M 0 / 2,882
    getHistory() 71.7 s / 132.9 s 220 ms / 359 ms 8.30M / 16.59M 5,760 / 2,882
    read_audit_log (hash_value) 69.2 s / 132.1 s 145 ms / 230 ms 8.30M / 16.59M 0 / 2,882
    read_audit_log (timestamp) 71.7 s / 133.0 s 250 ms / 362 ms 8.30M / 16.59M 5,760 / 2,882

    All four paths now go through historyEntryReader → HistoryReader.read. That builds each patch's value from the previous entry's, so reads grow linearly with the number of patches. Results were checked against the data: the length is N+1, and the values at the midpoint and the end are correct.

    The durable MQTT replay path (#3032) is not covered by this fix. It still reads quadratically and stays open. A fix for it is queued.

    — Claude Opus 5.5 (on behalf of Kris)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

Fields

Priority

P3

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions