redis源码学习之压缩列表

系统管理员 2022-07-11 15:28 211阅读 0赞

# 压缩列表 #

列表键和哈希键的底层实现。是为了节约内存而实现。

压缩列表是一段连续的内存，每个属性都会有固定的编码大小，例如对于字符串来说，我们需要知道字符串的长度，假设小于63字节，那么我们只需要一个字节的大小来表示（2位标识，6位数据）；而存储的结构是整型的数的话，我们只需要1个字节来表示该整型是16/32/64位整型。

压缩列表用一段连续内存表示`unsigned char *`类型指针来访问，不过它人为的规定了这一段连续内存的数据类型：  
前4个字节（uint32\_t）表示整个ziplist的长度所占用的内存数：zlbytes；  
再往后4个字节表示表尾节点到压缩列表的字节数：zltail；  
然后2个字节（uint16\_t）表示压缩列表中节点数目：zllen；  
之后就是数据内容zlentry；  
最后压缩列表有1个字节的特殊值标记列表末尾：zlend：0xFF

根据上述说明，redis定义了一些宏来获取各个元素的值，主要是进行地址运算，因为header的大小固定：

// 定位到 ziplist 的 bytes 属性，该属性记录了整个 ziplist 所占用的内存字节数
    // 用于取出 bytes 属性的现有值，或者为 bytes 属性赋予新值
    #define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
    // 定位到 ziplist 的 offset 属性，该属性记录了到达表尾节点的偏移量
    // 用于取出 offset 属性的现有值，或者为 offset 属性赋予新值
    #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
    // 定位到 ziplist 的 length 属性，该属性记录了 ziplist 包含的节点数量
    // 用于取出 length 属性的现有值，或者为 length 属性赋予新值
    #define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
    // 返回 ziplist 表头的大小
    #define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
    // 返回指向 ziplist 第一个节点（的起始位置）的指针
    #define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
    // 返回指向 ziplist 最后一个节点（的起始位置）的指针
    #define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
    // 返回指向 ziplist 末端 ZIP_END （的起始位置）的指针
    #define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

对字节长度进行编码，有两个数据类型，一个是字节长度，一个是编码字节长度所需要的长度。

在Redis设计与实现中，给了两个表格，分别是字节数组编码（在源码中又叫字符串），整数编码。

现在给定一个长度len，需要对其进行编码。首先源码中定义了一些宏，分别表示不同字节范围表示的编码。

/*
     * 字符串编码类型
     */
    #define ZIP_STR_06B (0 << 6)//长度小于等于63字节
    #define ZIP_STR_14B (1 << 6)//长度小于等于16383字节
    #define ZIP_STR_32B (2 << 6)//长度小于等于4294967295字节
    
    /*
     * 整数编码类型
     */
    #define ZIP_INT_16B (0xc0 | 0<<4)//1100 0000
    #define ZIP_INT_32B (0xc0 | 1<<4)//1101 0000
    #define ZIP_INT_64B (0xc0 | 2<<4)//1110 0000
    #define ZIP_INT_24B (0xc0 | 3<<4)//1111 0000
    #define ZIP_INT_8B 0xfe//1111 1110

这种编码方式很好理解，对于长度小于等于63字节编码，编码方式应该是`00xxxxxx`，除了高位两位的标识位，后六位能表示的数字范围为`0~63`，这是1个字节的情况。当数据变大时，一个字节显然不能满足条件了，因此就需要加一个字节（8+6 位）的编码长度来表示长度。

如果是整型类型编码就容易多了，不同于字节数组需要记录数据长度，整型数据总是只需要1个字节来表示整型数据类型。

在redis源码`src/ziplist.c`中用`zipEncodeLength`函数来描述上述过程。

static unsigned int zipEncodeLength(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
        unsigned char len = 1, buf[5];
    
        // 编码字符串
        if (ZIP_IS_STR(encoding)) {
            /* Although encoding is given it may not be set for strings,
             * so we determine it here using the raw length. */
            if (rawlen <= 0x3f) {
       //63
                if (!p) return len;//1
                buf[0] = ZIP_STR_06B | rawlen;
            } else if (rawlen <= 0x3fff) {
       //16383
                len += 1;//2
                if (!p) return len;
                buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
                buf[1] = rawlen & 0xff;
            } else {
                len += 4;//5
                if (!p) return len;
                buf[0] = ZIP_STR_32B;
                buf[1] = (rawlen >> 24) & 0xff;
                buf[2] = (rawlen >> 16) & 0xff;
                buf[3] = (rawlen >> 8) & 0xff;
                buf[4] = rawlen & 0xff;
            }
    
        // 编码整数
        } else {
            /* Implies integer encoding, so length is always 1. */
            if (!p) return len;
            buf[0] = encoding;
        }
    
        /* Store this length at p */
        // 将编码后的长度写入 p 
        memcpy(p,buf,len);
    
        // 返回编码所需的字节数
        return len;
    }

# 插入元素 #

主要过程是：  
1.确定插入位置：头插/尾插。  
分为头部和尾部来讨论，  
如果在头部插入，则待插入元素所需要的字节数就是头部元素prelen的值。  
如果在尾部插入，则尾部元素的字节长度就是p节点的prelen长度。  
2.尝试将字符串转换为长整型，比如“123”->123  
转换成功将根据encoding获取不同编码获取不同大小例如uint\_32位4个字节，否则使用字符串原始长度，例如“hello”长度为5个字节，将这个长度值加到reqlen上，reqlen为新添加节点的长度，包括content的长度和header的长度。  
3.将prelen编码长度加到reqlen上  
4.将encoding编码长度加到reqlen上  
5.之后就是最复杂的一步了，就考虑如果在头部插入元素，且原来头部元素的prelen不够编码新的元素，他们之间产生一个差值，这个差值也要计算到重新分配ziplist时的大小。  
比如，原节点的prelen为1个字节（记录content小于254的情况），现在插入一个很长的节点，则需要5个字节的空间保存，那么这个额外多出来的4个字节nextdiff则需要记录进来。  
6.重新申请ziplist大小，为原长度curlen+新节点长度reqlen+第5步所说的nextdiff。  
7.调整原来的元素，为新元素挪动位置。  
8.将header写入新元素地址，此时需要挪动指针，方便拷贝content。这部分想了很久：

// 一切搞定，将前置节点的长度写入新节点的 header
        p += zipPrevEncodeLength(p,prevlen);
        // 将节点值的长度写入新节点的 header
        p += zipEncodeLength(p,encoding,slen);
    //这里写入同时还要移动p的位置，方便后面memcpy拷入content
    
        // 写入节点值
        if (ZIP_IS_STR(encoding)) {
            // T = O(N)
            memcpy(p,s,slen);
        } else {
            // T = O(1)
            zipSaveInteger(p,value,encoding);
        }