Фильтр Блума, не сложный

Java
Фильтр Блума, не сложный

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

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

Обычно мы сталкиваемся со многими бизнес-сценариями, где нам нужно определить, находится ли элемент в определенном наборе.Как правило, мы думаем о сохранении всех элементов в наборе, а затем подтверждаем их сравнением. Связанные списки, деревья, хэш-таблицы (также известные как хэш-таблицы, Hash-таблицы) и другие структуры данных — все это так. Но по мере увеличения количества элементов в коллекции необходимое нам пространство для хранения также будет расти линейно, в конечном итоге достигая узкого места. В то же время скорость поиска становится все медленнее и медленнее.Сложность времени поиска трех вышеуказанных структур составляет:O(n)O(n),O(logn)O(logn),O(1)O(1).

В это время появился фильтр Блума (Bloom Filter).

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

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

хэш-функция

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

Все хеш-функции обладают следующими основными свойствами:

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

  • Вход и выход хэш-функции не являются однозначно соответствующими. Если два значения хеш-функции одинаковы, два входных значения, вероятно, будут одинаковыми, но они также могут быть разными. Эта ситуация называется ""хэш-коллизия(столкновение)».

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

Структура данных фильтра Блума

BloomFilter состоит из двоичного вектора или растрового изображения фиксированного размера и ряда функций отображения.

В начальном состоянии для битового массива длины m все его биты установлены в 0, как показано на следующем рисунке:

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

При запросе переменной нам нужно только посмотреть, все ли эти точки равны 1, и мы можем с высокой вероятностью узнать, есть ли она в наборе

  • Если любая из этих точек равна 0, запрашиваемая переменная должна отсутствовать;
  • Если оба равны 1, запрашиваемая переменная оченьЭто может существовать

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

ложноположительный показатель

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

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

характеристика

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

Шаги добавления и запроса элемента

добавить элемент

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

элемент запроса

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

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

По сравнению с другими структурами данных фильтры Блума имеют огромные преимущества в пространстве и времени. Объем памяти фильтра Блума и время вставки/запроса являются постоянными.O(K)O(K), кроме того, хеш-функции не имеют отношения друг к другу, что удобно для параллельной реализации аппаратно. Фильтрам Блума не нужно хранить сам элемент, и они полезны в некоторых случаях, когда требуется очень строгая конфиденциальность.

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

недостаток

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

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

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

Сценарии и примеры использования фильтра Блума

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

Например, дедупликация URL-адресов веб-страниц, идентификация спама, оценка повторяющихся элементов в больших коллекциях и проникновение в кэш.

Типичные области применения фильтров Блума:

  • База данных не позволяет пройти через библиотеку. Google Bigtable, HBase и Cassandra, а также Postgresql используют BloomFilter, чтобы сократить количество операций поиска на диске для несуществующих строк или столбцов. Избегание дорогостоящих обращений к диску значительно повышает производительность операций запросов к базе данных.

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

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

  • Перехватчик WEB, если один и тот же запрос перехватывается, чтобы предотвратить повторные атаки. Когда пользователь запрашивает в первый раз, параметры запроса помещаются в фильтр Блума.Когда пользователь запрашивает во второй раз, сначала оценивается, попали ли параметры запроса в фильтр Блума. Может улучшить скорость попадания в кэш. Кэш-сервер веб-прокси Squid использует фильтры Блума в своих дайджестах кеша. Google Chrome использует фильтр Блума для ускорения безопасного просмотра

  • Система хранения документов Venti также использует фильтры Блума для обнаружения ранее сохраненных данных.

  • Детектор модели SPIN также использует фильтры Блума для отслеживания достижимых пространств состояний при проверке проблем в масштабе.

Coding~

Зная принцип и сценарии использования фильтра Блума, мы можем реализовать простой фильтр Блума самостоятельно.

Пользовательский фильтр Блум

public class MyBloomFilter {

    /**
     * 一个长度为10 亿的比特位
     */
    private static final int DEFAULT_SIZE = 256 << 22;

    /**
     * 为了降低错误率，使用加法hash算法，所以定义一个8个元素的质数数组
     */
    private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};

    /**
     * 相当于构建 8 个不同的hash算法
     */
    private static HashFunction[] functions = new HashFunction[seeds.length];

    /**
     * 初始化布隆过滤器的 bitmap
     */
    private static BitSet bitset = new BitSet(DEFAULT_SIZE);

    /**
     * 添加数据
     *
     * @param value 需要加入的值
     */
    public static void add(String value) {
        if (value != null) {
            for (HashFunction f : functions) {
                //计算 hash 值并修改 bitmap 中相应位置为 true
                bitset.set(f.hash(value), true);
            }
        }
    }

    /**
     * 判断相应元素是否存在
     * @param value 需要判断的元素
     * @return 结果
     */
    public static boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (HashFunction f : functions) {
            ret = bitset.get(f.hash(value));
            //一个 hash 函数返回 false 则跳出循环
            if (!ret) {
                break;
            }
        }
        return ret;
    }

    /**
     * 模拟用户是不是会员，或用户在不在线。。。
     */
    public static void main(String[] args) {

        for (int i = 0; i < seeds.length; i++) {
            functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
        }

        // 添加1亿数据
        for (int i = 0; i < 100000000; i++) {
            add(String.valueOf(i));
        }
        String id = "123456789";
        add(id);

        System.out.println(contains(id));   // true
        System.out.println("" + contains("234567890"));  //false
    }
}

class HashFunction {

    private int size;
    private int seed;

    public HashFunction(int size, int seed) {
        this.size = size;
        this.seed = seed;
    }

    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        int r = (size - 1) & result;
        return (size - 1) & result;
    }
}

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

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

BloomFilter в Гуаве

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>23.0</version>
</dependency>

public class GuavaBloomFilterDemo {

    public static void main(String[] args) {
        //后边两个参数：预计包含的数据量，和允许的误差值
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 100000, 0.01);
        for (int i = 0; i < 100000; i++) {
            bloomFilter.put(i);
        }
        System.out.println(bloomFilter.mightContain(1));
        System.out.println(bloomFilter.mightContain(2));
        System.out.println(bloomFilter.mightContain(3));
        System.out.println(bloomFilter.mightContain(100001));

        //bloomFilter.writeTo();
    }
}

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

Конечно, мы также можем передать фильтр Блума черезbloomFilter.writeTo()Напишите файл и поместите его в объектное хранилище, такое как OSS и S3.

BloomFilter в Redis

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

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

При условии, что Redis установлен, есть два способа установить RedisBloom.

Скомпилируйте и установите напрямую

git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make     #编译 会生成一个rebloom.so文件
redis-server --loadmodule /path/to/rebloom.so   #运行redis时加载布隆过滤器模块
redis-cli    # 启动连接容器中的 redis 客户端验证

Установить с помощью Докера

docker pull redislabs/rebloom:latest # 拉取镜像
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest #运行容器
docker exec -it redis-redisbloom bash
redis-cli

использовать

Основные инструкции фильтра Блума:

  • bf.add добавляет элемент в фильтр Блума
  • bf.exists определяет, находится ли элемент в фильтре Блума
  • bf.madd добавляет несколько элементов в фильтр Блума, bf.add может добавить только один
  • bf.mexists определяет, находятся ли несколько элементов в фильтре Блума
127.0.0.1:6379> bf.add user Tom
(integer) 1
127.0.0.1:6379> bf.add user John
(integer) 1
127.0.0.1:6379> bf.exists user Tom
(integer) 1
127.0.0.1:6379> bf.exists user Linda
(integer) 0
127.0.0.1:6379> bf.madd user Barry Jerry Mars
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists user Barry Linda
1) (integer) 1
2) (integer) 0

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

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

Redis также предоставляет фильтры Блума с настраиваемыми параметрами.bf.reserve 过滤器名 error_rate initial_size

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

Но эту операцию необходимо создать явно перед добавлением. Если соответствующий ключ уже существует, bf.reserve сообщит об ошибке

127.0.0.1:6379> bf.reserve user 0.01 100
(error) ERR item exists
127.0.0.1:6379> bf.reserve topic 0.01 1000
OK

Я Javaer, и я должен использовать Java для его реализации. Существует много клиентов Redis на Java, и некоторые из них еще не предоставляют механизм расширения инструкций. Я знаю, что Redisson и салат могут использовать фильтры Блума. Здесь мы используемRedisson

public class RedissonBloomFilterDemo {

    public static void main(String[] args) {

        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        RedissonClient redisson = Redisson.create(config);

        RBloomFilter<String> bloomFilter = redisson.getBloomFilter("user");
        // 初始化布隆过滤器，预计统计元素数量为55000000，期望误差率为0.03
        bloomFilter.tryInit(55000000L, 0.03);
        bloomFilter.add("Tom");
        bloomFilter.add("Jack");
        System.out.println(bloomFilter.count());   //2
        System.out.println(bloomFilter.contains("Tom"));  //true
        System.out.println(bloomFilter.contains("Linda"));  //false
    }
}

расширять

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

Из-за меньшего использования мы пока не будем вдаваться в подробности.

Статья постоянно обновляется, вы можете искать в WeChat "JavaKeeper"Прочитайте ее в первый раз, получите более 500 электронных книг и более 30 обучающих видео и исходный код без каких-либо процедур, эта статьяGitHub github.com/JavaKeeperОн был включен, разработка Javaer, спектр основных навыков интервью, есть то, что вы хотите.

Ссылка и спасибо

У-у-у. В это время. Растения. Квота/~Большой кофе/бумаги…

Woohoo. Просто сделайте java.com/2019/10/22/…

Блог Woo Woo.cn на.com/CPS Elvis/Afraid/…

nuggets.capable/post/684490…

Категории