English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Введение
Сжатый список (ziplist) состоит из ряда специальных закодированных блоков памяти и играет очень важную роль в оптимизации хранения данных Redis. В этой статье я кратко рассмотрю одну из часто используемых структур данных Redis - сжатый список ziplist. Эта структура данных в Redis можно сказать无处不在, кроме списка, многие другие структуры данных также используются для перехода, например, SortedSet, о котором упоминалось в предыдущей статье. Не будем более задерживаться, давайте посмотрим на подробное описание.
Введение в структуру данных сжатого списка ziplist
Сначала рассмотрим структуру ziplist в целом, как показано на следующем рисунке:
Схема структуры сжатого списка ziplist
Как видно, есть много полей, и размер байтов也不同, но это и есть суть сжатого списка, и мы будем их по порядку обобщать.
| Поле | Значение |
|---|---|
| zlbytes | Это поле является первым полем сжатого списка, это несigned integer, занимающий четыре байта. Используется для отображения занимаемого всего сжатого списка объема байт (включая самого себя). |
| zltail | Несigned integer, занимающий четыре байта. Используется для хранения смещения от начала сжатого списка到最后 одного entry (не элемент zlend), что используется для быстрого перехода к концу списка. |
| zllen | Несigned integer, занимающий два байта. Используется для хранения总数 entry, содержащихся в сжатом списке. |
| zlend | Специальный entry, используемый для представления конца сжатого списка. Занимает один байт и его значение всегда равно 255. |
Обобщение в heads и tails ziplist, далее кратко рассмотрим важный полей entry.
В общем, entry состоит из трех полей: prevlen, encoding и entry-data, но когда entry является очень маленьким целым числом, поле entry-data может быть опущено в зависимости от кодирования. Ниже приведен их последовательный обзор:
首先是字段prevlen：表示前一个entry的长度，有两种编码方式。
然后是字段encoding：它会根据当前元素内容的不同会采用不同的编码方式，如下：
1、如果元素内容为字符串，encoding的值分别为：
00xx xxxx ：00开头表示该字符串的长度用6个bit表示。
01xx xxxx | xxxx xxxx ：01开头表示字符串的长度由14bit表示，这14个bit采用大端存储。
1000 0000 | xxxx xxxx | xxxx xxxx | xxxx xxxx | xxxx xxxx ：10开头表示后续的四个字节为字符串长度，这32个bit采用大端存储。
2、如果元素内容为数字，encoding的值分别为：
1100 0000：表示数字占用后面2个字节。
1101 0000：表示数字占用后面4个字节。
1110 0000：表示数字占用后面8个字节。
1111 0000 ：表示数字占用后面3个字节。
1111 1110 ：表示数字占用后面1个字节。
1111 1111 ：表示压缩链表中最后一个元素（特殊编码）。
1111 xxxx ：表示只用后4位表示0~12的整数，由于0000，1110跟1111三种已经被占用，也就是说这里的xxxx四位只能表示0001~1101，转换成十进制就是数字1~13，但是redis规定它用来表示0~12，因此当遇到这个编码时，我们需要取出后四位然后减1来得到正确的值。
最后是字段entry-data：如果元素的值为字符串，则保存元素本身的值。如果元素的值为很小的数字（按上面编码规则即0~12），则没有该字段。
压缩链表的编码非常复杂，但这也正是该数据结构的精髓所在，一起来看一个例子吧：
注：这个例子是redis源码中提到的
//由元素2，5组成的压缩链表 [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] | | | | | | zlbytes zltail entries "2" "5" end //Содержимое кодированной строки "Hello World" [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
Выше приведен отрезок, представляющий сжатую链ку, состоящую из элементов 2 и 5 в шестнадцатеричном формате.
Далее мы вставляем строковый элемент "Hello World" в конец этой сжатой链ки. Давайте сначала посмотрим, как кодировать эту строку. В соответствии с约定的 кодировкой, сначала нужно использовать байты для представления длины предыдущего элемента. Здесь предыдущий элемент составляет 5, что занимает два байта, поэтому сначала используется один байт для представления длины предыдущего элемента 02,接下来 идет кодирование строки. Длина строки, которую мы хотим добавить, составляет 11 (пробел также учитывается), преобразованная в двоичную систему - это 1011, в соответствии с правилами кодирования строки, мы используем 0000 1011, преобразованная в шестнадцатеричную систему - это 0b, а затем добавляем нам саму строку ASCII. В совокупности мы получаем кодирование строки: [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64].
В этот момент вся сжатая链ка становится:
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 0b 48 65 6c 6c 6f 20 57 6f 72 6c 64] [ff] | | | | | | | zlbytes zltail entries "2" "5" "Hello World" end
Secondly, the source code analysis of the ziplist command for compressed lists
After understanding the above encoding rules, let's take a look at the source code of some operations on the compressed list ziplist. This article summarizes the basic principles of the compressed list through the creation, insertion, deletion, and search of elements.
Firstly, let's look at the creation:
// Define the header size of the compressed list composed of zlbytes, zltail, and zllen
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
// Create a compressed list and return a pointer to the list
unsigned char *ziplistNew(void) {
// The reason for +1 is that the tail element occupies one byte, which is also the minimum size of a compressed list
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
// Allocate memory
unsigned char *zl = zmalloc(bytes);
// Set the size of the list
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
// Set the offset of the last element
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
// Set the number of elements
ZIPLIST_LENGTH(zl) = 0;
// Set the tail element (above is just to apply space)
zl[bytes-1] = ZIP_END;
return zl;
}
The logic for creating a compressed list is very simple, just apply a fixed space containing the head and tail nodes, and then initialize the list context.
Compared to creation, the source code for adding elements is very long. In order to facilitate understanding, let's sort out the logic of adding elements before looking at the source code.
Upper three steps are the core steps, the rest include updating the tail node offset, modifying the number of elements in the list, and other operations. Of course, since the compressed list is implemented based on an array, memory copying is also indispensable when inserting or deleting elements.
Суммируя上面的 шаги, мы начинаем постепенно анализировать исходный код, это долго, медленно смотрите:
//四个参数依次是：压缩链表，插入位置（新元素插入p元素后面），元素值，元素长度
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
//这里是保存当前链表的长度
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned int prevlensize, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789;
zlentry tail;
//1. 这段逻辑目的就是获取前置元素的长度
if (p[0] != ZIP_END) {
//如果插入位置的元素不是尾元素,则获取该元素的长度
//这里为了后面使用方便进行了拆分，prevlensize保存encoding字段的长度，prevlen保存元素本身的长度
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
//如果插入位置的元素是尾元素，那么需要把新元素插入链表尾端
//获取到链表最后一个元素（注：最后一个元素不等于尾元素）
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
//如果最后一个元素不是尾元素，则该元素为新元素的前置元素，获取该元素长度
prevlen = zipRawEntryLength(ptail);
}
//否则说明链表还没有任何元素，即新元素的前置元素长度为0
}
//2. 对新元素进行编码，获取新元素的总大小
if (zipTryEncoding(s,slen,&value,&encoding)) {
//如果是数字，则按数字进行编码
reqlen = zipIntSize(encoding);
} else {
//元素长度即为字符串长度
reqlen = slen;
}
//Общее значение длины нового элемента составляет длина значения плюс длина前置 элемента и элемента encoding
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
//Если положение вставки не в конце списка,则需要 проверить поле prevlen элементов после нового элемента
//Согласно上面的 правилам кодирования, это поле может потребовать расширения
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {
nextdiff = 0;
forcelarge = 1;
}
//По новому рассчитанному размеру массива производиться расширение, так как адрес нового массива может измениться, поэтому здесь записывается старое смещение
offset = p - zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
//На новом массиве вычисляется положение вставки
p = zl + offset;
//Если вставленный элемент не в конце списка
if (p[0] != ZIP_END) {
//Копирование следующего элемента нового элемента в новый массив, -1 для элемента конца
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
//Prevlen поля следующего элемента нового элемента
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
//Обновление смещения последнего элемента
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
//Когда следующий элемент нового элемента не содержит одного элемента, новый смещение конца элемента нужно добавить nextdiff
zipEntry(p+reqlen, &tail);
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)) + nextdiff);
}
} else {
//Новый элемент вставляется в конец списка, обновляется смещение конца
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
//nextdiff != 0 означает, что изменился размер последующего элемента, поэтому нам нужно выполнить каскадное обновление для последующих элементов элемента
if (nextdiff != 0) {
offset = p - zl;
zl = __ziplistCascadeUpdate(zl, p + reqlen);
p = zl + offset;
}
//Запись нового элемента в список
p += zipStorePrevEntryLength(p, prevlen);
p += zipStoreEntryEncoding(p, encoding, slen);
if (ZIP_IS_STR(encoding)) {
memcpy(p, s, slen);
} else {
zipSaveInteger(p, value, encoding);
}
//Увеличение количества элементов в сжатом списке на 1
ZIPLIST_INCR_LENGTH(zl, 1);
return zl;
}
После анализа логики вставки глубоко вздохнув, действительно, это долго, и деталей много.
Далее рассмотрим процесс удаления элементов, по сравнению с добавлением, удаление несколько проще, после очистки текущего элемента, необходимо копировать последующие элементы по одному (это и различие между массивами и списками), затем注意, нужно ли выполнять каскадное обновление, см. следующий код:
//Параметры по порядку: сжатый список, начальное положение удаляемого элемента, количество удаляемых элементов
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
unsigned int i, totlen, deleted = 0;
size_t offset;
int nextdiff = 0;
zlentry first, tail;
//Чтение элемента, указанного p, и сохранение его в first
zipEntry(p, &first);
for (i = 0; p[0] != ZIP_END && i < num; i++) {
//Счет общей длины удаленного
p += zipRawEntryLength(p);
//Счет фактического количества удаленных элементов
deleted++;
}
//Количество байт для удаления элемента
totlen = p - first.p;
if (totlen > 0) {
if (p[0] != ZIP_END) {
//Определение изменилось ли размер элемента
nextdiff = zipPrevLenByteDiff(p, first.prevrawlen);
//Изменение поля prevlen элементов после удаленного элемента
p -= nextdiff;
zipStorePrevEntryLength(p, first.prevrawlen);
//Обновление смещения последнего элемента
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)) - totlen);
//При удалении элемента, у которого есть только один последующий элемент, смещение нового последнего элемента необходимо увеличить на nextdiff
zipEntry(p, &tail);
if (p[tail.headersize + tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)) + nextdiff);
}
//Перемещение оставшихся элементов вперед
memmove(first.p, p,
intrev32ifbe(ZIPLIST_BYTES(zl)) - (p - zl) - 1);
} else {
//Прямое удаление до конца списка, поэтому не требуется копирование памяти, достаточно изменить смещение последнего элемента
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p - zl) - first.prevrawlen);
}
//Изменение размера массива
offset = first.p - zl;
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl)) - totlen + nextdiff);
//Изменение количества элементов списка
ZIPLIST_INCR_LENGTH(zl, -deleted);
p = zl + offset;
//nextdiff != 0 означает, что размер элемента изменился, и необходимо выполнить каскадное обновление
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl, p);
}
return zl;
}
Наконец, посмотрим на операцию поиска элементов:
//Параметры следуют в порядке: сжатый список, значение элемента, длина элемента, количество элементов, пропускаемых при сравнении
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
int skipcnt = 0;
unsigned char vencoding = 0;
long long vll = 0;
//只要还没到尾元素就不断循环
while (p[0] != ZIP_END) {
unsigned int prevlensize, encoding, lensize, len;
unsigned char *q;
//查询链表当前元素的prevlen字段
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
//查询链表当前元素的encoding字段
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
q = p + prevlensize + lensize;
//已到达需要比较的元素位置
if (skipcnt == 0) {
//如果链表中的当前元素时字符串
if (ZIP_IS_STR(encoding)) {
//跟要查找的字符串进行比较
if (len == vlen && memcmp(q, vstr, vlen) == 0) {
//匹配成功，则要查找元素的指针
возврат p;
}
} else {
//如果当前元素为数字且vencoding为0
if (vencoding == 0) {
//尝试对要查找的值进行数字编码
if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
//如果编码失败，则说明要查找的元素根本不是数字
//然后把vencoding设置为最大值，起一个标记作用
//也就是说后面就不用尝试把要查找的值编码成数字了
vencoding = UCHAR_MAX;
}
assert(vencoding);
}
//如果vencoding != UCHAR_MAX，则说明要查找的元素成功编码为数字
if (vencoding != UCHAR_MAX) {
//按数字取出当前链表中的元素
long long ll = zipLoadInteger(q, encoding);
if (ll == vll) {
//Если два числа равны, то вернем указатель на элемент
возврат p;
}
}
}
//Перезаписать количество элементов, которые нужно пропустить
skipcnt = skip;
} else {
//Пропустить элемент
skipcnt--;
}
//Пробежимся по следующему элементу
p = q + len;
}
//Пробежались по всему списку, элемент не найден
возврат NULL;
}
До этого момента были завершены основные операции создания, добавления, удаления и поиска сжатого списка ziplist.
Третья часть: Обобщение структуры данных сжатого списка ziplist
Компрессия списка ziplist广泛应用于redis, это можно считать одним из самых характерных структур данных redis. Суть этой структуры данных заключается в правилах кодирования, которые были подведены в первой части статьи, сначала нужно понять这部分内容, а затем можно просто просмотреть код для лучшего понимания.
不得不说源码部分确实有点冗长，确实需要耐心，我自己在读的过程中也很头大。如果对源码感兴趣的话，建议按我的方法，先自己梳理某个操作（例如上面提到的插入元素）需要做哪些事情，然后再看代码可能会更好理解一些。
В конце оставим один маленький вопрос,既然redis中的ziplist так эффективно использует память, то почему все еще предоставляется обычная структура списка для использования пользователями?
Этот вопрос не имеет стандартного ответа, каждый видит по-своему ~
Обобщение
Вот и все, что есть в этой статье, надеюсь, что содержимое статьи будет иметь определенную ценность для вашего обучения или работы. Если у вас есть вопросы, пожалуйста, оставляйте комментарии для обсуждения, спасибо за поддержку呐喊教程。
Заявление: содержимое этой статьи взято из Интернета, авторские права принадлежат соответствующему автору. Контент предоставлен пользователями Интернета, самостоятельно загружен, сайт не имеет права собственности, не был обработан вручную и не несет ответственности за соответствующие юридические последствия. Если вы обнаружите подозрительное нарушение авторских прав, пожалуйста, отправьте письмо по адресу: notice#oldtoolbag.com (во время отправки письма замените # на @) для сообщения о нарушении и предоставьте соответствующие доказательства. Если факт будет подтвержден, сайт немедленно удалят涉嫌侵权的内容。