PotentialStorage/DESIGN.md

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 DocChanges 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