Hash Rings and Consistent Hashing

Up to now, we've focused on squeezing every ounce of performance out of a single CPU core. But what happens when the workload outgrows a single machine? In a massive multiplayer game or a globally distributed database, we can have more concurrent connections than a single core can physically process.

We need to distribute the work across a cluster of different threads/cores, or even a cluster of different servers. Additionally, this distribution must be consistent. If Player One's active session is being managed by Server B, every single packet Player One sends must be routed to Server B.

This sounds like a similar problem to what we've been solving with hash tables throughout the rest of the chapter. We could hash a key (the Player ID), and map it to a bucket. Except now, each bucket represents a different server.

However, the bitwise masking or modulo math approach - Hash(PlayerID) % NumServers - is problematic in this context.

Let's look at the modulo approach. If we have 50 servers, we can hash the incoming network packet and use % to find its destination:

1// A naive distributed routing function
2int GetServerIndex(std::string_view key, int numServers) {
3  size_t hash = HashString(key);
4  return hash % numServers;
5}

This works perfectly when the network is completely static. The math evenly distributes the keys, and every time a request comes in for "PlayerOne", the formula would deterministically route it to the same server.

But networking isn't static. What if we want to add or remove some servers from the pool? Removing servers might be intentional - as our player counts change throughout the day, we may want to distribute them across more or fewer servers.

It may also be unintentional - a server might suddenly crash.

If one server out of 50 dies, we now have around 2.5% of our players trying to interact with an offline server. However, in our modulo-based technique, if we change numServers from 50 to 49, the routing for almost every single player also changes:

1#include <iostream>
2#include <vector>
3#include <string>
4
5// A simple string hasher
6uint64_t HashString(const std::string& key) {
7  uint64_t hash = 5381;
8  for (char c : key) hash = ((hash << 5) + hash) + c;
9  return hash;
10}
11
12int main() {
13  const int NumKeys = 100'000;
14  int MigratedKeys = 0;
15
16  for (int i = 0; i < NumKeys; ++i) {
17    std::string key = "Player" + std::to_string(i);
18    uint64_t hash = HashString(key);
19
20    // Where does the key live when we have 50 servers?
21    int oldServer = hash % 50;
22
23    // A single server crashes. Where does the key live now?
24    int newServer = hash % 49;
25
26    if (oldServer != newServer) {
27      MigratedKeys++;
28    }
29  }
30
31  double failureRate = (MigratedKeys / (double)NumKeys) * 100.0;
32  std::cout << "Keys forced to migrate: " << failureRate << "%\n";
33}

1Keys forced to migrate: 98.024%

This is known as a Network Reallocation Spike, and it is a major source of outages.

Because 98% of the data now hashes to the "wrong" server, 98% of traffic received by each server will be for a player that the server doesn't know about. All of those requests might then try to load the player's data from our database all at once.

Maybe the architecture can handle this, and the network reallocation just causes some disruption and latency. Or maybe the database will melt under the explosion in traffic. What started with a failure in one node can take the entire architecture offline.

Instead, we need a layout that decouples our hash outputs from the server count.

Consistent Hashing solves this by mapping both the keys and the servers onto the same integer space.

Imagine taking all of our possible hash outputs and visualizing those integers as a ring that wraps around.

We then take some way to identify our servers, such as their IP address. We hash those identifiers to generate an integer, and place them onto our ring at that corresponding location. If our cluster had 4 servers, our ring might look something like this:

When a request for "PlayerOne" comes in, we hash the string "PlayerOne" to find its position on the ring. Then, to figure out which server owns the data, we simply "walk" clockwise around the ring (increasing the integer value) until we hit the first server.

Below, we take "PlayerOne"'s hash, and find the first server that hashed to a higher integer, which is Server B:

Now, if Server B crashes and is removed from the ring, we don't recalculate modulo math for the entire network. The only keys affected are the ones that were sitting directly between Server A and Server B.

Those orphaned keys simply continue walking clockwise until they find Server C. The rest of the network is completely untouched. Only the immediate neighbor absorbs the load of the dead machine:

This prevents a complete network reallocation. Server C suddenly becoming responsible for all of Server B's traffic isn't ideal, but we'll see how to distribute the load more fairly later in the lesson. For now, let's implement this initial idea.

How do we actually build this ring in C++? Even though we are going to map servers and requests to a huge 64-bit integer space, that doesn't mean we need a huge array. We're not actually storing the requests - we're just routing them.

Therefore, all slots between the servers in our ring will be empty - we can just remove them.

This means our ring can be compressed into a much smaller array that only needs to be large enough to store our server nodes. The order of these nodes still needs to be the same in the compressed ring, so we sort this array by the original hash value:

Implementing the Ring

Let's implement this by creating a small std::vector of sortable Node structs representing our servers. We'll use a basic int to identify the servers, which will also be the key for our hash function.

We'll also cache the uint64_t hash value as a performance optimization, and we'll implement the < operator to allow our nodes to be sorted by this value:

1#pragma once
2#include <vector>
3#include <string>
4#include <string_view>
5#include <algorithm>
6#include <cstdint>
7
8class HashRing {
9private:
10  struct Node {
11    uint64_t Hash;
12    int ServerId;
13    
14    // Operator overload to allow sorting
15    bool operator<(const Node& other) const {
16      return Hash < other.Hash;
17    }
18  };
19
20  std::vector<Node> Ring;
21};

Implementing AddServer()

Our lightweight 4-byte ServerId integer is an internal handle for our nodes that has no real meaning outside of our HashRing. In real-world use cases, there would be a more meaningful identifier for our servers, such as their IP address.

To maintain our data-oriented design philosophy, we would not want these heavy and unnecessary std::strings disrupting the memory layouts used in the performance-critical paths, which are the Nodes in this example.

We could intern those strings in a separate global vault, but to keep things simple in this lesson, we'll just store them as a separate std::vector within our HashRing.

Let's implement our AddServer() function, which accepts these strings, creates a corresponding Node, and adds it to our Ring. It also needs to re-sort the Ring after this happens to maintain the relative order. Adding servers to our cluster is a relatively rare action, so keeping this array sorted is inexpensive:

1// ...
2
3class HashRing {
4private:
5  // ...
6  std::vector<std::string> ServerNames;
7  
8  // A hasher using the Mix64 avalanche effect
9  uint64_t HashString(std::string_view key) const {
10    uint64_t hash = 5381;
11    for (char c : key) hash = ((hash << 5) + hash) + c;
12    hash ^= hash >> 30;
13    hash *= 0xbf58476d1ce4e5b9ULL;
14    hash ^= hash >> 27;
15    hash *= 0x94d049bb133111ebULL;
16    hash ^= hash >> 31;
17    return hash;
18  }
19
20
21public:
22  void AddServer(std::string_view serverName) {
23    int serverId = static_cast<int>(ServerNames.size());
24    ServerNames.emplace_back(serverName);
25
26    uint64_t hash = HashString(serverName);
27    Ring.push_back({hash, serverId});
28    
29    // Keep the contiguous array perfectly sorted
30    std::sort(Ring.begin(), Ring.end());
31  }
32};

Why not use std::hash?

You might wonder why we wrote our own HashString function instead of using std::hash. In a distributed environment, our hash function might be running on multiple machines, and we need the outputs to be deterministic across all of those machines.

The standard does not require that of std::hash - it is only guaranteed to be consistent during a single execution of the program. Many implementations intentionally randomize their internal seed on startup.

Additionally, std::hash returns a size_t, which changes size depending on whether the architecture is 32-bit or 64-bit.

By providing our own algorithm like the approach above, or common open-source options like MurmurHash3, we guarantee consistent routing tables across the entire cluster.

Implementing RemoveServer()

For RemoveServer() , we need to take the string and find its index in ServerNames, which maps directly to the ServerId in our Node struct. We then need to erase that Node in the Ring.

1// ...
2
3class HashRing {
4private:
5  // ...
6public:
7  // ...
8  void RemoveServer(std::string_view serverName) {
9    auto it = std::find(
10      ServerNames.begin(), ServerNames.end(), serverName
11    );
12    if (it == ServerNames.end()) return;
13    
14    int serverId = static_cast<int>(
15      std::distance(ServerNames.begin(), it)
16    );
17
18    // Physically erase the node from the contiguous array
19    std::erase_if(Ring, [serverId](const Node& n) {
20      return n.ServerId == serverId;
21    });
22  }
23};

Using std::erase_if() is a little inefficient right now. We know we only have one server to delete, but std::erase_if() assumes there may be multiple matching elements. It continues to search the full array even after it finds our server.

We'll leave it there for now, as this behavior will be useful when we add virtual nodes in the next section.

Implementing Routing

To route a packet, we take the key such as "PlayerOne", we hash it, and we then search our array to find the first Node whose hash is greater than "PlayerOne"'s hash.

Because the Ring is sorted by the nodes' hash values, this can be an $O(\text{log}N)$ binary search and, because the array is relatively small - one Node per physical server - $N$ is pretty small, too.

To retrieve the owning server, we can use std::upper_bound() binary search function. Because our array represents a ring, if our binary search walks past the very last element in the array, we simply wrap around and return the first element.

1#pragma once
2#include <vector>
3#include <string>
4#include <string_view>
5#include <algorithm>
6#include <cstdint>
7
8class HashRing {
9private:
10  // ...
11
12public:
13  // ...
14  std::string_view GetOwningServer(std::string_view key) const {
15    if (Ring.empty()) return "";
16
17    uint64_t hash = HashString(key);
18    Node dummy{hash, -1};
19
20    // Binary search the ring for the next node clockwise
21    auto it = std::upper_bound(Ring.begin(), Ring.end(), dummy);
22
23    // If we walked past the end, wrap around to the beginning
24    if (it == Ring.end()) {
25      it = Ring.begin();
26    }
27
28    return ServerNames[it->ServerId];
29  }
30};

Our structure works, but there are two remaining problems.

Firstly, hash functions distribute keys randomly, but random does not mean evenly spaced. If we throw 3 servers onto our ring, our hash function might create the following setup:

This would result in Server C being responsible for a disproportionate amount of traffic, whilst Server A is relatively idle.

And the second problem is: what happens if Server B gets removed? All of its traffic gets reallocated to Server C, whilst Server A still has very little to do.

The solution to both of these problems is to introduce Virtual Nodes (VNodes).

Instead of putting each physical server on the ring once, we place many virtual copies of it - perhaps 50 or 100 instances. Each copy will have the same ServerId, representing that they map to the same underlying physical server, but they will have a different Hash, representing that they have a different position in the ring.

Below, we give our 3 physical servers 50 virtual nodes each, which smooths out the variance. Whilst many of these copies still get lucky or unlucky with their hash, across 50 different hashes, that will average out such that each physical server gets an approximately equal share of the ring:

There are two main ways to generate these 100 different hashes. Some hash functions let us provide the random seed that they use, so we would just use the same key with 100 different seeds.

Alternatively, each VNode can use a different key. For example, if a server was identified by the IP address 50.128.65.59, the VNodes might append an incrementing number, using keys like 50.128.65.59#1, 50.128.65.59#2, 50.128.65.59#3, and so on. With a hash function that avalanches correctly, these similar keys will scatter our VNodes across our ring.

Let's modify our class to support virtual nodes. We'll set a default of 100 VNodes per physical machine:

1// ...
2class HashRing {
3private:
4  // ...
5  int VNodes{100}; 
6  
7public:
8  void SetVNodes(int count) { VNodes = count; } 
9
10  void AddServer(std::string_view serverName) {
11    int serverId = static_cast<int>(ServerNames.size());
12    ServerNames.emplace_back(serverName);
13
14    // Generate 100 virtual nodes for this physical server
15    for (int i = 0; i < VNodes; ++i) { 
16      std::string vNodeName = std::string(serverName)   
17                              + "#" + std::to_string(i); 
18      uint64_t hash = HashString(vNodeName); 
19      Ring.push_back({hash, serverId}); 
20    } 
21    
22    std::sort(Ring.begin(), Ring.end());
23  }
24  // ...
25};

Below, we have an example of our HashRing in action. It sends requests from Player1, Player2, and Player3 to three different servers. After the machine serving Player1 is removed, those requests get rerouted to another server.

The other players are not disrupted - their requests are routed to the same server they were previously:

1#include <print> // C++23
2#include <dsa/HashRing.h>
3
4int main() {
5  HashRing ring;
6
7  ring.AddServer("192.168.1.10");
8  ring.AddServer("192.168.1.20");
9  ring.AddServer("192.168.1.30");
10
11  std::string P1{"Player1"};
12  std::string P2{"Player2"};
13  std::string P3{"Player3"};
14
15  std::println("{} -> {}", P1, ring.GetOwningServer(P1));
16  std::println("{} -> {}", P2, ring.GetOwningServer(P2));
17  std::println("{} -> {}", P3, ring.GetOwningServer(P3));
18
19  ring.RemoveServer("192.168.1.20");
20  std::println("\n192.168.1.20 has crashed!\n");
21
22  std::println("{} -> {}", P1, ring.GetOwningServer(P1));
23  std::println("{} -> {}", P2, ring.GetOwningServer(P2));
24  std::println("{} -> {}", P3, ring.GetOwningServer(P3));
25}

1Player1 -> 192.168.1.20
2Player2 -> 192.168.1.30
3Player3 -> 192.168.1.10
4
5192.168.1.20 has crashed!
6
7Player1 -> 192.168.1.10
8Player2 -> 192.168.1.30
9Player3 -> 192.168.1.10

Let's measure how effective these virtual nodes are at smoothing out the variance in our load balancer.

In this benchmark, we simulate an influx of 1,000,000 requests across a 10-node cluster. We will track the minimum and maximum number of requests handled by a single server. We can use Google Benchmark's custom counters to see how our load is balanced:

1#include <benchmark/benchmark.h>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <algorithm>
6#include <dsa/HashRing.h>
7
8const int kNumServers = 10;
9const int kNumKeys = 1'000'000;
10
11// Helper to find the busiest and most idle server load counts
12struct LoadStats {
13  int minLoad;
14  int maxLoad;
15};
16
17LoadStats CalculateLoadStats(
18  const std::unordered_map<std::string, int>& loadCounts
19) {
20  LoadStats stats{INT_MAX, INT_MIN};
21  for (const auto& pair : loadCounts) {
22    stats.minLoad = std::min(stats.minLoad, pair.second);
23    stats.maxLoad = std::max(stats.maxLoad, pair.second);
24  }
25  return stats;
26}
27
28static void BM_HashRing_NoVNodes(benchmark::State& state) {
29  HashRing ring;
30  ring.SetVNodes(1); // Force 1 VNode (Naive approach)
31  std::vector<std::string> servers;
32  for (int i = 0; i < kNumServers; ++i) {
33    std::string srv = "Server_" + std::to_string(i);
34    servers.push_back(srv);
35    ring.AddServer(srv);
36  }
37  for (auto _ : state) {
38    std::unordered_map<std::string, int> loadCounts;
39    for (const auto& srv : servers) loadCounts[srv] = 0;
40    for (int i = 0; i < kNumKeys; ++i) {
41      std::string key = "Key_" + std::to_string(i);
42      std::string_view owner = ring.GetOwningServer(key);
43      loadCounts[std::string(owner)]++;
44    }
45    LoadStats stats = CalculateLoadStats(loadCounts);
46    state.counters["Load_Min"] = stats.minLoad;
47    state.counters["Load_Max"] = stats.maxLoad;
48  }
49}
50
51static void BM_HashRing_WithVNodes(benchmark::State& state) {
52  HashRing ring;
53  ring.SetVNodes(100); // 100 VNodes per physical machine
54  std::vector<std::string> servers;
55  for (int i = 0; i < kNumServers; ++i) {
56    std::string srv = "Server_" + std::to_string(i);
57    servers.push_back(srv);
58    ring.AddServer(srv);
59  }
60  for (auto _ : state) {
61    std::unordered_map<std::string, int> loadCounts;
62    for (const auto& srv : servers) loadCounts[srv] = 0;
63    for (int i = 0; i < kNumKeys; ++i) {
64      std::string key = "Key_" + std::to_string(i);
65      std::string_view owner = ring.GetOwningServer(key);
66      loadCounts[std::string(owner)]++;
67    }
68    LoadStats stats = CalculateLoadStats(loadCounts);
69    state.counters["Load_Min"] = stats.minLoad;
70    state.counters["Load_Max"] = stats.maxLoad;
71  }
72}
73
74BENCHMARK(BM_HashRing_NoVNodes);
75BENCHMARK(BM_HashRing_WithVNodes);

1-----------------------------------------------------------
2Benchmark                UserCounters...
3-----------------------------------------------------------
4BM_HashRing_NoVNodes     Load_Max=257.325k Load_Min=15.731k
5BM_HashRing_WithVNodes   Load_Max=114.389k Load_Min=89.993k

In a perfectly balanced network, every server would process exactly 100,000 requests. Without virtual nodes, one server got unlucky with its hash and got hammered with over 257,000 requests - almost 26% of the entire network's traffic. Another was allocated less than 1.6% of the traffic.

By giving each physical server 100 hashes through virtual nodes, the variance collapses. The busiest server processes roughly 11% of the traffic, and the quietest processes 9%.

Here is the complete implementation of our robust, cache-friendly HashRing class, featuring virtual nodes:

In this lesson, we expanded the principles of hashing to manage distributed data across a network cluster. We learned that:

1. The Reallocation Spike: Modulo-based routing mathematically destroys the network when the server count changes. Consistent hashing decouples keys from the machine count, ensuring only immediate neighbors are affected by hardware failures.
2. Logical Ring / Physical Array: We map the theoretical 360-degree hash ring into a tightly packed, sorted std::vector, using $O(\text{log}N)$ binary searches to route traffics.
3. Data-Oriented Node Structures: By storing heavy std::string data in a separate location and packing our ring with raw 4-byte handles, we maximize the number of nodes the CPU prefetcher can load in a single cycle.
4. Virtual Nodes: Hash algorithms are random, which naturally leads to clustered hotspots. We forcefully eliminate this variance by injecting many virtual nodes per physical machine, statistically balancing load across the network.