Add files using upload-large-folder tool
d522ffa verified about 1 month ago
24.6 kB
# minidb

A **pure-Node.js** (zero native addons) embedded key-value database that mixes
ideas from **Redis** (in-memory KV speed, data structures, AOF-style rewrite)
and **SQLite** (durable single-file persistence, WAL, indexed queries).
Written in **TypeScript**, with strict types and zero runtime dependencies.

> Built by studying the real source code of Redis, SQLite, NeDB, Bitcask, and a
> tiny SQLite clone — see [`DESIGN_NOTES.md`](./DESIGN_NOTES.md) for what each
> one taught us.

## Features

- **O(1) GET/SET** from an in-memory index (`Map`), values as bytes.
- **Optional larger-than-RAM values**: `valueMode: 'disk'` keeps only value
  pointers in RAM and reads value bulk from the snapshot/WAL with synchronous
  positioned reads.
- **Durable**: append-only **WAL** with group commit + three fsync policies
  (`always` / `everysec` / `no`), exactly like Redis AOF.
- **Crash-safe recovery**: CRC-framed records; a torn tail from a crash is
  detected and truncated automatically.
- **Snapshots + compaction** (WAL rewrite) bound disk growth and speed up
  restart.
- **TTL**: lazy + active expiration (Redis-style, heap-backed).
- **Secondary indexes**: equality and **range** indexes over JSON documents,
  backed by a Redis-style **skip list** with O(log N) rank/range; unique and
  sparse supported; array fields indexed per element.
- **RESP server** (optional): talk to it with `redis-cli` / `ioredis`.
- **ClusterDb** (optional sharding layer): multi-process concurrent read/write
  over N sharded MiniDb directories, scaling write throughput with shard count.
- **Value codecs**: `buffer`, `string`, or `json`.
- **Zero dependencies**, pure `node:*` built-ins.

## Install / layout

Written in **TypeScript**, zero runtime dependencies. Source is in `src/`; build
output goes to `dist/` (generated by `npm run build`).

```
src/
  index.ts          public API barrel (re-exports; no logic)
  mini-db.ts        the MiniDb class (open/close, KV reads, index admin, delegates)
  types.ts          public option/record types (+ the internal PreparedOp)
  value-codec.ts    value codecs + key byte-string / atomic sidecar helpers
  memory-guard.ts   maxMemory facet (LRU access set, evict/reject enforce)
  backup.ts         online backup (write-gate fence + atomic copy)
  query-engine.ts   unified query facet (candidate collection, dt fast path)
  text-registry.ts  text-index registry facet (defs, create/drop, search)
  wal-group.ts      WAL group-commit + in-place recovery gating facet
  generation-builder.ts  persistent index generation build facet
  generation-loader.ts   generation load facet (image loads + WAL delta replay)
  write-path.ts     write path facet (set/del/batch/expire commit machinery)
  read-path.ts      read path facet (KV reads, scans, live-record feeds)
  index-admin.ts    secondary/compound index admin facet (+ open-time rebuild)
  lifecycle.ts      open/close/openOrRebuild/renewLock flows
  stats.ts          the stats object factory
  codec.ts          binary frame encode/decode + CRC parser + resync
  crc32.ts          table-based CRC-32
  wal.ts            buffered append + group commit + fsync policies
  store.ts          in-memory index + TTL (lazy + active) + value refs
  value-reader.ts   synchronous positioned reads for disk-backed values
  snapshot.ts       chunked snapshot writer
  recovery.ts       load snapshot + replay WAL + resync/truncate
  compaction.ts     WAL rewrite / rotation
  skiplist.ts       comparator-driven skip list with span
  index-manager.ts  secondary indexes (equality + range)
  dt-index.ts       datetime-column indexes
  query.ts          jq-like value query engine
  text-index/       full-text index (in-RAM dictionary + on-disk postings)
  text-postings.ts  on-disk postings file for the full-text index
  lockfile.ts       exclusive file lock + read-only
  server.ts         optional RESP TCP server
```

```bash
npm run build      # compile src/ -> dist/ (JS + .d.ts)
npm run typecheck  # tsc --noEmit (strict)
```

## Quick start (embedded)

```ts
import { MiniDb } from 'minidb';
const db = await MiniDb.open({
  dir: './data',
  valueCodec: 'string',     // 'buffer' | 'string' | 'json'
  fsyncPolicy: 'everysec',  // 'always' | 'everysec' | 'no'
});
await db.set('hello', 'world');
db.get('hello');            // 'world'
await db.set('temp', 'x', { ttl: 5000 }); // expires in 5s
db.ttl('temp');             // remaining ms (-1 none, -2 missing)
await db.del('hello');
await db.close();           // flush + fsync + close
```

> Within this repo, import from `./src/index.ts` (run with `tsx`). As an installed
> package, import from `'minidb'` (the built `dist/` output).

Re-open the same `dir` and your data is recovered from the snapshot + WAL.

### Typed usage

`MiniDb` is generic over the value type:

```ts
interface User { name: string; age: number; city: string }
const db = await MiniDb.open<User>({ dir: './data', valueCodec: 'json' });
await db.set('u1', { name: 'Ann', age: 30, city: 'Paris' });
const u = db.get('u1'); // User | undefined
```

### JSON + secondary indexes

```js
const db = await MiniDb.open({ dir: './data', valueCodec: 'json' });
await db.createIndex('byCity', { field: 'city' });                 // equality
await db.createIndex('byAge',  { field: 'age',  type: 'range' });  // range (skip list)
await db.createIndex('byMail', { field: 'email', unique: true });  // unique
await db.set('u1', { name: 'Ann', city: 'Paris', age: 30, email: 'ann@example.com' });
await db.set('u2', { name: 'Bob', city: 'Paris', age: 41, email: 'bob@example.com' });
db.findEq('byCity', 'Paris');          // [{ key:'u1', value:{...} }, { key:'u2', ... }]
db.findRange('byAge', { min: 30, max: 40, count: 10 });
```

Index definitions are persisted and rebuilt from the store on startup.

## Document model & querying (MongoDB-like subset)

A record is:

```js
{ key: 'user:1234', value: { ...any JSON... }, dt1..dtN: <datetime columns> }
```

- **key** — string ≤ 128 chars, unique, **ordered** (range / prefix / ordered scan).
- **value** — any JSON object (jq-like filter + projection + full-text).
- **dt1..dtN** — any number of top-level **datetime columns**, each indexed for
  O(log N) range queries. Pass them as `{ dt: { created: Date.now() } }` (ISO
  strings or epoch ms).

### Key scans (ordered)

```js
db.scan({ gte: 'user:1', lte: 'user:9', limit: 100 }); // range in key order
db.prefix('user:');                                    // prefix scan
```

### Datetime column queries

```js
await db.set('a', { n: 1 }, { dt: { created: '2024-01-01' } });
db.dtColumns();                              // ['created']
db.dtRange('created', { gte: t0, lte: t1 }); // O(log N), [{ key, value, dt, dtValue }]
```

### Unified query

`db.query(q)` composes key range, dt range, full-text, and a value filter:

```js
db.query({
  key:    { prefix: 'post:' },
  dt:     { created: { gte: t0, lte: t1 } },
  text:   { index: 'body', q: '北京', op: 'AND' },
  filter: { age: { $gte: 18 }, $or: [{ city: 'Paris' }, { city: 'London' }] },
  sort:   { age: -1 },
  project: ['name', 'age'],
  skip: 0, limit: 20,
});
```

Filter operators: `$eq $ne $gt $gte $lt $lte $in $nin $regex $exists $contains
$type`, plus `$and $or $nor $not`. Paths use dot/bracket notation
(`"address.city"`, `"tags[0]"`).

> Indexed dimensions (key / dt / text / a `createIndex`'d field) are fast;
> `db.query()` automatically uses matching equality/range value indexes for simple
> top-level predicates (including `$and`), while a value `filter` with no matching
> index falls back to a full collection scan, exactly like MongoDB without an index.

### Full-text search

```js
await db.createTextIndex('body', { fields: ['bio'] }); // fields optional (default: all strings)
db.search('body', 'hello 世界', { op: 'AND' });         // [{ key, value, score }]
```

Latin words + CJK unigram/bigram tokenization (no dictionary, zero deps), with
TF-IDF ranking.

## API

| Method | Description |
|---|---|
| `MiniDb.open({ dir, valueCodec?, valueMode?, fsyncPolicy?, compactThresholdBytes?, autoCompact?, activeExpireIntervalMs?, recovery?, readOnly?, onLockFail?, maxMemoryBytes?, maxMemoryPolicy? })` | Open / create a database |
| `MiniDb.restore(srcDir, destDir, opts?)` | Restore a `db.backup()` directory and open it |
| `MiniDb.openOrRebuild(opts, { onRebuild? })` | Open; on corruption, discard + reopen empty (cache use). Never deletes a live-locked db |
| `get(key)` | Decoded value or `undefined` |
| `set(key, value, { ttl? })` | Set; `ttl` in ms. Resolves per fsync policy |
| `del(key)` | Delete; returns `true` if it existed |
| `has(key)`, `size` | Membership / live key count |
| `mget([keys])`, `mset([[k,v],...])` | Batch read / write |
| `batch([{op:'set'|'del', key, value?, ttl?, dt?}])` | Atomically commit multiple ops (all-or-nothing) |
| `expire(key, ttlMs)`, `ttl(key)` | Set / read TTL |
| `createIndex(name, { field, type?, unique?, sparse? })` | Secondary index (json codec) |
| `dropIndex(name)`, `listIndexes()` | Manage indexes |
| `findEq(name, value)`, `findRange(name, opts)` | Query value indexes |
| `createCompoundIndex(name, { groupBy, orderBy, orderType? })` | Compound index (group + order, e.g. workspace + updatedAt) |
| `compoundRange(name, groupValue, opts)` | Ordered range within a group, O(log N + limit), no full sort |
| `dropCompoundIndex(name)`, `listCompoundIndexes()` | Manage compound indexes |
| `scan({ gte, gt, lte, lt, limit, reverse })` | Ordered key range scan |
| `prefix(p, limit?)` | Key prefix scan |
| `dtColumns()`, `dtRange(col, opts)` | Datetime column range query |
| `query({ key, dt, text, filter, project, sort, skip, limit })` | Unified Mongo-like query |
| `createTextIndex(name, { fields? })`, `dropTextIndex(name)` | Full-text index |
| `search(name, q, { op?, limit? })` | Full-text search |
| `compact()` | Force a snapshot + WAL rewrite now |
| `backup(destDir, { compact? })` | Write a consistent online backup directory |
| `close()` | Flush, fsync, close |

### Durability (`fsyncPolicy`)

| Policy | Guarantees | Relative speed |
|---|---|---|
| `always` | fsync after every flush | slowest (safest) |
| `everysec` | fsync once per second (default) | fast, ≤1s loss window |
| `no` | OS decides when to flush | fastest, may lose seconds on power loss |

### Value storage mode (`valueMode`)

`valueMode` controls where value bulk lives:

```js
const db = await MiniDb.open({
  dir: './data',
  valueCodec: 'json',
  valueMode: 'memory', // 'memory' | 'disk' | 'auto'
});
```

- `memory` (default): values are kept in RAM, Redis-style. Reads are memory-bound.
- `disk`: values stay inline in the durable snapshot/WAL, while RAM keeps only
  keys, metadata, indexes, and small `{ file, off, len }` value pointers. Reads
  use synchronous positioned reads, so the public API stays synchronous. This
  allows value bulk to exceed RAM, at the cost of disk reads on cold `get()`
  paths.
- `auto`: at startup, compare the current `db.snapshot` + `db.wal` size with
  `maxMemoryBytes`. If the persisted files exceed the budget, open as `disk`;
  otherwise open as `memory`. If `maxMemoryBytes` is not set, `auto` falls back
  to `memory`.

### Memory limits

With `valueMode: 'memory'` the budget bounds keys plus values. With
`valueMode: 'disk'` it bounds the in-RAM key/metadata/index footprint, not the
value bulk. You can bound writes with an approximate memory budget:

```js
const db = await MiniDb.open({
  dir: './data',
  valueCodec: 'json',
  maxMemoryBytes: 512 * 1024 * 1024,
  maxMemoryPolicy: 'reject', // or 'evict-lru'
});
```

`reject` throws when a write would exceed the budget; `evict-lru` durably deletes
least-recently-used keys first. In `valueMode: 'disk'`, `evict-lru` trims keys to
bound the metadata/index footprint; it does not delete value bytes from disk
because values are already stored outside RAM. `db.stats.evictions` and
`db.stats.maxMemoryRejections` track the behavior.

The budget is tracked in **approximate logical bytes** (key + value + dt
metadata), not real JS heap usage. Actual per-key overhead is higher — on the
order of several hundred bytes per key for the Map entry, the ordered index
node, and bookkeeping — so a database of many small keys needs far more RAM
than `store.bytes` suggests. (Measured: ~0.6 KB of heap per key for tiny
records, so 1M small keys ≈ 600 MB of heap.) For millions of small keys,
prefer `valueMode: 'disk'` and/or budget accordingly.

### Online backup / restore

```js
await db.backup('./backup');
const restored = await MiniDb.restore('./backup', './restored', { valueCodec: 'json' });
```

`backup()` optionally compacts, then fences writes at a linearization point —
writes submitted while the backup runs reject with a `BACKUP_IN_PROGRESS`
error, and every write acknowledged before the fence is included — and copies
the snapshot, WAL, index definitions, and text postings into a sibling temp
directory that is fsync'd and atomically renamed over the destination (the
manifest, written last, is the commit marker). A failed backup leaves no
partial directory behind, and `restore()` can reopen the result.

### Write throughput & SSD endurance

MiniDb's write path is append-only and sequential, which is already
SSD-friendly. A few choices have an outsized effect on write amplification
and flash wear:

- **Use batch writes.** `set()` resolves after its own flush, so
  `for (const x of xs) await db.set(...)` issues one flush (and, under
  `fsyncPolicy: 'always'`, one fsync) per key. Coalesce writes with
  `db.batch([...])` / `db.mset([[k, v], ...])` (single atomic WAL frame) or
  `await Promise.all(xs.map(x => db.set(x)))` (group commit collapses the
  tick into one `writev` + one fsync).
- **Keep the default `fsyncPolicy: 'everysec'`.** It bounds fsyncs to ~1/s.
  `always` is the most durable but the hardest on flash (one fsync per
  flush); reserve it for data that must survive any crash.
- **Tune `compactThresholdBytes` for large datasets.** Compaction rewrites
  all live data, so steady-state write amplification is roughly
  `1 + liveDataBytes / compactThresholdBytes`. Raising the threshold (e.g.
  256 MiB–1 GiB) trades a larger WAL / longer recovery for less rewrite.
- **Observe it via `db.stats`.** `walBytesWritten`, `walFsyncs`,
  `snapshotBytesWritten`, `compactions`, `evictions`, `maxMemoryRejections`, and
  `queryIndexHits` let you measure real write volume, fsync rate, memory
  pressure, and index usage under your workload.

## RESP server (redis-cli compatible)

```bash
npm run server -- --dir ./data --port 6379
# or: node --import tsx src/server.ts --dir ./data --port 6379
```

Then in another shell:

```bash
redis-cli -p 6379 SET foo bar
redis-cli -p 6379 GET foo
```

Supported commands: `PING ECHO GET SET DEL EXISTS MGET MSET TTL DBSIZE COMPACT INFO QUIT`.

## Benchmarks

Measured on Node v24, 100-byte values (`npm run bench`, `N=100000`):

| Operation | Throughput |
|---|---|
| Raw `Map` set (baseline) | ~8.6 M ops/s |
| Raw `Map` get (baseline) | ~20 M ops/s |
| **DB get** (in-memory) | **~8.0 M ops/s** |
| **DB set, fsync=everysec** (concurrent, group commit) | **~725 k ops/s** |
| **DB set, fsync=no** (concurrent, group commit) | **~396 k ops/s** |
| DB set, fsync=always (sequential, 1 fsync/op) | ~328 ops/s |
| Compact snapshot of 100k keys | ~69 ms (12 MiB) |

Reads are memory-bound and track the raw `Map` closely. Writes are
disk-bound; **group commit** makes concurrent writes very fast, while
`synchronous` (`always`) writes pay the fsync cost one would expect from any
database. Numbers vary by machine/disk.

Query benchmarks (N=50k docs, 200 iters each, `node bench/query.js`):

| Query | Throughput |
|---|---|
| dt range (small result) | ~183 k ops/s |
| key prefix scan (~100 rows) | ~23 k ops/s |
| full-text search (latin / CJK) | ~350–490 ops/s |
| value filter, **no index** (full scan of 50k) | ~23 ops/s |

Indexed dimensions (key / dt / text) are fast; an unindexed value filter scans
the whole collection — create a secondary index (`createIndex`) for hot value
predicates.

For **ordered pagination within a group** (e.g. "sessions in a workspace ordered
by updatedAt"), use a **compound index** instead of fetching the whole group and
sorting in memory. On 10k sessions in one workspace, paginating with
`compoundRange` is ~20–40× faster than "fetch-all + sort", and stays
sub-millisecond at any offset.

Multi-process `ClusterDb` scaling across process counts × shard counts (the
headline: shard-affinity writes scale ~linearly until the single-shard speed
is reached; uniform cross-shard traffic pays lock handoffs):

```bash
pnpm bench:cluster   # bench/cluster.ts — spawns real writer/reader processes
```

## Testing

Three layers of tests, run with the built-in `node:test` runner (no deps):

```bash
npm test            # unit tests (fast)
npm run test:e2e    # end-to-end stability suite
npm run test:all    # both
```

The **unit tests** (`test/*.test.js`) cover each module: frame codec/CRC, WAL
group commit, store TTL, snapshot/compaction, recovery truncation, skip list,
secondary/full-text indexes, and the RESP server.

The **E2E stability suite** (`test/e2e/*.test.js`) covers crash-safety and
long-run behavior:

| File | What it verifies |
|---|---|
| `fuzz-model.test.js` | thousands of random ops match a reference model (seeded, reproducible) |
| `crash-recovery.test.js` | `kill -9` mid-write and mid-compaction → recovery is always consistent |
| `index-consistency.test.js` | key/dt/secondary/full-text indexes never drift from the store |
| `compaction-race.test.js` | heavy concurrent writes during compaction lose nothing |
| `recovery-matrix.test.js` | WAL corruption at head/mid/tail under `resync` vs `strict` |
| `durability.test.js` | `always`/`everysec`/`no` close-durability + many open/close cycles |
| `boundary.test.js` | key-length limits, large values, many keys, empty db |
| `soak.test.js` | sustained ops + heap stability (opt-in: `SOAK=30 npm run test:e2e`) |

The **cluster suite** (`test/cluster/*.test.ts`) covers the `ClusterDb`
sharding layer: topology/routing, merged scans, lock contention and lease
renewal in-process, cross-shard indexes/compaction, true multi-process
scenarios (concurrent writers on disjoint and shared shards, live cross-process
read visibility, read/write storms) and crash takeovers (`kill -9` → contiguous
recovery + stale-lock handoff).

## Design in one paragraph

Log-structured engine: all writes append to a CRC-framed **WAL** (group
committed, configurable fsync); all reads hit an in-memory `Map`. When the WAL
grows past a threshold, a **snapshot** of the live keys is written and the WAL
is rotated — **non-blocking**: writers keep appending to the WAL (which doubles
as a Redis-style rewrite buffer) while the snapshot is written, and pause only
for a brief final rotation. Recovery loads the latest
snapshot then replays the WAL, truncating any torn tail. Secondary indexes use
a Redis-style skip list for range queries. See
[`DESIGN_NOTES.md`](./DESIGN_NOTES.md) for the full rationale and the
source-code study behind each choice.

## Concurrency & multi-process

minidb is **single-writer**. Opening a directory for writing acquires an exclusive
lock file (`db.lock`); a second writer is rejected with a `LockError`. A lock is
taken over only when its owner PID is dead (stale-lock recovery), never merely
because it is old.

```js
// second process: throws LockError
await MiniDb.open({ dir: './data' });
// degrade to read-only instead of throwing
const ro = await MiniDb.open({ dir: './data', onLockFail: 'readonly' });
ro.get('k');        // ok (point-in-time view)
await ro.set('k');  // throws "read-only mode"
// open read-only alongside a writer
const r = await MiniDb.open({ dir: './data', readOnly: true });
```

For many clients, run the **RESP server** (single minidb process, many TCP
clients) — that is the intended concurrent-access model, like Redis.

### ClusterDb: multi-process sharding

When several **processes** must read and write the same logical database
without a server, `ClusterDb` shards the key space over N ordinary minidb
directories (each with its own WAL, snapshot, and `db.lock`):

```js
import { ClusterDb } from '@moonshot-ai/minidb/cluster';
const db = await ClusterDb.open({ dir: './data', shardCount: 16, valueCodec: 'json' });
await db.set('user:1', { name: 'alice' });      // routed by hash to one shard
await db.mset([['a:1', v1], ['b:2', v2]]);      // grouped per shard, atomic per shard
const all = await db.scan({ prefix: 'user:' }); // merged over all shards
await db.close();
```

- **Writes** never meet a single global writer: each process acquires shard
  write locks on demand (with retry up to `lockAcquireTimeoutMs`), caches them
  briefly (`lockPoolMaxShards`, LRU), and yields a held shard after
  `lockHoldMs` (default 250ms) so other processes are never starved. Throughput
  scales with the number of distinct shards being written — up to the
  single-shard speed of MiniDb per shard.
- **Reads** never take locks: they use the cached writer when the local
  process holds the shard, else a read-only instance that is revalidated
  against the shard files on every use, so a read that starts after another
  process's commit always observes it.
- **Consistency**: single-key and same-shard batch ops are strongly
  consistent (single writer per shard, atomic WAL frames). Cross-shard
  `mset`/`mdel`/`batch` are best-effort (atomic per shard, not globally;
  `crossShard: 'none'` rejects them instead). Scans merge per-shard snapshots,
  so entries from different shards may reflect different points in time.
- **Indexes** (`createIndex`/`createTextIndex`) are recorded in a cluster-wide
  registry and applied by every shard writer on open; `findEq`/`findRange`/
  `search` merge per-shard results (text scores are per-shard). Index
  management acquires every shard writer — run it from one process, off the
  hot path.
- Crash recovery is per shard: a lock left by a dead PID is taken over by the
  next opener, exactly like single MiniDb.

`crossShard: '2pc'` is reserved for a future two-phase commit and is rejected
today. Performance numbers across process/shard counts: run
`pnpm bench:cluster` (see `bench/cluster.ts`).

For a **rebuildable cache**, use `openOrRebuild`: a corrupt cache is discarded
and reopened empty, while a live-locked db is never destroyed:

```js
const db = await MiniDb.openOrRebuild(
  { dir: cacheDir, valueCodec: 'json' },
  { onRebuild: (err) => log.warn('cache rebuilt:', err.message) },
);
```

## Caveats / roadmap

- In the default `valueMode: 'memory'`, the dataset must fit in RAM Redis-style.
  Use `valueMode: 'disk'` for larger-than-RAM value bulk; cold reads then perform
  synchronous positioned reads against the snapshot/WAL.
- Full-text index postings are stored on disk (larger-than-RAM); only the term
  dictionary and per-doc metadata stay in memory. Postings are rebuilt from the
  store on open and on compaction. Search reads postings synchronously, so a
  cold, very large postings list can briefly block the event loop.
- Compaction is **non-blocking for writes**: the WAL itself acts as a
  `BGREWRITEAOF`-style rewrite buffer, so the (slow) snapshot is written while
  writers keep appending. Writes pause only for the final rotation (a flush, a
  tail copy, and two atomic renames). A pre-copy drains most of the tail
  beforehand when writes are slow enough; under sustained writes that outrun
  the pre-copy, the rotation absorbs a larger tail — the same bounded
  end-of-rewrite pause Redis accepts for its AOF diff flush — so compaction
  always terminates. Mid-compaction crashes leave `db.*.tmp` files behind,
  which the next writer open removes automatically.
- Snapshot encoding runs on the main thread (chunked + yielding); offloading to
  a `worker_thread` is a planned optimization.
- Single minidb directory = single process / single writer. For multi-process
  access use `ClusterDb` (above): sharding scales writes, but hash routing
  means whole-range scans fan out to all shards, and uniform cross-shard write
  patterns pay shard-lock handoff costs (`lockHoldMs` per yield) — workloads
  with per-process shard affinity scale best.

## Credits

Design distilled from reading: Redis (`references/redis`), the SQLite WAL
paper, NeDB (`references/nedb`), Bitcask (`references/bitcask`), and the
cstack SQLite tutorial (`references/db_tutorial`).