Xudong's Blog

Redis中的数据结构

Word count: 2.6k / Reading time: 9 min
2019/01/14 Share

Redis 命令参考
try Redis(不用安装Redis即可体验Redis命令

Redis支持丰富的数据结构,常用的有string、list、hash、set、sortset。

“Redis is written in ANSI C” – Redis由C语言编写

Redis的存储是以key-value的形式的。Redis中的key一定是字符串,value可以是string、list、hash、set、sortset这几种常用的。

但要值得注意的是:Redis并没有直接使用这些数据结构来实现key-value数据库,而是基于这些数据结构创建了一个对象系统

  • 简单来说:Redis使用对象来表示数据库中的键和值。每次我们在Redis数据库中新创建一个键值对时,至少会创建出两个对象。一个是键对象,一个是值对象。

Redis中的每个对象都由一个redisObject结构来表示:

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct redisObject{

// 对象的类型
unsigned type 4:;

// 对象的编码格式
unsigned encoding:4;

// 指向底层实现数据结构的指针
void * ptr;

//.....
}robj;

不同类型和编码的对象
img

简单来说就是Redis对key-value封装成对象,key是一个对象,value也是一个对象。每个对象都有type(类型)、encoding(编码)、ptr(指向底层数据结构的指针)来表示。

值为1006的字符串对象

SDS简单动态字符串

Redis中的Simple dynamic string使用sdshdr结构来表示一个SDS值:

1
2
3
4
5
6
7
8
9
10
11
struct sdshdr{

// 字节数组,用于保存字符串
char buf[];

// 记录buf数组中已使用的字节数量,也是字符串的长度
int len;

// 记录buf数组未使用的字节数量
int free;
}

SDS例子

使用SDS的好处

  1. sdshdr数据结构中用len属性记录了字符串的长度。那么获取字符串的长度时,时间复杂度只需要O(1)
  2. SDS不会发生溢出的问题,如果修改SDS时,空间不足。先会扩展空间,再进行修改!(内部实现了动态扩展机制)。
  3. SDS可以减少内存分配的次数(空间预分配机制)。在扩展空间时,除了分配修改时所必要的空间,还会分配额外的空闲空间(free 属性)。
  4. SDS是二进制安全的,所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据。

链表

对于链表而言,我们不会陌生的了。在Java中Linkedxxx容器底层数据结构也是有链表存在的。

Redis使用listNode结构来表示每个节点:

1
2
3
4
5
6
7
8
9
10
11
12
typedef strcut listNode{

//前置节点
strcut listNode *pre;

//后置节点
strcut listNode *pre;

//节点的值
void *value;

}listNode

使用listNode是可以组成链表了,Redis中使用list结构来持有链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct list{

//表头结点
listNode *head;

//表尾节点
listNode *tail;

//链表长度
unsigned long len;

//节点值复制函数
void *(*dup) (viod *ptr);

//节点值释放函数
void (*free) (viod *ptr);

//节点值对比函数
int (*match) (void *ptr,void *key);

}list

链表结构

Redis链表的特性

Redis的链表有以下特性:

  • 无环双向链表
  • 获取表头指针,表尾指针,链表节点长度的时间复杂度均为O(1)
  • 链表使用void *指针来保存节点值,可以保存各种不同类型的值

哈希表

又有书中称作“字典”

在Redis中,key-value的数据结构底层就是哈希表来实现的。对于哈希表来说,我们也并不陌生。在Java中,哈希表实际上就是数组+链表的形式来构建的。下面我们来看看Redis的哈希表是怎么构建的吧。

在Redis里边,哈希表使用dictht结构来定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictht{

//哈希表数组
dictEntry **table;

//哈希表大小
unsigned long size;

//哈希表大小掩码,用于计算索引值
//总是等于size-1
unsigned long sizemark;

//哈希表已有节点数量
unsigned long used;

}dictht

哈希表的数据结构

我们下面继续写看看哈希表的节点是怎么实现的吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictEntry {

//键
void *key;

//值
union {
void *value;
uint64_tu64;
int64_ts64;
}v;

//指向下个哈希节点,组成链表
struct dictEntry *next;

}dictEntry;

从结构上看,我们可以发现:Redis实现的哈希表和Java中实现的是类似的。只不过Redis多了几个属性来记录常用的值:sizemark(掩码)、used(已有的节点数量)、size(大小)。

同样地,Redis为了更好的操作,对哈希表往上再封装了一层(参考上面的Redis实现链表),使用dict结构来表示:

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
typedef struct dict {

//类型特定函数
dictType *type;

//私有数据
void *privdata;

//哈希表
dictht ht[2];

//rehash索引
//当rehash不进行时,值为-1
int rehashidx;

}dict;


//-----------------------------------

typedef struct dictType{

//计算哈希值的函数
unsigned int (*hashFunction)(const void * key);

//复制键的函数
void *(*keyDup)(void *private, const void *key);

//复制值得函数
void *(*valDup)(void *private, const void *obj);

//对比键的函数
int (*keyCompare)(void *privdata , const void *key1, const void *key2)

//销毁键的函数
void (*keyDestructor)(void *private, void *key);

//销毁值的函数
void (*valDestructor)(void *private, void *obj);

}dictType

所以,最后我们可以发现,Redis所实现的哈希表最后的数据结构是这样子的:

从代码实现和示例图上我们可以发现,Redis中有两个哈希表

  • ht[0]:用于存放真实key-vlaue数据
  • ht[1]:用于扩容(rehash)

Redis中哈希算法和哈希冲突跟Java实现的差不多,它俩差异就是:

  • Redis哈希冲突时:是将新节点添加在链表的表头
  • JDK1.8后,Java在哈希冲突时:是将新的节点添加到链表的表尾

rehash的过程

下面来具体讲讲Redis是怎么rehash的,因为我们从上面可以明显地看到,Redis是专门使用一个哈希表来做rehash的。这跟Java一次性直接rehash是有区别的。

在对哈希表进行扩展或者收缩操作时,rehash过程并不是一次性地完成的,而是渐进式地完成的。

Redis在rehash时采取渐进式的原因:数据量如果过大的话,一次性rehash会有庞大的计算量,这很可能导致服务器一段时间内停止服务

Redis具体是rehash时这么干的:

  1. 在字典中维持一个索引计数器变量rehashidx,并将设置为0,表示rehash开始。
  2. 在rehash期间每次对字典进行增加、查询、删除和更新操作时,除了执行指定命令外;还会将ht[0]中rehashidx索引上的值rehash到ht[1],操作完成后rehashidx+1。
  3. 字典操作不断执行,最终在某个时间点,所有的键值对完成rehash,这时将rehashidx设置为-1,表示rehash完成
  4. 在渐进式rehash过程中,字典会同时使用两个哈希表ht[0]和ht[1],所有的更新、删除、查找操作也会在两个哈希表进行。例如要查找一个键的话,服务器会优先查找ht[0],如果不存在,再查找ht[1],诸如此类。此外当执行新增操作时,新的键值对一律保存到ht[1],不再对ht[0]进行任何操作,以保证ht[0]的键值对数量只减不增,直至变为空表。

跳跃表(shiplist)

跳跃表(shiplist)是实现sortset(有序集合)的底层数据结构之一。

Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成。其中zskiplist保存跳跃表的信息(表头,表尾节点,长度),zskiplistNode则表示跳跃表的节点

按照惯例,我们来看看zskiplistNode跳跃表节点的结构是怎么样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typeof struct zskiplistNode {
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
// 成员对象
robj *obj;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;

zskiplistNode的对象示例图(带有不同层高的节点):

一个完整的跳跃表如下:
跳跃表节点的示例图

zskiplist的结构如下:

1
2
3
4
5
6
7
8
typeof struct zskiplist {
// 表头节点,表尾节点
struct skiplistNode *header,*tail;
// 表中节点数量
unsigned long length;
// 表中最大层数
int level;
} zskiplist;

整数集合(intset)

整数集合是set(集合)的底层数据结构之一。当一个set(集合)只包含整数值元素,并且元素的数量不多时,Redis就会采用整数集合(intset)作为set(集合)的底层实现。

整数集合(intset)保证了元素是不会出现重复的,并且是有序的(从小到大排序),intset的结构是这样子的:

1
2
3
4
5
6
7
8
typeof struct intset {
// 编码方式
unit32_t encoding;
// 集合包含的元素数量
unit32_t lenght;
// 保存元素的数组
int8_t contents[];
} intset;

intset示例图

说明:虽然intset结构将contents属性声明为int8_t类型的数组,但实际上contents数组并不保存任何int8_t类型的值,contents数组的真正类型取决于encoding属性的值

  • INTSET_ENC_INT16
  • INTSET_ENC_INT32
  • INTSET_ENC_INT64

从编码格式的名字我们就可以知道,16,32,64编码对应能存放的数字范围是不一样的。16明显最少,64明显最大。

如果本来是INTSET_ENC_INT16的编码,想要存放大于INTSET_ENC_INT16编码能存放的整数值,此时就得编码升级(从16升级成32或者64)。步骤如下:

  • 1)根据新元素类型拓展整数集合底层数组的空间并为新元素分配空间。
  • 2)将底层数组现有的所以元素都转换成与新元素相同的类型,并将类型转换后的元素放到正确的位上,需要维持底层数组的有序性质不变。
  • 3)将新元素添加到底层数组。

另外一提:只支持升级操作,并不支持降级操作

压缩列表(ziplist)

压缩列表(ziplist)是list和hash的底层实现之一。如果list的每个都是小整数值,或者是比较短的字符串,压缩列表(ziplist)作为list的底层实现。

压缩列表(ziplist)是Redis为了节约内存而开发的,是由一系列的特殊编码的连续内存块组成的顺序性数据结构。

压缩列表结构图例

节点的结构图

压缩列表从表尾节点倒序遍历,首先指针通过zltail偏移量指向表尾节点,然后通过指向节点记录的前一个节点的长度依次向前遍历访问整个压缩列表

CATALOG
  1. 1. SDS简单动态字符串
    1. 1.1. 使用SDS的好处
  2. 2. 链表
    1. 2.1. Redis链表的特性
  3. 3. 哈希表
    1. 3.1. rehash的过程
  4. 4. 跳跃表(shiplist)
  5. 5. 整数集合(intset)
  6. 6. 压缩列表(ziplist)