Krav: Nyligen såg jag en video med Redis Bloom-algoritmen på Bilibili för att lösa problemet med cachepenetration, enkelt uttryckt, lägga till ett lager av logisk bedömning innan man går åt databasen för att avgöra om datan existerar, och i så fall få tillgång till databasen. Till exempel, om en webbplats är ett nyhetssystem, genereras artiklars URL:er med självinkrementerande primärnyckel-ID:n (URL-format example:/news-1.html), kan webbplatsen bara ha tiotusentals artiklar och cacher.
Ursprungligen:
Begär nyhetsresurs -> Fastställ om cachen finns -> Närvaro -> Cachen returnerar data.
Begär nyhetsresurser -> Bestäm om cachen existerar -> inte finns -> Fråga från databasen -> Presentera -> cache och returnera data.
Begär en nyhetsresurs -> Fastställ om cachen finns -> inte finns -> Fråga från databasen -> Finns inte -> Returnerar ett 404-fel.
Nu:
Begär nyhetsresurs -> Blooms algoritm -> Existence -> Följ den ursprungliga logiken.
Begär nyhetsresurs -> Blooms algoritm -> inte existerar -> returnerar ett 404-fel direkt.
BloomFilter
BloomFilter-algoritmen är en big data-schemaläggningsalgoritm. I en mängd med stora mängder data kan man noggrant fastställa att ett objekt inte ingår i mängden; Det är möjligt att bedöma ett objekt i en mängd och ta upp lite plats. detDen är inte lämplig för situationer som kräver hög noggrannhet och noll fel。 Effektiv användning av utrymme uppnås genom att offra partiell noggrannhet.
Blooms algoritm är en metod baserad påOffra en viss noggrannhet i utbyte mot en filtreringsalgoritm med låg minnesförbrukning, som kan genomföra filtrering, deduplicering och andra operationer för en stor mängd data.
Bloom-algoritmen är bara ett abstrakt koncept och kan implementeras på många sätt, och användningen av BitMap i Redis i artikeln är bara en enkel implementation.
Hänvisning:Inloggningen med hyperlänken är synlig.
Introduktion till BitMap
BitMap är en bitmap, som faktiskt är en bytearray, representerad i binärt system.Det finns bara två siffror, 0 och 1, bitmap är att använda varje binär bit för att lagra eller markera värdet som motsvarar ett element. Den används vanligtvis för att avgöra om viss data finns eller inte, eftersom den lagras i bitar, så Bitmap i sig sparar mycket lagringsutrymme.
Som visas i figuren nedan lagras strängen i binär form i datorn.
Bitmap-datatyper i Redis
Datatypen som Redis tillhandahåller är BitMap, och varje bit motsvarar två tillstånd: 0 och 1. Även om den interna lagringen fortfarande är i String-typen, tillhandahåller Redis vissa instruktioner för att direkt manipulera BitMap, vilket kan ses som en bitarray, och indexet i arrayen är offset.
Dess fördelar är:Låg minnesöverhead och hög effektivitetOch operationen är enkel.
Utrymmesbesparing: En bit används för att representera värdet eller tillståndet för ett element, där nyckeln är värdet på motsvarande element. Faktum är att 8 bitar kan utgöra en byte, så det sparar plats.
Hög effektivitet: Tidskomplexiteten för setbit och getbit är O(1), och effektiviteten hos andra bitar är också hög.
Här är ett exempel på att använda set collection och BitMap-lagring:
| datatyp | Varje användarid tar upp plats | Antalet användare som behöver lagras | Allt upptar minnet | | ställa | 32 bitar är 4 byte (förutsatt att userid använder heltal, många webbplatser använder faktiskt långa heltal) | 50,000,000 | 32 bitar * 50 000 000 = 200 MB | | Bitmapp | 1 bit | 100,000,000 | 1 bit * 100 000 000 = 12,5 MB |
Tiden sträcker sig lite
| | En dag | En månad | Ett år | | ställa | 200 meter | 6G | 72G | | Bitmapp | 12,5 miljoner | 375M | 4,5G |
Efter beräkning fann man att ju längre tiden gick, desto mer data som skulle registreras, kontrasten blev mer uppenbar, och BitMap tog upp mindre plats än det satta.
Redis tillhandahåller följande instruktioner för att använda BitMap:
Kommandodokumentation:Inloggningen med hyperlänken är synlig.
Nu när du har en kort förståelse för algoritmen och Bitmap-funktionerna och syntaxen i Redis, låt oss använda redis för att göra en enkel operation.
SETBIT-syntax:SETBIT-nyckeloffsetvärde
Sätt artikeln id:9, 10, 156 till 1, och kommandot är följande:
GETBIT-syntax: GETBIT-tangentförskjutning
För att avgöra om id: 10 eller 11 existerar, är kommandot följande:
.NET/C# manipulerar Redis BitMap-typ
Vi lärde oss om flera BitMap-kommandon i redis och hur man använder dem programmatiskt. Skapa ett nytt .NET 3.1-konsolprojekt, referera till StackExchange.Redis-paketet och använd följande kommando:
Källkoden är följande:
Det finns många andra bitmap-applikationsscenarier för Redis, såsom följande:
- Den kan användas som ett enkelt Bloom-filter för att avgöra om en användare har utfört vissa åtgärder.
- Statistik över användarens dagliga aktivitet, månatlig aktivitet och kvarhållningsgrad
- Förstå statistiken över antalet användarlanseringar
- Användares närvaro på nätet och statistik över personer
(Slut)
|
Publicerad på 2023-01-02 17:37:01
|
|
|
|
Hyresvärd|
Publicerad på 2023-01-02 17:41:56
|
Publicerad på 2023-01-02 20:42:47
|
