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

Redis

Внимательно пишите статьи и делитесь ими с душой.

Персональный сайт:yasinshaw.com

Общедоступный номер: технический круг xy

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

redisObject

Ключ Redis — это модель верхнего уровня, и его значение сглажено. В Redis все значения являются объектом, и его структура такова:

typedef struct redisObject {
    unsigned [type] 4;
    unsigned [encoding] 4;
    unsigned [lru] REDIS_LRU_BITS;
    int refcount;
    void *ptr;
} robj;

Кратко опишите эти поля:

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

数据类型及其数据结构

string

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

  • int: хранить целочисленный тип;
  • SDS: хранить с плавающей запятой, строкой, байтовым типом;

SDS: простая динамическая строка простая динамическая строка

SDS

Внутренняя структура данных SDS:

typedef struct sdshdr {
    // buf中已经占用的字符长度
    unsigned int len;
    // buf中剩余可用的字符长度
    unsigned int free;
    // 数据空间
    char buf[];
}

Видно, что нижний слой представляет собой массив символов. Максимальная емкость buf составляет 512 МБ, что позволяет помещать строки, числа с плавающей запятой и байты. Так что можно даже поставить сериализованное изображение. Почему он не использует массив напрямую, а оборачивает его в такую ​​структуру данных?

Потому что buf нужно будет динамически расширять и сжимать. Если массив используется напрямую, каждое изменение строки приведет к перераспределению памяти, что очень неэффективно.

Процесс расширения buf выглядит следующим образом:

  • Если длина len после модификации будет меньше 1M, то размер, выделенный для free, такой же, как len.Например, если после модификации 10 байт, то и для освобождения 10 байт, а фактическая длина buf становится 10 + 10 + 1 = 21 байт.
  • Если измененная длина len будет больше или равна 1M, то длина, выделенная для free, равна 1M, например, после модификации 30M, тогда free равна 1M. Фактическая длина buf становится 30M + 1M + 1 байт.

扩容

Освобождено инертное пространствоОтносится к сокращению строки, нет настоящего ужаса, а указатель на свободу. Это не переназначит память, когда длина строки увеличивается. Но это приведет к отходу, а Redis предоставляет API по-настоящему выпустить память.

list

В нижней части списка находятся две структуры данных: связанный список linkedlist и сжатый список ziplist. Когда количество элементов списка невелико, а длина содержимого элемента невелика, используйте для реализации ziplist, в противном случае используйте связанный список.

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

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

链表

typedef struct list{
    //表头节点
    listNode *head;
    //表尾节点
    listNode *tail;
    //链表所包含的节点数量
    unsigned long len;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void *(*free)(void *ptr);
    //节点值对比函数
    int (*match)(void *ptr,void *key);
}list;

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

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

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

压缩列表

Значения полей на рисунке выше:

  • zlbytes: общая длина списка
  • zltail: указывает на последний элемент
  • zllen: количество элементов
  • запись: содержимое элемента, которое записывает длину предыдущей записи, которая используется для облегчения двунаправленного обхода
  • zlend: всегда 0xFF, как разделитель ziplist

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

hash

В основе хэша лежат две реализации: сжатый список и словарь (dict). Список сжатия был только что представлен выше, а далее в основном представлена ​​структура данных словаря.

Словарь

Словарь на самом деле похож на язык JavaMap, на языке Pythondict. с ЯвойHashMapТочно так же используется нижний слой Redis.хеш-таблицаВ качестве реализации словаря метод связанного списка используется для разрешения конфликтов хэшей. Redis также использует структуру данных для хранения этой хеш-таблицы:

链表

Когда ключ увеличивается или уменьшается, он расширяется или сжимается, аrehash, Значение хеша пересчитано в соответствии с индексом значения. Если словарь тому, как это сделать?

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

set

В наборе нет повторяющихся наборов. Реализация set относительно проста. Если это целочисленный тип, используйте целочисленную коллекцию intset напрямую. Используя бинарный поиск, скорость по-прежнему довольно высока. Однако при вставке из-за движущихся элементов временная сложность составляет O (N).

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

zset

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

пропустить стол

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

Как показано на рисунке ниже, например, если мы хотим найти 8, мы сначала ищем в верхнем слое L2 и находим, что он находится между 1 и 9; затем переходим на слой L1, чтобы найти, что он находится между 5 и 9. ; затем перейдите к L0 и найдите, что он находится между 7 и 9 между ними, затем найдите 8.

Когда элементов много, использование списка пропуска может значительно сократить количество поисков.

跳表

Подобно списку, Redis не использует таблицу пропуска напрямую, а использует настраиваемую структуру данных для хранения таблицы пропуска. Синяя часть слева на рисунке ниже — это список пропуска, а справа — 4 узла zskiplistNodes. В zskiplistNode много слоев L1, L2 и т. д., и указатель указывает на следующий узел этого слоя. BW — это обратный указатель (назад), который используется для возврата при поиске. Затем ниже находится оценка и сам объект объекта.

跳表的数据结构

Суммировать

Redis выставлен снаружиобъект(тип данных), и каждый объект используетredisObjectдержать, через разныекодирование, который соответствует разнымструктура данных. С самого начала этой фигуры вы можете знать, иногдаРазличные объекты могут использовать одну и ту же структуру данных под капотом, такие как сжатые списки и словари.

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

Справочная статья

Эта статья в основном относится к серии статей Redis блогера The Cliffside Xiaosheng, спасибо автору. Ссылка на блог:

блог woo woo woo.cn на.com/hunter net/he…

Обратите внимание на общедоступный номер: технический круг xy

Категории