Bitmappar (även kallade bitarrayer, bitvektorer etc.) är datastrukturen som omedelbart dyker upp i ditt huvud när behovet är att mappa boolesk information för en enorm domän till en kompakt representation. Det är en mycket populär datastruktur närhelst minnesutrymmet är begränsat:OS-kärnor (minnessidor, inoder etc.), digital bildbehandling etc.
Redis, som är en datastrukturserver i minnet, ger stöd för bitmanipuleringsoperationer. Det finns dock ingen speciell datastruktur för bitmappar i Redis. Snarare stöds operationer på bitnivå på den grundläggande Redis-strukturen:Strings. Nu är den maximala längden för Redis-strängar 512 MB. Den största domänen som Redis kan mappa som en bitmapp är alltså 2 (512 MB =2 byte =2 bitar).
Bitrelaterade operationer i Redis är av två slag:Konstant tid (O(1)) t.ex. operationer för att få/ställa in en viss bit och operationer som är O(N) som i princip fungerar på en grupp av bitar. N i dessa fall är längden på bitar som operationen behöver arbeta med. Låt oss titta på några exempel.
Kommandon
# 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
Förutom det finns operatorer som arbetar på själva nyckeln, BITOP operatorn används för bitvis logiska operationer mellan flera nycklar.
# 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"
Internt
Eftersom bitmappsoperationer inte har en egen datastruktur, finns det ingen speciell datastruktur att beskriva. Själva Redis-strängarna är implementerade som en binär säker sträng. Redis strängdatastruktur kallas internt Simple Dynamic String (SDS). Det är i huvudsak en infödd char [] med ytterligare bokföringsinformation. Implementeringsdetaljer finns här.
Implementeringen av bitmappsfunktionerna finns i filen bitops.c .
PS:Med tanke på vikten av bitmanipuleringsalgoritmer för kritiska operativsystem och grafikfunktioner, tillhandahåller de flesta arkitekturer speciella instruktioner för sådana operationer. Ett bra ställe att läsa på om olika intressanta aritmetiska datoralgoritmer är den tidlösa klassikern Hacker's Delight.
Applikationer
Denna populära GetSpool-blogg är ett bra exempel på användning av bitmapp för realtidsanalys över en stor datamängd. Det är också ett exempel på det klassiska användningsfallet för en bitmapp:att lagra boolesk information om en extremt stor domän i (relativt) litet utrymme med bibehållen prestanda.
Storlek är vanligtvis ett problem för riktigt stora bitmappar, eftersom de mest användbara operationerna över den är O(N). För att undvika att arbeta med stora nycklar rekommenderar Redis dokumentation att dela upp stora nycklar i flera mindre. BITCOUNT-prestanda förblir acceptabel tills nyckeln blir stor. Vid den tidpunkten är rekommendationen att antingen dela upp nycklarna eller använda intervallargumenten för att fråga stegvis. Rekommendationen för att hantera långsamma BITOP-operationer är att köra den på slavar. Så i allmänhet är det vettigt att ta itu med måttliga nycklar och planera för framtida potentiell tillväxt genom att dela upp nycklar i flera nycklar.
Redis Sets vs Redis Bitmap
Funktionaliteten som tillhandahålls av Redis Sets och bitmappsoperationerna är liknande. Så det är ofta förvirrande vilket av de två tillvägagångssätten som är bättre. Tja, det beror verkligen på den exakta typen av användningsfall. Uppenbarligen är den här diskussionen endast giltig för den typ av operationer som både set och bitmapp kan uppnå.
Redis-uppsättningar är i allmänhet effektiva och skalas väl och bör vara den valda datastrukturen tills dess storlek blir ohållbar. Redis Sets är också lättare att hantera, programmering och felsökning skulle fungera bra för de flesta applikationer. Användarvänligheten för Sets bör inte underskattas:Kod som manipulerar bitmappar är vanligtvis svår att läsa, förstå, felsöka och underhålla. Även när domänen är mycket stor kan uppsättningar fortfarande vara lämpliga. För t.ex. om en applikation är avsedd att spåra dagliga besök på en populär e-handelswebbplats, kan resultaten ändå passa väl in i en uppsättning eftersom vanligtvis bara 5-10 % av hela användarbasen kommer att besöka webbplatsen dagligen. Detta förändras uppenbarligen för en webbplats där 60 % av hela användarbasen förväntas logga in dagligen. Då blir bitmappar mer relevanta med tanke på storleken och prestandan av logiska bitvisa operationer över ett stort antal nycklar. Redis Sets har också den distinkta fördelen att de inte behöver mappa ID:n till bitoffset. På liknande sätt, om dina värden kommer från en domän som är större än 2, så är Redis Sets enklare att använda än att ta reda på mekanismer för att dela domänen för bitmapp.
Analytics för en MOOC
Här är ett sammanfattat (men tillräckligt verkligt!) exempel på en plats där man kan tillämpa Redis-bitmappsoperationer. Säg att du kör en mycket populär online MOOC som hundratusentals studenter har anmält sig till. Det akademiska teamet som underlättar kursen vill ha en instrumentpanel där de kan se realtidsstatus för studenters framsteg samt den allmänna bakgrunden för inskrivna studenter. Du bestämmer dig för att implementera detta via Redis bitmappsoperationer. Här är ett steg för steg tillvägagångssätt.
- Skapa en plan för att mappa mellan student-ID till bitmappsoffset. Det kan vara så enkelt som att ID är förskjutningen i bitmappen.
- Skapa och fyll i olika demografiska relaterade bitmappar när kursen börjar. För t.ex. studenter som är inskrivna i andra MOOC från samma universitet, utbildningsnivå, kön etc.
- Nu när kursen fortskrider kan du skapa nya bitmappar för att registrera kursframsteg. För t.ex. studenter som har tittat på alla föreläsningar under vecka 1, studenter som gjort alla uppgifter från vecka 1 osv.
- Nu skulle det vara en mycket enkel övning att skapa realtidsanalyser baserade på dessa nycklar och kan göras med ett dra-och-släpp-gränssnitt. För t.ex.
- En professor som vill se hur många studenter som tittade på föreläsningarna för vecka 1 (A) men inte klarade uppgiften för vecka 1 (B):Operatör:BITOP. Funktion:A OCH (INTE B).
- Elev som gjort alla uppgifter för vecka 1 (A), vecka 2 (B), vecka 3 (C) och vecka 4 (D):Operatör:BITOP. Operation A OCH B OCH C OCH D. Säg att det här är personerna som klarade kursen.
- Alla manliga studenter (M) som klarat kursen (som beräknat ovan, säg P):Operatör:BITOP. Drift:M OCH P.
- Antal studenter som klarat kursen:BITCOUNT P.
På liknande sätt kan valfritt antal intressanta kohorter ställas in som bitmappar och sådana permutationer körs på dem.
Fotnot
Andra inlägg i vår Redis-datastrukturserie:
- Set
- Hashar
- Sorterade uppsättningar