Привет, Хабр!
Компактные структуры данных – это эффективные решения для обработки больших объемов данных с минимальным использованием памяти. Они позволяют выполнять такие задачи, как фильтрация, поиск и хранение, с меньшими затратами ресурсов, что особенно полезно в Golang, т.к частенько на нем реализуют именно высоконагруженные системы с ограниченной памятью.
В этой статье мы рассмотрим популярную структуру данных: Bloom-фильтры, они помогут минимизировать использование памяти и ускорить выполнение задач.
Bloom-фильтры
Bloom-фильтр — это такая хитрая структура данных, которая позволяет проверять, принадлежит ли элемент множеству. Сразу хочу оговориться — проверка всегда быстрая, но есть нюанс: она может дать ложноположительный результат (сказать, что элемент есть, хотя его нет), но никогда — ложноотрицательный (если говорит, что элемента нет, то его точно нет). Для многих приложений это абсолютно нормально — лучше иногда ошибаться в сторону «элемент есть», чем хранить гигантские таблицы или массивы.
Характеристики Bloom-фильтра:
-
Малое использование памяти. Использует фиксированное количество памяти независимо от размера данных.
-
Ложноположительные срабатывания. Возможны ложные срабатывания, но отсутствуют ложноотрицательные.
-
Постоянное время проверки. Вставка и проверка присутствия элемента происходят за фиксированное время.
-
Невозможность удаления элементов. Хотя есть модификации фильтра, которые поддерживают удаление, классический Bloom-фильтр не предназначен для удаления элементов.
Как работают Bloom-фильтры
Простота в основе. По сути, Bloom-фильтр — это битовый массив и несколько хеш-функций. Когда ты добавляешь элемент, несколько хеш-функций вычисляют индексы, которые нужно выставить в «1» в битовом массиве. При проверке элемента те же хеш‑функции вычисляют индексы и смотрят, выставлены ли они в «1». Если хотя бы один индекс равен «0», элемент точно не принадлежит множеству. Если все равны «1» — возможно, элемент есть, но не факт (здесь и кроется возможность ложноположительного результата).
Алгоритм:
-
Инициализируем битовый массив размера
m
, заполненный нулями. -
Выбираем
k
различных хеш-функций. -
При добавлении элемента, каждую хеш-функцию применяем к элементу, получаем
k
индексов, и ставим соответствующие биты в единицу. -
Для проверки элемента, снова применяем хеш-функции и проверяем соответствующие биты. Если хотя бы один бит — «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
, элемента точно нет.
Теперь копнем чуть глубже. Как выбрать оптимальные параметры для фильтра?
-
Размер битового массива (m). Это влияет на точность фильтра. Чем больше битов, тем меньше вероятность ложных срабатываний, но больше памяти потребуется.
-
Количество хеш-функций (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».
ссылка на оригинал статьи https://habr.com/ru/articles/843714/
Добавить комментарий