# Versions Directory Sharding

## Context

All version files for documents in a given directory share a single flat `versions/` subdirectory. A frequently-edited document or a directory with many documents accumulates thousands of files in one directory. `findVersions()` calls `os.ReadDir()` on the entire directory and filters by prefix, making it O(all entries) instead of O(document versions). This is the hot path — called on every Get, CurrentVersion, Write, and Versions request.

## Scope

This is a **server-side storage change only**. The publish CLI and all other client commands are thin network wrappers — they send QUIC requests and never touch the versions directory. No client code changes needed.

## Problem Dimensions

Two axes of growth compound in the flat layout:
1. **Many documents in one directory** — 1000 docs x 50 versions = 50K entries
2. **Many versions of one document** — 1 doc with 10K versions = 10K entries

## Scaling Analysis

With per-document subdirectories, no operation scans the top-level `versions/` directory:

| Operation | Current (flat) | New (per-doc subdir) |
|-----------|---------------|---------------------|
| `findVersions("doc.md")` | `ReadDir(versions/)` scans ALL entries | `ReadDir(versions/doc.md/)` scans only that doc |
| `getVersion("doc.md", 3)` | Direct path: O(1) | Direct path: O(1) |
| `Write` | Create file in flat dir | Create file in per-doc dir |
| `BuildHashIndex` | Walks tree, skips `versions/` | Same — `SkipDir` skips entire subtree |

Directory lookup for `versions/{docname}/` is O(log n) on ext4 (htree) and APFS (B-tree):
- 10K documents: ~14 comparisons. Negligible.
- 100K documents: ~17 comparisons. Still negligible.

The one linear scan remaining is `findVersions` reading a single document's version directory. A document with 10K versions produces ~1ms of ReadDir. This matches the current best case and can be addressed with version-range bucketing later if ever needed.

## Options Considered

### A: Per-Document Subdirectory (recommended)

```
versions/
  doc.md/
    v1
    v2
    v3
  other.md/
    v1
    v2
```

Symlink: `versions/doc.md/v3`

Pros: Eliminates cross-product, `findVersions` scoped to one doc, simple naming.
Cons: Extra directory per document, migration needed.

### B: Name-Prefix Sharding

```
versions/
  do/
    doc.md.v1
    doc.md.v2
  ot/
    other.md.v1
```

Pros: Spreads entries across shard buckets.
Cons: Uneven distribution, does NOT help many-versions-of-one-doc, `findVersions` still scans shard dir.

### C: Version-Range Bucketing

```
versions/
  doc.md/
    v0001-1000/
      v1 ... v1000
    v1001-2000/
      v1001 ...
```

Pros: Caps leaf directories at fixed size.
Cons: Overkill for typical use (< 100 versions), `findVersions` must merge across buckets, cross-bucket complexity in chain verification.

## Plan: Option A with Lazy Migration

### New Layout

```
root/
  doc.md              → versions/doc.md/v3
  versions/
    doc.md/
      v1
      v2
      v3
```

### Migration Strategy

Zero-downtime, lazy migration. Existing installs keep working immediately after upgrade:

- **Reads** detect which layout a document uses and handle both transparently
- **Writes** trigger migration of that document to the new layout before writing the new version
- New documents always use the new layout
- The pattern already exists in the codebase (`migrateFlatFile` at line 1087 of store.go)
- Optional: batch migration CLI command for proactive migration of existing stores

### Implementation

#### Step 1: Extract path helpers (pure refactor)

Add two functions in `store.go`:

```go
func versionFilePath(versionsDir, base string, version int) string {
    return filepath.Join(versionsDir, base, fmt.Sprintf("v%d", version))
}

func versionSymlinkTarget(base string, version int) string {
    return filepath.Join("versions", base, fmt.Sprintf("v%d", version))
}
```

Update all 12 call sites. Initially produce OLD layout paths — pure refactor, no behavior change.

#### Step 2: Add layout detection

```go
func isPerDocLayout(versionsDir, base string) bool {
    info, err := os.Stat(filepath.Join(versionsDir, base))
    return err == nil && info.IsDir()
}
```

#### Step 3: Update helpers to use new layout

- Writes always create per-document subdirectory and use new layout
- Reads detect which layout exists and handle both

#### Step 4: Update `findVersions`

New layout: `os.ReadDir(filepath.Join(versionsDir, base))` — reads only that document's versions, parses `v{N}` names.
Old layout: falls back to current scan-and-filter logic.

#### Step 5: Add `migrateToPerDocDir`

Modeled on existing `migrateFlatFile`. Called from `Write` before creating new version when old layout detected:

1. Create `versions/{base}/` directory
2. Move all `{base}.v{N}` files into `versions/{base}/v{N}`
3. Update symlink atomically

#### Step 6: Verify `BuildHashIndex`

Currently skips `versions/` via `filepath.SkipDir`. This already skips the entire subtree — no change needed.

### Files to Modify

- `server/internal/store/store.go` — path helpers, layout detection, migration, findVersions
- `server/internal/store/store_test.go` — tests for both layouts, migration, mixed layout coexistence

### Verification

1. Run existing tests after Step 1 refactor — must all pass with no behavior change
2. Add tests for new layout: write, read, findVersions, getVersion, verifyChain, archive
3. Add test for migration: create documents in old layout, trigger write, verify files moved
4. Add test for mixed layout: old and new layout documents coexist in same directory
5. Run `bash pre-commit.sh`
6. Manual smoke test: start server with existing content, publish a document, verify new layout

---

## COMPLETE — shipped the day it was written

Implemented in **PR #90 (`d7cb68a`, merged 2026-04-08)** — per-document
`versions/{base}/v{N}` subdirectories with lazy migration and flat-layout
read fallback, per Option A above. The store was later hoisted from
`server/internal/store` to `protocol/store` (#120), where
`isPerDocLayout` / `resolveVersionFile` live today.

Record correction (2026-07-05): the soul index listed this plan as
"fully specced; no code yet, unstarted" from a 2026-05-31 verification
pass that missed #90 — likely because the plan doc carried no completion
stamp (this section now closes that gap) and the commit says
`feat(filestore)` while the plan says "sharding".