Storage: Add support for storing nars using Content-Defined Chunking (CDC)

[kalbasit]

It would be great and space saving to store nars in chunks.

[kalbasit]

Leaving this here from a discussion with Claude about #660.

Content-Defined Chunking (CDC) Feasibility Study

This document outlines the feasibility, architecture, and implementation steps for adding Content-Defined Chunking (CDC) to the ncps storage layer.

Overview

Implementing CDC would allow ncps to deduplicate NAR files at a sub-file level. Instead of storing each NAR as a single blob, ncps would break it into variable-sized chunks based on content. Identical chunks across different NAR files (or different versions of the same package) would be stored only once.

Benefits

• Storage Efficiency: Significant deduplication, especially for similar Nix packages.
• Transfer Efficiency: Potential to only download missing chunks from upstreams (if upstreams support CDC).
• Resilience: Data corruption in one chunk only affects files containing that chunk.

Challenges

• Read Latency: Reassembling a NAR from many chunks adds overhead, especially on high-latency storage like S3.
• Complexity: New storage layer, database schema updates, and more complex Garbage Collection (GC).
• Database Load: Tracking many chunks and their references increases database size and query complexity.

Proposed Architecture

1. CDC Library

We recommend using fastcdc-go which implements the FastCDC algorithm. It is performant and widely used in the Go ecosystem.

2. Storage Layer Refactoring

CDC requires a two-layer storage approach:

• Chunk Store: Responsibility for storing and retrieving raw chunks (content-addressed by their hash, e.g., SHA-256).
• NAR Store (Chunked): Responsibility for orchestrating the chunking of NARs and reassembling them from the Index.

New Interface: ChunkStore

type ChunkStore interface {
    HasChunk(ctx context.Context, hash string) bool
    GetChunk(ctx context.Context, hash string) (io.ReadCloser, error)
    PutChunk(ctx context.Context, hash string, data []byte) error
}

3. Database Schema Changes

The database needs to track chunks and their association with NAR files.

New Tables

• chunks: Stores chunk metadata (hash, size).
• nar_file_chunks: A junction table with a sequence number to define the order of chunks in a NAR file.

Important

Reference Counting: The database must track how many NAR files use each chunk to ensure chunks are only deleted during GC when they are no longer referenced.

Implementation Plan

Phase 1: Foundation

• Add fastcdc-go dependency.
• Define ChunkStore interface and implementations (Local and S3).
• Implement database migrations for chunks and nar_file_chunks.

Phase 2: Core Implementation

• Implement ChunkedNarStore that wraps ChunkStore.
• Update PutNar to perform chunking and store the index in the database.
• Update GetNar to reassemble chunks on-the-fly via a streaming io.Reader.

Phase 3: Garbage Collection

• Update the GC logic to safely delete unreferenced chunks.

Verification Plan

Automated Tests

• Unit Tests: Test the chunking algorithm with various file sizes and overlapping content.
• Integration Tests: Verify that PutNar and GetNar cycle works correctly and that files are identical before and after.
• Benchmarks: Measure the overhead of reassembly compared to single-file storage.

Manual Verification

• Compare storage usage before and after ingesting multiple versions of the same package (e.g., nixpkgs stdenv).
• Verify that deleting a NAR file correctly handles chunk reference counts.

Conclusion

Difficulty: Moderate to High.
While the individual components are well-understood, integrating them into the existing streaming download/upload pipeline without significant performance regressions requires careful implementation.

Recommendation: Start with an optional "CDC Backend" that users can enable if storage savings are more important than absolute read latency.