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:

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:

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

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".