Claude
cb9ff514a0
CI / Node 22 (push) Successful in 13s
CI / Node 24 (push) Successful in 13s
CI / Node 26 (push) Successful in 14s
CI / Node 22 (pull_request) Successful in 12s
CI / Node 24 (pull_request) Successful in 13s
CI / Node 26 (pull_request) Successful in 14s
CI / Chromium (push) Successful in 46s
CI / Publish to staging registry (push) Successful in 9s
CI / Chromium (pull_request) Successful in 45s
CI / Publish to staging registry (pull_request) Skipped
- Requests carry a random X-Nonce, signed as ${timestamp}:${nonce}:${path}:${body}. The
server rejects a nonce the same key already used within the timestamp window. Identical
requests at the same moment (two tabs, parallel reads) are now distinct, replacing the
per-process increasing-timestamp workaround.
- Composite: a sync no longer reverts keys with local writes the source hasn't confirmed
yet (in flight or queued); they briefly disappeared when a sync's scan ran before the
write reached the source. Pending keys are reloaded from a persistent queue on start.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_017Qxbkp4tA7G5SCWjzWuxmE
322 lines
22 KiB
Markdown
322 lines
22 KiB
Markdown
# PotentialStorage — Design
|
||
|
||
Layered TypeScript storage: **KV → Events → Documents**. Each layer is an abstract base class
|
||
that implementations extend; each is usable on its own. No runtime dependencies.
|
||
|
||
This supersedes the original implementation brief (see git history before the `simplify` branch);
|
||
section 7 lists what changed and why.
|
||
|
||
## 1. Principles
|
||
|
||
1. **One abstract class per layer.** Implementations provide a handful of raw primitives; the
|
||
whole user-facing API is written once in the base class. A client (e.g. HTTP) and a server-side
|
||
store are the same kind of object, and wrappers (e.g. encryption) are just another subclass
|
||
that delegates the primitives.
|
||
2. **One navigation primitive: `child(key)`.** Every instance is a node; `child` returns a view of
|
||
the same storage rooted deeper (via `Object.create`, so it shares the instance's state). Sync, no I/O.
|
||
Child nodes are **frozen**: an implementation that reassigns a field while running on a child
|
||
would silently shadow the root's value, so that throws instead. Implementations keep mutable
|
||
state in a `readonly state` object or in Maps.
|
||
3. **Self or child by argument.** `get()` reads this node, `get(key)` a child. A key that is passed
|
||
but `undefined`/`null` throws (`InvalidKeyError`) instead of silently meaning "self". Methods use
|
||
optional parameters or tuple-union rest parameters, not overloads.
|
||
4. **Indexes belong to the store.** Document stores receive the fields to index and use them however
|
||
suits the backend (in-memory equality maps, native Mongo/SQLite/IndexedDB indexes, or nothing).
|
||
5. **Simple over clever.** Code style: classes, TS `private` (not `#`), no method overrides in
|
||
subclasses, tests only under `test/`.
|
||
6. **No runtime dependencies.** Third-party code is vendored into `src/utils/` with a header naming
|
||
its source: `sse-session/` (Harvmaster/sse-session), `event-emitter.ts` and `extended-json.ts`
|
||
(xo-cash-utils, branch installable-sse). Node ≥ 22; CI runs Node 22, 24 and 26.
|
||
|
||
## 2. Layout
|
||
|
||
```
|
||
src/
|
||
kv-storage/ base-kv-storage.ts, kv-storage-in-memory.ts, kv-storage-indexeddb.ts,
|
||
kv-storage-http.ts, kv-storage-http-server.ts, kv-storage-composite.ts,
|
||
kv-storage-encrypted.ts
|
||
event-storage/ base-event-storage.ts, event-storage-kv.ts
|
||
document-storage/ base-document-storage.ts, document-storage-in-memory.ts, document-storage-kv.ts,
|
||
event-sourced-document-storage.ts
|
||
utils/ keys, sorted-map, json, extended-json, event-emitter, ulid, errors, schema (types),
|
||
document-path/query/update, sse-session/ (vendored)
|
||
test/ mirrors src/; shared suites: kv-storage.conformance.ts, document-storage.suite.ts;
|
||
browser/ runs in headless Chromium against a real cross-origin server;
|
||
readme.test.ts runs the README's examples
|
||
bench/
|
||
```
|
||
|
||
## 3. Keys (`utils/keys.ts`)
|
||
|
||
- A node's key is its escaped path segments joined by `/` (`users/123`). The separator is fixed.
|
||
- **Escaping:** every character at or below `/` (space, `!"#$%&'()*+,-.`, `/`, control characters)
|
||
and `~` itself becomes `~XX` (uppercase hex). Escaped segments contain only characters above `/`,
|
||
so all keys of one child sort together (`p/a`, `p/a/…`, then `p/a~2D1` for `a-1`). That keeps
|
||
child listing a plain skip-scan.
|
||
- **Reserved segments** are `~` + a lowercase letter (`~e` = event commits). Escaping only produces
|
||
`~` + uppercase hex, so user keys can't collide.
|
||
- Keys sort lexicographically by escaped form (`10` before `9`; `a-1` → `a~2D1` after `a0`).
|
||
- Empty keys, `NaN`/`Infinity` and non-string/number keys are rejected.
|
||
|
||
## 4. KV storage
|
||
|
||
`BaseKVStorage` primitives (absolute keys). Implementations provide two reads and one protected
|
||
write; the public `writeMany(changes)` / `removeMany(keys)` live in the base class and emit a
|
||
`change` event after each write, so every store emits change events.
|
||
|
||
| Primitive | |
|
||
| ------------------------------------------- | ---------------------------------------------------------------------------------------------------- |
|
||
| `readMany(keys)` | values in order, `undefined` for missing |
|
||
| `scan({ gte, lt, limit, reverse, values })` | key-ordered; must keep working if keys change mid-scan (keys present throughout appear exactly once) |
|
||
| `write(changes)` → public `writeMany` | `{ key, value }` sets, `{ key }` deletes, in one batch |
|
||
|
||
There is no conditional write. Stores execute exactly the operations they are given, and the last
|
||
write wins. Data that can be written concurrently belongs in event storage (section 5), where
|
||
concurrent appends never touch the same key. Data whose key is the hash of its content is
|
||
immutable, so concurrent writes of it are identical.
|
||
|
||
**Values** are JSON plus `bigint` and `Uint8Array` (as in JSON, `-0` becomes `0` and `undefined` properties are dropped). Anything crossing the network is encoded as
|
||
Extended JSON (`<bigint: 123n>`, `<uint8array: abcd>`); IndexedDB stores them natively.
|
||
|
||
**Events** (`EventEmitter`, shared by all nodes of a storage): `change` →
|
||
`{ changes: { key, value? }[], origin: 'local' | 'remote' }` (no `value` = removed), and
|
||
`resync` → changes may have been missed, so re-read.
|
||
|
||
Node API (defined once): `child`, `as`, `get(key?)`, `getMany`, `set(value)` / `set(key, value)`,
|
||
`setMany`, `setFields({ a, b })` / `getFields()` (direct children as an object), `delete(key?)`,
|
||
`deleteMany`, `deleteTree(key?)`, `keys({ limit, after, reverse })`, `entries(...)`. The root has
|
||
no own value. A node's own value and its children are independent keys.
|
||
|
||
- **`keys()`** is a skip-scan: one seek per child that has descendants; siblings without
|
||
descendants share one iterator. It lists children that only have descendants, and skips
|
||
reserved segments.
|
||
- **The only KV "index" is the ordered key space.** There is no `find`: with KV you know where to look,
|
||
or you list a node's children.
|
||
- **Implementations:**
|
||
- `KVStorageInMemory`: `SortedMap` (sorted chunks of ≤1024 keys); values deep-copied.
|
||
- `KVStorageIndexedDB`: one object store with string keys. Scans read in batches, each in its own
|
||
transaction, resuming after the last key (IndexedDB transactions close when the code awaits
|
||
anything else). A write is one readwrite transaction.
|
||
- `KVStorageHttp` (client) and `KVStorageHttpServer` (wraps any KV storage;
|
||
`handle(Request) → Response`): `POST /readMany`, `/write`, `/scan` with Extended JSON bodies;
|
||
`scan` streams NDJSON. Unreachable server (fetch failure, 502/503/504) →
|
||
`StorageUnavailableError`. The server executes exactly what clients send and never reads values
|
||
for decisions, so values can be encrypted end to end.
|
||
- `KVStorageComposite`: see 4.2. `KVStorageEncrypted`: see 4.3.
|
||
- **CORS.** `allowOrigins` (`['https://app…']` or `'*'`; default none) answers preflights and adds
|
||
`Access-Control-Allow-Origin` for allowed origins. Allowed request headers: `content-type`,
|
||
`cache-control` (sent by `SSESession`), `last-event-id` and the auth headers.
|
||
- **Change stream (SSE).** `POST /events` with `{ paths }` streams every change to those keys and
|
||
their subtrees as `event: change` (data: the changes), including the subscriber's own writes.
|
||
`event: ready` follows each connection; keep-alive comments are sent every 15 s. The server keeps
|
||
no history: nothing is replayed after a reconnect.
|
||
- `KVStorageHttp.subscribe(path = this.key)` / `unsubscribe(path)` / `close()` manage the
|
||
subscribed paths. Each change reconnects the stream (vendored `SSESession`, backoff) with the
|
||
new list; `subscribe` resolves once connected. A 401/403 rejects instead of retrying.
|
||
- The client emits each pushed batch as `change` (`origin: 'remote'`), and `resync` whenever the
|
||
stream reconnects after a drop, since changes may have been missed meanwhile.
|
||
- One SSE connection per `KVStorageHttp` instance. Browsers allow 6 HTTP/1.1 connections per
|
||
host, so apps should share one client per server (or use HTTP/2); `close()` releases it.
|
||
- Limitation: a server only sees writes made through its own storage instance, so several server
|
||
processes over one database need a shared pub/sub (not built).
|
||
- **Wrappers** (e.g. a future encryption layer) extend `BaseKVStorage` and delegate the primitives.
|
||
Keys must stay plaintext (or be deterministically encrypted) for prefix scans to work; values can be
|
||
encrypted freely.
|
||
|
||
### 4.1 Authentication (`utils/request-auth.ts`)
|
||
|
||
The server requires `auth`: either `{ verifiers, maxSkewMs?, now? }`, or `'none'` (open, for local
|
||
development and tests). It can't be left open by omission.
|
||
|
||
- **Signed requests.** The client's `RequestSigner` signs `${timestamp}:${nonce}:${path}:${body}`
|
||
(nonce = 16 random bytes as hex, fresh per request; path = URL pathname; body = the exact request
|
||
body). Based on Harvmaster/sync-server-example, plus the nonce. Headers: `X-Public-Key`
|
||
(lowercase hex), `X-Timestamp` (ms), `X-Nonce`, `X-Signature` (hex) and `X-Signature-Algorithm`.
|
||
Every request is signed, and so is each SSE (re)connect, with a fresh timestamp and nonce.
|
||
- **Verification (401).** The server picks the `SignatureVerifier` registered for the algorithm
|
||
(unknown → 401), checks the nonce format (16–128 characters of `[0-9A-Za-z_-]`) and that the
|
||
timestamp is within `maxSkewMs` (default 60 s). It then rejects a nonce the same public key
|
||
already used within that window (replay protection), and verifies the signature over the
|
||
received timestamp, nonce, path and raw body. The body is parsed only afterwards.
|
||
- **Why a nonce.** Ed25519 signatures are deterministic, so without it two identical requests
|
||
from one key at the same millisecond (two tabs or devices subscribing to the same path, parallel
|
||
identical reads) would be indistinguishable, and the second rejected as a replay.
|
||
- **Algorithms are pluggable.** Built in: `Ed25519Signer` / `Ed25519Verifier` (WebCrypto, so no
|
||
dependencies; Node 22+ and current browsers; keys persist as PKCS #8). Others, e.g. secp256k1 via
|
||
libauth, implement `RequestSigner` (`algorithm`, `publicKey`, `sign`) and `SignatureVerifier`
|
||
(`algorithm`, `verify`). The server can accept several algorithms at once.
|
||
- **Authorization (403): the public key is the user id.** Every key in `readMany` and `write`, and
|
||
every subscription path, must be `<publicKey>` or under
|
||
`<publicKey>/`. A scan must stay within `[<publicKey>, <publicKey>0)`, i.e. the key and its
|
||
subtree (escaping guarantees no other key falls in that range, including lookalikes such as
|
||
`<publicKey>x`).
|
||
- **Scoped events.** Each subscriber only receives changes under its own (authorized) paths.
|
||
- Proxies must preserve the URL path, because the signature covers it.
|
||
|
||
### 4.2 `KVStorageComposite({ source, replicas, queue?, prefix?, retryMs? })`
|
||
|
||
Keeps local copies of a source (e.g. `KVStorageHttp`) so reads are local and the app works
|
||
offline. With `prefix` (e.g. the user's public key) only that key and its subtree are synced, cached
|
||
and subscribed to; keys outside it throw `RangeError`. Without it, the whole source is copied, which
|
||
is only appropriate when the client may read all of it.
|
||
|
||
- **Replicas** are listed fastest first (e.g. `[inMemory, indexedDb]`); the last one seeds the
|
||
others on start. Reads come from the first.
|
||
- **The queue** is any KV store (default: in memory). It holds writes the source couldn't take
|
||
(`writes/<ulid>`) and whether a sync has completed (`synced`). Use a persistent node outside the
|
||
synced range, e.g. `indexedDb.child('~sync')` with `prefix: userKey`; a queue inside the range is
|
||
refused, since a sync would delete it.
|
||
- **Writes** are applied to every replica, then sent to the source, exactly as given.
|
||
- Applying locally first means the source relaying the write back finds nothing new.
|
||
- A write the source refuses (e.g. 403) is undone locally and rethrown.
|
||
- On `StorageUnavailableError`, or while a sync runs or writes are queued (to keep order), the
|
||
write goes to the queue and is sent later. The last write to reach the source wins.
|
||
- A queued write the source refuses on replay is dropped (retrying would block every later
|
||
write), the source's values for its keys are restored locally, and it is reported to `onError`.
|
||
- **Remote changes** pushed by the source are applied and announced (`change`, `origin: 'remote'`)
|
||
only where they differ from what the first replica holds. No write tagging or echo tracking is
|
||
needed: echoes of this client's writes change nothing.
|
||
- **`sync()`**: replay the queue in order (send, then re-apply locally) → merge-scan the source
|
||
against the last replica (both key-ordered), applying the difference in batches of 500, except
|
||
for keys with local writes the source hasn't confirmed yet (in flight or queued; counted per
|
||
key, and reloaded from a persistent queue on start), which would otherwise briefly revert →
|
||
replay again (writes made meanwhile) → mark `synced`. It runs on start, on `resync` (the stream
|
||
reconnected), and `retryMs` after a failure while offline. Called while a sync is running, it
|
||
schedules one more after it (shared by all callers meanwhile), so changes after the running
|
||
sync's scan aren't missed; e.g. the sync after subscribing, which closes the gap between the
|
||
first scan and the stream connecting.
|
||
- **Reads** wait for the first sync. Until one has completed, they go to the source. With a
|
||
persistent queue, a restart reads locally straight away (offline too).
|
||
- `start()` (also lazy on first use), `sync()`, `queued`, `close()`; `onError` receives errors no
|
||
caller can be rejected with (refused queued writes, failed syncs). Default `console.error`.
|
||
- Limitations: catching up re-scans the whole range (no server history); a remote change can
|
||
overwrite a value whose write is still queued until that write is replayed (last write wins);
|
||
replicas, source and queue must be root stores (the primitives use absolute keys).
|
||
|
||
### 4.3 `KVStorageEncrypted(inner, { key })`
|
||
|
||
Encrypts values before they reach another KV storage (usually `KVStorageHttp`), so the server only
|
||
stores ciphertext.
|
||
|
||
- AES-GCM (WebCrypto) with a fresh 96-bit random IV per write. Stored value: `Uint8Array`
|
||
`[1 (format), iv (12), ciphertext + tag]`. The storage key is the additional authenticated data,
|
||
so a value moved to another key, or altered, fails to decrypt (`Error`, with the cause).
|
||
- Keys stay plaintext (the server needs them for authorization, ordering and prefix scans); value
|
||
sizes and timing are visible.
|
||
- Remote `change` events from the inner storage are decrypted (in order) and re-emitted; `resync`
|
||
and `subscribe` / `unsubscribe` pass through, so it works as a composite `source`.
|
||
- Keys: `generateKey()` (extractable), `exportKey` / `importKey` (raw), `deriveKey(password, salt,
|
||
iterations = 600 000)` (PBKDF2-SHA-256, not extractable). No key rotation yet.
|
||
|
||
## 5. Event storage
|
||
|
||
`BaseEventStorage` primitives over stream paths: `appendTo(stream, events)` → ids,
|
||
`readFrom(stream, { after, limit, reverse })`, `streamsOf`. Node API: `append(events)` /
|
||
`append(key, events)` → ids, `read(opts?)` / `read(key, opts?)` → `{ id, at, data }`, `keys()`.
|
||
The root is not a stream.
|
||
|
||
**Appends never conflict.** Concurrent writers each add their own events, and every reader sees all
|
||
of them in the same order. There are no versions and no `expectedVersion`; folding events into
|
||
state is where concurrent changes meet (see event-sourced documents).
|
||
|
||
**`EventStorageKV`** (on any KV storage): each event is one plain KV write,
|
||
`<stream>/~e/<time:15>_<sha256(time + canonical Extended JSON of the event)>` → the event.
|
||
|
||
- Keys sort by time, so a stream reads in time order with one scan; `after` is an exclusive id.
|
||
- Events from different writers in the same millisecond order by hash: arbitrary, but the same for
|
||
every reader. One instance never reuses a time, so its own appends keep their order.
|
||
- The id can be recomputed from the content, and re-sending an event (e.g. a retried request)
|
||
writes the same key, so it can't be duplicated.
|
||
- An append is one `writeMany`, so it works through `KVStorageComposite` offline and syncs like any
|
||
other data.
|
||
|
||
## 6. Document storage
|
||
|
||
`BaseDocumentStorage` primitives over document paths:
|
||
|
||
| Primitive | |
|
||
| ------------------------------ | -------------------------------------------------------------------------------------------------------------------------------------- |
|
||
| `readMany(paths)` | |
|
||
| `mutate(path, change)` | maps current state → `DocChange` (or `null` = no-op), applies it, returns the new state; the implementation decides how it's made safe |
|
||
| `query(parent, DocumentQuery)` | children of `parent`, filtered, sorted and paged |
|
||
|
||
Node API: `get(key?)`, `getMany`, `set(doc)` / `set(key, doc)`, `insert(doc)` → ULID-like id,
|
||
`update(spec, opts?)` / `update(key, spec, opts?)` → new state or `undefined` (`{ upsert }`),
|
||
`delete(key?)` → existed, `find(filter, { sort, limit, skip })`, `findOne`, `keys()`.
|
||
|
||
- **Queries** (`utils/document-query.ts`): `{ field: value }` (dot paths; `null` also matches missing),
|
||
`$eq $gt $gte $lt $lte $in`. Comparisons are type-bracketed. On arrays a condition matches the array
|
||
or any one element. Sorting order: missing/null < booleans < numbers < strings < other.
|
||
- **Updates** (`utils/document-update.ts`): `$set $unset $inc $push $pull $addToSet` (`$each` for
|
||
push/addToSet). They resolve to a `DocChange` with final values (`$inc` → `set: { n: 6 }`), so
|
||
changes replay deterministically.
|
||
- **Indexes:** `{ indexes: { users: ['email', 'age'], 'users/*/posts': ['createdAt'] } }`, passed to
|
||
the implementation.
|
||
|
||
**Implementations**
|
||
|
||
- `DocumentStorageInMemory`: maps per collection; equality index per declared field (used for
|
||
`{ f: v }` / `{ f: { $eq: v } }`), otherwise scans. Writes are atomic in-process.
|
||
- `DocumentStorageKV`: each document is the KV value at its path; queries scan the collection's
|
||
children; no indexes; concurrent writes to one document are last-writer-wins.
|
||
- `EventSourcedDocumentStorage(events, projections)`: each document's `DocChange`s are appended to
|
||
its own stream. Current state lives in **any** `BaseDocumentStorage` used as the projection store,
|
||
which serves all reads, queries and indexes.
|
||
- A write reads the projection, resolves the change (`$inc` → `set: { n: 6 }`), appends it, and
|
||
applies it to the projection.
|
||
- Concurrent edits to different fields both survive; the same field ends with the later event's
|
||
value. (Increments from two devices don't add up: each resolves to a final value.)
|
||
- Events written elsewhere (another device, arriving through sync) are folded in by
|
||
`catchUp(key?)`, which rebuilds the projection from the whole stream. It also repairs a
|
||
projection left behind by a crash between append and projection write.
|
||
- Extras: `history(key?)`, `getAt(eventId)` / `getAt(key, eventId)`. Children keep these methods
|
||
in their types through interface declaration merging (types only).
|
||
|
||
## 7. Changes from the original brief
|
||
|
||
- Drivers + node classes → one abstract class per layer (client and server share an API).
|
||
- KV indexes (`findBy`, pattern trie, order-preserving value encoding, read-repair) removed.
|
||
Document indexes are declared as fields and handled by each store; unique indexes and the query
|
||
planner were removed.
|
||
- Queries: `$ne $nin $exists $and $or $not` and projections dropped.
|
||
- Separator fixed to `/`, and every character ≤ `/` is escaped so child keys stay contiguous. This
|
||
removed the subtree-order workaround in child listing.
|
||
- Event-sourced documents are events + a projection store instead of a bespoke projection format.
|
||
- No conditional writes and no versions: KV stores execute exactly what they're given (so a server
|
||
never needs to read values, which may be encrypted), and events get time + content-hash ids so
|
||
concurrent appends never collide. Optimistic concurrency (`expectedVersion`) was dropped.
|
||
- `tree()` removed (use `entries()` for field-per-key reads).
|
||
|
||
## 8. Open questions
|
||
|
||
- Composite: lazily syncing parts of a large subtree on first read; catching up without a full
|
||
re-scan (would need server-side history or a change log in event storage).
|
||
- Event-sourced documents: subscribing to event streams to run `catchUp` automatically.
|
||
- Authorization beyond "public key = user id" (sharing a subtree with other keys).
|
||
- Encryption: key rotation (re-encrypt, or a key id in the value format); sharing encrypted data
|
||
between users.
|
||
- Multi-process servers need a shared change feed (pub/sub) for SSE.
|
||
|
||
- Hard deletes from immutable event logs (privacy requests): compaction vs crypto-shredding. The
|
||
encryption wrapper could support per-subject keys.
|
||
- Order-preserving numeric keys (`9` before `10`) as an opt-in key encoding.
|
||
|
||
## 9. Benchmark baselines
|
||
|
||
`npm run bench`, in-memory stores, Node 22, Linux x64 cloud container (shared CPU, ±10–20%). Mean per operation.
|
||
|
||
| Benchmark | Mean |
|
||
| -------------------------------------------------------------------- | --------------- |
|
||
| KV `get` / `set` @ 10k keys | 1.5 / 1.7 µs |
|
||
| KV `get` / `set` @ 100k keys | 2.0 / 2.3 µs |
|
||
| KV `getMany` × 100 | 25–35 µs |
|
||
| `keys()` on 1k children × 100 descendants (skip-scan vs full scan) | 2.8 ms vs 34 ms |
|
||
| Event `append` (one SHA-256 via WebCrypto + one write) | 72 µs |
|
||
| Event `read` 100 from the middle of 10k | 119 µs |
|
||
| Event `read` full 10k stream | 11 ms |
|
||
| Event-sourced document `update ($inc)` | 86 µs |
|
||
| Documents in-memory @ 10k: `get` / `update` | 1.8 / 6.6 µs |
|
||
| Documents in-memory: `find` indexed (~100 hits) / scan (~200 of 10k) | 0.20 / 11 ms |
|
||
| Event-sourced @ 10k: `get` / `update` | 1.6 / 17 µs |
|
||
| Event-sourced: `find` indexed / scan | 0.38 / 12 ms |
|