Говоря об основных принципах пяти структур данных Redis

концепция

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

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

Далее мы проанализируем базовую структуру этих пяти структур данных.

Здесь выбрана версияredis-5.0.4, так что сегодня может быть много мест, которые не согласуются с другими сообщениями блога в Интернете, и я укажу на разные места в тексте.

string

Поскольку Redis разработан на языке C, строковых библиотек для Java и C++, естественно, нет.В Redis он определяет строковый формат, называемый SDS (Simple Dynamic String), который представляет собой простую динамическую строку.

Эта структура определена в sds.h:

typedef char *sds;

Но этот тип sds используется только как параметр и возвращаемое значение, а не тип, который действительно используется для операций.Настоящая основная часть — это следующие классы:

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 
    uint8_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;
    uint16_t alloc; 
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; 
    uint64_t alloc;
    unsigned char flags; 
    char buf[];
};

За исключением первой структуры (которая устарела), структуру определенного типа sds можно разделить на следующие части:

len: используемая длина, т.е. реальная длина строки
alloc: удалена длина после заголовка и терминатора ('\0')
флаги: младшие 3 бита представляют тип строки, а остальные 5 бит не используются (я еще не нашел, где Redis использовал это свойство)
buf[]: хранить данные персонажа

Вот сравнение со старой версией, т.к. у меня под рукой только версии 4.x и 5.x, и их реализация sds одинакова, но по другим данным реализация предыдущей версии sds отличается, буду загрузите его, когда у меня будет время. Посмотрите, он делит строку на следующие части:

len: длина, уже занятая в buf (представляющая фактическую длину этой строки)
бесплатно: неиспользованная длина буфера в buf
buf[]: где на самом деле сохраняются строковые данные

При этом redis пишет и переписывает большое количество методов, связанных с типом sds.Почему redis так усердно работает?Есть следующие четыре преимущества:

Уменьшите временную сложность получения длины строки до O (1)
Уменьшено перераспределение памяти при изменении строк
Несмотря на совместимость со струнами C, эффективность некоторых методов струнных инструментов была повышена.
Двоичная безопасность (данные записываются в том же формате, что и читаются)

list

Когда мы смотрим на исходный файл, мы видим, что есть два списка: один — ziplist, что буквально означает сжатый список, а другой — quicklist, что буквально означает быстрый список.Быстрый список используется непосредственно в Redis, но давайте посмотрим на сначала зиплист.

ziplist

ziplist не является именем класса, его структура следующая:<zlbytes><zltail><entries><entry>...<entry><zlend>

Значения каждой части следующие:

zlbytes: 4 байта (32 бита), указывающее общее количество байтов, занимаемых ziplist
zltail: 4 байта (32 бита), указывающее количество байтов смещения в ziplist последнего узла в ziplist
записи: 2 байта (16 бит), указывающие количество элементов в ziplist
запись: длина является переменной, что указывает на данные в ziplist
zlend: 1 байт (8 бит), указывающий конечный маркер, это значение фиксируется на ff (255)

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

Ziplist использует сжатие данных для хранения, а метод сжатия не имеет значения. С точки зрения макросов ziplist подобен инкапсулированному массиву. С помощью zltail хвостовые данные можно легко добавлять и удалять, а записи можно использовать для легкого вычисления длина.

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

quicklist

Его основная структура данных выглядит следующим образом:

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* ziplist所有节点的个数 */
    unsigned long len;          /* quicklistNode节点的个数 */
    int fill : 16;              /* 单个节点的填充因子 */
    unsigned int compress : 16; /* 压缩端结点的深度 */
} quicklist;

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

В redis.conf для оптимизации можно использовать следующие два параметра:

list-max-ziplist-size: указывает размер в байтах каждого узла quicklistNode. Значение по умолчанию — 2, что означает 8 КБ.
list-compress-depth: указывает, должен ли быть сжат узел quicklistNode. По умолчанию 0, что означает отсутствие сжатия.

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

hash

Хэш-структура является наиболее распространенной в использовании Redis.В Redis хэш-структура имеет два представления: zipmap и dict

zipmap

Формат zipmap следующий:<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"

Смысл каждой части следующий:

zmlen: 1 байт, указывающий общее количество байтов zipmap
len: 1~5 байтов, указывающих длину строки, которая будет сохранена следующей
свободный: 1 байт, представляющий собой 8-битное число без знака, указывающее количество свободных неиспользуемых байтов после строки, которая генерируется путем изменения значения, соответствующего ключу

Две соседние строки — это ключ и значение, например, в приведенном выше примере это означает"foo" => "bar", "hello" => "world"такая переписка

Недостаток этого метода также очевиден, то есть временная сложность поиска O(n), поэтому его можно использовать только как легковесную хеш-карту.

dict

Этот метод подходит для хранения больших данных в следующем формате:

typedef struct dict {
    dictType *type;	/* 指向自定义类型的指针，可以存储各类型数据 */
    void *privdata; /* 私有数据的指针 */
    dictht ht[2];	/* 两个hash表，一般只有h[0]有效，h1[1]只在rehash的时候才有值 */
    long rehashidx; /* -1：没有在rehash的过程中，大于等于0：表示执行rehash到第几步 */
    unsigned long iterators; 	/* 正在遍历的迭代器个数 */
} dict;

Если мы не хотим углубляться, мы можем понять этот уровень.Структура dictEntry, которая фактически хранит данные, выглядит следующим образом:

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

Очевидно, что это связанный список, мы знаем, что достаточно хранить в связанной структуре

Этот метод потребляет больше памяти, поэтому облегченная zip-карта обычно используется, когда данных меньше.

set

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

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

Значения полей следующие:

encoding: формат кодирования данных, указывающий, что каждый элемент данных хранится в нескольких байтах (значения 2, 4 и 8)
длина: количество элементов
содержимое: гибкий массив, эта часть памяти выделяется отдельно, в intset не входит

Мы не будем подробно раскрывать конкретные операции. Это должно быть очень ясно, чтобы понять структуру данных наборов. Давайте поговорим об этом здесь. В Intset есть концепция обновления данных. Например, у нас есть набор 16-битных целых чисел. 32-битное целое число, поэтому вся коллекция обновляется до 32-битного целого числа, но не наоборот, что является источником гибкого массива.

Если коллекция слишком велика, она будет сохранена в методе dict.

zset

Zset, также называемый во многих местах отсортированным набором, представляет собой структуру пар ключ-значение.Его ключ называется member, который является элементом набора (zset по-прежнему установлен, поэтому члены не могут совпадать), а соответствующее ему значение называется счет — это число с плавающей запятой, которое можно понимать как приоритет, который используется для упорядочивания zset

Он также имеет два метода хранения, один из них — формат ziplist/zipmap, который мы не будем слишком подробно представлять, просто нужно понять этот формат и упорядочить данные в порядке оценки.

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