Nydus Chunk Deduplication Mechanism: How Dragonflyoss/Nydus Eliminates Redundant Container Data

Nydus eliminates redundant storage and network traffic by deduplicating identical 1 MiB chunks across different container images and versions using a two-stage algorithm that combines DBSCAN clustering with exponential smoothing to build a reusable chunk dictionary.

Nydus stores container images as a metadata bootstrap plus a set of data blobs that are split into fixed-size chunks of approximately 1 MiB. To minimize storage costs and accelerate downloads, the Nydus chunk deduplication mechanism identifies identical chunks that appear across different images or across different versions of the same image, storing only one physical copy in a chunk dictionary (chunkdict) that subsequent builds can reference.

How Nydus Chunk Deduplication Works

The deduplication process operates at the chunk level rather than the file or layer level, enabling finer-grained reuse. When converting an OCI image to Nydus format, the builder computes a digest (SHA‑256, Blake3, etc.) for each chunk. If that digest already exists in a provided chunk dictionary, the builder reuses the existing blob reference instead of uploading new data.

This approach delivers two primary benefits:

• Cross-image deduplication eliminates redundant copies of common libraries or base images shared across many containers.
• Version-wise deduplication ensures that updated image versions reuse unchanged chunks from previous releases, reducing incremental update sizes.

The Two-Stage Deduplication Algorithm

The chunk dictionary generation algorithm implemented in src/bin/nydus-image/deduplicate.rs proceeds in two distinct stages to maximize reuse across large image corpora.

Stage 1: Cross-Image Deduplication with DBSCAN Clustering

The first stage identifies groups of images that share significant chunk overlap using DBSCAN (Density-Based Spatial Clustering of Applications with Noise).

The algorithm loads all chunk metadata from a SQLite database (ChunkdictChunkInfo rows) and computes a distance metric between every pair of images:

[ d(x,y)=1-\frac{\lvert C(R_x)\cup C(R_y) \rvert - \lvert C(R_x)\cap C(R_y) \rvert}{\lvert C(R_x)\cup C(R_y) \rvert} ]

Where C(R_x) represents the set of unique chunk digests belonging to image x. This distance function is implemented in Algorithm::distance within deduplicate.rs.

DBSCAN marks an image as a core point if it has at least MinPts neighbors within radius γ (default γ = 0.5). Core points and their density-reachable neighbors form a cluster. For each cluster, the algorithm selects chunks that appear in at least 90 % of the cluster’s images, adding these high-frequency chunks to an intermediate dictionary.

Stage 2: Version-Wise Deduplication with Exponential Smoothing

The second stage refines the dictionary by favoring chunks that persist across multiple versions of the same image lineage, using exponential smoothing to score chunk popularity over time.

For a chronological sequence of image versions, the smoothing score updates as:

[ S_t = \alpha , Y_{t-1} + (1-\alpha) S_{t-1},\qquad \alpha = 0.5 ]

Where Y_{t-1} equals 1 if the chunk appeared in the previous version, otherwise 0. This logic resides in Algorithm::exponential_smoothing in deduplicate.rs.

After computing scores, the algorithm applies a configurable threshold (e.g., score > 0.8) to filter out transient chunks. Surviving chunks are deduplicated by their digest using a unique_chunks map (around line 52 of deduplicate.rs) before being materialized into the final dictionary.

Chunk Dictionary Implementation

The chunk dictionary abstraction decouples the deduplication logic from storage details, enabling both in-memory and persistent implementations.

The ChunkDict Trait and HashChunkDict

The ChunkDict trait defined in builder/src/core/chunk_dict.rs specifies the interface for chunk lookup and insertion:

pub trait ChunkDict: Sync + Send + 'static {
    fn get(&self, digest: &str) -> Option<ChunkInfo>;
    fn insert(&mut self, digest: String, info: ChunkInfo);
}

The default implementation, HashChunkDict, stores the digest-to-chunk mapping in an in-memory HashMap keyed by the chunk’s cryptographic digest. This structure supports SHA‑256, Blake3, and other digest algorithms, providing O(1) lookup during image conversion.

Dictionary Materialization and Bootstrap Generation

Once the two-stage algorithm selects the optimal chunk set, Algorithm::fill_chunkdict (in deduplicate.rs) gathers all chunks belonging to the selected blobs. The system then generates a bootstrap (metadata file) that references these blobs, creating a self-contained chunk dictionary image.

This bootstrap can be loaded independently of the original images via ChunkDict::from_bootstrap_file (defined in chunk_dict.rs around lines 151‑154), allowing subsequent nydusify convert operations to reference the dictionary without reprocessing source images.

Practical Usage and CLI Commands

The nydusify CLI provides first-class support for generating and consuming chunk dictionaries.

Generating a Chunk Dictionary

To build a chunk dictionary from multiple image versions or related images, use the chunkdict generate subcommand:

nydusify chunkdict generate \
    --sources registry.com/redis:nydus_7.0.1,registry.com/redis:nydus_7.0.2,registry.com/redis:nydus_7.0.3 \
    --target registry.com/redis:nydus_chunkdict \
    --source-insecure --target-insecure \
    --backend-type oss \
    --backend-config-file /path/to/backend-config.json

This command internally invokes nydus-image chunkdict generate, stores each source’s chunk metadata in a SQLite database, executes the DBSCAN and exponential smoothing algorithms, and emits a chunk dictionary bootstrap along with the selected blob list.

Converting Images with Deduplication

When converting a new OCI image to Nydus format, reference an existing chunk dictionary to enable deduplication:

nydusify convert \
    --source registry.com/redis:OCI_7.0.4 \
    --target registry.com/redis:nydus_7.0.4 \
    --chunk-dict registry.com/redis:nydus_chunkdict

During conversion, the builder consults the supplied ChunkDict and reuses any chunk that already exists in the dictionary, significantly reducing the number of new chunks uploaded to the registry.

Programmatic Access in Rust

For custom tooling, the Nydus builder crate exposes the deduplication primitives directly:

use nydus_builder::{HashChunkDict, Builder};

let mut dict = HashChunkDict::new(digest::Algorithm::Sha256);
let builder = Builder::new(&mut dict);
// ... feed layers, then `builder.build()` will deduplicate automatically.

The HashChunkDict can be pre-populated from a previously saved chunk dictionary bootstrap using ChunkDict::from_bootstrap_file in builder/src/core/chunk_dict.rs, enabling incremental deduplication across multiple build sessions.

Key Source Files and Implementation Details

Component	File	Key Elements
Deduplication workflow (CLI)	src/bin/nydus-image/deduplicate.rs	Algorithm::chunkdict_generate, DBSCAN distance, exponential smoothing
Distance calculation	src/bin/nydus-image/deduplicate.rs (lines 62‑96)	fn distance
Exponential smoothing	src/bin/nydus-image/deduplicate.rs (lines 95‑60)	fn exponential_smoothing
Chunk dictionary trait & Hash implementation	builder/src/core/chunk_dict.rs	pub trait ChunkDict, pub struct HashChunkDict, from_bootstrap_file
Dictionary materialization	src/bin/nydus-image/deduplicate.rs	Algorithm::fill_chunkdict
Algorithm documentation	docs/chunk-deduplication.md	Full design description, parameters, example commands
CLI entry point for generation	src/bin/nydus-image/main.rs (around line 1450)	Parsing --algorithm flag and invoking Algorithm

Summary

• Nydus chunk deduplication splits container images into ~1 MiB chunks and eliminates redundant copies across images and versions using a chunk dictionary.
• The system employs a two-stage algorithm: DBSCAN clustering identifies groups of images sharing many chunks, while exponential smoothing selects chunks that persist across version histories.
• The ChunkDict trait in builder/src/core/chunk_dict.rs abstracts chunk lookup, with HashChunkDict providing in-memory HashMap storage keyed by cryptographic digests.
• Use nydusify chunkdict generate to build dictionaries from multiple source images, then reference them with --chunk-dict during nydusify convert to automatically reuse existing chunks.

Frequently Asked Questions

How does Nydus determine if two chunks are identical?

Nydus computes a cryptographic digest (SHA‑256, Blake3, or another configured algorithm) for each chunk’s content. When the HashChunkDict implementation in builder/src/core/chunk_dict.rs encounters a digest that already exists in its HashMap, it treats the chunk as a duplicate and references the existing blob rather than storing new data.

What is the difference between cross-image and version-wise deduplication?

Cross-image deduplication (Stage 1) uses DBSCAN clustering to find unrelated images that happen to share many chunks—such as different containers built on the same base image—and extracts common chunks into a shared dictionary. Version-wise deduplication (Stage 2) applies exponential smoothing to a single image’s version history, scoring chunks by how frequently they appear across recent releases and keeping only those with high temporal persistence.

Can I use an existing chunk dictionary when building new images?

Yes. After generating a chunk dictionary with nydusify chunkdict generate, you can pass it to the conversion command using the --chunk-dict flag:

nydusify convert \
    --source registry.com/app:new \
    --target registry.com/app:nydus_new \
    --chunk-dict registry.com/shared:chunkdict

The builder loads the dictionary via ChunkDict::from_bootstrap_file and automatically reuses any chunks whose digests match the new image’s content, significantly reducing upload size and build time.

Where is the deduplication algorithm implemented in the source code?

The core algorithm resides in src/bin/nydus-image/deduplicate.rs. Key functions include:

• Algorithm::distance (lines 62‑96) – computes the Jaccard-like distance between images for DBSCAN.
• Algorithm::exponential_smoothing (lines 95‑60) – scores chunk persistence across versions.
• Algorithm::chunkdict_generate – orchestrates the two-stage pipeline and emits the final dictionary.

The ChunkDict trait and its HashChunkDict implementation are located in builder/src/core/chunk_dict.rs, providing the storage abstraction used by the algorithm.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}