[Самая полная серия] Redis-структура статей-список сжатия

Что такое сжатый список

Сжатый список ziplist также широко используется в Redis, это одна из базовых реализаций наших часто используемых структур zset, list и hash. Когда количество элементов нашего объекта-контейнера меньше определенного условия, Redis будет использовать ziplist для хранения, чтобы уменьшить использование памяти.

    > hset test_hash me sidfate
    (integer) 1
    > object encoding test_hash
    "ziplist"

Зачем использовать ziplist, когда элементов меньше?

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

Как ziplist уменьшает использование памяти?

Давайте внимательно посмотрим на исходный код.

структура исходного кода

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

Прежде всего, мы можем понять некоторую основную информацию из комментариев к исходному коду:

ziplist — это специально закодированная структура двустороннего списка для повышения эффективности использования памяти. Он может хранить строковые или целочисленные значения, где целочисленные значения кодируются как фактические целые числа, а не как строки. это может быть вO(1)Нажимайте и открывайте оба конца списка вовремя. Однако, поскольку каждая операция требует перераспределения памяти, используемой ziplist, фактическая сложность связана с объемом памяти, используемой ziplist.

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

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

Атрибуты	количество байтов	значение
zlbytes	4	Количество байтов памяти, занимаемых сжатым списком: используется при перераспределении памяти для сжатого списка или при вычислении позиции zlend.
zltail	4	Смещение конечного узла сжатого списка: используется для обхода сжатого списка в обратном порядке.
zllen	2	Записывается количество узлов, содержащихся в сжатом списке: когда значение этого атрибута меньше UINT16_MAX (65535), значением этого атрибута является количество узлов, содержащихся в сжатом списке; когда это значение равно UINT16_MAX, фактическое количество узлов должно пройти через весь сжатый список до вычисляемого.
entry[]	в ожидании	Массив узлов, содержащий конкретную информацию об элементе
zlend	1	Специальное значение 0xFF (десятичное число 255) используется для обозначения конца упакованного списка.

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

<prevlen> <encoding> <entry-data>

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

prevlen

prevlen представляет длину предыдущего элемента, чтобы иметь возможность перемещаться по списку от конца к началу. Он имеет специальный метод кодирования: если длина меньше 254 байт, он занимает 1 байт, если длина больше или равна 254, он занимает 5 байт, а первый байт устанавливается равным 254 (0xFE), оставшиеся 4 байта принимают в качестве значения длину предыдущей записи. Когда prevlen представлен 5 байтами, это не означает, что длина должна быть больше или равна 254. Это делается для уменьшения realloc и memmove и повышения эффективности.

Почему критическое значение 254? Давайте проведем расчет.Максимальное значение, которое может хранить байт, равно 255. Критическое значение должно быть 255. Не забывайте, что у нас также есть zlend, значение которого равно 0xFF (255).Чтобы избежать путаницы, 254 используется для различения это. .

encoding

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

• |00pppppp| - 1 байт

  Строки с длиной меньше или равной 63 байтам, 63 могут быть представлены 6 байтами, поэтому pppppp представляет фактическую длину строки.

• |01pppppp|qqqqqqqq| - 2 байта

  Строка длиной меньше или равна 16383 байтам (14 бит).

• |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 байт

  Строка длиной более 16383 (14 бит), последние 4 байта представляют длину.

• |11000000| - 3 байта

  11000000 + int16 (2 байта).

• |11010000| - 5 байт

  11010000 + int32 (4 байта).

• |11100000| - 9 bytes

  11010000 + int64 (8 байт).

• |11110000| - 4 bytes

  11110000 + 24-битное целое число со знаком (3 байта).

• |11111110| - 2 bytes

  11110000 + int8 (1 байт).

• |1111xxxx|

  Очень маленькое целое число, диапазон xxxx может быть только (0001~1101), что составляет 1~13, но поскольку все 0000, 1110, 1111 заняты. Прочитанное значение должно вычесть 1 из xxxx, то есть целое число 0~12 является окончательным значением.

• |11111111|

  Указывает конец ziplist, то есть значение zlend равно 0xFF.

Если вы думаете, что это сбивает с толку, не паникуйте, вам не нужно запоминать все вышеперечисленное, я буду использовать свежий каштан (официальный пример), чтобы резюмировать ниже. Ниже приведен сжатый список, содержащий строки «2» и «5»:

[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
      |             |          |       |       |     |
   zlbytes        zltail    zllen     "2"     "5"   end

Первые 4 байта представляют собой число 0x0f = 15 (zlbytes = 15), указывая на то, что этот ziplist занимает всего 15 байт. Следующие 4 байта представляют собой число 0x0c = 12 (zltail = 12), указывающее, что смещение последнего элемента равно 12, что является длиной элемента «5» до начала ziplist. Далее zllen = 2, что означает, что всего 2 элемента. После этого идет запись, которая на самом деле хранит «2» и «5». Объясните, почему «2» — это 00 f3, 00 означает, что предыдущий элемент имеет длину 0, потому что это первый элемент, f3 — это 0x11110011, что является нашим1111xxxxТип кодировки 3 - 1 = 2 - это в точности наша "2", и то же самое верно и для "5". В конце есть окончание ff, обозначающее конец.

Вы заметили, что официальный пример всегда хранит «2» и «5» строки, а Redis хранит ее как целое число? Это на самом деле сделано redis специально.Аналогичная обработка будет выполняться во многих местах.Цель все-таки уменьшить потребление памяти.

Наконец, давайте посмотрим на пример хранения строк.Мы заменим «5» выше на «Hello World», тогда исходная запись «5» станет:

[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]

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