Изисквания: Наскоро видях видео на алгоритъма Redis Bloom в Bilibili, за да реши проблема с проникването в кеша – просто казано, добавяне на слой логическо преценяване преди достъп до базата данни, за да се определи дали данните съществуват, и ако да, достъп до базата данни. Например, ако уебсайтът е новинарска система, URL адресите на статиите се генерират чрез самоувеличаващи се първични ключове (URL формат example:/news-1.html), уебсайтът може да има само десетки хиляди статии и кешове.
Първоначално:
Запитване на новинарски ресурс -> Определи дали кешът съществува -> Присъствие -> Кешът връща данни.
Запитване на новинарски ресурси -> Определи дали кешът съществува -> не съществува -> Заявка от базата данни -> Наличен -> Кеш и връщане на данни.
Заявка за новинарски ресурс -> Определи дали кешът съществува -> не съществува -> Заявка от базата данни -> Не съществува -> Връща грешка 404.
Точно сега:
Заявете новинарски ресурс -> алгоритъма на Блум -> Съществуване -> Следвайте оригиналната логика.
Запитай новинарски ресурс -> алгоритъмът на Блум -> не съществува -> връща директно грешка 404.
BloomFilter
Алгоритъмът BloomFilter е алгоритъм за планиране на големи данни. В множество с голямо количество данни може точно да се определи, че даден обект не е в множеството; Възможно е да се съди даден обект в множество и да заема малко място. тоНе е подходящ за ситуации, които изискват висока точност и нула грешки。 Ефективното използване на пространството се постига чрез жертване на частична точност.
Алгоритъмът на Блум е метод, базиран наЖертвай определена точност в замяна на алгоритъм за филтриране с ниска консумация на памет, който може да реализира филтриране, дедупликация и други операции на голямо количество данни.
Алгоритъмът на Блум е просто абстрактна концепция и може да бъде реализиран по много начини, а използването на BitMap в Redis в статията е просто проста реализация.
Препратка:Входът към хиперлинк е видим.
Въведение в битмап
BitMap е битмап, който всъщност е байтов масив, представен в двоичен формат.Има само две числа, 0 и 1, битмап означава да се използва всеки двоичен бит за съхранение или маркиране на стойността, съответстваща на елемент. Обикновено се използва за определяне дали дадена дата съществува или не, тъй като те се съхраняват в битове, така че самият Bitmap значително ще спести място за съхранение.
Както е показано на фигурата по-долу, низът се съхранява в двоична форма в компютъра.
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.5M | 375M | 4.5G |
След изчисления беше установено, че с увеличаването на времето обемът на записаните данни се увеличава, контрастът става по-очевиден, а BitMap заема по-малко място от зададеното.
Redis предоставя следните инструкции за работа с BitMap:
Документация на командите:Входът към хиперлинк е видим.
Сега, когато имате кратко разбиране за алгоритъма, битмап характеристиките и синтаксиса на Redis, нека използваме redis за една проста операция.
SETBIT синтаксис:Стойност на отместването на ключа SETBIT
Задайте артикула id:9, 10, 156 на 1 и командата е следната:
GETBIT синтаксис: GETBIT изместване на клавишите
За да се определи дали съществува id: 10 или 11, командата е следната:
.NET/C# манипулира битмап типа на Redis
Научихме за няколко BitMap команди в redis и как да ги управляваме програмно. Създайте нов .NET 3.1 конзолен проект, позовавате се на пакета StackExchange.Redis и използвайте следната команда:
Изходният код е следният:
Съществуват много други сценарии за битмап приложения за Redis, както следва:
- Може да се използва като прост Bloom филтър, за да се определи дали потребителят е извършил определени действия.
- Статистика за дневната активност на потребителите, месечната активност и степента на задържане
- Разберете статистиката за броя на стартираните потребители
- Потребителско онлайн присъствие и статистика на хората
(Край)
|
Публикувано в 2.01.2023 г. 17:37:01 ч.
|
|
|
|
Хазяин|
Публикувано в 2.01.2023 г. 17:41:56 ч.
|
Публикувано в 2.01.2023 г. 20:42:47 ч.
|
