Redis имеет пять основных структур данных: строка, хэш, набор, zset и список. Но знаете ли вы, какие структуры данных лежат в основе этих пяти структур? Сегодня мы потратим пять минут, чтобы узнать. (Текущая версия Redis — 3.0.6)

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

SDS — это сокращение от «простая динамическая строка». Строки, которые появляются во всех сценариях в Redis, в основном реализуются SDS.

Все нецифровые клавиши. Напримерset msg "hello world"ключ в сообщении.
Значение строкового типа данных. Например, значение msg в ``set msg "hello world" равно "hello wolrd"
«строковое значение» в нестроковых типах данных. НапримерRPUSH fruits "apple" "banana" "cherry""яблоко" "банан" "вишня" в

СДС выглядит так:

свободно: сколько места осталось len: длина строки buf: сохраненный массив символов

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

Чтобы уменьшить количество перераспределений памяти, вызванных изменением строк, sds использует стратегию «одноразового управления»:

Если длина sds после модификации меньше 1 МБ, будет выделено больше места существующей длины len.
Если длина sds после модификации больше или равна 1 МБ, расширение добавит 1 МБ пространства в дополнение к изменению длины.

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

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

int

Это различные числа, хранящиеся в Redis. Включите это, намеренно поместив в кавычки ""

Двусвязный список

Это выглядит так:

Он разделен на две части: одна — «общая часть»: оранжевая, а другая — «конкретная реализация»: синяя.

Основная «координаторская часть»:

headУказатель на начало определенного двусвязного списка
tailУказывает на хвост определенного двусвязного списка
lenдлина двусвязного списка

Конкретная «реализация»: четкая структура двусвязного списка с предшественниками.preиметь преемникаnext

Зависит отlistиlistNodeСостоит из двух структур данных.

ziplist

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

Затем в текстеentryСтруктура такая:

обход элементов

Сначала найдите последний элемент списка:

Затем в соответствии с элементом узла ziplistprevious_entry_lengthсвойства, чтобы пройти один за другим:

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

посмотри сноваentryСтруктура элемента, естьprevious_entry_lengthполе, его длина составляет либо 1 байт, либо 5 байтов:

Длина предыдущего узла меньше 254 байт, тогдаprevious_entry_lengthдлина 1 байт
Длина предыдущего узла больше 254 байт, тогдаprevious_entry_length5 байт в длину

Предположим, что теперь есть набор сжатых списков, каждый из которых имеет длину от 250 до 253 байт, и внезапно добавляется новый узел.new, Если длина больше или равна 254 байтам, появится:

Программа должна постоянно перераспределять пространство сжатого списка до конца.

В дополнение к операциям добавления операции удаления также могут приносить «обновления цепочки». Пожалуйста, смотрите рисунок ниже Длина всех входных узлов в ziplist составляет от 250 байт до 253 байт, длина больших узлов больше 254 байт, а длина маленьких узлов меньше 254 байт.

хеш-таблица

Хэш-таблицы немного сложнее. Обычно существует два способа создания хэш-таблицы, один из них:开放寻址法, один拉链法. Хэш-таблица redis сделана с использованием拉链法.

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

Он также разделен на две части: оранжевая часть слева и синяя часть справа, Точно так же это соотношение между «координацией» и «реализацией». Реализация конкретной хеш-таблицы реализована в синей части. Давайте сначала посмотрим на синюю часть:

Это также разделено на две части: «координация» и «реализация» на левой и правой сторонах.

Правая часть проста для понимания: это стиль хеш-таблицы, обычно реализуемый zip-таблицей; массив — это ведро. Как правило, сначала разные ключи будут располагаться в разных ведрах. Если ключи повторяются, конфликтующие ключи будут связаны связным списком.

Процесс создания нового ключа:

Если повторяется:

rehash

Давайте взглянем на оранжевую часть «координации» слева на общей диаграмме хеш-таблицы, которая имеет два ключевых атрибута:htиrehashidx.htпредставляет собой массив всего из двух элементов ht[0] и ht[1], среди них ht[0] хранит хэш-таблицу, используемую в redis, а ht[1] и rehashidx и хеш-таблицуrehashСвязанный.

rehashОтносится к процессу пересчета хеш-значения и значения индекса ключа, а затем переупорядочению пары ключ-значение.

加载因子（load factor） = ht[0].used / ht[0].size.

Критерии расширения и сжатия

Расширение:

Без выполнения инструкций BGSAVE и BGREWRITEAOF хэш-таблица加载因子больше или равно 1.
В случае выполнения инструкций BGSAVE и BGREWRITEAOF хэш-таблица加载因子больше или равно 5.

сокращать:

加载因子Когда он меньше 0,1, программа автоматически начинает сжимать хеш-таблицу.

Величина расширения и сжатия

Расширение:

Первое больше или равноht[0].used * 2из2^n(2 в энной степени).

сокращать:

Первое больше или равноht[0].usedиз2^n(2 в энной степени).

(Следующая часть относится к подробному анализу, вы можете пропустить, чтобы увидеть шаги расширения напрямую)Насчет усадки у меня возникли сомнения: критерий усадки加载因子Когда он меньше 0,1, то есть если в хэш-таблице 4 элемента, то при длине хэш-таблицы больше 40 она будет уменьшаться.Если длина больше 40, но существующий элемент равен 4 (ht[0].usedДля хеш-таблицы из 4) уменьшите ее, каково значение после сжатия?

Я подумал об этом: по содержанию, упомянутому выше, должно быть 4. Однако, если оно равно 4, существующая и сжатая длины равны, следует ли его снова расширить? Пролистайте исходный код, чтобы увидеть:

Специфические функции сжатия:

int dictResize(dict *d)     //缩小字典d
{
    int minimal;

    //如果dict_can_resize被设置成0，表示不能进行rehash，或正在进行rehash，返回出错标志DICT_ERR
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;

    minimal = d->ht[0].used;            //获得已经有的节点数量作为最小限度minimal
    if (minimal < DICT_HT_INITIAL_SIZE)//但是minimal不能小于最低值DICT_HT_INITIAL_SIZE（4）
        minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(d, minimal);      //用minimal调整字典d的大小
}

int dictExpand(dict *d, unsigned long size)     //根据size调整或创建字典d的哈希表
{
    dictht n; 
    unsigned long realsize = _dictNextPower(size);  //获得一个最接近2^n的realsize

    if (dictIsRehashing(d) || d->ht[0].used > size) //正在rehash或size不够大返回出错标志
        return DICT_ERR;

    if (realsize == d->ht[0].size) return DICT_ERR; //如果新的realsize和原本的size一样则返回出错标志
    /* Allocate the new hash table and initialize all pointers to NULL */
    //初始化新的哈希表的成员
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {   //如果ht[0]哈希表为空，则将新的哈希表n设置为ht[0]
        d->ht[0] = n;
        return DICT_OK;
    }

    d->ht[1] = n;           //如果ht[0]非空，则需要rehash
    d->rehashidx = 0;       //设置rehash标志位为0，开始渐进式rehash（incremental rehashing）
    return DICT_OK;
}

static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE; //DICT_HT_INITIAL_SIZE 为 4

    if (size >= LONG_MAX) return LONG_MAX + 1LU;
    while(1) {
        if (i >= size)
            return i;
        i *= 2;
    }
}

Из кода видно, что если длина после сжатия равна 4, он не только не сожмется, но даже сообщит об ошибке. (😝)

Вернемся и посмотрим на сеттинг: возможен ли заголовок? Расширение хэш-таблицы увеличено в 2 раза, а минимум в 4. 4 ===> 8 ====> 16 =====> 32 ======> 64 ====> 128

То есть: нет случая, когда длина больше 40, только 64. Но если оно равно 64, 64 X 0,1 (предел усадки) = 6,4, то есть при уменьшении до 6 хэш-таблица уменьшится, насколько она уменьшится? это 8. В этот момент продолжайте уменьшать до 4, он больше не будет уменьшаться. Следовательно, нет хеш-таблицы с длиной больше 40, а есть элемент 4.

Шаги расширения

шаг усадки

Прогрессивное обновление

На «этапе расширения» и «этапе сжатия» четвертый этап каждого изображения в двух анимациях «пересчитывает данные в ht[0] с помощью хеш-функции и повторно хэширует их в ht[1]», что не завершено. в один шаг, но разделенный на N шагов и выполненный шаг за шагом. Потому что в хеше можно хранить десятки миллионов или даже сотни миллионов ключей, ведь каждый хеш в Redis может хранить2^32 - 1Пары ключ-значение (более 4 миллиардов), если эти ключи-значения перехешировать за один раз, это может привести к тому, что сервер перестанет обслуживать на какой-то период времени, ведь хеш-функцию приходится вычислять для пока ((#^.^#)).

Обновление хеш-таблицы выполняется несколько раз и последовательно.

Прогрессивное обновление и в оранжевом разделе «Организация» слева на изображении нижеrehashidxтесно связаны:

Значение rehashidx — это позиция элемента текущего повторного хеширования.
Когда rehashidx равен -1, это означает, что обновление не выполняется.

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

Возьмем шаги расширения в качестве примера:

intset

Целочисленные коллекции — это одна из низкоуровневых реализаций ключей коллекций.

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

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

В Redis таблица переходов абстрагируется следующим образом:

Посмотрите на эту картинку, слева - "координация", а справа реализовано. Раздел «Координация» включает в себя следующие пункты:

заголовок: заголовок таблицы переходов
хвост: пропустить конец таблицы
уровень: количество слоев узла с наибольшим количеством слоев
length: длина стола пропуска

В части реализации есть следующие моменты:

Заголовок: это контрольный узел связанного списка, в котором не записываются основные данные.
это двусвязный список
Баллы в порядке
o1, o2 и o3 — элементы, сохраненные узлом, и указатели, которые могут указывать на значение SDS.
Высота самого высокого уровня 32. Каждый раз, когда создается новый узел, программа будет случайным образом генерировать значение от 1 до 32 в качестве размера массива уровней, который является «высотой».

Реализация пяти структур данных в Redis

объект Redis

Redis напрямую не использует различные структуры данных, упомянутые выше, для реализации базы данных «ключ-значение», но основан на объекте, а нижний уровень объекта косвенно ссылается на конкретную структуру данных, упомянутую выше.

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

нить

Среди них: embstr и raw состоят из динамических строк SDS. Единственная разница в том, что когда raw выделяет память, redisobject и sds каждый выделяет часть памяти, а embstr — это redisobject и в одной и той же памяти.

список

hash

set

zset

Для получения более интересного контента, пожалуйста, обратите внимание на мой публичный аккаунт WeChat.`互联网技术窝`Или добавьте WeChat для обсуждения и общения:

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

бросает new.com/2017/09/12/…
«Проектирование и реализация Redis»