Bitmaps (også kaldet bitarrays, bitvektorer osv.) er den datastruktur, der straks dukker op i dit hoved, når behovet er at kortlægge boolesk information for et enormt domæne til et kompakt repræsentation. Det er en meget populær datastruktur, når hukommelsespladsen er begrænset:OS-kerner (hukommelsessider, inoder osv.), digital billedbehandling osv.
Redis, som er en datastrukturserver i hukommelsen, understøtter bitmanipulationsoperationer. Der er dog ikke en særlig datastruktur for Bitmaps i Redis. Bitniveau-operationer understøttes snarere på den grundlæggende Redis-struktur:Strings. Nu er den maksimale længde for Redis-strenge 512 MB. Således er det største domæne, som Redis kan kortlægge som en bitmap, 2 (512 MB =2 bytes =2 bit).
Bitrelaterede operationer i Redis er af to slags:Konstant tid (O(1)) f.eks. operationer for at få/sætte en bestemt bit og operationer, der er O(N), som grundlæggende opererer på en gruppe af bit. N i disse tilfælde er længden af bits, som operationen skal arbejde på. Lad os se på nogle eksempler.
Kommandoer
# 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
Udover der operatører, der arbejder på selve nøglen, er BITOP operator bruges til bitvise logiske operationer mellem flere nøgler.
# 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"
Internal
Da bitmaphandlinger ikke har en egen datastruktur, er der ikke en særlig datastruktur at beskrive. Selve Redis-strengene er implementeret som en binær sikker streng. Redis strengdatastruktur kaldes internt Simple Dynamic String (SDS). Det er i bund og grund en indfødt char [] med nogle ekstra bogføringsoplysninger. Implementeringsdetaljer kan findes her.
Implementeringen af bitmapfunktionerne er i filen bitops.c .
PS:I betragtning af vigtigheden af bitmanipulationsalgoritmer for kritisk OS og grafikfunktionalitet, giver de fleste arkitekturer specielle instruktioner til sådanne operationer. Et godt sted at læse op på forskellige interessante computeraritmetiske algoritmer er den tidløse klassiker Hacker's Delight.
Applikationer
Denne populære GetSpool-blog er et godt eksempel på brug af bitmap til realtidsanalyse over et stort datasæt. Det er også et eksempel på det klassiske brugstilfælde af en bitmap:at gemme boolsk information om et ekstremt stort domæne på (relativt) lille plads og samtidig bevare en anstændig ydeevne.
Størrelse er normalt et problem for virkelig store bitmaps, da de fleste nyttige operationer over det er O(N). For at undgå at arbejde med store nøgler anbefaler Redis dokumentation at opdele enorme nøgler i flere mindre. BITCOUNT ydeevne forbliver acceptabel, indtil nøglen bliver stor. På det tidspunkt er anbefalingen enten at opdele nøglerne eller bruge områdeargumenterne til at forespørge trinvist. Anbefalingen til at håndtere langsomme BITOP-operationer er at køre det på slaver. Så generelt giver det mening at beskæftige sig med moderat størrelse nøgler og planlægge for fremtidig potentiel vækst ved at opdele nøgler i flere nøgler.
Redis Sets vs Redis Bitmap
Karakteren af funktionalitet, der leveres af Redis Sets, og bitmap-handlingerne er ens. Så det er ofte forvirrende, hvilken af de to tilgange der er bedre. Nå, det afhænger virkelig af den nøjagtige karakter af use casen. Denne diskussion er naturligvis kun gyldig for den type operationer, som både sæt og bitmap kan opnå.
Redis-sæt er generelt effektive og skaleres godt og bør være den valgte datastruktur, indtil størrelsen bliver uholdbar. Redis-sæt er også lettere at administrere, programmering og fejlretning ville fungere godt for de fleste applikationer. Brugervenligheden af sæt skal ikke undervurderes:Kode, der manipulerer bitmaps, er normalt svær at læse, forstå, fejlfinde og vedligeholde. Selv når domænet er meget stort, kan sæt stadig være passende. For f.eks. hvis en applikation er beregnet til at spore daglige besøg på en populær e-handelsside, kan resultaterne stadig passe godt ind i et sæt, da normalt kun 5-10 % af hele brugerbasen besøger webstedet dagligt. Dette ændrer sig naturligvis for et websted, hvor 60% af hele brugerbasen forventes at logge ind dagligt. Så bliver bitmaps mere relevante i betragtning af størrelsen og ydeevnen af logiske bitvise operationer over et stort antal nøgler. Redis-sæt har også den klare fordel, at de ikke skal tilknytte id'er til bit-offsets. Tilsvarende, hvis dine værdier er fra et domæne, der er større end 2, så er Redis-sæt nemmere at bruge end at finde ud af mekanismer til at opdele domænet til bitmap.
Analyse til en MOOC
Her er et opdigtet (men reelt nok!) eksempel på et sted, hvor man kan anvende Redis bitmap-operationer. Lad os sige, at du kører en meget populær online MOOC, som hundredtusindvis af studerende har tilmeldt sig. Det akademiske team, der faciliterer kurset, ønsker et dashboard, hvor de kan se realtidsstatus for studerendes fremskridt samt den generelle baggrund for tilmeldte studerende. Du beslutter dig for at implementere dette via Redis bitmap-operationer. Her er en trinvis tilgang til det.
- Opret en plan for at kortlægge mellem elev-id til bitmap-offset. Det kunne være så simpelt som at ID'et er forskydningen i bitmap'et.
- Opret og udfyld forskellige demografiske relaterede bitmaps, når kurset begynder. For f.eks. studerende indskrevet på andre MOOC'er fra samme universitet, uddannelsesniveau, køn osv.
- Nu som kurset skrider frem, kan du oprette nye bitmaps for at registrere kursets fremskridt. For f.eks. studerende, der gennemførte at se alle forelæsninger i uge 1, studerende, der gennemførte alle opgaver i uge 1 osv.
- Nu ville det være en meget simpel øvelse at oprette realtidsanalyse baseret på disse taster og kan udføres på en træk og slip brugergrænseflade. For f.eks.
- En professor, der vil se, hvor mange studerende, der har set forelæsningerne i uge 1 (A), men ikke har fuldført opgaven i uge 1 (B):Operatør:BITOP. Betjening:A OG (IKKE B).
- Elev, der har udført alle opgaverne for uge 1 (A), uge 2 (B), uge 3 (C) og uge 4 (D):Operatør:BITOP. Operation A OG B OG C OG D. Sig, det er de personer, der bestod kurset.
- Alle mandlige studerende (M), der bestod kurset (som beregnet ovenfor, f.eks. P):Operatør:BITOP. Betjening:M OG P.
- Antal elever, der har bestået kurset:BITCOUNT P.
På samme måde kan et hvilket som helst antal interessante kohorter konfigureres som bitmaps, og sådanne permutationer kører på dem.
Fodnote
Andre indlæg i vores Redis-datastrukturserie:
- Sæt
- Hashes
- Sorterede sæt