Согласованное хеширование

Готовясь к собеседованиям по System Design, вы наверняка встречали согласованное хеширование. Это фундаментальный алгоритм в распределенных системах, который используется для распределения данных по кластеру серверов.

В этой статье мы дадим максимально сфокусированный обзор согласованного хеширования: какую проблему оно решает, как работает и как вы можете использовать его на интервью.

Согласованное хеширование на примере

Представьте, что вы проектируете систему бронирования билетов вроде Ticketmaster. Изначально система простая:

• Одна база данных хранит все данные о событиях
• Пользователи отправляют запросы, чтобы получить информацию о событиях
• В начале все работает гладко

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

Вопрос, на который нужно ответить: как понять, какие события хранить в каком экземпляре базы данных?

Первая попытка: простое хеширование по модулю

Самый прямолинейный подход для распределения данных по нескольким базам - хеширование по модулю.

1. Сначала мы берем ID события и пропускаем его через хеш-функцию, которая превращает его в число.
2. Затем мы берем это число по модулю (%) количества баз данных.
3. Результат говорит, в какой базе должно храниться событие.

В коде это выглядит так:

database_id = hash(event_id) % number_of_databases;

Конкретный пример для 3 баз данных:

// примем названия баз, начиная с 1
// результат деления по модулю 3: {0, 1, 2}
// соответствует Базам 1, 2, 3
Событие #1234 -> hash(1234) % 3 = 1 -> База 2
Событие #5678 -> hash(5678) % 3 = 0 -> База 1
Событие #9012 -> hash(9012) % 3 = 2 -> База 3

Отлично! Это работает, пока вы не столкнетесь с несколькими проблемами.

Первая проблема появляется, когда вы хотите добавить четвертый экземпляр базы данных. Можно наивно подумать, что все, что нужно сделать - заменить в операции деления по модулю 3 на 4:

database_id = hash(event_id) % 4;

Вы меняете код и развертываете его в продакшене, и затем активность баз данных взлетает до небес! И не только на четвертой базе - на всех.

Оказывается, что изменение хеш-функции повлияло не только на данные, которые должны попасть на новый экземпляр, но и на то, в какой экземпляр базы попадает почти каждое событие.

Например, событие #1234 раньше отображалось на базу 1, а теперь hash(1234) % 4 = 0, поэтому эти данные нужно перенести в базу 0.

Это значит, что данные должны быть перемещены из базы 1 в базу 0. И это не единичный случай - большую часть данных нужно перераспределить по всем экземплярам! Это вызывает резкие всплески нагрузки на базу и означает, что пользователи либо не могут получить доступ к данным, либо сталкиваются с большими задержками.

Посмотрим на другую проблему простого хеширования по модулю.

Представьте, что база отказала. Это могло случиться из-за чего угодно: аппаратной поломки, бага в ПО и т.д. В любом случае нам нужно убрать ее из нашего пула экземпляров баз и перераспределить данные по оставшимся экземплярам, пока мы не поднимем новый.

Наша хеш-функция меняется с database_id = hash(event_id) % 3 на database_id = hash(event_id) % 2, и мы сталкиваемся с той же проблемой перераспределения, что и раньше.

Очевидно, простое хеширование по модулю не справляется. За дело берется согласованное хеширование.

Согласованное хеширование

Согласованное хеширование - это техника, которая решает проблему перераспределения данных при добавлении или удалении экземпляра в распределенной системе. Ключевая идея - расположить и наши данные, и наши экземпляры базы данных в круговом пространстве, которое часто называют "хеш-кольцом" (hash ring).

Вот как это работает:

1. Сначала мы создаем хеш-кольцо с фиксированным количеством точек. Для простоты пусть это будет 100.
2. Затем мы равномерно распределяем наши базы данных по хеш-кольцу. Если у нас 4 базы, мы можем поставить их в точки 0, 25, 50 и 75.
3. Чтобы понять, в какой базе хранить событие, мы хешируем ID события как раньше, а затем просто находим значение хеша на кольце и двигаемся по часовой стрелке, пока не встретим ближайший экземпляр базы.

Как это решило проблему? Посмотрим, что происходит, когда мы добавляем или удаляем базу данных.

Добавление базы (база #5)
Предположим, мы добавляем пятую базу в позицию 90 на нашем кольце. Теперь:

• Переместить нужно только события, которые хешируются в диапазоне между 75 и 90
• Раньше эти события отправлялись в базу #1 (в позиции 0)
• Все остальные события остаются ровно там, где были

Если раньше почти все данные нужно было перераспределить, то с согласованным хешированием мы перемещаем только около 60% событий, которые были в базе #1, или примерно 15% всех событий.

Удаление базы
Аналогично, если база #2 (в позиции 25) отказывает:

• Переместить нужно только события, которые были привязаны к базе #2
• Теперь эти события будут отображаться на базу #3 (в позиции 50)
• Все остальное остается на месте

Виртуальные узлы

Мы хорошо продвинулись, но остается одна проблема. В примере выше, где мы удалили базу #2, нам пришлось переместить все события, которые хранились в базе #2, в базу #3. Теперь база #3 имеет нагрузку в 2 раза больше, чем база #1 и база #4. Нам бы хотелось распределить нагрузку более равномерно, чтобы база #3 не оказалась перегруженной.

Решение - использовать так называемые "виртуальные узлы" (virtual nodes). Вместо того чтобы размещать каждую базу ровно в одной точке кольца, мы размещаем ее в нескольких точках, хешируя разные варианты имени базы.

Например, вместо того чтобы просто хешировать "DB1" и получить позицию 0, мы хешируем "DB1-vn1", "DB1-vn2", "DB1-vn3" и т.д., что может дать позиции 20, 35, 65 и так далее. Мы делаем это для каждой базы, и в результате виртуальные узлы естественным образом перемешиваются по кольцу.

Теперь, когда база #2 падает:

• События, которые были привязаны к "DB2-vn1", перераспределятся в базу #1
• События, которые были привязаны к "DB2-vn2", переместятся в базу #3
• События, которые были привязаны к "DB2-vn3", переместятся в базу #4
• И так далее

Это означает, что нагрузка от отказавшей базы распределяется гораздо более равномерно по всем оставшимся базам, вместо того чтобы перегружать одного соседа. Чем больше виртуальных узлов вы используете для каждой базы, тем более ровным становится распределение нагрузки.

Согласованное хеширование в реальном мире

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

Мы видим согласованное хеширование во многих крупных, широко используемых системах. Например:

1. Apache Cassandra: использует согласованное хеширование для распределения данных по кольцу
2. Amazon DynamoDB: использует под капотом согласованное хеширование
3. CDN (Content Delivery Networks): используют согласованное хеширование, чтобы определить, какой edge-сервер будет кэшировать конкретный контент

Когда использовать согласованное хеширование на интервью

Большинство современных распределенных систем берут на себя шардирование и распределение данных. Когда вы проектируете систему используя DynamoDB, Cassandra и т.п., обычно достаточно просто упомянуть, что такие системы используют согласованное хеширование (или его вариант) внутри себя при масштабировании.

Однако согласованное хеширование становится важной темой в инфраструктурных интервью, где вас просят проектировать распределенные системы "с нуля". Вот несколько распространенных задач:

1. Спроектировать распределенную базу данных
2. Спроектировать распределенный кэш
3. Спроектировать распределенный брокер сообщений

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

Ключевой навык - понимать, когда нужно углубиться в обсуждение деталей, а когда достаточно просто отметить, что существующие решения уже берут на себя эту сложность. Большинство интервью по System Design относится ко второй категории!

Заключение

Согласованное хеширование - один из тех алгоритмов, которые произвели революцию в распределенных системах, решив на первый взгляд простую проблему: как распределять данные по серверам и при этом минимизировать перераспределение, когда число серверов меняется.

Хотя детали реализации могут быть сложными, базовая идея удивительно проста: расположить все по окружности и идти по часовой стрелке. Это элегантное решение сейчас встроено во многие распределенные системы, которыми мы пользуемся ежедневно.

На следующем собеседовании по System Design, помните: обычно вам не нужно реализовывать согласованное хеширование самостоятельно. Просто понимайте, когда оно используется "под капотом", а в детали уходите только в инфраструктурных задачах, где это действительно важно.