Redis源码学习基本数据结构之ziplist

ziplist

  压缩列表是列表键和哈希键的底层实现之一。 当一个列表键只包含少量表项，并且每个列表项要么是小整数，要么是较短的字符串 ，那么redis就会使用压缩列表来作为列表键的底层实现。 当一个哈希键只包含少量key-value对，且每个key-value对的key和value要么是小整数，要么是较短字符串，那么redis就会使用ziplist作为哈希键的底层实现。
  ziplist是一个经过特殊编码的双向链表，它的设计目标就是为了提高存储效率。ziplist可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。它能以O(1)的时间复杂度在表的两端提供push和pop操作。

ziplist结构

一个完整的ziplist结构如下：
<zlbytes 4字节> <zltail 4字节> <zllen 2字节> <entry>
 <entry> ... <entry> <zlend 一字节>
其中：
<zlbytes : ziplist所占字节数> uint32_t，小端存储 4字节
<zltail : 最后一个entry的偏移量 , pop O(1)>  uint32_t 4字节
<zllen : entry的个数 当有超过2^16-2个entry时，设为 2^16-1 
然后通过遍历来得到长度> uint16_t 2字节
<entry : 数据记录元素>
<entry : 数据记录元素> ... <entry : 数据记录元素> 
<zlend:结束标志 255> uint8_t 1字节
所以一个ziplist最低使用字节数为4+4+2+1

元素entry结构

其一般性结构为：
      <prelen><encoding><entry-data>
prelen 表示 前一个entry的所占内存字节数
encoding 表示entry-data编码方式
entry-data 表示实际的数据
其中，当entry-data是数字且足够小时，encoding中可以就包含data了，此时就没有entry-data这一结构了。
其中，对于encoding：
如果entry-data是string类型：
00,xxxxxx  表示长度小于63字节(6bit位表示)的字符串
01,xxxxxx xxxxxxxx 表示长度小于16383字节(14bit位表示)的字符串
10,000000 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 10的话直接用四字节表示字符串的长度。
如果entry-data是数字 那么encoding第一个字节的前两个bit设置为11，随后的两个bit用来表示时什么类型的数字：
11,00,0000 int16_t(2字节)
11,01,0000 int32_t(4字节)
11,10,0000 int64_t(8字节)
11,11,0000 int24_t(24bit)
11,11,1110 int8_t(1字节)
11,11,xxxx(0001-1101)表示4bit的数字（表示范围0-12）
11,11,1111 结束标志

api

unsigned char *ziplistNew(void);//创建一个空压缩链表 空压缩链表长度为7字节

unsigned char *ziplistMerge(unsigned char **first, unsigned char **second);//合并两个链表
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where);//s插入压缩链表前插或者后插

unsigned char *ziplistIndex(unsigned char *zl, int index);//寻找第index个entry
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);//寻找下一个元素
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);//寻找上一个元素

unsigned int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, long long *lval);//entry p 得到他的数据 *sval==null的话就是数字 否则就是字符串

unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);//在entry p后面插入一个entry s

unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);//删除一个元素
unsigned char *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num);//删除从index开始的num个元素

unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen);//比较entry p的数据和slen长度的数据

unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip);

unsigned int ziplistLen(unsigned char *zl);//压缩链表entry个数
size_t ziplistBlobLen(unsigned char *zl); //压缩链表的所占内存字节数

void ziplistRepr(unsigned char *zl);//打印压缩链表信息

主要api之插入数据

//在p位置上面插入一个长度为slen的数据s
unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    return __ziplistInsert(zl,p,s,slen);
}

//在p位置上插入一个item 可能导致后面的所有entry长度变化！！！
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;//prevlensize prelen所占字节数
    size_t offset;//偏移
    int nextdiff = 0;//下一个存储prelen 需要的字节数差
    unsigned char encoding = 0;//编码
    long long value = 123456789;
    zlentry tail;

    //找到p前一个entry所占字节数 如果p就是结束标志 那么直接得到最后一个entry的len
    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)) {//可以被编码为数字吗
        reqlen = zipIntSize(encoding);//entry-data len 所占字节数
    } else {
        reqlen = slen;//entry-data len 所占字节数
    }
    //更新需要的字节数 数据长度+prelen+ecoding
    reqlen += zipStorePrevEntryLength(NULL,prevlen);//+prenlen 所占字节数
    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);//+encoding len 所占字节数

    //当插入位置不是尾部插入时
    int forcelarge = 0;// 0
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
//p的prelen要重新赋值为reqlen的值
// 字节空间需要多少   现在存储reqlen所需的字节数 - 原来的prelen 
所占字节数(可能的值 0 -4 +4)
 //1 5  = -4 需要减少四个字节 此时 reqlen需要字节数为1 p->prelen 需要5个字节
// 而reqlen > p->prelen所需字节数(5个字节) 所以这一步不存在的吧！！！！
//即  reqlen必然大于5
//5 1  = +4 需要扩张4个字节
//1 1  =  0 不用处理
//5 5  =  0 不用处理
//对于这个函数的理解，我们分两部 先假设nextdiff ==0时的情况，
//再考虑nextdiff ！=0时的情况，比较容易想通。
    if (nextdiff == -4 && reqlen < 4) {
        nextdiff = 0;
        forcelarge = 1;
    }
    offset = p-zl;//p的偏移量 防止realloc地址变化
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);//重新申请内存
    p = zl+offset;//重新获得p

    if (p[0] != ZIP_END) {
        //后移p以及以后的数据 为将要插入的数据腾出空间
        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);
    }
    //如果p存储之前的prelen与存储现在的prelen不一样的话 就更新这个
    if (nextdiff != 0) {
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;
    }
    //往空entry里面写要插入的数据
    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;
}

主要api之移除数据

insert的反操作 
待更新.............

参考

• https://blog.csdn.net/u012658346/article/details/51321337
• https://redis.io/
• https://blog.csdn.net/zhaoliang831214/article/details/82054476