Консистентное хеширование — это алгоритм распределения данных по узлам (например, серверам или кешам), который минимизирует перераспределение ключей при добавлении или удалении узлов. Вместо классического хеширования, где изменение числа узлов приводит к перераспределению почти всех ключей, консистентное хеширование изменяет размещение только части ключей, что повышает устойчивость и масштабируемость системы.

Идея в том, что и узлы, и ключи отображаются на кольцо хеш-пространства (например, 0..2^32-1). Каждый ключ хранится на первом узле, который идет по часовой стрелке после позиции ключа на кольце.

Виртуальные шарды (виртуальные бакеты) — это способ улучшить балансировку нагрузки. Вместо того, чтобы каждый физический узел соответствовал одной точке на кольце, ему назначается множество виртуальных точек (виртуальных узлов). Это позволяет равномернее распределять ключи между узлами, особенно если узлы имеют разную мощность или при небольшом числе узлов.

Пример на C# (упрощённо):

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()]; // кольцо
    }
}

Что такое консистентное хеширование (consistent hashing)? Виртуальные шарды/бакеты?