Экономия памяти до предела! ! ! Сжатые таблицы в Redis, о которых стоит знать...

Несколько изображений, объясняющих процесс обновления целочисленного набора Redis intset

предисловие

Всем привет, до новых встреч😊.

За последние несколько недель мы рассмотрели базовую структуру данных Redis, такую ​​как动态字符串SDS,双向链表Adlist,字典Dict,跳跃表,整数集合intset, если вы не понимаете общие типы или базовые структуры данных Redis, посетите портал выше.

Сегодня поговорим о базовой реализации zset.压缩表(在数据库量小的时候用), если вы не понимаете zset, посмотрите на портал выше.

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

традиционный массив

Как и базовые данные ранее, сжатый список также является структурой хранения данных, разработанной Redis.

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

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

существующие проблемы

уже упоминалось выше需要用最大长度的字符串大小в виде整个数组所有元素的内存大小, если только один элемент имеет очень большую длину, а другие элементы имеют относительно небольшие длины, то мы используем большие числа для памяти всех элементов, что приведет к трате памяти.

Итак, как мы должны улучшить?

Экспортировать сжатый список

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

Как показано на рисунке ниже, размер памяти определяется в соответствии с фактическим содержимым хранилища каждого узла, то есть первый узел занимает 5 байтов, второй узел занимает 5 байтов, третий узел занимает 1 байт и четвертый узел занимает 1 байт, первый узел занимает 4 байта, а пятый узел занимает 3 байта.

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

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

Графический анализ сжатого списка

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

заголовок

Заголовок состоит из четырех частей: количества байтов в памяти zlbytes, количества байтов от хвостового узла до начального адреса zltail_offset, количества узлов zllength и конечной метки zlend.

• zlbytes: запишите количество байтов памяти, занимаемых всем сжатым списком.
• zltail_offset: записать количество байтов от начального адреса хвостового узла сжатого списка до сжатого списка（目的是为了直接定位到尾节点，方便反向查询）.
• zllength: записывает количество узлов в сжатом списке. То есть количество узлов на приведенном выше рисунке равно 2.
• zlend: содержит константу 255 (0xFF), отмечающую конец сжатого списка.

узел данных

Узел данных включает в себя три части, а именно длину prev_entry_len предыдущего узла, текущий тип данных и формат кодирования, а также конкретное значение указателя данных.

Конкретная реализация сжатого списка

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

Redis не инкапсулирует структуру для хранения информации сжатого списка, как предыдущие структуры, такие как SDS строки, словарь, таблица переходов и т. д. Вместо этого он работает с данными, определяя серию макросов.

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

//返回整个压缩列表的总字节
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

//返回压缩列表的tail_offset变量，方便获取最后一个节点的位置
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

//返回压缩列表的节点数量
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

//返回压缩列表的表头的字节数
//（内存字节数zlbytes，最后一个节点地址ztail_offset,节点总数量zllength）
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))

//返回压缩列表最后结尾的字节数
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))

//返回压缩列表首节点地址
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)

//返回压缩列表尾节点地址
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))

//返回压缩列表最后结尾的地址
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

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

Давайте посмотрим на код ниже, сосредоточившись на комментариях,Note that this is not how the data is actually encoded, это предложение указывает на то, что это не фактический формат хранения данных.

Не смешно ли, он определяется, но не используется.

Потому что эта структура хранения слишком расточительна. В этой структуре 32-битная машина занимает 25 (5 тип int, каждый int занимает 4 байта, 1 тип char, каждый char занимает 1 байт, 1 тип char*, каждый char* занимает 4 байта байтов, так что всего 5*4+ 1*1+1*4=25) байт, занимая 29 в 64-битной машине (5 типов int, каждое int занимает 4 байта, 1 тип char, каждый char занимает 1 байт, 1 тип char* и каждый char* занимает 8 байт, поэтому всего 5*4+1*1+1*8=29 байт). Это не служит цели сокращения списков.

/* We use this function to receive information about a ziplist entry.
 * Note that this is not how the data is actually encoded, is just what we
 * get filled by a function in order to operate more easily. */
typedef struct zlentry {
    unsigned int prevrawlensize; //记录prevrawlen需要的字节数
    unsigned int prevrawlen;    //记录上个节点的长度
    unsigned int lensize;        //记录len需要的字节数
    unsigned int len;           //记录节点长度
    unsigned int headersize;   //prevrawlensize+lensize 
    unsigned char encoding;   //编码格式
    unsigned char *p;       //具体的数据指针
} zlentry;

Итак, Redis улучшил приведенную выше структуру, абстрактно объединив три параметра.

prev_entry_len:сумма prevrawlensize и prevrawlen.

Если длина предыдущего узла меньше 254 байт, то prev_entry_len представлен одним байтом.

Если длина предыдущего узла больше или равна 254 байтам, то prev_entry_len представлен пятью байтами. Первый байт — константа oxff, а последние четыре бита — длина реального предыдущего узла.

encoding: сумма размера линзы и длины. Redis устанавливает набор определений макросов, чтобы он мог иметь две функции: размер линзы и длину. (спецификация не расширена)

value:конкретные данные.

Преимущества сжатых списков

Недостатки сжатых списков

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

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

Схема процесса обновления цепочки сжатого списка (выделено)

Как упоминалось ранее, каждая запись узла будет иметь поле prevlen для хранения длины предыдущей записи узла.Если содержимое меньше 254, prevlen хранится в одном байте, а если больше 254, оно хранится в пяти байтах. байт. Это означает, что если запись изменится с 253 байтов на 254 байта, поле pervlen ее следующей записи узла будет обновлено с 1 байта до 5 байтов; если длина записи также равна 253 байтам, то поле prevlen следующей записи необходимо продолжать обновлять.

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

所以，发生级联更新的前提是有连续的250-253字节长度的节点。

шаг первый

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

Шаг 2

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

Шаг 3

После корректировки обнаруживается, что длина третьего элемента увеличилась, поэтому поле prevlen четвертого элемента также необходимо модифицировать.

Шаг 4

После корректировки обнаруживается, что длина четвертого элемента увеличилась, поэтому поле prevlen пятого элемента также необходимо модифицировать.

Анализ исходного кода сжатых списков

Создать пустую сжатую таблицу ziplistNew

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

unsigned char *ziplistNew(void) {
    //表头加末端大小
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1;

    //为上面两部分（表头和末端）分配空间
    unsigned char *zl = zmalloc(bytes);

    //初始化表属性
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;

    //设置模块，赋值为常量
    zl[bytes-1] = ZIP_END;

    return zl;
}

Каскадные обновления (выделено)

unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
    size_t offset, noffset, extra;
    unsigned char *np;
    zlentry cur, next;

    //while循环，当到最后一个节点的时候结束循环
    while (p[0] != ZIP_END) {
        //将节点数据保存在cur中
        zipEntry(p, &cur);
        //取前节点长度编码所占字节数，和当前节点长度编码所占字节数，在加上当前节点的value长度
        //rawlen = prev_entry_len + encoding + value
        rawlen = cur.headersize + cur.len;
        rawlensize = zipStorePrevEntryLength(NULL,rawlen);

        //如果没有下一个节点则跳出循环
        if (p[rawlen] == ZIP_END) break;
        //取出后面一个节点放在next中
        zipEntry(p+rawlen, &next);

        //当next的prevrawlen，即保存的上一个节点等于rawlen，说明不需要调整，现在的长度合适
        if (next.prevrawlen == rawlen) break;

        //如果next对前一个节点长度的编码所需的字节数next.prevrawlensize小于上一个节点长度进行编码所需要的长度
        //因此要对next节点的header部分进行扩展，以便能够表示前一个节点的长度
        if (next.prevrawlensize < rawlensize) {
            //记录当前指针的偏移量
            offset = p-zl;
            ///需要扩展的字节数
            extra = rawlensize-next.prevrawlensize;
            //调整压缩列表的空间大小            
            zl = ziplistResize(zl,curlen+extra);
            //还原p指向的位置
            p = zl+offset;

           //next节点的新地址
            np = p+rawlen;
            //记录next节点的偏移量
            noffset = np-zl;

          //更新压缩列表的表头tail_offset成员，如果next节点是尾节点就不用更新
            if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }

           //移动next节点到新地址，为前驱节点cur腾出空间
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);
            //将next节点的header以rawlen长度进行重新编码，更新prevrawlensize和prevrawlen
            zipStorePrevEntryLength(np,rawlen);

            //更新p指针，移动到next节点，处理next的next节点
            p += rawlen;
            //更新压缩列表的总字节数
            curlen += extra;
        } else {
            // 如果需要的内存反而更少了则强制保留现有内存不进行缩小
            // 仅浪费一点内存却省去了大量移动复制操作而且后续增大时也无需再扩展
            if (next.prevrawlensize > rawlensize) {
                zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
            } else {
             
                zipStorePrevEntryLength(p+rawlen,rawlen);
            }

            /* Stop here, as the raw length of "next" has not changed. */
            break;
        }
    }
    return zl;
}

Спасибо всем ❤

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

2. Подпишитесь на официальный аккаунт «Miss Sister Learning Java», чтобы добавить меня в друзья.