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