Replicated documents and Arrow-native overrides

Scope

polars-hist-db provides Yjs-compatible documents for collaborative drafts and an Arrow-native immutable operation-set CRDT for typed valid-time overrides. The Arrow operation stream is the recommended override data plane. Arrow is the canonical in-process and wire representation; normalized native database columns are the durable representation. JSON is not an intermediate override representation.

An optional access registry persists document lifecycle and opaque group-to-role grants. Applications own authentication, authorization policy, transport, field declarations, and business conflict policy.

The implementation uses the maintained Yjs/Yrs ecosystem instead of implementing a CRDT algorithm. Browser clients use Yjs. Python services use pycrdt, whose Yrs updates are binary-compatible with Yjs. Binary updates are commutative, associative, and idempotent, so every backend stores the same protocol rather than implementing its own merge rules.

Yjs compatibility path

The document model below remains supported for collaborative document state and existing operation-map integrations. New typed override flows should keep mutable draft text in Yjs and publish immutable changes into the Arrow operation data plane. This prevents Yjs/JSON scalar encoding from becoming authoritative for database value types while preserving offline draft editing.

Document model

The library does not prescribe a complete application schema. It reserves two conventions for reusable override documents:

root
  drafts       application-owned Y.Map/Y.Array/Y.Text collaborative state
  operations   Y.Map keyed by immutable operation_id

Draft values may be edited, removed, and undone. Published operation entries are immutable. An application may add other shared types without changing the storage contract.

Each value in operations has this backend-independent envelope:

Field Type Rule
format_version integer 1 for this contract
operation_id UUID Caller-generated idempotency key; globally unique
change_set_id UUID Groups one multi-field action
layer_id string Override layer identity
actor_id string Server-derived principal finalized at acceptance
feed_id string Source dataset identity
entity_id string Stable source entity identity
field_path string Field or nested path being overridden
operation_type enum set or remove
value OverrideTypedValue or null Required for set only
supersedes_operation_ids array of UUIDs Values observed and replaced by set
removes_operation_ids array of UUIDs Values observed and closed by remove
valid_from UTC timestamp Inclusive business-valid start
valid_to UTC timestamp or null Exclusive business-valid end
recorded_at UTC timestamp Server time finalized at acceptance
payload_hash string Server-computed hash of immutable persisted fields
observed_canonical_value_json JSON or null Source value seen by the editor
comment string or null Immutable snapshot of any collaborative rationale
metadata_json object Versioned extension data only

Concurrent published edits use different operation IDs and therefore coexist in the map. Explicit supersede/remove references preserve business conflicts; Y.Map’s scalar conflict choice is never used to choose an effective override.

An offline client creates a provisional entry without authoritative actor_id, recorded_at, or payload_hash. After applying and validating that entry in a temporary document, the server replaces it causally with a finalized entry containing those fields. It persists and broadcasts the combined server-origin update. Subsequent replay of the provisional client update is idempotent and cannot supersede the finalized value. Once finalized, any mutation or deletion of the operation is rejected.

Synchronization

Clients persist documents locally and may create changes without a network. On reconnect they exchange state vectors and only missing Yjs updates. The library stores opaque update bytes and can reconstruct or merge a document with pycrdt; it does not define HTTP, WebSocket, NATS, or peer-to-peer transport.

The accepting service uses optimistic compare-and-swap on the document revision. It does not require a cross-backend lock abstraction:

  1. load the latest accepted document and revision;
  2. apply the source update to that state in a temporary document;
  3. reject mutation/deletion of existing operations and validate new operations;
  4. authorize the current principal against the resulting document state;
  5. replace provisional operations with server-finalized entries;
  6. derive one accepted update relative to the state loaded in step 1;
  7. atomically compare-and-swap the revision, append that update, and insert its relational operation projection;
  8. on a revision conflict, repeat from step 1 or return a retriable conflict;
  9. broadcast only after the commit succeeds.

Rejected updates are never broadcast or persisted. The client keeps them in a quarantined local branch so work can be copied or retargeted, but it must reset the shared document to the last accepted server state before further sync.

Presence and undo

Presence, selections, and cursor positions use the Yjs Awareness protocol. They are ephemeral, expire when a client disconnects, and are never written to the database or audit history.

Undo/redo is client-local and scoped to mutable draft/shared-text types. Undo must not track the immutable operations map. Reversing a published override creates a new remove or set operation so audit history remains append-only.

Override convergence

For one layer, feed, entity, field, and requested valid time:

  1. Select set operations whose half-open interval [valid_from, valid_to) contains the requested time.
  2. Discard a set referenced by an applicable remove.
  3. Discard a set referenced by an applicable superseding set.
  4. The remaining sets are the frontier. One distinct value is clean, several distinct values are concurrent, and no value means no override.
  5. Sort concurrent values by operation ID for stable output only.

Arrival order, client clocks, backend row order, and Y.Map scalar conflict selection never choose an effective value. Equal normalized values may be grouped for display while retaining all provenance.

Validation and idempotency

The reusable validator enforces:

  • unique and immutable operation_id entries;
  • timezone-aware UTC timestamps;
  • bounded set intervals with valid_to > valid_from;
  • set/remove value and reference rules;
  • references within the same layer, feed, entity, and field;
  • references to existing operations or earlier operations in one atomic batch;
  • exact replay as a no-op and conflicting reuse of an ID as an error.

Applications additionally validate the authenticated actor, permissions, allowed fields, document lifecycle, and domain value types.

Acceptance and repository boundaries

The implementation has three boundaries rather than one backend-shaped store:

  1. A pure acceptance function applies and validates Yjs updates with pycrdt. It produces a PreparedCrdtCommit containing the base revision, source and accepted update hashes, accepted update bytes, resulting state vector, and finalized operation rows.
  2. The application authorizes the prepared change and supplies any row guards and deterministic insert-only side effects required in the same transaction. Authentication and field policy do not enter the persistence adapter.
  3. A repository atomically commits the prepared change using compare-and-swap.

The source update is the untrusted client input. The accepted update is a server-origin update containing both the source change and causal replacement of provisional operation entries with finalized values. It is generated relative to the previously accepted state, so applying it once brings any replica at that state to the accepted state. Replaying the source update later cannot replace its causal server descendant.

Client-supplied actor_id, recorded_at, or payload_hash values are rejected. The server supplies one actor and acceptance timestamp for the request and computes each operation payload hash after finalization. A draft-only update is valid and produces no relational operation rows.

The repository contract is intentionally small:

load_document(document_id) -> CrdtDocument | None
commit(prepared_commit, guards=(), inserts=(), updates=()) -> CrdtCommitResult
write_snapshot(document_id, expected_revision) -> CrdtSnapshot

The optional atomic extensions are deliberately constrained:

RowGuard(table_config, key_values, expected_values)
AtomicInsert(table_config, row)
AtomicUpdate(table_config, key_values, expected_values, values)

A guard requires one current row matching its key and expected values. Typical uses are an active layer revision or the source row/version used during validation. An atomic insert adds a row with a deterministic primary key; typical use is a transactional outbox event. An atomic update is a constrained compare-and-swap used for a server-authoritative lifecycle revision in the same commit. There are no arbitrary SQL callbacks or cross-database participants.

commit has five portable outcomes:

  • accepted: revision advances exactly once and all rows are committed;
  • duplicate: the same source update was already accepted and revision does not advance;
  • revision conflict: another commit won the compare-and-swap and the caller must re-prepare against the latest document;
  • precondition failed: an application guard no longer matches and the caller must reauthorize or revalidate;
  • invalid/corrupt: validation, immutable-operation, hash, or reconstruction invariants failed and nothing is written.

Exact source bytes use source_update_hash as a fast retry key. A differently encoded Yjs update that adds no structs and leaves the state vector unchanged is also a no-op, but need not add a persistent hash alias. An exact retry returns the original accepted result without re-running write guards or insert side effects. The application still authorizes document access before returning that result.

The result includes the accepted update and new revision, so a service can respond and broadcast without an immediate database read. An adapter may also return an opaque consistency token. XTDB callers crossing connections use its await token; MariaDB normally needs no token.

The application-level retry loop is the same for every backend:

while True:
    current = repository.load_document(document_id)
    prepared = prepare_update(current, source_update, actor_id, recorded_at)
    guards, inserts, updates = authorize_and_build_side_effects(prepared)
    result = repository.commit(
        prepared, guards=guards, inserts=inserts, updates=updates
    )
    if not result.revision_conflict:
        return result

Authorization to access the document happens before returning either accepted or duplicate content and is repeated after each re-prepare. Repeated revision conflicts may be returned to the caller rather than retried without bound. Malformed updates, client-supplied authoritative fields, and application-defined size or operation-count limits are rejected before persistence. Rejected source bytes are not retained by this library.

Document access registry

Purpose and boundary

Collaborative applications need durable document lifecycle and membership state to authorize a CRDT update. Keeping that state only in application code would duplicate MariaDB and XTDB compare-and-swap behavior and make the CRDT commit guard impossible to construct portably.

The optional access registry therefore stores only:

  • immutable document identity, name, and description;
  • active or archived status and a monotonic access revision;
  • server-derived creation and archival audit fields;
  • audit-preserving group grants with an opaque application-defined role string;
  • grant and revocation audit fields.

It does not verify tokens, interpret group names, rank roles, decide capabilities, or expose HTTP/WebSocket/NATS APIs. Those remain application policy. It is not a general IAM framework.

API

config = DocumentAccessStoreConfig(
    schema="overrides",
    documents_table="document_access",
    grants_table="document_access_grants",
    commands_table="document_access_commands",
)
store = backend.document_access(connection, config)

store.create(document_id, name, description, actor_id, recorded_at,
             initial_grants=(), idempotency_key=command_id)
store.get(document_id)
page = store.list_for_groups(groups, include_archived=False, limit=100)
page.items
next_page = store.list_for_groups(groups, cursor=page.next_cursor, limit=100)
store.list_all(include_archived=False, limit=100)
store.grants(document_id, include_revoked=False, limit=100)
store.grant(document_id, grant_id, group, role, actor_id, recorded_at,
            expected_revision, idempotency_key=command_id)
store.revoke(document_id, group, actor_id, recorded_at, expected_revision,
             idempotency_key=command_id)
store.archive(document_id, actor_id, recorded_at, expected_revision,
              idempotency_key=command_id)
store.guard(document_id, expected_revision) -> RowGuard

List and history APIs return a Page: an immutable items tuple and an opaque next_cursor. Pass that cursor back unchanged to read the next page. Page sizes must be between 1 and 500.

create, grant, revoke, and archive return AccessMutationResult with the authoritative document, active grants, and one of accepted or duplicate. Exact command retries return the original result. Reusing an idempotency key with different content raises IdempotencyConflict. Unknown documents, archived documents, stale revisions, and missing active grants raise distinct typed errors. Applications map those errors to non-disclosing transport responses.

The application supplies actor identity only after token verification and uses its authoritative clock for recorded_at; no mutation accepts actor or audit fields inside an opaque payload. The application also validates names, allowed role values, caller permissions, and group naming policy. The store validates required identifiers, timezone-aware audit timestamps, status transitions, uniqueness, and expected revisions.

list_all is intentionally authorization-neutral. It exists for applications whose verified global administrators or auditors are not represented by a document grant. Calling it before application authorization is a security bug.

Use cases

  • Create a collaborative document and its initial group grants atomically.
  • List documents reachable through the caller’s current identity groups.
  • Add, revoke, or later re-add a group without losing grant provenance.
  • Archive a document irreversibly while preserving readable history.
  • Guard a CRDT acceptance transaction against a racing revocation or archive.
  • Retry a lifecycle command after an unknown network outcome without applying it twice.

Tables

document_access contains:

Column Rule
document_id immutable primary key
name, normalized_name immutable display name and unique case-folded key
description optional immutable text
status active or archived
revision starts at 1; advances for every grant/lifecycle mutation
created_by, created_at server-derived
archived_by, archived_at both null until archive

document_access_grants is audit-preserving. Its primary key is grant_id. active_group_key is a normalized (document_id, group_name) key while active and null after revocation; a unique constraint/assertion prevents two active grants for one group while allowing later re-grant. Revocation closes the current row through backend temporal versioning and never hard-deletes it. The table contains role, grant/revoke actors and timestamps, and the document revision at which each change became authoritative.

document_access_commands records idempotency_key, payload hash, result revision, command kind, recorded time, and the serialized backend-neutral AccessMutationResult. It contains no token or raw request payload. Storing the result allows an exact retry to return the original response even after later access mutations.

All three tables share the CRDT document/projection connection. Cross-database membership and CRDT writes are unsupported.

Concurrency and CRDT integration

Every mutation checks status = active and revision = expected_revision, applies its grant/lifecycle row, advances the document revision once, and records the command result in one transaction. A concurrent grant, revocation, or archive permits exactly one winner. The loser reloads and reauthorizes; it never retries using stale permissions.

Before accepting a CRDT update, an application reads the document and active grants, authorizes the caller, and passes store.guard(document_id, revision) to the existing prepared CRDT commit. The same access row is checked inside the CRDT transaction. An archive or revocation racing the update therefore either commits first and rejects the update, or commits after the accepted update at a later access revision.

An access mutation does not edit CRDT bytes, projected override operations, or public outbox data. Document deletion and unarchive are deliberately absent.

Backend semantics

MariaDB locks the access row, checks the expected revision, writes the grant or archive mutation, and updates the revision in one transaction. Unique indexes enforce document names, command IDs, and active grants.

XTDB submits one asserted DML transaction: assertions check command idempotency, active status, and expected revision; inserts create the new document/grant/command versions. Composite _id values use the existing table-config primary-key policy. The returned transaction token is awaited before a caller reads through another connection.

The in-memory implementation is the executable reference model. Backend contract tests run the same lifecycle scenarios against all three stores:

  • exact command retry and conflicting idempotency-key reuse;
  • case-insensitive document-name uniqueness;
  • concurrent expected-revision mutation with one winner;
  • grant, revoke, re-grant, and provenance retention;
  • archive racing grant and CRDT acceptance;
  • inaccessible document lookup left to application non-disclosure policy;
  • MariaDB/XTDB parity for rows, revisions, and failure outcomes.

Configuration

The equivalent YAML shape is:

document_access:
  schema: overrides
  documents_table: document_access
  grants_table: document_access_grants
  commands_table: document_access_commands

There is no backend selector in this block. The existing database backend owns adapter selection. Applications may use different table names, but the three tables must share one connection with the CRDT document and projection tables.

Implementation sequence

  1. Add config, immutable models, typed outcomes/errors, table configs, and the in-memory reference store.
  2. Add MariaDB storage using row locks, unique constraints, and one transaction per mutation.
  3. Add XTDB storage using one asserted DML transaction and consistency tokens.
  4. Run one shared contract suite against in-memory, MariaDB, and XTDB stores.
  5. Expose backend.document_access(...) and use its RowGuard in prepared CRDT commits.

No transport, token verifier, role hierarchy, or application-specific layer model belongs in these steps.

Library API

CRDT support is an optional crdt extra so ingestion-only users do not install Yrs bindings.

prepare_update(current_document, source_update, actor_id, recorded_at)
    -> PreparedCrdtCommit
load_document(document_id) -> CrdtDocument | None
commit(prepared_commit, guards=(), inserts=(), updates=()) -> CrdtCommitResult
diff(document, state_vector) -> bytes
write_snapshot(document_id, expected_revision) -> CrdtSnapshot

validate_override_changes(before, after) -> list[OverrideOperation]
project_operations(operations, valid_at) -> dict[str, OverrideFrontier]

prepare_update is backend-independent and performs all CRDT and immutable operation checks. commit deduplicates the source update, advances a monotonic storage revision, evaluates row guards, and writes relational projections and insert-only side effects in the same transaction. diff returns the Yjs update missing from a supplied state vector. The pure override projector is shared by every backend.

Storage

Every backend exposes equivalent logical tables:

crdt_documents(document_id, revision, head_state_vector_base64,
               snapshot_update_base64, snapshot_update_hash,
               snapshot_state_vector_base64, snapshot_through_revision,
               updated_at)
crdt_updates(document_id, revision, source_update_hash, accepted_update_hash,
             update_base64, accepted_at, metadata_json)

(document_id, revision) and (document_id, source_update_hash) are unique. source_update_hash is the SHA-256 idempotency key for the untrusted incoming bytes. accepted_update_hash is the SHA-256 checksum of update_base64 after server finalization. These hashes must be separate because finalization changes the Yjs update bytes. Update bytes, snapshots, and state vectors are opaque binary values at the API boundary and base64-encoded MEDIUMTEXT in relational storage. This gives MariaDB and XTDB the same logical schema without backend-specific blob types. In-memory storage follows the same revision and deduplication rules.

The merged table contract’s single update_hash and ambiguous state_vector_base64 are therefore transitional. Before a persistent adapter is released, the update hash must split into the two hashes above and the state vector must split into head and snapshot vectors. There is no data migration requirement until such an adapter has written rows.

crdt_updates is the append-only synchronization log. crdt_documents is its rebuildable head/snapshot record, not an independent source of truth. Each accepted commit updates the head revision and head state vector. Snapshot fields may lag the head revision and explicitly declare the revision they cover. snapshot_update_hash checks the stored snapshot bytes before they are parsed.

Snapshots contain a full merged Yjs update and state vector through a known revision. Updates covered by a verified snapshot may be archived, but the snapshot itself remains available to every rebuild path. Snapshotting is introduced with the storage contract because unbounded replay would make offline reconnect progressively slower; frequency remains application policy.

The relational valid-time projection remains configured independently:

override_ledgers:
  - schema: overrides
    table: data_override_operations
    valid_time:
      from_column: valid_from
      to_column: valid_to

Replicated projection rows add nullable crdt_document_id and crdt_document_revision provenance columns. They remain null for existing personal-ledger rows. The provenance makes per-document comparison and repair possible without inferring document membership from application-owned layer names.

owner_user_id is required by the personal command model but nullable in the shared projection schema. Shared rows use layer_id, actor_id, and CRDT document provenance; they never invent a personal owner. Existing deployments must relax the legacy NOT NULL constraint before shared rows are written.

The portable repository receives the existing two config objects:

document_store = CrdtDocumentStoreConfig(
    schema="overrides",
    documents_table="crdt_documents",
    updates_table="crdt_updates",
)
projection = OverrideLedgerConfig(
    schema="overrides",
    table="data_override_operations",
    valid_from_column="valid_from",
    valid_to_column="valid_to",
)
repository = backend.crdt_documents(connection, document_store, projection)

Backend selection remains part of the existing database configuration. No CRDT config contains mariadb or xtdb. The document, update, and projection tables must be reachable through one backend connection and one atomic transaction. Cross-database projection is outside this contract; it would require a durable outbox and an explicitly eventually-consistent projection.

A CRDT update may contain several valid-time operations, so the update’s acceptance time must never be used as their business valid time. CRDT storage is the synchronization source of truth; normalized operation rows are the SQL query/audit projection and must be reproducible from accepted snapshots and updates.

Atomic commit by backend

Both adapters implement the same compare-and-swap behavior, but use native transaction primitives. The library does not introduce a database-neutral SQL dialect or transaction wrapper; the repository outcomes are portable, while the statements that guarantee them are backend-specific.

For MariaDB, one transaction:

  1. checks (document_id, source_update_hash) for an exact retry;
  2. locks and verifies each application guard row;
  3. inserts the initial document head or conditionally updates it with WHERE revision = base_revision;
  4. inserts the immutable update row, finalized operation rows, and deterministic side-effect rows;
  5. commits only if every guard, insert, and revision comparison succeeds.

The document primary key, update primary key, source-hash unique constraint, and operation primary key enforce races. A failed conditional update or unique constraint rolls back the transaction; the adapter then distinguishes an exact retry from a genuine revision or operation-ID conflict.

XTDB DML transactions are serialized and atomic but not interactive, and XTDB has no uniqueness constraints beyond _id. Preparation therefore happens against a read snapshot, followed by one DML transaction containing:

  1. ASSERT that the source hash has not already been accepted;
  2. ASSERT every application row guard;
  3. ASSERT that the current document revision equals base_revision, or that no head exists for revision zero;
  4. the document-head write, immutable update insert, operation inserts, and deterministic side-effect inserts.

The update _id is derived from (document_id, revision) and each operation uses operation_id as _id. Source-hash uniqueness is enforced by the transaction assertion. Because XTDB DML transactions are serialized and atomic, concurrent assertions cannot both commit. If an assertion fails, the adapter rereads the source hash, application guards, and document revision. A source match becomes duplicate, a changed guard becomes precondition failed, and a changed revision becomes revision conflict. Any remaining assertion failure is invalid/corrupt rather than guessed. The pgwire path waits for transaction indexing and exposes the await token when later reads use another connection.

XTDB operation inserts explicitly map business valid_from and valid_to to _valid_from and _valid_to; acceptance/system time must never replace those values. MariaDB stores the same business timestamps in the configured columns.

Recovery and repair

A process crash before commit leaves no rows; a crash after commit leaves the update, head revision, and operation projection together. Broadcasting is post-commit and may be repeated because clients merge accepted updates idempotently.

If a connection fails while the commit outcome is unknown, the caller retries the same source bytes. A source-hash lookup resolves the ambiguity as either the existing accepted result or a new compare-and-swap attempt.

On load, the adapter rebuilds from the latest snapshot plus later updates and verifies the resulting state vector and accepted-update hashes. Missing or invalid bytes are reported as corruption rather than skipped. The operation projection can be rebuilt by extracting finalized entries from the reconstructed operations map and comparing payload hashes. Repair replaces derived head and projection state; it never rewrites the accepted update log.

Snapshot creation is a separate compare-and-swap operation. It reconstructs and verifies a document through revision N, then updates snapshot fields only if the head is still at N. Losing that race is harmless and the snapshot can be retried. Update archival remains deferred until a verified snapshot, restore test, and retention policy exist.

Sync cases

Case Required result
First update Create revision 1, append one accepted update
Exact source retry Return existing accepted result; no new rows
Concurrent offline drafts Re-prepare loser against latest state; both edits converge
Concurrent published values Persist both operation IDs; projector reports a conflict
Mutation/deletion of published operation Reject before commit
Duplicate operation ID with different payload Reject and write nothing
Draft-only collaborative text Persist CRDT update; write no operation rows
Projection insert failure Roll back update and head revision
Broadcast failure after commit Retry broadcast; do not recommit

Existing personal ledgers

Existing OverrideLedger rows remain valid and require no migration. Online personal edits may continue using the current command path. When personal offline editing is enabled, the same Yjs document and immutable operation conventions apply, with layer identity derived from the owner.

Test contract

  • A Yjs browser update can be loaded by pycrdt, and a pycrdt update can be loaded by Yjs.
  • Offline updates from two replicas converge after reconnect in either order.
  • Duplicate updates do not advance logical content or create duplicate rows.
  • Source-update retries deduplicate independently of accepted-update checksums.
  • Two commits prepared at one revision produce one acceptance and one retriable revision conflict, never a partial write.
  • Mutation or deletion of a published operation is rejected.
  • Undo affects local draft/text changes but cannot erase published operations.
  • Awareness data is not persisted.
  • Snapshots plus later updates reproduce the same document and override rows.
  • Projection failure rolls back the document head and update append.
  • Missing or corrupt accepted updates fail reconstruction instead of being silently skipped.
  • Head and snapshot state vectors are independently verified at their declared revisions.
  • MariaDB, XTDB, and in-memory adapters expose equivalent revision, binary, snapshot, and valid-time behavior.

Deferred work

  • Peer-to-peer transport. The initial topology remains authenticated client/server synchronization.
  • End-to-end encryption. Server-side authorization and projection require the server to inspect accepted documents.
  • A rich-text editor binding. Y.Text is the portable data model; applications select an editor appropriate to their UI.
  • Document deletion, unarchive, legal erasure, and retention policy. The access registry supports active-to-archived only; CRDT update archival remains disabled.