Katkat
Back

Deduplicate a 256 GB File on a Machine With 128 MB of Memory

WaymoSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Remove duplicate records from a single 256 GB file on a machine with only 128 MB of memory. Tests external-memory techniques such as hash partitioning and external merge sort, skew handling, I/O cost, open-file limits, and preserving the original order.

You have one file of 256 GB containing a large number of records, some of which are duplicates. The machine you run on has only 128 MB of memory. How do you remove the duplicates so that the output contains each distinct record exactly once?

Explain the approach, its cost in passes over the data and disk space, and sketch the code.

Clarifying Questions

  • What is a record: a line of text, a fixed-size binary record, or something else? How large is a typical record, and what is the largest?
  • Are duplicates byte-for-byte identical records, or records with the same key?
  • Must the output preserve the original order (keeping the first occurrence of each record), or is any order acceptable?
  • How much free disk space is available for temporary files? Can the output overwrite the input?
  • Is an exact result required, or is a tiny probability of dropping a distinct record acceptable?
  • Is this a single machine, or could the work be spread across several?

Hints

Hint 1

Divide until it fits: The file is 2048 times larger than memory. Think about how to split it so that every copy of a given record is guaranteed to land in the same piece.

Hint 2

Not every piece is the same size: Consider what happens if one piece of your split is still larger than memory.

Follow-up questions

  • The output must keep the first occurrence of each record in original file order. What changes, and what does it cost?
  • Would a Bloom filter solve this within 128 MB? What exactly would go wrong?
  • You now have 100 machines, each with the same memory. How do you distribute the work?
  • Instead of whole records, duplicates are defined by a key field, and you must keep the record with the latest timestamp. How does the method change?