Під капотом Redis: Хеш таблиця (частина 2) і Список

першої частини я сказав, що хеш таблиця це трохи LIST, SET SORTED SET. Судіть самі — LIST складається з ziplist/linkedlist, SET складається з dict/intset, а SORTED SET це ziplist/skiplist. Ми вже розглянули словник (dict), а у другій частині статті будемо розглядати структуру ziplist — другу найбільш часто застосовується структуру під капотом Redis. Подивимося на LIST — друга частина його «кухні» це проста реалізація зв'язного списку. Це знадобиться нам, щоб уважно розглянути часто згадуваний рада про оптимізацію хеш-таблиць через їх заміну на списки. Порахуємо скільки пам'яті потрібно на накладні витрати при використанні цих структур, яку ціну ви платите за економію пам'яті. Підведемо підсумки при роботі з хеш-таблиць, при використанні кодування в ziplist.

Минулого разу ми закінчили на тому, що збережені з використанням ziplist 1,000,000 ключів зайняли 16 мб оперативної пам'яті, тоді як в dict ці ж дані зажадали 104 мб (ziplist в 6 разів менше!). Давайте розбиратися якою ціною:


Отже, ziplist — це двусвязный список. На відміну від звичайного зв'язного списку, тут посилання в кожному вузлі вказують на попередній і на наступний вузол в списку. За двусвязному списком можна ефективно пересуватися в будь-якому напрямі — як до початку, так і кінця. У цьому списку простіше проводити видалення і перестановку елементів, так як легко доступні адреси тих елементів списку, покажчики яких спрямовані на змінний елемент. Розробники Redis позиціонують свою реалізацію як ефективну з точки зору пам'яті. Список вміє зберігати рядки і цілі числа, числа зберігаються саме у вигляді чисел, а не redisObject зі значенням. А якщо ви захочете зберегти рядок «123» вона буде збереження як число 123, а не послідовність символів`1`,`2`,`3`.
В гілці 1.х Redis замість dict в словнику використовувався zipmap — дуже проста (~140 рядків) реалізація зв'язного списку, оптимізована на економію пам'яті, де всі операції займають O(n). Ця структура не використовується в Redis (хоч і перебуває у його основи і підтримується в актуальному стані), при цьому частина ідей zipmap лягли в основу ziplist.
Ключ і значення зберігаються як розташовані один за одним елементи списку. Операції над списком це пошук ключа, через перебір і робота зі значенням, яке розташування наступного елемента списку. Теоретично операції вставки та зміни виконуються за константна O(1). Фактично ж будь-яка така операція в реалізації Redis вимагає виділення і перерозподілу пам'яті і реальна складність
безпосередньо залежить від кількості вже використаної пам'яті. В даному випадку пам'ятаємо про O(1) як ідеальний випадок і O(n) — як найгірший.
+-------------+------+-----+-------+-----+-------+-----+
| Total Bytes | Tail | Len | Entry | ... | Entry | End | 
+-------------+------+-----+-------+-----+-------+-----+
^ 
| 
+-------------------+--------------+----------+------+-------------+----------+-------+
| Prev raw len size | Prev raw len | Len size | Len | Header size | Encoding | Value | 
+-------------------+--------------+----------+------+-------------+----------+-------+

Подивіться на цю структуру в исходниках
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))

typedef struct zlentry {
unsigned int prevrawlensize, prevrawlen;
unsigned int lensize, len;
unsigned int headersize;
unsigned char encoding;
unsigned char *p;
} zlentry;


Давайте порахуємо її розмір.
Відповідь на питання, скільки пам'яті буде використано насправді, залежить від операційної системи, компілятора, типу вашого процесу і використовуваного аллокатора(в redis за замовчуванням jemalloc). Всі подальші розрахунки я наводжу для redis 3.0.5 зібраному на 64-бітному сервері під управлінням centos 7.
З заголовком все просто — це ZIPLIST_HEADER_SIZE (константа, визначена в ziplist.c і дорівнює sizeof(uint32_t) * 2 + sizeof(uint16_t) + 1). Розмір елемента — 5 * size_of(unsigned int) + 1 + 1не менше 1 байта на значення. Загальний оверхед на зберігання даних у такому кодуванні для n елементів (без урахування значення):
12 + 21 * n
Кожний елемент починається з фіксованого заголовка, що складається з декількох фрагментів з інформацією. Перший — розмір попереднього елемента і використовується для переходу назад двусвязному списком. Другий, кодування з опціональною довжиною самої структури в байтах. Довжина попереднього елемента працює наступним чином: якщо довжина не перевищує 254 байта (вона ж константа ZIP_BIGLEN) буде використано 1 байт для зберігання довжини значення. Якщо довжина перевищує або дорівнює 254, буде використано 5 байт. При цьому перший байт буде встановлений в константне значення ZIP_BIGLEN, щоб ми розуміли, що у нас довге значення. Решта 4 байта зберігають довжину попереднього значення. Третій — заголовок, який залежить від міститься у вузлі значення. Якщо значення рядок — 2 перших біта заголовка поля заголовка будуть зберігати тип кодування довжини рядка, з наступним числом з довжиною рядка. Якщо значние — ціле, перші 2 біта буде виставлено в одиницю. Для чисел використовується ще 2 біта, які визначають, який розмірності ціле в ньому зберігається.
Розшифровка заголовка, для бажаючих заморочити
Як лежить Байт Що лежить
|00pppppp| 1 Рядок, значення якого менше або дорівнює 63 байта (тобто sds REDIS_ENCODING_EMBSTR, див. першу частину серії
|01pppppp|B1 байт| 2 Рядок, значення якого менше або дорівнює 16383 байт (14 біт)
|10______|BBBBB4 байта| 5 Рядок, значення якого більше або дорівнює 16384 байт
|11000000| 1 Ціле, int16_t (2 байта)
|11010000| 1 Ціле, int32_t (4 байта)
|11100000| 1 Ціле, int64_t (8 байт)
|11110000| 1 Ціле зі знаком, що «влізе» 24 біта (3 байти)
|11111110| 1 Ціле зі знаком, що «влізе» 8 біт(1 байт)
|1111xxxx| 1 Де xxxx лежить між 0000 і 1101 означає ціле, які «влізе» в 4 біта. Без знакове ціле від 0 до 12. Декодированное значення за фактом від 1 до 13, адже 1111 0000 і вже зайняті і ми завжди віднімаємо 1 з декодувати значення, щоб отримати шукане.
|11111111| 1 Маркер кінця списку

Перевіримо і подивимося на зворотний бік бік медалі. Ми будемо використовувати LUA, так що вам не потрібно нічого крім Redis, щоб повторити цей тест самостійно. Спочатку дивимося, що виходить при використанні dict.
Виконаємо
multi
time
eval "for i=0,10000,1 do redis.call('hset', 'test', i, i) end" 0
time

і
multi
time
eval "for i=0,10000,1 do redis.call('hget', 'test', i) end" 0
time

Висновок з redis=cli
config set hash-max-ziplist-entries 1 
+OK
config set hash-max-ziplist-value 1000000
+OK
flushall
+OK
info memory 
$225
# Memory
used_memory:508536
multi
+OK
time
+QUEUED
eval "for i=0,10000,1 do redis.call('hset', 'test', i, i) end" 0
+QUEUED
time
+QUEUED
exec
*3
*2
$10
1449161639
$6
948389
$-1
*2
$10
1449161639
$6
967383
debug object test
+Value at:0x7fd9864d6470 refcount:1 encoding:hashtable serializedlength:59752 lru:6321063 lru_seconds_idle:23
info memory
$226
# Memory
used_memory:1025432
multi
+OK
time
+QUEUED
eval "for i=0,10000,1 do redis.call('hget', 'test', i) end" 0
+QUEUED
time
+QUEUED
exec
*3
*2
$10
1449161872
$6
834303
$-1
*2
$10
1449161872
$6
841819

flushall
+OK
info memory
$226
# Memory
used_memory:510152

config set hash-max-ziplist-entries 100000
+OK
multi
+OK
time
+QUEUED
eval "for i=0,10000,1 do redis.call('hset', 'test', i, i) end" 0
+QUEUED
time
+QUEUED
exec
*3
*2
$10
1449162574
$6
501852
$-1
*2
$10
1449162575
$6
212671

debug object test
+Value at:0x7fd9864d6510 refcount:1 encoding:ziplist serializedlength:59730 lru:6322040 lru_seconds_idle:19

info memory 
$226
# Memory
used_memory:592440
multi
+OK
time
+QUEUED
eval "for i=0,10000,1 do redis.call('hget', 'test', i) end" 0
+QUEUED
time
+QUEUED
exec
*3
*2
$10
1449162616
$6
269561
$-1
*2
$10
1449162616
$6
975149


У випадку з encoding:hashtable (dict) витратили ~516 кб пам'яті і 18,9 мс на збереження 10,000 значень, 7,5 мс на їх читання. З encoding:ziplist отримуємо ~81 кб пам'яті і 710 мс на збереження, 705 мс на читання. Для тесту в 10,000 записів отримали:
Виграш з пам'яті в 6 разів ціною просідання по швидкості запису в 37,5 разів і 94 рази з читання.
При цьому важливо розуміти, що падіння продуктивності не лінійне і вже для 1,000,000 ви ризикуєте просто не дочекатися підсумків. Хто стане складати в ziplist 10,000 елементів? Це, на жаль, одна з перших рекомендацій від більшості консультантів. Коли гра ще варта свічок? Я б сказав, що поки кількість елементів лежить у діапазоні 1 — 3500 елементів ви можете вибирати, пам'ятаючи, що по пам'яті у ziplist завжди виграє від 6 разів і вище. Все що більше — вимірюйте на своїх реальних даних, але до навантаженим систем реального часу це вже не буде мати ніякого відношення. Ось що відбувається з продуктивністю читання/запису в залежності від розміру хеш на dict і ziplist(gist на тест):

Чому так? Ціна вставки, зміни довжини елементів і видалення ziplist жахлива — це або realloc (вся робота лягає на плечі аллокатора) або повне перестроювання списку від n + 1 від зміненого елемент до кінця списку. Перестроювання — це дуже багато мелкофрагментных realloc, memmove, memcpy (див. __ziplistCascadeUpdate ziplist.c).

Чому в статті про HASH важливо поговорити про LIST? Справа в одному дуже важливому раді щодо оптимізації структурованих даних. Пішов він здається від DataDog, точно сказати важко. У перекладі звучить так(оригинал):
Ви зберігаєте в Redis дані своїх користувачів, наприклад `hmset user:123 id 123 firstname Іван lastname Іванов location Томськ twitter ivashka`. Тепер, якщо створити ще одного користувача, ви даремно витратите пам'ять на імена полів — id, firstname, lastname і т. д. Якщо таких користувачів багато — це багато викинута пам'яті (ми вже маємо рахувати скільки — для цього набору полів 384 байта на одного користувача).

Отже, якщо у вас
  1. У вас багато об'єктів, скажімо від 50,000 і вище.
  2. Ваші об'єкти мають регулярну структуру (по суті завжди всі поля)

Можна скористатися концепцією іменованих кортежів з пітона — лінійний список з доступом тільки на читання, навколо якого побудувати хеш таблицю «руками». Грубо кажучи «fisrtname» — це значення з індексом 0 списку, «lastname» по першому і т. д. Тоді створення користувача буде виглядати як `lpush user:123 Іван Іванов Томськ ivashka`.
І це вельми корисна порада. Очевидно, що список (LIST) допоможе вам сильно заощадити мінімум у 2 разу.
Як і в HASH — з допомогою list-max-ziplist-entries/list-max-ziplist-val ви керуєте яким внутрішнім типом даних буде представлений конкретний list ключ. Наприклад, при list-max-ziplist-entries = 100 ваш LIST буде представлений REDIS_ENCODING_ZIPLIST, поки в ньому буде менше 100 елементів. Як тільки елементів стане більше, він буде конвертований в REDIS_ENCODING_LINKEDLIST. Налаштування list-max-ziplist-val працює аналогічно hash-max-ziplist-val (див. першу частину).
C ziplist ми вже розібралися, давайте дивитися REDIS_ENCODING_LINKEDLIST. У реалізації Redis це дуже простий(~270 рядків коду) не сортований однозв'язний списоквсе як у вікіпедії). З усіма його перевагами і недоліками:
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;

typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;

Нічого складного — кожен LIST такий кодуванні це 5 покажчиків і 1 unsigned long. Так що накладні витрати 5 * size_of(pointer) + 8 байт. А кожен вузол це 3 покажчика. Оверхед на зберігання даних у такому кодуванні для n це елементів:
5 * size_of(pointer) + 8 + n * 3 * size_of(pointer)
У реалізації linkedlist немає ніяких realloc — тільки виділення пам'яті під потрібний вам фрагмент, в значеннях — redisObejct без будь-яких хитрощів і оптимізацій. За оверхеду пам'яті різниця на службові витрати між ziplist і linkedlist близько 15%. Якщо розглядати службові дані плюс значення — в рази (від 2 і вище), в залежності від типу значення. Так для списку 10,000 елементів, що складається лише з цифр у ziplist ви витратите близько 41 кб пам'яті, в linkedlist — 360 кб реальної пам'яті:
config set list-max-ziplist-entries 1
+OK
flushall
+OK
info memory
$226
# Memory
used_memory:511544
eval "for i=0,10000,1 do redis.call('lpush', 'test', i) end" 0
$-1
debug object test
+Value at:0x7fd9864d6530 refcount:1 encoding:linkedlist serializedlength:29877 lru:6387397 lru_seconds_idle:5
info memory
$226
# Memory
used_memory:832024
config set list-max-ziplist-entries 10000000
+OK
flushall
+OK
info memory
$226
# Memory
used_memory:553144
eval "for i=0,10000,1 do redis.call('lpush', 'test', i) end" 0
$-1
info memory
$226
# Memory
used_memory:594376
debug object test
+Value at:0x7fd9864d65e0 refcount:1 encoding:ziplist serializedlength:79681 lru:6387467 lru_seconds_idle:16

Давайте подивимося на різницю в продуктивності при запису та отриманні елемента через LPOP (прочитати і видалити). Чому не LRANGE — його складність позначена як O(S+N) і для обох реалізацій списку цей час константним. LPOP ж все не зовсім як написано в документації — складність позначена як Про(1). Але що станеться, якщо мені буде потрібно послідовне читання щоб вважати:

Що не так зі швидкістю читання при використанні ziplist? Кожен `LPOP` — вилучення елемента з початку списку з його повним перестроением. До речі, якщо ми використовуємо на читанні RPOP, замість LPOP — ситуація не сильно зміниться (привіт realloc'у функції оновлення списку в ziplist.c). Чому важливо? Команди RPOPLPUSH/BRPOPLPUSH популярне рішення при організації черг на базі Redis(наприклад Sidekiq, Resque). Коли в такій черзі з кодуванням ziplist надає велике значення число (від декількох тисяч) — отримання одного елемента вже не константним і систему починає трясти.

У завершенні прийшла пора сформулювати кілька висновків:
  • У вас не вийде використовувати ziplist в хеш таблиці з великою кількістю значень (від 1000), якщо вам все ще важлива продуктивність при великому обсязі запису.
  • Якщо дані у вашій хеш таблиці мають регулярну структури забувайте про хеш таблиці і переходьте до зберігання даних у списках.
  • Який би вид кодування ви не використовували — Redis ідеальний для цифр, прийнятний для рядків з довжиною до 63 байт і не однозначний при зберіганні рядків більшого розміру.
  • Якщо у вашій системі багато списків, пам'ятайте, що поки вони маленькі (до list-max-ziplist-entries) — ви витрачаєте мало пам'яті і все, в цілому, задовільно по продуктивності, але як тільки вони почнуть рости — пам'ять може різко зрости від 2 разів та вище стрибком, а сам процес зміни кодування буде займати вагоме час (нарощування з послідовною вставкою + видалення).
  • Будьте обережні з поданням списку (налаштування list-max-*), якщо використовуєте список для побудови черг або активної запису/читання з видаленням. Або інакше, якщо ви використовуєте Redis для побудови черг на базі списків — виставляйте list-max-ziplist-entries = 1 (пам'яті все одно витратите всього лише трішки більше)
  • Redis ніколи не віддає пам'ять, вже виділену системою. Враховуйте накладні витрати на службову інформацію і стратегію зміни розміру — при активній запису ви можете сильно збільшувати фрагментацію пам'яті з-за цієї особливості і витрачати до 2-х разів більше оперативної пам'яті, ніж розраховуєте. Це особливо важливо, коли ви запускаєте N примірників Redis на одному фізичним сервері.
  • Якщо вам важливо зберігати різнорідні за обсягом і швидкості доступу дані на одному Redis — подумайте над тим, щоб трохи дописати код Redis і перейти на налаштування list-max-* параметрів на кожен ключ, замість сервера.
  • Кодування одного й того ж типу даних на master/slave можуть різнитися, що дозволяє гнучкіше підходити до вимог — наприклад, швидко і з великою витратою пам'яті на читання, повільніше і економніше по пам'яті на слейве або навпаки.
  • Накладні витрати при використанні ziplist мінімальні, зберігати рядки дешевше в ziplist ніж в будь-якій іншій структурі (оверхед zlentry всього 21 байт на рядок, в той час як традиційне уявлення redisObject + sds рядок — 56 байт).
Зміст:
Матеріали, використані при написанні статті:


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.