Понимание структуры данных, лежащей в основе высокой производительности Redis (2)

Redis

предисловие

В предыдущей статье мы узнали о реализации базовых структур данных String, List и Hash, а затем рассмотрим реализацию базовых структур данных Set и ZSet. Без дальнейших церемоний, давайте начнем.

1. Набор для сбора

1.1 Базовая реализация set

Давайте посмотрим на базовую структуру данных набора через клиент Redis:

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

athkGR.png

На приведенном выше рисунке у меня есть только 10 значений, соответствующих ключу, и базовая структура данных по-прежнему является intset, но когда я добавляю еще одну строку, базовая структура данных также преобразуется из intset в dict.

Кроме того, мы можем только продумать название структуры данных, что intset может хранить только числа типа int, а наибольший целочисленный диапазон, который может выражать intset, равен -2^64 ~ 2^64-1, если добавленное число size находится за пределами этого диапазона, что также приводит к тому, что intset превращается в dict. Итак, мы можем резюмировать следующим образом:

  1. Когда значение, соответствующее ключу в наборе, является числом (значение, соответствующее ключу, может быть только числом), и когда диапазон чисел находится между -2^64~2^64-1, и количество добавленных множество элементов не превышаетset-max-intset-entriesКогда значение настроено, базовой структурой данных набора ключей коллекции является intset.
  2. В других случаях базовой структурой данных является словарь dict.

1.2 Целочисленная коллекция Intset

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

Структура данных intset определяется следующим образом (код взят изintset.h):

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

  • encoding: Формат кодирования данных, указывающий, что каждый элемент в наборе значений хранится в нескольких байтах.

    1. INTSET_ENC_INT16 означает, что каждый элемент хранится в 2 байтах.
    2. INTSET_ENC_INT32 означает, что каждый элемент хранится в 4 байтах.
    3. INTSET_ENC_INT64 означает, что каждый элемент хранится в 8 байтах.

    Таким образом, целое число, хранящееся в intset, может занимать не более 64 бит.

  • length: указывает количество элементов в intset.

  • contents: это динамический массив, который фактически хранит данные. Общая длина этого массива равнаencoding * length. Здесь нам нужно обратить внимание на то, что формат кодирования intset будет скорректирован с учетом вновь добавленных элементов, а кодирование данных будет обновлено в соответствии с размером элементов.

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

1.2 Зачем создавать целочисленную коллекцию intset

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

Некоторые друзья могут задавать вопросы. Даже если накладные расходы памяти, используемые dict, немного больше, временная сложность запроса dict составляет O (1). По сравнению с intset среднее время запроса меньше. Для Redis, который стремится к высокой производительности. Конечно, лучше использовать дикт. Здесь я хочу напомнить всем, не забывайте, что intset — это отсортированный набор, мы можем использовать бинарный метод для поиска данных в отсортированном наборе, и его временная сложность O(logn), потому что при использовании intset количество set элементов относительно невелик, так что это мало на что влияет.

2. Сортированный набор zset

2.1 Базовая реализация zset

Упорядоченный набор расширяет упорядоченный набор на основе набора.В zset реализованы две базовые структуры данных: сжатый списокziplistи стол для прыжковzskiplist.

Когда zset использует ziplist в качестве базовой реализации, должны быть выполнены следующие два условия:

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

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

2.2 список пропусков

2.2.1 Что такое таблица пропуска

Полное имя списка пропуска — это список пропуска, который позволяет быстро запрашивать, вставлять и удалять связанный с данными список упорядоченных последовательных элементов. Средняя сложность времени поиска и вставки для списков пропуска составляет O (logn).

Список с пропуском построен на основе односвязного списка.Мы знаем, что преимущество структуры данных односвязного списка заключается в том, что временная сложность вставки и удаления составляет O (1), но эффективность запросов односвязного списка очень низка, а временная сложность O(n), даже если наши данные упорядочены, нам нужно пройти с самого начала, чтобы получить узел связанного списка, который мы хотим получить. Есть ли способ повысить эффективность запросов односвязного списка? Мы знаем, что временная сложность запроса массива составляет O(1), потому что массивы могут напрямую обращаться к данным через индексы, и мы также можем понимать индексы как индексы. Можно ли повысить эффективность запроса данных, добавив индекс в односвязный список?

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

Если мы добавим указатель через каждые два соседних узла, пусть указатель указывает на следующий узел, как показано на рисунке:

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

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

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

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

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

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

2.2.2 Сравнение таблиц переходов, хеш-таблиц и бинарных сбалансированных деревьев

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

2.2.3 Реализация списка пропусков в Redis

Skiplist — это просто структура данных, предоставляемая zset.Нижний слой zset использует не только skiplist, но и dict.

Redis определяет список пропусков следующим образом, а исходный код взят из:redis/src/server.h


#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPLIST_P 0.25

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;

Проанализируйте приведенный выше исходный код:

  • zskiplist определяет структуру данных списка пропуска, которая включает в себя:
    1. Голова указателя головы и хвост указателя хвоста
    2. length представляет длину связанного списка, то есть количество узлов в связанном списке.
    3. level указывает общее количество уровней skiplist, то есть максимальное количество уровней всех узлов
  • zskiplistNode определяет содержимое каждого узла связанного списка.
    1. sds ele: Это поле данных, которое фактически хранит данные. Оно использует динамическую строку sds, о которой мы упоминали ранее, для хранения данных.
    2. двойная оценка`: оценка, сортировка основана на этой оценке.
    3. zskiplistNode *backward: Указатель на узел-предшественник текущего узла, здесь мы можем понимать его как двусвязный список.
    4. zskiplistLevel: Уровень каждого узла, максимальное значение 32, определяется ZSKIPLIST_MAXLEVEL.
      • zskiplistNode *forward: Указатель уровня на следующий узел.
      • zskiplistNode *forward: span, промежуток слоя от следующего узла

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

zskiplist.png

2.2.4 Базовая реализация отсортированного множества в Redis

Ранее мы говорили только о реализации Redis для списка пропуска, но базовая реализация Redis для отсортированного набора — это не только структура данных списка пропуска, но и dict+skiplist.Redis определяет zset следующим образом:

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

Почему Redis спроектирован таким образом, нужен дополнительный дикт. Из вышеизложенного мы, возможно, уже знаем преимущества skipsit.Эффективность skiplist для запроса диапазона относительно высока, но эффективность поиска с одним значением, очевидно, не так хороша, как у dict.Поэтому Redis использует структуру данных dict. для достижения быстрого поиска с одним значением означает найти. Точно так же, как когда мы ищем ключевые элементы score zscore члена в ключе, если мы используем таблицу переходов для поиска, нам нужно пройти каждый элемент в связанном списке один за другим, пока элемент, который вам нужно найти, не будет сопоставлен. , поэтому эффективность запроса очень низкая.

Таким образом, Redis дополнительно использует словарь для хранения членов и значений оценок. Ключ в словаре — это член, а значение — оценка. В списке пропусков хранится каждый узел связанного списка, отсортированный по баллам. В узле связанного списка хранятся баллы и члены. Структура хранения может быть структурой, которую мы нарисовали на рисунке выше. Но здесь я хочу сказать, что только команда zscore в структуре данных отсортированного набора использует dict, а остальные команды используют структуру данных zskiplist для обеспечения операций.

Вот как на самом деле выглядит структура данных zset:

3. Анализ хранилища данных Redis

3.1 Структура хранилища Redis

Redis – это типичная высокопроизводительная база данных типа "ключ-значение", которая поддерживает множество типов данных. Ключ может быть только строкового типа. Значение поддерживает следующие типы данных: строка, список, хэш, набор и сортировка. Сортировка набора. set, как Redis поддерживает несколько структур данных? С точки зрения внутренней реализации Redis, Redis фактически эквивалентен объектной системе Redis инкапсулирует каждый тип данных в объект redisObject, и каждый объект реализуется как минимум одной из структур данных, упомянутых ранее. Давайте посмотрим, как нижний уровень Redis хранит данные через исходный код Redis, У нас есть простое понимание общего обзора Redis на следующем рисунке.

RedisServer имеет несколько redisDbs. RedisDb эквивалентен концепции библиотеки в Mysql. Redis по умолчанию использует 16 redisDbs на сервере. Этот параметр можно изменить с помощью файла конфигурации redis. Каждый redisDb представляет собой словарь dict, и каждый dict содержит хранятся данные пары "ключ-значение", такие как ключ-значение. Каждый ключ и значение в Redis состоит из redisObject. Каждый redisObject соответствует пяти основным типам данных, предоставляемым Redis. Конкретные детали будут подробно рассмотрены ниже.

Я считаю, что у меня есть определенное понимание структуры хранения данных Redis. Далее, давайте посмотрим на детали реализации Redis через исходный код, и это также проверка того, что мы сказали ранее. Это не то, что Я сказал чушь, о которой написано в исходниках redis.

Во-первых, давайте взглянем на исходный код redisDb.Следующий исходный код взят изredis/src/server.h. Я не буду здесь говорить о коде redisServer, если вам интересно, вы можете кликнуть здесь, чтобы забрать его:Исходный код redisServer

typedef struct redisDb {
    // 键值对字典，保存数据库中所有的键值对
    dict *dict;                 /* The keyspace for this DB */
    // 过期字典，保存着设置过期的键和键的过期时间
    dict *expires;              /* Timeout of keys with a timeout set */
     // 保存着 所有造成客户端阻塞的键
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
     // 保存着 处于阻塞状态的键，value为NULL
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    // 事物模块，用于保存被WATCH命令所监控的键
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    // 数据库ID
    int id;                     /* Database ID */
    // 键的平均过期时间
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

Мы обнаружили, что в redisDb есть пять словарей, тесно связанных с пользователями.dict *dictа такжеdict *expires, первый словарь используется для хранения всех данных пары ключ-значение, а второй хранит ключи, которые мы установили, время истечения срока действия в таблице словарей, ключ — это наш ключ, а значение — отметка времени.

3.2 анализ redisObject

Выше мы сказали, что все ключи и значения, хранящиеся в словаре, являются redisObjects.Давайте посмотрим на определение структуры redisObject через исходный код: исходный код исходит изredis/src/server.h строка 606

typedef struct redisObject {
   
    unsigned type:4;
    unsigned encoding:4; 
 
    unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */
    //引用计数
    int refcount;
    //指向底层数据实现的指针
    void *ptr;
} robj;

Значение каждого параметра redisObject:

  1. unsigned type:4: Тип данных объекта, на который приходится 4 бита, всего 5 типов, а именно:
    • OBJ_STRING: строковый объект
    • OBJ_LIST: Объект списка
    • OBJ_SET: объект коллекции
    • OBJ_ZSET: упорядоченный набор объектов
    • OBJ_HASH: Хэш-объект
  2. unsigned encoding:4: Кодировка объекта с учетом 4 бит, всего 10 типов
    • OBJ_ENCODING_RAW: необработанное представление, строковые объекты представляют собой простые динамические строки.
    • OBJ_ENCODING_INT: целое число длинного типа
    • OBJ_ENCODING_HT: словарь
    • OBJ_ENCODING_ZIPMAP: устарело, не используется
    • OBJ_ENCODING_LINKEDLIST: двусторонний связанный список
    • OBJ_ENCODING_ZIPLIST: почтовый список
    • OBJ_ENCODING_INTSET: набор целых чисел
    • OBJ_ENCODING_SKIPLIST: пропустить таблицу и словарь, соответствующие zset, который мы анализировали ранее.
    • OBJ_ENCODING_EMBSTR: простая динамическая строка, закодированная с помощью embstr
    • OBJ_ENCODING_QUICKLIST: Быстрый список
  3. unsigned lru:LRU_BITSИспользуется алгоритмом LRU для расчета времени LRU относительно server.lruclock.
  4. int refcount: счетчик ссылок.
  5. void *ptr: Указатель на базовую реализацию данных.

Писал сюда, вдруг подумал, что в redis есть две команды, одна это команда type, которая возвращает тип данных значения, я думаю возвращаемый тип должен быть в redisObjectunsigned typeполе. Есть еще одна команда кодирования объекта, которая возвращает кодировку типа данных, я думаю, что она должна быть возвращена здесь, в объекте redisObject.unsigned encodingполе. Взгляд на исходный код действительно совпадает с моим предположением.

char* getObjectTypeName(robj *o) {
    char* type;
    if (o == NULL) {
        type = "none";
    } else {
        switch(o->type) {
        case OBJ_STRING: type = "string"; break;
        case OBJ_LIST: type = "list"; break;
        case OBJ_SET: type = "set"; break;
        case OBJ_ZSET: type = "zset"; break;
        case OBJ_HASH: type = "hash"; break;
        case OBJ_STREAM: type = "stream"; break;
        case OBJ_MODULE: {
            moduleValue *mv = o->ptr;
            type = mv->type->name;
        }; break;
        default: type = "unknown"; break;
        }
    }
    return type;
}

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

4. Анализ исходного кода поиска данных Redis

Пока что мы прошли все структуры данных в Redis и имеем определенное представление обо всем хранилище данных Redis. Наконец, я хотел бы проанализировать, как Redis ищет данные через исходный код. Давайте иметь определенное представление обо всем процессе поиска данных Redis. Здесь я возьму команду zscore в отсортированном наборе в качестве примера.

Сначала Redis получает команду, отправленную клиентом через запрос.Если функция вызывается, сервер прочитал полный набор параметров команды и сохранил их в списке параметров. В этот момент он входит в метод processCommand. исходный кодметод processCommand() в server.c

int processCommand(client *c) {
    if (!strcasecmp(c->argv[0]->ptr,"quit")) {
        addReply(c,shared.ok);
        c->flags |= CLIENT_CLOSE_AFTER_REPLY;
        return C_ERR;
    }
  // 这里封装了客户端发送的命令。c->argv[0]->ptr 这里返回的是我们输入的命令第一个参数。
  //比如说我们输入的是 zscore fruits apple. c->argv[0]->ptr 是fruits。
    c->cmd = c->lastcmd = lookupCommand(c->argv[0]->ptr);
    /** 根据name查找返回对应的命令。源码位置server.c 第3103行
      struct redisCommand *lookupCommand(sds name) {
        return dictFetchValue(server.commands, name);
      }
     */
    /**redisCommand里面记录了命令对应的函数。源码位置server.c 第150行
      struct redisCommand redisCommandTable[] = { 
       {"zscore",zscoreCommand,3,"rF",0,NULL,1,1,1,0,0}
      }
    */
     ...
     /** 此处省略了一些代码，需要的自行翻看源码*/
     ....
     //做了很多的校验，判断命令
     
    // 执行普通的命令
     call(c,CMD_CALL_FULL);
}

c->cmd->proc(c) Это команда выполнения, и последний вызываемый здесь метод — zscoreCommand(). Исходный код изt_zset.c строка 3074

void zscoreCommand(client *c) {
    robj *key = c->argv[1];//这里存储的是c->argv[1] 返回的是我们输入的命令中第二个参数fruits.
    robj *zobj;
    double score;
    // 以读操作取出有序集合对象
    if ((zobj = lookupKeyReadOrReply(c,key,shared.nullbulk)) == NULL ||
        checkType(c,zobj,OBJ_ZSET)) return;
     /** 以读操作取出key的值对象，如果key不存在，则发送reply信息，并返回NULL
        这段代码来自于db.c
        robj *lookupKeyReadOrReply(client *c, robj *key, robj *reply) {
            robj *o = lookupKeyRead(c->db, key);//取出key对应的value
            if (!o) addReply(c,reply);
            return o;
        }
     */
    // zsetScore方法通过我们获取到的ob对象以及成员，返回对应的分数。
    if (zsetScore(zobj,c->argv[2],&score) == C_ERR) {
        //如果失败，返回null
        addReply(c,shared.nullbulk);
    } else {
        addReplyDouble(c,score);    //发送分值
    }
}

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

наконец

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

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

Категории