[04.11.2025] Diva: Dynamic Range Filter for Var-Length Keys and Queries
Ruslan Savchenko
Diva: Dynamic Range Filter for Var-Length Keys and Queries
Аннотация
Range filters — важный компонент современных систем хранения, позволяющий быстро отсекать пустые диапазоны и избегать лишних обращений к диску. Однако существующие решения (SuRF, Rosetta, Memento, Grafite и др.) страдают от серьёзных ограничений: они либо требуют фиксированную длину ключей и диапазонов, либо не поддерживают динамические операции, либо не обеспечивают стабильный FPR при ограниченном объёме памяти. Более того, их структуры данных плохо подходят для переменной длины ключей и неэффективны для больших диапазонов.
В докладе будет представлен Diva — первый универсальный range filter, одновременно обеспечивающий низкий FPR, поддержку произвольной длины ключей и диапазонных запросов, а также динамические вставки и удаления. Ключевая идея включает выборочные ключи, организованные в cache-efficient trie, и Infix Stores — компактные структуры, где ключи хранятся в виде усечённых инфиксов, построенных без хеширования. Будут рассмотрены механизмы удаления общих префиксов, устранения ненужных битов, дискретизации ключевого пространства, а также использование quotienting и rank/select операций для быстрых запросов.