압축 목록(ziplist)은 특수하게 인코딩된 일련의 메모리 블록으로 구성된 목록으로, Redis 데이터 저장소 최적화에 매우 중요한 역할을 합니다. 이 문서에서는 주로 사용되는 데이터 구조인 압축 연결 목록 ziplist를 공유합니다. 레디스에서. 이 데이터 구조는 Redis 어디에나 존재한다고 해도 과언이 아닙니다. 연결된 목록 외에도 이전 기사에서 언급한 SortedSet과 같은 다른 많은 데이터 구조에서도 이를 전환에 사용합니다. 아래에서는 할 말이 많지 않으니, 자세한 소개를 살펴보겠습니다.
1. 압축 연결 목록 ziplist 데이터 구조 소개
먼저 아래와 같이 ziplist의 구조를 전체적으로 살펴보겠습니다.
압축 연결 목록 ziplist 구조 다이어그램
필드가 많고 바이트 크기가 다양하다는 것을 알 수 있지만 이것이 압축 연결 목록의 핵심입니다.
|
필드 |
의미 |
|
즐바이트 |
이 필드는 압축 연결 리스트의 첫 번째 필드로 부호 없는 정수이며 4바이트를 차지합니다. 전체 압축 연결 목록(자체 포함)이 차지하는 바이트 수를 나타내는 데 사용됩니다. |
|
즐테일 |
부호 없는 정수, 4바이트를 차지합니다. 압축된 연결 목록의 헤드부터 마지막 항목(꼬리 요소 zlend 아님)까지의 오프셋을 저장하는 데 사용되며, 연결 목록의 끝으로 빠르게 이동할 수 있는 시나리오에 사용됩니다. |
|
즐렌 |
부호 없는 정수, 2바이트를 차지합니다. 압축된 연결 목록에 포함된 전체 항목 수를 저장하는 데 사용됩니다. |
|
즐렌드 |
압축된 연결 목록의 끝을 나타내는 데 사용되는 특수 항목입니다. 1바이트를 차지하고 값은 항상 255입니다. |
ziplist의 head와 tail로 요약되며, 가장 중요한 입력 필드는 아래와 같이 요약됩니다.
일반적으로 항목은 prevlen, 인코딩 및 항목 데이터의 세 가지 필드로 구성됩니다. 그러나 항목이 작은 정수인 경우 인코딩에 따라 항목 데이터 필드가 생략됩니다. 다음은 요약입니다:
첫 번째 필드는 prevlen입니다. 이는 이전 항목의 길이를 나타냅니다. 두 가지 인코딩 방법이 있습니다.
그런 다음 필드 인코딩이 있습니다. 다음과 같이 현재 요소의 내용에 따라 다른 인코딩 방법을 사용합니다.
1. 요소 콘텐츠가 문자열인 경우 인코딩 값은 다음과 같습니다.
00xx xxxx: 00으로 시작하는 문자열의 길이가 6비트로 표시됨을 나타냅니다.
01xxxxxx |
1000 0000 |xxxxxxxxxxx |
2. 요소 내용이 숫자인 경우 인코딩 값은 다음과 같습니다.
1100 0000: 숫자가 다음 2바이트를 차지함을 나타냅니다.
1101 0000: 숫자가 다음 4바이트를 차지함을 나타냅니다.
1110 0000: 숫자가 다음 8바이트를 차지함을 나타냅니다.
1111 0000: 숫자가 다음 3바이트를 차지함을 나타냅니다.
1111 1110: 숫자가 다음 바이트를 차지함을 나타냅니다.
1111 1111: 압축된 연결 목록(특수 인코딩)의 마지막 요소를 나타냅니다.
1111xxxx
: 0부터 12까지의 정수를 나타내기 위해 마지막 4자리만 사용됨을 나타냅니다. 0000, 1110, 1111은 이미 채워져 있으므로, 즉 여기서 xxxx의 4자리는 0001부터 1101까지만 나타낼 수 있습니다. 십진수로 변환하면 , 1부터 13까지의 숫자입니다. 그러나 redis에서는 0~12를 나타내는 데 사용된다고 규정하고 있으므로 이 인코딩을 만나면 마지막 4자리를 빼고 1을 빼야 올바른 값을 얻을 수 있습니다.
마지막으로 항목 데이터 필드가 있습니다. 요소 값이 문자열이면 요소 자체의 값이 저장됩니다. 요소의 값이 매우 작은 숫자(위의 인코딩 규칙에 따라 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라는 두 요소로 구성된 압축된 연결 목록이며 16진수로 표시됩니다.
우선, 처음 4바이트는 전체 ziplist가 차지하는 바이트 수를 나타냅니다. redis는 little-endian 저장소를 사용하므로 15바이트는 0f 00 00 00으로 표시됩니다.
이때 전체 압축 연결 리스트는 다음과 같습니다.
[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
로그인 후 복사
2. 압축된 연결 목록 ziplist 명령 소스 코드 분석
위의 인코딩 규칙을 이해한 후 압축 연결 목록 ziplist의 일부 작업 소스 코드를 살펴보겠습니다. 이 기사에서는 압축 연결 목록 생성, 요소 삽입, 삭제의 네 가지 작업을 통해 압축 연결 목록의 기본 원리를 요약합니다. 요소 및 요소 검색.
첫 번째는 다음을 만드는 것입니다:
//定义由zlbytes，zltail跟zllen组成的压缩链表的头大小
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//创建一个压缩链表，并且返回指向该链表的指针
unsigned char *ziplistNew(void) {
//这里之所以+1是因为尾元素占用一个字节，这也是一个压缩链表最小尺寸
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
//分配内存
unsigned char *zl = zmalloc(bytes);
//设置链表大小
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
//设置最后一个元素的偏移量
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
//设置元素个数
ZIPLIST_LENGTH(zl) = 0;
//设置尾元素（上面只是申请空间）
zl[bytes-1] = ZIP_END;
return zl;
}로그인 후 복사
압축된 연결 목록을 생성하는 논리는 매우 간단합니다. 즉, 헤드 및 테일 노드가 포함된 고정 공간을 적용한 다음 연결 목록 컨텍스트를 초기화하는 것입니다.
与创建相比，添加元素的源码就非常冗长了，为了便于理解，在看源码之前我们先自己梳理一下添加元素的逻辑。
首先我们要找到指定插入位置的前一个元素的大小，因为该属性是新元素的组成部分之一。
然后我们要对当前元素进行编码来获得相应的encoding字段跟实际元素值的字段。
新插入元素的后继元素的prevlen字段要更新，因为它前面的元素已经改变。这里可能引起级联更新（删除元素也有该问题），原因就是prevlen字段大小是可变的。
上面三步是核心步骤，其余的还有更新尾节点偏移量，修改链表元素个数等操作。当然，由于压缩链表是基于数组实现的，因此在插入或删除元素的时候内存拷贝也是必不可少的。
总结好上面的步骤以后，我们开始一步一步分析源码，比较长，慢慢看：
//四个参数依次是：压缩链表，插入位置（新元素插入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 <p>
分析完插入元素的逻辑，长舒一口气，真的很长，细节也很多。</p><p>
接下来在再看下删除元素的过程，与添加相比，删除相对要简单一些，清空当前元素以后，需要把后继元素一个一个拷贝上来（这也是数组跟链表两个数据结构的差别），然后注意是否需要级联更新，上代码：</p><pre class="brush:php;toolbar:false">//参数依次为：压缩链表，删除元素的其实位置，删除元素的个数
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 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);
}
//resize数组大小
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) {
//匹配成功，则要查找元素的指针
return 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) {
//如果两个数字相等，则返回元素指针
return p;
}
}
}
//重置需要跳过的元素个数
skipcnt = skip;
} else {
//跳过元素
skipcnt--;
}
//遍历下个元素
p = q + len;
}
//遍历完整个链表，没有找到元素
return NULL;
}로그인 후 복사
到这里就把压缩链表的创建，添加，删除，查找四个基本操作原理总结完了。
三、压缩链表ziplist数据结构总结
压缩链表ziplist在redis中的应用非常广泛，它算是redis中最具特色的数据结构了。该数据结构的精髓其实就在于文章第一部分总结的编码规则，先理清楚这部分内容，后面的源码可以简单看下加深理解。
不得不说源码部分着实有点冗长，确实需要耐心，我自己在读的过程中也很头大。如果对源码感兴趣的话，建议按我的方法，先自己梳理某个操作（例如上面提到的插入元素）需要做哪些事情，然后再看代码可能会更好理解一些。
相关推荐：
深入剖析 redis 数据结构 ziplist
Redis源码分析（六）---ziplist压缩列表
Redis内部数据结构详解之ziplist
위 내용은 Redis 압축 연결 목록 ziplist 소스 코드에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
