0%

Redis - 基础数据结构

Redis,一个高性能,纯内存的NoSQL数据库,官方给出的性能数据是10W+QPS,多用于各种高并发业务的缓存框架中。本文主要介绍Redis的一些基础数据结构。

Redis是一个key-value数据库,所有的key-value都存在一个大的字典里,数据结构定义在dict.h里,大致的结构如下:

1

字典数据结构

dictEntry

先从最内层的dictEntry说起,dictEntry是用来存储key-value数据指针的数据结构:

1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;

其中:

  • key

    key通过void*指针,指向存储键的内存地址。键是由SDS(simple dynamic string,简单动态字符串)进行存储,具体数据结构下文会分析。

  • v

    值存储在变量v中,注意v是一个union结构,当值是一个数值时,则直接存储在u64,s64或者d中,否则由void*指针指向存储值的内存地址。

    不管使用的Redis中的何种数据结构,当值不为数值类型时,都是由RedisObject进行存储的,具体数据结构下文会分析。

  • next

    当key-value产生hash冲突时,冲突的项会以链表的形式存储,因此使用next指向下一个dictEntry。

dictht

dictht是用来存储哈希表的结构,定义如下:

1
2
3
4
5
6
7
8
9
10
typedef struct dictht {
// 保存dictEntry指针的数组
dictEntry **table;
// 记录dictEntry指针数组的长度
unsigned long size;
// 用于将哈希值映射到数组的索引
unsigned long sizemask;
// 记录现有的数据个数,used与size的比值就是负载因子(load factor),比值越大,hash冲突概率越高
unsigned long used;
} dictht;

dictht是一个典型的哈希存储结构,先预分配一块内存,记录下能存储的数据大小(size);需要添加新数据时,将key值按照哈希函数计算之后,对sizemask进行’&’操作,得到数组的索引;若此索引下已经存储了数据,则表示产生了哈希冲突,则使用链表的方式,将数据追加到已存在数据的后面,用next指针关联;当负载因子过大时,便会执行rehash逻辑进行扩容。

dict

dict是整个hash结构最顶层的结构,详细代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;

typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;

其中:

  • type:一个dictType对象,定义了字典相关的函数(dict.c#BenchmarkDictType

    • hashFunction:对key进行哈希值计算的哈希算法;
    • keyDup和valDup:分别定义key和value的深拷贝函数;
    • keyCompare:定义两个key的比较操作;
    • keyDestructor和valDestructor:分别定义对key和value的析构函数。
  • privdata:私有数据指针,在dictType的某些操作被调用时会传回给调用者。

  • ht[2]:定义了两个dictht,一般情况下使用[0],当处于rehash的时候,会用到[1],后续会详细讲解;

  • rehashidx:默认值为-1,表示未处于rehash状态;否则表示当前正在进行rehash,并记录了处于哪一步;
  • interators:当前正在进行遍历的iterator的个数。

rehash

Redis中保存的键值对会逐渐增多或减少,为了让负载因子维持在一个合理范围之内,当哈希表保存的键值对太多或太少时,程序要对哈希表的大小进行相应的扩展或收缩,于是便会发生rehash操作。

Redis的数据都存在一个大的字典结构中,当数据量比较大的时候,一次阻塞式的rehash操作可能会导致Redis在一段时间内无法提供服务,因此Redis采用的是渐进式的rehash,分多次完成,以扩容为例,大致步骤为:

  • 为dict.ht[1]哈希表分配空间,这个空间大小取决于要执行的操作:

    • 如果执行的是扩展操作,则ht[1]的大小为第一个大于等于等于ht[0].used*2的2^n;
    • 如果执行的收缩操作,则ht[1]的大小为第一个大于等于ht[0].used的2^n。
  • 在每次执行字典的find、delete、insert操作时,将一小部分保存在ht[0]中的键值对,重新计算键的哈希值和索引值,然后将键值对转移到ht[1]的指定位置上,同时用rehashidx记录下[0]中已经转移了的索引;

  • 当ht[0]包含的所有键值对都迁移到ht[1]之后,释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备。

以一次查找为例,代码如下:

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
#define dictIsRehashing(d) ((d)->rehashidx != -1)

dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
uint64_t h, idx, table;

// 字典为空
if (d->ht[0].used + d->ht[1].used == 0) return NULL;
// 如果正处于rehash状态,则从[0]中转移一部分数据到[1]中
if (dictIsRehashing(d)) _dictRehashStep(d);
// 计算key的hash值
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
// 得到hash值对应的索引
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
// 当hash冲突时,idx位置会保存一个链表,因此需要循环查找key相同的dictEntry
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
// 如果没有处于rehash状态,则只在[0]中查找;否则继续循环,在[1]中查找
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}

其中,rehash相关的代码如下:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
static void _dictRehashStep(dict *d) {
if (d->iterators == 0) dictRehash(d,1);
}

int dictRehash(dict *d, int n) {
int empty_visits = n*10;
if (!dictIsRehashing(d)) return 0;

// 每次操作,最多只处理n个索引的数据
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;

assert(d->ht[0].size > (unsigned long)d->rehashidx);
while(d->ht[0].table[d->rehashidx] == NULL) {
// 如果d->rehashidx位置没有保存数据,则继续处理d->rehashidx + 1的位置
d->rehashidx++;
// 如果连续很大一片数据为空,则也不会一直查找下去,最多查找empty_visits个位置
if (--empty_visits == 0) return 1;
}
// 找到一个存储有数据的索引
de = d->ht[0].table[d->rehashidx];
while(de) {
// 使用while循环,将d->rehashidx索引处的整个链表数据都转移到[1]中
uint64_t h;

nextde = de->next;
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}

// 将ht[1]设置为ht[0],然后为ht[0]新创建一个空白哈希表
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}

return 1;
}

详细的图解例子,可以参考:Redis之字典

其他:

  • insert:如果正在重哈希中,它会把数据插入到ht[1];否则插入到ht[0];
  • delete:如果当前不在重哈希过程中,它只在ht[0]中查找要删除的key;否则ht[0]和ht[1]它都要查找。

基础数据结构

SDS

Redis中,所有的key都是字符串类型的,在Redis底层是以SDS(simple dynamic string)对象存储的。SDS是一种用来存储二进制数据、字符串的数据结构,他有如下几个特点:

  • SDS能存储任意二进制数据;
  • 支持动态扩展内存;
  • 与传统的C语言字符串类型兼容。

其具体数据结构为:

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
34
35
36
37
38
39
typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len;
uint8_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[];
};

#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
#define SDS_TYPE_MASK 7

sdshdr5如注释所说,并没有被使用,因此不讨论。

为什么会有多个sdshdr

这里定义了多个sdshdr数据结构,区别只在于len和alloc变量的类型不同,redis会根据数据的大小,使用合适的数据结构。sdshdr8为uint8_t类型,因此可以表示的字符串最长为255字节;同理sdshdr16可以表示的最长为65536字节,以此类推,具体实现代码为:

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
// 根据输入数据的长度,判断应该用哪种sdshdr类型
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5)
return SDS_TYPE_5;
if (string_size < 1<<8)
return SDS_TYPE_8;
if (string_size < 1<<16)
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32)
return SDS_TYPE_32;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}

// 根据SDS_TYPE_*,返回需要申请的内存长度
static inline int sdsHdrSize(char type) {
switch(type&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return sizeof(struct sdshdr5);
case SDS_TYPE_8:
return sizeof(struct sdshdr8);
case SDS_TYPE_16:
return sizeof(struct sdshdr16);
case SDS_TYPE_32:
return sizeof(struct sdshdr32);
case SDS_TYPE_64:
return sizeof(struct sdshdr64);
}
return 0;
}

typedef char *sds是什么意思

sds.h中,sds被定义为char*,但是我们上面看到明明是有多个sdshdr数据结构,为什么不是一个void*指针指向数据结构?

一个SDS对象,可以分为三部分:

1

头部包含len,alloc,flags三个信息:

  • len:真实数据的大小,即是保存在buf中的真实数据长度。
  • alloc:给buf分配的实际内存的大小。
  • flags:使用低三位表示当前SDS的类型,如代码中定义的SDS_TYPE_*,根据不同类型,来确定当前SDS是上述sdshdr*中的哪种,例如flags如果为4,则表示当前数据结构为sdshdr64。

由于sdshdr有多个数据结构,如果用一个void*指针指向sdshdr对象,那么实际运行过程中,根本不知道将void*强转为哪种类型。因此将sds定义为char*,用来直接指向char buf[]数据部分,然后将指针向低地址偏移一个字节,便能得到flags,通过flags的第三位类型,便能知道len和alloc的变量类型,从而继续向低地址偏移一定的字节,便能得到len和alloc。

1

单从这个case说,其实也可以将flags定义为struct的第一个成员变量,然后就可以使用void*指针了,这样第一个字节就是flags,然后通过类型就可以继续判断是哪个类型。

  • 内存对齐

    为了支持从sds指针左移一个字节就能得到flags,因此sdshdr数据结构都被定义为__attribute__ ((__packed__)),这个是让编译器以紧凑模式来分配内存,如果没有这个属性,编译器可能会为struct的字段做优化对齐,在其中填充空字节。那样的话,就不能保证header和sds的数据部分紧紧前后相邻,也不能按照固定向低地址方向偏移1个字节的方式来获取flags字段了。

  • 内存回收

    内存分配之后,sds指向数据部分,则整块内存起始地址为:

    1
    2
    3
    4
    5
    6
    7
    char oldtype;
    void *sh;
    sds s;
    // s[-1]取flags变量,oldtype为sds类型
    oldtype = s[-1] & SDS_TYPE_MASK;
    // sds指针向低地址偏移,得到起始地址
    sh = (char*)s-sdsHdrSize(oldtype);

    内存回收函数为:

    1
    2
    3
    4
    5
    6
    #define s_free zfree

    void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
    }

为啥SDS对象末尾会有一个\0

在上面SDS对象中,最后一部分是一个固定的\0,这个是为了与传统的C语言字符串类型兼容。C语言字符串,都是以\0结尾的,当len<alloc的时候,buf中空余的内存部分会被填充为\0,当len=alloc的时候,buf中保存的都是真实数据,因此需要最后面这一个额外的\0

相关函数

sds.h中,定义了一些操作SDS对象的函数,一些重要函数如下:

  • sds sdsnewlen(const void *init, size_t initlen)

    新建一个SDS对象,大致步骤如下:

    • 根据c_str的长度选择合适的sds头部类型;
    • 分配足够的空间存储头部与有效字符串(sds字符串末尾需要一个字节存储’\0’);
    • 设置头部信息,将c_str内容copy到sds中。
  • sds sdsMakeRoomFor(sds s, size_t addlen)

    为一个SDS对象增加存储空间,大致步骤如下:

    • 看sds中是否有足够的剩余空间容纳addlen长度的字符串,有则返回,无则继续;
    • 计算需要重新分配的存储空间的长度,包括原sds长度与addlen,另外预备一部分的剩余空间;
    • 根据新的长度,得到新的SDS对象类型,如果新的头部类型与原类型相同,则使用s_realloc分配更多的空间;如果新的头部类型与原类型不相同,则使用s_alloc重新分配内存,并将原sds内容copy到新分配的空间。
  • sds sdsRemoveFreeSpace(sds s)

    释放sds未使用的存储空间,大致步骤如下:

    • 根据len计算新的sds类型与所需内存空间;
    • 如果新的类型与原sds类型相同,使用s_realloc压缩原内存空间;
    • 如果新的类型与原sds类型不相同,使用s_alloc重新分配空间,将原内容copy到新分配的sds中,并释放原内存。

另外还有sdscat,sdscpy等操作,就不一一介绍了。

RedisObject

Redis中,一共有五种常用的数据结构(string,list,set,zset,hash)用来存储key-value中的value,而不管value为何种数据结构,都是在外层封装了一层RedisObject,相关的定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
#define LRU_BITS 24

typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
/* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;

其中:

  • type

    type字段,用来标示这个redisObject是保存的哪种数据结构,type有如下几种类型:

    1
    2
    3
    4
    5
    #define OBJ_STRING 0    /* String object. */
    #define OBJ_LIST 1 /* List object. */
    #define OBJ_SET 2 /* Set object. */
    #define OBJ_ZSET 3 /* Sorted set object. */
    #define OBJ_HASH 4 /* Hash object. */
  • encoding

    encoding表示编码方式,或者也可以理解成二级type,因为就算是同一种类型,根据数据大小,类型等不同,底层的存储结构也可以有多种不同的方式(即是有多种数据编码方式),这种设计主要是尽最大可能节约内存资源。例如当type为OBJ_STRING时,表示这个redisObject存储的是一个string,此时encoding可能为如下几种:

    • OBJ_ENCODING_INT: 当value为一个数值类型时;
    • OBJ_ENCODING_EMBSTR: 当长度小于OBJ_ENCODING_EMBSTR_SIZE_LIMIT时(一种特殊的嵌入式的SDS);
    • OBJ_ENCODING_RAW: 上述两种都不成立时(即是SDS)。

    string类型的编解码函数,见object.c#tryObjectEncoding与object.c#getDecodedObject,也可以参考Redis内部数据结构详解(3)——robj一文中的编解码函数源码解析。

    encoding一共有如下几种取值:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 只有string类型才会用这个encoding值(表示成SDS对象)
    #define OBJ_ENCODING_RAW 0 /* Raw representation */
    #define OBJ_ENCODING_INT 1 /* Encoded as integer */
    #define OBJ_ENCODING_HT 2 /* Encoded as hash table */
    #define OBJ_ENCODING_ZIPMAP 3 /* Encoded as zipmap */
    // 小于Redis 2.6的版本中才有
    #define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
    #define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
    #define OBJ_ENCODING_INTSET 6 /* Encoded as intset */
    #define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
    #define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */
    #define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists */
    #define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */

    其中不同的type,可能的编码方式为:

    • string:RAW,INT,EMBSTR
    • list:QUICKLIST
    • set:INTSET,HT
    • zset:ZIPLIST,SKIPLIST
    • hash:ZIPLIST,HT
  • lru:做LRU替换算法时使用,这里不做深入介绍。

  • refcount

    引用计数,记录一个redisObject被引用的次数,相关代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void incrRefCount(robj *o) {
    if (o->refcount != OBJ_SHARED_REFCOUNT) o->refcount++;
    }

    void decrRefCount(robj *o) {
    if (o->refcount == 1) {
    switch(o->type) {
    case OBJ_STRING: freeStringObject(o); break;
    case OBJ_LIST: freeListObject(o); break;
    case OBJ_SET: freeSetObject(o); break;
    case OBJ_ZSET: freeZsetObject(o); break;
    case OBJ_HASH: freeHashObject(o); break;
    case OBJ_MODULE: freeModuleObject(o); break;
    case OBJ_STREAM: freeStreamObject(o); break;
    default: serverPanic("Unknown object type"); break;
    }
    zfree(o);
    } else {
    if (o->refcount <= 0) serverPanic("decrRefCount against refcount <= 0");
    if (o->refcount != OBJ_SHARED_REFCOUNT) o->refcount--;
    }
    }

    如果引用计数减一之前,已经剩下最后一个引用了,则在decrRefCount函数调用之后,redisObject对象将会被释放掉。

  • ptr:void*指针,指向真正的数据存放的内存地址。例如一个string类型的数据,ptr可能指向一个SDS对象。

string

string类型比较简单,如果value为数值类型,则直接使用dictEntry.v中的三个数值类型的变量存储;如果value为字符串,则使用SDS对象存储,然后使用dictEntry.v.val指向SDS对象。

list

list底层是用quicklist实现的,而quicklist是双向链表和ziplist的结合体,我们先看看大致结构:

1

上图中,node节点主要保存了节点之间的关联关系,数据的状态信息,并不保存实际的数据,数据都存储在ziplist中。

ziplist

上面的数据结构中,并没有明确定义ziplist的数据结构,ziplist就是一块连续的内存,通过地址偏移,划分成不同字段:

可参考ziplist.c中头部的注释。

1

其中:

  • zlbytes:uint32_t类型,存储整个ziplist所占用的内存的字节数;

  • zltail:uint32_t类型,指向ziplist中最后一个entry的偏移量,用于快速定位最后一个entry,以便完成pop等操作;

  • zllen:uint16_t类型,表示entry的数量。因为是一个uint16_t类型,所以当实际数量小于2^16-1时,zllen表示entry的数量;当实际数量大于2^16-1时,则zllen固定为2^16-1,而真实数量需要遍历所有entry才能得到。

  • zlend:终止字节, 0xff,ziplist保证任何情况下,一个entry的首字节都不会是0xff。

  • entry:存储具体的数据,entry的内存布局如下:

    entry根据数据类型,长度不同,形态还比较复杂,这里不深入说明,可以参考:Redis中的数据结构一文中的ziplist部分。

    • prevlen:前一个entry所占用的字节数,这样可以实现反向遍历。注意这是一个变长的字段,根据前一个entry的数据长度不同而不同;
    • encoding:定义后面data字段的存储方式,根据数据类型,值,长度等等不同,encoding的取值也不同,情况较为复杂;
    • data:数据存储字段。

ziplist是一段连续的内存,还可以用LZ4算法压缩后(是否压缩是个配置项),可以包装成一个quicklistLZF结构,数据结构如下:

1
2
3
4
typedef struct quicklistLZF {
unsigned int sz; /* LZF size in bytes*/
char compressed[];
} quicklistLZF;

quicklist

先上源码:

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
34
35
36
37
38
39
40
41
42
// 链表中的node
typedef struct quicklistNode {
// 前一个node
struct quicklistNode *prev;
// 后一个node
struct quicklistNode *next;
// 指向底层的ziplist或者quicklistLZF,取决于是否开启压缩
unsigned char *zl;
unsigned int sz; /* ziplist size in bytes */
unsigned int count : 16; /* count of items in ziplist */
// 等于1的时候,表示底层是ziplist;等于2的时候,表示底层是压缩有的ziplist,即是quicklistLZF
unsigned int encoding : 2; /* RAW==1 or LZF==2 */
unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
// 当前结点所持有的ziplist是否经过了解压,如果该字段为1即代表之前被解压过,且需要在下一次操作时重新压缩
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;

typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
// 所有node中的所有entry的数量
unsigned long count;
// 所有node的数量
unsigned long len;
// 影响每个node中的ziplist的最大占用空间
int fill : 16; /* fill factor for individual nodes */
// 压缩配置
unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

// 对ziplist中的entry的一个封装
typedef struct quicklistEntry {
const quicklist *quicklist;
quicklistNode *node;
unsigned char *zi;
unsigned char *value;
long long longval;
unsigned int sz;
int offset;
} quicklistEntry;

其中,几个重要的参数:

  • quicklist.compress:表示底层ziplist是否压缩成quicklistLZF

    • 0表示不压缩, zl字段直接指向ziplist;
    • 1表示quicklist的链表头尾结点不压缩, 其余结点的zl字段指向的是经过压缩后的quicklistLZF;
    • 2表示quicklist的链表头两个, 与末两个结点不压缩, 其余结点的zl字段指向的是经过压缩后的quicklistLZF;
    • 以此类推, 最大值为2^16。
  • quicklist.fill:控制每个链表结点中, ziplist的长度.

    • 当数值为负数时, 代表单个ziplist的最大占用字节数:

      • -1:不超过4kb;
      • -2:不超过8kb;
      • -3:不超过16kb;
      • -4:不超过32kb;
      • -5:不超过64kb;
    • 当数值为正数时, 代表单个ziplist中,最大的entry数量,最大值为2^15个。

set

set底层使用intset或者hashtable(即是上面介绍的dict)来存储数据。

intset

源码如下:

1
2
3
4
5
6
7
8
9
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;

其中:

  • length:代表存储的整数个数;
  • encoding:取值有三种
    • INTSET_ENC_INT16, contents中以int16_t的形式存储数据;
    • INTSET_ENC_INT32:contents中以int32_t的形式存储数据;
    • INTSET_ENC_INT64:contents中以int32_t的形式存储数据。
  • contents:存储具体的数据。

contents有几个特点:

  • contents中的数据是以升序排列的;
  • 只要有任意一个值超过了encoding对应的数据类型的最大值,则整个contents的数据都要升级。并且升级之后,不会降级;

zset

zset底层使用ziplist或者skiplist来存储数据。

1
2
3
4
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
  • ziplist

    当存储的数据同时满足下面两个条件时,会使用ziplist:

    • 元素数量小于128个;
    • 所有member的长度都小于64字节;

    当使用ziplist存储数据时,两个相邻的entry作为一个item,第一个entry存储值,第二个entry存储score,按照score从小到大进行排列。

  • skiplist

    skiplist俗称跳表,性能能逼近各种搜索树的性能,也是比较流行的一种数据结构,这里就不详细介绍了。

hash

hash底层使用ziplist或者hashtable(即是上面介绍的dict)来存储数据。

当存储的数据同时满足下面两个条件时,会使用ziplist:

  • 哈希中元素数量小于512个;
  • 哈希中所有键值对的键和值字符串长度都小于64字节。

当使用ziplist存储数据时,两个相邻的entry作为一个item,第一个entry存储键,第二个entry存储值。

参考



-=全文完=-