«Проектирование и реализация Redis» 1 — Структура данных и объекты

Redis

предисловие

  • Почему производительность Redis такая хорошая? Чем он отличается от другого промежуточного ПО для кэширования?
  • Какие структуры данных использует базовый Redis для поддержки такой эффективной производительности?
  • Почему базовые расширенные типы данных реализованы с использованием как минимум двух структур данных? Кто они такие?
  • Можно ли использовать Redis с максимальной пользой, если использовать его разумно?

После изучения предыдущих глав о структурах данных и объектах в «Проектировании и реализации Redis» можно ответить на поставленные выше вопросы. Вы также можете понять, что автор Redis кропотливо разработал так много богатых структур данных, чтобы оптимизировать память. Изучив это содержимое, в процессе использования Redis он также будет использоваться разумно, чтобы адаптироваться к его внутренним характеристикам. Конечно, новая версия Redis поддерживает больше и более богатые функции.Книга основана на версии Redis3 и не охватывает это содержание.

Книга «Проектирование и внедрение Redis» очень проста для понимания, автором является г-н Хуан Цзяньхун, родившийся в 1990-х годах. Кроме того, он также является переводчиком «redis Combat».

Другой может ссылаться на«Проектирование и реализация Redis» 2 — Реализация базы данных

Обзор

Функции

  1. Разработка языка C, отличная производительность, чистая работа с памятью, может обрабатывать более 10 Вт чтения и записи в секунду (QPS)
  2. Разнообразие структур данных, единый максимальный лимит может составлять до 1 ГБ (memcached поддерживает только строки, максимум 1 МБ)
  3. Ограниченный физической памятью, он не может читать и записывать массивные данные. Подходит для высокопроизводительных операций и операций с небольшими объемами данных
  4. Сопровождение сделки, постоянство
  5. Однопоточная модель (memcached многопоточная)

Поддерживаемые типы данных

  1. Sring
  2. List
  3. Set
  4. SortedSet
  5. hash
  6. Bitmap
  7. Hyperloglogs
  8. Geo
  9. pub/sub

Почему Redis такой быстрый

  1. Чистая работа с памятью, без диска io
  2. Однопоточная обработка запросов, отсутствие накладных расходов на переключение потоков, условий гонки и проблем с блокировкой
  3. Модель мультиплексирования epoll, неблокирующий ввод-вывод (мультиплексирование: несколько сетевых подключений; мультиплексирование: мультиплексирование одного и того же потока) Технология мультиплексирования позволяет одному потоку эффективно обрабатывать несколько запросов на подключение.
  4. Структура данных проста, и обработка данных также проста. Также сделал собственную оптимизацию структуры данных

Почему Redis однопоточный?

  1. Один поток уже очень быстр, что снижает нагрузку на сеть, вызванную многопоточностью, операцией блокировки
  2. Последующие версии 4.0 учитывают многопоточность.
  3. Single thread означает, что при обработке сетевых запросов работает только один поток, а не только один поток redis-сервера. При сохранении он выполняется путем разветвления дочернего потока.
  4. Недостаток: Команды, занимающие много времени, приведут к снижению параллелизма, например ключей *

Стратегия утилизации Redis

  1. volatile-lru: выбрать наименее использованные данные из набора данных с истекшим сроком действия server.db[i].expires
  2. volatile-ttl: выберите данные с истекшим сроком действия из набора данных с истекшим сроком действия server.db[i].expires для устранения
  3. volatile-random: выберите произвольные данные для удаления в server.db[i].expires
  4. allkeys-lru: выбрать данные из набора данных (server.db[i].dict), которые использовались реже всего.
  5. allkeys-random: Случайный выбор данных из набора данных (server.db[i].dict) для исключения
  6. no-enviction: запретить удаление данных

Будьте осторожны

  1. Один поток Redis не может обеспечить производительность многоядерного процессора, его можно улучшить, открыв несколько экземпляров Redis на одном компьютере.
  2. Redis реализует распределенные блокировки: сначала используйте setnx (установите, если он не существует), чтобы конкурировать за блокировки.После захвата, expire устанавливает время истечения срока действия, чтобы не забыть снять.
  3. Redis реализует подписку на сообщения «один ко многим»: структура данных sub/pub
  4. Redis реализует очередь сообщений с задержкой: когда метка времени zadd используется в качестве оценки, операция запроса выполняется в соответствии с меткой времени + временем задержки.

Введение основных версий

Новые функции в версии redis5:

  • zpopmax zpopmin и варианты блокировки: возвращает максимальное и минимальное количество данных в коллекции для заданной оценки.

Новые функции в версии reids4:

  • Функция модуля, предоставляющая способ, аналогичный подключаемому модулю, самостоятельно разработать модуль .so и установить его. Сам автор предоставляет модуль нейронной сети. Дополнительные модули можно найти на redis-modules-hub. Функциональность модуля позволяет пользователям использовать Redis в качестве инфраструктуры и создавать дополнительные функции поверх нее, что открывает бесчисленные новые возможности для Redis.
  • PSYNC: устранены некоторые несоответствия в репликации старых версий Redis.
  • Оптимизация стратегии очистки кэша Добавлено последнее часто используемое Оптимизация существующих стратегий
  • неблокирующий DEL FLUSHDB FLUSHALL Решена проблема блокировки при выполнении этих команд до Flushdb async, flushall async, unlink (заменяет del)
  • Добавлен swapdb: база данных подкачки
  • Формат сохраняемости гибридного RDB-AOF
  • Добавить команду использования памяти: MEMORY

структура данных

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

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

структура данных

struct sdshdr {
    uint8_t len; /* used，使用的字节数 */
    uint8_t alloc; /* excluding the header and null terminator，预分配总字节数，不包括结束符\0的长度 */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[]; /*c风格的字符，包括结束符\0*/
};
  • Находится в файле sds.h
  • SDS следует соглашению о том, что строки C заканчиваются на \0 и хранятся в buf (в отличие от базовой реализации nginx, которая не сохраняет последний \0 ​​в реализации)
  • Но не считайте длину последнего символа в len
  • Преимущество сохранения buf в стиле c заключается в том, что вы можете повторно использовать некоторые функции библиотеки c.

Стратегии распределения и освобождения

предварительное выделение пространства

  • Используется для оптимизации операций роста строки SDS, чтобы уменьшить количество перераспределений памяти, необходимых для выполнения последовательных операций роста.
  • При расширении пространства SDS сначала проверьте, достаточно ли неиспользуемого пространства.Если его достаточно, используйте его напрямую.Если нет, не только выделите достаточно места, но и предварительно выделите некоторое пространство.
  • Стратегия предварительного распределения:
    • Измененная длина SDS (значение len)
    • Измененная длина SDS (значение len) >= 1 МБ, предварительно выделено 1 МБ места

Выпуск инертного пространства

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

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

  • Временная сложность получения длины строки снижена с O(N) до O(1)
  • Избегайте переполнения буфера
  • Уменьшите количество перераспределений памяти при изменении строк. Выделение памяти включает сложные алгоритмы и может потребовать системных вызовов, которые отнимают много времени.
  • Двоичная безопасность: терминатор языка c ограничивает его сохранением только текстовых данных, а не двоичных данных, таких как изображения и аудио.

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

структура данных

Находится в файле adlist.h

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;

Функции

  • Двусторонняя очередь, вы можете получить передний узел и задний узел узла, сложность O (1)
  • Ациклический
  • Сложность получения верхнего и нижнего колонтитула O (1)
  • С длиной сложность получения длины связанного списка составляет O (1)
  • Полиморфизм: используйте void* для сохранения значений узлов, которые могут сохранять значения разных типов.

Словарь

структура данных

находится в файле dict.h

хеш-таблица

// 哈希表
typedef struct dictht {
    dictEntry **table; // 一个数组，数组中每个元素都是指向dictEntry结构的指针
    unsigned long size; // table数组的大小
    unsigned long sizemask; // 值总数size-1
    unsigned long used; // 哈希表目前已有节点（键值对）的数量
} dictht;

хеш-узел

// 每个dictEntry都保存着一个键值对，表示哈希表节点
typedef struct dictEntry {
    void *key; // 键值对的键
    // 键值对的值，可以是指针，整形，浮点型
    union { 
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 哈希表节点指针，用于解决键冲突问题
} dictEntry;

Тип словаря

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

typedef struct dictType {
    // 计算哈希值的函数
    uint64_t (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);  
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

Словарь

// 字典
typedef struct dict {
    dictType *type; // 不同键值对类型对应的操作函数
    void *privdata; // 需要传递给对应函数的参数
    dictht ht[2]; // ht[0]用于存放数据，ht[1]在进行rehash时使用
    long rehashidx; /* rehashing not in progress if rehashidx == -1，目前rehash的进度*/
    unsigned long iterators; /* number of iterators currently running */
} dict;

хеш-алгоритм

  • Redis использует алгоритм MurmurHash2 для вычисления хеш-значения ключа.
  • Хеш-значение объединяется с помощью ИЛИ с маской размера, чтобы получить хеш-индекс.
  • Коллизия хэшей (два или более ключа назначаются одному и тому же индексу в массиве хэш-таблицы): метод цепной адресации разрешает коллизию

rehash

  • Расширьте или уменьшите хеш-таблицу, чтобы коэффициент загрузки хэш-таблицы оставался в разумных пределах.
  • Коэффициент загрузки = количество сохраненных (используемых) узлов / размер хеш-таблицы (размер)

Шаги перефразирования включают

  • Выделить место для хеш-таблицы ht[1] словаря, размер которой зависит от выполняемой операции и количества пар ключ-значение, которое ht[0] содержит в данный момент.
    • Операция расширения: размер ht[1] равен первой n степени числа 2, большей или равной ht[0].used, умноженной на 2.
    • Операция сжатия: размер ht[1] равен первой n степени числа 2, больше или равной ht[0].used
  • Перехешировать все пары ключ-значение, хранящиеся в ht[0], в ht[1]: пересчитать хеш-значение и значение индекса ключа.
  • Когда все пары ключ-значение ht[0] будут перенесены в ht[1], освободите ht[0], установите для ht[1] значение ht[0] и создайте новый хеш ужасов как ht[1]

Условия автоматического расширения

  • Сервер не выполняет команду BGSave или команду GBRewriteAOF, а коэффициент загрузки хеш-таблицы >= 1.
  • Сервер выполняет команду BGSave или команду GBRewriteAOF, а коэффициент загрузки хэш-таблицы >= 5.
  • Когда используется команда BGSave или GBRewriteAOF, серверу необходимо создать дочерний процесс текущего серверного процесса, который будет потреблять память.Улучшите коэффициент загрузки, чтобы избежать записи и экономии памяти.

условие автоматического сжатия

  • Автоматически сжимать, когда коэффициент загрузки хэш-таблицы меньше 0,1.

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

  • Переиндексация данных ht[0] в ht[1] не выполняется централизованно за один раз, а выполняется несколько раз постепенно (чтобы избежать проблем с производительностью, когда хеш-таблица слишком велика).

Подробные шаги прогрессивного перефразирования

  • Выделить место для ht[1] для автоматического одновременного хранения двух хеш-таблиц.
  • Rehashidx в словаре установлен в 0, что означает запуск выполнения rehash (значение по умолчанию -1)
  • Во время повторного хэширования каждый раз, когда над словарем выполняется операция, все пары ключ-значение в индексе rehashidx хэш-таблицы ht[0] повторно хэшируются в ht[1]
  • Когда все перефразирование завершено, rehashidx устанавливается равным -1.

будь осторожен

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

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

  • Таблица переходов — это упорядоченная структура данных, которая обеспечивает быстрый доступ к узлам за счет поддержки нескольких указателей на другие узлы в каждом узле.
  • Временная сложность: худшее O(N), среднее O(logN)
  • В большинстве случаев эффективность сопоставима с эффективностью сбалансированного дерева, но его проще реализовать, чем сбалансированное дерево.
  • Одна из базовых реализаций отсортированных наборов

структура данных

находится в файле server.h

// 跳跃表节点
typedef struct zskiplistNode {
    sds ele; // 成员对象
    double score; // 分值，从小到大排序
    struct zskiplistNode *backward; // 后退指针，从表尾向表头遍历时使用
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span; // 跨度，记录两个节点之间的距离
    } level[]; // 层，是一个数组
} zskiplistNode;

// 跳跃表相关信息
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 表头和表尾
    unsigned long length; // 跳跃表长度（包含节点的数量）
    int level; // 跳跃表内层数最大那个节点的层数（不包括表头节点层数）
} zskiplist;

  • Размер массива уровней генерируется случайным образом каждый раз, когда создается новая таблица переходов, и находится в диапазоне от 1 до 32.
  • Операция обхода использует только прямой указатель, диапазон используется для вычисления ранга, а сумма всех промежутков слоя, посещенных на этом пути, является рангом узла.
  • Несколько узлов могут содержать одну и ту же ветвь, но каждый объект-член узла уникален.

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

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

структура данных

Находится в файле intset.h

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length; // 长度
    int8_t contents[]; // 内容,数组内容类型取决于encoding属性，并不是int8_t。按照大小排序，没有重复
} intset;

Обновить

  • Когда мы хотим добавить новый элемент в коллекцию целых чисел, а тип нового элемента длиннее, чем все существующие типы элементов коллекции целых чисел, перед добавлением новых данных необходимо обновить коллекцию.
  • Процедура обновления состоит из трех шагов:
    • В соответствии с типом, расширить размер, выделить место
    • Преобразуйте базовые данные массива в новый тип и измените правильное местоположение.
    • Новые элементы добавляются в базовый массив
  • Добавление элементов может привести к обновлениям, поэтому добавление новых элементов имеет мировую сложность O (N)
  • Даунгрейд не поддерживается, новый тип данных всегда будет поддерживаться после обновления

Преимущества обновления

  • Повышение гибкости
  • сохранить память

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

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

Состав сжатого списка

Атрибуты тип длина использовать
zlbytes uint32_t 4 байта Количество байтов памяти, занимаемых всем сжатым списком
zltail uint32_t 4 байта Сколько байт занимает хвостовой узел от начального адреса сжатого списка, и хвостовой узел можно получить без обхода
zllen uint16_t 2 байта Количество узлов. Если оно меньше 65535, это фактическое значение. Когда оно превышает 65535, его необходимо пройти для расчета
entryN узел списка неопределенный Каждый узел включен
zlend uint8_t 1 байт Специальное значение 0xFF, конечный маркер

Состав узлов сжатого списка

  • previos_entry_length: длина предыдущего узла, используемого для возврата от хвоста к голове
    • Если длина предыдущего узла меньше 254 байт, длина preivos_entry_length представлена ​​1 байтом.
    • Если длина предыдущего узла меньше 254 байт, длина preivos_entry_length представлена ​​5 байтами, первый байт равен 0xFE (254), а следующие четыре байта представляют фактическую длину.
  • Кодировка: Запишите тип и длину содержимого.Кодировка разделена на две части: старшие два бита и оставшиеся цифры.Значения старших двух цифр следующие:
    Два самых высоких значения Представляет тип данных байты кодирования оставшиеся биты максимальная дальность
    00 массив символов байт 6bit 63 бит
    01 массив символов два байта 14bit 2^14-1
    10 массив символов пять байтов 4*8, оставшиеся 6 бит первого байта остаются пустыми 2^32-1 бит
    11 целое число 1 байт 000000 целое число типа int16_t
    11 целое число 1 байт 010000 целое число типа int32_t
    11 целое число 1 байт 100000 целое число типа int64_t
    11 целое число 1 байт 110000 24-битное целое число со знаком
    11 целое число 1 байт 111110 8-битное целое число со знаком
    11 целое число 1 байт xxxxxx Без содержимого xxxx сам по себе представляет целое число от 0 до 12.
  • содержимое: содержит значение узла

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

  • Несколько последовательных узлов размером около 254 узлов вызывают непрерывное выделение памяти из-за расширения. Однако в случае со временем такая ситуация встречается относительно редко.

объект

Обзор

  • Redis не использует напрямую предыдущую структуру данных для реализации базы данных пар ключ-значение, а создает объектную систему на основе структуры данных, и каждый объект использует хотя бы одну из предыдущих структур данных.
  • Каждый объект представлен структурой redisObject.
//server.h
typedef struct redisObject {
   unsigned type:4; //类型
   unsigned encoding:4; // 编码
   // 对象最后一个被命令程序访问的时间
   unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                           * LFU data (least significant 8 bits frequency
                           * and most significant 16 bits access time). */
   int refcount; // 引用计数
   void *ptr; // 指向底层的数据结构指针
} robj;

Преимущества использования объектов

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

объект в редисе

  • строковый объект
  • объект списка
  • хэш-объект
  • объект коллекции
  • упорядоченное сочетание объектов

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

тип объекта

объект Свойство типа объекта вывод команды типа
строковый объект REDIS_STRING string
объект списка REDIS_LIST list
хэш-объект REDIS_HASH hash
объект коллекции REDIS_SET set
упорядоченный объект коллекции REDIS_ZSET zset

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

  • Кодировка определяет тип данных, на который указывает ptr, указывая, какой тип данных используется в качестве базовой реализации.
  • Используйте как минимум две разные кодировки для каждого типа объекта.
  • Благодаря кодированию Redis может устанавливать разные кодировки в соответствии с разными сценариями, что значительно повышает гибкость и эффективность.
константа кодирования соответствующая структура данных Вывод команды OBJECT ENCODING
REDIS_ENCODING_INT Целое число длинного типа "инт"
REDIS_ENCODING_EMBSTR Простая динамическая строка, закодированная с помощью embstr "эмбстр"
REDIS_ENCODING_RAW простая динамическая строка "сырой"
REDIS_ENCODING_HT Словарь "хеш-таблица"
REDIS_ENCODING_LINKEDLIST Двусторонний связанный список "связанный список"
REDIS_ENCODING_ZIPLIST Сжатый список "зиплист"
REDIS_ENCODING_INTSET коллекция целых чисел "вставка"
REDIS_ENCODING_SKIPLIST Таблицы перехода и словари "скиплист"

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

  • Кодировка строкового объекта может быть
    • int
    • raw
    • embstr
  • Числа с плавающей запятой также хранятся в Redis как строковые объекты, и при выполнении вычислений они сначала преобразуются обратно в числа с плавающей запятой.
Содержимое строкового объекта длина тип кодирования
целочисленное значение - int
строковое значение менее 32 байт embstr
строковое значение больше 32 байт raw

Кодировка embstr — это оптимизированный метод кодирования, специально используемый для сохранения коротких строк. Эта кодировка, как и исходная кодировка, использует структуру redisObject и структуру sdshdr для представления объектов. Разница в том, что:

  • Необработанное кодирование дважды вызывает функцию выделения памяти для создания структур redisObject и sdrhdr соответственно.
  • embstr вызывает функцию выделения памяти один раз, чтобы создать непрерывное пространство, которое включает в себя redisObject и sdrhdr.

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

Когда объекты с кодировкой int и embstr удовлетворяют условиям, они будут автоматически преобразованы в строковые объекты с необработанным кодированием.

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

строковая команда

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

  • set
  • get
  • append
  • incrbyfloat
  • incrby
  • decrby
  • strlen
  • strrange
  • getrange

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

  • Кодировка объекта списка может быть
    • ziplist
    • linkedlist

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

Два условия для использования кодировки ziplist следующие, а те, которые не выполняются, кодируются в linkedlist (эти два условия можно изменить в файле конфигурации):

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

команда списка

  • lpush
  • rpush
  • lpop
  • rpop
  • lindex
  • llen
  • linsert
  • lrem
  • ltrim
  • lset

хэш-объект

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

  • ziplist
  • hashtable

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

  • Для использования ziplist необходимо выполнить два условия, если нет, то используется хеш-таблица (эти два условия можно изменить в файле конфигурации)
    • Все пары ключ-значение имеют строки ключа и значения длиной менее 64 байт.
    • Количество пар ключ-значение меньше 512.

хэш-команда

  • hset
  • hget
  • hexists
  • hdel
  • hlen
  • hgetall

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

Кодировка объекта коллекции может быть:

  • intset: все элементы хранятся в наборе целых чисел
  • hashtale: значение словаря равно null

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

Коллекция использует intset для выполнения двух условий, если нет, используйте hashtable (параметры можно изменить через файл конфигурации)

  • Все сохраненные элементы являются целыми значениями
  • Количество элементов не превышает 512

установить команду

  • sadd
  • scard
  • sismember
  • smembers
  • srandmember
  • spop
  • srem

упорядоченное сочетание объектов

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

  • ziplist: каждый элемент представлен двумя узлами рядом друг с другом, первый представляет участника, а второй представляет счет. Маленькие баллы располагаются ближе к началу таблицы, а большие — ближе к концу таблицы.
  • skiplist: используйте zset в качестве базовой реализации.Структура zset включает в себя как словарь, так и список пропусков, которые используются для поиска оценки и сортировки оценки или запроса диапазона в соответствии с ключом соответственно.
// 两种数据结构通过指针共享元素成员和分值，不会浪费内存
typedef struct zset {
    zskplist *zsl; //跳跃表，方便zrank，zrange
    dict *dict; //字典，方便zscore
}zset;

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

При выполнении следующих двух условий используйте кодировку ziplist, в противном случае используйте Skiplist (можно изменить в файле конфигурации)

  • Количество сохраненных элементов меньше 128
  • Длина элемента меньше 64 байт.

упорядоченная команда установки

  • zadd
  • zcard
  • zcount
  • zrange
  • zrevrange
  • zrem
  • zscore

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

Команды Redis можно разделить на две категории:

  • Может быть выполнен на любом типе ключа, например
    • del
    • expire
    • rename
    • type
    • object
  • Может выполняться только для определенных типов ключей, например, предыдущие команды для различных объектов. Это реализовано через атрибут type объекта redisObject.

восстановление памяти

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

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

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

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

  • Продолжительность бездействия = текущее время - redisObject.lru, lru записывает время последнего доступа к объекту
  • Когда Redis настроен на максимальный объем памяти (maxmemory), когда алгоритм восстановления определяет, что объем памяти превышает это значение, для восстановления памяти первыми будут освобождены те, у которых больше времени простоя.

Справочная команда

# 设置字符串
set msg "hello world"
rpush numbers 1 2 3 4 5
llen numbers
lrange numbers 0 5
# 获取键值使用的底层数据结构
object encoding numbers
# 查看对象的引用计数值
object refcount numbers
# 对象空转时长: value=now-object.lru
object idletime numbers

использованная литература

  • «Проектирование и реализация Redis»
Категории