Chapter 7: Partitioning

Introduction

The introduction contrasts partitioning with replication and previews the partitioning topics covered in the chapter.

• Partitioning and replication purposes: Distinguish partitioning as a way to overcome the scalability limits of a single component from replication as a way to overcome its reliability limits.
  Why it matters: The distinction explains why the book treats partitioning and replication as separate techniques.
• Partitioning chapter roadmap: Describe the topics previewed for the chapter: the concept of partitioning, static versus dynamic and vertical versus horizontal partitioning, item-based versus directory-based lookup, and common strategies.
  Why it matters: The roadmap shows which distinctions the chapter will develop.

Key terms: partitioning, replication, scalability, reliability, static and dynamic partitioning, vertical and horizontal partitioning, item-based lookup, directory-based lookup, common strategies

7.1 Encyclopedias and volumes

The section uses an encyclopedia split into volumes to introduce partitioning a software system across nodes and the challenges that follow.

• Logical whole and physical parts: Explain how an encyclopedia is one logical object whose entries physically occupy separate volumes, and how a software system can likewise be divided into disjoint partitions across nodes when it is too extensive for one node.
  Why it matters: This distinction makes it easier to reason about one system whose contents live in multiple places.
• Shared entry placement rule: Describe how assigning entries to volumes by their first letter lets the producer place an entry and the consumer fetch it from the corresponding volume, rather than searching every volume.
  Why it matters: A shared placement rule makes a divided collection usable for both storing and finding items.
• Partitioning challenges and requirements: Explain the three challenges illustrated by the volumes—uneven numbers of entries, uneven demand for volumes, and references that require consulting another volume—and relate them to partitions in a software system. State that the best partition strategy depends on the system’s requirements.
  Why it matters: Partitioning solves a size problem but introduces tradeoffs that the strategy must address.

Key terms: logical object, physical objects, disjoint subsets, partitions, node, producer, consumer, place, fetch, uneven distribution

7.2 Thinking in partitions

This section defines partitioning as a way to spread a logical object and its demands across nodes, then shows why both resource limits and the meaning of “big data” depend on the node.

• Logical and physical partitions: Explain how partitioning represents one logical object as multiple disjoint physical objects, called partitions, distributed across nodes to avoid a single node’s scalability limit.
  Why it matters: This is the basic model behind the chapter’s later partitioning strategies.
• Limits beyond data size: Explain that partitioning can overcome any limitation imposed by a single resource, not just insufficient storage: data volume is an intrinsic example, while request volume is an extrinsic example. Describe why “big data” is relative to what fits or can be processed on one node.
  Why it matters: It prevents you from treating partitioning as a solution only for large stored datasets.
• Inherent distributed system partitions: Describe the section’s observation that a distributed system is inherently partitioned in one sense: its communicating components each have exclusive access to their own local state, so each component and its state can be viewed as a partition.
  Why it matters: It connects partitioning to the book’s basic model of a distributed system.

Key terms: partitioning, logical object, physical objects, partitions, nodes, data volume, request volume, intrinsic property, extrinsic property, big data

7.3 The mechanics of partitioning and balancing

The section separates the two assignments involved in partitioning and shows why a partitioning strategy must fit—and adapt to—a system’s workload.

• Two partitioning assignments: Explain the difference between assigning key-value items to partitions and assigning partitions to nodes, and how distributing partitions lets a system handle more data than one node can.
  Why it matters: Keeping the two assignments separate makes it easier to reason about where data lives and how work is distributed.
• Workload-dependent partitioning tradeoffs: Explain why an apparently even distribution of data may still produce uneven reads or writes, using the social-media or sensor example. Describe why the system’s workload and requirements determine an adequate strategy.
  Why it matters: A strategy that balances stored data can still overload a partition when requests concentrate there.
• Adaptation of partitioning strategy: Describe why partitioning is not a one-time decision: requirements and conditions change, and adapting may involve moving data between partitions while the system continues serving requests.
  Why it matters: A useful initial layout may need a difficult transition as the system changes.

Key terms: key-value items, partitions, nodes, assignment, partitioning strategy, well-balanced reads and writes, skewed, unique characteristics and requirements, requirements and conditions, moves data between partitions

7.4 (Re)partitioning

This section distinguishes assigning data items to partitions from reassigning them when the partition layout changes.

• Partitioning and repartitioning distinction: Distinguish partitioning, which assigns data items to partitions, from repartitioning, which moves previously assigned items to different partitions, for example when the number of partitions changes.
  Why it matters: The distinction makes it clear whether the system is placing items or changing where existing items belong.

Key terms: partitioning, repartitioning, data items, partitions

7.4.1 Types of partitioning

This section distinguishes two ways to classify partitioning—static versus dynamic and horizontal versus vertical—and shows how the latter two can be combined for user data.

• Static and dynamic partitions: Distinguish a fixed number of partitions that changes only through offline administration from a variable number that can change online during normal operation. Explain that this distinction concerns partitions, not nodes, and trades elasticity for added complexity.
  Why it matters: This distinction tells you whether a system can adjust its partition count as demand changes.
• Horizontal and vertical partitions: Describe horizontal partitioning, or sharding, as dividing table rows and vertical partitioning as dividing table columns.
  Why it matters: Rows and columns provide a simple way to picture two different ways of dividing data.
• Combined user data partitioning: Trace how the user-information example first separates text profiles from profile pictures vertically, then distributes each kind horizontally. Explain why the two data types use different storage systems and how the combination lets them scale independently.
  Why it matters: The example shows that partitioning by data type and partitioning for distribution can solve different needs together.

Key terms: static partitioning, dynamic partitioning, elastic, online, offline, horizontal partitioning, sharding, vertical partitioning, rows, columns

7.4.2 Data item to partition assignment strategies

This section compares item-based and directory-based ways to assign data to partitions, including how to judge their suitability and the tradeoff between simplicity and placement control.

• Assignment strategy evaluation: Explain how variance and relocation are used to assess a partition assignment strategy: variance concerns how evenly items are distributed, while relocation counts items that must move when the number of partitions changes.
  Why it matters: These measures help you compare assignment strategies as a system changes.
• Item and directory assignment: Distinguish item-based assignment, which determines a partition solely from an item's characteristics such as its key or a hash and needs no stored assignment state, from directory-based assignment, which uses the item and a separate, stateful directory or lookup table.
  Why it matters: The source of the assignment determines both how simple the strategy is and what control it offers.
• Placement control tradeoff: Explain why stateless item-based assignment is simpler but offers only coarse-grained control, while directory-based assignment is more complex but permits placement in specific partitions. Describe the risk of hot items landing together under item-based assignment and of the directory becoming a scalability or reliability bottleneck.
  Why it matters: Choosing an assignment strategy means weighing operational simplicity against precise placement and the directory's costs.

Key terms: variance, relocation, item-based assignment, directory-based assignment, stateless, stateful, directory, lookup table, coarse-grained, fine-grained

7.5 Common item-based assignment strategies

The section sets up an experiment for comparing item-to-partition assignment functions by how well they let the system find items and balance them across partitions.

• Assignment function requirements: Explain that an assignment function must let the system find an item and distribute items evenly across partitions.
  Why it matters: These are the criteria for comparing the assignment strategies that follow.
• Word assignment experiment: Describe the experiment: assign each word in a UNIX words file to one of five partitions, then count the items in each partition to compare assignment functions. State that with 235,976 words, an even split would put just under 47,200 items in each partition.
  Why it matters: The counts provide a concrete way to compare how evenly the functions distribute items.

Key terms: assignment function, find an item, balance items, words file, five partitions, count the items, Listing 7.3

7.5.1 Range partitioning

This section shows how range partitioning assigns keys to partitions and illustrates that it can produce an uneven distribution.

• Key range assignment: Explain that each partition hosts items whose keys fall within a particular range, and that the example assignment function uses the first letter of a key to choose a partition.
  Why it matters: The assignment rule determines where each item is stored.
• Uneven partition distribution: Describe how the example’s resulting distribution is poorly balanced, with partitions 3 and 0 standing out as hotspots.
  Why it matters: A clear assignment rule does not guarantee that items will be spread evenly.

Key terms: range partitioning, key range, assignment function, distribution, well-balanced, hotspots

7.5.2 Hash partitioning

This section introduces hash-based assignment of keys to partitions and observes that the example produces a balanced distribution.

• Hash-based key assignment: Explain that hash partitioning calculates a hash value for each key and uses the result to assign the key to a partition; the example assigns keys among five partitions.
  Why it matters: Hash values provide a way to decide where each key belongs.
• Balanced example distribution: Describe the reported outcome of running the example: items were well balanced across partitions, with no hotspots caused by uneven item distribution.
  Why it matters: The example shows what a balanced placement looks like in terms of item counts.

Key terms: hash value, key, partition, assignment function, well balanced, hotspots, distribution

7.6 Repartitioning

This introduction explains why changing the number of partitions can disrupt item placement and sets up a count of items that stay or move when partitions increase from five to six.

• Partition count and item placement: Explain that the number of partitions can increase or decrease over time, and that changing it has an outsized effect on placement under item-based assignment strategies.
  Why it matters: This is why repartitioning requires attention to where items end up.
• Staying and relocating item counts: Describe the section's proposed comparison: use code to count items that remain in their partition and items that must move when the number of partitions changes from five to six.
  Why it matters: Counting both groups makes the placement impact of a partition-count change concrete.

Key terms: repartitioning, item-based assignment strategies, number of partitions, placement, items remaining in their partition, items that must be relocated, 5 to 6

7.6.1 Range partitioning

This subsection reports how many items stay put or move when the author tests range-partitioning placement functions.

• Range repartitioning relocation split: Describe the reported result of running the script from listing 7.6 with the placement functions in listing 7.7: on the author's machine, 48.6% of items remained in their current partition and 51.4% moved to a different one.
  Why it matters: The result shows that this test produced an almost-even split between items that stayed and items that moved.

Key terms: range partitioning, placement functions, partition, relocate

7.6.2 Hash partitioning

This subsection shows that hash partitioning minimizes variance but, like range partitioning, can require extensive item relocation during repartitioning.

• Variance and relocation tradeoff: Explain that hash partitioning performs well at minimizing variance, while both hash and range partitioning perform poorly at minimizing relocation.
  Why it matters: A balanced split does not necessarily mean that repartitioning moves few items.
• Observed hash repartitioning split: Describe the reported run of the script with the hash placement function: 16.7% of items stayed in their current partition, while 83.3% had to move to another.
  Why it matters: The reported split makes the relocation cost concrete.

Key terms: hash partitioning, range partitioning, minimizing variance, minimizing relocation, placement function, current partition, relocate

7.7 Consistent hashing

The section presents consistent hashing through its partitioning effects and argues for understanding those effects before its implementation.

• Consistent hashing partitioning effects: Explain that consistent hashing aims for both minimal variance and minimal relocation: with n items and m partitions, about n/m items need to move to another partition on average. Describe the reported run in which 81.5% of items stayed put and 18.5% moved.
  Why it matters: These effects explain why consistent hashing is useful when partition assignments change.
• Effect-first algorithm mental model: Explain why the section approaches consistent hashing through its specification or interface—what it achieves—rather than building an understanding from implementation details.
  Why it matters: Focusing on an algorithm’s effects makes its system-level role clear without first unpacking its internals.

Key terms: consistent hashing, minimal variance, minimal relocation, partitions, specification, signatures or interfaces, effect of consistent hashing

7.8 (Re)balancing and overpartitioning

This section explains how assigning multiple partitions to each node makes it easier to rebalance capacity, while the number of partitions still limits how many nodes can be used.

• Balancing and rebalancing assignments: Distinguish balancing, which assigns partitions to nodes, from rebalancing, which moves previously assigned partitions to different nodes, for example when demand changes.
  Why it matters: This distinction makes it clear what changes when a system responds to demand.
• Overpartitioning and flexible capacity: Explain that overpartitioning creates more partitions than nodes, giving each node multiple partitions that can be reassigned when nodes are added or removed. Contrast this with a one-partition-per-node setup, which lacks that flexibility.
  Why it matters: Multiple partitions per node let the system adjust its node count as demand changes.
• Partition count scaling limit: Explain why overpartitioning does not allow unlimited node growth: the number of partitions sets the maximum number of nodes that can receive partitions.
  Why it matters: Overpartitioning provides room to scale, but its partition count sets a ceiling.

Key terms: balancing, rebalancing, partitions, nodes, overpartitioning, number of partitions, maximum number of nodes

7.9 Summary

The section recaps how partitioning scales a system, distinguishes partitioning from balancing, and summarizes choices for dividing and assigning data as requirements change.