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

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. ```hint 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 Not every piece is the same size Consider what happens if one piece of your split is still larger than memory. ``` ### 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? ### What a Strong Answer Covers - Why a single in-memory hash set cannot work, with the size arithmetic - An external-memory method (hash partitioning or external merge sort) and why it is exact - The number of passes, the total disk reads and writes, and the temporary disk space - Handling skew: a partition that is still too large for memory - Practical limits such as the number of open files and buffer sizes within 128 MB - How to keep the original order if required ### 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?