Redis数据结构之压缩列表（ziplist）

压缩列表( ziplist) 是列表键和晗希键的底层实现之一。当一个列表键只包含少量 列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么 Redis 就 会使用压缩列表来做列表键的底层实现。

压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以 保存一个字节数组或者一个整数值。

数据结构

压缩列表结构
zlbytes zltail zllen entry1 endtry2 ... entryN zlend

zlbytes ：四个字节，记录了整个压缩列表总共占用了多少字节数
zltail ：四个字节，记录压缩列表表尾节点距离压缩列袤的起始地址有多少字节:通过这个偏移量程序无须遍历整个压缩列表就可以确定表尾节点的地址
zllen ：两个字节，记录了整个压缩列表中总共包含几个endtry节点
entryx：非固定字节，记录的是单个节点
zlend: 0xFF 一个字节，十进制的值为 255，标志压缩列表的结尾

entry结构
previous_entry_length encoding  content

previous_entry_length 属性以字节为单位，记录了压缩列表中前一个节点的长度，可以是1字节或者5字节
如果前一节点的长度小于254字节，previous_entry_length占用1字节，具体的长度局存在这1字节中
如果前一节点的长度大于等于254字节，previous_entry_length占用5字节，且第一字节设置为0XFE(254),之后4字节保存具体的长度

encoding 属性记录了节点的 content 属性所保存数据的类型以及长度:
一字节、两宇节或者五宇节长，值的最高位为 00、01 或者 10 的是字节数组编码: 这种编码表示节点的  content 属性保存着字节数组，数组的长度由编码除去最高两 位之后的其他位记录
一字节长，值的最高位以 11 开头的是整数编码:这种编码表示节点的 content属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录

00xxxxxx            一个字节	长度小于 63 的字符串
01xxxxxx xxxxxxxx	两个字节	长度小于 16383 的字符串
10xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx	五个字节	长度小于 4294967295 的字符串
content 的具体长度，由编码除去高两位剩余的二进制位表示。

编码	    编码长度	content类型
11000000	一个字节	int16_t 类型的整数
11010000	一个字节	int32_t 类型的整数
11100000	一个字节	int64_t 类型的整数
11110000	一个字节	24 位有符号整数
11111110	一个字节	8 位有符号整数

typedef struct zlentry {
    //前一个节点长度使用了几字节编码
    unsigned int prevrawlensize; 
    //前一个节点长度
    unsigned int prevrawlen;     
    //当前节点长度使用了几字节编码，对于string有1,2,5，对于intergers为1
    unsigned int lensize;        
    //当前节点长度，对于string就是本身串的长度，对于intergers 有0,1,2,3,4,8
    unsigned int len;           
    //prevrawlensize + lensize
    unsigned int headersize;     
    //ZIP_STR_* or ZIP_INT_*
    unsigned char encoding;    
    //指向当前节点数据  
    unsigned char *p;            
} zlentry;
//次结构并没有真实使用，对于整数来说，比较浪费空间

节点插入

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;
    //prevlensize 存储前一个节点长度，本节点使用了几个字节 1 or 5
    //prelen  存储前一个节点实际占用了几个字节
    if (p[0] != ZIP_END) {
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    } else {
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        if (ptail[0] != ZIP_END) {
            prevlen = zipRawEntryLength(ptail);
        }
    }
    if (zipTryEncoding(s,slen,&value,&encoding)) {
        //s 指针指向一个整数，尝试进行一个转换并得到存储这个整数占用了几个字节
        reqlen = zipIntSize(encoding);
    } else {
        //s 指针指向一个字符串（字符数组），slen 就是他占用的字节数
        reqlen = slen;
    }
    //当前节点存储数据占用 reqlen 个字节，加上存储前一个节点长度占用的字节数
    reqlen += zipStorePrevEntryLength(NULL,prevlen);
    //encoding 字段存储实际占用字节数
    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);
    //至此，reqlen 保存了存储当前节点数据占用字节数和 encoding 编码占用的字节数总和
    int forcelarge = 0;
    //当前节点占用的总字节减去存储前一个节点字段占用的字节
    //记录的是这一个节点的插入会引起下一个节点占用字节的变化量
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
    if (nextdiff == -4 && reqlen < 4) {
        nextdiff = 0;
        forcelarge = 1;
    }
    //扩容有可能导致 zl 的起始位置偏移，故记录 p 与 zl 首地址的相对偏差数，事后还原 p 指针指向
    offset = p-zl;
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
    p = zl+offset;
    if (p[0] != ZIP_END) {
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
        //把当前节点占用的字节数存储到下一个节点的头部字段
        if (forcelarge)
            zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
        else
            zipStorePrevEntryLength(p+reqlen,reqlen);

        ZIPLIST_TAIL_OFFSET(zl) =
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
        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);
    }
    //是否触发连锁更新
    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);
    }
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}