Požadavky: Nedávno jsem viděl video algoritmu Redis Bloom na Bilibili, který řeší problém pronikání do cache, jednoduše řečeno, přidává vrstvu logického úsudku před přístupem do databáze, abych zjistil, zda data existují, a pokud ano, tak k databázi přistupovat. Například pokud je webová stránka zpravodajským systémem, URL adresy článků jsou generovány samopřirůstajícími primárními klíčovými ID (URL formát example:/news-1.html), web může mít pouze desítky tisíc článků a cache.
Původně:
Požádat o zpravodajský zdroj -> Zjistit, zda cache existuje -> Přítomnost -> Cache vrací data.
Požádat o zpravodajské zdroje -> Zjistit, zda cache existuje -> neexistuje -> Dotazovat z databáze -> Prezentovat -> Cache a vrátit data.
Požádat o zpravodajský zdroj -> Zjistit, zda cache existuje -> neexistuje -> Dotaz z databáze -> Neexistuje -> Vrátí chybu 404.
Hned teď:
Požádat o zpravodajský zdroj -> Bloomův algoritmus -> Existence -> Řiďte se původní logikou.
Požádat o zpravodajský zdroj -> Bloomův algoritmus -> neexistuje -> přímo vrací chybu 404.
BloomFilter
Algoritmus BloomFilter je algoritmus pro plánování velkých dat. V množině s velkým množstvím dat lze přesně určit, že objekt v této množině není; Je možné hodnotit objekt v množině a zabírat jen málo místa. onoNení vhodný pro situace, které vyžadují vysokou přesnost a nulové chyby。 Efektivní využití prostoru je dosaženo obětováním částečné přesnosti.
Bloomův algoritmus je metoda založená naObětovat určitou přesnost výměnou za filtrační algoritmus s nízkou spotřebou paměti, které mohou provádět filtrování, deduplikaci a další operace velkého množství dat.
Bloomův algoritmus je jen abstraktní koncept a lze jej implementovat mnoha způsoby, a použití BitMapu v Redis v článku je jen jednoduchá implementace.
Odkaz:Přihlášení k hypertextovému odkazu je viditelné.
Úvod do BitMap
BitMap je bitmapa, což je ve skutečnosti bajtové pole reprezentované binárně.Existují pouze dvě čísla, 0 a 1, bitmapa slouží k použití každého binárního bitu k uložení nebo označení hodnoty odpovídající prvku. Obvykle se používá k určení, zda určitá data existují, protože jsou uložena v bitech, takže samotný Bitmap výrazně šetří místo na úložišti.
Jak je znázorněno na obrázku níže, řetězec je uložen v binární formě v počítači.
Datové typy BitMap v Redis
Datový typ poskytnutý Redis je BitMap a každý bit odpovídá dvěma stavům: 0 a 1. Ačkoliv je interní paměť stále v typu String, Redis poskytuje některé instrukce pro přímou manipulaci s BitMapou, kterou lze chápat jako bitové pole, a index pole je offset.
Její výhody jsou:Nízká paměťová režie a vysoká účinnostA operace je jednoduchá.
Úspora místa: Bit se používá k reprezentaci hodnoty nebo stavu prvku, kde klíč je hodnota příslušného prvku. Ve skutečnosti může 8 bitů tvořit bajt, takže šetří prostor.
Vysoká efektivita: Časová složitost setbitu a getbitu je O(1) a efektivita ostatních bitů je také vysoká.
Zde je příklad použití kolekce setů a úložiště BitMap:
| datový typ | Každý userid zabírá místo | Počet uživatelů, které je potřeba uložit | Vše zabírá paměť | | nastavit | 32 bitů je 4 bajty (za předpokladu, že userid používá celá čísla, mnoho webů skutečně používá dlouhá celá čísla) | 50,000,000 | 32 bitů * 50 000 000 = 200 MB | | Bitmapa | 1 bit | 100,000,000 | 1 bit * 100 000 000 = 12,5 MB |
Čas se trochu protahuje
| | Jednoho dne | Jeden měsíc | Jeden rok | | nastavit | 200M | 6G | 72G | | Bitmapa | 12,5M | 375M | 4,5G |
Po výpočtu se zjistilo, že s postupem času se zvyšuje množství dat, která je třeba zaznamenat, kontrast je zřetelnější a BitMap zabírá méně místa než nastaveno.
Redis poskytuje následující instrukce pro provoz BitMapy:
Dokumentace příkazů:Přihlášení k hypertextovému odkazu je viditelné.
Teď, když máte stručné pochopení algoritmu a bitmapových funkcí a syntaxe Redis, použijme redis k jednoduché operaci.
Syntaxe SETBIT:Hodnota posunu klíče SETBIT
Nastavte id článku 9, 10, 156 na 1 a příkaz je následující:
GETBIT syntaxe: GETBIT key offset
Pro určení, zda existuje id: 10 nebo 11, je příkaz následující:
.NET/C# manipuluje s typem BitMap v Redis
Naučili jsme se o několika BitMap příkazech v redisu a o tom, jak je programově ovládat. Vytvořte nový .NET 3.1 konzolový projekt, odkazujte na balíček StackExchange.Redis a použijte následující příkaz:
Zdrojový kód je následující:
Existuje mnoho dalších scénářů aplikace bitmapových map pro Redis, a to následovně:
- Může být použit jako jednoduchý Bloom filtr k určení, zda uživatel provedl určité akce.
- Statistiky denní aktivity uživatelů, měsíční aktivity a míry udržení uživatelů
- Uvědomte si statistiky počtu spuštění uživateli
- Online přítomnost uživatelů a statistiky o osobách
(Konec)
|
Zveřejněno 02.01.2023 17:37:01
|
|
|
|
Pronajímatel|
Zveřejněno 02.01.2023 17:41:56
|
Zveřejněno 02.01.2023 20:42:47
|
