Тема Redis — базовая структура данных

Базовая структура данных Redis

Простые динамические строки (SDS)

Преимущества перед струнами C:

• Постоянная сложность получает длину строки.
• Избегайте переполнения буфера. Строки C не записывают свою длину, что может легко привести к переполнению буфера.SDSПри изменении API автоматическиSDSпространство для расширения до размера, необходимого для выполнения модификации, прежде чем фактическая модификация будет выполнена.
• Уменьшите количество весов памяти, которые принесли, изменив строки.SDSИспользование пространства PrealLocation (增长操作) и отложенный выпуск (缩短操作)
• Бинарный сейф. Строки C могут содержать только текстовые данные, а не двоичные данные, такие как изображения, аудио, видео и сжатые файлы.SDSДвоичные данные можно сохранять в любом формате.
• Совместим с некоторыми строковыми функциями C, что позволяет избежать ненужного дублирования кода.

связанный список

Связанные списки широко используются для реализации различных функций Redis, таких как списки, публикация и подписка, медленные запросы, мониторы и т. д.

listNodeструктура:

Несколько узлов списка могут формировать двусторонний связанный список с помощью указателей prev и next.

listструктура:

Структура списка предоставляет головной указатель, хвостовой указатель и счетчик длины списка len для связанного списка, в то время как элементы dup, free и match являются специфическими для типа функциями, необходимыми для реализации полиморфных связанных списков:

• Функция дублирования используется для копирования значения, хранящегося в узле связанного списка;
• Функция free используется для освобождения значения, хранящегося в узле связанного списка;
• Функция match используется для сравнения, равно ли значение, сохраненное узлом связанного списка, другому входному значению.

Связанный список, состоящий из структуры списка и трех структур listNode:

Передний узел головного узла связанного списка и задний узел хвостового узла указывают на NULL, поэтому реализация связанного списка Redis представляет собой ациклический связанный список.

Словарь

Словарь Redis использует хэш-таблицу в качестве базовой реализации.Структура хеш-таблицы выглядит следующим образом:

Пустая хеш-таблица размера 4 (без пар ключ-значение).

Узлы хэш-таблицы представлены структурами dictEntry, каждая из которых содержит пару ключ-значение:

Атрибут key содержит ключ в паре ключ-значение, а атрибут v содержит значение в паре ключ-значение, где значением пары ключ-значение может быть указатель, целое число uint64_t или целое число int64_t.

Структура словаря в Redis:

• typeсвойство является указателем наdictTypeуказатели на структуры, каждыйdictTypeСтруктура содержит набор функций для управления парами ключ-значение определенного типа, а Redis устанавливает разные функции для разных типов словарей с разными целями.
• privdataСвойства содержат необязательные аргументы, которые необходимо передать этим функциям, зависящим от типа.

прогрессивная перефразировка

Чтобы избежать влияния повторного хэширования на производительность сервера, сервер не выполняет повторное хэширование всех пар ключ-значение в новой хеш-таблице за один раз, а выполняет повторное хэширование в несколько последовательных шагов.

Ниже приведены подробные шаги прогрессивного перефразирования хеш-таблицы:

1. Выделите место для ht[1] и позвольте словарю содержать две хеш-таблицы ht[0] и ht[1] одновременно.
2. Сохраните в словаре переменную индексного счетчика rehashidx и установите для нее значение 0, что указывает на официальное начало работы по перехэшированию.
3. Во время перехеширования каждый раз, когда словарь добавляется, удаляется, ищется или обновляется, программа не только выполняет указанную операцию, но и перехеширует все пары ключ-значение в индексе rehashidx хэш-таблицы ht[0] к rehash.ht[1], после завершения перефразирования программа увеличивает значение атрибута rehashidx на единицу.
4. При непрерывном выполнении операций со словарем, наконец, в определенный момент времени все пары ключ-значение ht[0] будут перехэшированы в ht[1], В это время программа устанавливает значение атрибута rehashidx в - 1, что указывает на завершение операции перефразирования.

Во время прогрессивного повторного хеширования такие операции, как удаление, поиск, обновление и т. д. словаря, выполняются в двух хеш-таблицах. Новые пары ключ-значение, добавленные в словарь, всегда будут храниться в ht[1].

стол для прыжков

Таблица прыжков (skiplist) — это упорядоченная структура данных, которая обеспечивает быстрый доступ к узлам за счет поддержки нескольких указателей на другие узлы в каждом узле. Redis использует таблицы пропуска как одну из базовых реализаций отсортированных наборов ключей.

zskiplistNodeСтруктура выглядит следующим образом:

• уровень: каждый уровень узла помечен словами L1, L2, L3 и т. д. в узле, L1 представляет первый уровень, L2 представляет второй уровень и т. д. Каждый слой имеет два свойства: прямой указатель и диапазон. Прямой указатель используется для доступа к другим узлам в направлении конца списка, а диапазон записывает расстояние между узлом, на который указывает прямой указатель, и текущим узлом. На рисунке ниже стрелка с числом в строке представляет собой указатель вперед, а это число — диапазон. Когда программа переходит от головы к хвосту, доступ будет следовать прямому указателю слоя.
• обратный указатель: обратный указатель узла, помеченного BW в узле, который указывает на предыдущий узел, расположенный в текущем узле. Задний указатель используется, когда программа перемещается от конца таблицы к началу таблицы.
• оценка: 1,0, 2,0 и 3,0 в каждом узле - это оценки, сохраненные узлом. В таблице переходов узлы располагаются от меньшего к большему в соответствии с их сохраненными очками.
• obj: o1, o2 и o3 в каждом узле — это объекты-члены, сохраненные узлом.

zskiplistСтруктура выглядит следующим образом:

• заголовок: указывает на узел заголовка таблицы переходов.
• хвост: указывает на хвостовой узел таблицы пропуска.
• уровень: запишите уровень узла с наибольшим уровнем в текущей таблице переходов (уровень узла заголовка не учитывается).
• длина: запишите длину таблицы переходов, то есть количество узлов, содержащихся в настоящее время в таблице переходов (узел заголовка не учитывается).

skiplist со структурой zskiplist

коллекция целых чисел

набор целых чисел (intset) является одной из базовых реализаций ключей коллекций.Если коллекция содержит только целочисленные элементы и количество элементов в этой коллекции невелико, Redis будет использовать целочисленную коллекцию в качестве базовой реализации ключей коллекций. Структура целочисленного множества выглядит следующим образом:

Обновить

Всякий раз, когда мы хотим добавить новый элемент в набор целых чисел, и тип нового элемента длиннее, чем типы всех существующих элементов набора целых чисел, набор целых чисел должен быть обновлен, прежде чем новый элемент может быть добавляется в коллекцию внутри набора целых чисел. Операция обновления обеспечивает операционную гибкость целочисленных коллекций и максимально экономит память. Операции понижения версии не поддерживаются.

Обновление коллекции целых чисел и добавление новых элементов — это трехэтапный процесс:

1. Увеличивает размер базового массива целочисленной коллекции и выделяет место для нового элемента в зависимости от типа нового элемента.
2. Преобразуйте все существующие элементы базового массива в тот же тип, что и новые элементы, и поместите преобразованные элементы в правильные позиции, а в процессе размещения элементов необходимо продолжать поддерживать упорядоченный характер базового массива. Изменять.
3. Добавляет новые элементы в базовый массив.

Сжатый список

Сжатый список (ziplist) — одна из низкоуровневых реализаций списков и хэшей. Когда список содержит только несколько элементов списка, и каждый элемент списка представляет собой либо небольшое целочисленное значение, либо строку относительно короткой длины, тогда Redis будет использовать сжатый список в качестве базовой реализации списка. Сжатый список разработан Redis для экономии памяти и представляет собой последовательную структуру данных, состоящую из ряда специально закодированных смежных блоков памяти. Компоненты компрессионного стола:

• zlbytes: запишите количество байтов памяти, занимаемых всем сжатым списком. Используется при перераспределении сжатого списка или вычислении позиции zlend.
• zltails: Запишите, сколько байтов от конца сжатого списка до начального адреса сжатого списка. С этим смещением программа может определить адрес конца списка, не просматривая весь сжатый список.
• ZLLEN: записывает количество узлов, содержащихся в сжатом списке.
• entryX: узлы, содержащиеся в сжатом списке.
• zlend: используется для обозначения конца сжатого списка.

На следующем рисунке показан пример сжатого списка:

Узлы сжатого списка:由previous_entry_length,encoding,contentСостоит из трех частей.

• previous_entry_length: записывает длину предыдущего узла в сжатом списке. Программа может вычислить начальный адрес предыдущего узла, вычитая из указателя значение previous_entry_length текущего узла.
• кодировка: записывает тип и длину данных, хранящихся в атрибуте содержимого узла.
• content: содержит значение узла. Значение узла может быть массивом байтов или целым числом.Тип и длина значения определяются свойством кодирования узла.

обновление цепочки

В сжатом списке есть несколько последовательных узлов от e1 до eN с длиной от 250 до 253 байтов, а атрибут previous_entry_length всех узлов от e1 до eN имеет длину 1 байт (поскольку все узлы имеют длину менее 254 байт). В это время, если мы установим новый узел new с длиной, большей или равной 254 байтам, в качестве узла заголовка сжатого списка, тогда новый станет передним узлом e1, а предыдущая_entry_length e1, e2 и e3 все требуют сопряжения программ. Сжатые списки выполняют перераспределение пространства, увеличивая свою длину. Redis называет эту непрерывную операцию расширения нескольких пространств в особых случаях «обновлением цепочки».

Добавление новых узлов в список уплотнения или удаление узлов из списка уплотнения может инициировать операцию обновления цепочки, но вероятность такой операции невелика.

быстрый список

quicklistКаждый узел вquicklistNodeобъект, структура данных которого определяется как:

typedef struct quicklistNode {
    struct quicklistNode *prev;//前一个节点
    struct quicklistNode *next;//后一个节点
    unsigned char *zl;//当前指向的ziplist或者quicklistLZF
    unsigned int sz;//当前ziplist占用字节
    unsigned int count : 16;//ziplist中存储的元素个数，16字节(最大65535个)
    unsigned int encoding : 2; //是否采用了LZF压缩算法压缩节点 1：RAW 2:LZF
    unsigned int container : 2; //存储结构，NONE=1, ZIPLIST=2
    unsigned int recompress : 1; //当前ziplist是否需要再次压缩(如果前面被解压过则为true，表示需要再次被压缩)
    unsigned int attempted_compress : 1;//测试用 
    unsigned int extra : 10; //后期留用
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head;//列表头节点
    quicklistNode *tail;//列表尾节点
    unsigned long count;//ziplist中一共存储了多少元素，即:每一个quicklistNode内的count相加
    unsigned long len; //双向链表的长度，即quicklistNode的数量
    int fill : 16;//填充因子
    unsigned int compress : 16;//压缩深度 0-不压缩
} quicklist;

По этим двум структурам мы можем получить упрощенную схему объекта списка после Redis3.2:

объект

Redis создает объектную систему на основе базовой структуры данных. Эта система включает пять типов объектов: объекты-строки, объекты-списки, хеш-объекты, объекты-коллекции и объекты упорядоченной коллекции. Каждый объект использует по крайней мере одну из наших предыдущих представленных структур данных. . Объектная система Redis также реализует механизм рециркуляции памяти и механизм совместного использования объектов, основанный на технологии подсчета ссылок.

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

Тип объекта и кодировка

Redis использует объекты для представления ключей и значений в базе данных, каждый раз, когда мы создаем новую пару ключ-значение в базе данных Redis, мы будем создавать как минимум два объекта, один объект используется в качестве ключа ключ-значение пара (ключевой объект) , другой объект для использования в качестве значения пары ключ-значение (объект значения). Ключ всегда представляет собой строковый объект, а значение может быть одним из строкового объекта (строка), объекта-списка (список), хэш-объекта (хэш), объекта-набора (набор) или отсортированного объекта-набора (zset). ). Структура объекта (redisObject) в Redis представлена ​​следующим образом:

• Тип: содержит строковые объекты, списковые объекты, хэш-объекты, объекты-коллекции и упорядоченные объекты-коллекции. быть пригодным для использованияTYPE keyкоманда для просмотра типа объекта значения.
• Кодировка: записывает кодировку, используемую объектом. быть пригодным для использованияOBJECT ENCODING keyПросмотрите кодировку объекта значения.
• Указатель ptr: указывает на базовую структуру данных реализации объекта.

На рисунке ниже показаны кодировки, которые можно использовать для каждого типа объекта.

использоватьOBJECT ENCODING keyКоманда кодирования для просмотра значения ключа базы данных объекта

Установка кодировки, используемой объектом, через атрибут encoding значительно повышает гибкость и эффективность Redis, поскольку Redis может устанавливать разные кодировки для объекта в соответствии с разными сценариями использования, тем самым оптимизируя эффективность объекта в определенном сценарии.

Когда объект списка содержит меньше элементов, Redis использует сжатый список в качестве базовой реализации объекта списка: поскольку сжатый список более эффективно использует память, чем двусторонний связанный список, а когда количество элементов невелико, сжатый список список сохраняется в непрерывных блоках памяти. Может загружаться в кэш быстрее, чем двусвязный список. По мере того, как объект списка содержит все больше и больше элементов, а преимущества использования сжатого списка для хранения элементов исчезают, объект сместит базовую реализацию со сжатого списка на более мощный двусторонний список, более подходящий для хранения большое количество элементов.

строковый объект

Кодировка строкового объекта может бытьint,rawилиembstr.

• Если строковый объект содержит целочисленное значение, и целочисленное значение может быть представлено типом long, то строковый объект сохранит целочисленное значение в атрибуте ptr структуры строкового объекта (преобразует void* в long) и установит кодирование строкового объекта в int.
• Если строковый объект содержит строковое значение, а длина строкового значения превышает 32 байта, то строковый объект будет использовать простую динамическую строку (SDS) для сохранения строкового значения, а кодировка объекта будет задана. к сырому.
• Если строковый объект сохраняет строковое значение, а длина строкового значения меньше или равна 32 байтам, то строковый объект будет использовать кодировку embstr для сохранения строкового значения.

embstrКодирование — это оптимизированный метод кодирования, специально используемый для сохранения коротких строк. Непрерывное пространство выделяется путем однократного вызова функции выделения памяти. Пространство содержит две структуры, redisObject и sdshdr по очереди.rawКодировка дважды вызовет функцию выделения памяти, чтобы создать их отдельно. освобожденembstrСтрока кодировки также требует только одного вызова.

Кодировки, используемые строковыми объектами для хранения различных типов значений, показаны на рисунке:

преобразование кодирования

• Строковые объекты с кодировкой Int и строковые объекты с кодировкой embstr будут преобразованы в строковые объекты с необработанным кодированием при выполнении условий.
• Redis не записывает никаких соответствующих модификаторов для строковых объектов в кодировке embstr, поэтому строковые объекты в кодировке embstr фактически доступны только для чтения.
• При изменении строкового объекта, закодированного с помощью embstr, кодировка объекта будет преобразована из embstr в необработанную, а затем будет выполнена команда модификации.
• После изменения строкового объекта, закодированного в embstr, он всегда становится необработанным строковым объектом, закодированным.

Реализация строковых команд

На следующем рисунке перечислены методы реализации некоторых строковых команд при различных кодировках строковых объектов.

список объектов

До Redis 3.2 кодирование объектов списка могло бытьziplistилиlinkedlist. После Redis3.2 унифицированное использованиеquicklistдля хранения объектов списка. воплощать в жизньRPUSHкоманда, сервер создаст объект списка в качестве значения ключа чисел, как показано нижеziplist,linkedlistструктура данных.

quicklist хранит двусторонний список, а узел каждого списка — это ziplist, поэтому на самом деле quicklist — это комбинация связанного списка и ziplist.

• Объект кодирования ziplist показан на рисунке:

• Объект кодированного списка связанного списка показан на рисунке:

Приведенная выше диаграмма упрощает представление строковых объектов.

преобразование кода

Объекты списка используют кодировку ziplist, когда они могут удовлетворять обоим из следующих условий:

• Длина всех строковых элементов, хранящихся в объекте списка, меньше 64 байт;
• Количество элементов, хранящихся в объекте списка, меньше 512; объект списка, который не соответствует этим двум условиям, должен использовать кодировку связанного списка.

доступныйlist-max-ziplist-valueварианты иlist-max-ziplist-entriesвозможность изменить верхний предел двух вышеуказанных условий

хэш-объект

Кодирование хеш-объекта может бытьziplistилиhashtable.

• ziplistЗакодированный хеш-объект использует сжатый список в качестве базовой реализации, а новые ключи и значения помещаются в конец сжатого списка как два соседних узла сжатого списка. Например, если мы выполним следующую команду:

redis> HSET profile name tom
redis> HSET profile age 25
redis> HSET profile career Programmer

Сжатый список, используемый объектом, показан на рисунке

• hashtableЗакодированный хэш-объект использует словарь в качестве базовой реализации, и каждая пара ключ-значение в хеш-объекте хранится с использованием пары ключ-значение словаря. Или возьмем для примера приведенную выше команду, ее структура показана на рисунке:

преобразование кода

Когда хеш-объект может одновременно удовлетворять следующим двум условиям, хеш-объект используетziplistкодировка, в противном случае используйтеhashtableкодирование.

• Длина строки всех пар ключ-значение, хранящихся в хеш-объекте, меньше 64 байтов;
• Количество пар ключ-значение, хранящихся в хэш-объекте, меньше 512.

доступныйhash-max-ziplist-valueварианты иhash-max-ziplist-entriesвозможность изменить верхний предел двух вышеуказанных условий

объект коллекции

Кодирование объекта коллекции может бытьintsetилиhashtable.

• Все элементы, содержащиеся в объекте коллекции с кодировкой intset, хранятся в целочисленной коллекции;
• Объект коллекции, закодированный с помощью хеш-таблицы, использует словарь в качестве базовой реализации.Каждый ключ словаря представляет собой строковый объект, каждый строковый объект содержит элемент коллекции, и все значения словаря установлены в NULL.

На следующем рисунке показана структура объекта коллекции с кодировкой intset и объекта коллекции с кодировкой хеш-таблицы:

преобразование кодирования

Когда объект коллекции может одновременно соответствовать следующим двум условиям, объект использует кодировку intset, в противном случае он использует кодировку хеш-таблицы:

• Все элементы, содержащиеся в объекте коллекции, являются целыми значениями;
• Объекты коллекции содержат не более 512 элементов.

доступныйset-max-intset-entriesВозможность изменить верхнее предельное значение вышеуказанного условия

упорядоченный объект коллекции

Кодирование отсортированного набора может бытьziplistилиskiplist.

• упорядоченная коллекция, закодированная в ziplist, с использованием сжатого списка в качестве базовой реализации, каждый элемент коллекции хранится с использованием двух узлов сжатого списка рядом друг с другом, первый узел содержит элемент элемента, а второй элемент хранит оценку элемента. Элементы коллекции отсортированы от мала до велика.
• Объект упорядоченного набора, закодированный с помощью skiplist, использует структуру zset в качестве базовой реализации, а структура zset также содержит словарь (dict) и таблицу пропуска (zsl). Обе структуры данных совместно используют члены и оценки одних и тех же элементов через указатели, не тратя впустую дополнительную память.

• zsl跳跃表Все элементы набора сохраняются от малого к большему: атрибут объекта узла таблицы переходов сохраняет элементы элемента, а атрибут оценки сохраняет оценку элемента, так что программа может выполнять операции с диапазоном над упорядоченным набором, такие как в видеZRANK,ZRANGEи так далее.
• dict字典Создает сопоставление членов с оценками для отсортированных наборов: ключи словаря содержат элементы элемента, а значения содержат оценку элемента. С помощью этого словаря программа может использовать сложность O(1) для нахождения оценки данного члена, напримерZSCOREЗаказ.

преобразование кодирования

Когда объект упорядоченного набора может одновременно удовлетворять следующим двум условиям, объект использует кодировку ziplist, в противном случае он использует кодировку Skiplist:

• Количество элементов, хранящихся в отсортированном наборе, меньше 128;
• Отсортированный набор содержит все члены элемента, длина которых меньше 64 байт.

доступныйzset-max-ziplist-entriesиzset-max-ziplist-valueвозможность изменить верхний предел двух вышеуказанных условий

Проверка типов и полиморфизм команд

Команды, используемые для управления ключами в Redis, в основном можно разделить на два типа:

• может выполняться на любом типе ключа (命令多态), такие как DEL, EXPIRE, RENAME, TYPE, OBJECT и т. д. Redis выберет правильную команду на основе кодировки, используемой объектом значения ключа.
• Может выполняться только для определенных типов ключей, таких как SET, GET, RPUSH, LPOP, ZADD, ZCARD и т. д. Redis проверяет, является ли объект значения ключа типом, необходимым для выполнения команды, через атрибут type структуры redisObject, если он не совпадает, он не будет выполнен. (类型检查)

Освобождение памяти и совместное использование объектов

• Redis реализует механизм перезапуска памяти путем создания технологии подсчета ссылок в объектной системе. Информация о счетчике ссылок для каждого объекта задаетсяredisObjectструктурныйrefcountзапись собственности
• При инициализации сервера Redis создаст строковый объект от 0 до 9999. Когда серверу потребуется использовать строковый объект со значением от 0 до 9999, сервер будет использовать эти общие объекты вместо вновь созданных объектов.

Количество созданных общих строковых объектов можно изменить, изменив redis.h/REDIS_SHARED_INTEGERS.

Почему Redis не делится объектами, содержащими строки?

Чем сложнее значения, которые содержит общий объект, тем сложнее будет проверить, что общий объект и целевой объект совпадают, и тем больше процессорного времени он будет потреблять.

• Если общий объект является строковым объектом, содержащим строковое значение, то сложность операции проверки равна O(N);
• Если общий объект представляет собой объект, содержащий несколько значений (или объектов), например объект-список или хеш-объект, то сложность операции проверки будет O(N²).

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

Почему счетчик ссылок Redis не отображает циклические ссылки?

Между объектами redis нет глубокой вложенности, в лучшем случае есть указатель на базовую структуру данных реализации, а redis разделяет только числовые строковые объекты от 0 до 9999. Для других объектов указатель ptr не будет искать, имеют ли они то же самое и затем укажите, чтобы не было циклической ссылки.

Время простоя объекта

redisObjectПомимо упомянутого ранееtype,encoding,ptrиrefcountВ дополнение к четырем атрибутам последний атрибутlruАтрибут.При использовании для LRU указывает время последнего доступа.При использовании для LFU старшие 16 бит записывают время доступа на уровне минут, а младшие 8 бит записывают частоту доступа от 0 до 255.

когда сервер включенmaxmemoryвариант, а алгоритм, используемый сервером для освобождения памяти,volatile-lruилиallkeys-lruКогда количество памяти, занимаемой сервером, превышает верхний предел, установленный maxmemory, часть ключей с более длительным временем простоя будет освобождена сервером в первую очередь, тем самым высвобождая память.

Bitmap, Stream, Geo, HyperLogLog будут обновлены

Ссылаться на

• «Проектирование и реализация Redis» (Хуан Цзяньхун)
• blog.CSDN.net/Zhuo Wenxuan900102/Ах…