Bitmaps (ook wel bit-arrays, bitvectoren enz. genoemd) is de datastructuur die onmiddellijk in je opkomt als het nodig is om booleaanse informatie voor een enorm domein in een compacte vertegenwoordiging. Het is een zeer populaire gegevensstructuur wanneer geheugenruimte schaars is:OS-kernels (geheugenpagina's, inodes enz.), Digitale beeldverwerking enz.
Redis, een in-memory datastructuurserver, biedt ondersteuning voor bitmanipulatiebewerkingen. Er is echter geen speciale gegevensstructuur voor Bitmaps in Redis. In plaats daarvan worden bewerkingen op bitniveau ondersteund op de basis Redis-structuur:Strings. Nu is de maximale lengte voor Redis-strings 512 MB. Het grootste domein dat Redis als bitmap kan toewijzen is dus 2 (512 MB =2 bytes =2 bits).
Bit-gerelateerde bewerkingen in Redis zijn er in twee soorten:Constante tijd (O(1)) b.v. operaties om een bepaald bit te krijgen/in te stellen en operaties die O(N) zijn die in feite op een groep bits werken. N is in deze gevallen de lengte van de bits waaraan de bewerking moet werken. Laten we enkele voorbeelden bekijken.
Opdrachten
# 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
Behalve de operators die aan de sleutel zelf werken, is de BITOP operator wordt gebruikt voor bitsgewijze logische bewerkingen tussen meerdere sleutels.
# 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"
Intern
Aangezien bitmapbewerkingen geen eigen gegevensstructuur hebben, is er geen speciale gegevensstructuur om te beschrijven. De Redis-strings zelf zijn geïmplementeerd als een binaire veilige string. De gegevensstructuur van de Redis-string wordt intern Simple Dynamic String (SDS) genoemd. Het is in wezen een native char [] met wat aanvullende boekhoudkundige informatie. Implementatiedetails zijn hier te vinden.
De implementatie van de bitmapfuncties staat in het bestand bitops.c .
P.S.:Gezien het belang van algoritmen voor bitmanipulatie voor kritieke OS- en grafische functionaliteit, bieden de meeste architecturen speciale instructies voor dergelijke bewerkingen. Een goede plek om kennis te maken met verschillende interessante rekenalgoritmen voor computers is de tijdloze klassieker Hacker's Delight.
Toepassingen
Deze populaire GetSpool-blog is een goed voorbeeld van het gebruik van bitmap voor realtime analyses over een grote dataset. Het is ook een voorbeeld van het klassieke gebruik van een bitmap:om booleaanse informatie van een extreem groot domein op te slaan in een (relatief) kleine ruimte met behoud van behoorlijke prestaties.
Grootte is meestal een probleem voor echt grote bitmaps, aangezien de meest bruikbare bewerkingen erop O(N) zijn. Om het werken met grote sleutels te vermijden, raadt Redis-documentatie aan om grote sleutels in meerdere kleinere te splitsen. BITCOUNT-prestaties blijven acceptabel totdat de sleutel groot wordt. Op dat moment is de aanbeveling om de sleutels te splitsen of de bereikargumenten te gebruiken om incrementeel te zoeken. De aanbeveling om met trage BITOP-bewerkingen om te gaan, is om het op slaves uit te voeren. Dus over het algemeen is het logisch om met sleutels van gemiddelde grootte om te gaan en toekomstige potentiële groei te plannen door sleutels in meerdere sleutels te splitsen.
Redis-sets versus Redis-bitmap
De aard van de functionaliteit die wordt geboden door Redis Sets en de bitmapbewerkingen is vergelijkbaar. Het is dus vaak verwarrend welke van de twee benaderingen beter is. Nou, het hangt echt af van de exacte aard van de use-case. Het is duidelijk dat deze discussie alleen geldig is voor het soort bewerkingen dat zowel sets als bitmap kunnen bereiken.
Redis-sets zijn over het algemeen efficiënt en goed te schalen en zouden de voorkeursdatastructuur moeten zijn totdat de grootte onhoudbaar wordt. Redis-sets zijn ook gemakkelijker te beheren, programmeren en debuggen zou goed werken voor de meeste toepassingen. Het gebruiksgemak van Sets mag niet worden onderschat:code die bitmaps manipuleert, is meestal moeilijk te lezen, te begrijpen, te debuggen en te onderhouden. Zelfs als het domein erg groot is, kunnen sets nog steeds geschikt zijn. Voor bijv. als een toepassing bedoeld is om dagelijkse bezoeken aan populaire e-commercesites bij te houden, kunnen de resultaten nog steeds goed in een reeks passen, aangezien gewoonlijk slechts 5-10% van het volledige gebruikersbestand de site dagelijks bezoekt. Dit verandert uiteraard voor een site waar naar verwachting 60% van het gehele gebruikersbestand dagelijks inlogt. Bitmaps worden dan relevanter gezien de grootte en prestaties van logische bitsgewijze bewerkingen over een groot aantal sleutels. Redis-sets hebben ook het duidelijke voordeel dat ze geen ID's hoeven toe te wijzen aan bit-offsets. Evenzo, als uw waarden afkomstig zijn uit een domein dat groter is dan 2, dan zijn Redis-sets gemakkelijker te gebruiken dan het bedenken van mechanismen om het domein voor bitmap te splitsen.
Analyse voor een MOOC
Hier is een verzonnen (maar echt genoeg!) voorbeeld voor een plaats waar men Redis-bitmapbewerkingen zou kunnen toepassen. Stel, u runt een zeer populaire online MOOC waarvoor honderdduizenden studenten zich hebben ingeschreven. Het academische team dat de cursus faciliteert, wil een dashboard waar ze realtime de voortgang van studenten kunnen zien, evenals de algemene achtergrond van ingeschreven studenten. U besluit dit te implementeren via Redis-bitmapbewerkingen. Hier is een stapsgewijze benadering ervan.
- Maak een plan om een kaart te maken tussen student-ID en bitmap-offset. Het kan zo simpel zijn als de ID die de offset in de bitmap is.
- Maak en vul verschillende demografisch gerelateerde bitmaps zodra de cursus begint. Voor bijv. studenten ingeschreven in andere MOOC's van dezelfde universiteit, opleidingsniveau, geslacht enz.
- Nu de cursus vordert, kun je nieuwe bitmaps maken om de voortgang van de cursus vast te leggen. Voor bijv. studenten die alle colleges van week 1 hebben bekeken, studenten die alle opdrachten van week 1 hebben voltooid, enz.
- Het maken van realtime analyses op basis van deze sleutels zou een heel eenvoudige oefening zijn en kan worden gedaan met een gebruikersinterface met slepen en neerzetten. Voor bijv.
- Een professor die wil zien hoeveel studenten de colleges van week 1 (A) hebben bekeken maar de opdracht van week 1 (B) niet hebben voltooid:Operator:BITOP. Bediening:A AND (NIET B).
- Leerling die alle opdrachten voor week 1 (A), week 2 (B), week 3 (C) en week 4 (D) heeft voltooid:Operator:BITOP. Operatie A EN B EN C EN D. Zeg, dit zijn de mensen die de cursus hebben gehaald.
- Alle mannelijke studenten (M) die geslaagd zijn voor de cursus (zoals hierboven berekend, bijvoorbeeld P):Operator:BITOP. Bediening:M EN P.
- Aantal studenten dat geslaagd is voor de cursus:BITCOUNT P.
Evenzo kan een willekeurig aantal interessante cohorten worden ingesteld als bitmaps en dergelijke permutaties worden daarop uitgevoerd.
Voetnoot
Andere berichten in onze reeks Redis-gegevensstructuren:
- Sets
- Hashes
- Gesorteerde sets