Реализация Bloom-фильтров в Golang18.09.2024 15:30

f49467140451ecebd0552bfc26a609eb.png

Привет, Хабр!

Компактные структуры данных — это эффективные решения для обработки больших объемов данных с минимальным использованием памяти. Они позволяют выполнять такие задачи, как фильтрация, поиск и хранение, с меньшими затратами ресурсов, что особенно полезно в Golang, т.к частенько на нем реализуют именно высоконагруженные системы с ограниченной памятью.

В этой статье мы рассмотрим популярную структуру данных: Bloom-фильтры, они помогут минимизировать использование памяти и ускорить выполнение задач.

Bloom-фильтры

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

Характеристики Bloom-фильтра:

  1. Малое использование памяти. Использует фиксированное количество памяти независимо от размера данных.

  2. Ложноположительные срабатывания. Возможны ложные срабатывания, но отсутствуют ложноотрицательные.

  3. Постоянное время проверки. Вставка и проверка присутствия элемента происходят за фиксированное время.

  4. Невозможность удаления элементов. Хотя есть модификации фильтра, которые поддерживают удаление, классический Bloom-фильтр не предназначен для удаления элементов.

Как работают Bloom-фильтры

Простота в основе. По сути, Bloom-фильтр — это битовый массив и несколько хеш-функций. Когда ты добавляешь элемент, несколько хеш-функций вычисляют индексы, которые нужно выставить в »1» в битовом массиве. При проверке элемента те же хеш-функции вычисляют индексы и смотрят, выставлены ли они в »1». Если хотя бы один индекс равен »0», элемент точно не принадлежит множеству. Если все равны »1» — возможно, элемент есть, но не факт (здесь и кроется возможность ложноположительного результата).

Алгоритм:

  1. Инициализируем битовый массив размера m, заполненный нулями.

  2. Выбираем k различных хеш-функций.

  3. При добавлении элемента, каждую хеш-функцию применяем к элементу, получаем k индексов, и ставим соответствующие биты в единицу.

  4. Для проверки элемента, снова применяем хеш-функции и проверяем соответствующие биты. Если хотя бы один бит — »0», элемента точно нет. Если все — »1», элемент может быть в множестве.

Пример работы:

  • Пусть у нас битовый массив длиной 10 (m = 10).

  • Выбраны 3 хеш-функции (k = 3).

  • Для элемента «Hello» хеш-функции возвращают индексы 2, 5 и 7. Мы устанавливаем их в 1 в массиве.

  • Когда добавляем другой элемент, например «World», хеш-функции могут возвращать другие индексы (например, 1, 4, 7).

Теперь проверка «Hello» покажет, что все индексы 2, 5, 7 равны 1, а значит, элемент, скорее всего, есть. Если хотя бы один из этих битов был бы 0 — элемента точно нет.

Теперь переходим к самому вкусному — коду.

Для начала нужно создать структуру для хранения фильтра: 

package bloom

import (
    "hash"
    "hash/fnv"
    "math"
)

type BloomFilter struct {
    bitSet  []bool
    size    int
    hashes  []hash.Hash64
}

// Инициализация фильтра
func NewBloomFilter(size int, hashCount int) *BloomFilter {
    bitSet := make([]bool, size)
    hashes := make([]hash.Hash64, hashCount)

    // Инициализация хеш-функций
    for i := 0; i < hashCount; i++ {
        hashes[i] = fnv.New64()
    }

    return &BloomFilter{
        bitSet: bitSet,
        size:   size,
        hashes: hashes,
    }
}

Этот код создает структуру для нашего фильтра. bitSet — это битовый массив, size — его размер, а hashes — набор хеш-функций. Для простоты возьмем fnv.New64 — удобная хеш-функция из стандартной библиотеки Go.

Добавим функцию для вставки элементов: 

func (bf *BloomFilter) Add(item string) {
    for _, hashFunc := range bf.hashes {
        hashFunc.Reset()
        hashFunc.Write([]byte(item))
        index := hashFunc.Sum64() % uint64(bf.size)
        bf.bitSet[index] = true
    }
}

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

Теперь добавим проверку: 

func (bf *BloomFilter) Check(item string) bool {
    for _, hashFunc := range bf.hashes {
        hashFunc.Reset()
        hashFunc.Write([]byte(item))
        index := hashFunc.Sum64() % uint64(bf.size)
        if !bf.bitSet[index] {
            return false
        }
    }
    return true
}

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

Теперь копнем чуть глубже. Как выбрать оптимальные параметры для фильтра?

  1. Размер битового массива (m). Это влияет на точность фильтра. Чем больше битов, тем меньше вероятность ложных срабатываний, но больше памяти потребуется.

  2. Количество хеш-функций (k). Большее количество хеш-функций уменьшает количество ложноположительных результатов, но увеличивает время проверки. Хорошее эмпирическое правило — выбирать k = (m / n) * ln(2), где n — это количество элементов в фильтре.

Для расчета этих параметров используем формулы:

  • m = -(n * ln (p)) / (ln (2))^2 — рассчитываем размер битового массива, где p — желаемая вероятность ложноположительного результата.

  • k = (m / n) * ln (2) — рассчитываем количество хеш-функций.

Вот как это можно реализовать: 

func OptimalParams(n int, p float64) (int, int) {
    m := int(math.Ceil(float64(-n) * math.Log(p) / (math.Pow(math.Log(2), 2))))
    k := int(math.Ceil(math.Log(2) * float64(m) / float64(n)))
    return m, k
}

Этот метод поможет выбрать оптимальные значения m и k для заданного количества элементов n и допустимой вероятности ложного срабатывания p.

Проверка дубликатов в БД пользователей с Bloom-фильтром

Создадим сервис для фильтрации новых регистраций пользователей, который будет проверять, регистрировался ли пользователь ранее на основе его email. Это будет полезно для системы, которая обрабатывает миллионы пользователей и не может позволить себе постоянно обращаться к базе данных для проверки каждого запроса. 

package main

import (
    "bufio"
    "fmt"
    "hash"
    "hash/fnv"
    "os"
    "strings"
)

type BloomFilter struct {
    bitSet  []bool
    size    int
    hashes  []hash.Hash64
}

// Функция для создания нового Bloom-фильтра
func NewBloomFilter(size int, hashCount int) *BloomFilter {
    bitSet := make([]bool, size)
    hashes := make([]hash.Hash64, hashCount)

    // Инициализация нескольких хеш-функций
    for i := 0; i < hashCount; i++ {
        hashes[i] = fnv.New64()
    }

    return &BloomFilter{
        bitSet: bitSet,
        size:   size,
        hashes: hashes,
    }
}

// Метод добавления элемента в Bloom-фильтр
func (bf *BloomFilter) Add(item string) {
    for _, hashFunc := range bf.hashes {
        hashFunc.Reset()
        hashFunc.Write([]byte(item))
        index := hashFunc.Sum64() % uint64(bf.size)
        bf.bitSet[index] = true
    }
}

// Метод проверки наличия элемента в Bloom-фильтре
func (bf *BloomFilter) Check(item string) bool {
    for _, hashFunc := range bf.hashes {
        hashFunc.Reset()
        hashFunc.Write([]byte(item))
        index := hashFunc.Sum64() % uint64(bf.size)
        if !bf.bitSet[index] {
            return false
        }
    }
    return true
}

// Функция для инициализации Bloom-фильтра с использованием оптимальных параметров
func OptimalBloomFilter(numElements int, falsePositiveRate float64) *BloomFilter {
    // Расчет размера битового массива и количества хеш-функций
    m := int(-float64(numElements) * (math.Log(falsePositiveRate) / (math.Pow(math.Log(2), 2))))
    k := int(math.Log(2) * float64(m) / float64(numElements))

    return NewBloomFilter(m, k)
}

// Реальный пример использования Bloom-фильтра в продакшене
func main() {
    // Параметры фильтра
    expectedUsers := 1000000   // Ожидаемое количество пользователей
    falsePositiveRate := 0.01 // Допустимая вероятность ложного срабатывания

    // Инициализируем фильтр с оптимальными параметрами
    bloomFilter := OptimalBloomFilter(expectedUsers, falsePositiveRate)

    // Чтение базы данных пользователей из файла (симуляция продакшен-данных)
    file, err := os.Open("users_db.txt")
    if err != nil {
        fmt.Println("Error opening file:", err)
        return
    }
    defer file.Close()

    scanner := bufio.NewScanner(file)
    
    // Добавляем пользователей из базы данных в Bloom-фильтр
    for scanner.Scan() {
        email := strings.TrimSpace(scanner.Text())
        bloomFilter.Add(email)
    }

    if err := scanner.Err(); err != nil {
        fmt.Println("Error reading file:", err)
    }

    // Теперь можно проверить, зарегистрирован ли новый пользователь
    newUsers := []string{
        "john.doe@example.com",
        "jane.doe@example.com",
        "spam.user@example.com",
    }

    for _, user := range newUsers {
        if bloomFilter.Check(user) {
            fmt.Printf("Пользователь %s уже зарегистрирован.\n", user)
        } else {
            fmt.Printf("Пользователь %s еще не зарегистрирован.\n", user)
            // Логика для регистрации нового пользователя
            // Например, можно добавить этого пользователя в Bloom-фильтр
            bloomFilter.Add(user)
        }
    }
}

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

Заключение

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

В завершение напоминаю про открытый урок, который состоится сегодня (18 сентября) вечером: «Верификация пользователя в системе с помощью телеграмм бота».

На уроке реализуем потоко-независимый тип map, создадим и настроим телеграмм бота для постоянного ожидания пользователей. Записаться на урок можно на странице курса «Golang Developer Basic».

© Habrahabr.ru