Always learning - Consistent hashing to reduce impact of database shard rebalancing

Introduction

This post will describe an approach to balancing the distribution and redistribution of data in horizontally scaled databases.

It is something that I came across as part of preparing for system design interviews, which often involve discussions weighing up the pros and cons and risks of applying particular approaches to storing data.

Storing structured data at scale

What is structured data?

Structured data is at the core of most applications on the Internet.

Without going into too much detail, let's just expect that it is something that is stored in a way that enables us to consistently be able to retrieve it for later use and be in a particular known shape.

How does retrieval work? 

Retrieval of structured data basically involves taking an identifier, such as a primary key, and being able to quickly look up an index to the one location that is expected to give an authoritative perspective of the current state of the corresponding record.

In the simplest case of a single physical server acting as the database, it has full responsibility for all records, but that is a severe limitation on scalability.

Simple hash for sharding to scale horizontally

If we scale up to store data across mutiple physical servers we can avoid redundant duplicate processing of lookups by applying an approach to distribute the storage based on the primary key. When we only have two servers it may be find to apply a very simple hash and modulo arithmetic model to consistently balance the distribution of data.

Store or retrieve data with key 235723

Hashing the key, might give a value such as 5821725

Modulo 2 of the hashed value gets us to 1, so that record is stored on node 1, and is retrievable from there.

That works fine, until we come to needing to scale up further. Once we add a third node our modulo of the key drastically changes where the lookups will be mapped to.

An extra layer of indirection

Knowing about a limitation in advance allows us an opportunity to prepare for the future and mitigate against limitations.

Rather than the coarse grained approach of hashing directly down to the number of nodes that are available, we can choose a wide range of potential hash values and define our own distribution of nodes that sub-ranges should be mapped onto. This is commonly represented as a ring of hashed key ranges which map out to a specific node. Different segments of the range of potential values can be allocated to the same destination node.

As nodes are added we can have more control over the redistribution of sub-sets of the data by adjusting the distribution to include new nodes. So instead of having to take the entire database offline to step through every item for potential redistribution we can restrict the blast radius down to a small sub-set at a time as the existing data gets migrated.

Likewise, if we have a situation where we want to scale down for some reason, we can apply a mechanism to update the mapping to different nodes in a gradual and balanced way.

A tip for simplifying rebalancing

When we store our data we can include some metadata to represent the hashed value that determines what node it is allocated to. This enables us to more quickly identify the objects that will need to be migrated when a hash range needs to be moved to a different node.

Without the metadata we would be stuck with iterating through all keys from the preceding node in the ring to re-calculate the hash and determine they happened to fall within the range of values that we are evaluating for, to decide whether the data should stay or be moved.