suaveplan/docs/drive/index-and-paths.md

The Two Indexes — Directory Metadata and File Location

The user's question: "a metadata object of nested directory indexes for efficiency and a file with an index to its location within the nested directories."

This document specifies that. There are exactly two indexes at the drive layer, and both live in storage as bitpacker-encoded blobs at well-known keys.

Why two indexes

A naive drive uses one storage key per file path. Listing a directory then means scanning every key and filtering by prefix — O(n) over the whole drive. A 1M-file drive becomes painful fast, and a content-addressed backend (ContentAddressedStorage) loses path information entirely because the key is a hash of the content.

Two indexes solve this:

1. Directory index — for efficient listing and metadata lookup.
2. File location index — for resolving a logical path to whatever the storage layer actually keeps.

Both are bitpacker-encoded (@suaveplan/bitpacker) so the on-disk size is small, deltas are cheap to gossip across the mesh, and writes are a single setPartial against a known offset.

Index 1 — Directory index

A nested-tree object, stored as a single bitpacker blob at the drive's root metadata key (<drive-id>/__meta/dirs). One node per directory:

interface DirEntry {
  name: string;          // single path component, no '/'
  type: 'dir' | 'file';
  fileLocId?: string;    // present iff type === 'file'; key into the file location index
  childIds?: string[];   // present iff type === 'dir'; ordered list of child DirEntry ids
  perm?: number;         // POSIX-ish bits, optional
  mtime?: number;        // unix ms, optional
  size?: number;         // bytes, optional (mirrored from file metadata for fast list)
}

interface DirIndex {
  rootId: string;
  entries: Map<string, DirEntry>;  // id → DirEntry
  version: number;                 // monotonic; bumps on every write
}

A path like /photos/2026/wedding.jpg resolves by walking from the root: read entries[rootId], find child with name === 'photos', follow its id, find child '2026', follow, find child 'wedding.jpg' (type 'file', with a fileLocId).

Properties

• list(prefix) is O(depth + children), not O(total files), because we only walk the relevant subtree.
• Stat-without-read is O(depth) — the size and mtime live on the entry, no need to fetch the file location.
• Rename is O(1) — change the name field of one entry, increment version, write.
• Move is O(1) — remove a childId from one parent's list, add it to another's.
• Hardlinks are possible — two parents can share the same child id (the file location is unaffected). The drive layer policies whether to allow them.

Concurrency

The directory index is one blob, so concurrent writes need a CAS. Three strategies:

1. Optimistic CAS — read, edit, write with if-match: version. Loop on conflict.
2. Per-directory blobs — split the index into one blob per directory; only the directory being modified takes a CAS. Better at scale, more keys.
3. CRDT — use @suaveplan/crdt to make the index conflict-free. Right for multi-writer drives where mesh reconciliation matters more than single-write throughput.

Strategy 1 is the genesis default. Strategy 2 kicks in when a single directory regularly exceeds 10k entries. Strategy 3 is opt-in when the drive is multi-writer.

Index 2 — File location index

A flat map from fileLocId → FileLocation, also bitpacker-encoded, stored at <drive-id>/__meta/locs:

interface FileLocation {
  fileId: string;          // stable, unique per file (not per version)
  version: number;         // CoW version; bumps on every write
  size: number;
  checksum: string;        // 'blake3:<hex>' for whole-file integrity
  storageHints: StorageHint[];  // ordered: fastest first
}

type StorageHint =
  | { kind: 'inline'; bytes: Uint8Array }                              // tiny files (<1 KiB) live in the location entry itself
  | { kind: 'whole'; storageId: string; key: string }                  // whole-blob layout: one storage key holds the file
  | { kind: 'sparse-file'; storageId: string; key: string; chunkSize: number }  // chunks plugin sparse layout
  | { kind: 'chunk-keys'; storageId: string; manifestKey: string }     // chunks plugin per-chunk keys + manifest
  | { kind: 'mesh'; manifestKey: string };                             // mesh-only: this drive doesn't have local copy

The storageHints array lets a single file have multiple representations simultaneously. A file might be:

• inline if tiny,
• in S3 with kind: 'whole' for cold storage,
• in OpfsStorage with kind: 'sparse-file' for hot local access,
• and known to the mesh (kind: 'mesh') so peers can serve chunks.

When drive.read(path) runs, the read middleware resolves path → fileLocId → FileLocation, then walks storageHints in order until one yields bytes. The chunks plugin reads manifestKey to learn the per-chunk layout and reassembles. The mesh plugin tries peers for any missing chunk.

How a write happens

drive.write("/photos/2026/wedding.jpg", bytes)
  ↓
[middleware: chunks plugin] split bytes into chunks, encrypt each (XChaCha20-Poly1305),
                            sign each (Ed25519), build manifest, sign manifest
  ↓
[middleware: dedup plugin (optional)] hash content; if it already exists in the
                                       content-addressed pool, skip the write and
                                       just point at the existing chunks
  ↓
[core: storage write] write each chunk to the chosen storage layout
                      (sparse-file or chunk-keys), write the manifest
  ↓
[middleware: chunks plugin (post)] return new FileLocation with the chunk pointer
  ↓
[drive: index update] CAS-update the file location index with the new FileLocation
                      CAS-update the directory index with the new DirEntry
                      (creating intermediate directories as needed)
  ↓
[middleware: mesh plugin (post)] gossip the new chunk inventory to peers
                                  via NetworkBus 'cd:advertise'

How a read happens

drive.read("/photos/2026/wedding.jpg")
  ↓
[drive: index resolve] walk dir index from root → DirEntry → fileLocId → FileLocation
  ↓
[middleware: chunks plugin (pre)] load manifest, parse chunk references
  ↓
For each chunk:
  [middleware: cache plugin (optional)] check local cache
  [core: storage read] try storageHints in priority order:
    'inline' → return bytes
    'whole'  → storage.get(key)
    'sparse-file' → storage.getPartial(key, chunkOffset, chunkOffset + chunkSize)
    'chunk-keys'  → storage.get(`${storageId}/${chunkId}`)
    'mesh'        → ask drive-mesh, which races peers via NetworkBus 'cd:request'
  ↓
[middleware: chunks plugin (verify)] verify Ed25519 sig, decrypt AEAD, check BLAKE3
  ↓
[middleware: chunks plugin (reassemble)] concat into the original bytes
  ↓
return Uint8Array

Why bitpacker, not JSON

The two indexes are read on every list, stat, and read — they belong in memory. Bitpacker buys us:

• Compactness — typical directory entry is ~20 bytes vs ~120 for JSON.
• Schema evolution — versioned schemas with forward/backward compatibility live in @suaveplan/schema-registry and @suaveplan/bitpacker.
• Delta gossip — the mesh advertises changes to the index, not the whole index. A 1 MiB index with 100 changes/s gossips ~2 KiB/s.

JSON is fine for the user-facing snapshot/export format. It's not fine for the hot-path index.

Path-to-key mapping summary

"/photos/2026/wedding.jpg"
       ↓ (DirIndex walk)
DirEntry { name: "wedding.jpg", type: "file", fileLocId: "f-1729...." }
       ↓ (FileLocation lookup)
FileLocation { fileId: "f-1729...", version: 3, storageHints: [
   { kind: "sparse-file", storageId: "local", key: "files/f-1729...", chunkSize: 65536 },
   { kind: "mesh", manifestKey: "manifests/f-1729...-v3" },
] }
       ↓ (chunks plugin)
manifest = bitpacker.decode(storage.get("manifests/f-1729...-v3"))
   → 14 chunks, each at offset i * 65536, signed by drive-id, AEAD-encrypted with file key
       ↓ (per-chunk read + verify + decrypt)
Uint8Array (the photo)

This is the whole "metadata object of nested directory indexes + a file with an index to its location" you asked for, expressed as a precise contract.

How a 100-file drive maps onto the storage backend

A common question: if I save 100 files through the drive, do I get 100 files on disk, or one big partition file? The answer depends on which backend you configure. The drive layer's two indexes plus the chunks plugin's layout selection produce different on-disk shapes:

Backend	Files-on-disk for 100 logical files (~50 MiB each)	Layout	Why
MemoryStorage	0 (in-process map)	sparse-file	partialWrites=true
FileStorage (Node fs)	~202 (100 chunk-files + 100 manifests + 2 indexes)	sparse-file	partialWrites=true
OpfsStorage (browser)	~202 OPFS handles	sparse-file	partialWrites=true
S3	~80,202 objects (one per chunk + manifests + indexes)	chunk-keys	partialWrites=false, RMW too expensive
IndexedDbStorage	~80,202 IDB rows	chunk-keys	partialWrites=false
SqliteStorage	1 .sqlite file with ~80k blob rows	sparse-file via incremental_blob_open	One file ≈ one partition
FatStorage	1 FAT disk image (mountable by the OS)	sparse-file inside the FS-in-a-file	True "partition file"
ContentAddressedStorage wrapping any backend	~80k unique chunk-blobs (deduped across files)	chunk-keys	Hashes coalesce identical content

So FileStorage gives you ~2 files per logical file (the sparse chunk-file plus its manifest). S3 gives you ~800 objects per logical file (one per chunk plus manifest). SqliteStorage and FatStorage give you genuine one-file-equals-one-partition semantics — pick these when you need atomic backup, mountable export, or fixed-size budgets.

Tiny files (<1 KiB) skip the chunks pipeline entirely via the kind: 'inline' storage hint — bytes live inside the FileLocationIndex itself. So a 100-file drive where 30 files are <1 KiB is closer to 172 files on disk with FileStorage.

The drive layer never produces "100 files mirroring user paths in plaintext on disk" — that is by design, because path mirroring leaks structural metadata to whichever backend holds the bytes (S3 admins, OPFS quotas, FAT disk inspectors). If plaintext path-mirror semantics are genuinely required, skip the drive layer and write to FileStorage directly; the drive's whole job is to abstract over storage.

Reading further

• plugins.md — what each middleware in the chain actually does.
• encryption.md — the chunks plugin in cryptographic detail.
• mesh-and-sharing.md — what kind: 'mesh' means.
• mesh-protocol.md — the chunk-request envelope forms (whole-file, specific, bitset).
• dehydrated-drives.md — server-signed templates that pre-configure folder structure with bytes arriving later.