zharkevich.ru
Хеш-таблицы: структура данных, которая изменила программирование

Хеш-таблицы: структура данных, которая изменила программирование

· 11 мин чтения

Представьте файл на восемь мегабайт. Внутри — одна очень длинная строка: aa=1&bb=2&cc=3&… и так несколько сотен тысяч раз. Ничего особенного — обычное тело POST-запроса, какие веб-сервер разбирает тысячами в секунду. Кроме одной детали: имена параметров подобраны с точностью криптоаналитика так, чтобы все до единого давали одинаковый хеш.

Отправьте этот файл на сервер PHP образца 2011 года — и получите сервер, занятый примерно на час. Один запрос. Один процессор. Сто процентов загрузки. Замените PHP на Java, Python, Ruby, ASP.NET или Node.js — ничего не изменится: та же сотка, тот же час. Мегабитный канал превращается в инструмент, способный положить целый кластер, — без ботнета, без уязвимости в приложении, без флуда. Просто очень тщательно сделанная форма.

Ровно это и демонстрировали Александр Клинк и Юлиан Велде 28 декабря 2011 года на конференции 28C3 — в докладе с невинным названием «Эффективный отказ в обслуживании веб-платформ». К следующему утру появились первые записи CVE: CVE-2011-4885 — PHP, CVE-2011-4858 — Tomcat, и дальше — целая серия для остальных. Неделю новостных лент спустя отрасль уже переписывала реализации хеш-таблиц.

Хуже всего было то, что атаку предсказали восемь лет назад — и все пропустили предсказание.

Предсказание, которое никто не услышал

В 2003 году двое исследователей из Университета Райса, Скотт Кросби и Дэн Уоллач, опубликовали статью с сухим академическим названием — «Denial of Service via Algorithmic Complexity Attacks». В переводе: «Отказ в обслуживании через атаки на вычислительную сложность».

Кросби и Уоллач описали сценарий с хирургической точностью: если протокол принимает пользовательские данные в хеш-таблицу, а хеш-функция предсказуема, атакующий может заранее вычислить ключи-коллизии. Таблица, которая должна работать за миллисекунды, деградирует до связного списка. В статье авторы показали, как с помощью этой техники можно положить Perl, Python-веб-приложения и сетевое устройство Snort.

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

Понадобилось восемь лет и одна публичная демонстрация на 28C3, чтобы все языки программирования массово начали переписывать реализации своих хеш-таблиц.

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

От картотеки к массиву: как всё начиналось

Январь 1953 года. Ханс Петер Лун, инженер IBM, трудится над задачей, которая сегодня кажется смешной: нужно быстро найти карточку в картотеке из тысяч записей. Компьютеры тогда занимали комнаты, а «память» измерялась не в гигабайтах, а в магнитных барабанах.

Лун рассуждает как инженер. Если у нас есть полка на сто ячеек, и мы кладём каждую карточку наугад, поиск в среднем потребует просмотра половины полки. Но что если от самой карточки вычислить число, а потом положить её в ячейку с этим номером? Тогда и искать можно в одно действие: вычислить число от запроса и сразу прыгнуть к ячейке.

Это и был прообраз хеш-таблицы. Внутренний документ IBM, в котором Лун её описал, никогда не публиковался в открытом доступе. Мир узнал о приёме позже, из работы Арнольда Думи, Джина Амдала и других. Но первым был именно Лун.

Смысл приёма простой до неприличия:

  1. Есть массив, скажем, на 16 ячеек.
  2. От ключа («Иванов», 42, адрес страницы) вычисляем хеш — число, которое должно равномерно размазывать разные ключи по всему диапазону.
  3. Берём остаток от деления хеша на 16, получаем индекс ячейки.
  4. Кладём туда значение.

Поиск работает так же: вычислил хеш, взял остаток, прыгнул в ячейку. Одно действие. То самое O(1), за которое хеш-таблицу любят все.

Когда два ключа хотят в одну ячейку

А теперь представьте: у нас 16 ячеек, а ключей мы вставляем двадцать. По принципу Дирихле хотя бы двум ключам обязательно достанется один и тот же индекс. Это называется коллизией, и с ней надо что-то делать.

Есть два принципиально разных подхода.

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

Открытая адресация. Ячейка занята — идём к следующей. Этот подход похож на парковку у торгового центра: если твоё место занято, ищешь ближайшее свободное. Данные лежат подряд, процессор доволен. Но удаление превращается в головоломку: если просто очистить ячейку, поиск сломается. Он остановится на «дырке», не дойдя до нужного ключа. Приходится помечать ячейки как «удалённые, но не пустые».

Оба подхода работают идеально в среднем. Проблема начинается, когда кто-то специально подбирает ключи, которые сталкиваются.

Когда O(1) превращается в O(n)

Вернёмся к докладу на 28C3. Вся красота атаки именно в этом превращении.

Пусть атакующий знает: веб-сервер парсит параметры запроса foo=1&bar=2&baz=3 в хеш-таблицу, а хеш-функция — детерминированная и известная (в 2011 году всё это было открыто задокументировано). Тогда он заранее, на своём ноутбуке, подбирает тысячу имён параметров, которые все хешируются в одно и то же число.

Сервер получает безобидный на вид POST-запрос. Начинает вставлять параметры. Первый — O(1). Второй — O(1), но таблица уже знает: в этой ячейке коллизия, надо сравнивать. Третий — уже сравнивается с двумя. К тысячному параметру каждая вставка — это обход тысячи коллизий. Суммарно — O(n²), где n — количество параметров.

На демонстрации Клинк и Велде показали: POST-запрос в 8 МБ занимал сервер на PHP примерно на час. Один запрос. Один мегабитный канал — и можно положить целый кластер. Ни флуда, ни ботнета, ни уязвимости в приложении. Просто очень тщательно составленный запрос.

Ответ: SipHash и секретный ключ

Инженерное сообщество отреагировало быстро и в три голоса.

Во-первых — лимиты. PHP добавил директиву max_input_vars. Tomcat, Jetty и другие серверы приложений ввели аналогичные ограничения. Это костыль, но рабочий: атакующий не может отправить миллион параметров, если сервер принимает максимум тысячу.

Во-вторых — рандомизация. Если хеш-функция зависит от секретного числа, которое выбирается при запуске программы, предсказать коллизии заранее невозможно. Атакующий больше не может на своём ноутбуке подобрать «ядовитые» ключи. Для этого ему нужно как-то добыть сам секрет из работающего сервера.

В-третьих — криптография. В 2012 году Жан-Филипп Омассон и Даниэль Бернштейн опубликовали SipHash — хеш-функцию, специально спроектированную для защиты хеш-таблиц. Это не классическая криптографическая функция вроде SHA-256. Для хеширования паролей она не годится. Но у неё есть ключевое свойство: без знания секретного ключа подобрать коллизии математически невозможно (точнее, эквивалентно взлому стойкого шифра).

SipHash стал стандартом де-факто. Python перешёл на него в версии 3.4. Ruby, Perl, Rust, Haskell — все последовали примеру. Это редкий случай, когда академическая статья за несколько лет стала промышленным стандартом.

Робин Гуд против богачей

Пока одни исследователи разбирались с безопасностью, другие воевали за скорость.

В 1986 году канадский аспирант Педро Селис защитил диссертацию с задорным названием Robin Hood Hashing — «Хеширование Робин Гуда». Идея простая и очень красивая.

Когда мы вставляем ключ при открытой адресации и натыкаемся на занятую ячейку, мы идём дальше. Каждый такой шаг — это «бедность»: чем дальше элемент от своей идеальной позиции, тем больше он страдает при каждом поиске. Обычная открытая адресация несправедлива: «богачи» (те, кто попал на своё место с первого раза) живут спокойно, а «бедняки» обречены на длинные поиски.

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

Результат выглядит скромно, но на деле впечатляет. В обычной открытой адресации при заполнении 90 % дисперсия длины поиска — 16,2 шага. В варианте Робин Гуда — 0,98 шага. То есть поиски становятся не просто быстрыми в среднем, а одинаково быстрыми. Хуже почти никому не будет.

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

Swiss Tables: как 16 сравнений стали одним

В 2017 году на конференции CppCon инженер Google Мэтт Кулукундис вышел на сцену с докладом «Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step». За 45 минут он рассказал, как команда Google — сам Кулукундис, Сэм Бензакен, Алкис Эвлогименос и Роман Перепелица — переписала хеш-таблицу для внутренних сервисов компании. Результат назвали Swiss Table (по аналогии со швейцарским сыром: много аккуратных «дырок» — свободных ячеек).

Ключ к скорости — инструкции SIMD (Single Instruction, Multiple Data, «одна инструкция на много данных»). Идея такая:

  1. Хеш ключа делится на две части: длинную (57 бит) и короткую (7 бит). Длинная часть определяет, в какой группе из 16 ячеек искать. Короткая — «отпечаток», который хранится отдельно, в массиве метаданных по одному байту на ячейку.
  2. При поиске процессор одной инструкцией загружает 16 байт метаданных в 128-битный регистр. Ещё одной инструкцией (_mm_cmpeq_epi8) сравнивает отпечаток искомого ключа сразу со всеми 16 ячейками. Результат сравнения — битовая маска: где совпало, там и смотрим реальный ключ.

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

История на этом не кончается. Когда Swiss Table открыли как часть библиотеки Abseil в 2018 году, другие языки потянулись следом. Rust в 2019-м заменил Робин Гуда на библиотеку hashbrown — порт Swiss Table. Go в версии 1.24 (февраль 2025) выбросил свою схему с цепочками по 8 элементов и переехал на Swiss Table — карты стали до 60 % быстрее на типичных операциях.

Go и сознательный хаос: история рандомизации

Из всей этой саги особняком стоит решение, принятое командой Go ещё в 2012 году, и это одна из лучших историй о том, как проектировать язык.

До Go 1.0 порядок обхода map через range был детерминированным. Ну, или почти — он зависел от деталей реализации. Программисты быстро это обнаружили и начали писать код, зависящий от порядка: тесты, которые сравнивали сериализованные строки, кеши, где порядок влиял на результат, логи, где хотелось «одинакового вывода».

Команда Go поняла: если оставить как есть, любое будущее изменение внутренней реализации сломает чужой код. И приняла смелое решение — специально внести случайность. При каждом вызове range стартовая ячейка выбирается случайно через быстрый генератор fastrand(). Два цикла range подряд по одной и той же карте дадут разный порядок.

Это не защита от атак. Это защита от себя — от программистов, которые случайно (или специально) начнут зависеть от порядка и превратят деталь реализации в часть контракта. Когда в Go 1.24 заменили всю реализацию хеш-таблицы целиком, ни одна программа не сломалась, потому что зависеть было не от чего.

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

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

Хеш-таблицы в четырёх языках

Rust. Стандартный HashMap — это библиотека hashbrown, порт Swiss Table, с хеш-функцией SipHash-1-3. Каждый запуск программы выбирает новый секретный ключ. Попытка отсортировать содержимое карты по ключам требует явного сбора в Vec — HashMap принципиально не реализует упорядоченность.

Go. После 1.24 — Swiss Table. Хеш-функция из пакета hash/maphash получает собственный секретный ключ при каждом создании карты. Сравнить две карты через == компилятор не даст.

Zig. Есть StringHashMap для строковых ключей и AutoHashMap для типов, у которых хеш можно вывести автоматически. Аллокатор передаётся явно. Можно использовать арену для временных таблиц, что в «больших» языках недоступно. По умолчанию используется Wyhash — быстрая, но некриптографическая функция. Встроенной рандомизации секретного ключа нет. Это решение пользователь принимает сам.

Nim. В стандартной библиотеке имеется модуль std/tables с типами Table[K, V] (неупорядоченная) и OrderedTable[K, V] (сохраняет порядок вставки; в Go и Rust отдельного типа нет — его пришлось бы собирать руками). Хеш-функция берётся из std/hashes, стандартная реализация для строк детерминирована между запусками. Рандомизация секретного ключа — задача разработчика: либо подмешивать собственный seed, либо подключать сторонний SipHash.

Примеры кода:

История повторяется: свежие уязвимости

Мы говорим о 2011 годе как о далёком прошлом, но класс уязвимостей никуда не делся. Стоит разработчику забыть о рандомизации, как проблема возвращается:

  • CVE-2024-21538 в пакете cross-spawn — предсказуемый разбор путей приводит к квадратичному времени;
  • CVE-2024-4067 в micromatch — коллизии в разборе шаблонов для поиска файлов;
  • CVE-2024-21490 в Angular — регулярные выражения плюс хеш-таблица.

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

Что осталось за кадром

Хеш-таблица — одна из тех структур, без которых современное программирование невозможно представить. dict в Python, объект в JavaScript, map в Go, HashMap в Rust, Table в Nim — под всеми этими разными именами работает одна и та же идея Ханса Петера Луна, которой скоро исполнится 75 лет.

Но за уютным фасадом O(1) скрывается долгая инженерная драма: выбор функции, борьба с коллизиями, защита от атак, компромисс между скоростью и предсказуемостью. Swiss Table с SIMD-пробированием — вершина эволюции на сегодня. Если история чему-то учит, через пять-десять лет появится следующая, и мы снова будем переписывать стандартные библиотеки.

А самое важное — помнить, что O(1) существует только на бумаге. В реальности всегда есть ключи, которые сделают ваш сервер очень, очень медленным. Вопрос только в том, догадается ли об этом атакующий раньше вас.

Источники

Предыдущий
Наверх