Консистентное хеширование: Математика распределенных баз данных
Когда веб-сервис вырастает до миллионов пользователей, одна база данных или один кэш-сервер (например, Memcached) перестает справляться с нагрузкой. Данные нужно шардировать — распределить по десяткам серверов. Как алгоритмически определить, на какой именно сервер положить фотографию пользователя? Стандартный подход с остатком от деления ломается при изменении архитектуры. Эту проблему в 1997 году решило консистентное хеширование (Consistent Hashing).
Стандартный наивный подход распределения данных выглядит так: мы берем ID пользователя, вычисляем от него хеш и берем остаток от деления на количество серверов (N). То есть server_index = hash(ID) % N. Все работает идеально, ключи распределяются равномерно. Но что произойдет, если один сервер выйдет из строя, и N станет равно N-1? Формула изменится для всех ключей! Почти 99% данных вдруг окажутся "не на своих" серверах, что вызовет лавинообразный шквал промахов кэша и падение всей системы (Cache Stampede).
Консистентное хеширование использует изящную геометрическую модель — Хеш-кольцо (Hash Ring). Представьте себе числовую ось от 0 до максимального значения хеша (например, 2^256 - 1), свернутую в замкнутую окружность.
Алгоритм работает в три этапа:
- Хешируются IP-адреса (или имена) самих кэш-серверов. Полученные значения определяют их фиксированные позиции на этом кольце.
- Когда нужно сохранить или найти данные (например, ключ "user_123"), алгоритм хеширует этот ключ и находит его точку на кольце.
- Правило маршрутизации: от точки ключа алгоритм движется по кольцу по часовой стрелке, пока не встретит первый сервер. Именно на этом сервере и будут храниться данные.
Магическое свойство этой структуры: если добавить новый сервер или удалить старый, перераспределение затронет только соседний сегмент кольца. В среднем переместится всего 1/N часть всех данных, а не 99%, как в классической схеме. Остальная сеть даже не заметит изменения топологии.
Для решения проблемы неравномерного распределения (когда серверы случайно "скучиваются" на одной стороне кольца) применяются Виртуальные узлы (vNodes). Один физический сервер хешируется сотни раз с разными суффиксами и занимает множество равномерно разбросанных точек на кольце. Сегодня консистентное хеширование является сердцем Amazon DynamoDB, Apache Cassandra, распределенных сетей доставки контента (CDN) и балансировщиков нагрузки.
