redis之list源码分析
source link: https://wakzz.cn/2019/07/13/redis/redis%E4%B9%8Blist%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
list的数据结构
redis的list的结构为quicklist,并非简单的类似java的LinkedList链表或者ArrayList数组,而是将链表和数值结合的一种数据结构。
宏观上list是一个quicklist链表,通过双向指针前后连接,但是链表的每一个节点是一个ziplist字节数组,在字节数组上保存list的数据。默认配置下,每个ziplist最大为8K字节,在向满了的ziplist插入新数据时或拆分或新建ziplist来存放新数据。
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的结尾。
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;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK