# 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.
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/`.

## 2. Layout

```
src/
  kv-storage/        base-kv-storage.ts, kv-storage-in-memory.ts, kv-storage-http.ts, kv-storage-http-server.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, ulid, errors, schema (types), document-path/query/update
test/                mirrors src/; shared suites: kv-storage.conformance.ts, document-storage.suite.ts
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):

| Primitive                                   |                                                                                                      |
| ------------------------------------------- | ---------------------------------------------------------------------------------------------------- |
| `readMany(keys)`                            | values in order, `undefined` for missing                                                             |
| `writeMany(entries)`                        |                                                                                                      |
| `removeMany(keys)`                          |                                                                                                      |
| `writeIfAbsent(entries)`                    | `true` = written; atomic per key (needed by events)                                                  |
| `scan({ gte, lt, limit, reverse, values })` | key-ordered; must keep working if keys change mid-scan (keys present throughout appear exactly once) |

Node API (defined once): `child`, `as`, `get(key?)`, `getMany`, `set(value)` / `set(key, value)`,
`setMany`, `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);
  `KVStorageHttp` (client) + `KVStorageHttpServer` (wraps any KV storage; `handle(Request) → Response`,
  `POST /<primitive>` with JSON bodies, `scan` streamed as NDJSON). The server exposes the whole
  underlying store (primitives use absolute keys).
- **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.

## 5. Event storage

`BaseEventStorage` primitives over stream paths: `appendTo`, `readFrom`, `versionOf`, `streamsOf`.
Node API: `append(events, opts?)` / `append(key, events, opts?)`, `read(opts?)` / `read(key, opts?)`,
`version(key?)`, `keys()`. The root is not a stream. An empty stream is version 0; the first event is 1.
`expectedVersion: number | 'any'` (default `'any'`).

**`EventStorageKV`** (on any KV storage):

- One key per append, densely numbered: `<stream>/~e/<commit:12>` → `{ firstVersion, at, events }`.
  Keying by commit number (not version) means any writer with a stale view collides with the
  existing key.
- Append: head from a bounded cache (else one reverse scan, `limit: 1`) → check `expectedVersion`
  (re-reading the head before rejecting, in case the cache is stale) → `writeIfAbsent`. On a lost race:
  `ConcurrencyError` if a version was expected, otherwise retry (default 5).
- `read({ from })`: commit `n` starts at a version ≥ n, so try commit `from` first (exact for
  single-event commits), else binary-search; then forward-scan.
- Multi-writer safe on any store, because `writeIfAbsent` is a required primitive.

## 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.
  - Projections carry `_version` (reserved; stripped from results), used as `expectedVersion` on the
    next append.
  - If a write crashes between append and projection update, the next write conflicts, rebuilds the
    projection from the stream, and retries. `catchUp(key?)` rebuilds on demand.
  - Missing projections with stream history (deleted documents, crashed first writes) are rebuilt
    before writing.
  - Writes to one document are serialised in-process, so retries only happen across processes.
  - Extras: `history(key?)`, `getAt(version)` / `getAt(key, version)`. 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.
- `writeIfAbsent` is a required primitive (no single-writer mutex fallback; no optional `batch` /
  `deleteRange`).
- `tree()` removed (use `entries()` for field-per-key reads).

## 8. Open questions

- 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` (warm cache)                                          | 7.8 µs          |
| Event `read` 100 from version 5 000 of 10k                           | 131 µs          |
| Event `read` full 10k stream                                         | 18 ms           |
| 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    |