Вимоги: Нещодавно я побачив відео алгоритму Redis Bloom на Bilibili, щоб вирішити проблему проникнення кешу, тобто додати рівень логічного судження перед доступом до бази даних, щоб визначити, чи існують дані, і якщо так, то отримати доступ до бази даних. Наприклад, якщо вебсайт є новинною системою, URL-адреси статей генеруються самозростаючими первинними ключовими ID (формат 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 MB | | Бітові | 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# маніпулює типом BitMap Redis
Ми дізналися про кілька команд BitMap у redis та про те, як ними програмно керувати. Створіть новий консольний проєкт .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
|
