# PotentialStorage — Design

This document is the design brief agreed with the project owner (sections 0–11), followed by
implementation decisions made where the brief was silent (section 12) and benchmark baselines
(section 13).

## 0. Setup and workflow

- Repository: `git@git.harvmaster.com:Harvmaster/PotentialStorage.git` (SSH; self-hosted Git, not GitHub). Clone it. If you can't reach it, stop and tell the owner rather than starting a fresh repo elsewhere.
- Inspect what's already in the repo first. If it has tooling (package.json, tsconfig, test runner), keep it. If it's empty, set up:
  - TypeScript (`strict: true`, `noUncheckedIndexedAccess: true`), ESM, Node ≥ 20
  - Vitest for tests and `vitest bench` for benchmarks; `expectTypeOf` for type tests
  - Package name `potential-storage` unless one already exists
  - **No runtime dependencies in the core.** Dev dependencies are fine (e.g. `fast-check` for property tests).
- Copy this brief into the repo as `DESIGN.md` and create a short `CLAUDE.md` pointing at it plus the build/test commands.
- Work milestone by milestone (section 9). Commit after each milestone with a clear message, and keep tests green. Ask the owner before pushing.

## 1. Principles

1. **Three layers**, each usable on its own: **KV** → **Event** (append-only, built on KV) → **Document** (Mongo-like, built on Events or native).
2. **Drivers vs stores.** Backends implement a tiny, flat, string-keyed _driver_. All path, child, index, escaping and typing logic lives once in the user-facing _node_ classes, so every backend gets identical behaviour.
3. **One navigation primitive: `child(key)`.** There are no collection/document classes. Every node is a store over its direct children, and `child(key)` re-roots to that key. Navigation is synchronous and does no I/O.
4. **No methods on data.** Reads return plain values.
5. **Performance is a requirement.** Batch operations are the primitive; scans are ordered and streamed; nothing replays or scans more than it must (section 8).

## 2. Paths and key encoding (`src/core/path.ts`)

- A node's path is `readonly string[]` of **unescaped** segments. Number keys are converted with `String()`.
- The separator is a single character, configurable, default `/`.
- **Escaping** (per segment): percent-encode `%`, the separator, and a **leading** `~`. Escaped segments never contain a raw separator. Write `escapeSegment` / `unescapeSegment` with round-trip property tests.
- **Reserved segments** start with `~` (user segments can't, because a leading `~` is escaped):
  - `~i` index entries
  - `~u` unique-index claims
  - `~e` event commits
  - `~p` document projections root
- Each node precomputes in its constructor:
  - `selfKey` = escaped segments joined by the separator (e.g. `users/123`)
  - `prefix` = `selfKey + sep` (`''` for the root)
  - No string work per call beyond `prefix + escapeSegment(key)`.
- Keys are ordered **lexicographically** (so `10` sorts before `9`). Document this. An order-preserving numeric key encoding is a possible later option, not part of v1.

Example layout:

```
users/123                          → KV value of users/123
users/123/posts/p1                 → KV value of a nested child
users/~i/byEmail/sada@x.io/123     → index entry (value: empty / true)
orders/o1/~e/000000000007          → event commit #7 of stream orders/o1
~p/users/123                       → document projection { state, version, commit }
```

## 3. Layer 1: KV

### 3.1 Driver interface (`src/kv/driver.ts`)

```ts
export interface ScanOptions {
  gte?: string
  lt?: string
  limit?: number
  reverse?: boolean
  values?: boolean // when false/omitted, yield value as undefined
}

export interface KVDriver {
  getMany(keys: string[]): Promise<(unknown | undefined)[]> // same order as keys
  setMany(entries: [key: string, value: unknown][]): Promise<void>
  deleteMany(keys: string[]): Promise<void>
  scan(opts: ScanOptions): AsyncIterable<[key: string, value: unknown]> // MUST be key-ordered

  // Optional capabilities. Stores feature-detect them and fall back where possible.
  setIfAbsent?(entries: [string, unknown][]): Promise<boolean[]> // true = written
  batch?(ops: BatchOp[]): Promise<void> // atomic multi-op write
  deleteRange?(gte: string, lt: string): Promise<void>
}

export type BatchOp = { type: 'set'; key: string; value: unknown } | { type: 'delete'; key: string }
```

- Values are passed through as JSON-serialisable values. Drivers that need bytes (HTTP, Redis, files) serialise internally via a pluggable `Codec` (default JSON).
- Provide an abstract `BaseKVDriver` with default implementations of `deleteRange` (scan + deleteMany) and helpers, so a minimal driver implements only the four required methods.
- **`InMemoryKVDriver`**: a sorted structure (sorted array with binary search is fine for v1; keep it behind an interface so it can become a B-tree). It implements every optional capability: `setIfAbsent`, atomic `batch` and `deleteRange`.
- Write a reusable **driver conformance suite** `runKVDriverConformance(name, makeDriver)` covering ordering, `gte`/`lt` bounds, reverse, limit, `values` on/off, `getMany` order with missing keys, and each optional capability when present.

### 3.2 `KVStorage` / `KVNode` (`src/kv/node.ts`)

```ts
const db = new KVStorage(driver, { separator: '/', indexes: { ... } })   // db is the root KVNode
const users = db.child('users')
const user  = users.child('123')
```

API of every `KVNode` (types in section 7):

| Method                                         | Meaning                                                                                                                   |
| ---------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------- |
| `child(key)`                                   | Sync. Returns a node at `path + key`.                                                                                     |
| `as<S>()`                                      | Type assertion for untyped use; returns the same node retyped.                                                            |
| `get()` / `get(key)`                           | Own value at `selfKey` / value at child key.                                                                              |
| `getMany(keys)`                                | Batch child read, same order, `undefined` for missing.                                                                    |
| `set(value)` / `set(key, value)`               | Write own value / child value.                                                                                            |
| `setMany(entries)`                             | Batch child write.                                                                                                        |
| `delete()` / `delete(key)`                     | Delete own value / child value only (not descendants).                                                                    |
| `deleteMany(keys)`                             | Batch child delete.                                                                                                       |
| `deleteTree()` / `deleteTree(key)`             | Delete own value **and all descendants** (uses `deleteRange` if available).                                               |
| `keys(opts?)`                                  | `AsyncIterable<string>` of **direct** child keys (unescaped). Options: `limit`, `after`, `reverse`.                       |
| `entries(opts?)`                               | `AsyncIterable<[key, value]>` of direct children that have an own value.                                                  |
| `tree({ depth })`                              | Assemble an object from descendant keys up to `depth` (for field-per-key style). Bounded and explicit; never the default. |
| `findBy(index, value \| { gte?, lt? }, opts?)` | Index lookup over direct children (section 3.3).                                                                          |

**Arity dispatch (important):**

- Self vs child is decided by `arguments.length`, never by checking for `undefined`.
- If a key argument is passed but is `undefined` or `null`, throw a `TypeError` (this prevents `users.get(maybeId)` silently reading self).
- The root node (`path = []`) has no own value: `get()`, `set(v)` and `delete()` on root throw.
- Implement one private `#resolve(args)` that every method uses.

**Direct-children listing (`keys`)** uses a skip-scan:

1. Scan `gte: prefix`, `lt: prefix + succ(sep)`.
2. For each key, take the first segment after `prefix`. Skip reserved (`~…`) segments. Yield the segment (unescaped) if it differs from the previous one.
3. When the next key is a descendant of the segment just yielded, re-seek the driver to `gte: prefix + escSeg + succ(sep)` (where `succ(c)` is the next char code) instead of iterating through the subtree. Keep using the same iterator while keys are siblings.

Listing must be O(direct children × seek cost), not O(subtree). A child that has no own value but has descendants **is** listed.

### 3.3 Indexes (`src/kv/indexes.ts`)

Indexes are declared on **path patterns** in the `KVStorage` constructor. A pattern names a parent node, and its index applies to that node's direct children's values:

```ts
new KVStorage(driver, {
  indexes: {
    users: { byEmail: (u: User) => u.email },
    'users/*/posts': { byDate: (p: Post) => p.createdAt, byTag: (p: Post) => p.tags },
  },
})
```

- An index function returns `IndexValue | IndexValue[] | undefined`, where `IndexValue = string | number | boolean | null`. An array means multi-entry; `undefined` means not indexed.
- Compile patterns into a **segment trie** (`*` matches one segment). A node resolves its index set **once, at construction**, in O(depth).
- Entry key: `<nodePrefix>~i/<indexName>/<encodedValue>/<escapedChildKey>` with a `true` value.
- **`encodeIndexValue` must be order-preserving and separator-safe:**
  - Type tag first, so values order by type: `null` < `false` < `true` < numbers < strings.
  - Numbers use an order-preserving float64 encoding (flip the sign bit for positives and all bits for negatives, then fixed-width hex).
  - Strings are escaped like segments.
  - This enables `findBy(index, { gte, lt })` range scans.
- **Writes to an indexed node:**
  1. Read the old value(s) (`getMany`) and compute the diff of index entries.
  2. If the driver has `batch`, write the value and the index adds/removes atomically.
  3. Otherwise, write index **adds first**, then the value, then index **removes**. Treat index entries as hints: `findBy` re-reads each value, re-checks the index function, and lazily deletes stale entries (read-repair).
- Non-indexed nodes must **not** pay the read-before-write cost.

## 4. Layer 2: Events (`src/events/`)

An append-only log per stream. A stream is identified by a node path. Same `child()` navigation as KV.

```ts
const events = new EventStorage(kv) // takes a KVStorage (or a KVNode as root)
const orders = events.child('orders')

await orders.append('o1', [{ type: 'created', total: 40 }], { expectedVersion: 0 })
await orders.child('o1').append([{ type: 'paid' }]) // self form
for await (const e of orders.read('o1', { from: 1 })) {
  /* { version, commit, at, data } */
}
await orders.version('o1')
for await (const id of orders.keys()) {
} // child streams
orders.child('o1').child('shipments')
```

- `EventStorage` is the abstract interface. `KVEventStorage` is the KV-backed implementation. Leave room for native backends (EventStoreDB, Kafka) implementing the same interface.
- **Arity:** `append(events, opts?)` vs `append(key, events, opts?)`. Dispatch on `Array.isArray(args[0])`, plus the undefined-key rule from 3.2. `read`, `version` and `keys` follow the 3.2 rules.
- **Versions:** an empty stream has version 0, and the first event has version 1. `expectedVersion: number | 'any'` (default `'any'`).
- **Storage: one key per commit, densely numbered.**
  - Key: `<streamSelfKey>/~e/<commitSeq zero-padded to 12>`
  - Value: `{ firstVersion, at, events: E[] }`
  - The commit sequence (not the event version) is the key so that **any** stale writer collides with the existing key. Keying by version would let a stale writer create overlapping version ranges.
- **Append:**
  1. Get the head `{ commitSeq, version }` (from the cache, or a reverse scan with `limit: 1`).
  2. If `expectedVersion` is a number and doesn't match the head, throw `ConcurrencyError`.
  3. Call `setIfAbsent(nextCommitKey)`.
  4. On `false` (collision): refresh the head. If `expectedVersion` was given, throw `ConcurrencyError`; otherwise retry up to 5 times.
  5. Without `setIfAbsent`, fall back to a per-stream in-process mutex. Document that this mode is single-writer only.
- **Head cache:** a bounded LRU keyed by stream path. Update it on successful append; invalidate it on collision.
- **`read({ from, to, reverse, limit })`** streams events with metadata. To start at version `from`, locate the containing commit by binary search over commit numbers using `getMany` probes (O(log commits) round trips), then forward-scan.
- There is no update or delete. Keys inside `~e` are never rewritten.

## 5. Layer 3: Documents (`src/documents/`)

`DocumentStorage` is the interface. There are two implementations:

- `EventSourcedDocumentStorage(events, { projections?: KVNode })` is the v1 target. Projections default to the `~p` root on the same KV.
- `MongoDocumentStorage(client)` is a later milestone (section 9).

```ts
const docs = new EventSourcedDocumentStorage(events, { indexes: { users: [{ fields: ['email'], unique: true }, { fields: ['age'] }] } })
const users = docs.child('users')

const id = await users.insert({ name: 'Ada', age: 36 }) // generates a time-sortable id
await users.set('123', { name: 'Ada', age: 36 })
await users.update('123', { $set: { name: 'Ada L.' }, $inc: { logins: 1 } })
await users.child('123').update({ $unset: { nickname: true } }) // self form
await users.get('123')
await users.delete('123')
for await (const { key, data } of users.find({ age: { $gte: 18 } }, { sort: { age: 1 }, limit: 20 })) {
}
await users.findOne({ email: 'ada@x.io' })
await users.history('123') // event-sourced only
await users.getAt('123', 17) // state as of version 17
users.child('123').child('posts') // nested docs, same as KV
```

### 5.1 Events and projections

- The doc at path `P` has its event stream at `P` in `EventStorage`. Its projection is at `~p/P` in the projections KV: `{ state, version }` (and `deleted: true` for tombstones).
- Event types: `{ op: 'set', doc }`, `{ op: 'patch', set?: Record<path, value>, unset?: path[] }`, `{ op: 'delete' }`.
- **Store resolved deltas, not operators.** For example, `$inc` resolves to `{ set: { logins: 6 } }`, so replay is deterministic.
- Supported update operators in v1: `$set`, `$unset`, `$inc`, `$push`, `$pull`, `$addToSet`, with dot-path support.

**Write path:**

1. Read the projection.
2. Compute the new state and patch.
3. `append` with `expectedVersion = projection.version`.
4. Write the projection and index entries (atomic `batch` if available).
5. On `ConcurrencyError`: catch up the projection from the stream, recompute, and retry (bounded).

**Reads** are a single projection `get`. Never replay on read.

**Crash between append and projection write:**

- The projection lags the stream. The next write's `expectedVersion` fails, which triggers catch-up, so the system self-heals.
- Provide `get(key, { consistent: true })` that checks the stream head and catches up first.
- Provide a `catchUp(node?)` maintenance method to repair a subtree.
- `insert` ids are time-sortable (ULID-like). Implement a small generator, with no dependency.

### 5.2 Queries and document indexes

- Filter subset:
  - `$eq`, `$ne`, `$gt`, `$gte`, `$lt`, `$lte`, `$in`, `$nin`, `$exists`
  - `$and`, `$or`, `$not`
  - implicit equality and dot paths
- Options: `sort`, `limit`, `skip`, `projection` (fields).
- `find` on a node queries that node's **direct children**.
- Indexes are declared per path pattern (same trie mechanism as 3.3).
  - Each index has `fields` (compound allowed); entries go under `~p/<node>/~i/<name>/<enc(field1)>/<enc(field2)>/…/<childKey>`, using `encodeIndexValue`.
  - `unique: true` additionally claims `~u/<name>/<enc(values)>` via `setIfAbsent`. Throw at construction if the driver lacks `setIfAbsent`.
- **Planner:**
  - Pick the index that covers the most leading equality fields, then at most one range field.
  - Use the index order for `sort` when it matches.
  - Otherwise do a full scan of children projections, with a one-time dev-mode `console.warn` naming the filter.

## 6. Shared conventions

- Every layer uses the same navigation (`child`, `as`, `keys`) and the same self/child arity rules.
- All multi-result reads are `AsyncIterable` (streamed, cancellable). Never build large arrays internally.
- Errors are typed classes exported from `src/errors.ts`: `ConcurrencyError`, `UniqueConstraintError`, `CapabilityError`, `InvalidKeyError`.
- Public exports go through `src/index.ts`, with subpath exports per layer if convenient.

## 7. Types (`src/types/schema.ts`)

Each node is typed by a single **Spec** that describes its own value and its children by key:

```ts
export type Spec = { value?: unknown; children?: Record<string, Spec> }
export type AnySpec = { value: unknown; children: Record<string, AnySpec> } // untyped default

export type ValueOf<S> = S extends { value: infer V } ? V : never
export type ChildrenOf<S> = S extends { children: infer C } ? C : {}
export type KeyOf<S> = Extract<keyof ChildrenOf<S>, string | number>
export type ChildOf<S, K extends KeyOf<S>> = ChildrenOf<S>[K]

// Helpers
export type Many<V, C extends Record<string, Spec> = {}> = { children: { [id: string]: { value: V; children: C } } }
export type Fields<T> = { [K in keyof T & string]: { value: T[K] } }
```

Node signatures:

```ts
class KVNode<S extends Spec = AnySpec> {
  child<K extends KeyOf<S>>(key: K): KVNode<ChildOf<S, K>>
  get(): Promise<ValueOf<S> | undefined>
  get<K extends KeyOf<S>>(key: K): Promise<ValueOf<ChildOf<S, K>> | undefined>
  // set/delete/getMany/etc. follow the same pattern
}
```

Example to cover with `expectTypeOf` tests:

```ts
type User = { username: string; age: number }
type Post = { title: string; createdAt: string }
type Schema = {
  children: {
    users: Many<User, { posts: Many<Post> }>
    profile: { children: { [id: string]: { children: Fields<User> } } } // field-per-key style
  }
}

const db = new KVStorage<Schema>(driver)
db.child('users').get('123') // User | undefined
db.child('users').child('123').get() // User | undefined (same key)
db.child('users').child('123').child('posts') // KVNode<Many<Post>>
db.child('users').child('123').child('postz') // ✗ type error
db.child('profile').child('9').get('age') // number | undefined
db.child('profile').child('9').get('agee') // ✗ type error
```

Notes:

- **Named levels** check keys at compile time; **dynamic `[id: string]` levels** accept any string.
- One node's children can't mix an index signature with named keys (a TS restriction), so schemas alternate between dynamic and named levels. That alternation exists only in types; the runtime API is just `child()`.
- `EventStorage` and `DocumentStorage` nodes use the same Spec machinery (the value type is the event type or the document type respectively).

## 8. Performance requirements

- Single-key ops: exactly one driver call (no hidden reads), except indexed writes (one `getMany` before the write) and document writes (projection read plus append plus projection write).
- `*Many` ops: one driver call each (plus index work), never N calls.
- `keys()`: skip-scan, O(direct children) seeks.
- Event head lookup: cached; cold lookup is a single reverse scan with `limit: 1`.
- Document `get`: one driver `get`.
- Add `vitest bench` benchmarks for:
  - KV `get`/`set`/`getMany` at 10k/100k keys
  - `keys()` on a node with 1k children each having 100 descendants
  - event append and read
  - document `get`/`update`/indexed `find` vs full-scan `find`
- Record baseline numbers in `DESIGN.md`.

## 9. Milestones

1. **Core:** `path.ts` (escape, unescape, encode, `succ`), `encodeIndexValue`, errors. Property tests for round-trips and order preservation.
2. **KV driver:** `KVDriver`, `BaseKVDriver`, `InMemoryKVDriver`, conformance suite.
3. **KV node:** full API from 3.2, including arity rules, skip-scan `keys`, `deleteTree`, `tree`. Add a model-based property test: random ops vs a reference `Map`.
4. **KV indexes:** pattern trie, atomic and non-atomic write paths, read-repair, range `findBy`.
5. **Events:** `KVEventStorage` with commit keys, `setIfAbsent` and mutex modes, head cache, binary-search `read({ from })`, concurrency tests (simulated interleaving with two storage instances on one driver).
6. **Documents:** `EventSourcedDocumentStorage`, update operators, projections, catch-up, queries, planner, unique indexes, `history` and `getAt`.
7. **Types:** Spec machinery wired through all three layers, plus `expectTypeOf` tests from section 7.
8. **HTTP driver:**
   - A `createKVHttpHandler(driver)` (framework-agnostic `Request → Response`) plus an `HttpKVDriver` client.
   - Endpoints: `POST /getMany`, `POST /setMany`, `POST /deleteMany`, `POST /batch`, `POST /setIfAbsent`, `GET /scan?gte&lt&limit&reverse&values` (NDJSON stream).
   - It must pass the conformance suite end-to-end.
9. **Benchmarks** and a `DESIGN.md` update with results.
10. **(Later, ask first)** `MongoDocumentStorage`:
    - Path pattern maps to a collection (e.g. `users/*/posts` → `users.posts`), with a `_parent` field and a compound index `(_parent, _id)`.
    - Native indexes map from the same index declarations.
    - It should pass the document test suite where semantics allow (no `history`/`getAt`).

## 10. Decisions already made (don't revisit without asking)

- `child()`-only navigation; no collection/doc classes.
- `get()` with no argument reads the node's **own key**. It never assembles the subtree; `tree()` does that explicitly.
- A node's own value and its children are independent keys.
- Self/child dispatch by arity; a passed-but-undefined key throws.
- Indexes are declared on path patterns at construction.
- Events use one key per commit, densely numbered.
- Documents store resolved deltas, and reads hit projections only.
- Keys sort lexicographically.
- Values are JSON-serialisable; byte drivers use a codec.

## 11. Open questions to raise with the owner (don't block on them)

- Order-preserving numeric **keys** (not just index values)?
- Should multi-writer safety be **required** (a hard error without `setIfAbsent`) rather than a documented single-writer fallback?
- The hard-delete story for immutable event logs (compaction or crypto-shredding) for privacy deletion requests.

## 12. Implementation decisions

Decisions taken where the brief was silent. Each is the simplest option consistent with sections 1–10.

### M1 — Core

- **Separator** must be a single printable ASCII character other than `%` and `~`.
- **Empty keys are rejected** (`InvalidKeyError`), as are `NaN`/`±Infinity` number keys. An empty segment
  would produce `a//b`, which is ambiguous with the subtree layout.
- **Separator escaping** uses `%` + two uppercase hex digits (`/` → `%2F`, `%` → `%25`, leading `~` → `%7E`).
- **`InvalidKeyError` extends `TypeError`**, so "passed-but-undefined key throws a `TypeError`" (3.2) and
  the typed error class (6) are the same throw.
- **Index string encoding deviates from "escaped like segments".** Percent-escaping is not
  order-preserving (`"a/"` → `"a%2F"` sorts below `"a&"`, and `"a"` + sep sorts above `"a!"`), which
  would break `findBy` range scans. Instead every character the index encoder emits sorts strictly
  above the separator: code units `<= succ(sep)` are written as `succ(sep)` followed by
  `chr(succ(sep) + 1 + c)`. This is monotone and prefix-safe, so `a < b ⇔ enc(a)+sep+… < enc(b)+sep+…`
  exactly (property-tested). Encodings are still separator-free.
- **Type tags and number digits**: tags are the first five digits of the digit alphabet; numbers use
  16 digits of `0-9a-f` when the separator sorts below `'0'` (e.g. `/`), otherwise the 16 characters
  just above the separator. `-0` is stored as `0`; `NaN` cannot be indexed.
- **Ordering** of strings is by UTF-16 code unit (JS `<`). Drivers that compare UTF-8 bytes agree
  except for astral-plane characters vs. U+E000–U+FFFF; noted as a driver-author caveat.

### M2 — KV driver

- **Conformance suite location**: `src/testing/kv-conformance.ts`, exported as `potential-storage/testing`.
  It imports `vitest`, which is an _optional peer dependency_; the core entry point never imports it.
- **`InMemoryKVDriver` clones values** on write and read (`structuredClone`, skipped for primitives) so
  stored state can't be mutated through shared references, matching serialising drivers. Opt out
  with `{ clone: false }`.
- **Scans tolerate concurrent writes**: the in-memory scan remembers the last key yielded and re-seeks
  if the map changed while suspended. Read-repair and `deleteTree` rely on this. The conformance suite
  requires it of every driver (deleting an already-yielded key mid-scan must not skip keys).
- **`setMany` bulk path**: ≥32 new keys are sorted and merged (O(n + k log k)); fewer are spliced.
- **`BaseKVDriver.deleteRange`** deletes in chunks of 1000 (scan with `limit`, then `deleteMany`,
  repeat), so it never deletes from under its own live iterator. It also provides `get`/`set`/`delete`
  single-key helpers.
- **No fake `batch`**: `BaseKVDriver` deliberately does not provide a non-atomic `batch`, since stores
  use its presence to mean "atomic".

### M3 — KV node

- **Child order is "subtree order", not plain segment order.** The brief's skip-scan assumes a
  child's keys are contiguous, but they aren't when a sibling extends a segment with a character
  that sorts below the separator (for `/`: space and `!"#$%&'()*+,-.`). With children `a` and `a-1`
  the key space is `p/a`, `p/a-1`, `p/a-1/x`, `p/a/x`, so `a`'s descendants sort _after_ `a-1`, and
  "yield if different from the previous segment" would emit `a` twice. `keys()`/`entries()` therefore
  order children by **escaped segment followed by the separator** (`a-1/` < `a/`), which is the order
  of their subtrees in key space. For keys without such characters this is plain lexicographic order.
  - Forward listing defers a child seen only through its own key on a small stack (bounded by
    segment length) until the scan passes `p/<seg>/`. It costs no extra driver calls beyond the
    brief's one seek per child with descendants.
  - Reverse listing needs one batched `getMany` probe per new child whose segment contains a
    below-separator character, to find shorter siblings that only have an own key.
  - `after` is exclusive in the direction of travel and follows the same order.
  - Implemented once in `src/kv/children.ts` (`scanChildren`) and reused by the event and document
    layers. A model-based property test checks forward, reverse, `after` and `limit` against
    brute force with keys like `a`, `a-1`, `a.b`, `a/x`, `%`, `~t`.
  - **Open question for the owner:** keep subtree order, or change segment escaping so the key
    layout nests exactly. That would mean escaping every below-separator character with an escape
    character above the separator, at the cost of the readable percent-encoding.
- **Errors from async methods are rejections.** Every async method (`get`, `set`, …) is an `async`
  function, so a bad key yields a rejected promise rather than a synchronous throw. `child()` is sync
  and throws synchronously.
- **`set(undefined)` is rejected** (`TypeError`: use `delete()`); `undefined` means "missing" in reads.
- **`deleteTree()` on the root** is allowed and clears the whole store (chunked scan + delete, since
  the root range has no upper bound). Subtree deletion is `delete(selfKey)` plus
  `deleteRange(prefix, selfKey + succ(sep))`. It is not `[selfKey, …)`, which would also catch
  siblings such as `a!`.
- **`tree({ depth })`** builds a plain object: leaves are values, interior nodes are objects. A node
  with both an own value and children exposes its own value under the `''` property (empty keys are
  invalid, so it can't collide). Reserved subtrees are skipped. Deeper levels are skipped by seeking
  rather than reading.
- **`keys()` and `entries()` yield string keys** (number keys come back as strings).
- **Exposed low-level properties** on every node: `path`, `selfKey`, `prefix`, `end` (subtree upper
  bound), `driver`, `separator`, `isRoot`. The event and document layers build on these.

### M4 — KV indexes

- **Pattern syntax**: segments separated by the storage separator; `*` matches one segment; `''`
  names the root. A literal `*` key can't be targeted by a pattern.
- **Overlapping patterns** that declare the same index name throw at construction.
- **Index trie state is stepped per `child()` call** (O(1) in patterns), so each node resolves its
  indexes in O(depth) overall. A node holds two bound index sets: one over its children (for child
  writes) and its parent's (for self-form writes such as `users.child('1').set(v)`).
- **Index function results**: `undefined` → not indexed; arrays are multi-entry and de-duplicated
  per child; anything that is not `string | number | boolean | null` (or `NaN`) throws a `TypeError`
  at write time. Index functions are not called for missing (`undefined`) values.
- **`findBy` results** are `[key, value]` pairs (the value is re-read anyway for verification).
  Range queries accept `gt`/`gte`/`lt`/`lte`. Results are in index-value order, then child-key order,
  and range queries de-duplicate multi-entry hits.
- **`findBy` batching**: entry keys are read in chunks of 128 (or of the remaining `limit`, if
  smaller) and values fetched with one `getMany` per chunk. Stale entries are deleted with one
  `deleteMany` per chunk.
- **Read-repair race (non-atomic drivers only)**: a reader can see a concurrent writer's fresh
  index add before that writer's value write lands, judge it stale, and delete it. With multiple
  writers on a driver without `batch`, this can lose an index entry. Mitigation: `readRepair: false`
  on `KVStorage` (stale entries are then only skipped, never deleted). With `batch`, entries never go
  stale, so the race doesn't arise.
- **`set` of an indexed child with duplicate keys in one `setMany`**: last write wins, and index
  diffs are computed once per key.

### M5 — Events

- **`EventStorage` is an interface (type), not a class.** The brief's sample says `new EventStorage(kv)`
  but also says it is the abstract interface; the concrete class is `KVEventStorage(kv, opts?)`, which
  accepts a `KVStorage` or any `KVNode` as root. Options: `headCacheSize` (default 10 000),
  `maxRetries` (default 5) and `now` (clock, default `Date.now`).
- **Commit value**: `{ firstVersion, at, events }`, with `at` in ms since epoch. Read results are
  `{ version, commit, at, data }`.
- **The root node is not a stream** (consistent with the root having no own KV value). Non-root
  nodes are both a stream and a container of child streams; `keys()` lists child streams, and a
  node's `~e` subtree is reserved, so streams and children never mix.
- **`version()` always reads storage** (one reverse scan with `limit: 1`) and refreshes the head cache.
  Only `append` trusts the cache. When a cached head disagrees with a numeric `expectedVersion`,
  the head is re-read before throwing, so a stale cache never produces a false `ConcurrencyError`.
- **`append([])`** writes nothing; it still checks `expectedVersion` against a fresh head and returns it.
- **Read arity**: `read()` and `read(opts)` are the self form (the first argument is a non-null
  object). Any other first argument is a key, so `read(undefined)` throws like every other
  passed-but-undefined key.
- **Locating `from`/`to`**: commit `n` has `firstVersion >= n`, so the commit containing version `v` has
  `seq <= v`. `read` probes `seq = v` first; with single-event commits that is the answer, in one
  `getMany`. Otherwise it runs an 8-ary search, one `getMany` of up to 8 probes per round, which is
  O(log₈ commits) round trips. The head is only read when the guess is past the end.
- **Mutex mode** (driver without `setIfAbsent`): a per-stream in-process promise chain serialises
  appends. It is safe only with a single writer process.

### M6 — Documents

- **Projection value** is `{ state, version, commit }`, or `{ deleted: true, version, commit }` for a
  tombstone. Tombstones keep the version, so re-creating a document continues its stream.
- **`expectedCommit` append hint.** Writes pass the projection's `commit` to `append` as
  `expectedCommit`, so a write is exactly projection `getMany` + `setIfAbsent` + projection `batch`
  (3 driver calls), even with a cold head cache. A hint taken from a projection can only be stale
  (which causes a collision, then catch-up and retry), never ahead of the stream, so it cannot
  create a gap. Non-KV backends may ignore it.
- **Per-document in-process write lock.** Writes to the same document within one storage instance
  are serialised (`KeyedMutex`), so optimistic retries (default 5) are spent only on cross-process
  contention.
- **Return values**: `set` → `void`; `insert` → id; `update` → new state, or `undefined` if the document
  doesn't exist (pass `{ upsert: true }` to treat missing as `{}`); `delete` → whether a document
  was deleted. No-op updates (resulting state equal to current) append nothing.
- **Arity for documents**: in forms with an optional leading key (`get`, `set`, `update`), a non-null
  object first argument selects the self form, and any other first argument is a key (so `undefined`
  throws). `delete`/`history` use argument count. `getAt(version)` vs `getAt(key, version)` also uses
  argument count, because a version and a numeric key are both numbers.
- **The root document node has no own document** (consistent with KV).
- **`keys()` on a document node** lists children holding a live document. Unlike KV `keys()`, it skips
  children that only have nested documents or tombstones.
- **`find` results** are `{ key, data }`. `findOne` returns the same shape or `undefined`.
- **Filter semantics vs MongoDB** (see `src/documents/filter.ts`):
  - Comparisons are type-bracketed (`$gt: 5` matches only numbers), and cross-type order follows
    the index encoding: `null/missing < false < true < numbers < strings < other`.
  - On array fields, every positive operator in one condition (`$eq $gt $gte $lt $lte $in`) must be
    satisfied by the **same element** (like `$elemMatch`). In MongoDB, `{ s: { $gt: 5, $lt: 10 } }`
    matches `[1, 20]`; here it doesn't. This makes index range scans exact. To get MongoDB's
    behaviour, split the condition with `$and`.
  - `{ f: null }` matches missing fields. `$not` works both at top level (negating a filter) and at
    field level. Unknown operators throw.
  - `$in` is not index-accelerated in v1.
- **Index entries** for each field value: scalars as-is, arrays as their scalar elements (multikey;
  empty arrays → `null`), and missing or non-scalar values as `null`. Every live document therefore
  has at least one entry per index, so a full index scan sees all documents. Indexing a document
  where more than one field of a compound index has multiple values throws (as MongoDB does).
- **Index names** default to the fields joined by `,`.
- **Unique indexes**: claims are scoped **per parent node** (`<node>/~u/<name>/<values>`), like one
  MongoDB collection per parent. Value tuples where every field is missing/null are not claimed
  (sparse). Claims are taken before appending, then released if the append fails. A claim value is
  `[ownerKey, claimedAtMs]`. A claim held by another document is taken over only if that
  document, after catching up from its stream, no longer holds the value, **and** the claim is older
  than `claimGraceMs` (default 30 s). The owner might otherwise be between claiming and appending.
  The residual risk is a writer stalling for longer than the grace period between claiming and
  appending.
- **Planner**: per index, count leading equality fields (k), then whether field k has a range;
  score = 2k + (range ? 1 : 0). Ties prefer an index whose order satisfies `sort` after dropping
  equality-constrained sort fields. With no usable predicate, an index matching `sort` is still used
  as an ordered full index scan, which streams and stops early with `limit`. Range bounds are clamped
  to the bound's type class. Index-backed results are re-read from projections, re-checked against the
  full filter, de-duplicated, and stale entries are read-repaired.
- **Result order** when `sort` is not given is the plan's order (index order, or child-key order for
  a full scan). Ties in sorted results are broken by child key in the direction of the first sort
  field, both for index-ordered and in-memory sorts.
- **In-memory sort** keeps a bounded top `skip + limit` buffer when a limit is given. Without a limit,
  it buffers all matches; this is the one place results are materialised.
- **Full-scan warning**: `console.warn` once per filter _shape_ (values replaced by `?`) per storage
  instance, only for non-empty filters. On by default unless `NODE_ENV === 'production'`; set it with
  `warnOnFullScan`.
- **Catch-up** re-asserts unique claims for the caught-up state with plain writes, since the log is
  the source of truth. A slow catch-up can briefly overwrite a newer projection with an older one;
  the next write's `expectedVersion` check detects this and heals it. `catchUp()` walks the subtree
  via event-stream `keys()` and returns the number of documents repaired.
- **Projections for non-KV event stores** must be passed explicitly (`projections: KVNode`); the
  projection key of a document is then `projections.prefix + docKey`.

### M7 — Types

- **`AnySpec` uses an index signature** (`{ [key: string]: AnySpec }`), not `Record<string, …>`, so
  `KeyOf<AnySpec>` is `string | number` and number keys type-check on untyped stores.
- **`ChildOf` guards with `infer C extends Spec`** so that `KVNode<ChildOf<S, K>>` satisfies the `Spec`
  constraint generically.
- **`setMany` entries are a union of precise `[key, value]` pairs** (`EntryOf<S>`), so on named levels a
  value must match its own key (`['age', 'x']` is rejected).
- **Listings**: `keys()` yields `` `${KeyOf<S>}` `` (string literals on named levels, `string` on dynamic
  ones). `entries()` and `findBy()` yield `[string, V]` on dynamic levels.
- **"Accept any node" parameters** are typed `KVNode<AnySpec>` / `EventNode<AnySpec>`. A typed node is
  assignable to these, but not to `KVNode<any>`, because `KeyOf<any>` collapses to `never`.
- **Type tests** live in `test/types.test-d.ts` and are enforced by `tsc --noEmit` (part of `npm test`),
  including the `@ts-expect-error` negative cases from section 7.

### M8 — HTTP driver

- **Extra endpoints** beyond the brief's list: `POST /deleteRange {gte, lt}` and
  `GET /capabilities`. Unsupported optional operations return `501`, driver errors `500`, and unknown
  routes `404`.
- **Missing vs `null`**: `/getMany` returns `{ values, missing }`, where `missing` lists the indices of
  absent keys, because `null` is a legitimate stored value.
- **Codec scope**: the codec serialises whole request/response bodies and each NDJSON scan line
  (`[key]` or `[key, value]`), so it must not emit newlines. The default is JSON.
- **Capabilities on the client**: `HttpKVDriver` defines `setIfAbsent`/`batch` only when the server
  supports them, so stores' feature detection (e.g. unique indexes requiring `setIfAbsent`, atomic
  index writes using `batch`) behaves as it would locally. `HttpKVDriver.connect()` discovers them via
  `/capabilities`. The constructor takes them explicitly (default: all). Without native
  `deleteRange` the client falls back to `BaseKVDriver`'s chunked delete.
- **Scan streaming**: the server pulls the driver iterator in chunks that grow from 16 to 256
  entries, so short reads (skip-scan re-seeks) don't make it run far ahead. Cancelling the client
  iterator cancels the response body, which calls `return()` on the server-side iterator.
- **Optional `headers`** (e.g. auth) and an injectable `fetch` on the client; an optional `basePath` on
  the handler.
- The conformance suite runs end-to-end in-process (fetch → handler), over a real `node:http`
  socket, and against a minimal server driver with discovered capabilities. A smoke test runs KV
  indexes, events and unique-indexed documents over HTTP.

### M9 — Benchmarks and in-memory driver performance

- **The in-memory driver's sorted array was replaced by `ChunkedSortedMap`** (sorted chunks of ≤1024
  keys, split in half on overflow; values in a `Map`). Profiling showed 59% of document-update time
  in the sorted array's O(n) `splice` once the store held ~70k keys (each write adds commit, index
  and claim keys). Inserts and deletes are now O(log n + 1024). Iteration is O(1) per step and
  re-seeks after a mutation, which replaces the old version-counter revalidation in the driver.
  The structure stays behind the `SortedMap` interface; a B-tree remains possible.
- **Value cloning uses a hand-written JSON deep copy** instead of `structuredClone` (about 10× cheaper
  per value), in the in-memory driver and the document layer. Values are JSON by contract (§10).

<!-- decisions appended per milestone -->

## 13. Benchmark baselines

`npm run bench` (Vitest bench), in-memory driver with default cloning, Node 22.22, Linux x64 cloud
container (shared CPU, so expect ±10–20% run-to-run). Mean time per operation.

**KV** (`bench/kv.bench.ts`): values are small objects.

| Operation            | 10k keys | 100k keys |
| -------------------- | -------- | --------- |
| `get`                | 1.2 µs   | 1.6 µs    |
| `set` (overwrite)    | 1.7 µs   | 2.0 µs    |
| `getMany` × 100 keys | 21 µs    | 22 µs     |

**`keys()`** (`bench/keys.bench.ts`): node with 1 000 children, each with 100 descendants (101k keys).

| Operation                        | Mean   |
| -------------------------------- | ------ |
| `keys()` skip-scan (1 000 seeks) | 2.9 ms |
| Reference: full subtree scan     | 36 ms  |

**Events** (`bench/events.bench.ts`): single-event commits.

| Operation                                      | Mean   |
| ---------------------------------------------- | ------ |
| `append` 1 event (warm head cache)             | 6.3 µs |
| `read` 100 events from version 5 000 of 10 000 | 174 µs |
| `read` full 10 000-event stream                | 21 ms  |
| `version()` (reverse scan, `limit: 1`)         | 3.9 µs |

**Documents** (`bench/documents.bench.ts`): 10 000 docs, indexes on `age` and unique `email`.

| Operation                                                         | Mean    |
| ----------------------------------------------------------------- | ------- |
| `get`                                                             | 2.6 µs  |
| `update` (`$inc`, indexed node: projection read + append + batch) | 22 µs   |
| `findOne` by unique index (`email`)                               | 16 µs   |
| `find` indexed (`age = k`, ~100 hits)                             | 0.57 ms |
| `find` full scan (`city = k`, ~200 hits of 10k)                   | 28 ms   |

For comparison, the first run with the sorted-array map and `structuredClone` measured: KV `get`
3.7 µs, `getMany`×100 186 µs, `append` 34 µs, document `update` 110 µs, full scan 57 ms, and
full stream read 62 ms.