redis的list的结构为quicklist，并非简单的类似java的LinkedList链表或者ArrayList数组，而是将链表和数值结合的一种数据结构。
宏观上list是一个quicklist链表，通过双向指针前后连接，但是链表的每一个节点是一个ziplist字节数组，在字节数组上保存list的数据。默认配置下，每个ziplist最大为8K字节，在向满了的ziplist插入新数据时或拆分或新建ziplist来存放新数据。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 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); ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); ZIPLIST_LENGTH(zl) = 0 ; zl[bytes-1 ] = ZIP_END; return zl; }
ziplist是一个紧凑的数据结构，redis为了节省内存空间没有定义结构体而直接使用字节数值，减少了指针的空间大小。
ziplist的数据结构如下图所示，zlbytes记录了ziplist的字节数组长度；zltail记录了ziplist中最后一个节点距离起始位的偏移量，可以通过该值直接定位到ziplist的最后一个元素；zllen表示ziplist中的节点数量；zlend则为固定值0xff表示ziplist的结尾。
ziplist的每个节点由3个部分组成：prev_entry_length、entry_encoding和value。
1 2 3 4 5 6 7 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，后四个字节表示字节的长度；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #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个字节；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 unsigned int zipStoreentry_encoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) { unsigned char len = 1 , buf[5 ]; if (ZIP_IS_STR(encoding)) { if (rawlen <= 0x3f ) { if (!p) return len; buf[0 ] = ZIP_STR_06B | rawlen; } else if (rawlen <= 0x3fff ) { 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来存放新数据。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #define OBJ_LIST_MAX_ZIPLIST_SIZE -2 lobj = createQuicklistObject(); quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size, server.list_compress_depth); static const size_t optimization_level[] = {4096 , 8192 , 16384 , 32768 , 65536 };REDIS_STATIC int _quicklistNodeSizeMeetsOptimizationRequirement(const size_t sz, const int fill) { if (fill >= 0 ) return 0 ; 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 ; } }
