Рубрики
Uncategorized

Прочитайте исходный код с помощью Dabin – Redis 9 – три списка объектного кодирования

Автор оригинала: David Wong.

Radius bottom использует три структуры списков ziplist, skiplist и Quick List для реализации связанных объектов. Как следует из названия, ziplist экономит больше места, skiplist уделяет внимание эффективности поиска и Быстрый список торговых мест и времени.

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

Как вы можете видеть, каждый элемент в связанном списке занимает отдельный фрагмент памяти, и элементы связаны указателями адресов (или ссылками). Этот метод может привести к большой фрагментации памяти, а указатель адреса также занимает дополнительную память. Это общий связанный список. Потеря памяти Проблема.

Кроме того, временная сложность случайного поиска составляет O (n), что неприемлемо для edi, ориентированных на эффективность. Это обычный связанный список. Эффективность поиска слишком низкая Проблема.

Чтобы решить эти две проблемы, Redis design Зиплист 、 Скиплист и Быстрый связанный список Проводится соответствующая оптимизация.

1 лист на молнии

Для ziplist решением является Потеря памяти В чем проблема. То есть, его целью проектирования является В целях экономии места и повышения эффективности хранения 。

Исходя из этого, Redis разработала специальный дизайн, чтобы сделать его специально закодированным. Двусторонний связанный список 。 Каждый элемент в таблице хранится в последовательном адресном пространстве, и почтовый список занимает большой объем памяти в целом. Это список, но это не связанный список.

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

Именно для такого эффективного хранения в ziplist выполняется множество операций на уровне битов, что делает код более неясным и трудным для понимания. Тем не менее, одна из целей этого раздела состоит в том, чтобы Понять, что оптимизация ziplist сделала для экономии места лучше, чем обычные связанные списки 。

Далее давайте формально разберемся в структуре сжатого списка.

Структура сжатого списка 1.1

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

На рис. 1-1 показаны различные компоненты сжатого списка:

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

  • Байты: 4 байта, представляющие общее количество байтов, занятых ziplist (включая четыре байта, занятых самими zlbytes).
  • Zltail: 4 байта, что указывает, сколько байтов составляет начальный адрес последнего списка расстояний в таблице ziplist, то есть смещение узла в конце таблицы. С помощью этого поля программа может быстро определить адрес конечного узла таблицы.
  • Zllen: 2 байта: Представляет количество узлов в ziplist. Обратите внимание, что, поскольку это поле содержит только 16 бит, максимальное выражаемое значение равно 2 ^ 16-1. Как только количество узлов в списке превысит это значение, необходимо просмотреть весь сжатый список, чтобы получить фактическое количество узлов.
  • Запись: Представляет узел ziplist. Длина является переменной, в зависимости от того, что сохраняется. Обратите внимание, что запись в списке также имеет свою собственную структуру данных, которая будет подробно объяснена позже.
  • Конечный тег blend: ziplist с фиксированным значением 255 используется для обозначения конца сжатого списка.

На рис. 1-2 показан сжатый список из пяти узлов:

  • Атрибут zlbytes списка имеет значение 0xd2 (210 десятичных знаков), указывающее, что общая длина сжатого списка составляет 210 байт.
  • Атрибут zltail списка имеет значение 0xb3 (179 десятичных знаков), указывающее, что конечная точка находится на расстоянии 179 байт от начального адреса списка. Если начальный адрес списка равен p, то адрес указателя P +.
  • Значение атрибута list zllen равно 0x5 (десятичное число 5), что указывает на то, что сжатый список содержит пять узлов.

1.2 Структура Узла Списка

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

typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;
    unsigned int lensize, len;
    unsigned int headersize;
    unsigned char encoding;
    unsigned char *p;
} zlentry;

На рис. 1-3 показана структура узла сжатого списка.

  • Превалирующий: Представляет общее количество байтов, занятых предыдущим узлом. Это поле предназначено для того, чтобы ziplist мог перемещаться вперед и назад.
  • Кодировка: В этом поле записывается тип данных, хранящихся в атрибуте содержимого узла.
  • Размер Len: В этом поле записывается длина данных, хранящихся в узле.
  • Размер заголовка: В этом поле записывается размер заголовка узла.
  • * p: В этом поле записывается указатель на содержимое, сохраненное узлом.

Как 1.3 Сжатый Список Экономит Память

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

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

Возьмем в качестве примера рисунок 1-4:

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

  • 3 указателя – занимают 3 байта
  • 2 целых числа – занимают 2 байта
  • Строка содержимого – Занимает 1 байт
  • Конец пустого символьного пространства – занимает 1 байт

Таким образом, для хранения 3 байтов данных требуется не менее 21 байта накладных расходов. Как вы можете видеть, такая эффективность хранения очень низкая.

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

Наконец, детализация операций общего связанного списка с единицей хранения составляет байт, что отнимает много места на байт при хранении меньших целых чисел или строк. Как и в трех вышеперечисленных узлах, он используется для хранения. Целое число оставшихся незанятых байтов Фактическое пространство для хранения требуется всего 1 бит, но для представления размера оставшегося пространства требуется 1 байт. В этом байте оставшиеся 7 бит тратятся впустую.

Итак, как Redis использует ziplist для преобразования обычных связанных списков? С помощью следующих двух аспектов:

С одной стороны, ziplist Использует целый блок непрерывной памяти, чтобы избежать фрагментации памяти и улучшить использование памяти 。

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

2 скиплиста

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

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

Кроме того, мы знаем, что решения проблемы “найти” обычно делятся на две категории: Сбалансированное дерево и Хэш-таблица 。 Интересно, что skiplist-это структура поиска, поскольку ее особенности не относятся к двум категориям, упомянутым выше. Но в большинстве случаев его эффективность сопоставима с эффективностью дерева баланса, а реализация таблицы переходов проще, поэтому многие программы используют таблицу переходов вместо дерева баланса.

В этом разделе не вводится определение и принцип таблицы переходов. Интересующуюся детскую обувь можно посмотреть здесь.

Знайте, что такое таблица переходов и что она делает. Далее давайте рассмотрим, как реализовать таблицу переходов, выделенную красным цветом .

оставайтесь сервер.h Исходный код таблицы переходов можно найти следующим образом:

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

По сравнению с обычным скиплистом, скиплист в Redis не сильно отличается по структуре, но имеет следующие отличия в некоторых деталях:

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

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

Для быстрого списка в quicklist.c Существуют следующие объяснения:

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

Это двунаправленный список и двунаправленный список, состоящий из ziplist.

Соответствующая структура источника доступна в quicklist.h Найдите в следующем:

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 12 bits, free for future use; pads out the remainder of 32 bits */
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;

/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
 * 'sz' is byte length of 'compressed' field.
 * 'compressed' is LZF data with total (compressed) length 'sz'
 * NOTE: uncompressed length is stored in quicklistNode->sz.
 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

/* quicklist is a 32 byte struct (on 64-bit systems) describing a quicklist.
 * 'count' is the number of total entries.
 * 'len' is the number of quicklist nodes.
 * 'compress' is: -1 if compression disabled, otherwise it's the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * 'fill' is the user-requested (or default) fill factor. */
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;

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

Ziplist оптимизирует два пункта по сравнению с общим связанным списком: Сокращение объема оперативной памяти и Уменьшение фрагментации памяти 。 Так называемые вещи всегда имеют две стороны. Ziplist решает проблему фрагментации памяти в общих связанных списках с помощью непрерывной памяти, но в то же время он также создает новые проблемы: Не способствует операциям модификации 。

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

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

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

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

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

список-максимальный-ziplist-размер -2

Этот параметр может быть как положительным, так и отрицательным.

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

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

  • – 1: Размер ziplist на каждом узле быстрого списка не может превышать 4 КБ;
  • – 2: Размер zip-списка на каждом узле быстрого списка не должен превышать 8 КБ (значение по умолчанию);
  • – 3: Размер ziplist на каждом узле быстрого списка не должен превышать 16 КБ.
  • – 4: Размер ziplist на каждом узле быстрого списка не может превышать 32 КБ;
  • – 5: Размер ziplist на каждом узле быстрого списка не должен превышать 64 КБ;

резюме

  1. Есть две проблемы с общими связанными списками: Низкое использование памяти и Склонен к фрагментации памяти 。
  2. Ziplist использует непрерывную память для уменьшения фрагментации памяти и обеспечения использования памяти.
  3. Список пропусков может быть реализован относительно просто для достижения той же эффективности поиска, что и дерево баланса.
  4. Quicklist использует преимущества общего связанного списка и сжатого связанного списка и максимально улучшает использование памяти при условии обеспечения производительности.

Оригинал: “https://developpaper.com/read-the-source-code-with-dabin-redis-9-three-lists-of-object-coding/”

Читайте ещё по теме: