Тема Redis (2): изучение нижнего уровня структуры данных Redis

предисловие

Предыдущая статьяЧат Redis (1): построение графа знанийПредставлены основные понятия, преимущества и недостатки redis и его механизм устранения памяти.Я думаю, что у всех есть предварительное представление о redis. Redis используется во многих сценариях приложений в Интернете, и он может делать вещи, выходящие за рамки нашего воображения. На что похожа базовая структура данных Redis и почему она может делать так много вещей? В этой статье мы рассмотрим базовую структуру данных Redis и часто используемые команды.

Карта мозга знаний в этой статье выглядит следующим образом:

1. Модель данных Redis

с парами ключ-значениеname："小明"Чтобы показать модель данных Redis, выполните следующие действия:

• dictEntry:В некоторых языках программирования структура данных пары «ключ-значение» называется словарем, а в Redis каждому значению ключа «ключ-значение» присваивается объект словаря, которым является «Dicentry». Дицентрий состоит из трех частей:указатель на ключ, указатель на значение, указатель на следующий, следующий указатель указывает на следующий dicteEntry для формирования связанного списка.Этот следующий указатель может связать вместе несколько пар ключ-значение с одним и тем же хеш-значением.Решите проблему коллизии хэшей с помощью метода цепных адресов.
• sds:Simple Dynamic String, простая динамическая строка, в которой хранятся строковые данные.
• redisObject: Redis Пять типов обычно используются для хранения в RedisObject, RedisObject вtypeПоле указывает тип данных значения (то есть 5 основных типов).ptrПоле указывает на адрес, по которому находится объект.

Объекты RedisObject важны, Redisтип объекта,Внутреннее кодирование,восстановление памяти,общий объекти другие функции реализованы на основе объекта RedisObject.

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

Redis использует jemalloc в качестве распределителя памяти по умолчанию, чтобы уменьшить фрагментацию памяти. В 64-битной системе jemalloc делит пространство памяти на три диапазона: малый, большой и огромный; каждый диапазон делится на множество небольших блоков памяти; когда Redis сохраняет данные, он выбирает блок памяти наиболее подходящего размера для хранения.

Во-вторых, структура данных, поддерживаемая Redis.

Какие структуры данных поддерживает Redis?

Если ответ String, List, Hash, Set и Zset, это неправильно.Эти пять являются общими базовыми типами данных Redis, и каждый тип данных также содержит различные структуры данных.

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

127.0.0.1:6379> set name tom
OK
127.0.0.1:6379> object encoding name
"embstr"

Значение имени здесь установлено как tom, а его структура данных — embstr, что будет подробно объяснено при вводе строк ниже.

127.0.0.1:6379> set age 18
OK
127.0.0.1:6379> object encoding age
"int"

В следующей таблице приведены все типы структур данных в Redis:

базовая структура данных	Кодирование константы	Вывод инструкции кодирования объекта
Целочисленный тип	REDIS_ENCODING_INT	"int"
тип строки embstr	REDIS_ENCODING_EMBSTR	"embstr"
простая динамическая строка	REDIS_ENCODING_RAW	"raw"
Тип словаря	REDIS_ENCODING_HT	"hashtable"
Двусторонний связанный список	REDIS_ENCODING_LINKEDLIST	"linkedlist"
Сжатый список	REDIS_ENCODING_ZIPLIST	"ziplist"
Целые числа	REDIS_ENCODING_INTSET	"intset"
Пропустить таблицы и словари	REDIS_ENCODING_SKIPLIST	"skiplist"

Дополнительные инструкции

Если интервьюер спросит: какие типы данных есть у Redis?

Ответ: Строка, список, хэш, набор, зет

В общем, этот ответ правильный.Как упоминалось выше, типы данных Redis включают эти 5 типов, но внимательные студенты должны были обнаружить, что 5 типов данных, упомянутых ранее, являются **«обычно используемыми»**. На самом деле, благодаря постоянному обновлению и улучшению Redis, в Redis существует более 5 типов данных.

Войдите на официальный сайт Redis, чтобы открыть официальный тип данных Введение:

Redis.IO/темы/данные...

Выяснилось, что Redis поддерживает не 5, а 8 структур данных, последние три типа:

• Битовые массивы (или растровые изображения для краткости): строковыми значениями можно манипулировать с помощью специальных команд, таких как битовые массивы: вы можете устанавливать и очищать отдельные биты, устанавливать все биты в 1, находить первый или неустановленный бит и так далее.
• HyperLogLogs: это вероятностная структура данных, используемая для оценки кардинальности коллекции. Не бойтесь, это проще, чем кажется.
• Потоки: коллекция картоподобных записей только для добавления, которые предоставляют абстрактный тип данных журнала.

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

2.1 струнная строка

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

Строки в Redis называются простыми динамическими строками «SDS», которые структурированы так же, как ArrayLists в Java, а их длина динамически изменяется.

struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组长度
  byte[] content; // 数组内容
}

content[]Сохраняет содержимое строки,capacityпредставляет длину выделения массива,lenУказывает фактическую длину строки.

Типы кодирования строк — int, embstr и raw, как показано в таблице выше, так в чем же разница между этими тремя типами кодирования?

• кодировка int: Save — это целочисленное значение, которое может быть представлено типом LONG.

• необработанное кодирование: Сохраняет строки длиннее 44 байт (39 байт до redis 3.2, 44 байта после).

• кодировка embstr: Сохраняет строки длиной менее 44 байт (39 байт до redis 3.2, 44 байта после).

Установите значение, чтобы проверить это:

127.0.0.1:6379> set num 300
127.0.0.1:6379> object encoding num
"int"
127.0.0.1:6379> set key1 wealwaysbyhappyhahaha
OK
127.0.0.1:6379> object encoding key1
"embstr"
127.0.0.1:6379> set key2 hahahahahahahaahahahahahahahahahahahaha
OK
127.0.0.1:6379> strlen key2
(integer) 39
127.0.0.1:6379> object encoding key2
"embstr"
127.0.0.1:6379> set key2 hahahahahahahaahahahahahahahahahahahahahahaha
OK
127.0.0.1:6379> object encoding key2
"raw"
127.0.0.1:6379> strlen key2
(integer) 45

Сравнение необработанного типа и типа embstr

Структура кодировки embstr:

Необработанная закодированная структура:

И embstr, и raw состоят из redisObject и sds. Разница в том, что redisObject и sds в embstr непрерывны, просто используйтеmallocВыделить память один раз, тогда как для raw нужно выделять память для redisObject и sds отдельно, то есть выделять память дважды.

Для сравнения, embstr за один раз выделяет меньше памяти, что более удобно. Но есть у embstr и очевидные минусы: для увеличения длины и redisObject, и sds нужно перераспределять память.

Разница в структуре между embstr и raw была представлена ​​выше. А вот и точка~Почему вы выбрали 44 в качестве разделительной точки между двумя кодировками? Почему 39 до версии 3.2? Как получаются эти два значения?

1) Рассчитать размер байтов, занятых RedisObject

struct RedisObject {
    int4 type; // 4bits
    int4 encoding; // 4bits
    int24 lru; // 24bits
    int32 refcount; // 4bytes = 32bits
    void *ptr; // 8bytes，64-bit system
}

• тип: разные объекты Redis будут иметь разные типы данных (строка, список, хеш и т. д.), тип записи, который будет использоваться4bits.
• кодировка: сохранить форму кодировки, использовать4bits.
• лру: использовать24bitsЗапишите информацию LRU объекта.
• refcount: счетчик ссылок, используемый32bits.
• *ptr: указатель указывает на конкретное содержимое объекта, которое требуется64bits.

Расчет: 4 + 4 + 24 + 32 + 64 = 128 бит =16bytes

Первый шаг выполнен, информация заголовка объекта RedisObject будет занимать16 байтразмер, который обычно является фиксированным.

2) Рассчитать размер байтов, занятых sds

старая версия:

struct SDS {
    unsigned int capacity; // 4byte
    unsigned int len; // 4byte
    byte[] content; // 内联数组，长度为 capacity
}

здесьunsigned int4 байта, что в сумме дает 8 байт.

Если память, выделенная распределителем памяти jemalloc, превышает 64 байта, она считается большой строкой и используется необработанное кодирование.

Строка содержимого в структуре SDS представляет собой строку, заканчивающуюся с байтом \ 0, что является более такими байтами, что является для облегчения прямого использования функций обработки струн Glibc и для легких строк. Отладка распечатки. Поэтому мы должны потерять 1 байт64byte - 16byte - 8byte - 1byte = 39byte

новая версия:

struct SDS {
    int8 capacity; // 1byte
    int8 len; // 1byte
    int8 flags; // 1byte
    byte[] content; // 内联数组，长度为 capacity
}

Здесь unsigned int становится uint8_t, uint16_t, кроме того, добавляется символьный флаг, и всего используется только 3 байта. Это эквивалентно оптимизации использования памяти sds, и соответствующая память для хранения строк станет больше.

Затем выполните расчет:

64byte - 16byte -3byte -1byte = 44byte.

Суммировать:

Таким образом, после версии redis 3.2 максимальная длина строки, которую может содержать embstr, составляет 44, а раньше — 39. Причина изменения длины — оптимизация памяти в SDS.

2.2 List

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

Итак, как реализован нижний слой быстрого списка? Почему можно достичь такой высокой производительности?

Рим не за один день строился, а quicklist не за один день реализовывался.Поначалу нижним слоем redis-листа был ziplist (сжатый список) или linkedlist (двусторонний список). Во-первых, две структуры данных вводятся отдельно.

zip-список zip-список

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

контрольная работа:

127.0.0.1:6379> rpush dotahero sf qop doom
(integer) 3
127.0.0.1:6379> object encoding dotahero
"ziplist"

Здесь для тестирования используется старая версия redis, а в список героев доты добавлены три героя, qop Queen of Pain, SF Shadow Demon и Doom Doom Messenger.Кодирование структуры данных использует ziplist.

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

struct ziplist<T> {
    int32 zlbytes; // 整个压缩列表占用字节数
    int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength; // 元素个数
    T[] entries; // 元素内容列表，挨个挨个紧凑存储
    int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

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

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

Из рисунка видно, что двусторонний связанный список Redis имеет следующие характеристики: узел имеет указатель на предыдущий, следующий, указатель на начало и указатель на хвост, получает передний узел, задний узел, головной узел и хвост. node и получает длину. Сложность O (1).

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

В глазах разработчиков Redis выбор структуры данных должна быть крайней с точки зрения времени и пространства. Следовательно, они объединили сжатый список и двойной список в один и созданныйбыстрый. Подобно hashmap в java, он сочетает в себе преимущества массивов и связанных списков.

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

• rpush: listAddNodeHead ---O(1)
• lpush: listAddNodeTail ---O(1)
• push:listInsertNode ---O(1)
• index : listIndex ---O(N)
• pop:ListFirst/listLast ---O(1)
• llen:listLength ---O(N)

struct ziplist {
    ...
}
struct ziplist_compressed {
    int32 size;
    byte[] compressed_data;
}
struct quicklistNode {
    quicklistNode* prev;
    quicklistNode* next;
    ziplist* zl; // 指向压缩列表
    int32 size; // ziplist 的字节总数
    int16 count; // ziplist 中的元素数量
    int2 encoding; // 存储形式 2bit，原生字节数组还是 LZF 压缩存储
    ...
}
struct quicklist {
    quicklistNode* head;
    quicklistNode* tail;
    long count; // 元素总数
    int nodes; // ziplist 节点的个数
    int compressDepth; // LZF 算法压缩深度
    ...
}

Глубина сжатия по умолчанию для быстрого списка равна 0, что означает отсутствие сжатия. Фактическая глубина сжатия определяется параметром конфигурации list-compress-depth. Для поддержки быстрых операций push/pop первый и последний два zip-списка быстрого списка не сжимаются, и в настоящее время глубина равна 1. Если глубина равна 2, это означает, что первый зип-лист в начале и в конце списка быстрого доступа и второй зип-лист в начале и в конце не сжаты.

2.3 Hash

Базовой реализацией типа данных Hash является ziplist (сжатый список) или словарь (также известный как хеш-таблица или хеш-таблица). Выбор сжатого списка или словаря здесь также определяется количеством элементов.

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

Когда мы добавляем данные со значением более 64 байт, структура данных по умолчанию становится хеш-таблицей.

Хэш-объекты будут использовать ziplist (сжатый список) только в том случае, если они удовлетворяют обоим из следующих условий:

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

Список сжатия только что понял, хеш-таблицы аналогичны хэш-карте до jdk1.7. Hashmap использует метод цепных адресов для решения проблемы коллизии хешей. Если вы хотите узнать больше, вы можете обратиться к предыдущему сообщению в блоге:Вы действительно понимаете хэшмап?

Redis в словаре

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

2.4 Set

Базовый тип данных набора может бытьintset(набор целых чисел) илиhashtable(Хеш-таблица также называется хеш-таблицей).

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

127.0.0.1:6379> sadd myset 111 222 333
(integer) 3
127.0.0.1:6379> object encoding myset
"intset"
127.0.0.1:6379> sadd myset hahaha
(integer) 1
127.0.0.1:6379> object encoding myset
"hashtable"

Структура данных вставки:

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

Базовая реализация intset представляет собой упорядоченный неповторяющийся массив. Целочисленный тип intset может быть 16-битным, 32-битным или 64-битным. Если все целые числа в массиве имеют длину 16 бит и добавляется 32-битное целое число, весь 16-битный массив будет обновлен до 32-битного массива. Обновление может улучшить гибкость intset и сэкономить память, но это необратимо.

2.5 Zset

Zset в Redis, также называемыйотсортированный набор. Его нижний слой представляет собой ziplist (сжатый список) илиskiplist(стол для прыжков).

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

Столик прыжков

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

Почему таблица пропуска имеет такую ​​высокую производительность? Как именно "прыгает"? В таблице пропуска используется идея дихотомии, которую можно использовать для быстрого поиска в массиве, а также ее можно использовать в связанном списке.

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

Предположим, чтобы найти узел 10, вам нужно пройти один за другим, чтобы определить, является ли это узлом, который вы ищете. Итак, как повысить эффективность? Я думаю, что все знакомы с индексом mysql, который может повысить эффективность, здесь также можно использовать индекс. Извлеките индексный слой, чтобы:

Так что просто нужно найти 10 9, а затем найти его, экономя время поиска.

Вы также можете извлечь еще один слой индекса, который лучше сэкономит время:

Таким образом, «двоичный поиск», основанный на связном списке, поддерживает быструю вставку и удаление, а временная сложность составляет O(logn).

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

Таблица переходов в Redis:

typedef struct zskiplist {
     // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
 } zskiplist;
typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值
    double score;
     // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
         // 跨度---前进指针所指向节点与当前节点的距离
        unsigned int span;
    } level[];
} zskiplistNode;

zadd---zslinsert--- среднее O(logN), наихудшее O(N)

zrem---zsldelete--- среднее O(logN), худшее O(N)

zrank--zslGetRank--- среднее O(logN), худшее O(N)

Суммировать

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

Красота структур данных ярко отражена в Redis: от String до сжатых списков, быстрых списков, хэш-списков и списков переходов — все эти структуры данных применяются в разных местах и ​​выполняют соответствующие функции.

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

Автор: Ян Хэн

Дальнейшее чтение:Чат Redis (1): построение графа знаний

Источник: Технологический институт CreditEase.