Wymagania: Niedawno widziałem film z algorytmem Redis Bloom na Bilibili, który rozwiązuje problem penetracji pamięci podręcznej, mówiąc wprost, dodaje warstwę logicznej oceny przed dostępem do bazy danych, aby sprawdzić, czy dane istnieją, a jeśli tak, to uzyskać dostęp do bazy. Na przykład, jeśli strona internetowa jest systemem informacyjnym, adresy URL artykułów są generowane przez samoprzyrastające identyfikatory klucza głównego (format URL example:/news-1.html), więc strona może mieć jedynie dziesiątki tysięcy artykułów i pamięci podręcznej.
Pierwotnie:
Request news resource -> Sprawdź, czy pamięć podręczna istnieje -> Obecność -> Pamięć podręczna zwraca dane.
Żądaj zasobów informacyjnych -> Sprawdź, czy pamięć podręczna istnieje -> nie istnieje -> Zapytaj z bazy danych -> Prezentuj -> Zwróć dane cache.
Zproś zasób wiadomości -> Sprawdź, czy pamięć podręczna istnieje -> nie istnieje -> Zapytanie z bazy danych -> Nie istnieje -> Zwraca błąd 404.
Teraz:
Poproś o źródło informacji -> algorytm Blooma -> Istnienie -> Postępuj zgodnie z oryginalną logiką.
Request news resource -> algorytm Blooma -> nie istnieje -> zwraca bezpośrednio błąd 404.
BloomFilter
Algorytm BloomFilter to algorytm planowania big data. W zbiorze z dużą ilością danych można dokładnie określić, że obiekt nie znajduje się w zbiorze; Można ocenić obiekt w zbiorze i zajmować niewiele miejsca. onoNie nadaje się do sytuacji wymagających wysokiej dokładności i zerowych błędów。 Efektywne wykorzystanie przestrzeni osiąga się poprzez poświęcenie częściowej dokładności.
Algorytm Blooma to metoda oparta naPoświęcić pewną dokładność na rzecz algorytmu filtrującego o niskim zużyciu pamięci, które mogą realizować filtrowanie, deduplikację i inne operacje dużej ilości danych.
Algorytm Bloom to po prostu abstrakcyjna koncepcja i może być implementowana na wiele sposobów, a użycie BitMap w Redis w artykule to prosta implementacja.
Odniesienie:Logowanie do linku jest widoczne.
Wprowadzenie do BitMap
BitMap to bitmapa, która w rzeczywistości jest tablicą bajtów, reprezentowaną w formie binarnej.Są tylko dwie liczby: 0 i 1, bitmapa polega na użyciu każdego bitu binarnego do przechowywania lub oznaczania wartości odpowiadającej elementowi. Zazwyczaj służy do określenia, czy dane istnieją, ponieważ są przechowywane w bitach, więc sam Bitmap znacznie oszczędza miejsce na dysku.
Jak pokazano na poniższym rysunku, ciąg jest przechowywany w formie binarnej w komputerze.
Typy danych BitMap w Redis
Typ danych dostarczany przez Redis to BitMap, a każdy bit odpowiada dwóm stanom: 0 i 1. Chociaż pamięć wewnętrzna nadal jest w typie String, Redis dostarcza instrukcje do bezpośredniej manipulacji BitMapą, którą można traktować jako tablicę bitową, a indeks tablicy to przesunięcie.
Jego zalety to:Niskie narzuty pamięci i wysoka wydajnośćA operacja jest prosta.
Oszczędzanie miejsca: bit służy do reprezentowania wartości lub stanu elementu, gdzie klucz to wartość odpowiadającego elementu. W rzeczywistości 8 bitów może stanowić bajt, więc oszczędza miejsce.
Wysoka wydajność: Złożoność czasowa setbit i getbit wynosi O(1), a efektywność innych bitów również jest wysoka.
Oto przykład użycia kolekcji zestawów i pamięci BitMap:
| Typ danych | Każdy userid zajmuje miejsce | Liczba użytkowników, których trzeba przechowywać | Wszystko zajmuje pamięć | | zbiór | 32 bity to 4 bajty (zakładając, że userid używa liczb całkowitych, wiele stron faktycznie używa długich liczb całkowitych) | 50,000,000 | 32 bity * 50 000 000 = 200 MB | | Bitmapa | 1 bit | 100,000,000 | 1 bit * 100 000 000 = 12,5 MB |
Czas trochę się rozciąga
| | Pewnego dnia | Jeden miesiąc | Jeden rok | | zbiór | 200M | 6G | 72G | | Bitmapa | 12,5 mln | 375M | 4.5G |
Po obliczeniach stwierdzono, że wraz ze wzrostem czasu rosła ilość danych do zapisu, kontrast stawał się bardziej widoczny, a BitMap zajmował mniej miejsca niż ustawiony.
Redis zawiera następujące instrukcje obsługi BitMap:
Dokumentacja poleceń:Logowanie do linku jest widoczne.
Teraz, gdy masz krótkie zrozumienie algorytmu oraz cech bitmapowych i składni Redis, użyjmy redis, aby wykonać prostą operację.
Składnia SETBIT:Wartość przesunięcia klucza SETBIT
Ustaw id:9, 10, 156 na 1, a polecenie jest następujące:
Składnia GETBIT: przesunięcie klucza GETBIT
Aby ustalić, czy istnieje id: 10 czy 11, polecenie jest następujące:
.NET/C# manipuluje typem BitMap w Redis
Poznaliśmy kilka poleceń BitMap w redis i jak je programowo obsługiwać. Stwórz nowy projekt konsoli .NET 3.1, odwołaj się do pakietu StackExchange.Redis i użyj następującego polecenia:
Kod źródłowy przedstawia się następująco:
Istnieje wiele innych scenariuszy zastosowań bitmapowych dla Redis, jak poniżej:
- Może być używany jako prosty filtr Bloom do określenia, czy użytkownik wykonał określone działania.
- Statystyki dziennej aktywności użytkownika, miesięcznej aktywności oraz wskaźnika retencji
- Zrozum statystyki liczby startów użytkowników
- Obecność użytkowników w sieci i statystyki dotyczące osób
(Koniec)
|
Opublikowano 02.01.2023 17:37:01
|
|
|
|
Ziemianin|
Opublikowano 02.01.2023 17:41:56
|
Opublikowano 02.01.2023 20:42:47
|
