Duplicate File Detector

A duplicate file detector identifies identical files across a directory tree. Rather than hashing every byte of every file on disk upfront (which wastes gigabytes of disk I/O on files that have unique sizes), a high-performance detector uses a three-stage progressive filtering pipeline:

1. Stage 1 — Group by File Size (Metadata::len): Any file whose byte length is unique in the directory tree cannot possibly have a duplicate—eliminating 80%–95% of files with zero file reads!
2. Stage 2 — Group by Partial Header Hash (First 4 KiB): For files sharing the exact same size, hash only the first 4,096 bytes. Files that differ in their header are eliminated without reading their remaining megabytes.
3. Stage 3 — Full Content Hash: Compute the full content hash only for files that matched in both exact byte size and first-4-KiB hash!

Three-Stage Progressive Deduplication Pipeline:

  All Files in Directory Tree (e.g., 10,000 files)
        |
        v  Stage 1: Group by `file_size: u64` (`stat` metadata only, 0 file bytes read!)
  Keep Only Groups with `len >= 2` (e.g., 800 candidate files)
        |
        v  Stage 2: Group by `(file_size, hash_first_4k)` (Reads at most 4 KiB per candidate)
  Keep Only Groups with `len >= 2` (e.g., 50 candidate files)
        |
        v  Stage 3: Group by Full Content Hash (`hash_full_stream`)
  Confirmed Duplicate Groups (`Vec<Vec<PathBuf>>`)!

Complete Runnable Implementation

use std::collections::HashMap;
use std::env;
use std::fs::{self, File};
use std::io::{self, Read};
use std::path::{Path, PathBuf};

const FNV_OFFSET_BASIS: u64 = 0xcbf2_9ce4_8422_2325;
const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
const HEADER_SAMPLE_BYTES: usize = 4096;

/// Computes a 64-bit FNV-1a hash over a `Read` stream in 8 KiB chunks.
pub fn hash_reader<R: Read>(mut reader: R) -> io::Result<u64> {
    let mut hash = FNV_OFFSET_BASIS;
    let mut buf = [0u8; 8192];
    loop {
        let n = reader.read(&mut buf)?;
        if n == 0 {
            break;
        }
        for &b in &buf[..n] {
            hash ^= u64::from(b);
            hash = hash.wrapping_mul(FNV_PRIME);
        }
    }
    Ok(hash)
}

pub fn hash_file_prefix(path: &Path, max_bytes: usize) -> io::Result<u64> {
    let file = File::open(path)?;
    hash_reader(file.take(max_bytes as u64))
}

pub fn hash_full_file(path: &Path) -> io::Result<u64> {
    let file = File::open(path)?;
    hash_reader(file)
}

/// Finds all duplicate non-empty files in `root` using the 3-stage progressive filter.
pub fn find_duplicate_groups(root: impl AsRef<Path>) -> io::Result<Vec<Vec<PathBuf>>> {
    // Stage 1: Group files by exact byte size (skipping 0-byte empty files)
    let mut by_size: HashMap<u64, Vec<PathBuf>> = HashMap::new();
    let mut stack = vec![root.as_ref().to_path_buf()];

    while let Some(dir) = stack.pop() {
        for entry_res in fs::read_dir(&dir)? {
            let entry = entry_res?;
            let ftype = entry.file_type()?;
            if ftype.is_symlink() {
                continue;
            }
            let path = entry.path();
            if ftype.is_dir() {
                stack.push(path);
            } else if ftype.is_file() {
                let len = entry.metadata()?.len();
                if len > 0 {
                    by_size.entry(len).or_default().push(path);
                }
            }
        }
    }

    // Stage 2: For size collisions (`paths.len() >= 2`), group by 4 KiB header hash
    let mut by_prefix: HashMap<(u64, u64), Vec<PathBuf>> = HashMap::new();
    for (size, paths) in by_size {
        if paths.len() < 2 {
            continue; // Unique file size -> impossible to be a duplicate!
        }
        for path in paths {
            if let Ok(prefix_hash) = hash_file_prefix(&path, HEADER_SAMPLE_BYTES) {
                by_prefix.entry((size, prefix_hash)).or_default().push(path);
            }
        }
    }

    // Stage 3: For header collisions (`paths.len() >= 2`), group by full-file hash
    let mut by_full_hash: HashMap<(u64, u64), Vec<PathBuf>> = HashMap::new();
    for ((size, _), paths) in by_prefix {
        if paths.len() < 2 {
            continue;
        }
        for path in paths {
            if let Ok(full_hash) = hash_full_file(&path) {
                by_full_hash.entry((size, full_hash)).or_default().push(path);
            }
        }
    }

    let mut duplicates: Vec<Vec<PathBuf>> = by_full_hash
        .into_values()
        .filter(|group| group.len() >= 2)
        .map(|mut group| {
            group.sort_unstable();
            group
        })
        .collect();

    duplicates.sort_unstable_by(|a, b| a[0].cmp(&b[0]));
    Ok(duplicates)
}

fn main() -> io::Result<()> {
    let dir = env::temp_dir().join("rust_ch67_dedup_demo");
    let _ = fs::remove_dir_all(&dir);
    fs::create_dir_all(dir.join("backup"))?;

    // Two identical files (`a.txt` and `backup/a_copy.txt`)
    fs::write(dir.join("a.txt"), "identical payload bytes 12345")?;
    fs::write(dir.join("backup/a_copy.txt"), "identical payload bytes 12345")?;

    // Same exact byte length (29 bytes), but different content (`b.txt`)
    fs::write(dir.join("b.txt"), "different payload bytes 99999")?;

    // Unique byte length (`unique.txt`) -> filtered out at Stage 1 without reading!
    fs::write(dir.join("unique.txt"), "short")?;

    let groups = find_duplicate_groups(&dir)?;
    assert_eq!(groups.len(), 1);
    assert_eq!(groups[0].len(), 2);

    println!("Found {} duplicate group(s):", groups.len());
    for group in &groups {
        let names: Vec<_> = group
            .iter()
            .map(|p| p.strip_prefix(&dir).unwrap().display().to_string())
            .collect();
        println!("  Duplicates: {names:?}");
    }

    fs::remove_dir_all(&dir)?;
    Ok(())
}

Found 1 duplicate group(s):
  Duplicates: ["a.txt", "backup/a_copy.txt"]