Úvod do datových struktur Redis:Bitmapy

Bitmapy (také nazývané bitová pole, bitové vektory atd.) je datová struktura, která se vám okamžitě objeví, když potřebujete zmapovat booleovské informace pro obrovskou doménu do kompaktního reprezentace. Je to velmi oblíbená datová struktura vždy, když je paměťový prostor na prvním místě:jádra OS (paměťové stránky, inody atd.), digitální zobrazování atd.

Redis, jakožto server datové struktury v paměti, poskytuje podporu pro operace bitové manipulace. V Redis však neexistuje speciální datová struktura pro bitmapy. Operace na úrovni bitů jsou spíše podporovány v základní struktuře Redis:Řetězce. Nyní je maximální délka pro řetězce Redis 512 MB. Největší doména, kterou může Redis mapovat jako bitmapa, je tedy 2 (512 MB =2 bajty =2 bity).

Operace související s bity v Redis jsou dvojího druhu:Konstantní čas (O(1)), např. operace pro získání/nastavení konkrétního bitu a operace, které jsou O(N), které v podstatě fungují na skupině bitů. N je v těchto případech délka bitů, na kterých bude operace muset pracovat. Podívejme se na několik příkladů.

Příkazy

# 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

Kromě operátorů, které fungují na samotném klíči, BITOP Operátor se používá k bitovým logickým operacím mezi více klíči.

# 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í informace

Protože bitmapové operace nemají vlastní datovou strukturu, neexistuje žádná speciální datová struktura, kterou by bylo možné popsat. Samotné řetězce Redis jsou implementovány jako binární bezpečný řetězec. Řetězcová datová struktura Redis se interně nazývá Simple Dynamic String (SDS). Je to v podstatě nativní char [] s některými dalšími informacemi o vedení účetnictví. Podrobnosti o implementaci naleznete zde.

Implementace bitmapových funkcí je v souboru bitops.c .

P.S.:Vzhledem k důležitosti algoritmů pro manipulaci s bity pro kritické funkce operačního systému a grafiky poskytuje většina architektur speciální instrukce pro takové operace. Dobrým místem k přečtení různých zajímavých počítačových aritmetických algoritmů je nadčasová klasika Hacker’s Delight.

Aplikace

Tento oblíbený blog GetSpool je skvělým příkladem použití bitmapy pro analýzu v reálném čase u velkého souboru dat. Je to také příklad klasického případu použití bitmapy:ukládat booleovské informace extrémně velké domény do (relativně) malého prostoru při zachování slušného výkonu.

Velikost je obvykle problémem u opravdu velkých bitmap, protože většina užitečných operací nad nimi je O(N). Abyste se vyhnuli práci s velkými klíči, doporučuje dokumentace Redis rozdělit velké klíče na několik menších. Výkon BITCOUNT zůstane přijatelný, dokud se klíč nezvětší. V tomto okamžiku se doporučuje buď rozdělit klíče, nebo použít argumenty rozsahu k přírůstkovému dotazování. Doporučení, jak se vypořádat s pomalými operacemi BITOP, je spouštět je na podřízených. Obecně má tedy smysl zabývat se středně velkými klíči a plánovat budoucí potenciální růst rozdělením klíčů do více klíčů.

 Redis Sets vs Redis Bitmap

Povaha funkcí poskytovaných sadami Redis a bitmapové operace jsou podobné. Často je tedy matoucí, který z těchto dvou přístupů je lepší. No, to opravdu záleží na přesné povaze případu použití. Je zřejmé, že tato diskuse platí pouze pro ty druhy operací, kterých mohou dosáhnout jak sady, tak bitmapa.

Sady Redis jsou obecně účinné a dobře škálovatelné a měly by být preferovanou datovou strukturou, dokud se jejich velikost nestane neudržitelnou. Sady Redis se také snáze spravují, programování a ladění by fungovalo dobře pro většinu aplikací. Snadné použití sad by se nemělo podceňovat:Kód, který manipuluje s bitmapami, je obvykle obtížné číst, pochopit, ladit a udržovat. I když je doména velmi velká, sady mohou být stále vhodné. Pro např. pokud je aplikace určena ke sledování denních návštěv oblíbeného webu elektronického obchodu, výsledky mohou stále dobře zapadat do souboru, protože web obvykle navštíví pouze 5–10 % z celé uživatelské základny. To se samozřejmě mění u webu, kde se očekává, že se denně přihlásí 60 % celé uživatelské základny. Poté se bitmapy stanou relevantnějšími vzhledem k velikosti a výkonu logických bitových operací s velkým počtem klíčů. Sady Redis mají také výraznou výhodu v tom, že nemusí mapovat ID na bitové offsety. Podobně, pokud jsou vaše hodnoty z domény větší než 2, musí být Redis Sets jednodušší na použití než zjišťování mechanismů pro rozdělení domény pro bitmapu.

Analytika pro MOOC

Zde je vymyšlený (ale dostatečně skutečný!) příklad místa, kde lze použít bitmapové operace Redis. Řekněme, že provozujete velmi populární online MOOC, do kterého se zapsaly stovky tisíc studentů. Akademický tým usnadňující kurz chce řídicí panel, kde by mohl v reálném čase vidět stav pokroku studentů a také obecné pozadí zapsaných studentů. Rozhodnete se to implementovat pomocí bitmapových operací Redis. Zde je postup krok za krokem.

1. Vytvořte plán mapování mezi ID studenta a bitmapovým offsetem. Mohlo by to být tak jednoduché, že ID je posun v bitmapě.
2. Jakmile kurz začne, vytvořte a naplňte různé demografické bitmapy. Pro např. studenti zapsaní v jiných MOOC ze stejné univerzity, úrovně vzdělání, pohlaví atd.
3. Nyní, jak kurz postupuje, můžete vytvářet nové bitmapy pro záznam průběhu kurzu. Pro např. studenti, kteří dokončili sledování všech přednášek 1. týdne, studenti, kteří dokončili všechny úkoly 1. týdne atd.
4. Vytváření analýzy v reálném čase založené na těchto klíčích by nyní bylo velmi jednoduchým cvičením a lze jej provádět pomocí uživatelského rozhraní přetažením. Například

• Profesor, který chce vidět, kolik studentů, kteří sledovali přednášky v 1. týdnu (A), ale nedokončili úkol v 1. týdnu (B):Operátor:BITOP. Operace:A AND (NE B).
• Student, který dokončil všechny úkoly pro týden 1 (A), týden 2 (B), týden 3 (C) a týden 4 (D):Operátor:BITOP. Operace A AND B AND C AND D. Řekněme, že toto jsou lidé, kteří prošli kurzem.
• Všichni studenti (M), kteří prošli kurzem (podle výpočtu výše, řekněme P):Operátor:BITOP. Operace:M AND P.
• Počet studentů, kteří prošli kurzem:BITCOUNT P.

Podobně lze jako bitmapy nastavit libovolný počet zajímavých kohort a spustit na nich takovéto permutace.

Poznámka pod čarou

Další příspěvky v naší sérii datových struktur Redis:

• Sady
• Hashes
• Seřazené sady