Wprowadzenie do struktur danych Redis:mapy bitowe

Mapy bitowe (zwane również tablicami bitowymi, wektorami bitowymi itp.) to struktura danych, która natychmiast pojawia się w Twojej głowie, gdy zachodzi potrzeba mapowania informacji logicznych dla ogromnej domeny w zwartą reprezentacja. Jest to bardzo popularna struktura danych, gdy miejsce w pamięci jest na wagę złota:jądra systemu operacyjnego (strony pamięci, i-węzły itp.), obrazowanie cyfrowe itp.

Redis, będąc serwerem struktury danych w pamięci, zapewnia obsługę operacji manipulacji bitami. Jednak nie ma specjalnej struktury danych dla bitmap w Redis. Operacje na poziomie bitowym są raczej obsługiwane w podstawowej strukturze Redis:ciągach. Teraz maksymalna długość ciągów Redis wynosi 512 MB. Zatem największa domena, którą Redis może mapować jako bitmapę, to 2 (512 MB =2 bajty =2 bity).

Operacje związane z bitami w Redis są dwojakiego rodzaju:Stały czas (O(1)), np. operacje do pobrania/ustawienia określonego bitu i operacje, które są O(N), które zasadniczo operują na grupie bitów. N w tych przypadkach to długość bitów, nad którymi operacja będzie musiała pracować. Spójrzmy na kilka przykładów.

Polecenia

# SETBIT key offset value: Store bit value 'value' at offset 'offset' for 'key'. O(1)
# Returns the original bit value stored at that offset.
127.0.0.1:6379> setbit k 10 1
(integer) 0
# GETBIT key offset: Fetch value of 'offset' in 'key'. O(1)
127.0.0.1:6379> getbit k 10
(integer) 1
127.0.0.1:6379> getbit k 11
(integer) 0
127.0.0.1:6379> getbit k 0
(integer) 0
127.0.0.1:6379> setbit k 9 1
(integer) 0
127.0.0.1:6379> setbit k 8 1
(integer) 0
# And since it is still a generic String, here's a get.
127.0.0.1:6379> get k
"\x00\xe0"
# "\x00\xe0" -> "0000 0000 111"
# BITCOUNT key [start end]: Number of set bits in the range. O(N)
# IMPORTANT: start & end are bytes not bits
127.0.0.1:6379> bitcount k
(integer) 3
127.0.0.1:6379> set m "meow"
OK
# meow -> 01101101 01100101 01101111 01110111 
127.0.0.1:6379> bitcount m
(integer) 21
# BITPOS key bit [start] [end]: 1st position of 1 or 0 in the key in range. O(N)
127.0.0.1:6379> SET mykey "\xff\xf0\x00"
OK
127.0.0.1:6379> BITPOS mykey 0
(integer) 12

Oprócz operatorów działających na samym kluczu, BITOP operator jest używany do bitowych operacji logicznych między wieloma klawiszami.

# BITOP operation destkey key [key ...]. O(N)
# operation can be  AND, OR, XOR and NOT
127.0.0.1:6379> set a "\xff\xff"
OK
127.0.0.1:6379> bitop not nota a
(integer) 2
127.0.0.1:6379> get nota
"\x00\x00"
127.0.0.1:6379> set b "\x0f\x0f"
OK
127.0.0.1:6379> set c "\xf0\xf0"
OK
127.0.0.1:6379> BITOP OR orbc b c
(integer) 2
127.0.0.1:6379> get orbc
"\xff\xff"
127.0.0.1:6379> BITOP AND andbc b c
(integer) 2
127.0.0.1:6379> get andbc
"\x00\x00"
127.0.0.1:6379> BITOP XOR xorbc b c
(integer) 2
127.0.0.1:6379> get xorbc
"\xff\xff"

Wewnętrzne

Ponieważ operacje bitmapowe nie mają własnej struktury danych, nie ma specjalnej struktury danych do opisania. Same ciągi Redis są zaimplementowane jako binarny bezpieczny ciąg. Struktura danych ciągu Redis jest wewnętrznie nazywana Simple Dynamic String (SDS). Zasadniczo jest to natywny char [] z dodatkowymi informacjami księgowymi. Szczegóły implementacji można znaleźć tutaj.

Implementacja funkcji bitmapowych znajduje się w pliku bitops.c .

PS:Biorąc pod uwagę znaczenie algorytmów manipulacji bitami dla krytycznej funkcjonalności systemu operacyjnego i grafiki, większość architektur zapewnia specjalne instrukcje dla takich operacji. Dobrym miejscem do zapoznania się z różnymi interesującymi komputerowymi algorytmami arytmetycznymi jest ponadczasowy klasyczny Hacker’s Delight.

Aplikacje

Ten popularny blog GetSpool jest doskonałym przykładem wykorzystania bitmapy do analizy w czasie rzeczywistym dużego zestawu danych. Jest to również przykład klasycznego przypadku użycia mapy bitowej:do przechowywania informacji logicznych bardzo dużej domeny na (stosunkowo) małej przestrzeni przy zachowaniu przyzwoitej wydajności.

Rozmiar jest zwykle problemem w przypadku naprawdę dużych bitmap, ponieważ większość użytecznych operacji na nim to O(N). Aby uniknąć pracy z dużymi kluczami, dokumentacja Redis zaleca dzielenie dużych kluczy na wiele mniejszych. Wydajność BITCOUNT pozostaje akceptowalna, dopóki klucz nie stanie się duży. W tym momencie zaleca się, aby podzielić klucze lub użyć argumentów zakresu, aby wykonać zapytanie przyrostowe. Zaleceniem radzenia sobie z powolnymi operacjami BITOP jest uruchomienie go na urządzeniach podrzędnych. Ogólnie rzecz biorąc, sensowne jest zajmowanie się kluczami o średniej wielkości i planowanie przyszłego potencjalnego wzrostu poprzez podzielenie kluczy na wiele kluczy.

 Zestawy Redis a bitmapa Redis

Charakter funkcji zapewnianych przez Zestawy Redis i operacji bitmapowych jest podobny. Dlatego często myli się, które z dwóch podejść jest lepsze. Cóż, to naprawdę zależy od dokładnego charakteru przypadku użycia. Oczywiście ta dyskusja dotyczy tylko tego rodzaju operacji, które mogą osiągnąć zarówno zestawy, jak i bitmapa.

Zbiory Redis są ogólnie wydajne i dobrze skalowalne i powinny być wybraną strukturą danych, dopóki ich rozmiar nie stanie się nie do utrzymania. Zestawy Redis są również łatwiejsze w zarządzaniu, programowanie i debugowanie będą działać dobrze w większości aplikacji. Łatwość użycia zestawów nie powinna być lekceważona:kod manipulujący mapami bitowymi jest zwykle trudny do odczytania, zrozumienia, debugowania i utrzymania. Nawet jeśli domena jest bardzo duża, zestawy mogą być nadal odpowiednie. Dla m.in. jeśli aplikacja ma śledzić codzienne wizyty w popularnej witrynie e-commerce, wyniki mogą nadal dobrze pasować do zestawu, ponieważ zwykle tylko 5-10% całej bazy użytkowników odwiedza tę witrynę codziennie. To oczywiście zmienia się w przypadku witryny, w której oczekuje się, że 60% całej bazy użytkowników będzie logować się codziennie. Wtedy mapy bitowe stają się bardziej istotne, biorąc pod uwagę rozmiar i wydajność logicznych operacji bitowych na dużej liczbie kluczy. Zestawy Redis mają również tę wyraźną zaletę, że nie muszą mapować identyfikatorów na przesunięcia bitowe. Podobnie, jeśli twoje wartości pochodzą z domeny większej niż 2, zestawy Redis muszą być łatwiejsze w użyciu niż wymyślanie mechanizmów podziału domeny na bitmapę.

Analityka MOOC

Oto wymyślony (ale wystarczająco prawdziwy!) przykład miejsca, w którym można zastosować operacje bitmapowe Redis. Załóżmy, że prowadzisz bardzo popularny internetowy kurs MOOC, na który zapisało się setki tysięcy studentów. Zespół akademicki ułatwiający kurs chce pulpitu nawigacyjnego, w którym mogą zobaczyć w czasie rzeczywistym stan postępów studentów, a także ogólne tło zapisanych studentów. Decydujesz się zaimplementować to za pomocą operacji mapy bitowej Redis. Oto podejście do tego krok po kroku.

1. Utwórz plan mapowania między identyfikatorem ucznia a przesunięciem mapy bitowej. To może być tak proste, jak ID będące przesunięciem w bitmapie.
2. Twórz i wypełniaj różne mapy bitowe związane z danymi demograficznymi po rozpoczęciu kursu. Dla m.in. studenci zapisani na inne MOOC z tej samej uczelni, poziomu wykształcenia, płci itp.
3. Teraz w miarę postępu kursu możesz tworzyć nowe mapy bitowe, aby rejestrować postępy w kursie. Dla m.in. studenci, którzy ukończyli oglądanie wszystkich wykładów w tygodniu 1, studenci, którzy ukończyli wszystkie zadania w tygodniu 1 itd.
4. Teraz tworzenie analiz w czasie rzeczywistym na podstawie tych kluczy byłoby bardzo prostym ćwiczeniem i można je wykonać za pomocą interfejsu użytkownika typu „przeciągnij i upuść”. Na przykład

• Profesor, który chce zobaczyć, ilu studentów obejrzało wykłady w tygodniu 1 (A), ale nie wykonało zadania w tygodniu 1 (B):Operator:BITOP. Operacja:A I (NIE B).
• Uczeń, który wykonał wszystkie zadania w tygodniu 1 (A), tygodniu 2 (B), tygodniu 3 (C) i tygodniu 4 (D):Operator:BITOP. Operacja A I B ORAZ C I D. Powiedzmy, że to są osoby, które zaliczyły kurs.
• Wszyscy studenci płci męskiej (M), którzy zaliczyli kurs (jak obliczono powyżej, powiedzmy P):Operator:BITOP. Operacja:M I P.
• Liczba uczniów, którzy zaliczyli kurs:BITCOUNT P.

Podobnie, dowolna liczba interesujących kohort może być skonfigurowana jako bitmapy i takie permutacje mogą być na nich uruchamiane.

Przypis

Inne posty w naszej serii struktur danych Redis:

• Zestawy
• Hasze
• Posortowane zestawy