Redis 압축 연결 목록 ziplist 소스 코드에 대한 자세한 설명

압축 목록(ziplist)은 특수하게 인코딩된 일련의 메모리 블록으로 구성된 목록으로, Redis 데이터 저장소 최적화에 매우 중요한 역할을 합니다. 이 문서에서는 주로 사용되는 데이터 구조인 압축 연결 목록 ziplist를 공유합니다. 레디스에서. 이 데이터 구조는 Redis 어디에나 존재한다고 해도 과언이 아닙니다. 연결된 목록 외에도 이전 기사에서 언급한 SortedSet과 같은 다른 많은 데이터 구조에서도 이를 전환에 사용합니다. 아래에서는 할 말이 많지 않으니, 자세한 소개를 살펴보겠습니다.

1. 압축 연결 목록 ziplist 데이터 구조 소개

먼저 아래와 같이 ziplist의 구조를 전체적으로 살펴보겠습니다.

압축 연결 목록 ziplist 구조 다이어그램

필드가 많고 바이트 크기가 다양하다는 것을 알 수 있지만 이것이 압축 연결 목록의 핵심입니다.

필드	의미
즐바이트	이 필드는 압축 연결 리스트의 첫 번째 필드로 부호 없는 정수이며 4바이트를 차지합니다. 전체 압축 연결 목록(자체 포함)이 차지하는 바이트 수를 나타내는 데 사용됩니다.
즐테일	부호 없는 정수, 4바이트를 차지합니다. 압축된 연결 목록의 헤드부터 마지막 ​​항목(꼬리 요소 zlend 아님)까지의 오프셋을 저장하는 데 사용되며, 연결 목록의 끝으로 빠르게 이동할 수 있는 시나리오에 사용됩니다.
즐렌	부호 없는 정수, 2바이트를 차지합니다. 압축된 연결 목록에 포함된 전체 항목 수를 저장하는 데 사용됩니다.
즐렌드	압축된 연결 목록의 끝을 나타내는 데 사용되는 특수 항목입니다. 1바이트를 차지하고 값은 항상 255입니다.

ziplist의 head와 tail로 요약되며, 가장 중요한 입력 필드는 아래와 같이 요약됩니다.

일반적으로 항목은 prevlen, 인코딩 및 항목 데이터의 세 가지 필드로 구성됩니다. 그러나 항목이 작은 정수인 경우 인코딩에 따라 항목 데이터 필드가 생략됩니다. 다음은 요약입니다:

첫 번째 필드는 prevlen입니다. 이는 이전 항목의 길이를 나타냅니다. 두 가지 인코딩 방법이 있습니다.

• 길이가 255바이트 미만인 경우 1바이트로 저장됩니다.

• 
  

• 길이가 255보다 크거나 같으면 저장에 5바이트가 사용되고 첫 번째 바이트는 255로 설정됩니다. 이는 이전 항목의 길이가 다음 4바이트로 표시됨을 나타냅니다.

그런 다음 필드 인코딩이 있습니다. 다음과 같이 현재 요소의 내용에 따라 다른 인코딩 방법을 사용합니다. 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으로 표시됩니다.

• 
  

다음 4바이트는 마지막 요소의 오프셋을 나타내며, 이는 ziplist 헤더(zlbytes)에서 마지막 요소(참고: tail 노드 아님)까지의 오프셋입니다. 또한 little endian으로 저장되므로 0c로 표현됩니다. 00 00 00.

• 
  

다음은 요소 수를 나타내는 2바이트로 구성된 zllen 필드입니다. 이 예에서는 두 요소와 리틀 엔디안 저장소가 있으므로 02 00으로 표현됩니다.

• 
  

다음은 요소 자체입니다. 먼저 가변 길이 워드는 이전 요소의 길이를 나타냅니다. 2는 첫 번째 요소의 크기가 0이므로 00바이트를 차지합니다. 위에서 언급한 인코딩 규칙에 따르면 요소 2와 5는 0에서 12 사이의 숫자에 속하므로 1111을 사용해야 합니다. xxxx 형식으로 인코딩하고, 2는 0010으로 바이너리로 변환되고, 1을 더하면 0011이 됩니다(1을 추가하는 이유는 위에 설명되어 있습니다). 결합된 요소 2는 00으로 표시됩니다. f3. 마찬가지로 요소 5는 02 f6으로 표시됩니다.

• 
  

마지막 요소는 비어 있는 코드 1111 1111(255)을 사용하는 꼬리 요소입니다.
다음으로, 이 압축 연결 목록 끝에 문자열 요소 Hello를 삽입합니다. World, 먼저 문자열을 인코딩하는 방법을 살펴보겠습니다. 합의된 인코딩 규칙에 따라 먼저 바이트를 사용하여 이전 요소의 길이를 나타냅니다. 여기서 이전 요소는 5로 총 2바이트를 차지하므로 먼저 단어를 사용합니다. 섹션은 이전 요소의 길이인 02를 나타냅니다. 다음은 문자열의 인코딩입니다. 추가하려는 문자열의 길이는 11입니다(공백도 계산됨). 바이너리로 변환하면 1011입니다. 문자열의 인코딩 규칙은 0000을 사용합니다. 1011은 16진수로 변환하면 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

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!