Redis(1)——基础数据结构
文章目录
前言
文章基于Redis5.0.8稳定版
PS:看源码最好直接到redis官网下载稳定版本的,github上面的dev分支下载下来,编译可能会有些奇奇怪怪的错误
本文会介绍Redis中内存分配封装和一些基础的数据结构
zmalloc
先来看一个宏定义
#ifdef __GLIBC__
#include <malloc.h>
#define HAVE_MALLOC_SIZE 1
#define zmalloc_size(p) malloc_usable_size(p)
#endif
size_t malloc_usable_size (void *ptr)
glibc是unix的c基础库,linux系统上都有这个库
malloc_usable_size这个函数,传入一个指针,返回指针指向的空间实际占用的大小
这个返回的大小,可能会比使用malloc申请的要大,由于系统的内存对齐或者最小分配限制
这里zmalloc_size 等价于 malloc_usable_size这个方法
并且定义了宏 HAVE_MALLOC_SIZE,就是个标志
zmalloc
现在来看zmalloc方法
void *zmalloc(size_t size) {
void *ptr = malloc(size + PREFIX_SIZE);
if (!ptr) zmalloc_oom_handler(size);
#ifdef HAVE_MALLOC_SIZE
update_zmalloc_stat_alloc(zmalloc_size(ptr));
return ptr;
#else
*((size_t*)ptr) = size;
update_zmalloc_stat_alloc(size+PREFIX_SIZE);
return (char*)ptr+PREFIX_SIZE;
#endif
}PREFIX_SIZE = sizeof(size_t)
分配内存时,会多分配一块大小
redis默认,实际分配的字节数量,应该是 sizeof(long) 的整数倍
例如sizeof(long)是4字节,那么实际分配的大小应该是4、8、12、16 这种倍数值
如果不是整数倍,那就向上取整到整数倍
在zmalloc.c文件中,定义了一个全局变量 static size_t used_memory = 0;
用来记录当前分配内存的总大小
update_zmalloc_stat_alloc这个方法,就是给used_memory增加分配的大小
当然,这个是加锁的,使用了pthread_mutex_lock
总结来说,zmalloc就是除了分配内存,还记录了总分配的内存
如果有glibc,其实多分配的那个size_t没用上,那个size_t是在无法获取实际分配的内存时,redis自己去内存对齐
zfree
过程类似,就是把used_memory减小,再free
SimpleDynamicString (sds)
sds是redis的字符串结构
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};packed表示结构体成员采用紧凑的方式排列
buf为字符数组,len为已使用长度,alloc为buf总长度-1,因为buf最后一个为 0
根据使用长度不同,划分了不同的结构体,其实就是保存长度使用不同的类型
然后还定义了枚举值,表示对应的结构
#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4注意,结构体中定义的这种不指定长度的数组,实际malloc的时候,是会忽略这个的
当访问这个buf时,实际上访问了结构体的末尾+1
sdsnewlen
然后来看第一个函数:
看注释
typedef char *sds;
/**
* 传入字符数组,及长度(不包括最后的 \0),返回sds结构体指针
*/
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
//一、根据大小,决定使用哪种结构体
char type = sdsReqType(initlen);
/* Empty strings are usually created in order to append. Use type 8
* since type 5 is not good at this. */
//长度为0,则使用8位大小的
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
//二、分配空间, 就是调用zmalloc
//initlen是分配数据的空间,最后的1是字符数组结尾的 \0
sh = s_malloc(hdrlen+initlen+1);
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
if (sh == NULL) return NULL;
//三、设置len, alloc, flags
//s指向数组的开头
s = (char*)sh+hdrlen;
//fp指向结构体中的flags
fp = ((unsigned char*)s)-1;
//len和alloc都为数组长度,因为也就分配了这么多
//flags为那几个枚举值
//SDS_TYPE_5比较特殊,因为它没有len和alloc,当长度小于32(二进制 100000)时使用
//SDS_TYPE_5的flags,低三位保存type,高五位保存长度
switch(type) {
case SDS_TYPE_5: {
*fp = type | (initlen << SDS_TYPE_BITS);
break;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
}
//四、把传入的数组复制到sds的数组
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';
return s;
}这里有个宏定义 SDS_HDR_VAR
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
##表示单纯的字符串拼接,当T为8的时候,就变成了:
struct sdshdr8 *sh = s - sizeof(struct sdshdr8)第二个参数s,为sds结构体中的数组的开头,所以这里的意思就很明显了,就是回到对应结构体的开头
(当然,这里其实可以直接强转 sh指针,一样的)
这里要注意了:这个函数并不是返回sds结构体,而是返回了字符数组的开头!
通过这个函数分配的空间结构是这样的:
| 不定长 len | 不定长 alloc | 1字节 flags | 字符数组 |
sdsfree
void sdsfree(sds s) {
if (s == NULL) return;
s_free((char*)s-sdsHdrSize(s[-1]));
}s是结构体后面的那个字符数组
s[-1]表示那个flag
这里就是要回到结构体的开头
sds sdsMakeRoomFor(sds s, size_t addlen)
s: 原始sds
addlen:需要增加的长度
sds扩容
首先判断 alloc - len > addlen,如果成立,空间足够,返回s
然后决定扩容后的大小
把当前有效长度len 加上 addlen,如果小于1024*1024(1M),那就长度乘2;否则再加1M
最终的长度有没有超过当前结构体的len和alloc的范围,如果没超过,直接realloc扩容,更新alloc值
如果超过了,释放传入的s,重新分配空间,设置好属性,把原来的字符串复制到新分配的结构体
sds sdscatlen(sds s, const void *t, size_t len)
s: 被拓展的sds
t: 需要复制的
len: t的长度
首先调用sdsMakeRoomFor
然后把复制过去,更新len值
sds sdscatrepr(sds s, const char *p, size_t len)
也是追加字符串,但这个函数会把p 的字符串中不可见字符转为16进制或特定字符
会追加上 "*p"
首先调用sdscatlen(s,"\"",1),添加第一个双引号
然后遍历p,判断几个特殊的:\ " n r a t b
其他的字符调用ctype.h中的isprint方法,可见字符直接拼接,不可见字符转为 x 十六进制
最后加上最后的双引号
sds sdssplitlen(const char s, ssize_t len, const char sep, int seplen, int count)
按照分割符,分割字符串
最后一个参数 count,会写入分出的大小
返回值为 指针,实际上为数组
里面遍历原串,预先分配大小为5的指针数组,需要扩容就乘以2
sds sdstrim(sds s, const char *cset)
cset是字符数组,从左右两边找到第一个不是cset中的字符,截取中间部分
这里是直接修改传入参数s
如果前面需要截取,就先使用memmove把要截取的字符串放到最前面,直接设置s[len] = '0',修改sds的len属性
如果前面不需要截取,就直接设置s[len] = '0',修改sds的len属性
sds sdssplitargs(const char line, int *argc)
按照空格、n、r、t、0 分割字符串,可以取出单引号、双引号,还可以转换16进制、换行符等转换为真正的字符
line为需要分割的原串,argc作为返回值数量,函数返回sds数组
sds sdscatprintf(sds s, const char *fmt, ...)
fmt为格式字符串,后面为可变参数。拼接到s后面
使用va_list获取可变参数
真正调用的是sds sdscatvprintf(sds s, const char *fmt, va_list ap)
由于不知道填充后的字符串到底有多长,所以先按照fmt的2倍长度预估
如果fmt长度小于512,那就在栈上分配1024字节的空间;如果大于512,使用zmalloc分配
调用标准c库的 int vsnprintf(char buffer, int n, const char format, va_list ap); //输出到字符串 (stdarg.h)
顺利的话,直接把buffer,sdscat到s后面就行了
如果超过长度,那就再乘以2,再分配空间
dict
其实和java的 hashmap差不多
dict是最外面的一层,dictType是函数指针列表,用这个来实现多态;rehashidx扩容的时候用;dictht是对数组的封装
table是数组,数组装指针,dictEntry类似于java里的 Map.Entry
存在哈希冲突的时候,使用链表解决,dictEntry的next成员就是用来做链表的
dictCreate
dict dictCreate(dictType type, void *privDataPtr)
首先分配dict的空间,初始化赋值,rehashidx为-1,table是NULL,第一次添加的时候会分配空间
dictExpand
int dictExpand(dict *d, unsigned long size)
先把size向上取整到2的n次方,然后分配dictht,并分配table
判断dict->ht[0].table是否为NULL,为NULL表示刚初始化的dict,那就直接让dict->ht[0]等于分配的dictht
否则,赋值到dict->ht[1],rehashidx = 0,表示进入扩容状态
_dictExpandIfNeeded
static int _dictExpandIfNeeded(dict *d)
如果d->ht[0].size == 0,也就是刚初始化,调用dictExpand为4
根据dict_can_resize,若为1,那么当used>=size就可以扩容;如果为0,需要used > 5*size才扩容
扩容为used*2
_dictKeyIndex
static long _dictKeyIndex(dict d, const void key, uint64_t hash, dictEntry **existing)
hash是用key计算出来的hash
existing是传入的指针,如果这个key在dict里没有,是NULL;如果已有,existing指向dictEntry
现在看一下具体的执行:
首先调用_dictExpandIfNeeded,然后将hash 与 sizemask,在table数组中找,如果数组中有,还要顺着链表找一遍
其实和java一样的
另外,如果正处于rehash,2个table都会找
dictAddRaw
dictEntry dictAddRaw(dict d, void key, dictEntry *existing)
首先查看key在dict是否已存在
//查看key在dict是否已存在
//如果已存在,返回-1,同时existing指向已存在dictEntry
//如果不存在,返回table数组中的index
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) {
return NULL;
}如果正在扩容,需要插入到ht[1];正常插入ht[0]
dictIsRehashing就是判断rehashidx是否等于-1
dictht *ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];开始插入,插入到链表的开头
dictSetKey:如果dictType的keyDup函数为NULL,那entry->key直接指向传入的key;如果keyDup函数有,entry->key指向keyDup函数返回结果
这里其实是判断key要不要拷贝一份
dictEntry *entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
/* Set the hash entry fields. */
dictSetKey(d, entry, key);
return entry;最后返回entry
dictRehash
int dictRehash(dict *d, int n)
redis使用渐进式rehash,就是不会一次过完成rehash,而是在每次访问dict时,移动一小部分到新数组
rehashidx表示旧数组(ht[0])的当前进行到的下标,所以是从0开始的
顺着数组找到第一个不为NULL的元素(dictEntry),把整个链表的元素重新哈希到新的数组(ht[1]),旧数组的used减一,新数组的used加一
如果旧数组的used减到0,释放旧数组,把新数组设为ht[0],rehashidx设为-1,整个rehash过程就完成了
dictAdd
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key,NULL);
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);
return DICT_OK;
}函数比较简单,dictAddRaw如果key已经存在,返回NULL
dictSetVal和 dictSetKey一样的,根据dictType的valDup函数有没有,决定是直接赋值还是拷贝
这个函数相当于java的 putIfAbsent
dictReplace
这个函数相当于java的 put
int dictReplace(dict *d, void *key, void *val)
{
dictEntry *entry, *existing, auxentry;
/* Try to add the element. If the key
* does not exists dictAdd will succeed. */
entry = dictAddRaw(d,key,&existing);
if (entry) {
dictSetVal(d, entry, val);
return 1;
}
/* Set the new value and free the old one. Note that it is important
* to do that in this order, as the value may just be exactly the same
* as the previous one. In this context, think to reference counting,
* you want to increment (set), and then decrement (free), and not the
* reverse. */
auxentry = *existing;
dictSetVal(d, existing, val);
dictFreeVal(d, &auxentry);
return 0;
}在替换旧的value时,需要处理旧的value
调用dictType的valDestructor函数
注释里说了,这个顺序很重要,先设置新value,再free旧value;对于引用计数来说
dictGetSomeKeys
unsigned int dictGetSomeKeys(dict d, dictEntry *des, unsigned int count)
从dict随机取最多count个entry,放到des数组,有可能不足count个,而且不保证随机分布
抓取方式:
dict在rehash时会有两个table,先不考虑这个
- 首先在table数组的长度范围内,随机取一个值,random() & sizemask
- 这个值作为下标访问数组,如果这里没有entry,看下一个
当连续count个(至少5)都没有时,回到第一步重新取随机值
在脸最黑的情况下,重新取随机值也是连续的空,那这个得有个限度,不能无限取下去吧
因此设置了最大步数:count * 10,到了最大步数就要return
如果取到的坑位不是空,我们知道,当哈希冲突的时候会以链表的方式保存;
因此就把整个链表的entry都存到des里,最多count个;不够的话看下一个坑
这样来看的话,取出来的entry,有可能是哈希值相近的;这应该就是为什么 注释里说的不保证很好的分布
————————————————————————————————————————————————————————————
如果正在rehash,两个table都取一次
但是,如果随机值小于dict->rehashidx,直接去第二个table找
dictGetRandomKey
dictEntry dictGetRandomKey(dict d)
这个函数随机取一个entry
在没有rehash的情况下,table数组随机取一个不为空的,然后链表里面再随机取一个
在有rehash时,取值范围变成了,第一个table数组 rehashidx至数组长度、第二个table数组全长
ziplist 压缩列表
可以看成是一个数组,元素大小可变;双向的列表
结构
- zlbytes: 开头的4字节表示整个结构的长度(包括自己),例如刚创建时,长度为11字节
- zltail: 然后的4字节记录压缩列表的起始地址距离压缩列表尾结点多少字节数。使得无须遍历即可访问列表尾。例如刚创建时为10
- zllen: 节点数量,刚创建时为0
- 最后的是0xff,结束符
Entry:
Entry由3部分组成:previous_entry_length, encoding, content
previous_entry_length
节点的previous_entry_length属性是以字节为单位,记录前一个节点的长度。长度可以是1字节或者5字节
通过判断第一个字节的大小,来判断是1字节还是5字节
小于254(0xfe),就是1字节;等于,那就是5字节,后面4字节才是长度
为什么不用0xff? 应该是因为ziplist的结束符是0xff,避免冲突
这个部分的存在,使得可以从后往前遍历。根据previous_entry_length可以跳到前一个节点的开头。
所以说ziplist是双向的
encoding
encoding属性记录本节点的content所保存数据的类型以及长度,可以保存字节数组或者整数
看第一个字节的最高2位,如果为11,那就是整数,否则就是字节数组
字节数组也有分为1、2、5个字节
| 编码 | 编码长度 | content属性保存的值 |
|---|---|---|
| 00bbbbbb | 1 byte | 保存长度小于等于63字节的字节数组(以00开头) |
| 01bbbbbb xxxxxxxx | 2 bytes | 保存长度小于等于16383字节的字节数组(以01开头) |
| 10bbbbbb xxxxxxxx aaaaaaaa cccccccc dddddddd | 5 bytes | 保存长度小于等于4294 967 295字节的字节数组(以10开头) |
整数:
| 编码 | 编码长度 | content属性保存的值 |
|---|---|---|
| 1100 0000 | 1 byte | int16_t类型的整数 |
| 1101 0000 | 1 byte | int32_t类型的整数 |
| 1110 0000 | 1 byte | int64_t类型的整数 |
| 1111 0000 | 1 byte | 24位有符号整数 |
| 1111 1110 | 1 byte | 8位有符号整数 |
| 1111 xxxx | 1 byte | xxxx将是介于0001到1101之间,表示 0 - 12 之间的值,所以使用这一编码无须content属性 |
content就是内容了
插入
插入函数:
先看前面的部分
//zl就是ziplist,p是需要插入到哪个节点的前面,如果ziplist是空的,那p就是最后的那个0xff
//如果ziplist不为空,则p就是entryX的指针
//s是要插入的数据指针,slen就是长度
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
//curlen就是第一个4字节,zlbytes
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
unsigned int prevlensize, prevlen = 0;
size_t offset;
int nextdiff = 0;
unsigned char encoding = 0;
long long value = 123456789; /* initialized to avoid warning. Using a value
that is easy to see if for some reason
we use it uninitialized. */
zlentry tail;
/* Find out prevlen for the entry that is inserted. */
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判断解释一下
如果p是0xff(ziplist结束符),那表示插入到尾部
ZIPLIST_ENTRY_TAIL就是获取zltail,如果zltail指向的数值也是0xff,说明ziplist为空,什么也不用做
如果zltail不是0xff,说明ziplist不为空,此时ptail指向的最后一个节点的开头
/* Return the total number of bytes used by the entry pointed to by 'p'. */
unsigned int zipRawEntryLength(unsigned char *p) {
unsigned int prevlensize, encoding, lensize, len;
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
return prevlensize + lensize + len;
}ZIP_DECODE_PREVLENSIZE就是判断previous_entry_length第一个字节,prevlensize为1或者5
ZIP_DECODE_LENGTH就是根据encoding,lensize是encoding长度,len是后面content的长度
返回的就是Entry的长度
那如果p不是0xff,说明p指向一个Entry,prevlensize就是previous_entry_length的长度,prevlen就是previous_entry_length表示的大小
插入的第一部分就是获取p的长度,然后是第二部分
/* See if the entry can be encoded */
if (zipTryEncoding(s,slen,&value,&encoding)) {
/* 'encoding' is set to the appropriate integer encoding */
reqlen = zipIntSize(encoding);
} else {
/* 'encoding' is untouched, however zipStoreEntryEncoding will use the
* string length to figure out how to encode it. */
reqlen = slen;
}
/* We need space for both the length of the previous entry and
* the length of the payload. */
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);zipTryEncoding就是看能不能把s转成整形(string2ll函数),如果可以,value就是值,encoding就是对应的值,reqlen就是这个整形存储需要的字节数(<=12那就是0)
不能转,那reqlen就是slen
因为需要新插入一个Entry,这个新Entry的previous_entry_length需要空间,所以需要看prevlen有多大。如果ziplist为空,prevlen为0,previous_entry_length仍然为1
注意:如果s不能转为整形,那现在encoding为0
encoding也需要空间,如果s转为了整形,那encoding只需要1字节,否则就是字符串,那就根据slen判断encoding需要的空间
做完之后,reqlen就是新节点需要的空间
现在
/* When the insert position is not equal to the tail, we need to
* make sure that the next entry can hold this entry's length in
* its prevlen field. */
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
if (nextdiff == -4 && reqlen < 4) {
nextdiff = 0;
forcelarge = 1;
}
/* Store offset because a realloc may change the address of zl. */
offset = p-zl;
zl = ziplistResize(zl,curlen+reqlen+nextdiff);
p = zl+offset;
/* Apply memory move when necessary and update tail offset. */
if (p[0] != ZIP_END) {
/* Subtract one because of the ZIP_END bytes */
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/* Encode this entry's raw length in the next entry. */
if (forcelarge)
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
/* Update offset for tail */
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
/* When the tail contains more than one entry, we need to take
* "nextdiff" in account as well. Otherwise, a change in the
* size of prevlen doesn't have an effect on the *tail* offset. */
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 {
/* This element will be the new tail. */
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}由于要在p前面插入一个Entry,我们知道p节点的previous_entry_length表示前一个节点的长度,现在前一个节点变了,那这个长度存储可能会变,nextdiff就是表示这个变化
ziplistResize就是调用realloc重新分配空间
memmove就是把p后面的数据往后移动,留出空间
forcelarge先认为为0,然后就是更改p节点的previous_entry_length
由于ziplist变长了,所以zltail也要增加reqlen
下面是做一些调整
最后把新增加的空间,填充要插入的数据
/* Write the 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;__ziplistInsert这个函数基本就是这样
quickList
就是链表,链表的Entry是zipList
quicklist的结构为什么这样设计呢?总结起来,大概又是一个空间和时间的折中:
- 双向链表便于在表的两端进行push和pop操作,但是它的内存开销比较大。首先,它在每个节点上除了要保存数据之外,还要额外保存两个指针;其次,双向链表的各个节点是单独的内存块,地址不连续,节点多了容易产生内存碎片。
- ziplist由于是一整块连续内存,所以存储效率很高。但是,它不利于修改操作,每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候,一次realloc可能会导致大批量的数据拷贝,进一步降低性能。
于是,结合了双向链表和ziplist的优点,quicklist就应运而生了。
Redis提供了一个配置参数list-max-ziplist-size,表示一个zipList最多放多少
list-max-ziplist-size为正数表示个数,负数则表示字节大小
- -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。(注:1kb => 1024 bytes)
- -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。
- -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。
- -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。(-2是Redis给出的默认值)
- -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。
还有另一个参数:list-compress-depth
- 0: 是个特殊值,表示都不压缩。这是Redis的默认值。
- 1: 表示quicklist两端各有1个节点不压缩,中间的节点压缩。
- 2: 表示quicklist两端各有2个节点不压缩,中间的节点压缩。
- 3: 表示quicklist两端各有3个节点不压缩,中间的节点压缩。
依此类推…
现在来看quicklist的结构
/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
* 'count' is the number of total entries.
* 'len' is the number of quicklist nodes.
* 'compress' is: -1 if compression disabled, otherwise it's the number
* of quicklistNodes to leave uncompressed at ends of quicklist.
* 'fill' is the user-requested (or default) fill factor. */
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count; /* 总的个数 */
unsigned long len; /* ziplist的个数 */
int fill : 16; /* list-max-ziplist-size */
unsigned int compress : 16; /* list-compress-depth */
} quicklist;createQuicklist
创建比较简单,就是赋值;head和tail都是null
插入
由于每个ziplist有大小限制,所以插入之前要先判断一下会不会超出
//node是quicklist->tail,fill就是fill属性,sz是插入的字节大小
REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,
const int fill, const size_t sz) {
if (unlikely(!node))
return 0;
int ziplist_overhead;
/* size of previous offset */
if (sz < 254)
ziplist_overhead = 1;
else
ziplist_overhead = 5;
/* size of forward offset */
if (sz < 64)
ziplist_overhead += 1;
else if (likely(sz < 16384))
ziplist_overhead += 2;
else
ziplist_overhead += 5;
/* new_sz overestimates if 'sz' encodes to an integer type */
unsigned int new_sz = node->sz + sz + ziplist_overhead;
if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz, fill)))
return 1;
else if (!sizeMeetsSafetyLimit(new_sz))
return 0;
else if ((int)node->count < fill)
return 1;
else
return 0;
}
如果第一个参数node是NULL,返回0;返回0表示不可以插入
ziplist里面的节点有三部分,首先内容的长度肯定是要的,然后是这个内容的编码长度;
因为插入了,所以后一个节点的previous_entry_length需要更换
ziplist_overhead就是这3部分的增加值, new_sz就是增加之后的总大小
第一个判断是判断如果fill小于0,判断new_sz是否满足限制
第二个判断,每个ziplist最大只能到8192
第三个判断,fill大于0,count需要小于fill
如果不能插入
//首先假设要插入到头head,先判断能否插入
_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz)
//如果返回0
//quicklist是一个双向链表,链表节点就是quicklistNode
quicklistNode *node = quicklistCreateNode();
//插入到ziplist
node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
//node->sz = ziplist的大小
quicklistNodeUpdateSz(node);
_quicklistInsertNodeBefore(quicklist, quicklist->head, node);
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl; //ziplist指针
unsigned int sz; /* ziplist size in bytes */
unsigned int count : 16; /* count of items in ziplist */
unsigned int encoding : 2; /* RAW==1 or LZF==2 */
unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
unsigned int recompress : 1; /* was this node previous compressed? */
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;ziplistPush 就是调用 __ziplistInsert,第二个参数p是ziplist头或者尾节点,取决于ziplistPush的第4个参数
最后那个函数,实际调用的是
void __quicklistInsertNode(quicklist quicklist, quicklistNode old_node, quicklistNode *new_node, int after)
这个函数做了3件事情:
- 链表节点插入,常规操作
- quicklist->len++
- 可能需要压缩old_node
压缩
压缩的逻辑在这个函数:
int __quicklistCompressNode(quicklistNode *node)
如果ziplist小于48字节,不需要压缩
压缩算法使用LZF
压缩之后,quicklistNode->zl指向的就不是ziplist,而是quicklistLZF
typedef struct quicklistLZF {
unsigned int sz; /* LZF size in bytes*/ //sz就是后面那个数组的大小
char compressed[];
} quicklistLZF;压缩之后,quicklistNode->encoding就是QUICKLIST_NODE_ENCODING_LZF,recompress = 0
对quicklist进行压缩的函数则是这个:
void __quicklistCompress(const quicklist quicklist, quicklistNode node)
首先判断quicklist的compress是否为0,并且长度要大于compress * 2
然后,分别从头和尾开始遍历compress个node,遍历的这些node全部解压缩
如果插入的这个node不在这里面,将之压缩
也就是说,中间的那些node有没有被压缩,这个就没有去检测了,因为遍历整个链表的话耗时很长
这里提个小问题,插入的时候,要插入到ziplist时,为什么没有判断是否需要解压的操作?
想一想compress的含义,0表示压缩,1表示头尾1个node不压缩
而插入时,要么插入到头,要么是尾,头和尾肯定是没有压缩的,所以不需要解压
当然,如果要插入到中间,那是需要解压的
如果可以插入
那就直接调用ziplistPush插入就是了
最后把quicklist->count++,插入基本就是这么个逻辑,从尾部插入也是一样的
查找第几个
在quicklist中查找第n个数据
前面说过,quicklist是一个装ziplist的双向链表,那要查找第n个数据,那就从头或者尾开始遍历
先累加ziplist的count,当第一次大于n时,就可以确定这个数据在这个ziplist中
然后再在这个ziplist中查找就行了
前面也讲到,会对ziplist进行压缩,如果这个ziplist压缩过(encoding是QUICKLIST_NODE_ENCODING_LZF),那要解压缩
之后并没有再次进行压缩,而是把ziplistNode的recompress置为1;在其他的操作中如果检测到这个recompress为1,会进行压缩
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论