Фильтр Блума (BloomFilter) расширенных тем Redis

Redis
Фильтр Блума (BloomFilter) расширенных тем Redis

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

1. Познакомьтесь с BloomFilter

1.1 Принцип

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

Давайте посмотрим, как фильтр Блума определяет, что элементы находятся в коллекции, как показано ниже:

Есть три хэш-функции и битовый массив.Оракул проходит через три хеш-функции и получает 1-й, 4-й и 5-й биты равными 1. Точно так же база данных получает 2, 5 и 10 битов 1, поэтому, если нам нужно Чтобы определить, находится ли оракул в этом битовом массиве, используется хеш-функция, чтобы определить, равны ли все биты 1, 4 и 5 битового массива 1. Если все они равны 1, считается, что оракул находится в этом бите. массив, и база данных такая же. Вот как фильтр Блума определяет, входит ли элемент в набор.

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

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

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

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

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

Подводя итог, постучим по доске:

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

1.2 Сценарии применения

  • База данных не позволяет пройти через библиотеку. Google Bigtable, HBase и Cassandra, а также Postgresql используют BloomFilter, чтобы сократить количество операций поиска на диске для несуществующих строк или столбцов. Избегание дорогостоящих обращений к диску значительно повышает производительность операций запросов к базе данных.
  • В бизнес-сценариях оценка того, прочитал ли пользователь определенное видео или статью, например Douyin или Toutiao, конечно, приведет к определенным ошибкам, но не позволит пользователям увидеть дублированный контент. В социальной сцене, похожей на игру, с которой я сталкивался ранее, мне нужно определить, находится ли пользователь в игре.Если да, то содержимое игры необходимо обновить.Вы также можете использовать фильтр Блума, чтобы уменьшить количество раз, когда отсутствующий пользователь запрашивает базу данных или кеш.
  • В сценарии простоя кеша и поломки кеша обычно оценивается, находится ли пользователь в кеше, если да, то результат будет возвращен напрямую, если нет, то будет опрошен БД, если волна холодных данных приходит, это вызовет большое количество поломок кеша и вызовет лавинный эффект. В это время вы можете Фильтр Блума используется в качестве кэшированного индекса. Только в фильтре Блума можно запросить кеш. Если он не запрашивается, он проникнет в БД. Если не в шароварах, возвращайтесь напрямую.
  • Перехватчик WEB, если один и тот же запрос перехватывается, чтобы предотвратить повторные атаки. Когда пользователь запрашивает в первый раз, параметры запроса помещаются в фильтр Блума.Когда пользователь запрашивает во второй раз, сначала оценивается, попали ли параметры запроса в фильтр Блума. Может улучшить скорость попадания в кэш.

1.3 Практический фильтр Блума

В соответствии с принципом фильтра Блума мы можем вручную реализовать фильтр Блума в Python. Сначала нужно установитьmmh3, mmh3 — это реализация алгоритма MurmurHash3, который также используется в Redis. Тогда также нужно установитьbitarray, реализация медианных массивов на Python.

pip install mmh3
pip install bitarray

После подготовки окружения приступайте к реализации фильтра Блума и переходите непосредственно к коду

# python 3.6  simple_bloomfilter.py
import mmh3
from bitarray import bitarray

class BloomFilter(object):
    def __init__(self, bit_size=10000, hash_count=3, start_seed=41):
        self.bit_size = bit_size
        self.hash_count = hash_count
        self.start_seed = start_seed
        self.initialize()

    def initialize(self):
        self.bit_array = bitarray(self.bit_size)
        self.bit_array.setall(0)

    def add(self, data):
        bit_points = self.get_hash_points(data)
        for index in bit_points:
            self.bit_array[index] = 1

    def is_contain(self, data):
        bit_points = self.get_hash_points(data)
        result = [self.bit_array[index] for index in bit_points]
        return all(result)

    def get_hash_points(self, data):
        return [
            mmh3.hash(data, index) % self.bit_size
            for index in range(self.start_seed, self.start_seed +
                               self.hash_count)
        ]

Полный код задокументирован вGitHub.com/VP предлагает/Job-Job-Day…

Приведенный выше код реализует класс BloomFilter, инициализирует три переменные: размер битового массива bit_size, количество хеш-функций hash_count и начальное случайное начальное число хэша start_seed.

Реализованы два метода: метод add предназначен для получения разных битов в соответствии с данными с помощью нескольких хеш-функций, установки соответствующей позиции в битовом массиве в 1, а метод is_contain предназначен для определения того, находятся ли данные в BloomFilter.

Протестируйте код:

>>> from simple_bloomfilter import BloomFilter
>>> bloomFilter = BloomFilter(1000000, 6)
>>> bloomFilter.add('databases')
>>> bloomFilter.add('bloomfilter')
>>> bloomFilter.is_contain('databases')
True
>>> bloomFilter.is_contain('bloomfilter')
True
>>> bloomFilter.is_contain('bloomfilte')
False

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

2. Практика Redis-BloomFilter

Redis запущен в версии 4.0moduleФорма, модуль могут реализовывать некоторые возможности Redis в виде дополнительных плагинов. Официальный сайт рекомендовалRedisBloomМодуль как фильтр Блума Redis.

Помимо этого, есть и другие способы добиться этого, которые перечислены ниже:

Давайте потренируем их один за другим.

2.1 RedisBloom

Предварительно необходимо установить RedisBloom, для установки рекомендуется использовать Docker, это просто и удобно:

docker pull redislabs/rebloom:latest
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
docker exec -it redis-redisbloom bash
# redis-cli
# 127.0.0.1:6379> bf.add tiancheng hello

Конечно, вы также можете скомпилировать и установить напрямую:

git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make //编译 会生成一个rebloom.so文件
redis-server --loadmodule /path/to/rebloom.so
redis-cli -h 127.0.0.1 -p 6379

Этот модуль не только реализует фильтр Блума, но и реализует CuckooFilter (фильтр с кукушкой), а также функцию TopK. Основанный на BloomFilter, CuckooFilter в основном устраняет тот недостаток, что BloomFilter нельзя удалить. Давайте сначала рассмотрим BloomFilter, а затем представим CuckooFilter.

2.1.1 Операции, связанные с BloomFilter

Для начала ознакомимся с основными инструкциями фильтра Блума:

  • bf.add добавляет элемент в фильтр Блума
  • bf.exists определяет, находится ли элемент в фильтре Блума
  • bf.madd добавляет несколько элементов в фильтр Блума, bf.add может добавить только один
  • bf.mexists определяет, находятся ли несколько элементов в фильтре Блума
127.0.0.1:6379> bf.add tiancheng tc01
(integer) 1
127.0.0.1:6379> bf.add tiancheng tc02
(integer) 1
127.0.0.1:6379> bf.add tiancheng tc03
(integer) 1
127.0.0.1:6379> bf.exists tiancheng tc01
(integer) 1
127.0.0.1:6379> bf.exists tiancheng tc02
(integer) 1
127.0.0.1:6379> bf.exists tiancheng tc03
(integer) 1
127.0.0.1:6379> bf.exists tiancheng tc04
(integer) 0
127.0.0.1:6379> bf.madd tiancheng tc05 tc06 tc07
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists tiancheng tc05 tc06 tc07 tc08
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

2.1.2 Частота ложноположительных результатов теста

Далее, давайте проверим частоту ложных срабатываний:

import redis
client = redis.StrictRedis()

client.delete("tiancheng")
size = 100000
count = 0
for i in range(size):
    client.execute_command("bf.add", "tiancheng", "tc%d" % i)
    result = client.execute_command("bf.exists", "tiancheng", "tc%d" % (i + 1))
    if result == 1:
        # print(i)
        count += 1

print("size: {} , error rate: {}%".format(
    size, round(count / size * 100, 5)))

Результаты теста следующие:

➜  BloomFilter git:(master) ✗ python redisbloom_test.py
size: 1000 , error rate: 1.0%
➜  BloomFilter git:(master) ✗ python redisbloom_test.py
size: 10000 , error rate: 1.25%
➜  BloomFilter git:(master) ✗ python redisbloom_test.py
size: 100000 , error rate: 1.304%

Если размер = 1000, будет 1% ложных срабатываний. Чем выше размер, тем выше ложные срабатывания. Есть ли способ контролировать ложные срабатывания? Ответ - да.

На самом деле фильтр Блума предоставляет пользовательские параметры, ранее использовались параметры по умолчанию, а также в этом модуле есть командаbf.reserve, предоставляет три параметра: key, error_rate и initial_size. Чем ниже частота ошибок, тем больше требуется места. Параметр initial_size указывает количество элементов, которые, как ожидается, будут помещены в фильтр Блума. Когда фактическое число превышает это значение, частота ложных срабатываний будет увеличиваться. Параметры по умолчанию: error_rate=0.01, initial_size=100.

Следующий тест:

import redis
client = redis.StrictRedis()

client.delete("tiancheng")
size = 10000
count = 0
client.execute_command("bf.reserve", "tiancheng", 0.001, size) # 新增
for i in range(size):
    client.execute_command("bf.add", "tiancheng", "tc%d" % i)
    result = client.execute_command("bf.exists", "tiancheng", "tc%d" % (i + 1))
    if result == 1:
        #print(i)
        count += 1

print("size: {} , error rate: {}%".format(
    size, round(count / size * 100, 5)))

Добавьте новую строку кода, чтобы просто проверить эффект:

➜  BloomFilter git:(master) ✗ python redisbloom_test.py
size: 10000 , error rate: 0.0%
➜  BloomFilter git:(master) ✗ python redisbloom_test.py
size: 100000 , error rate: 0.001%

Количество ложноположительных результатов мгновенно сократилось более чем в 1000 раз.

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

Если имеется 10 миллионов данных, частота ложных срабатываний может составлять 1%, и потребуется около 11 миллионов данных, как показано на следующем рисунке:

Если требуется, чтобы показатель ложных срабатываний составлял 0,1%, потребуется около 17 М.

Но это пространство намного меньше, чем при непосредственном использовании набора для хранения 10 миллионов данных.

2.1.3 Расширенное обучение

Модуль RedisBloom также реализует фильтр кукушки, у меня есть краткое представление о нем, есть статья, которую вы можете прочитать, если вас интересует общение.У-у-у. В это время. Растения. Квота/~Большой кофе/бумаги…

В статье сравнивается фильтр Блума и фильтр с кукушкой По сравнению с фильтром с кукушкой фильтр Блума имеет следующие недостатки:

  • Слабая производительность запросов Низкая производительность запросов связана с тем, что фильтру Блума необходимо использовать N хэш-функций для вычисления N различных точек в битовом массиве.Эти точки имеют большой диапазон в памяти, что приводит к низкой частоте попаданий в кэш ЦП.
  • Неэффективное использование пространства При той же частоте ложных срабатываний коэффициент использования пространства кукушки выше, чем у фильтра Блума, что может сэкономить около 40%.
  • Операция удаления не поддерживается Это самая большая оптимизация фильтра кукушки по сравнению с фильтром Блума, он поддерживает обратные операции и функции удаления.
  • подсчет не поддерживается

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

2.2 pyreBloom

pyreBloom — это модуль Redis + BloomFilter на Python, реализованный на языке c. Если вы чувствуете, что развертывание модуля Redis очень проблематично или версия Redis в онлайн-среде не 4.0 или выше, вы можете использовать это, но оно основано на аирдисе, вам нужно установить аирдис и не поддерживает повторное подключение и повторная попытка, если вы используете его в производстве, в среде требуется простая инкапсуляция.

Установить:

git clone https://github.com/redis/hiredis.git src/hiredis && \
cd src/hiredis && make && make PREFIX=/usr install && ldconfig

// mac  brew install hiredis
git clone https://github.com/seomoz/pyreBloom src/pyreBloom && \
cd src/pyreBloom && python setup.py install

Демонстрационный код:

from pyreBloom import pyreBloom

redis_conf = {'host': '127.0.0.1', 'password': '', 'port': 6379, 'db': 0}

for k, v in redis_conf.items():
    redis_conf = convert_utf8(redis_conf)

key = convert_utf8('tc')
value = convert_utf8('hello')

p = pyreBloom(key, 10000, 0.001, **redis_conf)
p.add(value)
print(p.contains(value))

2.3 Родной язык + реализация Redis

Родной язык Python относительно медленный.Если это язык Go, если вы не можете найти подходящий redis BloomFilter с открытым исходным кодом, вы можете использовать родной язык + операции, связанные с растровыми изображениями redis, чтобы реализовать его самостоятельно. На языке Java есть реализация в проекте RedisBloomJReBloom, из-за не-Java-разработчиков, вы можете понять это сами.

В этой демонстрации используется язык Python, а версия на языке Go будет добавлена, когда будет время:

# python3.6 bloomfilter_py_test.py
import mmh3
import redis


class BloomFilter(object):
    def __init__(self, bf_key, bit_size=10000, hash_count=3, start_seed=41):
        self.bit_size = bit_size
        self.hash_count = hash_count
        self.start_seed = start_seed
        self.client = redis.StrictRedis()
        self.bf_key = bf_key

    def add(self, data):
        bit_points = self._get_hash_points(data)
        for index in bit_points:
            self.client.setbit(self.bf_key, index, 1)

    def madd(self, m_data):
        if isinstance(m_data, list):
            for data in m_data:
                self.add(data)
        else:
            self.add(m_data)

    def exists(self, data):
        bit_points = self._get_hash_points(data)
        result = [
            self.client.getbit(self.bf_key, index) for index in bit_points
        ]
        return all(result)

    def mexists(self, m_data):
        result = {}
        if isinstance(m_data, list):
            for data in m_data:
                result[data] = self.exists(data)
        else:
            result[m_data] = self.exists[m_data]
        return result

    def _get_hash_points(self, data):
        return [
            mmh3.hash(data, index) % self.bit_size
            for index in range(self.start_seed, self.start_seed +
                               self.hash_count)
        ]

вышеsimple_bloomfilter.pyОснова для внедрения redissetbitиgetbit, заменяя битовый массив. При этом реализованы методы madd и mexists, аналогичные BloomFilter.Результаты тестирования следующие:

>>> from bloomfilter_py_test import BloomFilter
>>> bf_obj = BloomFilter('bf.tc')
>>> bf_obj.add('tc01')
>>> bf_obj.madd('tc02')

>>> bf_obj.madd(['tc03', 'tc04'])
>>> bf_obj.exists('tc01')
True
>>> bf_obj.mexists(['tc02', 'tc03', 'tc04', 'tc05'])
{'tc02': True, 'tc03': True, 'tc04': True, 'tc05': False}

Здесь отрабатывается соответствующий контент фильтра Блума. Соответствующий код находится вGitHub.com/VP предлагает/Job-Job-Day…

Для получения дополнительных статей и обсуждений, связанных с Redis, обратите внимание на общедоступный аккаунт: «Tiancheng Technology Talk».

Категории