Понимание структуры данных, лежащей в основе высокой производительности Redis (1)

предисловие

Как инструмент, используемый многими крупными производителями для решения проблемы параллелизма и быстрого реагирования, многие компании предпочитают Redis из-за его чрезвычайно высокой производительности.Я думаю, что высокая производительность Redis неотделима от проектирования и реализации базовой структуры данных. Учащиеся, которые использовали Redis, могут знать, что Redis имеет пять основных типов данных: строка, список, хэш, набор, zset; это только структуры данных первого уровня, предоставляемые службой Redis клиенту. Фактически внутренняя структура данных по-прежнему имеет реализацию второго уровня, Redis использует один или несколько типов данных второго уровня для реализации типа данных первого уровня. Я думаю, что есть люди, которые так же заинтересованы в базовой структуре данных Redis, как и я, поэтому давайте изучим дизайн и реализацию базовой структуры данных, лежащих в основе высокой производительности Redis.

Здесь мы в основном изучаем реализацию структуры данных второго уровня.Пять основных типов данных в Redis реализованы через следующие структуры данных.Давайте рассмотрим их по порядку:

sds
ziplist
quicklist
dict
skiplist

1. Динамические строки (SDS)

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

Динамически расширяемая память. Строка, представленная sds, может быть динамически расширена. Поскольку строка языка C не записывает собственную длину, при изменении длины строки необходимо перераспределить память для новой строки.Если память не выделена, может произойти переполнение. Однако SDS не нужно вручную изменять размер памяти, и не будет проблемы с переполнением буфера, поскольку SDS сам запишет размер хранимых данных и максимальную емкость и автоматически расширится при превышении емкости.
Бинарный сейф. sds может хранить произвольные двоичные данные, не только строки, но и двоичные данные, такие как аудио, изображения и сжатые файлы. API-интерфейс SDS будет обрабатывать данные, хранящиеся в массиве buf, в двоичном виде и не будет накладывать никаких ограничений на данные.
Кроме того, sds также совместим с символьным типом языка C.

Ниже приведена часть исходного кода SDS в Redis.исходный код сдс

typedef char *sds;
/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

На самом деле, мы можем узнать через исходный кодsds, мы обнаружили, что sds определяется как тип char. Является ли базовый тип String в Redis типом char? На самом деле, чтобы поддерживать совместимость типов с традиционными строками языка C, sds имеют то же определение типа, что и char *, но sds не эквивалентны char.

Реальные данные хранятся вsdshdrсерединаbufПомимо хранения строк, эта структура данных также может хранить двоичные данные, такие как изображения и видео. Чтобы быть совместимым со строками языка C, SDS следует соглашению о том, что строки языка C заканчиваются нулевым символом, поэтому вbuf, пользовательские данные всегда сопровождаются\0То есть "данные" + "\0" на рисунке - это т.н.buf. Кроме того, обратите внимание, что существует пять типов sdshdr.На самом деле sdshdr5 не используется, а используются только четыре. Определено так много заголовков типов, что строки различной длины могут использовать заголовки разных размеров. Это позволяет коротким строкам использовать меньшие заголовки, экономя память.

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

За исключением sdshdr5, остальные 4 структуры заголовка содержат 3 поля.

len: указывает истинную длину строки (исключая\0терминатор).
alloc: указывает максимальную емкость всего SDS (исключая\0байт).
flags: всегда занимает один байт. Младшие 3 бита используются для указания типа заголовка. Типов заголовков 5, а используются только 4. В sds.h есть определения констант.

2. список список

2.1 Базовая структура данных

То, что Redis предоставляет внешнему миру,listТип данных, на самом деле существует несколько внутренних структур данных, от которых зависит его базовая реализация.До Redis 3.2 базовая реализация связанного списка былаlinkedListа такжеzipList, но после версии 3.2linkedListа такжеzipListв основном устарел, используйтеquickListВ качестве базовой реализации связанных списков, хотя ziplist заменен quicklist, ziplist по-прежнему является одной из базовых реализаций hash и zset.

2.2 Сжатый связанный список zipList в двусвязный список linkedList

Здесь мы используем версию Redis 2.8, чтобы увидеть, что когда я вставляю 110 относительно коротких фрагментов данных в ключ k5, список представляет собой кодировку ziplist, а когда я вставляю в него 10 000 фрагментов данных, кодировка данных k5 становится связанным списком.

До Redis 3.2,listНижний слой используется по умолчаниюzipListКак узел данных по умолчанию внизу списка, при определенных условияхzipListпревратится вlinkedList. Причина, по которой Redis спроектирован таким образом, заключается в том, что двусвязный список занимает больше памяти, чем сжатый список, поэтому при создании нового ключа списка список будет отдавать приоритет использованию сжатого списка и конвертировать только из сжатого списка. к двустороннему, когда это необходимо Реализация связанного списка. при каких условияхzipListпревратится вlinkedList, должны быть выполнены следующие два произвольных условия:

Длина этой строки превышает server.list_max_ziplist_value (по умолчанию 64).
ziplist содержит больше узлов, чем server.list_max_ziplist_entries (по умолчанию 512).

Эти два условия можно изменить в redis.conf:

list-max-ziplist-value 64 
list-max-ziplist-entries 512

Примечание. Перечисленную здесь конфигурацию списка можно найти только в конфигурации до Redis 3.2, поскольку Redis 3.2 и более поздние версии удалили эту конфигурацию, поскольку базовая реализация не использует ziplist, а использует quicklist в качестве реализации по умолчанию.

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

Когда данные записи связанного списка превышают 512 или длина одного значения превышает 64, нижний уровень преобразует zipList в кодировку связанного списка. Связанный список представляет собой стандартный двусвязный список. Узел Node содержит указатели prev и next, которые могут перемещаться в обоих направлениях, голова и хвост также сохраняются два указателя. Таким образом, временная сложность вставки начала и конца связанного списка составляет O (1), что также является ключом к эффективной реализации таких команд, как LPUSH, RPOP и RPOPLPUSH.

2.4 Сжатый список zipList

Хотя версия Redis 3.2 больше не использует ziplist напрямую для реализации построения списка, нижний уровень по-прежнему косвенно использует ziplist.

Сжатый список разработан Redis для экономии памяти.Официальное определение Redis для ziplist (Из src/ziplist.c в исходном коде RedisПримечания):

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values,where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist

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

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

2.4.1 Структура данных сжатого списка

ziplist — это специальный двусвязный список, ziplist не поддерживает двусторонний указатель: prev next; вместо этого он сохраняет длину предыдущей записи и длину текущей записи и вычисляет, где находится следующий элемент на основе длины, жертвуя производительностью чтения и получение эффективного места для хранения, что типично для «Time for Space».

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

Что представляет каждое поле.

zlbytes: 32 бита, указывающее общее количество байтов, занимаемых ziplist (включаяzlbytes4 байта занято собой).
zltail: 32 бита, указывающее количество байтов смещения в ziplist последней записи в таблице ziplist.zltailСуществование , упрощает поиск последнего элемента (без обхода всего ziplist), так что мы можем быстро выполнять операции push или pop в конце ziplist.
zllen: 16 бит, указывающее количество элементов данных (записей) в ziplist. Поскольку поле zllen имеет только 16 бит, максимальное значение, которое может быть выражено, равно 2^16-1. Здесь следует отметить, что если количество элементов данных в ziplist превышает максимальное значение, которое может быть выражено 16 битами, ziplist все равно может быть представлен. Что это значит? Вот правило: еслиzllenМеньше или равно 2^16-2 (то есть не равно 2^16-1), тогдаzllenОн представляет количество элементов данных в ziplist; в противном случае этоzllenЭто равносильно случаю, когда все 16 бит равны 1, тогдаzllenОн не указывает количество элементов данных.В настоящее время, если вы хотите узнать общее количество элементов данных в ziplist, вы должны пройти каждый элемент данных от начала до конца ziplist, чтобы подсчитать их.
entry: Указывает элемент данных, который фактически хранит данные, длина не определена. Элемент данных (запись) также имеет свою внутреннюю структуру.
zlend: последний байт ziplist является конечным маркером, а значение фиксировано и равно 255.

2.4.2 Структура записи узла zipList

Каждый узел хранения в ziplist является zlentry.Исходный код zlentry находится в строке 268 файла ziplist.c.

/* 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; /* prevrawlensize是指prevrawlen的大小，有1字节和5字节两种*/
    unsigned int prevrawlen;     /* 前一个节点的长度 */
    unsigned int lensize;        /* lensize为编码len所需的字节大小*/
    unsigned int len;            /* len为当前节点长度*/
    unsigned int headersize;     /* 当前节点的header大小 */
    unsigned char encoding;      /*节点的编码方式：ZIP_STR_* or ZIP_INT_* */
    unsigned char *p;            /* 指向节点的指针 */
} zlentry;

prevrawlen: запись количества байтов памяти, занимаемых предыдущим узлом, через это значение мы можем вычислить адрес предыдущего узла из текущего узла, который можно использовать для перехода от конца таблицы к головному узлу; код переменной длины, есть два способа выразить
- Если длина предыдущего узла меньше 254 байт, используйте 1 байт (uint8_t) для хранения преображенного;
- Если длина предыдущего узла больше или равна 254 байтам, установите значение первого байта равным 254, а затем используйте следующие 4 байта для хранения фактической длины.
len/encoding: записывает количество байтов памяти, занимаемых текущим содержимым узла, и тип его хранения, который используется для разбора содержимого;
содержимое: сохраняет значение текущего узла. Наиболее важным является prevrawlen и len/encoding, контент — это просто биты, которые фактически хранят значение.

2.4.3 Почему zipList может сжимать данные

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

2.4.4 Почему zipList был заброшен

Благодаря структуре данных ziplist, которую мы ясно поняли выше, каждый zlentry в ziplist хранит количество байтов, занятых предыдущим узлом, и это значение является переменным, такая структура данных может вызвать ziplist.连锁更新. Предположим, у нас есть сжатый связанный список entry1 entry2 entry3 ......, длина entry1 ровно 253 байта, тогда согласно тому, что мы сказали выше, entry2.prevrawlen записывает длину entry1, используем1 байтЧтобы сохранить размер элемента entry1, если новый узел new_entry теперь вставляется между entry1 и entry2, а размер new_entry равен ровно 254, то entry2.prevrawlen необходимо расширить до5 байт;Если изменяется общая длина элемента entry2 и длина хранения элемента entry3.prevrawlen, обновление цепочки до конечного узла или prevrawlen определенного узла достаточно для сохранения длины предыдущего узла.Конечно, удаление узла также то же самое, пока наша эта цепочка обновления происходит, когда prevrawlen после изменения рабочего узла.

Из-за проблемы обновления цепочки ziplist преимущества и недостатки ziplist предельно очевидны; ziplist предназначен для экономии памяти, а эта структура плохо подходит для модификации операций. Как только данные будут изменены, это вызовет перераспределение памяти, что может привести к копированию памяти. Это также заставляет следующий Redis пойти на компромисс и заменить ziplist на quicklist.

2.5 Быстрый список

Основываясь на вышеизложенном, мы уже знаем дефекты ziplist, поэтому после версии Redis 3.2 базовая реализация списка по умолчанию использует quicklist вместо ziplist и linkedlist? Далее давайте посмотрим, какова структура данных быстрого списка, почему мы используем быстрый список в качестве базовой реализации списка Redis и каковы его преимущества по сравнению с ziplist.Далее давайте посмотрим на конкретную реализацию быстрого списка. Ниже показано, что я сделал на основе версии Redis 3.2.Здесь мы видим, что базовая реализация списка по умолчаниюquicklistКодировка объекта.

2.5.1 структура данных быстрого списка

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

исходный код быстрого спискаredis/src/quicklist.hСтруктура определяется следующим образом:

typedef struct quicklist {
    quicklistNode *head;  // 头结点
    quicklistNode *tail; // 尾结点 
    unsigned long count; // 所有ziplist数据项的个数总和
    unsigned long len;   //quicklistNode的节点个数
    int fill : QL_FILL_BITS;   //ziplist大小设置，通过配置文件中list-max-ziplist-size参数设置的值。
    unsigned int compress : QL_COMP_BITS; //节点压缩深度设置，通过配置文件list-compress-depth参数设置的值。
    unsigned int bookmark_count: QL_BM_BITS; 
    quicklistBookmark bookmarks[];
} quicklist;

На самом деле, даже если структура quicklist используется вместо ziplist, quicklist также имеет определенные недостатки.Нижний слой по-прежнему использует ziplist, что также имеет проблему, потому что ziplist является непрерывным адресом памяти, если ziplist слишком маленький, это приведет к большой фрагментации диска, что снизит эффективность хранения.Если ziplist большой, будет сложнее выделить смежные большие блоки памяти, что также снизит эффективность хранения. Как сбалансировать размер ziplist? Далее это будет зависеть от сценария использования, Redis предоставляет параметр конфигурацииlist-max-ziplist-sizeZiplist может быть изменен.

Когда принимается положительное значение, это означает, что длина 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 Кб.

Когда у нас есть большой объем данных, наиболее удобными для доступа являются данные в начале и в конце очереди (временная сложность O(1)), а к данным в середине обращаются реже (и производительность доступа также низкая). , временная сложность O (N). Если ваш сценарий использования соответствует этой функции, Redis предоставляетlist-compress-depthЭта конфигурация может сжимать промежуточные узлы данных. Алгоритм сжатия внутренних узлов списка быстрого доступа с использованиемLZF- Алгоритм сжатия без потерь.

Этот параметр указывает количество несжатых узлов на обоих концах списка быстрого доступа. параметрlist-compress-depthСмысл значения следующий:

0: это специальное значение, означающее отсутствие сжатия. Это значение по умолчанию для Redis.
1: Указывает, что один узел на обоих концах списка быстрого доступа не сжат, а узлы в середине сжаты.
2: Указывает, что два узла на обоих концах списка быстрого доступа не сжаты, а узлы в середине сжаты.
3: Указывает, что 3 узла на обоих концах списка быстрого доступа не сжаты, а узлы в середине сжаты.
Так далее и тому подобное

2.5.2 структура quicklistNode

quicklist состоит из двусвязного списка узлов quicklistNodes.

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; 
    char compressed[];
} quicklistLZF;

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

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

Структура быстрого списка сочетает в себе преимущества ziplist и связанного списка. Быстрый список взвешивает потребление времени и места и в значительной степени оптимизирует производительность. Поскольку временная сложность операций быстрого списка в начале и в конце очереди составляет O (1), Список Redis также может использоваться очередями действий.

3. Словарь

Из приведенного выше рисунка видно, что базовая структура данных по умолчанию для хеш-ключа — ziplist.По мере увеличения количества хэш-ключей структура данных становится хэш-табличной.Хотя формат кодирования объекта, который мы видим здесь, является хэш-таблицей, но нижний слой Redis использует словарь dict для завершения базовой структуры данных ключа Hash, но базовая реализация словаря dict реализована с использованием хеш-таблицы. Для клиента тип сервиса Redis, открытый внешнему миру, — это хэш, и есть две реализации базовой структуры данных: один — это сжатый список (ziplist), а другой — словарь (dict); о ziplist мы in Я уже говорил это, когда говорил о списке, поэтому не буду повторяться здесь. Здесь мы сосредоточимся на конкретной реализации словаря (dict).

Здесь нужно сказать, при каких обстоятельствахziplistПревратиться вhashtableШерстяная ткань? Два параметра предоставлены в redis.conf

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

Указывает, что когда количество элементов (полей, значений), соответствующих ключу в хеш-ключе, превышает 512, он преобразуется в словарь.
Указывает, что когда длина значения, соответствующего ключу в хеш-ключе, превышает 64, оно преобразуется в словарь.

3.1 Реализация словаря (dict)

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

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

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

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

Из приведенного выше рисунка и исходного кода ясно видно, что состав словаря dict состоит из следующих элементов:

ДикТип:Указатель (тип) на структуру dictType, которая позволяет ключам и значениям dict хранить данные любого типа произвольным образом.
личная дата:Частный указатель, переданный вызывающей стороной при создании dict.
[2]:Массив хеш-таблиц, размер массива равен 2. И ht[0], и ht[1] допустимы только во время процесса перефразирования. При нормальных обстоятельствах допустим только ht[0], а в ht[1] нет данных.
рехашидекс:Текущий индекс перефразирования (rehashidx). Если rehashidx = -1, это означает, что процесс повторного хеширования в данный момент не выполняется; в противном случае это означает, что в данный момент выполняется повторное хеширование, и его значение записывает текущий шаг повторного хеширования.
итераторы:Количество итераторов, проходимых в данный момент.

Самое важное здесь — это структура dicttht, которая определяет хэш-таблицу, структура которой состоит из следующего:

dictEntry: массив указателей dictEntry (таблица). Наконец, хеш-значение ключа сопоставляется с определенной позицией в этом массиве (соответствующей корзине). Если несколько ключей сопоставляются с одним и тем же расположением, возникает конфликт, после чего извлекается связанный список dictEntry. Студенты, знакомые с Java, могут здесь подумать о HashMap, который на самом деле чем-то похож на реализацию HashMap.
size: определяет длину массива указателей dictEntry. Это всегда показатель степени 2.
sizemask: индекс местоположения, используемый для сопоставления хеш-значения с таблицей. Его значение равно (size-1), что является нижним индексом массива. Это фактически то же самое, что и метод вычисления индекса в HashMap.
used: Запишите количество существующих данных в dict. Отношение его к размеру является коэффициентом нагрузки. Чем больше отношение, тем выше вероятность столкновения хеш-значений.

3.2 Как перефразировать dict в Redis

В целом немного похоже на реализацию HashMap в Java, размер HashMap в обработке хеш-коллизий и массивов такой же, как и у HashMap в Java, но здесь есть разница, речь идет о механизме расширения. , Redis использует две хэш-таблицы, а еще одна хеш-таблица используется для расширения. Словарь в Redis такой же, как и HashMap в Java.Чтобы обеспечить эффективность запроса при увеличении количества данных, размер массива следует корректировать соответствующим образом, то есть перехэшировать, что нам знакомо с расширением . Мы не будем здесь говорить о расширении HashMap в Java, здесь мы в основном рассмотрим расширение словарей в Redis.

Так когда его переделают? условие:

1. 服务器目前没有执行的BGSAVE命令或者BGREWRUTEAOF命令，并且哈希表的负载因子大于等于1；
2. 服务器目前正在执行BGSAVE命令或者BGREWRUTEAOF命令，并且哈希表的负载因子大于等于5；

Итак, как именно происходит перехеширование?Согласно приведенному выше исходному коду и диаграмме структуры данных, мы видим, что в словаре определен массив хэш-таблицы размером 2. Как мы упоминали ранее, когда не выполняется расширение, все данные Хранящаяся в первой хеш-таблице вторая хеш-таблица будет использоваться только при расширении. Когда необходимо выполнить повторное хеширование, установите размер хеш-таблицы dicttht[1] на размер, который необходимо расширить, а затем повторно хэшируйте все данные в dicttht[0] на dicttht[1]. большой объем, повторное хеширование не потребляет слишком много производительности сервера.Он принимает прогрессивное повторное хэширование.Когда объем данных мал, мы повторно хэшируем данные в расширенную хеш-таблицу за один раз.Производительность службы Redis можно игнорировать, но когда количество хэш-ключей в Redis велико, сотни тысяч или даже миллионы данных, влияние повторного хеширования на Redis огромно и даже приводит к тому, что Redis прекращает обслуживание на определенный период времени, что неприемлемо.

Когда сервису Redis требуется повторное хеширование, оно не выполняет повторное хеширование всех данных в dicttht[0] в dicttht[1] за один раз, а перехеширует данные пакетами, в свою очередь, в хэш-таблицу dicttht[1]. Это идея «разделяй и властвуй», которая позволяет избежать огромного объема вычислений, вызванных централизованным повторным хэшированием, даже когда объем данных велик. Во время перехеширования, добавления, удаления, модификации и проверки словаря будут работать две хеш-таблицы, потому что при перехешировании данные есть в обеих хеш-таблицах, когда мы не можем найти данные в одной хеш-таблице, так же уйдут в другой хэш таблицу для поиска данных. Новое добавление во время повторного хеширования не будет добавлено в первую хэш-таблицу, а вновь добавленные данные будут сохранены непосредственно во второй хеш-таблице, чтобы гарантировать, что данные в первой хеш-таблице только уменьшаются. данные пусты, чтобы закончить перефразирование.

Студенты, знакомые с Java, могут подумать об алгоритме расширения в HashMap.На самом деле, есть много общего в дизайне емкости и внутренней структуре.Заинтересованные студенты могут узнать об этом или обратиться к этой статье, которую я написал.«Работа HashMap в Java 1.8», По сравнению с методом перефразирования словаря в Redis, я предпочитаю способ тонкого перефразирования в HashMap в Java, и его идеи по-прежнему очень достойны нашего упоминания.