CS
Задачник Базовый курс EN

Задача

Пары реплик

хеширование балансировка репликация распределённые системы в проде

Каждый ключ хранится на двух серверах — тех двух, у которых рандеву-вес этого ключа наибольший. Вес считается так. Для строки s её хеш FNV-1a — 64-битное число: начинаем с 0xCBF29CE484222325 и для каждого байта c строки делаем h ← (h XOR c) · 0x100000001B3 по модулю 264. Перемешивание mix(z): z ← (z XOR (z >> 30)) · 0xBF58476D1CE4E5B9, затем z ← (z XOR (z >> 27)) · 0x94D049BB133111EB, затем z ← z XOR (z >> 31), всё по модулю 264. Вес ключа k на сервере s — mix(FNV(k) XOR FNV(s)), имена берутся как байты.

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

Вход

В первой строке — число серверов n и число ключей m (3 ≤ n ≤ 30, 1 ≤ m ≤ 30 000). Дальше n строк — имена серверов, различные, затем m строк — ключи, затем имя отключившегося сервера. Имена и ключи — непустые строки из видимых символов ASCII без пробелов, длиной до 100.

Выход

В первой строке — n чисел: во скольких парах состоит каждый сервер, в порядке входа. Во второй — n − 1 чисел: сколько новых ключей получит каждый из оставшихся серверов, в том же порядке.

Во втором примере сервер c состоял в четырёх парах, и после его отключения эти четыре ключа переходят к a (один) и к b (три): у каждого из них новым напарником становится третий по весу сервер.

Примеры

Пример 1

Вход
4 5
alpha
beta
gamma
delta
/
/index.html
/images/logo.gif
/news
/shuttle
beta
Выход
2 2 3 3
0 0 2

Пример 2

Вход
3 4
a
b
c
x
y
z
xyz
c
Выход
3 1 4
1 3

Ограничения

Время · Python
8000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Когда сервер отключается, порядок весов остальных серверов для ключа не меняется: их веса от него не зависят. Чья пара после этого может измениться — и на кого?

2Идея

Пара ключа — первые два сервера в его списке по убыванию весов. Если отключившийся сервер в эту пару не входил, первые два места остались за теми же серверами, и пара не меняется. Если входил — его место занимает третий по весу. Значит, для каждого ключа достаточно найти три самых тяжёлых сервера, и «перепрыгивать» отключение не нужно: ответ на второй вопрос — сколько раз каждый сервер оказывался третьим у ключей, где отключившийся был в первой двойке.

3Разбор

Посчитайте FNV каждого сервера один раз. Для ключа — его FNV, потом вес на каждом сервере и три наибольших: при n ≤ 30 хватает одного прохода с тремя ячейками. Первые два сервера получают по паре; если среди них отключившийся, третий получает новый ключ.

Арифметика по модулю 264: в Go это обычный uint64, где умножение само переполняется как надо, в Python — маска & (2**64 − 1) после каждого умножения. На адресах NASA с восемью прокси отключённый proxy-3 был в 1068 парах, и его ключи разошлись по семи остальным почти поровну — от 141 до 162 у каждого.

3+Решение
4Сложность

O(n · (m + длина ключей)): вес каждого ключа на каждом сервере считается один раз.

5Типичные ошибки
  • Перемешать по отдельности. mix(FNV(k)) XOR mix(FNV(s)) — не то же, что mix(FNV(k) XOR FNV(s)): у такого «веса» порядок серверов для ключа задаётся одной маской, наложенной на одни и те же числа серверов, и пары выходят другими. Первый пример это ловит.
  • Пересчитать пары заново без отключённого сервера и сравнить. Верно, но вдвое дольше — и мимо главного: менять нечего, кроме пар с отключившимся сервером.
  • Байты имён. Хеш считается по байтам строки, без перевода строки в конце.

Алгоритмы задачи

SYS Алгоритм Рандеву-хеширование Каждый ключ уходит к серверу с наибольшим хешем пары «ключ, сервер»: равномерно, без таблиц, отказ сдвигает только ключи упавшего. O(N) на ключ 2 задачи SYS Алгоритм Консистентное хеширование Распределяет ключи по серверам так, что при добавлении сервера переезжает лишь его доля. O(log(N·v)) на поиск сервера 1 задача
Каталог алгоритмов