Требования: Недавно я увидел видео с алгоритмом Redis Bloom на Bilibili, который решает проблему проникновения в кэш, проще говоря, добавляет слой логического суждения перед доступом к базе данных, чтобы определить, существуют ли данные, и если да, то получить доступ к базе данных. Например, если сайт — это новостная система, а URL-адреса статей генерируются самоувеличивающимися первичными ключевыми идентификаторами (формат URL example:/news-1.html), сайт может содержать только десятки тысяч статей и кэшей.
Первоначально:
Запросить новостной ресурс -> Определить, существует ли кэш -> Присутствие -> Кэш возвращает данные.
Запросить новостные ресурсы -> Определить, существует ли кэш -> не существует -> Запросить из базы данных -> Представить -> Кэш и вернуть данные.
Запросить новостной ресурс -> Определить, существует ли кэш -> не существует -> Запрос из базы данных -> Не существует -> Возвращает ошибку 404.
Прямо сейчас:
Запросить новостной ресурс -> алгоритм Блума -> Существование -> Следовать исходной логике.
Запросить новостной ресурс -> алгоритм Блума -> не существует -> возвращает ошибку 404 напрямую.
BloomFilter
Алгоритм BloomFilter — это алгоритм планирования больших данных. В множестве с большим объёмом данных можно точно определить, что объект отсутствует в этом наборе; Можно оценить объект в множестве и занять мало места. оноОн не подходит для ситуаций, требующих высокой точности и отсутствия ошибок。 Эффективное использование пространства достигается за счёт жертвы частичной точности.
Алгоритм Блума — это метод, основанный наЖертвуйте определённой точностью в обмен на алгоритм фильтрации с низким потреблением памяти, который может выполнять фильтрацию, дедупликацию и другие операции большого объёма данных.
Алгоритм Блума — это всего лишь абстрактная концепция, которую можно реализовать разными способами, а использование BitMap в Redis в статье — это просто простая реализация.
Ссылка:Вход по гиперссылке виден.
Введение в битмап
BitMap — это растровый мап, который на самом деле представляет собой массив байтов, представленный в бинарном виде.Существует всего два числа — 0 и 1, растровая карта — использовать каждый бинарный бит для хранения или маркировки значения, соответствующего элементу. Обычно он используется для определения существования определённых данных, так как они хранятся в битах, поэтому сам растровый мап значительно экономит место для памяти.
Как показано на рисунке ниже, строка хранится в бинарном виде в компьютере.
Типы данных BitMap в Redis
Тип данных, предоставляемый Redis, — BitMap, и каждый бит соответствует двум состояниям: 0 и 1. Хотя внутреннее хранилище всё ещё находится в типе String, Redis предоставляет некоторые инструкции по прямой обработке BitMap, который можно рассматривать как битовый массив, а индекс массива — это смещение.
Её преимущества следующие:Низкие накладные расходы памяти и высокая эффективностьИ операция проста.
Экономия пространства: Бит используется для представления значения или состояния элемента, где key — значение соответствующего элемента. На самом деле, 8 бит могут составлять байт, что экономит место.
Высокая эффективность: Временная сложность setbit и getbit составляет O(1), а эффективность других битов тоже высока.
Вот пример использования коллекции множеств и хранилища BitMap:
| тип данных | Каждый пользователь занимает место | Количество пользователей, которых нужно хранить | Всё занимает память | | набор | 32 бита — это 4 байта (если Userid использует целые числа, многие сайты действительно используют длинные целые числа) | 50,000,000 | 32 бита * 50 000 000 = 200 МБ | | Точечный рисунок | 1 бит | 100,000,000 | 1 бит * 100 000 000 = 12,5 MB |
Время немного растянулось
| | Однажды | Один месяц | Один год | | набор | 200 м | 6G | 72G | | Точечный рисунок | 12,5 млн | 375 м | 4,5G |
После расчёта было установлено, что с увеличением времени количество данных увеличивается, контраст становится более заметным, а BitMap занимает меньше места, чем было установлено.
Redis предоставляет следующие инструкции по работе с BitMap:
Документация командования:Вход по гиперссылке виден.
Теперь, когда у вас есть краткое представление об алгоритме, растровых функциях и синтаксисе Redis, давайте возьмём Redis для простой операции.
Синтаксис SETBIT:Смещение ключа SETBIT
Установите артикл id:9, 10, 156 по 1, и команда выглядит следующим образом:
Синтаксис GETBIT: смещение ключа GETBIT
Чтобы определить, существует ли id: 10 или 11, команда выглядит следующим образом:
.NET/C# управляет растровым типом Redis
В redis мы узнали о нескольких командах BitMap и о том, как ими управлять программно. Создайте новый консольный проект .NET 3.1, откройте ссылку на пакет StackExchange.Redis и используйте следующую команду:
Исходный код следующий:
Существует множество других сценариев применения растрового изображения для Redis, а именно следующие:
- Его можно использовать как простой фильтр Bloom для определения, выполнил ли пользователь определённые действия.
- Статистика ежедневной активности пользователя, ежемесячной активности и уровня удержания пользователей
- Изучите статистику числа запусков пользователей
- Онлайн-присутствие пользователей и статистика людей
(Конец)
|
Опубликовано 02.01.2023 17:37:01
|
|
|
|
Хозяин|
Опубликовано 02.01.2023 17:41:56
|
Опубликовано 02.01.2023 20:42:47
|
