Тренды

Реализация фильтра Блума на Go

07.05.2024

Представим концепцию фильтра Блума в двух видах: простом и масштабируемом — и реализуем их на Go. Весь код доступен на GitHub. Технические термины постараемся объяснить понятным для широкой аудитории языком.

Введение

Представьте огромную библиотеку. Как узнать, имеется ли в ней среди миллионов книг одна-единственная? Проверить каждую полку нереально. Если книги там нет, неплохо было бы знать это заранее, избавив себя от лишних поисков.

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

Что такое «фильтр Блума»? Это не физический фильтр, а умная структура данных. Присутствие элемента во множестве проверяется ею с невероятной скоростью. Фильтр Блума способен обрабатывать огромные наборы данных, занимая при этом минимальное пространство.

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

Какова цель этой статьи? Для меня, как разработчика, фильтры Блума притягательны своей элегантностью. Но эффективная их реализация — задача непростая. Попробуем решить ее: сделаем практическую реализацию фильтра Блума на Go, используя в качестве ориентира мой код.

Понимание основ

Принцип работы фильтра Блума

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

Вероятность и эффективность

Процент ложноположительных результатов. Важно понимать, что это такое. Это вероятность того, что наличие элемента указано фильтром Блума некорректно. На ней сказываются размер битового массива и количество добавляемых элементов.
Подсчет размера и хеш-функций. Самое интересное происходит при балансировке размера массива битов m и количества хеш-функций k. В большем массиве с большим количеством хеш-функций процент ложноположительных результатов снижается, но требуется больше памяти и вычислений. Исходя из ожидаемого количества элементов и приемлемого процента ложноположительных результатов, достигается оптимальный баланс.

Компромиссы

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

Реализация на Go

Сначала определим интерфейсы:

package gobloom

import "hash"

type Interface interface {
 Add([]byte)
 Test([]byte) bool
}

type Hasher interface {
 GetHashes(n uint64) []hash.Hash64
}

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

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

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

Интерфейсом Interface определяется основная функциональность, ожидаемая от любой реализации фильтра Блума: добавление элемента, а затем тестирование, может ли он уже там присутствовать или нет.

Реализуем его:

package gobloom

import (
 "fmt"
 "hash"
 "math"
)

// «BloomFilter» — одиночная структура фильтра Блума.
type BloomFilter struct {
 bitSet []bool        // Битовый массив в виде среза «bool»
 m      uint64        // Количество битов в наборе битов, сокращенно для «len(bitSet)»
 hashes []hash.Hash64 // Применяемые хеш-функции
 k      uint64        // Количество используемых хеш-функций, сокращенно для «len(hashes)»
 mutex  sync.Mutex    // Мьютекс для потокобезопасности
}

// С помощью «NewBloomFilterWithHasher» создается новый фильтр Блума с числом 
// элементов «n» и процентом ложноположительных результатов «p».
func NewBloomFilterWithHasher(n uint64, p float64, h Hasher) (*BloomFilter, error) {
 if n == 0 {
  return nil, fmt.Errorf("number of elements cannot be 0")
 }
 if p <= 0 || p >= 1 {
  return nil, fmt.Errorf("false positive rate must be between 0 and 1")
 }
 if h == nil {
  return nil, fmt.Errorf("hasher cannot be nil")
 }
 m, k := getOptimalParams(n, p)
 return &BloomFilter{
  m:      m,
  k:      k,
  bitSet: make([]bool, m),
  hashes: h.GetHashes(k),
 }, nil
}

// С помощью «getOptimalParams» вычисляются оптимальные параметры для фильтра Блума,
// количество битов в наборе битов «m» и количество хеш-функций «k».
func getOptimalParams(n uint64, p float64) (uint64, uint64) {
 m := uint64(math.Ceil(-1 * float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)))
 if m == 0 {
  m = 1
 }
 k := uint64(math.Ceil((float64(m) / float64(n)) * math.Log(2)))
 if k == 0 {
  k = 1
 }
 return m, k
}

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

В основе этой оптимизации — желаемое количество элементов n для хранения в фильтре Блума и приемлемый процент ложноположительных результатов p. Мьютекс применяется для потокобезопасности.

Что учитывается при определении параметров:

Ожидаемые данные. Фильтр Блума настраивается функцией, исходя из объема хранимых в нем данных n и приемлемого процента ложноположительных результатов p.
Соотношение размера и точности. Цель — найти баланс, при котором фильтр Блума не слишком большой, иначе память растрачивается, и не слишком неточный, иначе ложноположительных результатов становится больше.
Объем данных и точность. Размер массива битов рассчитывается, исходя из ожидаемого количества элементов и желаемого процента ложноположительных результатов.
Предотвращение переполнения. Больший массив битов означает меньшую вероятность ложноположительных результатов, но больший объем используемой памяти. Функция нацелена на нахождение размера, который подходит «в самый раз».
Оптимизация производительности. Количество хеш-функций важно для распределения данных по битовому массиву.
Соотношение распределения и рабочей нагрузки. Если хеш-функций слишком мало, данные распределяются недостаточно и ложноположительных результатов становится больше. Если слишком много, фильтр Блума замедляется, ведь работы им выполняется больше необходимого.

Теперь реализуем функции «Add» и «Test»

// Функцией «Add» в фильтр Блума добавляется элемент.
func (bf *BloomFilter) Add(data []byte) {
 bf.mutex.Lock()
 defer bf.mutex.Unlock()
 for _, hash := range bf.hashes {
  hash.Reset()
  hash.Write(data)
  hashValue := hash.Sum64() % bf.m
  bf.bitSet[hashValue] = true
 }
}

func (bf *BloomFilter) Test(data []byte) bool {
 bf.mutex.Lock()
 defer bf.mutex.Unlock()
 for _, hash := range bf.hashes {
  hash.Reset()
  hash.Write(data)
  hashValue := hash.Sum64() % bf.m
  if !bf.bitSet[hashValue] {
   return false
  }
 }
 return true
}

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

Функцией Test проверяется возможное наличие элемента в фильтре Блума, а также задано ли в bitSet соответствующим хешированным битам значение true. Если нет, этим подтверждается, что данные еще не записаны в фильтр.

Тестирование фильтра

Вот небольшое приложение для тестирования созданного нами фильтра:

package main

import (
 "fmt"

 "github.com/franciscoescher/gobloom"
)

func main() {
 bf, _ := gobloom.NewBloomFilter(1000, 0.01)
 bf.Add([]byte("foo"))
 bf.Add([]byte("bar"))
 bf.Add([]byte("baz"))

 fmt.Println(bf.Test([]byte("foo"))) // true
 fmt.Println(bf.Test([]byte("bar"))) // true
 fmt.Println(bf.Test([]byte("baz"))) // true
 fmt.Println(bf.Test([]byte("qux"))) // false
}

Реализация хешера

Структурой hasher должно возвращаться число n для хешей. Воспользуемся пакетом github.com/spaolacci/murmur3:

package gobloom

import (
 "hash"

 "github.com/spaolacci/murmur3"
)

type MurMur3Hasher struct{}

func NewMurMur3Hasher() *MurMur3Hasher {
 return &MurMur3Hasher{}
}

func (h *MurMur3Hasher) GetHashes(n uint64) []hash.Hash64 {
 hashers := make([]hash.Hash64, n)
 for i := 0; uint64(i) < n; i++ {
  hashers[i] = murmur3.New64WithSeed(uint32(i))
 }
 return hashers
}

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

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

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

Масштабирование фильтра Блума

Относительно количества элементов значений эта реализация статична: задав какое-то количество значений, изменить его вы уже не сможете.

Что, если создать фильтр, который по мере использования увеличивается?

Зачем нужен масштабируемый фильтр?

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

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

Посмотрим, как это достигается.

Компоненты масштабируемого фильтра Блума

// Чтобы приспособиться к растущему числу элементов, с помощью «ScalableBloomFilter» объединяется несколько срезов «BloomFilter».
type ScalableBloomFilter struct {
 filters  []*BloomFilter // Это срез указателей «BloomFilter», каждый уровень масштабируемого фильтра
 n        uint64         // Количество добавленных элементов
 fpRate   float64        // Процент ложноположительных результатов для текущего среза фильтра
 fpGrowth float64        // Коэффициент, на который увеличивается вероятность ложноположительных результатов для каждого дополнительного среза фильтра
}

filters: срез указателей BloomFilter, каждый из которых — это уровень в масштабируемой структуре. Благодаря этим уровням емкость фильтра увеличивается.
n: в этом поле отслеживается общее количество элементов, добавленных во все уровни фильтра.
fpRate: процент ложноположительных результатов для текущего уровня фильтра, определяющий вероятность того, что наличие элемента указано фильтром некорректно.
fpGrowth: коэффициент, которым определяется, насколько увеличивается вероятность ложноположительных результатов с каждым дополнительным уровнем фильтра.

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

Разберем эту логику и то, как она управляется с динамическим характером хранимых в ней данных:

// С помощью «NewScalableBloomFilterWithHasher» инстанцируется новый «ScalableBloomFilter».
func NewScalableBloomFilterWithHasher(initialSize uint64, fpRate float64, fpGrowth float64, h Hasher) (*ScalableBloomFilter, error) {
 if initialSize <= 0 {
  return nil, errors.New("invalid initial size, must be greater than 0")
 }
 if fpRate <= 0 || fpRate >= 1 {
  return nil, fmt.Errorf("invalid false positive rate, must be between 0 and 1, got %f", fpRate)
 }
 if fpGrowth <= 0 {
  return nil, fmt.Errorf("invalid false positive growth rate, must be greater than 0, got %f", fpGrowth)
 }

 bf, err := NewBloomFilterWithHasher(initialSize, fpRate, h)
 if err != nil {
  return nil, err
 }

 // Возвращается новая структура масштабируемого фильтра Блума с инициализированным срезом и параметрами.
 return &ScalableBloomFilter{
  filters:  []*BloomFilter{bf}, // Начинаем с одного среза фильтра
  fpRate:   fpRate,             // Задаем исходный процент ложноположительных результатов
  fpGrowth: fpGrowth,           // Задаем скорость роста ложноположительных результатов при масштабировании фильтра
  n:        0,                  // Инициализируем добавленные элементы нулем
 }, nil
}

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

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

Параметры

initialSize (uint64): расчетное количество элементов, которое предполагалось хранить в фильтре Блума изначально. Это не жесткое ограничение, а скорее рекомендация по подготовке начального уровня фильтра Блума. Слишком маленький размер подразумевает быстрое добавление новых срезов, увеличивая потребление памяти, а слишком большой приводит к преждевременному расходу памяти.
fpRate (float64): желаемая вероятность ложноположительных результатов для первого среза фильтра Блума. Этим параметром определяется, насколько вероятно то, что в операции Test ложно указывается на наличие элемента. Меньшим значением fpRate увеличивается количество битов, используемых в исходном фильтре, чем уменьшается вероятность ложноположительных результатов, но увеличивается и потребление памяти. Типичные значения находятся в диапазоне 0,01–0,001, то есть от 1% до 0,1%.
fpGrowth (float64): скорость роста вероятности ложноположительных результатов с добавлением каждого последующего среза фильтра. Если задано значение больше 1, на каждом новом уровне фильтра допустим более высокий процент ложноположительных результатов, а значит, добавление новых уровней можно отложить и проконтролировать использование памяти. Обычно для этого параметра задается значение, близкое к 1, например 1,5–2, поскольку более высокие темпы роста чреваты быстрым снижением процента ложноположительных результатов.

Практические рекомендации

Чтобы оценить, какие показатели initialSize и fpGrowth приемлемые, проведите предварительный анализ, руководствуясь ожидаемыми темпами роста данных. Учитывайте текущую и будущую доступность памяти, схемы доступа к данным.
Создавайте журналы или метрики, связанные с поведением масштабируемого фильтра Блума, отслеживая количество созданных срезов и потребление памяти с течением времени. Это источник полезной информации о закономерностях использования фильтра и необходимости корректировок.
Избегайте очень маленьких значений fpGrowth, иначе придется часто добавлять срезы фильтра, увеличивая расход памяти и потенциально способствуя возникновению узких мест производительности, поскольку функции Test необходимо проверять больше срезов.
В распределенных системах, где необходима согласованность узлов, все экземпляры инициализируйте одинаковыми параметрами и обрабатывайте обновления для одинаковой фильтрации срезов.
Как и в случае с любым фильтром Блума, при использовании нескольких независимых хеш-функций распределение элементов в наборе битов улучшается. В масштабируемом фильтре Блума при добавлении дополнительных уровней этим хеш-функциям нужно сохранять свои свойства.

Добавление и тестирование значений

// Функцией «Add» данный элемент вставляется в масштабируемый фильтр Блума.
// // Если текущий срез фильтра превышает его емкость исходя из скорости роста, добавляется новый срез.
func (sbf *ScalableBloomFilter) Add(data []byte) {
 // Элемент добавляется ко всем имеющимся срезам фильтра.
 for _, filter := range sbf.filters {
  for i := uint64(0); i < filter.k; i++ {
   filter.Add(data)
  }
 }

 // Общее количество элементов, добавленных во все срезы фильтра, увеличивается.
 sbf.n++

 // Емкость последнего фильтра проверяется, и при необходимости добавляется новый срез фильтра.
 // В текущей реализации добавляются только новые фильтры, а не предыдущие.
 // Нужно основывать условие на свойствах последнего фильтра и текущем количестве добавленных элементов.
 currentFilter := sbf.filters[len(sbf.filters)-1] // Получается самый последний фильтр

 // Чтобы определить, когда добавлять новый фильтр, используется это корректное пороговое значение.
 // Это пороговое значение определяется тем, насколько заполнен текущий фильтр.
 currentCapacity := float64(currentFilter.m) * math.Log(sbf.fpGrowth) / math.Log(2)
 // Если количество элементов превышает текущую емкость фильтра:
 if float64(sbf.n) > currentCapacity {
  newFpRate := sbf.fpRate * math.Pow(sbf.fpGrowth, float64(len(sbf.filters)))
  // Новый срез фильтра создается и добавляется.
  nbf, _ := NewBloomFilter(sbf.n, newFpRate)
  sbf.filters = append(sbf.filters, nbf)
 }
}

func (sbf *ScalableBloomFilter) Test(data []byte) bool {
 // Элемент проверяется по всем срезам фильтра от старейшего до новейшего.
 for _, filter := range sbf.filters {
  // Предполагается, что элемент присутствует в фильтре, пока не доказано обратное.
  isPresent := true

  // // Используются те же хеш-функции, которые применялись для добавления элемента.
  for i := uint64(0); i < filter.k; i++ {
   // Если какой-либо из битов, соответствующих хеш-значениям элемента, не задан, его точно нет в этом фильтре.
   if !filter.Test(data) {
    isPresent = false
    // Мы выходим из цикла хеш-функции, как только находим незаданный бит.
    break
   }
  }

  // Если все биты для этого фильтра заданы, элемент потенциально присутствует, с некоторым процентом ложноположительных результатов.
  if isPresent {
   return true
  }
  // В противном случае продолжается проверка следующего фильтра, не присутствует ли там этот элемент.
 }

 // Если ни в одном из фильтров не заданы все биты, элемента во множестве точно нет.
 return false
}

Добавление элементов, функция «Add»

Распределение по уровням. При добавлении элемент добавляется во все имеющиеся уровни фильтра Блума. Так элемент гарантированно отслеживается независимо от того, насколько увеличивается масштабируемый фильтр.
Подсчет элементов. В фильтре поддерживается подсчет всех добавленных элементов n. Это очень важно для понимания, когда добавлять новый уровень.
Проверка емкости и расширения:
Фильтром проверяется, не превышена ли емкость текущего, самого последнего уровня для поддержания желаемого процента ложноположительных результатов.
Если текущий уровень признается заполненным, исходя из currentCapacity, которым учитывается fpGrowth, создается и добавляется к фильтру новый уровень фильтра Блума.
У этого нового уровня более высокий процент ложноположительных результатов, рассчитанный на основе исходного fpRate и количества имеющихся уровней. Коэффициентом fpGrowth определяется, насколько увеличиваются ложноположительные результаты с каждым новым уровнем.

Тестирование на наличие элементов, функция «Test»

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

Управление ложноположительными результатами

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

Сферы применения фильтра

Сетевая безопасность. В области кибербезопасности фильтрами Блума быстро проверяется, состоит ли IP-адрес или домен в черном списке, при этом эффективно отфильтровывается вредоносный трафик.
Механизмы веб-кеширования. Фильтры Блума используются веб-браузерами или прокси-серверами для определения, кеширован ли веб-ресурс, при этом сокращается количество ненужных сетевых запросов, ускоряется веб-серфинг.
Оптимизация запросов к базе данных. Фильтры Блума применяются базами данных для проверки того, хранится ли результат запроса в кеше, так за счет исключения лишних запросов снижается нагрузка на сервер базы данных.
Проверка орфографии. Фильтры Блума применяются текстовыми редакторами и программами редактирования текстов для быстрой проверки наличия слова в словаре, слова с ошибками ими выявляются мгновенно.
Предотвращение атаки Сивиллы в одноранговых сетях. В одноранговых сетях за счет эффективной проверки принадлежности узла сети фильтрами Блума обнаруживаются и предотвращаются атаки Сивиллы.
Блокчейн и криптовалюта. Блокчейн-приложениями вроде Bitcoin фильтры Блума применяются для эффективной синхронизации и проверки транзакций без загрузки всего блокчейна.
Системы противодействия мошенничеству. Финансовыми учреждениями фильтры Блума используются для отслеживания транзакций или запросов доступа к счетам на предмет соответствия известным схемам мошенничества или спискам скомпрометированных счетов.
Защита от спама и фишинга. Почтовыми серверами фильтры Блума используются для отфильтровывания спама или фишинговых писем путем проверки входящих сообщений на соответствие списку известных характеристик спама.
Биоинформатика. При геномном секвенировании фильтры Блума приходятся кстати для выполнения быстрых запросов в большие базы данных ДНК и выявления последовательности генов без исчерпывающего поиска.
Распределенные системы и большие данные. В крупномасштабных распределенных системах фильтрами Блума осуществляется эффективное управление распределением и репликацией данных, обеспечивается оптимальное выполнение таких операций, как разделение данных и балансировка нагрузки.

Заключение

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

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