Design a System for Sorting Large Data Sets — System Design Interview Practice

Interview prompt

Design a distributed service that sorts datasets larger than one machine's memory and makes the sorted result available reliably to downstream consumers.

• Choose an external-sort pipeline with bounded partitions and spill files.
• Explain partitioning, shuffle, skew handling, retries, and output commit semantics.
• Separate durable input and output objects from ephemeral worker state.
• Define validation, cleanup, observability, and cost controls.

Requirements and scale assumptions

• Accept a dataset and sort key or comparator.
• Split, sort, shuffle, merge, and publish a sorted result.
• Support CSV, JSONL, and binary records with schema validation.
• Expose job status, progress, cancellation, retry, and result download APIs.
• Never require the complete dataset in one worker's memory.
• Make task retries safe and publish outputs atomically only after validation.
• Scale workers with input size while bounding shuffle amplification and hot partitions.
• Preserve tenant isolation, encryption, retention, and auditability.
• Datasets range from 100 GB to 100 TB.
• Input arrives in object storage and records have a stable sortable key.
• A job may use thousands of workers and produce many output shards.
• Most jobs are batch workloads with a completion SLO rather than interactive latency.

• Input throughput: >=2 GB/s — Aggregate scan throughput across workers for large jobs.
• Shuffle amplification: <2x — Track bytes written and read during partition exchange.
• Job completion: p95 <30 min — Target for a representative 10 TB sort with provisioned capacity.
• Failed task retry rate: <1% — Detect bad partitions, transient storage errors, and skew.

Key entities

• SortJobjobId, tenantId, inputManifest, keySchema, partitionCount, status

  Versioned sort request and input manifest.

• SortedRunrunId, jobId, partition, uri, recordCount, minKey, maxKey, checksum

  Immutable sorted run produced by a worker.

• ShufflePartitionjobId, partition, runUris, minKey, maxKey, status

  Reducer input manifest for a key range.

• OutputManifestjobId, partUris, recordCount, checksum, sortOrder, publishedAt

  Atomic downstream-readable sorted output.

Data flow

1. 1. Plan the external sortThe coordinator validates the input manifest, chooses memory/run size and partition count, and creates a versioned sort plan.
2. 2. Create sorted runsWorkers stream input chunks within memory limits, sort them locally, spill immutable runs to object storage, and report checksums.
3. 3. Shuffle by key rangeThe planner assigns run ranges to reducers; workers read only relevant run segments and build bounded merge inputs.
4. 4. Merge and publishReducers perform k-way merges, write ordered parts, validate counts/checksums, and publish one output manifest atomically.
5. 5. Clean up and recoverFailed stages resume from immutable runs, while a reconciler deletes only temporary objects owned by the job after retention checks.

Deep dives and trade-offs

• Spill/run sizing and object-store layoutFor the external sort service, the output manifest is visible only when all parts are complete, ordered, and validated. Design for the failure case where worker loss, skew, duplicate input, and cleanup races must not corrupt or delete a downstream result; keep retries, versions, and repair state explicit. Expose freshness, version, lineage, or audit metadata so operators and clients can distinguish current, pending, and degraded state.
• Range partitioning and skewFor the external sort service, the output manifest is visible only when all parts are complete, ordered, and validated. Keep this concern off unrelated request paths and partition it by the external sort service access key. Expose freshness, version, lineage, or audit metadata so operators and clients can distinguish current, pending, and degraded state.
• Atomic output and cleanupFor the external sort service, the output manifest is visible only when all parts are complete, ordered, and validated. Keep this concern off unrelated request paths and partition it by the external sort service access key. Expose freshness, version, lineage, or audit metadata so operators and clients can distinguish current, pending, and degraded state.
• More memory versus more spillsTune run size to worker memory and object-store costs, then measure spill and merge amplification. Oversized runs cause OOM; tiny runs create excessive metadata and merge fan-in.
• Range partitioning versus hash partitioningUse range partitioning for globally ordered output and detect skewed key ranges for adaptive splits. Hashing balances load but requires another global ordering phase.
• Eager cleanup versus recovery windowKeep immutable intermediate runs through validation and a bounded recovery window, then garbage-collect by manifest ownership. Eager deletion turns a failed reducer into a full rerun.