[Изучение исходного кода Redis5] Сжатый список ziplist, 2009-04-17

байюнь Все видео: https://segmentfault. com/a/11…

Зачем вам нужен ziplist

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

Список: 3.2.x-это быстрый список после ziplist + LinkedList
Хэш: ziplist используется, когда данные малы, а хэш-таблица (dict) используется, когда данные большие.
Zset: используйте ziplist, когда данные малы, и skiplist, когда данные большие

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

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

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

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

В ziplist он хранится в соответствии со следующей структурой. Соответствует ли это вашим ожиданиям? Значение каждого поля заключается в следующем:

Байты: 4 байта. Запишите общее количество байтов, занятых сжатым списком, и используйте его при перераспределении сжатого списка в памяти
Хвост Zl: 4 байта. Вы можете быстро найти конец списка с помощью этого поля
Аллен: 2 байта. Запишите, сколько всего записей
Запись: Содержание конкретных данных существует здесь
Смешивание: 1 байт. Для шестнадцатеричного значения 0xFF отметьте конец сжатого списка

Конкретные данные хранятся в записи. В ziplist можно хранить два типа данных:

Строка (массив байтов)
целое число

Например, Zset с небольшим объемом данных будет нажимать имя и значение элемента по От малого до большого Порядок записей в ziplist сохраняется непрерывно: Поэтому возникает вопрос. Когда мы читаем данные, как мы узнаем, следует ли нам читать их так, как мы читаем строки или целые числа? Нам нужно знать тип данных, которые в настоящее время хранятся в поле ввода, поле кодирования, чтобы определить тип текущих данных ввода. Кроме того, когда мы ищем элемент, нам нужно его пересечь. Как мы пройдем по нему в ziplist? Вспомните, как мы проходим массивы:

Обход обычных массивов хранится в массивах тип данных Для поиска следующего элемента, например, массив типа int (также указатель) каждый раз обращается к следующему элементу только со смещением указателя соответствующего типа (если массив представлен индексами, процесс от P [0] до P [1] эквивалентен P + 1*sizeof (int); если используется метод указателя, он может быть представлен P + 1, он также эквивалентен. При p+1*размер(int)

Таким образом, в ziplist мы не знаем ни типа данных, ни длины данных. Как мы перемещаем указатель, используемый для обхода, в обратном направлении? Для этого требуется поле для выполнения задачи. Вот previous_entry_length, который записывает длину предыдущей записи и может быть использован для завершения обхода сжатого списка. Наконец, наиболее важным полем является содержимое поля, в котором хранятся реальные данные. Давайте продолжим со структурой входа, как показано в примере выше.

previous_entry_length Записано в сжатом списке Длина предыдущей записи 。 Занимайте 1 или 5 байт
кодировка Представляет текущую запись сохраненных данных тип И данные длина . Занимают 1, 2 или 5 байт
контент : реальный Данные хранилища Место

Обход зиплиста

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

прямой обход

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

Если длина предыдущей записи меньше 254 байт, previous_entry_length выражается в 1 байте.
Если длина предыдущей записи больше или равна 254 байтам, значение previous_entry_length выражается в 5 байтах. Обратите внимание, что первый байт является фиксированным флагом 0xFE (254), а последние четыре байта используются для указания длины предыдущей записи.

Таким образом, мы можем знать, что, поскольку наш текущий указатель имеет тип без знака char * (см. Исходный код), операция с указателем p + 1 эквивалентна смещению на один байт назад (то есть на восемь битов). Таким образом, вам нужно только прочитать содержимое первого байта текущего указателя, то есть, находится ли значение P [0] в диапазоне от 00000000 до 11111111110 в двоичной системе (то есть от 0 до 254). Если предыдущая длина _entry_length занимает только один байт в этом интервале, первый адрес кодирования может быть получен с помощью p+1; если значение p[0] равно 11111111111 (255), длина former_entry_length занимает пять байтов, и первый адрес кодирования также может быть получен с помощью p+5.
Теперь наш указатель переходит на начальный адрес поля кодирования. Итак, как поля кодирования хранят типы и длины данных? Чтобы сэкономить место в памяти, занимаемое полями кодирования, все типы массивов символов (строк) и целочисленные типы различаются в соответствии со следующими методами кодирования:

Рассматривая кодировку кодирования на рисунке выше, мы обнаруживаем, что длина поля кодирования может быть получена только путем считывания содержимого текущего смещения положения указателя в два раза назад. (00, 11 занимает 1 байт; 01 занимает 2 байта; 10 занимает 5 байт). Затем наши соответствующие P + 1, P + 2, P + 5 могут переместить указатель в положение содержимого.
Поскольку мы знаем длину типа данных поля содержимого в поле кодирования (например, int16 и т. Д.), А затем перемещаем указатель назад перед соответствующей длиной типа данных, хранящегося в поле кодирования, мы можем перейти к концу поля содержимого. Позже, если есть несколько записей одной и той же структуры, верно то же самое, что успешно реализует положительный обход ziplist.

обратный обход

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

Причины преобразования кодирования redis

На самом деле, ziplist относится к идее массива, skiplist относится к идее связанного списка. Независимо от того, перемещаемся ли мы вперед или назад, вставляем или удаляем ziplist, нам нужно переместить назад или вперед следующие элементы. Все операции являются O (n). По сравнению с временной сложностью запроса O (1) в dict + skiplist, другой реализации zset, и сложностью вставки и удаления O (logn), ziplist не имеет преимуществ в эффективности. Но, как мы уже говорили ранее, redis, как правило, предназначен для обмена времени на пространство. Поэтому, по сравнению со skiplist, ему необходимо поддерживать большое количество указателей и повторять данные на нескольких слоях (skiplist занимает 2n места, подробнее см. Примечание), ziplist имеет преимущество в сложности пространства.
Но мы должны сказать, что недостаток ziplist во временной сложности все еще существует, поэтому мы не можем бесконечно увеличивать этот недостаток, но мы должны в полной мере использовать его сильные стороны и избегать его слабых сторон. Поэтому разработчики redis взвешивают и взвешивают это снова и снова. В случае набора z кодирование списка z используется только при соблюдении следующих двух условий, в противном случае используется кодирование списка пропусков:

Количество элементов, сохраненных объектами в наборе, не превышает 128
Длина всех элементов, сохраненных в наборе, составляет менее 64 байт

Таким образом, поскольку ziplist обрабатывает только небольшой объем данных, что делает временную сложность O (n) очень малой, когда ziplist обрабатывает небольшой объем данных. Таким образом, он может свести к минимуму влияние своей временной сложности и максимизировать преимущество своей пространственной сложности, что является основной причиной необходимости преобразования кодирования.

Ключ к ziplist закончился. Что касается конкретного исходного кода, заинтересованные читатели могут перейти в ziplist. C для углубленного осмотра. Для автора не имеет значения копировать и вставлять снова в эту статью. В процессе обучения я читаю много материалов, но качество контента неравномерное. Здесь я хочу сказать, что, когда мы изучаем новое знание, мы должны не только знать, как оно выглядит, но и почему оно такое и почему оно делает это без использования других альтернатив. В чем его сравнительное преимущество? Вместо того, чтобы просто выстраивать концепции. В обучении в то же время, если не через собственное мышление, эффекта мало.