Представьте: вы пишете парсер, который обходит сотни миллионов URL. Каждую новую ссылку нужно проверить — посещали ли мы её раньше? Заводить гигабайтный хеш-набор для хранения всех адресов — расточительно и медленно.

Но существует вероятностная структура данных, которая способна ответить на вопрос «видели ли мы этот URL?», занимая при этом в десятки раз меньше памяти, чем полное множество строк. Плата за такое - мизерная возможность ложноположительного срабатывания, где алгоритм заявит что URL существует, хотя на самом деле он новый. Зато на вопрос «не видели?» она не ошибётся никогда.

Это и есть Фильтр Блума, созданный Бёртоном Блумом аж в 1970 году. Более полсотни лет этому алгоритму! В принципе, никогда не помешает освежить знания и вспомнить, как писать реально оптимизированное ПО.

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

Фильтр Блума сам по себе устроен до неприличия просто. В основе лежит битовый массив фиксированной длины , каждый бит которого равен нулю, и набор из независимых хеш-функций . Все операции с ним сведены к манипуляциям с отдельными битами - взять хеши, установить биты, проверить биты.

Когда мы добавляем новый элемент, мы пропускаем его через независимых хеш-функций.

Я взял MurmurHash3 — современную некриптографическую хеш-функцию, которая известна своей скоростью и отличным распределением.

Каждая хеш-функция возвращает число в диапазоне от нуля до размера массива за вычетом единицы (), то есть фактически индекс бита. Мы вычисляем все хешей для элемента и устанавливаем каждый полученный бит в единицу. Если какой-то бит уже был установлен ранее — ничего страшного, он остаётся единицей; несколько элементов могут пересекаться по одним и тем же позициям.

Проверка принадлежности элемента строится на том же принципе, но в обратную сторону. Для проверяемого элемента снова вычисляются все хешей, и мы смотрим на биты под соответствующими индексами. Если хотя бы один из них равен нулю, элемент гарантированно отсутствует во множестве — потому что при его добавлении мы бы обязательно установили все эти биты. Если же все битов равны единице, фильтр сообщает «элемент, скорее всего, присутствует», но с некоторой вероятностью это может быть ложноположительным срабатыванием — биты могли быть установлены другими элементами, создавая коллизию.

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

Но! У фильтра Блума есть ограничение: из него нельзя удалять элементы. Биты в массиве не привязаны к конкретным элементам, один и тот же бит может быть установлен разными элементами. Если попытаемся удалить элемент, обнулив его биты, мы рискуем поломать и другие элементы, что приведёт к ложноотрицательным срабатываниям, а это для фильтра Блума неприемлемо по определению.

В ответ на этот недостаток появилась модификация под названием Counting Bloom Filter, которая заменяет битовый массив на массив счётчиков. При добавлении элемента все соответствующие счётчики инкрементируются, при удалении — декрементируются. Это позволяет удалять элементы без риска задеть другие, но платой становится дополнительная память: вместо одного бита на позицию требуется несколько бит (обычно от 2 до 4) для хранения счётчика. Впрочем, даже в таком виде структура остаётся значительно компактнее полноценного хеш-набора, и на практике эту модификацию используют там, где удаления действительно необходимы и часты. Для классического же однобитного фильтра Блума правило остаётся неизменным: добавление — да, удаление — нет.

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

Начнём с чистого листа. У нас есть:

• n — количество элементов, которые мы планируем добавить в фильтр (например, 10 миллионов URL).

• m — размер битового массива, наша основная структура данных. Измеряется в битах.

• k — количество хеш-функций. Для каждого элемента мы вычисляем k индексов в битовом массиве.

Наша цель — понять, как, зная n, подобрать m и k, чтобы вероятность ошибки была не выше заданной, но при этом не потратить лишнюю память.

После добавления всех n элементов каждый из k хешей выставил случайный бит в 1. Выберем один конкретный бит в массиве. Какова вероятность, что он остался равен нулю?

Одна хеш-функция для одного элемента имеет вероятность попасть в этот бит. Значит, вероятность не попасть в него равна . Нам нужно, чтобы все kn операций (каждый из n элементов, помноженный на k хеш-функций) прошли мимо нашего бита. Так как операции независимы, вероятности перемножаются:

Работать с этим выражением напрямую неудобно. К счастью, в реальных задачах m — это миллионы или миллиарды, то есть очень большое число. Срабатывает известный математический предел: выражение при больших m стремится к , где e — число Эйлера ().

Это позволяет нам записать исходную вероятность в эквивалентной, но более простой форме. Представим как . Заменяя внутреннюю часть на , получаем изящную экспоненциальную форму:

Что означает kn/m в показателе? Это среднее количество попаданий хеш-функций на одну ячейку массива. Если это число равно 2, то в каждую ячейку в среднем «прилетело» два хеша. Логично, что чем выше эта плотность, тем меньше у ячейки шансов уцелеть и остаться нулём.

Мы знаем шанс бита остаться нулём (). Тогда вероятность, что он уже установлен в единицу, равна:

Теперь — ключевой момент для понимания ложного срабатывания. Мы проверяем элемент, которого в фильтре заведомо нет. Мы вычисляем для него k хеш-функций и получаем k индексов в массиве. Ложная тревога произойдёт, только если биты по всем этим индексам случайно оказались единицами. Считая эти события независимыми, мы получаем итоговую вероятность ошибки P:

Это и есть основная формула фильтра Блума.

При фиксированных n и m у нас есть свобода выбора k. Наша задача — найти такое k, при котором вероятность ошибки P минимальна. Для этого нам не нужно перебирать числа наугад. Мы можем взять производную функции P(k) и найти её минимум. Опуская детали дифференцирования, результат оказывается на удивление простым:

То есть оптимальное число хеш-функций напрямую зависит от того, сколько бит массива мы можем выделить на один элемент (m/n). Если подставить это оптимальное k обратно в формулу вероятности пустого бита (), мы получим . Это важное следствие: в оптимально настроенном фильтре Блума ровно половина битов будет единицами, а половина — нулями.

На практике задача ставится иначе. Мы знаем n (ожидаемое число элементов) и P (допустимую вероятность ошибки). Нам нужно найти минимальный размер массива m. Для этого мы берём нашу основную формулу для P, подставляем в неё выражение для оптимального k и решаем получившееся уравнение относительно m:

Выражая отсюда m, получаем практическую, инженерную формулу:

Эта формула сразу даёт ответ в битах, и рост памяти здесь логарифмический относительно . Это объясняет эффективность фильтра: чтобы снизить вероятность ошибки в 100 раз, объём памяти нужно увеличить на константу, а не в 100 раз.

Закрепим на конкретных цифрах. Допустим, у нас n = 10 миллионов URL, и мы готовы мириться с вероятностью ошибки P = (одно ложное срабатывание на тысячу проверок).

Сначала давайте посчитаем память (m):

Делим на 8 и на , чтобы получить мегабайты: . Для сравнения, хранение 10 миллионов строк в Set заняло бы сотни мегабайт, если не гигабайты.

Считаем оптимальное число хеш-функций (k):

Округляем до ближайшего целого: k = 10.

Теперь у нас есть конкретный технический дизайн: массив в 17,2 МБ и 10 хеш-функций.

Прежде чем говорить о самом фильтре Блума, нужно уделить внимание хеш-функции. От её качества зависит всё: если хеш-функция распределяет биты неравномерно или имеет зависимости между битами, все наши мечты о гарантиях алгоритма рушатся.

Я выбрал MurmurHash3, ибо его лавинный эффект и равномерность распределения изучены вдоль и поперёк, и отлично подходят для вероятностных алгоритмов.

static inline uint64_t murmur3_fmix64(uint64_t k) {
    k ^= k >> 33;
    k *= 0xff51afd7ed558ccdULL;
    k ^= k >> 33;
    k *= 0xc4ceb9fe1a85ec53ULL;
    k ^= k >> 33;
    return k;
}

static inline uint64_t murmur3_64(const void* key, size_t len, uint64_t seed) {
    const uint8_t* data = (const uint8_t*)key;
    const int nblocks = len / 16;
    uint64_t h1 = seed;
    uint64_t h2 = seed;

    const uint64_t c1 = 0x87c37b91114253d5ULL;
    const uint64_t c2 = 0x4cf5ad432745937fULL;

    const uint64_t* blocks = (const uint64_t*)data;

    for (int i = 0; i < nblocks; i++) {
        uint64_t k1 = blocks[i * 2];
        uint64_t k2 = blocks[i * 2 + 1];

        k1 *= c1;
        k1 = (k1 << 31) | (k1 >> 33);
        k1 *= c2;
        h1 ^= k1;
        h1 = (h1 << 27) | (h1 >> 37);
        h1 += h2;
        h1 = h1 * 5 + 0x52dce729;

        k2 *= c2;
        k2 = (k2 << 33) | (k2 >> 31);
        k2 *= c1;
        h2 ^= k2;
        h2 = (h2 << 31) | (h2 >> 33);
        h2 += h1;
        h2 = h2 * 5 + 0x38495ab5;
    }

    const uint8_t* tail = data + nblocks * 16;
    uint64_t k1 = 0;
    uint64_t k2 = 0;

    switch (len & 15) {
        case 15: k2 ^= (uint64_t)tail[14] << 48;
        case 14: k2 ^= (uint64_t)tail[13] << 40;
        case 13: k2 ^= (uint64_t)tail[12] << 32;
        case 12: k2 ^= (uint64_t)tail[11] << 24;
        case 11: k2 ^= (uint64_t)tail[10] << 16;
        case 10: k2 ^= (uint64_t)tail[9] << 8;
        case 9:  k2 ^= (uint64_t)tail[8];
                 k2 *= c2;
                 k2 = (k2 << 33) | (k2 >> 31);
                 k2 *= c1;
                 h2 ^= k2;
        case 8:  k1 ^= (uint64_t)tail[7] << 56;
        case 7:  k1 ^= (uint64_t)tail[6] << 48;
        case 6:  k1 ^= (uint64_t)tail[5] << 40;
        case 5:  k1 ^= (uint64_t)tail[4] << 32;
        case 4:  k1 ^= (uint64_t)tail[3] << 24;
        case 3:  k1 ^= (uint64_t)tail[2] << 16;
        case 2:  k1 ^= (uint64_t)tail[1] << 8;
        case 1:  k1 ^= (uint64_t)tail[0];
                 k1 *= c1;
                 k1 = (k1 << 31) | (k1 >> 33);
                 k1 *= c2;
                 h1 ^= k1;
    }

    h1 ^= len;
    h2 ^= len;
    h1 += h2;
    h2 += h1;

    h1 = murmur3_fmix64(h1);
    h2 = murmur3_fmix64(h2);
    h1 += h2;
    h2 += h1;

    return h1;
}

static inline uint64_t murmur3_64_string(const char* str, uint64_t seed) {
    return murmur3_64(str, strlen(str), seed);
}

Алгоритм обрабатывает блоками по 16 байт, используя два независимых 64-битных регистра, а финальное перемешивание выполняет функция fmix64, миксуя биты с помощью умножений и сдвигов. На выходе мы получаем 64 бита, которые ведут себя как равномерно случайные, — идеальное сырьё для нашего вероятностного алгоритма.

Кстати, этот алгоритм в виде ГПСЧ я описывал в одной из своих статей.

Наконец-то мы достигли практической части, где опустим занудную математику и достанем не менее занудный C!

Структура фильтра Блума на C выглядит вот так:

typedef struct {
    uint64_t size;          /* размер битового массива в битах */
    uint64_t hash_count;    /* число хеш-функций */
    uint64_t items_count;   /* количество добавленных элементов */
    uint8_t *bit_array;     /* упакованный битовый массив */
} BloomFilter;

Размеры полей выбраны 64-битными, потому что фильтр Блума часто работает с миллионами и миллиардами элементов, и 32-битных значений для размера массива может не хватить. Поле bit_array — это указатель на область памяти, где биты упакованы по 8 штук в байт. Такой подход сокращает потребление памяти в 8 раз по сравнению с массивом bool, а также улучшает локальность данных при последовательном обходе.

Инициализация фильтра происходит через функцию bloom_filter_create, которая выделяет память под структуру и под битовый массив, заполняя его нулями:

BloomFilter* bloom_filter_create(uint64_t size, uint64_t hash_count) {
    if (size == 0 || hash_count == 0) {
        return NULL;
    }
    BloomFilter *bf = (BloomFilter*)malloc(sizeof(BloomFilter));
    if (!bf) {
        return NULL;
    }
    bf->size = size;
    bf->hash_count = hash_count;
    bf->items_count = 0;
    bf->bit_array = (uint8_t*)calloc((size + 7) / 8, sizeof(uint8_t));
    if (!bf->bit_array) {
        free(bf);
        return NULL;
    }
    return bf;
}

Выражение (size + 7) / 8 — стандартный приём округления вверх при делении на 8: для хранения, скажем, 20 бит нужно 3 байта (24 бита), потому что 20 нацело на 8 не делится, а два байта дадут только 16. Именно поэтому мы добавляем 7 перед делением — гарантируем, что байтов будет ровно столько, сколько нужно для размещения всех битов, включая последний неполный байт.

Функция bloom_filter_from_expected — это удобная обёртка, которая принимает как аргументы ожидаемое число элементов и желаемую вероятность ложного срабатывания, а затем вычисляет оптимальные параметры по формулам из предыдущего раздела:

BloomFilter* bloom_filter_from_expected(uint64_t expected_elements, double false_positive_rate) {
    if (expected_elements == 0 || false_positive_rate <= 0.0 || false_positive_rate >= 1.0) {
        return NULL;
    }
    double ln2 = 0.6931471805599453;
    double size_d = -(expected_elements * log(false_positive_rate)) / (ln2 * ln2);
    uint64_t size = (uint64_t)ceil(size_d);
    if (size < 1) size = 1;
    double hash_count_d = (size / (double)expected_elements) * ln2;
    uint64_t hash_count = (uint64_t)round(hash_count_d);
    if (hash_count < 1) hash_count = 1;
    return bloom_filter_create(size, hash_count);
}

Здесь расчётный размер округляется вверх через ceil, а число хеш-функций — до ближайшего целого через round. Обработка крайних случаев, когда размер или число хешей оказывается меньше единицы, присутствует на всякий случай, хотя при корректных входных данных этого не происходит.

Работа с отдельными битами реализована через две простые inline-функции. set_bit устанавливает бит с индексом index в единицу, get_bit проверяет, установлен ли он:

static inline void set_bit(uint8_t *array, uint64_t index) {
    array[index >> 3] |= (1 << (index & 7));
}

static inline bool get_bit(const uint8_t *array, uint64_t index) {
    return (array[index >> 3] & (1 << (index & 7))) != 0;
}

Операция index >> 3 — это деление на 8, то есть номер байта. Выражение index & 7 даёт остаток от деления на 8, то есть позицию бита внутри байта. Установка бита выполняется через побитовое ИЛИ с маской, сдвинутой на нужную позицию. Проверка — через побитовое И с той же маской и сравнение с нулём.

Для вычисления индексов битов используется техника двойного хеширования. Вместо того чтобы вычислять независимых хеш-функций, что было бы дорого, мы вычисляем два 64-битных хеша ( и ) и генерируем все необходимые индексы по формуле:

static inline uint64_t double_hash(uint64_t h1, uint64_t h2, uint64_t i, uint64_t size) {
    return (h1 + i * h2) % size;
}

При обходе значений от 0 до hash_count - 1 эта формула даёт последовательность псевдослучайных чисел, равномерно распределённых в диапазоне . Это стандартный приём для фильтров Блума, он опирается на теорему о том, что линейная комбинация двух хороших хешей даёт результат, неотличимый от независимых хеш-функций. Главное требование — чтобы не было равно нулю, иначе последовательность выродится в одно и то же число. Поэтому в коде есть проверка и принудительная установка в случае нуля.

Добавление элемента в фильтр выглядит так:

void bloom_filter_add(BloomFilter *bf, const char *item) {
    if (!bf || !item) {
        return;
    }
    uint64_t seed1 = 0x123456789ABCDEF0ULL;
    uint64_t seed2 = 0xFEDCBA9876543210ULL;
    uint64_t h1 = murmur3_64_string(item, seed1);
    uint64_t h2 = murmur3_64_string(item, seed2);
    if (h2 == 0) h2 = 1;
    bool was_new = false;
    for (uint64_t i = 0; i < bf->hash_count; i++) {
        uint64_t idx = double_hash(h1, h2, i, bf->size);
        if (!get_bit(bf->bit_array, idx)) {
            was_new = true;
            set_bit(bf->bit_array, idx);
        }
    }
    if (was_new) {
        bf->items_count++;
    }
}

Мы вычисляем два базовых хеша с разными солями, затем в цикле проходим по всем hash_count индексам. Для каждого индекса проверяем бит: если он был нулевым, значит, мы действительно добавляем новый элемент или, по крайней мере, устанавливаем хотя бы один бит, который раньше не был установлен. Флаг was_new позволяет увеличить счётчик добавленных элементов только в том случае, если элемент действительно что-то изменил в фильтре. Это важно для корректного подсчёта items_count, который используется в формуле оценки вероятности ложного срабатывания.

Проверка принадлежности элемента строится на той же логике, но без модификации состояния:

bool bloom_filter_contains(const BloomFilter *bf, const char *item) {
    if (!bf || !item) {
        return false;
    }
    uint64_t seed1 = 0x123456789ABCDEF0ULL;
    uint64_t seed2 = 0xFEDCBA9876543210ULL;
    uint64_t h1 = murmur3_64_string(item, seed1);
    uint64_t h2 = murmur3_64_string(item, seed2);
    if (h2 == 0) h2 = 1;
    for (uint64_t i = 0; i < bf->hash_count; i++) {
        uint64_t idx = double_hash(h1, h2, i, bf->size);
        if (!get_bit(bf->bit_array, idx)) {
            return false;
        }
    }
    return true;
}

Если хотя бы один бит равен нулю, функция немедленно возвращает false — элемента гарантированно нет. Если все биты единицы — возвращает true, что означает вероятное присутствие.

Для анализа состояния фильтра предусмотрены две функции. bloom_filter_fill_ratio вычисляет долю установленных битов в массиве, проходя по всем байтам и подсчитывая единичные биты внутри каждого байта через последовательное смещение вправо до тех пор, пока байт не станет нулевым:

double bloom_filter_fill_ratio(const BloomFilter *bf) {
    if (!bf || bf->size == 0) {
        return 0.0;
    }
    uint64_t filled = 0;
    uint64_t bytes = (bf->size + 7) / 8;
    for (uint64_t i = 0; i < bytes; i++) {
        uint8_t byte = bf->bit_array[i];
        while (byte) {
            filled += byte & 1;
            byte >>= 1;
        }
    }
    return (double)filled / (double)bf->size;
}

bloom_filter_current_fp_rate вычисляет текущую оценку вероятности ложного срабатывания по формуле, которую мы вывели в разделе математики, используя актуальные значения hash_count, items_count и size:

double bloom_filter_current_fp_rate(const BloomFilter *bf) {
    if (!bf || bf->items_count == 0) {
        return 0.0;
    }
    double exponent = -((double)bf->hash_count * (double)bf->items_count) / (double)bf->size;
    return pow(1.0 - exp(exponent), (double)bf->hash_count);
}

Для красивого вывода всей статистики есть функция bloom_filter_stats, которая печатает данные в формате JSON.

Запустим этот код! Пример из main создаёт фильтр с параметрами, рассчитанными на 1000 элементов и вероятность ложного срабатывания 1%, добавляет в него семь названий фруктов, а затем проверяет слово «watermelon», которого там нет:

Optimal size: 9586
Optimal hash count: 7

'watermelon' in filter: false
Statistics: {
  "size": 9586,
  "hash_count": 7,
  "items_added": 7,
  "fill_ratio": 0.005112,
  "estimated_fp_rate": 0.000000
}

Фильтр честно сообщает, что элемента нет — все 7 битов, соответствующих «watermelon», оказались нулевыми. Заполненность битового массива составляет чуть больше половины процента, что ожидаемо при семи добавленных элементах из тысячи возможных.

Второй пример показывает, что происходит при неудачном выборе параметров: фильтр размером 20 бит с двумя хеш-функциями, в который добавили 10 строк. Заполненность достигает 70%, а расчётная вероятность ложного срабатывания — почти 40%, и проверка на слово «watermelon» даёт ложное срабатывание:

Small filter: 'watermelon' in filter: true
Small filter statistics: {
  "size": 20,
  "hash_count": 2,
  "items_added": 10,
  "fill_ratio": 0.700000,
  "estimated_fp_rate": 0.399576
}

Когда я строил этот алгоритм впервые, я тоже удивился поначалу, как работает ложноположительное срабатывание.

По аналогии со статьёй про HyperLogLog я решил провести тесты с изменёнными константами и нарисовать графики. Полный набор сырых данных доступен по этой ссылке.

По этим графикам можно сделать вывод, что использовать фильтр Блума при количестве элементов менее 500 стоит избегать. Используйте конфигурации high_fp, когда важна скорость (на 10–35% быстрее), и применяйте для них hash_count = 4, а для low_fp используйте hash_count = 7.

Эта статья — некое развитие моей серии алгоритмов и структур данных с реализацией на C. Вы можете взглянуть на эту серию статей по вот этой ссылке. Тут я применил формат «один алгоритм — одна статья», что позволяет разбирать интересные алгоритмы, которые слишком велики для того, чтобы называться небольшим трюком. В этом формате я уже выпускал статью, которую приводил здесь, про вероятностную структуру данных HyperLogLog.

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩