Patterns of Distributed Systems

Chapter 20

Key-Range Partitions

Partition data in sorted key ranges to efficiently handle range queries.

Problem

To split data across a set of cluster nodes, each data item needs to be mapped to a node. If users want to query a range of keys, specifying only the start and end key, all partitions will need to be queried for the values to be acquired. Querying every partition for a single request is far from optimal.

Take a key-value store as an example. We can store the author names using hash-based mapping, as in Fixed Partitions (Table 20.1).

Table 20.1 Key Mapping to Cluster Nodes Using Hash of a Key

Keys	Hash	Partition = Hash % Number of partitions (9)	Node
alice	133299819613694460644197938031451912208	0	0
bob	63479738429015246738359000453022047291 ...