How Would You Sort 1 Terabyte of Data? My Uber System Design Interview(last year pre-breakup)

And why the answer is basically a 2004 Google paper in disguise.

I got asked this in a system design round at Uber. At first it sounds like a trick question — you can’t just call .sort() on a terabyte. But once you break it down, the solution is elegant, and it has roots in one of the most influential papers in distributed systems: Dean and Ghemawat's MapReduce (OSDI 2004).

Here’s how I’d approach it.

The Core Constraint

You have ~1 TB of data. You have maybe 8–64 GB of RAM per machine. You need a globally sorted output.

The moment you accept you can’t hold it all in memory, the rest of the design follows naturally.

Step 1: Figure Out the Split Points (Sampling)

Before you send data anywhere, you need to know how to divide it fairly across machines. The right tool here is range partitioning — not hashing.

Hashing is great for grouping, terrible for sorting. Hash-based partitions have no ordering relationship to each other, so you can never reconstruct a global order without a second full pass.

Range partitioning works like this:

• Sample a small subset of the data (say, 0.1%)
• Sort the sample
• Pick splitter values that divide the data into roughly equal buckets

[0 ──── 100 ──── 200 ──── 300 ──── 400]
  Machine 1  Machine 2  Machine 3  Machine 4

Each machine now owns a range, and crucially, concatenating machine outputs in order gives you the globally sorted file.

Step 2: External Sort on Each Machine

Each machine receives its partition but still can’t fit it all in RAM. This is where external sort comes in.

Phase 1 — Create sorted runs: Read data in memory-sized chunks (e.g., 1 GB), sort each chunk in memory, write it back to disk as a “sorted run.”

Phase 2 — K-way merge: Open all sorted runs simultaneously, use a min-heap to merge them efficiently.

- Push the first element from each run into the heap
- Pop the minimum → write to output
- Insert the next element from that same run
- Repeat

Time complexity: O(N log K) where K is the number of runs. This is the workhorse of the whole system.

Step 3: The MapReduce Connection

This is where it gets interesting. The architecture above maps almost exactly onto what Dean and Ghemawat described in their 2004 paper.

📌 Figure 1 from the MapReduce paper — The execution overview below shows the full pipeline: the master forks workers, assigns map and reduce tasks, workers read input splits, write intermediate files locally, reduce workers do a remote read (shuffle), and finally write output files. This is the same shape as our sort.

MapReduce Working Procedure

📌 Solution diagram — The second diagram shows how the 1TB sort maps onto this: sample → broadcast splitters → each machine runs external sort on its range → partitions are concatenated in order.

Solution Architecture for the Sorting

The paper defines distributed sort as a clean MapReduce problem: the map function extracts the sort key from each record and emits a (key, record) pair. The reduce function emits all pairs unchanged — the ordering comes from the partitioning and shuffle, not the reduce logic itself.

The paper explicitly notes that this computation “depends on the partitioning facilities” and the ordering guarantees of the shuffle phase. That’s exactly the range partitioning we described above. In Google’s implementation (and later in Hadoop’s TotalOrderPartitioner), a sample of the data is used to determine split points, which are broadcast to all mappers before the shuffle begins.

The shuffle phase — where each mapper sends its output to the correct reducer based on the key range — is the distributed analog of our “send data to the right machine” step.

So the full flow in MapReduce terms:

Map:    (record) → emit(key, record)        [with range-based partitioning]
Shuffle: route to correct reducer by key range
Reduce: emit(key, record) unchanged         [already sorted within partition]

The paper’s insight was to hide all the complexity of partitioning, fault tolerance, and inter-machine communication behind this simple two-function interface. The sorting problem is a perfect stress test of those facilities.

Step 4: Stitch It Together

Since each machine sorted its own range, the final output is just:

Machine 1 output → Machine 2 output → Machine 3 output → ...

No final merge step required. That’s the payoff of range partitioning up front.

The Details That Actually Matter in an Interview

This is where most candidates fall short. Getting the algorithm right is table stakes — the real signal is whether you can reason about what breaks it in production.

Buffering — Disk I/O is the true bottleneck, not CPU. You want large sequential reads and writes, not random access. Practically this means reading and writing in blocks of 4–64 MB at a time, keeping the disk head moving in one direction. Random seeks at 1 TB scale will destroy your throughput.

Compression during shuffle — The shuffle phase moves data across the network, which is expensive. Compressing intermediate files with Snappy or LZ4 before sending them to reduce workers cuts bandwidth significantly with minimal CPU overhead. The MapReduce paper explicitly calls this out as one of its key optimizations.

Spill-to-disk strategy — During the external sort, if you open too many sorted runs at once during the k-way merge, you’ll hit OS file descriptor limits and thrash on seeks. Fix this with a multi-level merge: merge groups of runs into larger intermediate runs first, then merge those. Think of it as a merge tree rather than a flat fan-in. You bound the number of simultaneously open files at each level.

Skew handling — If your sample is unlucky, one machine gets 3x more data than the others and becomes the straggler everyone waits on. Fix: oversample aggressively (1% instead of 0.1%), use more split points than you have machines, and dynamically reassign ranges at runtime based on actual load. The coordinator tracks partition sizes and can rebalance.

Fault tolerance — Map workers write intermediate results to local disk before the shuffle, not to a remote store. This means if a reduce worker fails, the map workers simply re-send their data — no recomputation from scratch. The coordinator tracks task state and reassigns failed tasks to idle workers, which is exactly the re-execution model the MapReduce paper describes as its primary fault tolerance mechanism.

Parallelism — Each machine should be doing multiple things at once: sorting one chunk in memory while writing the previous sorted run to disk, and simultaneously receiving shuffle data from other nodes. This means multi-threaded sort within each worker and async disk and network I/O so neither sits idle waiting for the other.

What to Say in the Interview

“I’d implement a Total Order Sort using sampling-based range partitioning to determine split points, distribute data to machines based on those ranges, and run external merge sort locally on each machine. The concatenated output is globally sorted with no final merge step. This is essentially the MapReduce distributed sort described by Dean and Ghemawat — the shuffle phase does the heavy lifting once partitioning is correct.”

That one paragraph shows you understand data locality, distributed coordination, algorithmic complexity, and that you’ve actually read the literature.

Real Systems That Do This

• Hadoop — TotalOrderPartitioner implements exactly the sampling approach described above
• Apache Spark — repartitionAndSortWithinPartitions / sortByKey with range partitioning
• BigQuery / Snowflake — similar ideas under the hood, optimized for columnar storage

The 1 TB sort problem is really a question about whether you understand the constraints that make distributed systems hard: memory limits, network costs, skew, and fault tolerance. The algorithm itself has been known since 2004. The interview is testing whether you can reason about why it works.

If you found this useful, the original MapReduce paper is worth reading in full — it’s remarkably accessible for something this foundational.(paper link:-https://static.googleusercontent.com/media/research.google.com/en//archive/mapreduce-osdi04.pdf)