Find Duplicate Files Safely at Scale

Task

Implement a duplicate file detector that scans a given root directory and groups files that have identical byte content. Your solution must be safe against filesystem cycles (e.g., circular symlinks), avoid loading entire files into memory, and minimize unnecessary disk reads when processing large volumes of data.

Requirements

1. Cycle & Link Safety: Safely handle symbolic links and hard links. Do not enter infinite loops due to directory symlink cycles. If two distinct paths point to the exact same underlying file (same (device, inode)), consider whether they should be reported as duplicates or treated as identical references.
2. Multi-Stage Filtering: Reading full file contents is expensive. Optimize duplicate detection using progressive checks:
   • Group files by size first (files with unique sizes cannot be duplicates).
   • For files with matching sizes, compute a partial hash (e.g., first 4 KB).
   • For files with matching partial hashes, compute a full content hash using chunked streaming.
   • Perform a byte-by-byte verification if cryptographic hash collisions must be strictly ruled out.
3. Bounded Memory: Large files (e.g., multi-gigabyte video or archive files) must be read in configurable chunk buffers rather than read entirely into RAM.

Interface

from typing import List, Set
import os

class DuplicateFileFinder:
    def __init__(self, chunk_size: int = 64 * 1024):
        """
        chunk_size: number of bytes to read per buffer chunk.
        """
        self.chunk_size = chunk_size

    def find_duplicates(self, root_dir: str) -> List[List[str]]:
        """
        Scans `root_dir` recursively and returns a list of duplicate groups.
        Each group contains two or more file paths with identical content.
        """
        pass

Example

Given directory structure:

/data/
  ├── a.txt (10 bytes, content: "helloworld")
  ├── b.txt (10 bytes, content: "helloworld")
  ├── c.txt (10 bytes, content: "foobar1234")
  ├── sub/
  │   ├── d.txt (10 bytes, content: "helloworld")
  │   └── symlink_to_root -> /data

Output:

[
    ["/data/a.txt", "/data/b.txt", "/data/sub/d.txt"]
]

Explanation: c.txt has the same size but different content. The symlink symlink_to_root points back to /data and is safely skipped without an infinite recursion.

Constraints & Edge Cases

• Empty files (0 bytes) should either be grouped together or ignored based on a configurable flag.
• Unreadable files (e.g., permission denied) should be skipped gracefully without aborting the traversal.
• File sizes can reach several gigabytes; directory trees can contain millions of files.