Ribbon Filter: Part 2 - построение фильтра через elimination и back substitution

В первой части мы разобрались, что Ribbon не хранит элементы напрямую, а кодирует весь набор ключей как систему XOR-уравнений внутри массива cells.

Остается вопрос: как именно мы получаем значения в cells, чтобы все эти уравнения выполнялись?

Сборка фильтра происходит внутри BuildFromKeyStream и делится на 2 этапах:
1. elimination - упрощение XOR уравнений через исключение одинаковых переменных
2. back substitution - вычисление неизвестных значений cells через те, которые стали известными после elimination

Как работает elimination

Ранее разбирали, что поиск в Ribbon реализуется за счет решения XOR уравнения с fingerprint ключа и значениями в cells внутри окна. Fingerprint нам известен на этапе поиска, поэтому при построении фильтра надо определить, что будет в cells

Алгоритм сборки в BuildFromKeyStream:
1. у каждой строки есть ведущая колонка (pivot - первая переменная в уравнении для cells[i])
2. если pivot для неё ещё не занят - строка становится pivot
3. если занят - строка XOR’ится с существующим pivot

Про pivots[i] - когда приходит новая строка с той же ведущей колонкой, она XOR’ится с уже сохранённой строкой и тем самым эта переменная «исключается» из уравнения (elimination). Чтобы вкурить, советую посмотреть комментариями в коде и как это реализовано в цикле elimination.

for cur.mask != 0 {
  leadCol := cur.leadingColumn()

  if !pivots[leadCol].isSet {
    pivots[leadCol].row = cur
    pivots[leadCol].isSet = true
    break
  }

  cur = xorRows(cur, pivots[leadCol].row)
}

Тут очередная экономия, так как вместо огромной матрицы Ribbon хранит только опорные уравнения - по одному pivot на колонку.

Как две строки XOR’ятся между собой

Так как mask хранит не глобальные индексы, а позиции внутри локального окна, перед XOR две строки надо сначала выровнять относительно общего пространства

cells[i]:
shift := int(pivot.start) - int(cur.start)
aligned = pivot.mask << shift // или >> если shift отрицательный
cur.mask ^= aligned

Если окна не пересекаются (разница по start слишком большая - в моем случае это +32 ), совпадающих cells нет, и XOR ничего не сокращает.

Затем строка нормализуется: убираются хвостовые нули, а start сдвигается вперёд через TrailingZeros64

tz := bits.TrailingZeros64(cur.mask)
cur.start += uint32(tz)
cur.mask >>= tz

Обратная подстановка (back substitution)

После elimination мы ещё не знаем значения cells, только зависимости между ними в виде уравнений.

Дальше мы последовательно вычисляем их справа налево:
- к моменту вычисления cells[i] все зависимые значения с бОльшими индексами уже посчитаны, поэтому можно выразить cells[i] через них, XOR’нув известные значения с fingerprint
- если для cells[i] pivot нет, значит в XOR нечего класть - значение считается равным 0 (подробнее)

Look up: как работает Contains

После адовой сборки лукап получается удивительно коротким: достаточно найти составляющие XOR и сравнить результат с fingerprint:

for localMask != 0 {
  bitPos := bits.TrailingZeros64(localMask)
  acc ^= rf.cells[start+uint32(bitPos)]
  localMask &= localMask - 1
}

Вывод

Как можно заметить, Ribbon filter переносит всю сложность в этап построения: мы решаем систему XOR-уравнений и затем сохраняем её решение в cells.

За счёт этого lookup превращается в простую и быструю операцию в виде нескольких XOR внутри локального окна.

А чтобы не оставаться в теории, я прогнала все три фильтра на одинаковой конфигурации на 1 млн ключей

По размеру индексов выиграл, правда, Cuckoo (1.2 MB), затем Ribbon (1.8 MB) и Bloom (2.7 MB).

Универсальным вариантом (ровный по перфу и простой в реализации) я бы назвала Bloom.

Если нужен быстрый lookup и поддержка delete - это Cuckoo. Но это оправдано, если не критичны стоимость сборки и дополнительные аллокации памяти.

Ribbon даёт низкий false positive rate, экономнее по памяти и быстрее Bloom на реальных данных. Но эта выгода достигается ценой сложной реализации и, соответственно, поддержки.

Как обычно - пример, готовый к использованию и сама дока

#fts #perf