redis源码分析六--压缩列表

1、压缩列表的特点

• 压缩列表是一种为节约内存而开发的顺序型数据结构。
• 压缩列表被用作列表键和哈希键的底层实现之一。
• 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
• 添加新节点到压缩列表， 或者从压缩列表中删除节点， 可能会引发连锁更新操作， 但这种操作出现的几率并不高

2、压缩列表的内存布局

上图就是压缩列表的布局情况

• zlbytes：表示整个压缩列表占用的内存字节数
• zltail：记录压缩列表表尾节点距离压缩列表起点地址有多少字节。通过这个我们可以快速访问到压缩列表的表尾
• zllen：记录了压缩列表中的节点数量，需要注意的是这个只占用两个字节，如果列表的数量超过65535时，这时候我们需要遍历整个列表才能知道整个列表中的节点数量
• extry：这里记录了每一个节点的信息
• zlend：特殊值0xFF，用来标记是末尾

其中entry的内存布局如下

• previous_entry_length：表示这个节点的前一个节点的长度。注意这个数据的长度可以为1个字节和5个字节，如果前面的节点的长度小于254个字节，那么这个数据的长度就是1个字节，如果前面节点的长度大于254个字节，那么这个数据的长度为5个字节。并且这5个字节中第一个字节为0xFE特殊值，后面4个字节的数据表示前面一个节点的长度
• encoding：表示编码格式，也是表示content所保存数据的类型和长度。他的长度有3种。分别是1个字节，2个字节，5个字节的长度。同时这个encoding的数值进行约定我们可以得到content的类型和长度范围
• content：表示了节点数据内容

3、压缩列表源码分析

3.1、压缩列表如何添加数据

static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    unsigned int curlen = ZIPLIST_BYTES(zl), reqlen, prevlen = 0;
    unsigned int offset, nextdiff = 0;
    unsigned char encoding = 0;
    long long value;
    zlentry entry, tail;

    /*获取添加节点位置的前置节点的长度
      1、如果添加的是首节点或者添加前压缩列表内没有节点数据，这时候前置节点的长度为0
      2、如果添加的节点在中间，这时候可以通过原来位置节点的前置节点长度数据来得到
      3、如果添加的节点位置在末尾，这时候不能通过下一个节点的前置节点长度来得到，需要自己进行获取
    */
    if (p[0] != ZIP_END) {
    	//添加的位置是中间
        entry = zipEntry(p);
        prevlen = entry.prevrawlen;
    } else {
    	//添加的位置是末尾
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        if (ptail[0] != ZIP_END) {
        	//获取末尾节点的长度，具体函数分析间3.2节分析
            prevlen = zipRawEntryLength(ptail);
        }
    }

    /* 这个函数可以将字符数组s是否可以转换成ll类型，因为转换成ll类型占用的空间会小很多 */
    if (zipTryEncoding(s,slen,&value,&encoding)) {
        /* 返回相应的整型类型的数据长度 */
        reqlen = zipIntSize(encoding);
    } else {
        /* 不能转换成整型，这时候的长度就是slen */
        reqlen = slen;
    }
    /* 上面已经得到了一个节点content的内容所需要占用的内存大小，还需要加上revious_entry_length:encoding的长度 */
    reqlen += zipPrevEncodeLength(NULL,prevlen);
    reqlen += zipEncodeLength(NULL,encoding,slen);

    /* 新添加的节点造成后一个节点的revious_entry_length膨胀问题
     1、如果添加的节点是末尾节点，那么新添加的节点之后没有后置节点了，也自然无需关心后置节点如何保存新增加节点的长度问题
     2、新增加的节点不是末尾节点，那么需要考虑一种情况，就是原来有1,2,3节点,我现在需要在2之后加入4节点,也就是变成了1,2，4,3，
     如果2的节点长度小于254个字节，那么原来3这个节点revious_entry_length的存储长度为1个字节，但是这时如果我新增的节点4的长度大于254个字节
     那么3这个节点的previous_entry_length的长度需要增大为5个字节，这时候我们需要进行recalloc
     下面这个函数就是为了得到新加入节点后是否需要进行增大revious_entry_length的存储空间 */
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;

    /* 保存需要新增节点的位置的偏移量，这样我们在重新recalloc后还可以定位到正确的位置 */
    offset = p-zl;
    /* 进行扩容*/
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
    p = zl+offset;

    /* 1、如果添加节点的位置是中间，我们需要移动压缩列表的数据
       2、无论添加节点的位置是哪里，我们都需要更新tail的位置信息*/
    if (p[0] != ZIP_END) {
        /* 移动数据，但是这里有一处疑问，为什么是从p-nextdiff开始移动？*/
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

        /* 更新新增节点的后置节点中previous_entry_length的信息 */
        zipPrevEncodeLength(p+reqlen,reqlen);

        /* 更新tail节点的位置信息 */
        ZIPLIST_TAIL_OFFSET(zl) += reqlen;

        /* 如果发生了扩容，同时还需要加上nextdiff的偏移量 */
        tail = zipEntry(p+reqlen);
        if (p[reqlen+tail.headersize+tail.len] != ZIP_END)
            ZIPLIST_TAIL_OFFSET(zl) += nextdiff;
    } else {
        /* 这种情况是添加的节点的位置已经是末尾 */
        ZIPLIST_TAIL_OFFSET(zl) = p-zl;
    }

    /* 如果发生了nextdiff增大的情况，可能会发生连锁反应，就是后置节点因为previous_entry_length增大了4个字节，这样如果这个后置节点的大小大于250的字节，小于
    254个字节，那么他的下一个字节也会造成膨胀 */
    if (nextdiff != 0) {
        offset = p-zl;
        //详细分析见3.3节
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;
    }

    /* 将previous_entry_length的数据和encoding的数据写入 */
    p += zipPrevEncodeLength(p,prevlen);
    p += zipEncodeLength(p,encoding,slen);
    /* 根据str类型和int类型写入数据*/
    if (ZIP_IS_STR(encoding)) {
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
    /* 标记节点数量+1 */
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}

3.2、如何获取末尾节点的节点长度

/* Return the total number of bytes used by the entry pointed to by 'p'. */
static unsigned int zipRawEntryLength(unsigned char *p) {
    unsigned int prevlensize, encoding, lensize, len;
    /*节点由3个部分组成，分别是revious_entry_length:encoding:content
       ZIP_DECODE_PREVLENSIZE获取revious_entry_length长度
       previous_entry_length的长度有两种：1和字节和5个字节，可以通过前面的节点分析得到
       ZIP_DECODE_LENGTH获取encoding的长度和content的长度*/
    ZIP_DECODE_PREVLENSIZE(p, prevlensize);
    ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
    return prevlensize + lensize + len;
}

3.3、如何处理insert的连锁反应

static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
    size_t offset, noffset, extra;
    unsigned char *np;
    zlentry cur, next;
	//一直处理直到最后
    while (p[0] != ZIP_END) {
    	/* 获取当前节点的信息*/
        cur = zipEntry(p);
        rawlen = cur.headersize + cur.len;
        rawlensize = zipPrevEncodeLength(NULL,rawlen);

        /* 如果到达最后的节点，则直接返回，否则获取当前节点的下一个节点 */
        if (p[rawlen] == ZIP_END) break;
        next = zipEntry(p+rawlen);

        /* 判断下一个节点的previous_entry_length的长度是否和当前节点的长度相等，
           如果相等，说明当前节点的previous_entry_length的内存空间没有变化，自然不需要
           进行下面的扩容，这时可以直接跳出循环，因为连锁反应到这里结束了 */
        if (next.prevrawlen == rawlen) break;

		/* 后置节点的previous_entry_length的长度小于当前节点的长度，说明当前节点发生了
			previous_entry_length从占用1个字节变成了占用5个字节的变化*/
        if (next.prevrawlensize < rawlensize) {
            /* 进行扩容操作 */
            offset = p-zl;
            extra = rawlensize-next.prevrawlensize;
            zl = ziplistResize(zl,curlen+extra);
            p = zl+offset;

            /* Current pointer and offset for next element. */
            np = p+rawlen;
            noffset = np-zl;

            /* 当下一个节点不是末尾节点时还需要更新末尾节点的位置信息 */
            if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }

            /* 空余出需要新增加的空间 */
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);
            //重新编辑后置节点的previous_entry_length的数据
            zipPrevEncodeLength(np,rawlen);

            /* 移动指针 */
            p += rawlen;
            curlen += extra;
        } else {
        	/* 这种情况是原来的后置节点的previous_entry_length为5个字节的长度，现在
        		只需要一个字节*/
            if (next.prevrawlensize > rawlensize) {
                /* 这时我们不需要重新分配内存，只需要将其强制改成5个字节的大小形式，及时
                第一个字节为0xFE，后面四个字节表示长度 */
                zipPrevEncodeLengthForceLarge(p+rawlen,rawlen);
            } else {
            	/* 这种情况就是虽然长度是发生改变了，但是previous_entry_length的内存空间的大小没有发生改变，我们只是需要更新一下previous_entry_length的内容就可以了，就比如说，本来是234个字节长度，我的previous_entry_length因为前置节点的关系增大了4个字节，现在我就需要占用238个字节，但是这样仍然没有达到254个字节，所以我们这时候不需要处理*/
                zipPrevEncodeLength(p+rawlen,rawlen);
            }

            /* 上面的两种情况下都不会在引起连锁反应，因此到这里也结束了 */
            break;
        }
    }
    return zl;
}

总结：压缩列表的content的存储格式只有char数组和int类型，但是这个压缩列表对char数组的长度情况和int类型是8位，16位，32位还是64位进行了区分，可以更加好的利用内存空间。
同时压缩列表还有很多的标记参数，previous_entry_length参数我们可以知道一个节点的前置节点的长度，这样我们可以在末尾一直往前遍历。encoding参数保存了content的参数类型的长度范围的信息。可以方便我们控制content的内存大小。但是也正是因为这些参数的存在造成了新增一个节点时需要考虑的复杂度。