Консистентное хеширование

Страницы сайта кэшируются на четырёх серверах. Какой сервер отвечает за страницу? Первое, что приходит в голову, — взять хеш адреса по модулю четырёх. Это работает, пока серверов четыре. Добавьте пятый: остаток по модулю пяти у почти всех адресов другой, и четыре пятых кэша мгновенно становятся бесполезными. Все запросы разом идут мимо кэша в базу, и база ложится. Ниже настоящие 8966 страниц legost.in. Добавьте сервер в обоих режимах и сравните.

При hash mod N сервер сменили 80,8 % страниц. На кольце — около двадцати процентов, ровно та доля, которую должен забрать пятый сервер. И переезжают только его ключи, ни одного лишнего: новый сервер начинает с пустым кэшем, всё, что ему достаётся, приходится отдать другим серверам, а остальные ключи не трогаются.

Идея

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

Кольцо — это просто числа от 0 до 2⁶⁴ − 1, закольцованные: за самым большим снова идёт ноль. Хеши серверов храним в отсортированном массиве, и поиск сервера для ключа — это двоичный поиск первой точки, большей хеша ключа. Если такой нет — берём самую первую: круг замкнулся.

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

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

Решение — поставить каждый сервер на кольцо много раз, в точки хешей имён «cache-1#0», «cache-1#1», … Это виртуальные узлы. Каждый сервер собирает много маленьких дуг, и их сумма гораздо ближе к средней. С сотней узлов нагрузка на наших страницах — от 1682 до 1848 при честной доле 1793. Заодно появляется удобная ручка: серверу вдвое мощнее можно дать вдвое больше виртуальных узлов.

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

Код

Кольцо — отсортированный список пар «хеш, сервер», поиск — bisect в Python и sort.Search в Go. Хеш — первые восемь байт MD5: криптостойкость здесь не нужна, нужно, чтобы хеш был одинаковым на всех машинах и во всех языках. Встроенный hash() Python для этого не годится — он меняется от запуска к запуску.

Обратите внимание на вторую строку: с одним виртуальным узлом переехало всего 8 % — меньше «положенных» 20 %. Это не выигрыш: просто пятый сервер встал на короткую дугу и получил мало ключей, а самый загруженный сервер держит 3519 страниц вместо 1793.

Сколько это стоит

Поиск сервера — двоичный поиск по N·v точкам: O(log(N·v)). Для десяти серверов по сто узлов это десять сравнений. Добавление или удаление сервера — пересортировка O(N·v log(N·v)), но это редкое событие. Память — те же N·v точек.

Главная оценка здесь не про время, а про переезды: при добавлении сервера к N существующим переезжает около 1/(N + 1) ключей против N/(N + 1) у остатка по модулю. Для четырёх серверов — 20 % против 80 %, для ста — 1 % против 99 %.

Что ещё бывает

• Рандеву-хеширование (наибольший случайный вес): для каждого ключа считаем хеш пары «ключ, сервер» для всех серверов и берём сервер с наибольшим. Никакого кольца и виртуальных узлов, нагрузка ровная, но поиск стоит O(N).
• Jump consistent hash (Ламппинг и Вич, Google, 2014): несколько строк арифметики, никакой памяти, идеально ровная нагрузка — но серверы нумеруются подряд, и убрать сервер из середины нельзя.
• Ограниченная нагрузка: если сервер переполнен, ключ идёт к следующему по кольцу. Так борются с «горячими» ключами, которые одни способны перегрузить сервер.

История

Консистентное хеширование придумали в 1997 году Дэвид Каргер, Том Лейтон, Дэниел Левин и их соавторы — для распределённых веб-кэшей, которые разгружали бы популярные сайты в часы пик. Через год Лейтон и Левин основали на этой идее компанию Akamai — одну из первых сетей доставки контента. Позже кольцо с виртуальными узлами стало основой хранилища Amazon Dynamo (статья 2007 года) и выросших из него баз данных вроде Cassandra.

Задачи

Реализуйте кольцо сами и посчитайте, сколько ключей переедет, когда к кластеру добавят новый сервер. Главная ловушка — ключи, которые «перешагнули» через ноль.