Фильтр Блума изнутри: откуда формулы, что при переполнении и как удалять

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

Как думаешь, сколько хеш-функций лучше

На каждый ключ отведено 10 бит. Осталось выбрать, сколько хеш-функций использовать: одну, семь или четырнадцать.

Попробуй угадать до чтения, какой выбор даёт меньше всего ложных срабатываний. Чем больше функций, тем больше битов должно случайно совпасть у чужого ключа - кажется, что четырнадцать лучше. Но каждая вставка зажигает столько же битов, и при четырнадцати функциях фильтр на три четверти состоит из единиц. Ответ - семь: ошибка 0,8% против 9,5% у одной функции и 1,9% у четырнадцати.

На что это похоже

Доска с лампочками в подъезде. Каждому жильцу при заселении зажигают k лампочек по номерам, зависящим от его фамилии. Вахтёр пускает того, у кого горят все его k лампочек.

Если k мало, посторонний легко пройдёт: одна-две его лампочки вполне могли быть зажжены другими. Если k велико, требование строгое - но и каждый жилец зажигает много лампочек, доска быстро светится почти вся, и строгость перестаёт что-либо значить. Лучшая строгость та, при которой горит половина доски.

Механизм: от шаров и корзин к оптимуму

Фильтр - массив из m битов. Вставка ключа зажигает k битов по номерам h₁(x), …, hₖ(x); проверка отвечает «возможно есть», если все k битов ключа горят.

Доля нулей. n вставок - это k · n бросков шаров в m корзин. Конкретный бит не задет одним броском с вероятностью 1 − 1/m, всеми бросками - с вероятностью (1 − 1/m)^(kn). Здесь предполагаются независимые равномерные хеши и n разных ключей. Ожидаемая доля единиц точно равна 1 − (1 − 1/m)^(kn), а приближённо - 1 − e^(−kn/m). Реальная доля случайна.

Ложное срабатывание. Зафиксируем заполненный фильтр с долей единиц q. Независимые равномерные хеши чужого ключа попадают в единицы с вероятностью qᵏ. Подставляя вместо случайной q её приближённое ожидание, получаем приближение общей вероятности, а не точное равенство:

p ≈ (1 − e^(−kn/m))ᵏ

Выбор k. В формуле два противоположных действия: рост k увеличивает показатель степени, что уменьшает p, и одновременно увеличивает долю единиц, что увеличивает p. Для m/n = 10:

k                 1        2        3        5        7        10       14
доля единиц       0,095    0,181    0,259    0,393    0,503    0,632    0,753
p                 0,0952   0,0329   0,0174   0,0094   0,0082   0,0102   0,0190

Среди показанных целых значений минимум при k = 7, где ожидаемая доля близка к половине. В приближённой формуле при непрерывном k минимум достигается, когда e^(−kn/m) = 1/2, то есть k = (m/n) · ln 2 ≈ 0,693 · m/n. Строгий вывод ищет минимум через производную и даёт это число; запомнить его помогает другое соображение: бит несёт больше всего сведений, когда он с равной вероятностью ноль или единица. Доска, на которой горит 10% лампочек, недоиспользована - можно требовать больше лампочек с человека; доска, на которой горит 90%, почти ничего не различает.

В этой модели при непрерывном оптимальном k ожидаемая доля единиц около 1/2, а ошибка примерно равна (1/2)ᵏ = (1/2)^(0,693·m/n) = 0,6185^(m/n). Каждый дополнительный бит на ключ умножает ошибку на 0,6185. Отсюда и формула размера: чтобы получить ошибку p, нужно m/n = log₂(1/p) / 0,693 = 1,44 · log₂(1/p) бит на ключ. Множитель 1,44 - цена устройства: при том же p теоретический минимум для любой структуры - log₂(1/p) бит на ключ, фильтр Блума тратит на 44% больше.

Правило

Для n разных ключей при независимых равномерных хешах ожидаемая доля единиц равна 1 − (1 − 1/m)^(kn) ≈ 1 − e^(−kn/m). Вероятность ложного срабатывания приближённо равна (1 − e^(−kn/m))ᵏ. Непрерывный оптимум этой модели - k = (m/n) · ln 2; целое k выбирают из соседних значений. Ожидаемая доля единиц около половины, ошибка около 0,6185^(m/n), размер около 1,44 · log₂(1/p) бит на ключ. Объединение двух фильтров одного размера с одинаковыми функциями - побитовое ИЛИ. Удалять из фильтра нельзя.

Разбор: замер против формулы

Фильтр на 5000 битов, 500 ключей. Хеш-функции получены приёмом раздела: генератор засевается ключом, и первые k случайных чисел после этого служат k хеш-значениями ключа. Функция opyt вставляет ключи от 0 до 499, затем проверяет 4000 ключей, которых не вставляли, и возвращает долю единиц и долю ложных срабатываний.

import math
import random

def opyt(m, n, k, zaprosov):
    bity = [0] * m
    for klyuch in range(n):
        random.seed(klyuch)
        for i in range(k):
            bity[random.randrange(m)] = 1
    lozhnyh = 0
    for klyuch in range(n, n + zaprosov):
        random.seed(klyuch)
        est = True
        for i in range(k):
            if bity[random.randrange(m)] == 0:
                est = False
                break
        if est:
            lozhnyh = lozhnyh + 1
    return [sum(bity) / m, lozhnyh / zaprosov]

m = 5000
n = 500
for k in [1, 3, 7, 14]:
    zamer = opyt(m, n, k, 4000)
    raschet = (1 - math.exp(-k * n / m)) ** k
    print(k, round(zamer[0], 3), round(zamer[1], 4), round(raschet, 4))
print(round(m / n * math.log(2), 2), round(0.6185 ** (m / n), 4))

1 0.096 0.094 0.0952
3 0.26 0.018 0.0174
7 0.502 0.0073 0.0082
14 0.752 0.018 0.019
6.93 0.0082

Столбцы: число функций, доля единиц, измеренная доля ложных срабатываний, расчётная. Доля единиц совпадает с таблицей из механизма до третьего знака. Ошибка при семи функциях - 0,73% в опыте при расчётных 0,82%; расхождение объясняется размером опыта: на 4000 запросов приходится около тридцати ложных срабатываний, и это число гуляет на пять-шесть в обе стороны. Последняя строка - оптимальное k по формуле, 6,93, и ошибка при нём.

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

Разбор: переполнение и удаление

Переполнение. Тот же фильтр на 5000 битов с семью функциями, но ключей не 500, а 5000. Доля единиц 1 − e^(−7) = 0,999, ошибка 0,999⁷ = 0,994. Фильтр отвечает «возможно есть» на 99,4% запросов про отсутствующие ключи - и при этом не выдаёт ни одной ошибки, которую можно было бы заметить: память та же, ответы формально допустимые. Фильтр Блума не растёт сам. Число ключей нужно знать заранее или следить за долей единиц и при превышении половины заводить следующий фильтр: старый остаётся только для проверок, новые ключи идут в новый, а ключ ищут во всех. Перенести ключи из старого фильтра в больший нельзя - их в нём нет; для этого нужны исходные данные.

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

mesta = {"a": [2, 5], "b": [5, 9], "c": [1, 9]}

def est(tablica, klyuch):
    for i in mesta[klyuch]:
        if tablica[i] == 0:
            return False
    return True

bity = [0] * 12
for klyuch in ["a", "b"]:
    for i in mesta[klyuch]:
        bity[i] = 1
for i in mesta["a"]:
    bity[i] = 0
print(est(bity, "a"), est(bity, "b"))

schetchiki = [0] * 12
for klyuch in ["a", "b"]:
    for i in mesta[klyuch]:
        schetchiki[i] = schetchiki[i] + 1
for i in mesta["a"]:
    schetchiki[i] = schetchiki[i] - 1
print(est(schetchiki, "a"), est(schetchiki, "b"), est(schetchiki, "c"), schetchiki)

False False
False True False [0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]

Первая строка: вставили a и b, погасили биты a - и пропал b, потому что бит 5 у них общий. Фильтр ответил «точно нет» про ключ, который в нём есть: главное обещание структуры нарушено.

Вторая строка - фильтр Блума со счётчиками: в каждой ячейке не бит, а число ключей, которые её задели. Вставка прибавляет единицу, удаление вычитает, проверка смотрит, что все счётчики ненулевые. a удалён, b на месте. Цена - память: счётчик обычно занимает четыре бита, то есть структура вчетверо больше. И удалять можно только то, что точно вставляли: удаление постороннего ключа уменьшит чужие счётчики и создаст ложное «нет».

Другой путь - кукушкин фильтр. Это кукушкина таблица из первой главы, в ячейках которой лежат не ключи, а их короткие отпечатки по несколько бит. Проверка смотрит в две ячейки и ищет отпечаток; ложное срабатывание - совпадение отпечатка у чужого ключа. Удаление - стереть отпечаток. При ошибке меньше трёх процентов такой фильтр ещё и занимает меньше памяти, чем фильтр Блума.

Что ломается без этого

Фильтр рассчитан на вчерашний объём. Данных стало вдесятеро больше, фильтр остался прежним, и обращений к диску, которые он должен был отсекать, стало столько же, сколько без него. Ошибок в журнале нет - есть только выросшая задержка.

Хеш-функций «с запасом». Четырнадцать вместо семи ухудшают ошибку вдвое и удваивают работу.

Одна слабая хеш-функция, нарезанная на куски. Если k значений получены из одного 32-битного хеша делением на части, они зависимы, и расчёт по формуле не выполняется. На практике берут два независимых хеша g и h и строят g + i · h для i от 0 до k − 1: показано, что этого достаточно.

«Возможно есть» принимают за «есть». Положительный ответ фильтра - повод сделать точную проверку, а не её замена.

Зачем это в работе

Хранилища на LSM-деревьях - RocksDB, Cassandra и им подобные - держат данные в нескольких файлах на диске и при чтении должны понять, в каком из них лежит ключ. У каждого файла есть фильтр Блума, который стараются держать в памяти, обычно около десяти бит на ключ. Ответ «точно нет» избавляет от чтения файла; при ошибке в 1% лишнее чтение случается в одном случае из ста.

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

Формула размера отвечает на вопрос, с которого начинается проектирование: миллиард ключей с ошибкой 1% - это 9,6 · 10⁹ бит, 1,2 гигабайта; с ошибкой 0,1% - 1,8 гигабайта. Сами ключи при этом могут занимать сотню гигабайт.

Теперь сам

1. На ключ отведено 8 бит. Сколько хеш-функций оптимально и какой будет ошибка? 0,6185⁸ ≈ 0,021.
2. Сколько бит на ключ нужно для ошибки 0,1%? log₂ 1000 ≈ 10.
3. В фильтре с четырьмя хеш-функциями горит 80% битов. Какова вероятность ложного срабатывания?
4. Два фильтра одного размера с одинаковыми функциями построены по двум половинам данных. Как получить фильтр для всех данных и что будет с его ошибкой?
5. Из фильтра со счётчиками удалили ключ, который в него не вставляли. Что может пойти не так?