Distributed
Storage Systems

In Chapter 1, "store" was one arrow in a seven-stage pipeline — a black box a record disappears into. This section opens that box. A distributed file system takes one logical file and spreads it, in pieces, across many machines, so that no single disk failure can take the file with it. The design nearly every modern system either runs or imitates is Hadoop's HDFS, itself modelled on Google's GFS — and its two central ideas are worth learning by name, because you will meet variants of both again in Chapter 3.

Two kinds of node, two very different jobs

An HDFS cluster has exactly one active NameNode and many DataNodes. The split is strict, and mixing the two up is the single most common misconception about how this works:

Every DataNode sends the NameNode a periodic heartbeat ("I'm alive") and a block report ("here is exactly what I'm holding"). Stop hearing heartbeats from a node, and the NameNode has to assume it's gone — which is exactly the scenario this section's worked example walks through.

Splitting a file into blocks

A file is cut into fixed-size blocks the moment it's written — not by content, not by row, just by raw byte position. Real HDFS defaults to a 128 MB block size, chosen for machines storing terabytes; every full block after the first is exactly that size, and only the last block is shorter. Each block is then replicated some number of times (the replication factor) and each copy is placed on a different DataNode, so losing one machine never means losing a block outright.

Worked Example · Blocking and Placing the Order Log

CityCourier's 16-row order log, written out one row per order, is 518 bytes total — about 32 bytes a row. That's roughly 0.0004% of one real HDFS block, which is exactly why we can lay out every byte on the page and still see the real mechanics.

Watch It Happen

Practice

1. If CityCourier's log grew to 40 orders and kept the same 3-block, round-robin, replication-factor-2 layout, how many total block-copies would exist on disk, and how many would each server hold?
   Solution

   3 blocks × 2 copies = 6 block-copies total, regardless of how many orders the blocks contain — the block count doesn't change just because the blocks got bigger (until a block exceeds the size limit and a 4th block is created). Each of the 3 servers holds exactly 2 of the 3 blocks, same as with 16 orders.

2. Suppose the round-robin placement had instead put replication factor 1 everywhere — Block 1 only on N, Block 2 only on S, Block 3 only on E — to save space. Redo the Hub S failure. What's lost?
   Solution

   Block 2 is gone completely — orders #7–11, with no surviving copy anywhere. Blocks 1 and 3 are untouched since they never lived on Hub S. This is exactly the gap replication factor 2 closed in the worked example: at RF=1, a node failure doesn't just risk data, it guarantees loss of whatever that node uniquely held.

3. After the NameNode's re-replication, Hub N and Hub E each hold all 3 blocks, and Hub S (once it comes back online) holds none of the fresh copies. Is this a problem, and if so, whose job is it to fix?
   Solution

   It's an imbalance, not a data-loss risk — every block is still safely at 2 copies. But it does mean N and E are now doing more than their share of the read load, and a returning Hub S is sitting idle. Real HDFS runs a background balancer process for exactly this: it doesn't fix urgent under-replication (the NameNode's re-replication already did that), it fixes long-run unevenness afterward.

4. Chapter 1's cost trade-off (Section 1.6) argued that moving computation to data beats moving data to computation when data is large. Does replication factor 2 make that argument stronger or weaker, and why?
   Solution

   Stronger. With RF=2, a computation that needs this file now has two machines it could run on locally instead of one — more chances to find a copy near the requesting client, and more chances to avoid shipping the data anywhere at all. Replication isn't only a durability feature; it's also what makes "run the job where the data already is" a realistic scheduling option rather than a lucky coincidence.

A relational table forces every row into the same fixed columns. NoSQL is the umbrella term for stores that don't — not one alternative design, but four genuinely different ones, each optimised for a different access pattern. Knowing the name of each model matters less than knowing which questions it answers cheaply.

The same order, modelled four ways

Worked Example · What Fits in a Byte

The same fact costs a different number of bytes depending which shape holds it — not because any model is "wasteful," but because each is paying for a different kind of flexibility.

The document format costs nearly 4× the key–value blob for the identical fact — that overhead buys self-describing structure (any tool can read a JSON document without a separate schema) and the ability to query by field name instead of parsing a blob. Whether that's a good trade depends entirely on what you're about to do with the data next.

The Graph View

Order #4's graph neighbourhood looks like this once the other orders that share its restaurant are added for context:

Orders #11 and #15 also ordered from Sushi Go — in a graph store, "which other orders share a restaurant with order #4" is one hop away: walk from Order #4 to the Sushi Go node, then out to whichever other Order nodes connect there. A relational answer needs a self-join on restaurant; a graph just walks an edge.

Practice

1. Order #10 (the veracity bug from Section 1.1) is stored as a document with fields delivery_time_sec: -60. In a column-family store with the same core/feedback split as above, which family holds delivery_time_sec, and does the veracity bug change how it's stored?
   Solution

   It belongs in the core family alongside hub, restaurant and amount — delivery time isn't feedback. And no, the bug doesn't change the storage shape at all: −60 is a perfectly well-typed integer as far as the column-family store is concerned. Veracity is a meaning problem, not a storage problem, which is exactly why catching it requires application-level validation (Section 1.2's Ingest-stage check), not a database constraint.

2. CityCourier wants to add a "customer allergy notes" field, but only about 2% of orders will ever have one. Which of the four models handles this addition most cheaply, and which would need the most rework?
   Solution

   Document and column-family both handle it cheaply — a document simply omits the field on the other 98%, and a column-family store treats it as another sparse family, exactly like the missing-rating case above. Key–value handles it only if the blob format itself has room to grow, which usually means quietly agreeing on a new blob layout across every piece of code that reads it. A rigid relational table would need an actual schema migration (add a nullable column) across the whole table.

3. A query asks: "total revenue across all orders." Rank the four models from cheapest to most expensive for this specific question, and justify the graph model's position.
   Solution

   Column-family and document are both cheap here — scan the amount field/column across all rows and sum, exactly Section 1.3's MapReduce pattern. Key–value is more expensive: the store can't see inside the blob, so every value must be fetched and parsed in application code before summing. Graph is worst: summing a property across every node means visiting every node anyway, gaining none of the traversal advantage graphs exist for, while paying extra overhead per node for relationship bookkeeping the query never uses.

4. Section 1.6 showed that shipping computation to data beats shipping data to computation when data is large. Which of the four models makes that principle easiest to apply for a "sum by hub" query, and why?
   Solution

   Column-family — because hub and amount are both plain columns the store's own engine can filter and aggregate locally, exactly the kind of routine a coordinator can ship to each node and get back only a partial sum (Section 2.6 works this scatter-gather pattern in full). A key–value store can't run that logic itself at all — the "computation" would have to ship out as a separate program that fetches, deserializes, and sums every blob by hand.

One clarification before anything else: from here on, "Hub N," "Hub S" and "Hub E" mean the server sitting at that hub's location — not the business hub an order was placed at. Those are different questions once you're inside the storage layer, and this section is precisely about how far apart the two answers can drift.

The naive approach, and why it breaks

The obvious scheme is hash(key) mod N: hash the key to a number, take it modulo the number of servers, that's the owner. It works — right up until N changes. Adding or removing even one server changes almost every key's modulo result, because the whole numbering shifts.

Consistent hashing fixes this by hashing servers onto the same numeric space as keys, arranging both on a conceptual ring, and giving each key to whichever server sits next going clockwise. Add or remove a server, and only the keys between the new server's position and its nearest clockwise neighbour move — everyone else's assignment is untouched.

Worked Example · Placing 16 Keys on a Ring

Using a simple illustrative hash — real systems use SHA-1 or Murmur3, but the mechanics are identical — hash(id) = (37×id + 11) mod 100 gives every order id a position from 0–99. Place the three servers at positions N=8, S=42, E=71, and every key belongs to the next server clockwise:

Sorted by hash, the pattern is visible directly: every key with hash ≤ 8 or > 71 belongs to N (wrapping around the top of the ring), hash 9–42 belongs to S, hash 43–71 belongs to E. Tally it up: N holds 6, E holds 6, S holds 4 — close to even, from just three points on a ring.

Adding a Fourth Server

CityCourier adds a fourth server, Zone Z, at ring position 60 — squarely inside what used to be Hub E's territory (43–71). Only the keys between Hub S's position and Zone Z's new position are affected:

Compare that to naive hash mod N: moving from 3 servers to 4 changes the modulo result for 11 of the same 16 keys (68.8%) — nearly three times the disruption, for the identical change in cluster size. This is the entire reason consistent hashing exists: the theoretical guarantee is that roughly k/n keys move when a server joins a system already holding k keys across n servers (16/4 = 4, matching exactly), and real systems soften even that with many small virtual nodes per physical server, so no single join or leave dumps its whole share of the disruption onto one neighbour.

Practice

1. Using the same hash function, order id 17 would hash to (37×17+11) mod 100. Compute it and name the owner, using the original 3-server ring (N=8, S=42, E=71).
   Solution

   37×17+11 = 640; 640 mod 100 = 40. Position 40 falls in the 9–42 range, so Hub S owns it.

2. If Hub S's server (not a new server, but a failing one) is removed from the original 3-server ring instead of a 4th being added, which keys move, and who inherits them?
   Solution

   Every key that belonged to S (ids 11, 3, 14, 6 — the same four rows that were assigned to S in the worked table) now belongs to whichever server is next clockwise from S's old position, which is Hub E at position 71. No other keys are affected — N's and E's own existing keys are untouched. Removal follows the identical rule as addition: only the range between the removed point and its immediate predecessor changes hands.

3. A support ticket claims "Hub E's server going down means Hub E's orders are unreadable." Using the ownership breakdown above (2 of Hub E's 5 own orders on Hub E's server, 3 on Hub N's), is the claim accurate?
   Solution

   No — it conflates business hub with storage owner, the exact confusion this section opened by warning against. Hub E's server going down affects whichever keys hash to Hub E's ring position, which happens to include only 2 of Hub E's own 5 orders (plus whichever other hubs' orders also hash there). The other 3 of Hub E's orders live on Hub N's server and are entirely unaffected.

4. Connect this to Section 2.1: both sections split the same 16-row file across 3 servers, but produce different placements. Why don't blocks and hash-ring ownership agree on which server holds order #4?
   Solution

   They're partitioning at different granularities for different reasons. Section 2.1 blocks the file by raw arrival position for fault-tolerant file storage — it has no notion of "order #4" at all, only byte ranges. This section partitions by an actual application key (the order id) for fast key-based lookup. Nothing requires the two schemes to place the same row on the same server, and in a real system built with both an HDFS-style layer underneath and a key-value layer on top, they generally won't.

Section 1.6 framed CAP as a single switch: choose Consistency or Availability during a partition. Real systems usually expose something more precise — two dials, called W (write quorum) and R (read quorum), against a fixed replication factor N. A write isn't acknowledged until W replicas confirm it; a read isn't returned until R replicas have responded and their values compared.

That guarantee isn't a rule someone imposed — it's the pigeonhole principle. If a write touched W of N replicas and a later read checks R of the same N, and W+R exceeds N, there is no way to choose R replicas that avoid all W written ones — there simply aren't enough replicas left over to dodge them all.

Worked Example · Does the Correction Get Seen?

Order #4's rating write goes out to all three replicas, but only two — Hub N and Hub E — acknowledge before a client's write-quorum requirement is met; Hub S is momentarily slow and still holds the old value.

Practice

1. For N=5, list every (W,R) pair from the set {1,2,3,4,5} where W+R>N, and identify the pair that guarantees overlap while minimising the larger of W and R.
   Solution

   Pairs with W+R>5 include (1,5),(2,4),(3,3),(3,4),(4,2),(4,3),(4,4),(5,1), and every combination with either value at 5. The pair minimising the larger value is (3,3): both below N, both equal, and 3+3=6>5 — the most balanced overlap-guaranteeing choice, which is why odd N with W=R=⌈(N+1)/2⌉ is a common real-world default.

2. CityCourier switches order confirmations to W=1 for speed, keeping R=2. Does W+R>N still hold at N=3, and what does that imply about reading your own just-written order back immediately?
   Solution

   1+2=3, which is not greater than N=3 — overlap is no longer guaranteed. A customer who writes an order and immediately reads it back with R=2 might hit the two replicas that haven't received the write yet, and briefly see no order at all, even though their own write "succeeded." This is exactly the read-your-own-write problem quorum tuning has to consider explicitly, not assume away.

3. A read at R=2 returns two different values for the same key from two different replicas. What does the quorum arithmetic alone tell you about which one is correct?
   Solution

   Nothing. W+R>N guarantees you'll see the latest write among the replicas you checked, not that every replica hands back a single agreed value, and it says nothing about how to pick the winner when two exist. That's a separate mechanism — typically a timestamp ("last write wins") or a version vector the application resolves — layered on top of the quorum guarantee, not implied by it.

4. Section 2.1 showed replication factor 2 surviving a single node failure for file blocks. Does the same N=2 replication factor support a W+R>N quorum with any usable W and R, and what does that reveal about the minimum replication factor a quorum-based design needs?
   Solution

   At N=2, W+R>2 needs W=R=2 (the only pair that works, since 1+1=2 fails and anything above 2 exceeds the replica count). But W=2 at N=2 means every replica must be reachable for every write — a single node failure now blocks all writes outright, the opposite of the fault tolerance Section 2.1 wanted. This is why quorum-based stores typically run N≥3: it's the smallest replication factor that offers a W+R>N choice (like 2-and-2) that still tolerates one replica being briefly unreachable.

Both structures below solve the same problem — keep a set of keys (here, order amounts) findable on disk — and both are genuinely in wide production use, because they make opposite bets about which side of the workload to optimise.

Worked Example · Inserting the Same 16 Orders, Two Ways

Insert all 16 orders, in arrival order, keyed by amount, into each structure with a small page/memtable capacity of 4 keys, and see what each looks like once the rush is over.

See Both Structures, Run the Same Query

Practice

1. If the query were "find the order with amount exactly 355" (a point lookup, not a range) instead, how many B-tree pages need checking, and does the LSM-tree's disadvantage shrink or vanish?
   Solution

   The B-tree still needs just 1 page — 355 sits alone in the [330,340,355] leaf. The LSM-tree's situation improves sharply with Bloom filters: a filter per SSTable can rule out the 3 SSTables that don't contain 355 in roughly constant time each, leaving only 1 real read (SSTable 2, which holds it) — the same 1-page answer as the B-tree, for point lookups specifically.

2. Head office's query changes to "amount between 150 and 200" instead of "over 400." Recompute which B-tree pages match.
   Solution

   Values in [150,200]: 180 and 165 and 150 — all three sit in the very first leaf page, [150,165,180,260]. Just 1 of 5 pages, even better than the >400 example, because this range happens to fall entirely inside one leaf's boundaries.

3. After the rush, a compaction merges all 4 SSTables into 1 large sorted file. Redo the "amount>400" query. What's the new cost, and what did compaction actually buy?
   Solution

   One SSTable now holds all 16 keys, sorted. The query touches that single file — but unlike the B-tree's targeted 2-of-5 pages, a naive scan of one large sorted SSTable for a range still means finding the right starting offset within it (which a well-built SSTable supports via an internal index, closing most of the remaining gap with the B-tree). Compaction buys back most of the read advantage the B-tree had, at the cost of the compaction work itself happening in the background.

4. Section 2.1 measured 20 B-tree page writes against 4 LSM flush writes for the same 16 inserts. If CityCourier scaled to 4,608,000 orders in a day (100× the citywide figure), which structure's write cost grows faster, and why does that matter for choosing a storage engine at scale?
   Solution

   The B-tree's page-write count doesn't scale linearly and predictably — every insert can trigger a split, and splits compound as the tree deepens, meaning write cost per insert can actually increase as the dataset grows. The LSM-tree's flush count scales exactly linearly (inserts ÷ memtable capacity, always), and every flush is a cheap sequential write regardless of how large the dataset has grown. At the volumes distributed storage exists for, that predictable, flat-scaling write cost is precisely why write-heavy big-data systems default to LSM-based engines.

A query engine that can't touch data directly has one real move: scatter-gather — send a piece of the question to every node that might hold relevant rows, then combine the partial answers centrally. How much network traffic that costs depends on whether the partitioning scheme happens to line up with what the query is asking for.

Worked Example · Full Aggregate vs Selective Filter

Revenue by hub, recomputed directly from all 16 rows: Hub N ₹2,085, Hub S ₹1,695, Hub E ₹1,765 — total ₹5,545, exactly matching Section 1.1.

The full aggregate touches all three nodes under any partitioning scheme, because it needs every row regardless. The selective query is where the partitioning choice actually shows up in the bill: hub-based partitioning answers "Hub E only" with 1 network round trip; Section 2.3's hash-of-order-id partitioning needs 3 — the coordinator has no way to know in advance that Hub S's server holds none of Hub E's rows, so it has to ask anyway and get an empty answer back. Same final number, ₹1,765, three times the network cost to get it.

Secondary Indexes: Finding the Needle Without Scanning the Haystack

One more query, one more callback: "find any order with a negative delivery time" — Section 1.1's veracity bug, order #10 at −60 seconds.

A secondary index is simply an index built on a column that isn't the primary key or partition key — here, delivery_time rather than order_id. It costs extra storage and extra write work (every insert now updates two structures, not one) to buy exactly this: a query on a non-key column stops being a full scan.

Practice

1. Under hash-of-order-id partitioning, how many network round trips does "Hub N's revenue only" need, and what's the answer?
   Solution

   3 round trips — same reasoning as Hub E: the coordinator can't know in advance which nodes hold Hub N's rows under hash partitioning, so it asks all three. The answer is ₹2,085, gathered from whichever nodes' partial sums are non-zero.

2. CityCourier's most common query becomes "give me this one order by id" (a point lookup), run far more often than any hub-level aggregate. Which partitioning scheme from this chapter should it prioritise, and why?
   Solution

   Section 2.3's hash-of-order-id ring — it turns "find order #4" into a single computed lookup (hash it, go straight to the owning node) with zero scatter-gather at all, which is precisely the access pattern consistent hashing was built for. Hub-based partitioning would force even a point lookup by id to check every node, since id has no relationship to hub.

3. Order #10's veracity bug was found via a secondary index on delivery_time in 1 read. Would that same index have helped find order #10 by searching on amount (₹440) instead?
   Solution

   No — an index is built on one specific column's values. A delivery_time index is sorted by delivery_time and gives no shortcut for an amount-based search; that would need its own separate secondary index on amount (exactly Section 2.5's B-tree, which was keyed on amount specifically). Every column you want fast lookups on needs its own index.

4. Combine Sections 2.4 and 2.6: if CityCourierDB uses N=3, W=2, R=2 replication (Section 2.4) and hash-of-order-id partitioning (Section 2.3), how many total network requests does a fully consistent read of a single order by id require in the worst case, and why?
   Solution

   Up to 3: the coordinator computes the order's ring position (no network cost, just arithmetic) to find which node is the primary owner — that's the 1 request a plain point lookup needs. But satisfying R=2 means checking a second replica of that same key too, since quorum reads compare multiple copies rather than trusting one. Point lookups get the ring's O(1) routing benefit; the replication factor still costs its own round trips on top, because routing and consistency are two separate concerns this chapter kept deliberately distinct.

1. A DataNode stops sending heartbeats. What does the NameNode need to do, and what information does it use to decide?
   Solution

   It checks its own metadata for which blocks that DataNode was holding, finds any now under-replicated, and issues copy commands to other live DataNodes to restore the replication factor — exactly Section 2.1's Hub S failure. It never touches file content directly; it only ever reasons about the block-to-node map it already keeps.

2. A dataset has N=4 replicas. Give one (W,R) pair that guarantees quorum overlap and one that doesn't.
   Solution

   Guarantees overlap: W=3,R=2 (3+2=5>4), or W=R=3. Doesn't guarantee it: W=2,R=2 (2+2=4, not >4) — a real, common trap, since W=R=2 looks balanced but fails the strict inequality at even N.

3. A store keeps a customer's order history as a nested JSON object with an optional "gift_note" field present on only a few orders. Which NoSQL model is this, and what would the same sparse field cost in a fixed-schema table?
   Solution

   Document model. In a fixed relational table, every row would need a "gift_note" column whether or not it's used — typically stored as NULL for the rows without one, which at scale is real wasted space for a field almost nobody fills in.

4. Five servers sit on a consistent-hash ring holding 500 keys total, evenly spread. Roughly how many keys move when a sixth server joins?
   Solution

   Roughly k/n_new = 500/6 ≈ 83 keys — only the keys in the range between the new server and its immediate clockwise predecessor. The other ~417 keys keep their existing owner untouched.

5. Why does a range query on a non-key column tend to be more expensive on an LSM-tree than a B-tree, even though both can answer it eventually?
   Solution

   A B-tree keeps everything sorted by that key at all times, so a range sits in a small contiguous run of pages. An LSM-tree's SSTables are ordered by flush time, not by the queried column's value, so a range's matches are smeared across every SSTable — each one has to be checked (or ruled out via stored min/max bounds) rather than walked to directly.

6. A query asks for the total row count across an entire dataset. Does the choice of partitioning scheme change how many nodes must be contacted?
   Solution

   No — a full-dataset aggregate needs every row regardless of how it's split, so it touches every node under any partitioning scheme. Partitioning choice only changes cost for selective queries that filter to a subset, exactly Section 2.6's Hub N-vs-Hub E-only comparison.

7. A graph database is asked to sum a numeric property across a million nodes. Is this the kind of query graph databases are built to make cheap?
   Solution

   No. Graph databases are optimised for traversal — following relationships a hop or several hops at a time — not bulk aggregation across every node, which is closer to a column-family or document store's strength. Asking a graph store to do this means paying its per-node relationship overhead for a query that never uses a single edge.

8. Order #10's veracity bug (Section 1.1) was found via a secondary index in this chapter. Which earlier chapter first flagged that this same row was a problem, and what kind of problem was it there?
   Solution

   Section 1.1, Chapter 1 — where it was introduced as a Veracity violation (a wrong-but-present value, not a missing one). This chapter reuses the identical row as a storage-and-retrieval example: the same bad data point, viewed first as a data-quality problem and later as an indexing problem.

• Hadoop: The Definitive Guide — Tom White. The full HDFS architecture behind Section 2.1's NameNode/DataNode sketch, including federation, high availability, and the actual write pipeline this chapter simplified away.
• Designing Data-Intensive Applications — Martin Kleppmann. Covers Sections 2.2 through 2.4 in real depth — data model trade-offs, partitioning strategies beyond consistent hashing, and replication consistency models with more nuance than N/W/R alone.
• Mining of Massive Datasets — Leskovec, Rajaraman & Ullman. Its index-structures chapter goes further into the B-Tree/LSM-Tree family than Section 2.5 had room for, including the hashing schemes distributed databases build on.