Požiadavky: Nedávno som videl video algoritmu Redis Bloom na Bilibili, ktorý rieši problém penetrácie cache, jednoducho povedané, pridáva vrstvu logického úsudku pred prístupom do databázy, aby sa zistilo, či dáta existujú, a ak áno, tak prístup k databáze. Napríklad, ak je webová stránka spravodajským systémom, URL adresy článkov sú generované samopridávajúcimi sa primárnymi kľúčovými ID (URL formát example:/news-1.html), webová stránka môže mať len desaťtisíce článkov a cache.
Pôvodne:
Požiadajte o spravodajský zdroj -> Zistite, či cache existuje -> Prítomnosť -> Cache vracia dáta.
Požiadajte o spravodajské zdroje -> Zistite, či cache existuje -> neexistuje -> Dotazujte z databázy -> Prezentujte -> Cache a vráťte dáta.
Požiadajte o spravodajský zdroj -> Zistite, či cache existuje -> neexistuje -> Dotaz z databázy -> Neexistuje -> Vráti chybu 404.
Hneď teraz:
Požiadajte o spravodajský zdroj -> Bloomov algoritmus -> Existencia -> Riaďte sa pôvodnou logikou.
Request news resource -> Bloomov algoritmus -> neexistuje -> vráti priamo chybu 404.
BloomFilter
Algoritmus BloomFilter je algoritmus na plánovanie veľkých dát. V množine s veľkým množstvom dát možno presne určiť, že objekt nie je v množine; Je možné posúdiť objekt v množine a zaberať len málo miesta. onoNie je vhodný pre situácie vyžadujúce vysokú presnosť a nulové chyby。 Efektívne využitie priestoru sa dosahuje obetovaním čiastočnej presnosti.
Bloomov algoritmus je metóda založená naObetujte určitú presnosť výmenou za filtračný algoritmus s nízkou spotrebou pamäte, ktoré dokážu realizovať filtrovanie, deduplikáciu a ďalšie operácie veľkého množstva dát.
Bloomov algoritmus je len abstraktný koncept a dá sa implementovať mnohými spôsobmi, pričom použitie BitMapu v Redis v článku je len jednoduchá implementácia.
Referencia:Prihlásenie na hypertextový odkaz je viditeľné.
Úvod do BitMapy
BitMap je bitmapa, ktorá je v skutočnosti bajtovým poľom, reprezentovaným binárne.Existujú len dve čísla, 0 a 1, bitmapa používa každý binárny bit na uloženie alebo označenie hodnoty zodpovedajúcej prvku. Zvyčajne sa používa na určenie, či určité dáta existujú alebo nie, pretože sú uložené v bitoch, takže samotný Bitmap výrazne šetrí miesto na úložisku.
Ako je znázornené na obrázku nižšie, reťazec je uložený v binárnej forme v počítači.
BitMap dátové typy v Redis
Dátový typ poskytovaný Redis je BitMap a každý bit zodpovedá dvom stavom: 0 a 1. Aj keď je vnútorné úložisko stále v type String, Redis poskytuje niektoré inštrukcie na priamu manipuláciu s BitMapou, ktorú možno považovať za bitové pole, a dolný index poľa je offset.
Jej výhody sú:Nízka režijná záťaž pamäte a vysoká efektivitaA operácia je jednoduchá.
Úspora miesta: Bit sa používa na reprezentáciu hodnoty alebo stavu prvku, kde kľúč je hodnota príslušného prvku. V skutočnosti môže 8 bitov tvoriť bajt, takže šetrí miesto.
Vysoká účinnosť: Časová náročnosť setbitu a getbitu je O(1) a efektivita ostatných bitov je tiež vysoká.
Tu je príklad použitia kolekcie množín a úložiska BitMap:
| Typ údajov | Každý userid zaberá miesto | Počet používateľov, ktoré je potrebné uložiť | Všetko zaberá pamäť | | množina | 32 bitov je 4 bajty (za predpokladu, že userid používa celé čísla, mnohé webové stránky skutočne používajú dlhé celé čísla) | 50,000,000 | 32 bitov * 50 000 000 = 200 MB | | Bitová mapa | 1 bit | 100,000,000 | 1 bit * 100 000 000 = 12,5 MB |
Čas sa trochu naťahuje
| | Jedného dňa | Jeden mesiac | Jeden rok | | množina | 200M | 6G | 72G | | Bitová mapa | 12,5M | 375M | 4,5G |
Po výpočte sa zistilo, že s časom sa zvyšuje množstvo dát, ktoré treba zaznamenať, kontrast sa stáva zreteľnejším a BitMap zaberá menej miesta, než je nastavené.
Redis poskytuje nasledujúce pokyny na prevádzku BitMapy:
Dokumentácia príkazov:Prihlásenie na hypertextový odkaz je viditeľné.
Teraz, keď máte stručné pochopenie algoritmu a bitmapových funkcií a syntaxe Redisu, použime redis na jednoduchú operáciu.
Syntax SETBIT:Hodnota posunu kľúča SETBIT
Nastavte id článku 9, 10, 156 na 1 a príkaz je nasledovný:
GETBIT syntax: GETBIT key offset
Na určenie, či existuje id: 10 alebo 11, je príkaz nasledovný:
.NET/C# manipuluje s typom BitMap v Redise
Naučili sme sa o viacerých BitMap príkazoch v redise a o tom, ako ich programovo ovládať. Vytvorte nový .NET 3.1 konzolový projekt, odvolajte sa na balík StackExchange.Redis a použite nasledujúci príkaz:
Zdrojový kód je nasledovný:
Existuje mnoho ďalších bitmapových aplikácií pre Redis, ako napríklad:
- Môže sa použiť ako jednoduchý Bloom filter na zistenie, či používateľ vykonal určité akcie.
- Štatistiky dennej aktivity používateľov, mesačnej aktivity a miery udržania používateľov
- Uvedomte si štatistiky počtu spustení používateľov
- Online prítomnosť používateľov a štatistiky ľudí
(Koniec)
|
Zverejnené 2. 1. 2023 17:37:01
|
|
|
|
Prenajímateľ|
Zverejnené 2. 1. 2023 17:41:56
|
Zverejnené 2. 1. 2023 20:42:47
|
