#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.