SYS Системы и большие данные Алгоритм
Рандеву-хеширование
Также: Rendezvous hashing · HRW · highest random weight · наибольший случайный вес · CARP · взвешенное рандеву-хеширование · weighted rendezvous hashing
Ключ сам выбирает сервер: каждому серверу он даёт случайный вес — хеш пары «ключ, сервер», — и уходит к самому тяжёлому. Ни кольца, ни таблицы, а при отказе сервера его ключи расходятся по остальным поровну. На неделе адресов сервера NASA — восемь кэширующих прокси, отказ одного и веса для серверов разной мощности.
Перед веб-сервером стоят восемь кэширующих прокси, и каждый адрес должен попадать всегда в один и тот же: тогда страница лежит в кэше одного прокси, а не копируется восемь раз. Адреса — настоящие: 4258 страниц и картинок сервера Космического центра Кеннеди за неделю 10–16 июля 1995 года, 538 838 запросов к ним. Как раскладывать адреса, чтобы прокси были загружены поровну, а отказ одного не перетряхивал остальные? Отключите любой прокси и посмотрите, куда уйдут его адреса.
При рандеву-хешировании адреса делятся почти поровну: от 502 до 593 на прокси. Отключите P3 — его 537 адресов разойдутся по семи оставшимся, от 67 до 89 на каждый, а все остальные адреса останутся на месте. Переключитесь на кольцо с одной меткой на прокси: делёж и без отказов неровный — от 25 адресов до 1505, — а при отказе P3 все его 439 адресов достаются одному соседу. Сто меток на прокси выравнивают кольцо, но отказ всё равно раскладывает чужие адреса неровно: от 28 до 126. А «хеш по модулю восьми» делит идеально ровно, пока прокси восемь; когда их семь, меняют прокси 3725 адресов из 4258.
Идея
Для ключа k и каждого сервера s посчитаем вес — хеш пары, h(k, s), — и отдадим ключ серверу с наибольшим весом. Хеш ведёт себя как случайное число, поэтому выиграть может любой сервер с равной вероятностью. Веса пары не зависят от других серверов, поэтому, когда сервер исчезает, у остальных ключей победитель не меняется, а его ключи переходят к тем, кто был у них вторым.
Отсюда и название. Метод придумали для многоадресной маршрутизации: роутеры, которые ничего друг другу не сообщают, должны выбрать для группы одну и ту же точку встречи, точку рандеву. Каждый из них считает веса одних и тех же пар и приходит к одному и тому же ответу. Авторы назвали способ «наибольшим случайным весом», highest random weight, HRW.
Сравните с кольцом. Там ключ и сервер ставятся на одну окружность, и ключ достаётся ближайшему серверу по часовой стрелке. Чтобы доли были ровными, у каждого сервера сотня меток, и их надо хранить и сортировать. Рандеву не хранит ничего, кроме списка серверов, — зато для каждого ключа перебирает их все.
Пусть веса h(k, s) для разных пар — независимые случайные числа. Тогда (1) каждый из N серверов получает ключ с вероятностью 1/N; (2) когда сервер s исчезает, меняют сервер ровно те ключи, которые были у s, и каждый из них уходит к любому из оставшихся с вероятностью 1/(N − 1); (3) когда появляется новый сервер, к нему уходят ровно те ключи, для которых его вес больше всех, — в среднем 1/(N + 1) всех ключей.
(1) Веса ключа на N серверах — N независимых одинаково распределённых чисел; наибольшим может быть любое из них с одной и той же вероятностью. (2) Если ключ был не у s, его победитель тяжелее всех, в том числе после удаления s, — ничего не меняется. Если у s, новым победителем станет наибольший из оставшихся N − 1 весов, и по той же симметрии это любой из оставшихся серверов с равной вероятностью. (3) Новый сервер выигрывает ключ, только если его вес больше всех прежних; другие ключи остаются у своих победителей. Вероятность выиграть — 1/(N + 1) по пункту (1).
В опыте с прокси так и вышло: 537 адресов P3 разошлись по семи прокси с разбросом, какой даёт случайность, — от 67 до 89 при среднем 77. Хеш пары здесь — 64-битный FNV-1a ключа, сложенный побитовым XOR с FNV-1a имени прокси и перемешанный финализатором splitmix64. Перемешивать нужно именно сумму: перемешать ключ и сервер по отдельности и сложить потом — значит получить веса, у которых порядок серверов задаётся одной маской, и случайности не будет (на этом ловит первая задача).
Чего не исправит никакой хеш
По адресам рандеву делит почти идеально: самый загруженный прокси держит в 1,11 раза больше адресов, чем в среднем. А по запросам — в 1,43 раза. Причина в данных: один адрес, логотип NASA /images/NASA-logosmall.gif, собрал 7,0 % всех запросов недели — больше половины средней нагрузки прокси, а ещё пять маленьких логотипов — по 3–4,6 %. Любая схема, где у адреса один хозяин, отдаёт весь логотип одному прокси. Против горячих ключей помогает только копирование: держать самые популярные адреса на нескольких серверах сразу.
Пары реплик даром
Рандеву даёт для каждого ключа не только победителя, но и весь список серверов по убыванию веса. Первые два — естественная пара: основной сервер и запасной. Если основной отказал, ключ уже лежит на втором — и это тот же сервер, к которому ключ ушёл бы по пункту (2). Первая задача статьи — сколько новых ключей получит каждый сервер, когда один из пары отключается. На адресах NASA ключи отключённого proxy-3 расходятся по семи остальным почти поровну. Так устроен балансировщик GLB в GitHub: порядок рандеву заполняет таблицу, где у каждой строки есть основной и запасной сервер, и при выводе сервера из работы соединения спокойно доживают на втором.
Серверы разной мощности
Что, если прокси P7 и P8 вчетверо мощнее первых четырёх, а P5 и P6 — вдвое? Хочется, чтобы доли адресов были пропорциональны мощности: 1/16, …, 2/16, …, 4/16. Первая мысль — умножить вес на мощность. Она неверна, и сильно.
На адресах NASA при весе w · u прокси мощности 4 получили по 43 % адресов вместо 25 %, а мощности 1 — по 0,1–0,3 % вместо 6,25 %. Точные доли для любых мощностей — вторая задача статьи, и их можно посчитать за O(N log N). Сильный сервер выигрывает всякий раз, когда выбросил больше, чем могут слабые вообще, и это перекашивает доли тем сильнее, чем больше серверов.
Пусть us — независимые случайные числа, равномерные на (0, 1), а сервер s получает вес −ws / ln us. Тогда ключ достаётся серверу s с вероятностью ws / (w1 + … + wN).
Наибольший вес −w/ln u — то же, что наименьшее Xs = −ln us / ws. Величина Xs распределена показательно с параметром ws: P(Xs > t) = P(us < e−wst) = e−wst. Сервер s выигрывает, если его Xs = t, а все остальные больше t:
$$P = \int_0^\infty w_s e^{-w_s t} \prod_{j \ne s} e^{-w_j t}\,dt = w_s \int_0^\infty e^{-W t}\,dt = \frac{w_s}{W},\qquad W = \sum_j w_j.$$Пункты (2) и (3) первого утверждения сохраняются: веса пар по-прежнему не зависят от других серверов. Логарифмический метод описали Кристиан Шиндельхауэр и Гуннар Шомакер в 2005 году. Тот же приём стоит в Ceph: способ размещения straw2 в CRUSH берёт логарифм 16-битного хеша и делит его на вес устройства. На адресах NASA он дал доли от 5,6 % до 6,6 % у мощности 1 и около 25,6 % у мощности 4 — в пределах случайного разброса на четырёх тысячах адресов.
Код
Рандеву, кольцо с одной и со ста метками и хеш по модулю — на неделе адресов NASA: делёж адресов и запросов, отказ proxy-3 и куда ушли его адреса, доли при мощностях 1, 1, 1, 1, 2, 2, 4, 4.
Сколько это стоит
| Способ | Поиск сервера | Память | Отказ сервера |
|---|---|---|---|
| hash mod N | O(1) | — | переезжает почти всё: 3725 из 4258 |
| кольцо, v меток | O(log(N·v)) | N·v меток | только ключи упавшего, раздел зависит от v |
| рандеву | O(N) | список серверов | только ключи упавшего, поровну на всех |
Перебор всех серверов на каждый ключ — главная цена рандеву. Для восьми прокси это восемь хешей, меньше микросекунды; для сотни серверов — тоже немного. Если серверов тысячи, их собирают в дерево: рандеву выбирает группу, внутри неё — подгруппу и так далее, и ключ проходит O(log N) уровней. Другой путь — как в GLB: один раз заполнить рандеву-порядком таблицу постоянного размера и дальше искать сервер по номеру строки — хешу соединения — за O(1).
История
Дэвид Талер и Чиня Равишанкар описали «наибольший случайный вес» в техническом отчёте 1996 года о выборе точки встречи, а в 1998 году — в журнальной статье о том, как раскладывать запросы к кэширующим серверам по именам объектов, чтобы одинаковые запросы попадали на один сервер. В том же году на нём был построен протокол массивов кэширующих прокси CARP, а в протоколах многоадресной маршрутизации PIM им выбирают точки рандеву. Консистентное хеширование с кольцом появилось почти одновременно, в 1997 году, и решает ту же задачу другим способом; рандеву проще, кольцо быстрее на большом числе серверов.
Задачи
Первая — пары реплик по рандеву и что с ними происходит при отказе. Вторая — точные доли при наивном умножении веса на мощность.
Пары реплик Наивные весаДанные: Журнал веб-сервера Космического центра Кеннеди, 10–16 июля 1995: NASA-HTTP, Internet Traffic Archive, свободно распространяется