Въведение в Redis Data Structures:Bitmaps

Растровите изображения (наричани още битови масиви, битови вектори и т.н.) са структурата от данни, която веднага изниква в главата ви, когато е необходимо да съпоставите булева информация за огромен домейн в компактен представителство. Това е много популярна структура от данни, когато пространството в паметта е на първо място:ядра на ОС (страници с памет, inodes и т.н.), цифрови изображения и т.н.

Redis, като сървър за структура на данни в паметта, осигурява поддръжка за операции за манипулиране на битове. Въпреки това, няма специална структура от данни за растерни изображения в Redis. По-скоро операциите на битово ниво се поддържат в основната структура на Redis:низове. Сега максималната дължина за низовете на Redis е 512 MB. По този начин най-големият домейн, който Redis може да картографира като растерна карта, е 2 (512 MB =2 байта =2 бита).

Свързаните с битове операции в Redis са два вида:Постоянно време (O(1)), напр. операции за получаване/задаване на конкретен бит и операции, които са O(N), които основно оперират с група битове. N в тези случаи е дължината на битовете, върху които ще трябва да работи операцията. Нека разгледаме някои примери.

Команди

# 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

Освен операторите, които работят върху самия ключ, BITOP операторът се използва за побитови логически операции между множество клавиши.

# 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"

Вътрешни елементи

Тъй като операциите с растерни изображения нямат собствена структура на данни, няма специална структура от данни, която да се опише. Самите низове на Redis се изпълняват като двоичен безопасен низ. Структурата на низовите данни на Redis се нарича вътрешно прост динамичен низ (SDS). По същество това е роден char [] с допълнителна счетоводна информация. Подробности за внедряването можете да намерите тук.

Внедряването на функциите за растерна графика е във файла bitops.c .

P.S.:Като се има предвид значението на алгоритмите за манипулиране на битове за критична операционна и графична функционалност, повечето архитектури предоставят специални инструкции за такива операции. Добро място за четене на различни интересни компютърни аритметични алгоритми е вечната класическа Hacker’s Delight.

Приложения

Този популярен блог на GetSpool е чудесен пример за използване на растерни изображения за анализ в реално време върху голям набор от данни. Това също е пример за  класическия случай на използване на растерното изображение:да се съхранява булева информация за изключително голям домейн в (сравнително) малко пространство, като се запазва прилична производителност.

Размерът обикновено е проблем за наистина големи растерни изображения, тъй като повечето полезни операции над него са O(N). За да избегнете работа с огромни ключове, документацията на Redis препоръчва разделянето на огромни ключове на множество по-малки. Производителността на BITCOUNT остава приемлива, докато ключът стане голям. В този момент препоръката е или да разделите ключовете, или да използвате аргументите на диапазона за поетапно запитване. Препоръката за справяне с бавни BITOP операции  е да го стартирате на подчинени. Така че като цяло има смисъл да се занимавате с клавиши с умерен размер и да планирате бъдещ потенциален растеж, като разделите ключовете на множество клавиши.

 Redis Sets срещу Redis Bitmap

Естеството на функционалността, предоставена от Redis Sets и операциите с растерни изображения, е сходна. Така че често се обърква кой от двата подхода е по-добър. Е, наистина зависи от точното естество на случая на употреба. Очевидно тази дискусия е валидна само за вида операции, които могат да постигнат както наборите, така и растерното изображение.

Наборите на Redis като цяло са ефективни и се мащабират добре и трябва да бъдат предпочитаната структура от данни, докато размерът им стане несъстоятелен. Наборите Redis също са по-лесни за управление, програмирането и отстраняването на грешки биха работили добре за повечето приложения. Не бива да се подценява лекотата на използване на наборите:кодът, който манипулира растерни изображения, обикновено е труден за четене, разбиране, отстраняване на грешки и поддръжка. Дори когато домейнът е много голям, наборите може да са подходящи. За напр. ако приложението е предназначено да проследява ежедневните посещения на популярен сайт за електронна търговия, резултатите все пак може да се впишат добре в набор, тъй като обикновено само 5-10% от цялата потребителска база ще посещават сайта ежедневно. Това очевидно се променя за сайт, където се очаква 60% от цялата потребителска база да влизат ежедневно. Тогава растерните изображения стават по-подходящи, като се има предвид размера и производителността на логическите побитови операции над голям брой ключове. Наборите Redis също имат ясното предимство, че не се налага да съпоставят идентификатори с битови отмествания. По същия начин, ако вашите стойности са от домейн, по-голям от 2, тогава Redis Sets трябва да са по-лесни за използване, отколкото да се измислят механизми за разделяне на домейна за растерно изображение.

Аналитика за MOOC

Ето един измислен (но достатъчно реален!) пример за място, където може да се прилагат Redis растерни операции. Да речем, че управлявате много популярен онлайн MOOC, в който са се записали стотици хиляди студенти. Академичният екип, който улеснява курса, иска табло за управление, където да могат да виждат в реално време състоянието на напредъка на студентите, както и общия фон на записаните студенти. Решавате да приложите това чрез Redis bitmap операции. Ето подход стъпка по стъпка към него.

1. Създайте план за съпоставяне между студентския идентификатор и изместването на растерното изображение. Може да е толкова просто, колкото идентификационният номер да бъде изместването в растерната карта.
2. Създавайте и попълвайте различни демографски свързани растерни изображения, след като курсът започне. За напр. студенти, записани в други MOOC от същия университет, ниво на образование, пол и др.
3. Сега, докато курсът напредва, можете да създавате нови растерни изображения, за да записвате напредъка на курса. За напр. студенти, завършили гледането на всички лекции от седмица 1, студенти, завършили всички задачи от седмица 1. и т.н.
4. Сега създаването на анализи в реално време въз основа на тези ключове би било много просто упражнение и може да се извърши с потребителски интерфейс с плъзгане и пускане. За напр.

• Професор, който иска да види колко студенти са гледали лекциите за седмица 1 (A), но не са изпълнили задачата за седмица 1 (B):Оператор:BITOP. Операция:А И (НЕ Б).
• Ученик, който е изпълнил всички задачи за седмица 1 (A), седмица 2 (B), седмица 3 (C) и седмица 4 (D):Оператор:BITOP. Операция А И Б И В И D. Кажете, това са хората, преминали курса.
• Всички ученици от мъжки пол (M), преминали курса (както е изчислено по-горе, да речем, P):Оператор:BITOP. Операция:M И P.
• Брой студенти, преминали курса:BITCOUNT P.

По същия начин, произволен брой интересни кохорти могат да бъдат настроени като растерни изображения и такива пермутации да се изпълняват върху тях.

Бележка под линия

Други публикации в нашата серия от структури от данни на Redis:

• Набори
• Хешове
• Сортирани набори