What is consistent hashing? Virtual shards/buckets?

Consistent hashing is a data distribution algorithm across nodes (such as servers or caches) that minimizes key redistribution when nodes are added or removed. Instead of traditional hashing, where changing the number of nodes results in almost all keys being redistributed, consistent hashing only changes the placement of some keys, increasing system robustness and scalability.

The idea is that both nodes and keys are mapped onto a hash ring (for example, 0..2^32-1). Each key is stored on the first node clockwise after the key's position on the ring.

Virtual shards (virtual buckets) are a way to improve load balancing. Instead of each physical node corresponding to a single point on the ring, it is assigned multiple virtual points (virtual nodes). This allows for a more even distribution of keys among nodes, especially if nodes have different capacities or if the number of nodes is small.

Example in C# (simplified):

class ConsistentHashRing
{
    SortedDictionary<int, string> ring = new SortedDictionary<int, string>();
    int virtualNodes = 100;

    int Hash(string key) => key.GetHashCode();

    public void AddNode(string node)
    {
        for (int i = 0; i < virtualNodes; i++)
        {
            int hash = Hash(node + i);
            ring[hash] = node;
        }
    }

    public string GetNode(string key)
    {
        int hash = Hash(key);
        foreach (var nodeHash in ring.Keys)
        {
            if (nodeHash >= hash)
                return ring[nodeHash];
        }
        return ring[ring.Keys.First()]; // ring
    }
}