Vereisten: Onlangs zag ik een video van het Redis Bloom-algoritme op Bilibili om het probleem van cachepenetratie op te lossen, simpel gezegd, voeg een laag logisch oordeel toe voordat je de database opent om te bepalen of de data bestaat, en zo ja, toegang tot de database. Als een website bijvoorbeeld een nieuwssysteem is, worden de URL's van artikelen gegenereerd door zelfverhogende primaire sleutel-ID's (URL-formaat example:/news-1.html), kan de website slechts tienduizenden artikelen en caches hebben.
Oorspronkelijk:
Vraag om nieuwsbron -> Bepaal of de cache bestaat -> Aanwezigheid -> De cache levert gegevens terug.
Vraag nieuwsbronnen aan -> Bepaal of de cache bestaat -> niet bestaat -> Vraag vanuit de database -> Presenteer -> Cache en geef gegevens terug.
Vraag een nieuwsbron aan -> Bepaal of de cache bestaat -> niet bestaat -> Vraag vanuit de database -> Bestaat niet -> Geeft een 404-foutmelding terug.
Nu onmiddellijk:
Vraag nieuwsbron aan -> Bloom's algoritme -> Existence -> Volg de oorspronkelijke logica.
Vraag nieuwsbron -> Bloom's algoritme -> niet bestaat -> direct een 404-fout teruggeeft.
BloomFilter
Het BloomFilter-algoritme is een big data-planningsalgoritme. In een verzameling met een grote hoeveelheid data kan nauwkeurig worden vastgesteld dat een object niet in de verzameling zit; Het is mogelijk om een object in een verzameling te beoordelen en weinig ruimte in te nemen. hetHet is niet geschikt voor situaties die hoge nauwkeurigheid en nul fouten vereisen。 Efficiënt gebruik van ruimte wordt bereikt door gedeeltelijke nauwkeurigheid op te offeren.
Het algoritme van Bloom is een methode gebaseerd opOffer een bepaalde nauwkeurigheid op in ruil voor een filteralgoritme met laag geheugenverbruik, die de filtering, deduplicatie en andere bewerkingen van een grote hoeveelheid data kan realiseren.
Het Bloom-algoritme is slechts een abstract concept en kan op veel manieren worden geïmplementeerd, en het gebruik van BitMap in Redis in het artikel is slechts een eenvoudige implementatie.
Referentie:De hyperlink-login is zichtbaar.
Introductie van BitMap
BitMap is een bitmap, die eigenlijk een bytearray is, weergegeven in binaire vorm.Er zijn maar twee cijfers, 0 en 1, bitmap is om elke binaire bit te gebruiken om de waarde die overeenkomt met een element op te slaan of te markeren. Het wordt meestal gebruikt om te bepalen of bepaalde data bestaat of niet, omdat deze in bits wordt opgeslagen, waardoor Bitmap zelf veel opslagruimte bespaart.
Zoals te zien is in de onderstaande figuur, wordt de string in binaire vorm opgeslagen in de computer.
BitMap-datatypes in Redis
Het datatype dat Redis levert is BitMap, en elk bit komt overeen met twee toestanden: 0 en 1. Hoewel de interne opslag nog steeds in het String-type zit, biedt Redis enkele instructies voor het direct manipuleren van BitMap, wat kan worden gezien als een bitarray, en het subscript van de array is de offset.
De voordelen zijn:Lage geheugenoverhead en hoge efficiëntieEn de operatie is eenvoudig.
Ruimtebesparing: Een bit wordt gebruikt om de waarde of toestand van een element weer te geven, waarbij key de waarde is van het overeenkomstige element. In feite kunnen 8 bits een byte vormen, dus het bespaart ruimte.
Hoge efficiëntie: De tijdscomplexiteit van setbit en getbit is O(1), en de efficiëntie van andere bits is ook hoog.
Hier is een voorbeeld van het gebruik van de set collection en BitMap-opslag:
| Datatype | Elke userid neemt ruimte in beslag | Het aantal gebruikers dat opgeslagen moet worden | Alles bezet het geheugen | | set | 32 bits is 4 bytes (ervan uitgaande dat userid gehele getallen gebruikt, veel websites gebruiken eigenlijk lange gehele getallen) | 50,000,000 | 32 bits * 50.000.000 = 200 MB | | Bitmap | 1 bit | 100,000,000 | 1 bit * 100.000.000 = 12,5 MB |
De tijd dringt een beetje
| | Eens | Eén maand | Eén jaar | | set | 200M | 6G | 72G | | Bitmap | 12,5 M | 375M | 4,5G |
Na berekening bleek dat naarmate de tijd vorderde, de hoeveelheid te registreren data toenam, het contrast duidelijker werd, en BitMap minder ruimte innam dan ingesteld.
Redis geeft de volgende instructies voor het bedienen van BitMap:
Commandodocumentatie:De hyperlink-login is zichtbaar.
Nu je een kort begrip hebt van het algoritme en de Bitmap-functies en -syntaxis van Redis, laten we redis gebruiken om een eenvoudige bewerking uit te voeren.
SETBIT-syntaxis:SETBIT sleutelverschuiving waarde
Zet het artikel id:9, 10, 156 op 1, en het commando is als volgt:
GETBIT-syntaxis: GETBIT-sleuteloffset
Om te bepalen of id: 10 of 11 bestaat, is het commando als volgt:
.NET/C# manipuleert het BitMap-type van Redis
We leerden over verschillende BitMap-commando's in redis en hoe je ze programmatisch kunt bedienen. Maak een nieuw .NET 3.1 consoleproject aan, raadpleeg het StackExchange.Redis-pakket en gebruik het volgende commando:
De broncode is als volgt:
Er zijn veel andere bitmap-toepassingsscenario's voor Redis, als volgt:
- Het kan worden gebruikt als een eenvoudige Bloom-filter om te bepalen of een gebruiker bepaalde acties heeft uitgevoerd.
- Statistieken van dagelijkse gebruikersactiviteit, maandelijkse activiteit en retentiepercentage
- Besef de statistieken van het aantal gebruikerslanceringen
- Online aanwezigheid van gebruikers en statistieken over mensen
(Einde)
|
Geplaatst op 02-01-2023 17:37:01
|
|
|
|
Huisbaas|
Geplaatst op 02-01-2023 17:41:56
|
Geplaatst op 02-01-2023 20:42:47
|
