1. Фильтр Блума
Сегодня мы обычно используем Toutiao, и Toutiao будет рекомендовать нам новый контент.Каждый раз, когда он рекомендует, ему приходится пересматривать и удалять контент, который уже был просмотрен. Вопрос в том, как реализовать push-дедупликацию?
Подсознательно мы будем помнить, что мы записываем новости, рекомендованные пользователям, в базу данных.Прежде чем рекомендовать пользователям, мы сначала проверяем таблицу записей, чтобы увидеть, были ли они рекомендованы.
Есть проблема: когда объем данных высок, база данных не может ее удерживать.
В это время некоторые друзья скажут, что я храню их в Redis, а когда объем данных в Redis велик, они будут занимать много места, что не является хорошим решением.
Фильтр Блума можно понимать как неточную структуру набора, когда вы используете его метод contains для определения существования объекта, он может неправильно оценить. Тем не менее, фильтр Блума не отличается особой неточностью: при разумных настройках параметров его точностью можно управлять достаточно точно, и вероятность неправильной оценки будет лишь небольшой.
Когда фильтр Блума говорит, что значение существует, это значение, вероятно, не существует; когда он говорит, что это не так, оно определенно не существует..
Фильтр Блума может точно отфильтровать контент, который был просмотрен, и новый контент, который еще не был просмотрен.Он также отфильтрует очень небольшую часть (ошибочное суждение), но он может точно идентифицировать подавляющее большинство нового контента. Таким образом, полностью гарантируется, что рекомендуемый пользователю контент не будет повторяться.
Фильтр Блума, официально предоставленный Redis, официально не дебютировал до тех пор, пока Redis 4.0 не предоставил функцию подключаемого модуля. Фильтры Блума загружаются в Redis Server в виде подключаемого модуля., который предоставляет Redis мощную функцию дедупликации Bloom.
2. Основное использование
bf.add добавляет элемент, а bf.exists запрашивает, существует ли этот элемент.
Установка плагина фильтра Блума
[root@izuf65itgtxe1lpfpb***** redis]# git clone https://github.com/RedisBloom/RedisBloom.git
[root@izuf65itgtxe1lpfpb***** redis]# cd RedisBloom/
[root@izuf65itgtxe1lpfpb***** RedisBloom]# make
[root@izuf65itgtxe1lpfpb***** RedisBloom]# vi /usr/local/redis/redis.conf
## 增加配置
loadmodule /usr/local/redis/RedisBloom/redisbloom.so
## 重启redis就行
127.0.0.1:6379> bf.add bloomFilterKey user1
(integer) 1
127.0.0.1:6379> bf.add bloomFilterKey user2
(integer) 1
127.0.0.1:6379> bf.exists bloomFilterKey user2
(integer) 1
127.0.0.1:6379> bf.exists bloomFilterKey user3
(integer) 0
3. Принцип
Когда аддитивный элемент в первом байтовом значении (GetBytes (значение, «UTF-8»)), рассчитывается по алгоритму элементов K (14) независимо от значения хеша, то k независимой длины растрового изображения Hash Value (201,978) Для модуля, соответствующего установленной позиции.
Определение того, присутствует ли элемент, рассчитанный на элемент k независимого значения хеша, а затем использовать это модульное k независимое хеш-значение и длину растровой карты (201,978), все позиции представлены наличием 1, до тех пор, пока есть 0 Это не существовало.
При его использовании не допускайте, чтобы фактический элемент был намного больше инициализированного размера.Когда фактический элемент начинает превышать инициализированный размер, следует перестроить фильтр Блума, переназначить фильтр большего размера, а затем все исторические элементы должны добавляться партиями (это требует от нас записи всех исторических элементов в другую память). Поскольку error_rate не увеличивается резко из-за превышения числа, это дает нам больше времени для перестройки фильтра.
Почему возникает ошибка?
Поскольку эта позиция равна 1, она может быть установлена другими клавишами.
Рекомендация: Не допускайте, чтобы фактический элемент был намного больше инициализированного размера при его использовании.Когда фактический элемент начинает превышать инициализированный размер, следует перестроить фильтр Блума, переназначить фильтр большего размера, а затем все исторические элементы следует добавлять партиями (это требует от нас записи всех исторических элементов в другую память). Поскольку error_rate не увеличивается резко из-за превышения числа, это дает нам больше времени для перестройки фильтра.
Примечание: Чем больше длина растрового изображения, тем ниже частота ошибок, но для этого требуется много места. Обычно здесь используется ожидаемое количество элементов. Когда фактическое число превышает это значение, частота ошибок увеличивается.
Калькулятор частоты ошибок:Крис Айвс.GitHub.IO/bloom-rubbed rough…
4. Настоящий бой
Или используйте требования, которые мы сказали в начале, чтобы реализовать дедупликацию новостных лент.Предполагая, что требования требуют от нас обеспечения 100% правильной скорости, как мы можем ее оптимизировать?
Нам нужно разработать два уровня проверки, первый уровень — фильтр Блума, второй уровень — MySQL.
public void exist(String data) {
// 数据是否存在
boolean existFlag = false;
// 1.先去布隆过滤器判断
if(bloomFilter.exist(data)) {
// 2.如果布隆过滤器存在，需要在MySQL中进行二次校验
if(mysqlService.exist(data)) {
// 3.数据存在
existFlag = true;
}
}
return existFlag;
}
public void insertRecord() {
// 1.先插入布隆过滤器
// 2.插入到数据库
}
Некоторые студенты сказали, что мне делать, если моя версия Redis ниже 4.0?
Мы можем сами реализовать фильтр Блума, используя растровые изображения Redis.
Сценарии использования фильтра Блума:
- черный список
- Краулер, прежде чем сканировать веб-страницу, сначала определите, был ли просканирован URL-адрес, и если он был просканирован, он больше не будет сканироваться
- проникновение в кеш