Storage System

How Xudanu stores and retrieves documents: content-addressed chunks, incremental checkpoints, and O(1) integrity verification.

1. Why We Needed a New Storage Engine

Xudanu's storage engine was designed to solve four specific problems that emerge when a content-addressed hypertext system scales beyond a prototype.

Figure 1: Four requirements that shaped the storage design, unified by content-addressed chunking.

The key insight: Xudanu already uses BLAKE3 content fingerprints throughout the engine — for transclusion identity, content deduplication, and the ContentAddressIndex. Reusing the same fingerprint as the storage key creates a system where identity, caching, and persistence all speak the same language.

2. The Problem with Monolithic JSON

The original storage mechanism wrote the entire server state to a single server.json file on checkpoint. This worked for prototyping but had three critical flaws that would prevent production use:

{
  "works": [
    { "be_id": 1, "edition": {
      "entries": [
        /* 10,000 entries */
      ]
    }},
    /* 5,000 more works */
  ],
  "clubs": /* ... */,
  "links": /* ... */
}

manifest.json        /* 12 KB index */
chunks/
  0a/
    0a3f...b2c1      /* entry chunk */
    0a7e...d4a8      /* entry chunk */
  3b/
    3bc9...1f07      /* root chunk */
  /* 256 shard dirs max */

3. Architecture: Three-Layer Storage

The storage system is organized in three layers, each with a distinct responsibility. The top layer is a lightweight JSON index; the middle layer handles serialization of document structures into binary chunks; the bottom layer is the content-addressed file store.

Figure 2: Three layers separate concerns — indexing, serialization, and physical storage.

4. ChunkStore: Content-Addressed Storage

ChunkStore is the foundation. It maps arbitrary byte sequences to files named by their BLAKE3 hash. The API is intentionally minimal:

pub struct ChunkStore {
    base_dir: PathBuf,
    cache: Mutex<Cache>,         // LRU, 1024 entries
    cache_hits: AtomicU64,
    cache_misses: AtomicU64,
}

impl ChunkStore {
    pub fn write_chunk(&self, data: &[u8]) -> Result<[u8; 32], ChunkError>;
    pub fn read_chunk(&self, hash: &[u8; 32]) -> Result<Vec<u8>, ChunkError>;
    pub fn chunk_exists(&self, hash: &[u8; 32]) -> bool;
    pub fn verify_chunk(&self, hash: &[u8; 32]) -> Result<(), ChunkError>;
}

Write Path

Figure 3: Write path — hash, check existence, atomic write, cache.

Read Path

Every read_chunk checks the LRU cache first. On a cache hit, no disk I/O occurs. On a miss, the chunk is read from disk and its BLAKE3 hash is verified against the requested hash before returning. This means corruption is detected at read time, not just at verification time.

5. BLAKE3 as the Universal Fingerprint

BLAKE3 serves double duty in Xudanu: it is both the content fingerprint used for transclusion identity and the storage key used for chunk addressing. This is not coincidental — it is a design decision that eliminates an entire class of mapping overhead.

Figure 4: BLAKE3 unifies content identity and storage addressing.

6. Edition Chunking: Breaking Documents into Pieces

An Edition (Xudanu's document data structure) is an O-tree with entries at integer positions. Rather than serializing an entire edition as one blob, edition_chunks.rs splits it into a root chunk and multiple entry chunks, each holding up to 256 entries.

Figure 5: An Edition with 300 entries becomes 3 chunks: 1 root + 2 entry chunks. Entry chunks hold up to 256 entries each.

Work Chunk Refs

A Work (document) contains its current edition plus a revision history. Each revision is stored as its own edition chunk tree. The WorkChunkRef is the manifest's pointer to a work's data:

pub struct WorkChunkRef {
    be_id: BeId,
    owner: Option<BeId>,
    revision_count: u64,
    current_root: EditionChunkRef,          // current version
    history: BTreeMap<u64, EditionChunkRef>, // past versions
    read_club: Option<BeId>,
    edit_club: Option<BeId>,
    sponsors: Vec<BeId>,
}

Revisions are loaded lazily. work_from_chunks_current() reads only the current edition. work_load_revision() loads a specific revision by number. This means opening a document with 200 revisions reads 1 edition, not 201.

Provenance Chunks

The root chunk of an edition may also contain an optional provenance_hash pointing to a separate ProvenanceChunk. This chunk stores SpanProvenance data that tracks where each span of content originally came from — essential for transclusion tracking. When content is transcluded from one document into another, the provenance record preserves the source document's identity and span location, enabling correct attribution and back-references even after the source document is modified.

7. Manifest: The Lightweight Index

The manifest (manifest.json) is the only JSON file in the system. It contains references (not data) to all works, clubs, links, and administrative state. It is small by design:

pub struct Manifest {
    format_version: u32,                // currently version 3
    created_at: String,                 // ISO 8601 timestamp
    server_version: String,             // cargo package version
    checksum: String,                   // SHA-256 of content
    grand_map_id_counter: BeId,
    session_counter: u64,
    operation_counter: u64,
    system_clubs: SystemClubs,
    works: Vec<(BeId, WorkChunkRef)>,   // references to chunk trees
    clubs: Vec<ClubChunkRef>,
    standalone_editions: Vec<StandaloneEditionChunkRef>,
    links: Vec<LinkEntry>,
    link_counter: BeId,
    admin: AdminEntry,
    reconcile_store: ReconcileStore,       // federation reconciliation
    reconcile_counter: u64,
    federation: Option<FederationSnapshot>,
    content_address: Option<ContentAddressIndex>,
    blob_metas: Vec<BlobMetaEntry>,        // binary blob metadata
    key_history: Option<KeyHistoryEntry>,  // server key rotation history
}

Club Chunk Refs

Each club is stored as its own chunk tree. The ClubChunkRef in the manifest captures all club metadata:

pub struct ClubChunkRef {
    be_id: BeId,
    name: Option<String>,
    signature_club: Option<BeId>,
    work_root: WorkChunkRef,
    default_read_club: Option<BeId>,
    default_edit_club: Option<BeId>,
    is_personal: bool,                        // personal identity clubs
    display_name: Option<String>,             // human-readable name
    credential: Option<Credential>,           // password/boo auth
    encrypted_signing_key: Option<EncryptedSigningKey>,
    members: Vec<BeId>,
    sponsored_works: Vec<BeId>,
}

Figure 6: The manifest references chunks by BLAKE3 hash. Chunk data lives separately.

Checksum Protection

The manifest includes an SHA-256 checksum computed over its own content (with timestamp and version fields zeroed). On load, the checksum is recalculated and compared. If they don't match, the manifest is rejected with a ChecksumMismatch error. This catches accidental edits, partial writes, and bit-level corruption.

8. Incremental Checkpoints

The most significant performance benefit of chunked storage is incremental checkpoints. When a user edits a document:

Figure 7: With 10,000 documents and 1 edit, the old system writes all 10K. The new system writes the changed edition's chunks plus the manifest.

The checkpoint path in server.rs (checkpoint_to_store()) follows this sequence:

1. Iterate works — skip if cached chunk_ref exists, serialize dirty ones
2. Iterate clubs — skip if not in dirty_clubs set and cached ref exists
3. Iterate standalone editions — skip if cached ref exists
4. Collect all references into the manifest
5. Write manifest atomically (tmp + rename)
6. Run GC to remove orphaned chunks
7. Log: "Checkpoint saved in Xms (dirty: W/C/E works/clubs/editions)"

Dirty Tracking

Incremental checkpoints rely on precise dirty tracking to avoid re-serializing unchanged data. Each entity type uses a different strategy:

Figure 8: Works use cached refs as implicit dirty flags. Clubs use an explicit HashSet for precise tracking.

9. Data Integrity and Verification

Xudanu provides a built-in verification tool: xudanu-server verify <data-dir>. This command performs a comprehensive integrity check across all stored data.

Verification Pipeline

Figure 9: Five-stage verification catches corruption, missing data, and storage leaks.

Report Output

$ xudanu-server verify /tmp/xudanu-data

Verification report:
  Chunks: 1,247 total, 1,247 verified
  Works: 50 ok, 0 failed
  Clubs: 3 ok, 0 failed
  Standalone editions: 12 ok, 0 failed
  Status: OK

The VerifyReport tracks: chunks verified, chunks corrupt (hash mismatch), chunks missing (referenced but not on disk), chunks orphaned (on disk but not referenced), deserialization errors, and per-type (work/club/edition) success/failure counts. A single failure in any category makes the overall status ISSUES FOUND.

10. Garbage Collection

After every checkpoint, the server automatically runs gc_orphaned_chunks() to reclaim disk space occupied by chunks no longer referenced by any work, club, or standalone edition. This prevents unbounded growth as documents are edited and old chunk trees are superseded.

Figure 10: Garbage collection reclaims disk space by removing chunks no longer reachable from the manifest.

The GC process is safe because it runs after the manifest has been atomically written. Any chunk that was referenced by the previous manifest but is no longer referenced by the new one is guaranteed to be an orphan — the new manifest's references are the single source of truth.

11. Federation: Chunk Replication

Content-addressed storage is a natural fit for federation. When two Xudanu servers synchronize, they exchange content at the chunk level. Because chunk identity is determined by content (BLAKE3 hash), peers can:

Figure 11: Federation sync exchanges only missing chunks. Shared content (same hash) is never sent twice.

The chunk-based federation protocol works in three steps:

12. Performance Characteristics

The storage system was designed for the access patterns that Xudanu actually exhibits: frequent writes to a small number of active documents, infrequent reads of historical revisions, and periodic full checkpoints.

LRU Cache Behavior

The 1,024-entry LRU cache is particularly effective for Xudanu's workload. A user typically edits a handful of documents at a time. Each edit re-reads the same edition chunks and writes new ones for changed entries. The hot set (current editions of active documents) fits comfortably in 1,024 entries.

Figure 12: LRU cache with 1,024 entries covers the active working set of most sessions.

13. File Layout and Operations Guide

Directory Structure

data-dir/
  manifest.json                  # Lightweight index (SHA-256 checksummed)
  server.key                     # Server identity key (encrypted or plaintext)
  blobs/                         # Binary blobs (images, attachments)
    {blake3-hex}                 # Content-addressed binary data
  chunks/                        # Edition and work data
    00/                          # Shard 00
      {64-char-blake3-hex}       # One file per unique chunk
    01/                          # Shard 01
      ...
    ff/                          # Shard ff
      ...
  security.log                   # Chained security audit log
  security.log.seed              # Chain verification seed

Operational Commands

Blob Storage

Binary blobs (images, attachments, and other non-text data) are stored in the blobs/ directory using the same content-addressed scheme as edition chunks. Each blob's filename is its BLAKE3 hash, ensuring automatic deduplication.

The manifest tracks blob metadata via BlobMetaEntry records:

pub struct BlobMetaEntry {
    content_hash: [u8; 32],       // BLAKE3 of blob data
    byte_size: u64,                // original file size
    mime_type: String,             // e.g. "image/png"
    preview_hash: Option<[u8; 32]>,// thumbnail/preview BLAKE3
    metadata: HashMap<String, String>, // extensible metadata
}

Key History

The manifest stores a KeyHistoryEntry that enables key rotation verification across server restarts:

pub struct KeyHistoryEntry {
    server_id: BeId,
    entries: Vec<KeyHistoryRecord>,
    rotation_proofs: Vec<SignedProof>,
    current_key_id: String,
}

Each key rotation generates a signed proof that the old key authorized the new key. On startup, the server verifies the entire chain from the initial key to the current key. This prevents an attacker who compromises an old key from forging subsequent rotations.

Recovery Scenarios

Figure 13: Three guarantees provided by the storage architecture.