#10 External Sorting/MapReduce
Large-Scale Data Sorting
Sort a file far larger than any one machine's memory, first on a single machine and then across a cluster.
What is being asked
Sort a terabyte, or a petabyte, of records. The interviewer wants external merge sort on one machine, then how the same idea is distributed, as in MapReduce.
Requirements
Functional
- Input: files of records with a sort key. Output: files that, read in order, are globally sorted.
Non-functional
- Data does not fit in memory, and for the large case not on one disk either.
- Finish in reasonable time using many machines.
- Survive the failure of a worker without starting again.
Design
On one machine (external merge sort)
- Read as much as fits in memory, sort it, write it out as a sorted run. Repeat until the input is consumed.
- Merge the runs with a min-heap holding the next record of each run, writing the smallest each time. With many runs, merge in several passes.
On a cluster
- Sample the keys to choose split points that divide the data into equal ranges, one per reducer.
- Mappers read input blocks and send each record to the reducer owning its key range.
- Each reducer sorts its range, using external merge sort if needed. Because the ranges are ordered, the concatenated outputs are globally sorted.
Key decisions and trade-offs
- Split points decide everything. Badly chosen ranges give one reducer most of the data. Sampling the input first avoids this skew.
- Sequential I/O. Both phases read and write whole runs in order, which is what disks and networks do fastest.
- Fault tolerance comes from re-running only the failed task, since tasks are deterministic and inputs are kept.
- Memory versus passes. A larger buffer means fewer, longer runs and fewer merge passes.
Follow-up questions
- How many merge passes for 1 TB with 8 GB of memory?
- What if 30% of the records share one key?
- How would you sort when records are 1 MB each but keys are small?
- How does a framework like Spark differ from this picture?