RETURN TO SYSTEM DESIGN VAULT (55)BLUEPRINT #21 // Easy
#21EasySearch, Autocomplete & Big Data
Design a System for Sorting Large Data Sets
ASKED IN INTERVIEWS AT:GoogleMicrosoft
EXECUTIVE SUMMARY & PROBLEM STATEMENT
Design an external sorting system capable of ordering 100 Terabytes of data on machines with only 16 GB of RAM using multi-way external merge sort.
SCALE ESTIMATION & TRAFFIC ENVELOPE
DAILY ACTIVE USERS / TPS100 TB input data on 16 GB RAM nodes
READ / WRITE TRAFFIC RATIO2-pass disk read and write
5-YEAR STORAGE CAPACITY100 TB input + 100 TB intermediate chunks + 100 TB sorted output
FUNCTIONAL REQUIREMENTS
- [1]Sort arbitrary terabyte-scale records by key
- [2]Handle data far exceeding total physical RAM
NON-FUNCTIONAL REQUIREMENTS
- •Maximize sequential disk read/write bandwidth
- •Fault-tolerant worker checkpoints
CORE ARCHITECTURAL COMPONENTS
Chunk Splitter & In-Memory Quicksorter
Sorted Runs Intermediate Store
K-Way Merge Engine (Min-Heap in RAM)
Master Task Coordinator
DATA SCHEMA & PERSISTENCE
Binary records: Key (10 bytes), Value (90 bytes)
DISTRIBUTED TRADE-OFFS & FAILURE MODES
- ⟡Using larger in-memory chunks reduces the number of merge runs and I/O passes.