Big Data and Distributed Systems

AA dataset that fits comfortably on one machine can be processed the ordinary way — load it, compute, done. Past a certain scale, that stops being an option: the data doesn't fit in one machine's memory, or one machine's storage, or can't be processed by one machine's CPU in acceptable time. Distributed systems exist to make many machines behave, from the outside, like one much larger one.

Partitioning Data Across Machines

ShardingSharding (or partitioning) splits a dataset across multiple machines, each holding only a subset — the practical answer to "the data doesn't fit on one disk." The immediate design question is how to decide which record goes on which machine, and the naive answer (hash the record's key, take the result modulo the number of machines) has a serious flaw: adding or removing even one machine changes the modulus, which reshuffles almost every record's assigned machine, forcing a massive, disruptive data migration for what should be a small change.

Consistent Hashing

KargerKarger et al.'s consistent hashing solves exactly this problem¹. Both machines and data keys are hashed onto the same conceptual ring (imagine hash values arranged around a circle from 0 to some large maximum, then wrapping back to 0); each key is assigned to whichever machine's hash position is the next one clockwise from the key's own position on that ring.

The payoff: adding or removing one machine only reshuffles the keys that fall between it and its nearest neighbour on the ring — everywhere else on the ring is completely undisturbed. Where the naive modulus approach could remap nearly every key on a single machine-count change, consistent hashing bounds the disruption to roughly 1/n of the keys when the nth machine is added or removed, which is exactly the property that makes scaling a distributed store up or down a routine operation instead of a disruptive migration event.

Workload Balancing

EvenEven with data evenly partitioned, hot spots can still emerge — a single popular key (a viral post, a trending product) receiving disproportionate traffic while its neighbours on the ring sit idle. Real systems handle this with techniques like virtual nodes (each physical machine takes responsibility for several scattered positions on the hash ring rather than just one, smoothing out load imbalances that a single ring position would concentrate) and replication (a popular key's data is copied to multiple machines, spreading read traffic across all of them rather than funnelling it through one).

Stream Processing versus Batch Processing

BatchBatch processing collects data over a period, then processes the whole accumulated batch at once — simpler to reason about, and efficient for large-scale, non-urgent computation (a nightly report, a full data-warehouse rebuild). Dean and Ghemawat's MapReduce is the paper that made large-scale batch processing practical for ordinary programmers: it splits a computation into a map step (transform each record independently, in parallel, across the cluster) and a reduce step (combine the mapped results grouped by key), and the runtime handles partitioning the data, scheduling the work, and recovering from machine failures automatically — a programmer writes the map and reduce functions and gets cluster-scale parallelism without writing any of the distributed-systems plumbing directly². Stream processing processes each record as it arrives, continuously, with no waiting for a batch to accumulate — the natural fit when a result is needed with low latency (fraud detection has to flag a suspicious transaction before it completes, not the next morning). The trade-off mirrors round-robin scheduling's throughput-versus-responsiveness trade-off covered on Operating Systems Fundamentals: batch processing is generally more efficient in aggregate (larger chunks amortise per-operation overhead better), while stream processing sacrifices some of that efficiency for immediacy.

Recommendation Systems as a Worked Example

RecommendationRecommendation at scale is a concrete big-data application worth walking through, because it needs several of the ideas above together. Item-based collaborative filtering recommends items similar to ones a user already liked, where "similar" is computed from other users' behaviour patterns (items frequently bought or rated together across the whole user base). User-based collaborative filtering instead finds other users with similar taste to the current one, and recommends what those similar users liked. Both require computing similarity across huge numbers of items or users — a computation that has to be partitioned across many machines (sharding), often precomputed in large offline batches (batch processing) rather than recalculated live for every single request, precisely because doing it live, for every user, on every visit, doesn't scale.

References