Базовая структура данных Redis (SDS и связанный список)

Java

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

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

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

image

В этой статье мы познакомим вас с двумя структурами данных SDS: простыми динамическими строками и двусторонними связанными списками.

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

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

В исходном коде Redis в файле sds.h есть пять видов sdshdr:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

Среди них комментарии sdshdr5 указывают на то, чтоsdshdr5 is never used. Структура данных sdshdr5 обычно используется для хранения строк длиной менее 32 символов, но эта структура больше не используется.Для хранения строк небольшой длины рекомендуется использовать sdshdr8, т. к. в sdshdr5 отсутствуют два ключа. не является операцией динамического расширения. После того, как предварительно выделенное пространство памяти будет израсходовано, необходимо перераспределить память и завершить репликацию и миграцию данных. В реальной производственной среде влияние на производительность по-прежнему велико, поэтому заброшенный, но на самом деле некоторые меньшие ключи все еще будут храниться в этой структуре.

Про sdshdr5 больше говорить не будем, давайте посмотрим на поля остальных четырех структур Поле len представляет общую длину текущей строки, то есть размер памяти, используемой текущей строкой, а alloc представляет собой общую память размер, выделенный для текущей строки (не включая память, выделенную len и самим полем flags), потому что каждая структура будет выделять дополнительное пространство памяти при предварительном выделении, в основном для облегчения будущего расширения. Нижние три бита флагов представляют текущий тип sds, а старшие пять битов бесполезны. Нижние три значения следующие:

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

На самом деле, redis отключает выравнивание памяти для выделения памяти sdshdr, то есть адреса памяти, выделенные каждым полем, расположены близко друг к другу, поэтому передача строковых параметров в redis напрямую используетchar* указатель.

Некоторые люди могут сомневаться, что только черезcharКак указатель определяет тип текущей строки? На самом деле, поскольку выделение памяти sdshdr запрещает выравнивание памяти, sds[-1] фактически указывает на адрес памяти поля flags. Через поле flags можно получить тип текущий sds, а затем вы можете прочитать поле «Возьмите заголовок», чтобы определить соответствующие атрибуты sds.

Далее поговорим об улучшении производительности sdshdr по сравнению с традиционными строками языка C и о том, какие у него есть удобные моменты.

во-первых, Для традиционных строк C я хочу получить длину строки, требуется как минимум O (n) обход массива, а нашим sds требуется только O (1), чтобы получить значение поля len.

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

Каждый раз, когда sdshdr выделяет память для sds, он выделяет дополнительную часть пространства памяти, которая не используется в настоящее время.Как правило, дополнительная память будет равна размеру памяти, занятой текущей строкой.Если он превышает 1 МБ , объем памяти дополнительного пространства составляет 1 МБ. Всякий раз, когда выполняется метод sdscat, программа будет использовать alloc-len для сравнения, достаточно ли оставшейся свободной памяти для выделения дополнительного содержимого, недостаточно ли ее для естественного запуска перераспределения памяти и достаточно ли оставшегося неиспользуемого пространства памяти для проставить, затем прямое выделение без перераспределения памяти.

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

Наконец, для обычной строки языка C он определяет конец строки, оценивая, является ли текущий символ нулевым символом, поэтому требуется, чтобы ваша строка не могла содержать даже нулевой символ, иначе символы после нулевого символа не будут читаются допустимые символы. Для некоторых специальных требований к формату, которые должны быть разделены нулевым символом, традиционная строка C не может быть сохранена, и наш sds оценивает конец строки не по нулевому символу, а по значению поля len Определить конец строки, поэтому у sds тоже естьбинарный сейфЭта функция заключается в том, что он может безопасно хранить двоичные данные с особыми требованиями к формату.

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

Во-вторых, связанный список

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

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

Структура двусвязного списка реализована в Redis с помощью языка C:

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

Указатель pre указывает на предыдущий узел, указатель next указывает на следующий узел, а значение указывает на объект данных, соответствующий текущему узлу. Я украду картинку, чтобы описать всю структуру связанного списка, соединенную последовательно:

image

Хотя я могу пройти узел связанного списка по первому заголовку всего списка, но в направлении структуры redis-layer пакета, исключительно для указания структуры списка:

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;

Руководитель списка указал узел головки, узел хвостовой узел, указывающий на хвост связанного списка, значение функции узла DUP для копии связанного списка для достижения копии передачи, с равными числами в целом достаточно, но в некоторых особых случаях может быть Функция метастазирования узла, по умолчанию можно назначить на эту функциональную нулевую индикацию I.e. Номер узла, равный передаче. Бесплатная функция для освобождения пространства памяти, занятого узлом, назначение по умолчанию NULL, то, что использование redis наступает функцию zfree для выпускания пространства памяти, мы также можем посмотреть на эту функцию zfree.

void zfree(void *ptr) {
#ifndef HAVE_MALLOC_SIZE
    void *realptr;
    size_t oldsize;
#endif

    if (ptr == NULL) return;
#ifdef HAVE_MALLOC_SIZE
    update_zmalloc_stat_free(zmalloc_size(ptr));
    free(ptr);
#else
    realptr = (char*)ptr-PREFIX_SIZE;
    oldsize = *((size_t*)realptr);
    update_zmalloc_stat_free(oldsize+PREFIX_SIZE);
    free(realptr);
#endif
}

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

Верхняя часть функции предназначена для вынесения некоторых суждений.Если определена общая память, занимаемая структурой данных, на которую указывает указатель, функция free вызывается непосредственно для освобождения памяти, в противном случае требуется вычисление. zmalloc в Redis будет добавлять блок данных заголовка PREFIX_SIZE каждый раз, когда выделяются данные в памяти, и его значение равно максимальному адресному пространству текущей системы.Например, если процессор равен 64, PREFIX_SIZE будет занимать 8 байтов, а эти 8 байты внутренне хранят размер памяти, фактически занимаемый текущими данными.

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

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

Функция соответствия по-прежнему является полиморфной реализацией, дается только определение. Конкретная реализация зависит от вас, или вы можете не реализовывать ее. Она используется для сравнения, равны ли значения значений двух узлов связанного списка. . Возвращает 0 для неравного и 1 для равенства.

Последнее поле Len описывает количество узлов, содержащихся во всем связанном списке. Вышеуказанное является базовым определением связанного списка в списке Redis, Plus, абстрактная диаграмма окончательного связанного списка структуры в Redis, вероятно, подобна этому, все еще украдена:

image

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


Обратите внимание на публику и не теряйтесь, программист, который любит делиться. Официальный аккаунт отвечает на "1024" и добавляет авторский WeChat для обсуждения и изучения вместе! Все материалы кода кейса, использованные в каждой статье, будут загружены на мой личный github. GitHub.com/один батат/о… Добро пожаловать!