Consistent Hashing: Hash Rings, Virtual Nodes and a C# Implementation

Version note: The code in this post was built and run with C# 14 and .NET 10; the hash function is XxHash3 from System.IO.Hashing 10.0.14, and the tests ran with xUnit v3 4.0.2.

Guess First

Bookstore's book cache is spread across four Redis instances. The application decides which book lives on which instance: it takes the key's hash and divides by the number of instances, and the remainder is the instance's index. The cache hit rate is 95% and the database is relaxed.

The day before the campaign, memory looks like it won't be enough and the team adds a fifth Redis instance. The moment they add it, what percentage of the cached keys ends up on the "wrong" instance, meaning a cache miss on the next read: 20%, 50% or 80%? And remembering the cache stampede from the caching post: what happens to the database at that moment?

Why Does hash % N Break?

The simplest way to spread a key across N nodes is hash(key) % N. The distribution is even, the math is cheap, no state is needed. The problem appears when N changes: for a key to stay put, hash % 4 and hash % 5 must give the same result, and that happens in only 4 of the 20 possible remainder pairs. So only one fifth of the keys stay. Measured with 100,000 keys:

hash % N        4 -> 5 nodes: 80.2% of keys move

The answer to the opening guess is 80%. The moment the fifth instance is added, 80% of the cache is effectively empty and the hit rate drops from 95% to below 20%; the stampede from "Caching Strategies: Cache-Aside, Write-Through, Write-Behind and Cache Stampede" now happens not for a single key but for almost the whole cache at once. In the previous post, "Scaling the Data Layer: Replication, Sharding and SQL (Structured Query Language) vs NoSQL", we saw the same 80% as orders that have to move between shards. In a cache it is a performance disaster; in a database it is a data migration that takes hours.

The property we want: going from N nodes to N+1, only the keys that fall to the new node's share, roughly 1/(N+1), should move and the rest should stay. When a node is removed, only its keys should spread to other nodes.

The Hash Ring

Consistent hashing was proposed in David Karger and colleagues' 1997 paper "Consistent Hashing and Random Trees" to spread web caches. The idea is to place both keys and nodes in the same hash space. The hash space is the numbers from 0 to 2^32, thought of as a ring with the ends joined. Each node sits at one or more points; a key belongs to the first node met by walking clockwise from the point its hash falls on.

The positions in the figure are real hash values from the code below. book:42 is at 131.5 degrees; the first point it meets clockwise is d#0 at 174.5 degrees, so cache-d. When a new node is added, new points are added to the ring and only the keys in the ranges right before those points change owner; the rest of the ring is untouched. When a node is removed, its ranges pass to the next node clockwise.

A Hash Ring in C#

We keep the ring in a SortedDictionary<uint, string>: the key is the position on the ring, the value the node's name. Because SortedDictionary has no "first key greater than this value" query, every time the ring changes we keep a sorted copy of the keys as an array and search with Array.BinarySearch. The ring changes rarely and is read often, so the trade-off is right.

public sealed class ConsistentHashRing(int virtualNodes)
{
    private readonly SortedDictionary<uint, string> _ring = [];
    private uint[] _positions = [];

    public void Add(string node)
    {
        for (int i = 0; i < virtualNodes; i++)
            _ring[Hash($"{node}#{i}")] = node;   // each node appears on the ring virtualNodes times
        _positions = [.. _ring.Keys];
    }

    public void Remove(string node)
    {
        for (int i = 0; i < virtualNodes; i++)
            _ring.Remove(Hash($"{node}#{i}"));
        _positions = [.. _ring.Keys];
    }

    // walk clockwise from the key's hash and take the first node
    public string GetNode(string key)
    {
        if (_positions.Length == 0) throw new InvalidOperationException("The ring is empty.");
        uint h = Hash(key);
        int index = Array.BinarySearch(_positions, h);
        if (index < 0) index = ~index;                  // first position greater than h
        if (index == _positions.Length) index = 0;      // wrap from the end of the ring to the start
        return _ring[_positions[index]];
    }

    public static uint Hash(string value) => (uint)XxHash3.HashToUInt64(Encoding.UTF8.GetBytes(value));
}

When the value is not found, Array.BinarySearch returns "the bitwise complement of the index of the first larger element"; that is why ~index gives the first position clockwise directly. If we reach the end of the ring we wrap to the start. The lookup is O(log V), where V is the total number of points on the ring. As the hash function we use XxHash3 from the System.IO.Hashing package: fast, well distributed and, most importantly, it gives the same result in every process on every machine. Why that matters is in the pitfalls section.

Virtual Nodes

If you put each node on the ring as a single point, four points cut the ring into four arcs of random length and the nodes' load is as uneven as those arcs. The fix is to place each node on the ring many times under different names (cache-a#0, cache-a#1…): virtual nodes. As the number of points grows, each node's total share approaches the average. Going from 4 to 5 nodes and the load spread on 4 nodes with three different virtual node counts:

ring,   1 vnodes 4 -> 5 nodes: 27.9% of keys move, load on 4 nodes: max/avg 2.16, min/avg 0.29
ring,  10 vnodes 4 -> 5 nodes: 17.9% of keys move, load on 4 nodes: max/avg 1.54, min/avg 0.44
ring, 200 vnodes 4 -> 5 nodes: 21.8% of keys move, load on 4 nodes: max/avg 1.07, min/avg 0.91

With a single point the busiest node gets 2.16 times the average number of keys and the least busy 0.29 times: one Redis instance does seven times the work of another. The moved fraction is also down to luck (27.9%), because the new node's single point lands in the middle of a random arc. With 200 virtual nodes the load is within ±10% of the average and the moved fraction is close to the ideal 20%. The cost is memory and the time to build the ring: 4 nodes × 200 points = an 800-element array, which is negligible. A side benefit of virtual nodes is heterogeneous machines: giving a machine twice as strong twice the virtual nodes gives a weighted distribution.

Measuring with xUnit

Writing the promises of consistent hashing as tests stops someone changing the implementation from breaking these properties without noticing:

[Fact]
public void Adding_a_fifth_node_moves_about_one_fifth_of_the_keys()
{
    ConsistentHashRing ring = RingOf("cache-a", "cache-b", "cache-c", "cache-d");
    Dictionary<string, string> before = Keys.ToDictionary(k => k, ring.GetNode);

    ring.Add("cache-e");

    string[] moved = [.. Keys.Where(k => before[k] != ring.GetNode(k))];
    double fraction = moved.Length / (double)Keys.Length;
    Assert.InRange(fraction, 0.15, 0.25);
    Assert.All(moved, k => Assert.Equal("cache-e", ring.GetNode(k)));   // every moved key goes to the new node
}

[Fact]
public void Removing_a_node_moves_only_the_keys_it_owned()
{
    ConsistentHashRing ring = RingOf("cache-a", "cache-b", "cache-c", "cache-d");
    Dictionary<string, string> before = Keys.ToDictionary(k => k, ring.GetNode);

    ring.Remove("cache-b");

    Assert.All(Keys.Where(k => before[k] != "cache-b"), k => Assert.Equal(before[k], ring.GetNode(k)));
}

The second half of the tests matters more than the fractions. The last assertion in the first test says every moved key goes to the new node: no key changes places among the existing four nodes. The second test verifies that when a node is removed, only its keys move. These are the definition of consistent hashing. The real output of the four tests (the other two check that with 200 virtual nodes the load stays within 15% of the average, and that the same key goes to the same node regardless of the order the nodes were added in):

=== TEST EXECUTION SUMMARY ===
   Hashing.Tests  Total: 4, Errors: 0, Failed: 0, Skipped: 0, Not Run: 0, Time: 0.130s

Where Is It Used?

Distributed cache clients: in the memcached world the Ketama algorithm, which does consistent hashing on the client side, became widespread. Database partitioning: Amazon's 2007 Dynamo paper used consistent hashing together with virtual nodes; Apache Cassandra applies the same idea with tokens, and the num_tokens setting decides how many tokens each node takes on the ring. Load balancing: Envoy proxy's ring_hash and maglev policies do the hash-based distribution from the series' load balancing post in a way that breaks little when instances are added and removed; Maglev is a consistent hashing variant with a more even distribution that Google developed for its own load balancer.

You need to know one exception: Redis Cluster does not use consistent hashing. It puts every key into one of 16,384 fixed hash slots with CRC16 (Cyclic Redundancy Check) and spreads the slots over nodes; when a node is added some slots move to it. This is exactly the "far more logical partitions than shards" idea from the previous post, and it gives the same result: only the keys of the moved slots move. When StackExchange.Redis connects to a cluster it learns the slot map from the server; in that case you are not the one distributing keys. The place where you need to write your own consistent hashing is where you distribute on the application side across instances that know nothing about each other (several independent Redis servers, your own cache nodes, your own sharding router).

A Quick Look at Rendezvous Hashing

The same problem has an older and simpler solution: rendezvous hashing, or HRW (Highest Random Weight), from David Thaler and Chinya Ravishankar's work in the late 1990s. There is no ring: for each key a score is computed for each node, and the node with the highest score wins.

public static class RendezvousHashing
{
    // compute hash(key + node) for each node; the node with the highest score wins
    public static string GetNode(string key, IEnumerable<string> nodes) =>
        nodes.MaxBy(node => ConsistentHashRing.Hash($"{key}|{node}"))!;
}

rendezvous      4 -> 5 nodes: 20.0% of keys move, load on 4 nodes: max/avg 1.01, min/avg 0.99

The moved fraction is exactly the expected 20% and the distribution is almost perfect even without virtual nodes. The new node takes a key only if its own score is higher than the score of the key's current owner; nothing changes among the other nodes. The cost is the lookup: N hashes are computed for each key, O(N). For a few, or a few dozen, nodes this is no problem at all and the code is much simpler; with thousands of nodes or very frequent lookups the ring's O(log V) lookup pulls ahead.

Common Pitfalls

Using string.GetHashCode(). In .NET the string hash is computed with a random seed per process. Running the same program twice:

string.GetHashCode("book:42") in this process: -1390271829
XxHash3 of "book:42":                        1568342426
string.GetHashCode("book:42") in this process: 1265436331
XxHash3 of "book:42":                        1568342426

GetHashCode differs on every run, XxHash3 stays the same. In a three-instance application that builds the ring with GetHashCode, each instance sends the same key to a different node and the cache never hits. The hash used for distribution must be deterministic and platform-independent.

Changing the virtual node count later. The virtual node count is part of the ring too; raising it from 100 to 200 moves some keys just like adding a new node. Make sure every client uses the same node list and the same virtual node count.

Thinking consistent hashing moves the data. The algorithm only answers "where does this key live now". In a cache that is enough, the entry at the old location expires over time. In a database, copying the data of moved keys, handling writes that arrive during the copy and switching reads to the new node at the right moment is separate work.

Thinking it solves hot keys. Consistent hashing balances keys, not traffic. A single key taking all the campaign traffic still goes to a single node; the remedy is the L1 (level 1, in-process) cache and key replication from the caching post.

Clients seeing different node lists. One instance's list being updated and another's not means the same key living on two different nodes for a while; the node list must come from a single source (configuration or service discovery).

A Small Experiment

★☆☆ In the demo make the node count 10 instead of 4 and compare the fractions hash % N and the ring move when going from 10 to 11. Is the fraction you expect 1/11?

★★☆ Add weight support to ConsistentHashRing: Add(string node, int weight) should multiply the virtual node count by the weight. Give cache-e twice the weight, measure the load spread and pin it down with an xUnit test.

★★★ Add replication to the ring: GetNodes(string key, int replicas) should walk clockwise and return the first replicas distinct physical nodes (don't count two virtual nodes of the same node twice). Test that when a node is removed, at least one copy of every key stays where it was.

We have solved spreading keys across nodes. In the next post we look at another load problem: heavy work that does not need to happen inside the request. With a queue, workers, fan-out, backpressure and 202 Accepted we will move invoice PDF generation from the API (Application Programming Interface) to a worker.