Patterns of Distributed Systems Link to heading

Based on: Catalog of Patterns of Distributed Systems by Unmesh Joshi (published on martinfowler.com, Nov 2023)

Table of Contents Link to heading

  1. Group E — Data Distribution & Partitioning

Group E — Data Distribution & Partitioning Link to heading

A single node cannot hold all data for a large-scale system. Partitioning distributes data across nodes. These two patterns cover the main approaches.

E1. Fixed Partitions Link to heading

Pre-assign a fixed number of buckets; map data to buckets.

Problem Link to heading

As data grows, you need to spread it across multiple nodes. But if the mapping of “data → node” changes every time you add or remove a node, you must move massive amounts of data around, which is expensive and disruptive.

Solution Link to heading

Create a fixed number of partitions (far more than the number of nodes — e.g., 1024 partitions for a 10-node cluster). Assign partitions to nodes. When you add/remove nodes, you reassign partitions, not individual data items. The partition count never changes.

How it works Link to heading 

1024 fixed partitions, 4 nodes:
  Node 1: partitions 0–255
  Node 2: partitions 256–511
  Node 3: partitions 512–767
  Node 4: partitions 768–1023

To store key K:
  partition = hash(K) % 1024  → e.g., partition 317
  → goes to Node 2

Add Node 5:
  Reassign some partitions from existing nodes to Node 5
  e.g., Node 1: 0–191, Node 5: 192–255 (and some from others)
  Only those partitions' data moves — the rest stays put

Real-world analogy Link to heading

A postal system where countries have fixed ZIP codes. Adding a new post office means reassigning some ZIP code ranges to it, not renumbering every address.

Example systems Link to heading

Kafka (fixed partitions per topic), Apache Cassandra (vnodes), Redis Cluster (16384 hash slots), Riak

Trade-offs Link to heading

Pro Con
Stable data routing (partition → node mapping is simple) Fixed partition count can be too small (or too large) for growth
Adding nodes only moves some data Hot partitions can overload specific nodes (uneven load)
Easy to reason about data placement Partition count must be set at creation time — hard to change later

→ Key-Range Partitions (alternative strategy) → Consistent Core (often tracks partition → node assignments) → Gossip Dissemination (propagates routing tables)

E2. Key-Range Partitions Link to heading

Assign sorted key ranges to nodes; enables efficient range queries.

Problem Link to heading

Hash-based partitions scatter keys randomly across nodes. This is great for uniform load distribution but terrible for range queries: “give me all orders between January 1 and January 31” would require querying every partition.

Solution Link to heading

Assign contiguous ranges of the key space to nodes (e.g., keys A–M go to Node 1, N–Z to Node 2). Since keys within a range are co-located, range queries only need to contact a small number of nodes.

How it works Link to heading 

Node 1: keys ["a" – "mzzz"]
Node 2: keys ["n" – "rzzz"]
Node 3: keys ["s" – "zzz"]

Query: all records with key starting with "o"
  → Contacts only Node 2 ✓ (efficient)

Query: all orders with order_date between 2024-01-01 and 2024-01-31
  If key = order_date → all in a small range → contacts 1-2 nodes ✓

Split and merge: When a range grows too large, split it into two. When adjacent ranges shrink, merge them. Node count stays the same; partition boundaries shift.

Real-world analogy Link to heading

A library using alphabetical sections. Looking for all books by authors with last names “Smith” through “Taylor” requires visiting only one contiguous shelf section.

Example systems Link to heading

Google Bigtable (tablets with row ranges), Apache HBase (regions), CockroachDB (key ranges), TiKV

Trade-offs Link to heading

Pro Con
Efficient range queries Risk of hotspots if keys are sequential (e.g., timestamps all going to one node)
Natural ordering of data Requires rebalancing (split/merge operations) as data grows
Maps well to time-series and sorted data More complex routing than fixed hash partitions

→ Fixed Partitions (alternative for non-range queries) → Consistent Core (manages range-to-node mapping) → Versioned Value (range queries often include version filtering)