50 лет технологии - фильтр Блума

Java

предисловие

О лавине кеша, проникновении и выходе из строя Redis мы уже говорили. В статье мы говорили, что одним из способов решения проблемы проникновения в кэш является布隆过滤器, но в прошлый раз я не говорил о том, как использовать фильтр Блума.

Как теплый человек, я восполню тебя, пожалуйста, позвони мнеIT老暖男.

Что такое фильтр Блума

Фильтр Блума был предложен молодым человеком по имени Блум в 1970 году. С тех пор прошло пятьдесят лет, и он так же стар, как мой брат.

На самом деле это длинный двоичный вектор и ряд функций случайного отображения.Каждый должен знать, что двоичные данные равны либо 0, либо 1, а значение по умолчанию равно 0.

В основном используется для определения того, находится ли элемент в наборе, 0 означает不存在Некоторые данные, 1 представляет存在некоторые данные.

понимать? в виде暖男Мой брат рисует для вас картинку, чтобы вы поняли:

Фильтр Блума использует

  • Устранение проникновения в кэш Redis (сосредоточьтесь на сегодняшнем дне)

  • При сканировании URL-адрес поискового робота фильтруется. URL-адрес, который уже существует в Bloom, не сканируется.

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

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

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

процесс депозита

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

  • Вычислить данные с помощью K хеш-функций и вернуть K вычисленных хеш-значений.

  • Эти K хэш-значений сопоставляются с соответствующими K индексами двоичного массива.

  • Измените двоичные данные, соответствующие индексам K, на 1.

Например, если первая хэш-функция возвращает x, а вторая и третья хеш-функции возвращают y и z, то: двоичный код, соответствующий X, Y и Z, изменяется на 1.

как показано на рисунке:

процесс запроса

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

  • Данные рассчитываются с помощью K хэш-функций, соответствующих рассчитанным K хеш-значениям.

  • Найдите соответствующий индекс двоичного массива по хэш-значению

  • Суждение: если есть позиция, где двоичные данные равны 0, то данные не существуют. Если оба равны 1, данные существуют в коллекции. (Здесь есть недостатки, о которых будет сказано ниже)

удалить процесс

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

Преимущества и недостатки фильтров Блума

преимущество

  • Поскольку он хранит двоичные данные, он занимает очень мало места.

  • Скорость вставки и запроса очень высока, а временная сложность O (K). Вы можете думать о процессе HashMap.

  • Конфиденциальность хороша тем, что не хранит никаких необработанных данных, только двоичные данные.

недостаток

Это возвращает нас к упомянутым выше недостаткам.

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

Например, "你好"и"hello", если хэш-значение, наконец, будет рассчитано как то же самое, то они изменят двоичные данные того же индекса на 1.

В настоящее время вы не знаете, представляет ли двоичный индекс 2 "你好"еще"hello".

Это приводит к следующим недостаткам:

1. Неверное суждение

Если изображение выше не существует"hello", только сохранено"你好", затем используйте"hello«Когда вы придете спрашивать, вы будете судить»hello"Есть в коллекции.

потому что"你好"и"hello«Значение хеш-функции такое же, через одно и то же значение хеш-функции, найденные двоичные данные одинаковы, все 1.

2. Сложность удаления

Я не буду говорить это здесь, все должны понять, почему, как вы暖男老哥, Давайте поговорим об этом.

Все еще используя приведенный выше пример, потому что "你好"и"hello"имеет такое же хэш-значение, и соответствующий индекс массива также одинаков.

В это время мой брат хочет удалить "你好», нижний индекс — это двоичные данные в 2, которые изменяются с 1 на 0.

Так мы даже "hello"Удалил все вместе. (0 значит есть эти данные, 1 значит нет таких данных)

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

Реализовать фильтр Блума

Существует множество реализаций, одна из которых — реализация, предоставляемая Guava.

1. Представьте конфигурацию Guava pom 

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>29.0-jre</version>
</dependency>

Во-вторых, реализация кода

Кстати, здесь мы измеряем уровень ложных срабатываний.

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterCase {

  /**
   * 预计要插入多少数据
   */
  private static int size = 1000000;

  /**
   * 期望的误判率
   */
  private static double fpp = 0.01;

  /**
   * 布隆过滤器
   */
  private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);


  public static void main(String[] args) {
    // 插入10万样本数据
    for (int i = 0; i < size; i++) {
      bloomFilter.put(i);
    }

    // 用另外十万测试数据，测试误判率
    int count = 0;
    for (int i = size; i < size + 100000; i++) {
      if (bloomFilter.mightContain(i)) {
        count++;
        System.out.println(i + "误判了");
      }
    }
    System.out.println("总共的误判数:" + count);
  }
}

результат операции:

На 100 000 данных приходится 947 ложных срабатываний, что составляет около 0,01%, что является частотой ложных срабатываний, установленной в нашем коде: fpp = 0,01.

Копайте глубже в код

основнойBloomFilter.createметод

@VisibleForTesting
  static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
    。。。。
}

Здесь четыре параметра:

  • funnel: тип данных (обычно вызывается в классе инструментов Funnels)

  • expectedInsertions: ожидаемое количество значений для вставки

  • fpp: частота ложных срабатываний (по умолчанию 0,03)

  • strategy: хеш-алгоритм

Давайте сосредоточимся наfppпараметр

частота ложных срабатываний fpp

Сценарий 1:fpp = 0.01

  • Количество ложных срабатываний: 947

  • Занять объем памяти: 9585058 цифр

Сценарий второй:fpp = 0.03(параметр по умолчанию)

  • Количество ложных срабатываний: 3033

  • Занимаемый объем памяти: 7298440 цифр

Резюме сценария

  • Ложноположительный показатель может быть передан черезfppпараметры для настройки

  • Чем меньше fpp, тем больше требуется памяти: для 0,01 требуется более 9 миллионов цифр, а для 0,03 требуется более 7 миллионов цифр.

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

надnumBits, что означает, что для хранения одного миллиона чисел типа int необходимо количество цифр 7298440, более 7 миллионов цифр. Теоретически хранится один миллион чисел.Int составляет 4 байта и 32 бита, что требует 481000000 = 32 миллиона бит. Если для хранения используется HashMap, согласно 50-процентной эффективности хранения HashMap требуется 64 миллиона битов. Видно, что место для хранения BloomFilter очень мало, всего около 1/10 от HashMap.

надnumHashFunctionsУказывает, что требуется несколько операций хэш-функции для сопоставления различных индексов, чтобы сохранить, существуют ли эти числа (0 или 1).

Брат здесь, я собрал последние вопросы интервью BAT в 2020 году, включая различные технические области Java, которые очень всеобъемлющи, в общей сложности более 80 документов в формате PDF.

Категории