Ribbon filter - это, пожалуй, один из самых недооцененных фильтров, который меньше по памяти чем
Bloom, и в моих тестах показал более низкий false positive rate, чем Cuckoo. Разберем, как он работает, и сделаем выводы.
RibbonВ отличии от
Bloom, где мы просто помечаем биты, и Cuckoo, где храним fingerprints ключей в бакетах, Ribbon для каждого ключа строит локальное XOR-уравнение внутри окна cells[start : start+w]. Фильтр статический, поэтому все такие уравнения решаются один раз при построении фильтра, а во время поиска мы просто вычисляем XOR по тем же позициям и проверяем, совпадает ли результат. За счёт того, что во время поиска каждый ключ работает только внутри своего окна, фильтр получается очень «кеш френдли» и хорошо укладывается в память. Звучит пока абстрактно, поэтому надо смотреть на структуру.
В моей реализации фильтр хранит не набор ключей, а массив ячеек
cells, плюс параметры окна и seed.
type RibbonFilter struct {
m uint32
w uint32
seed uint64
span uint32
cells []uint16
built bool
}
Главное поле - это
cells []uint16: именно его мы в итоге строим, а потом используем для поиска. Поле w - ширина локального окна, внутри которого будут составные части уравнения для каждого ключа; span - диапазон допустимых стартов окна. Тут нет классического
Add()метода, потому что Ribbon - это статический фильтр, то есть он строится сразу целиком, когда известны все ключи. Что происходит с каждым ключом
Для каждого ключа фильтр собирает набор для уравнения:
type row struct {
start uint32
mask uint64
fingerprint uint16
}
Из одного ключа мы получаем:
start - где начинается его локальное окно,mask - какие ячейки внутри окна участвуют в XOR,fingerprint - какой результат этот XOR должен дать. Через makeRow собираем все необходимое:
func (rf *RibbonFilter) makeRow(item []byte) row {
h := hash64(item, rf.seed)
start, mask, fp := derive(h, rf.span, rf.w)
return row{
start: start,
mask: mask,
fingerprint: fp,
}
}
Внутри
derive(...) один хеш раскладывается на три независимых части через mix64(). Что, кстати, куда дешевле, чем делать по 3 хеша. (поэтому можно подтянуть отдельно метод derive и пользоваться) Итого:
каждый ключ в Ribbon filter превращается не в запись, а в XOR-уравнение над кусочком массива cells
Роль окон в уравнении
Одна из самых приятных вещей в
Ribbon, это локальность по памяти. Если убрать детали, то в уравнении:
XOR(cells[start : start+w]) = fingerprint(key)
ключ резервирует не весь массив, а только локальное окно
cells[start : start+w]. Внутри этого окна маска определяет, какие позиции реально участвуют в XOR - это видно из start, w, mask и из того, как Contains проходит по установленным битам маски. То есть каждый ключ работает только внутри своего окна. У такого подхода есть практический плюс: за счёт окон lookup работает локально по памяти, а не прыгает по всем cells; но при этом построение у Ribbon заметно дороже, чем у Bloom. Локальная позиция внутри окна (mask) превращается в глобальный индекс через
start + bitPos, и именно за счёт этого Ribbon получается cache-friendly. Это только часть описания
Ribbon фильтра, но уже видно, что он не работает с привычной вставкой элементов. Вместо этого он один раз строит систему XOR-уравнений, которая кодирует весь набор ключей, а при поиске просто подставляет ключ в это уравнение и сравнивает результат с fingerprint. За счёт того, что все вычисления происходят внутри небольшого окна, lookup обычно укладывается в одну кеш линию и требует минимум памяти.
В следующей части будет описан сам алгоритм сборки фильтра и вывод из сравнения бенчей
Дополнительно про ribbon:
- https://rocksdb.org/blog/2021/12/29/ribbon-filter.html
- https://engineering.fb.com/2021/07/09/core-infra/ribbon-filter/
- https://github.com/RibbonFilter/ribbonGo
Потыкать ribbon можно по примеру из ридми
#fts #perf
