Как положить сервер на разборе параметров?

Есть одна оговорка про хеш-таблицы, которую все выдают на собеседовании, но забывают при разработке.

Поиск и вставка работают за O(1). В среднем.

Это «в среднем» многое меняет, если ключи в таблицу присылает тот, кто хочет положить сервис.

Можно специально подобрать их так, чтобы сервер тратил всё больше времени на каждую последующую вставку. Эта атака называется hash flooding. И начинается она с обычной коллизии.

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

Возьмём простую реализацию с цепочками. Перед вставкой проходим по цепочке и проверяем, нет ли там такого ключа. Если ключи распределились равномерно, проверять почти нечего.

Теперь возьмём учебную хеш-функцию:

И передадим ей ключи:

Все попадут в одну корзину. Остальные 1023 могут стоять пустыми. Таблица почти пустая, а поиск уже тормозит.

При вставке второго ключа придётся проверить первый. При вставке третьего — два предыдущих. Для десятитысячного нужно пройти уже 9999 элементов.

Суммарно получится почти 50 миллионов сравнений на 10 тысяч ключей. В этой реализации обработка набора вырастает до O(n²).

Если в такую таблицу складываются параметры HTTP-запроса, сервер потратит ресурсы ещё до вызова бизнес-логики. До базы даже не дошли, а CPU уже занят.

С % 1024 всё выглядит слишком просто. Но для атаки достаточно уметь подбирать коллизии и у более сложной функции.

Получается неприятная история: запросов немного, а работы от них столько, что сервер перестаёт справляться. Ограничение RPS само по себе здесь не спасает. Оно считает запросы, но ничего не говорит о стоимости их обработки.

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

Например, у каждой map в Go map в Go свой seed. Хотя сама Go map устроена иначе, чем таблица с цепочками из нашего примера.

И всё равно нужны лимиты на размер тела запроса и количество параметров. Рандомизация хеширования не отменяет ограниченность ресурсов сервера.

За словами «в среднем за O(1)» стоят условия. Например, что ключи достаточно равномерно распределяются по корзинам.

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