redis之list源码分析

本是古典何须时尚 2021-06-26 16:06 485阅读 0赞

## `list`的数据结构 ##

redis的`list`的结构为`quicklist`，并非简单的类似`java`的`LinkedList`链表或者`ArrayList`数组，而是将链表和数值结合的一种数据结构。

宏观上`list`是一个`quicklist`链表，通过双向指针前后连接，但是链表的每一个节点是一个`ziplist`字节数组，在字节数组上保存`list`的数据。默认配置下，每个`ziplist`最大为8K字节，在向满了的`ziplist`插入新数据时或拆分或新建`ziplist`来存放新数据。  
![在这里插入图片描述][20210223155230350.png]

typedef struct quicklist { 
        quicklistNode *head;
        quicklistNode *tail;
        unsigned long count;
        unsigned long len;
        int fill : 16;
        unsigned int compress : 16;
    } quicklist;
    
    
    typedef struct quicklistNode { 
        struct quicklistNode *prev;
        struct quicklistNode *next;
        unsigned char *zl;
        unsigned int sz;
        unsigned int count : 16;
        unsigned int encoding : 2;
        unsigned int container : 2;
        unsigned int recompress : 1;
        unsigned int attempted_compress : 1;
        unsigned int extra : 10;
    } quicklistNode;
    
    
    unsigned char *ziplistNew(void) { 
        unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
        unsigned char *zl = zmalloc(bytes);
        ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); // 4字节
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); // 4字节
        ZIPLIST_LENGTH(zl) = 0; // 2字节
        zl[bytes-1] = ZIP_END;
        return zl;
    }

## `ziplist` ##

`ziplist`是一个紧凑的数据结构，`redis`为了节省内存空间没有定义结构体而直接使用字节数值，减少了指针的空间大小。

`ziplist`的数据结构如下图所示，`zlbytes`记录了`ziplist`的字节数组长度；`zltail`记录了`ziplist`中最后一个节点距离起始位的偏移量，可以通过该值直接定位到`ziplist`的最后一个元素；`zllen`表示`ziplist`中的节点数量；`zlend`则为固定值`0xff`表示`ziplist`的结尾。

![在这里插入图片描述][20210223160114717.png]

### `ziplist`元素节点 ###

`ziplist`的每个节点由3个部分组成：`prev_entry_length`、`entry_encoding`和`value`。

p += zipStorePrevEntryLength(p,prevlen);
    p += zipStoreEntryEncoding(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) { 
    	memcpy(p,s,slen);
    } else { 
    	zipSaveInteger(p,value,encoding);
    }

**`prev_entry_length`**

`prev_entry_length`表示前一个节点的长度，且`prev_entry_length`本身的字节长度不固定：

当前一个节点的长度小于`254`时：`prev_entry_length`占用1个字节长度，表示节点的字节长度；  
当前一个节点的长度大于等于`254`时：`prev_entry_length`占用5个字节长度，第一个字节固定值为`0xfe`，后四个字节表示字节的长度；

#define ZIP_BIG_PREVLEN 254 
    unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) { 
        if (p == NULL) { 
            return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(len)+1;
        } else { 
            if (len < ZIP_BIG_PREVLEN) { 
                p[0] = len;
                return 1;
            } else { 
                return zipStorePrevEntryLengthLarge(p,len);
            }
        }
    }
    
    int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) { 
        if (p != NULL) { 
            p[0] = ZIP_BIG_PREVLEN;
            memcpy(p+1,&len,sizeof(len));
            memrev32ifbe(p+1);
        }
        return 1+sizeof(len);
    }

**`entry_encoding`**

`entry_encoding`表示节点的编码格式，且`entry_encoding`本身的字节长度不固定：

*  `value`为整数值时占用1个字节；
 *  `value`为字符串值时：
    
     *  如果字节长度小于等于`63`则占用1个字节；
     *  如果字节长度大于`63`且小于等于`16383`则占用`2`个字节；
     *  如果字节长度大于`16383`则占用`5`个字节；

unsigned int zipStore
    entry_encoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) { 
        unsigned char len = 1, buf[5];
    
        if (ZIP_IS_STR(encoding)) {  // 字符串值
            if (rawlen <= 0x3f) {  // 63
                if (!p) return len;
                buf[0] = ZIP_STR_06B | rawlen;
            } else if (rawlen <= 0x3fff) { 	// 16383
                len += 1;
                if (!p) return len;
                buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
                buf[1] = rawlen & 0xff;
            } else { 
                len += 4;
                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 { 	// 整数值
            if (!p) return len;
            buf[0] = encoding;
        }
    
        memcpy(p,buf,len);
        return len;
    }

## 临界值 ##

默认配置下，每个`ziplist`最大为`8K`字节，在向满了的`ziplist`插入新数据时或拆分或新建`ziplist`来存放新数据。

#define OBJ_LIST_MAX_ZIPLIST_SIZE -2
    lobj = createQuicklistObject();
    // quicklist->fill = server.list_max_ziplist_size = -2
    quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,
    					server.list_compress_depth);
    
    static const size_t optimization_level[] = { 4096, 8192, 16384, 32768, 65536};
    // 判断ziplist是否能插入新节点
    REDIS_STATIC int
    _quicklistNodeSizeMeetsOptimizationRequirement(const size_t sz,
                                                   const int fill) { 
        if (fill >= 0)
            return 0;
    
        // 默认offset为1即ziplist的最大长度为8192字节
        size_t offset = (-fill) - 1;
        if (offset < (sizeof(optimization_level) / sizeof(*optimization_level))) { 
            if (sz <= optimization_level[offset]) { 
                return 1;
            } else { 
                return 0;
            }
        } else { 
            return 0;
        }
    }

[20210223155230350.png]: /images/20210626/fa1cc99ba79d4c9fbeb00bf91c31138a.png
[20210223160114717.png]: /images/20210626/8a921b6305344af6afdca7a6fe2d5d21.png