В Elixir для распределённых систем часто используют консистентное хеширование — например, чтобы сделать распределённый rate limiter или кэш. Самый популярный инструмент для этого — библиотека ExHashRing от Discord. Она надёжная, проверенная боем и очень быстрая. Но у неё есть недостаток: нужно запускать и управлять процессами кольца. Это stateful-сущности, которые висят в supervision tree, их состояние надо поддерживать.
Альтернатива — rendezvous hashing (он же HRW, Highest Random Weight). Вместо кольца с процессами — чистая функция. Передаёшь ключ и список узлов, получаешь владельца. Никакого состояния. Автор приводит пример: ExHashRing.Ring.find_node(ring, "key1") vs HRW.owner("key1", ["a", "b", "c"]) — оба возвращают "b".
Проблема HRW — линейная сложность O(n). На 14 узлах разница с ExHashRing почти незаметна: 418 ns против 375 ns. Но на 10 000 узлах HRW.owner проседает в 4200 раз — до 2.2 ms. Впрочем, для многих сценариев 2 ms — это нормально.
Можно ускорить HRW через структуру skeleton. По описанию с Wikipedia: узлы сортируются, разбиваются на кластеры, и вместо хеширования со всеми узлами считается только адрес кластера. Сложность падает до O(log n). На 10К узлах HRW.owner(skeleton) работает за 1.41 µs — всего в 3 раза медленнее ExHashRing, без NIFов и stateful-процессов. Плата — нестабильность при добавлении/удалении узлов.
Отдельно автор сравнивает распределение ключей. Обычный ExHashRing с дефолтными настройками на 1000 узлов выдаёт стандартное отклонение 31.4% от среднего, причём некоторые узлы получают 0 ключей. HRW с :erlang.phash2 даёт всего 9.9%. Murmur3 чуть лучше на малых кластеризациях, но не критично.
Автор выпустил библиотеку hrw на hex.pm. Для больших кластеров рекомендует ExHashRing или HRW.Skeleton. В библиотеке есть и дополнительные стратегии: HRW.Weighted для гетерогенных кластеров и HRW.Bounded для точного распределения, если ключи известны заранее.