[16.10.2025] Sphinx: A Succinct Perfect Hash Index for x86
Ruslan Savchenko
Одной из популярных и естественных задач в работе различных сервисов и систем является Key-Value Storage, сохраняющий данные на диске и поддерживающий некий index в памяти для быстрых лукапов.
Распространённым решением являются Log Structured Hash Tables, которые хранят данные в append-only логе, а в памяти — хэш таблицу, отображающую hash(key) в offset данных в логе.
Большой размер хэша в LSH-tables ведёт к разрастанию индекса в памяти, а компактные хэши — к коллизиям и дополнительным IO операциям.
В рамках доклада мы рассмотрим современные подходы: Delta hash tables, разработанный для FPGA, и его оптимизацию под x86 CPU Sphinx, — основанные на идее perfect hashing, реализованной с помощью delta-боров с очень компактной битовой записью (3-4 бита в среднем на один ключ). Посмотрим, как они сводят False positive rate IO операцию к нулю для существующих ключей, и как Sphinx оптимизирует FPR для несуществующих ключей.
В финале проанализируем замеры производительности и сравним Sphinx, DHT, и некоторые реализации LSH-таблиц.