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 压缩列表

可以看成是一个数组,元素大小可变;双向的列表

结构

image

  • 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属性保存的值
00bbbbbb1 byte保存长度小于等于63字节的字节数组(以00开头)
01bbbbbb xxxxxxxx2 bytes保存长度小于等于16383字节的字节数组(以01开头)
10bbbbbb xxxxxxxx aaaaaaaa cccccccc dddddddd5 bytes保存长度小于等于4294 967 295字节的字节数组(以10开头)

整数:

编码编码长度content属性保存的值
1100 00001 byteint16_t类型的整数
1101 00001 byteint32_t类型的整数
1110 00001 byteint64_t类型的整数
1111 00001 byte24位有符号整数
1111 11101 byte8位有符号整数
1111 xxxx1 bytexxxx将是介于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,会进行压缩

评论

暂无评论