Anforderungen: Kürzlich habe ich ein Video des Redis-Bloom-Algorithmus auf Bilibili gesehen, um das Problem der Cache-Penetration zu lösen – einfach gesagt: eine logische Schicht logischer Einschätzung hinzufügen, bevor man auf die Datenbank zuruft, um festzustellen, ob die Daten existieren, und falls ja, auf die Datenbank zugreifen. Wenn zum Beispiel eine Website ein Nachrichtensystem ist, werden die URLs von Artikeln durch selbststeigernde Primärschlüssel-IDs (URL-Format example:/news-1.html) generiert; die Website kann nur zehntausende Artikel und Caches enthalten.
Ursprünglich:
Nachrichtenressource anfordern -> Bestimmen, ob der Cache existiert -> Präsenz -> Der Cache liefert Daten zurück.
Nachrichtenressourcen anfordern -> Bestimmen, ob der Cache existiert > nicht existiert -> Abfrage aus der Datenbank -> Präsentieren -> Cache und Rückgabe von Daten.
Eine Nachrichtenressource anfordern -> Bestimmen, ob der Cache existiert -> nicht existiert -> Abfrage aus der Datenbank -> Existiert nicht -> Gibt einen 404-Fehler zurück.
Jetzt gerade:
Nachrichtressource anfordern -> Blooms Algorithmus -> Existence -> Folgen Sie der ursprünglichen Logik.
Fordern Sie eine Nachrichtenquelle -> Blooms Algorithmus an, > nicht existiert -> direkt einen 404-Fehler zurückgibt.
BloomFilter
Der BloomFilter-Algorithmus ist ein Big-Data-Planungsalgorithmus. In einer Menge mit großer Datenmenge kann genau festgestellt werden, dass ein Objekt nicht in der Menge ist; Es ist möglich, ein Objekt in einer Menge zu beurteilen und dabei wenig Platz einzunehmen. esSie ist nicht geeignet für Situationen, die hohe Genauigkeit und null Fehler erfordern。 Eine effiziente Platznutzung wird durch den Opfer der teilweisen Genauigkeit erreicht.
Blooms Algorithmus ist eine Methode, die aufOpfere eine gewisse Genauigkeit zugunsten eines Filteralgorithmus mit geringem Speicherverbrauch, die die Filterung, Deduplizierung und andere Operationen einer großen Datenmenge realisieren kann.
Der Bloom-Algorithmus ist nur ein abstraktes Konzept und kann auf viele Arten implementiert werden, und die Verwendung von BitMap in Redis im Artikel ist nur eine einfache Implementierung.
Referenz:Der Hyperlink-Login ist sichtbar.
BitMap-Einführung
BitMap ist eine Bitmap, die tatsächlich ein Byte-Array ist, das binär dargestellt wird.Es gibt nur zwei Zahlen, 0 und 1bitmap bedeutet, dass jedes Binärbit verwendet wird, um den Wert eines Elements zu speichern oder zu markieren. Sie wird üblicherweise verwendet, um festzustellen, ob bestimmte Daten existieren oder nicht, da sie in Bits gespeichert sind, sodass Bitmap selbst erheblich Speicherplatz spart.
Wie in der untenstehenden Abbildung gezeigt, wird die Zeichenkette im Computer in binärer Form gespeichert.
BitMap-Datentypen in Redis
Der von Redis bereitgestellte Datentyp ist BitMap, und jedes Bit entspricht zwei Zuständen: 0 und 1. Obwohl der interne Speicher noch im String-Typ ist, bietet Redis einige Anweisungen zur direkten Manipulation von BitMap, das als Bitarray betrachtet werden kann, und der Index des Arrays ist der Offset.
Seine Vorteile sind:Niedriger Speicher-Overhead und hohe EffizienzUnd die Operation ist einfach.
Platzeinsparung: Ein Bit wird verwendet, um den Wert oder Zustand eines Elements darzustellen, wobei der Schlüssel der Wert des entsprechenden Elements ist. Tatsächlich können 8 Bits ein Byte ausmachen, was Platz spart.
Hohe Effizienz: Die Zeitkomplexität von Setbit und Getbit beträgt O(1), und die Effizienz anderer Bits ist ebenfalls hoch.
Hier ist ein Beispiel für die Verwendung der Set-Collection und der BitMap-Speicherung:
| Datentyp | Jede Userid nimmt Platz ein | Die Anzahl der Nutzer, die gespeichert werden müssen | Alles besetzt das Gedächtnis | | Garnitur | 32 Bit sind 4 Bytes (vorausgesetzt, UserID verwendet ganze Zahlen, viele Webseiten verwenden tatsächlich lange Ganzzahlen). | 50,000,000 | 32 Bit * 50.000.000 = 200 MB | | Bitmap | 1 Bit | 100,000,000 | 1 Bit * 100.000.000 = 12,5 MB |
Die Zeit zieht sich ein wenig aus
| | Eines Tages | Ein Monat | Ein Jahr | | Garnitur | 200M | 6G | 72G | | Bitmap | 12,5 M | 375M | 4,5G |
Nach der Berechnung stellte sich heraus, dass mit zunehmender Zeit die Datenmenge zunahm, der Kontrast deutlicher wurde und BitMap weniger Platz einnahm als eingestellt.
Redis bietet folgende Anweisungen zum Betrieb von BitMap:
Befehlsdokumentation:Der Hyperlink-Login ist sichtbar.
Jetzt, da du den Algorithmus und die Bitmap-Funktionen und -syntax von Redis kurz verstehst, verwenden wir Redis für eine einfache Operation.
SETBIT-Syntax:SETBIT-Schlüsselversatzwert
Setzen Sie den Artikel id:9, 10, 156 auf 1, und der Befehl lautet wie folgt:
GETBIT-Syntax: GETBIT-Schlüsselversatz
Um festzustellen, ob id: 10 oder 11 existiert, lautet der Befehl wie folgt:
.NET/C# manipuliert den BitMap-Typ von Redis
Wir lernten mehrere BitMap-Befehle in Redis kennen und wie man sie programmatisch bedient. Erstellen Sie ein neues .NET 3.1-Konsolenprojekt, beziehen Sie sich auf das StackExchange.Redis-Paket und verwenden Sie folgenden Befehl:
Der Quellcode ist wie folgt:
Es gibt viele weitere Bitmap-Anwendungsszenarien für Redis, wie folgt:
- Er kann als einfacher Bloom-Filter verwendet werden, um zu bestimmen, ob ein Benutzer bestimmte Aktionen ausgeführt hat.
- Statistiken der täglichen Nutzeraktivität, der monatlichen Aktivität und der Bindungsrate
- Erkennen Sie die Statistiken der Anzahl der Nutzerstarts
- Online-Präsenz und Personenstatistiken der Nutzer
(Ende)
|
Veröffentlicht am 02.01.2023 17:37:01
|
|
|
|
Vermieter|
Veröffentlicht am 02.01.2023 17:41:56
|
Veröffentlicht am 02.01.2023 20:42:47
|
