Реализация списка после версии Redis 3.2 — quickList

Redis

Redis quickList

краткий список

  • Объекты списков в Redis До версии 3.2 нижняя кодировка списка была реализована с помощью ziplist и linkedlist, но после версии 3.2 была повторно введена структура данных быстрого списка, а нижний уровень списка был реализован с помощью быстрого списка.

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

Преимущества и недостатки этих двух способов хранения

  • Двусвязный список linkedlist удобен для операций push и pop на обоих концах таблицы, а сложность вставки узлов очень низка, но его накладные расходы на память относительно велики. Во-первых, помимо сохранения данных по каждому узлу, ему также необходимо сохранять два дополнительных указателя, во-вторых, каждый узел двусвязного списка представляет собой отдельный блок памяти, и адреса не являются непрерывными. легко генерировать фрагментацию памяти.
  • Ziplist хранится в непрерывном сегменте памяти, поэтому эффективность хранения очень высока. Однако это не способствует операциям модификации, а операции вставки и удаления требуют частого выделения и освобождения памяти. Особенно, когда длина ziplist очень велика, перераспределение может привести к большому количеству копий данных.

Базовая структура

image-20191218153013717
Базовая структура

конфигурация параметров 

  • list-max-ziplist-size -2

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

    Когда принимается отрицательное значение, это означает, что длина ziplist на каждом узле quicklist ограничена в соответствии с количеством занятых байтов. В настоящее время он может принимать только пять значений от -1 до -5, и значение каждого значения следующее:

  • -5: Размер ziplist на каждом узле quicklist не может превышать 64 Кб. (Примечание: 1 КБ => 1024 байта)

  • -4: размер ziplist на каждом узле быстрого списка не может превышать 32 КБ.

  • -3: размер ziplist на каждом узле быстрого списка не может превышать 16 Кб.

  • -2: Размер ziplist на каждом узле quicklist не может превышать 8 Кб. (-2 — это значение по умолчанию, заданное Redis)

  • -1: Размер ziplist на каждом узле quicklist не может превышать 4 Кб.

  • list-compress-depth 0

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

    параметрlist-compress-depthСмысл значения следующий:

  • 0: это специальное значение, означающее отсутствие сжатия. Это значение по умолчанию для Redis.

  • 1: Указывает, что один узел на обоих концах списка быстрого доступа не сжат, а узлы в середине сжаты.

  • 2: Указывает, что два узла на обоих концах списка быстрого доступа не сжаты, а узлы в середине сжаты.

  • 3: Указывает, что 3 узла на обоих концах списка быстрого доступа не сжаты, а узлы в середине сжаты.

  • Так далее и тому подобное…

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

    Redis использует алгоритм сжатия для внутренних узлов быстрого списка.LZF- Алгоритм сжатия без потерь.

Определение структуры данных быстрого списка 

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned int len;           /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

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

  • prev: Указатель на предыдущий узел связанного списка.
  • next: указатель на следующий узел в связанном списке.
  • zl: указатель данных. Если данные текущего узла не сжаты, они указывают на структуру ziplist, в противном случае — на структуру quicklistLZF.
  • sz: Указывает общий размер ziplist, на который указывает zl (включаяzlbytes, zltail, zllen, zlendи отдельные элементы данных). Следует отметить, что если ziplist сжат, значение sz по-прежнему равно размеру ziplist до сжатия.
  • count: Указывает количество элементов данных, содержащихся в ziplist. Это поле всего 16 бит. Позже мы посчитаем, достаточно ли этих 16 бит.
  • encoding: Указывает, сжат ли ziplist (и какой алгоритм сжатия использовался). В настоящее время есть только два значения: 2 означает сжатие (и использованиеLZFалгоритм сжатия), 1 означает отсутствие сжатия.
  • контейнер: зарезервированное поле. Первоначально он был разработан, чтобы указать, хранит ли узел быстрого списка данные непосредственно, использует ли ziplist для хранения данных или использует другие структуры для хранения данных (используемые в качестве контейнера данных, так называемый контейнер). Однако в текущей реализации это фиксированное значение равное 2, что указывает на использование ziplist в качестве контейнера данных.
  • recompress: когда мы используем такую ​​команду, как lindex, для просмотра определенного элемента изначально сжатых данных, нам нужно временно распаковать данные, затем установить recompress=1, чтобы сделать пометку, а затем повторно сжать данные, когда есть возможность.
  • tryed_compress: это значение полезно только для автоматических тестовых программ Redis. Нас это не волнует.
  • дополнительно: другие поля расширения. Он не используется в текущей реализации Redis.
Категории