Katkat
Back

Design Duplicate File Detection

OpenAIMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteSystem Design

Last updated

This question tests the ability to design a scalable content-based deduplication system using cryptographic hashing and distributed storage principles to manage large-scale file ingestion.

Problem Statement

Design a system capable of detecting duplicate files within a massive cloud storage service (e.g., billions of files totaling petabytes). The goal is to identify files that are bit-for-bit identical, even if they have different filenames or storage paths. The system must support high-throughput ingestion and periodic batch scanning.

Functional Requirements

  1. Identify all exact-match duplicates across the distributed storage system.
  2. Provide an API to check if a specific file exists before a new upload (preventing future duplicates).
  3. Scale to handle millions of new files uploaded daily.

Non-Functional Requirements

  1. Low latency for the "check existence" API.
  2. High availability of the duplicate index.
  3. Robustness against collisions.

Constraints

  • The files can range in size from a few kilobytes to hundreds of gigabytes.
  • The system should minimize network I/O; avoid downloading entire files for comparison if possible.

Deliverables

  • Describe the high-level architecture and the flow of data during file ingestion.
  • Define the database schema for the metadata index.
  • Explain the strategy for handling files of different sizes efficiently.
  • Discuss how you would handle hash collisions if they occur.

Hints

Hint 1

Consider using cryptographic hash functions (like SHA-256) to create a unique content fingerprint.

Hint 2

For very large files, compute the hash in chunks or use a multi-tiered approach (e.g., file size check -> partial hash check -> full hash check).

Hint 3

Think about using a distributed Key-Value store or a columnar database to store the mapping between file hashes and their storage locations.

Follow-up questions

  • How would you modify your design if the requirement changed to detect 'near-duplicates' (e.g., images with slight color shifts or documents with small text edits)?
  • What steps would you take to clean up storage if a user deletes a file that was part of a duplicate group?
  • How would you handle the re-processing of historical data if the hashing algorithm needs to be updated to a more secure version?