Redis底层数据结构分析 - Sanarous的博客

Redis底层数据结构分析

Redis 是一个基于键值对(key-value)的分布式存储系统,与 Memcached 类似,却优于 Memcached 的一个高性能的 key-value 数据库。

《Redis设计与实现》这样描述:Redis 数据库里面的每个键值对(key-value) 都是由对象(object)组成的

  1. 数据库键总是一个字符串对象(string object);
  2. 数据库的值则可以是字符串对象、列表对象(list)、哈希对象(hash)、集合对象(set)、有序集合(sort set)对象这五种对象中的其中一种。

我们为什么会说 Redis 优于 Memcached 呢,因为 Redis 的出现,丰富了 memcached 中 key-value 的存储不足,在部分场合可以对关系数据库起到很好的补充作用,而且这些数据类型都支持 push/pop、add/remove 及取交集并集和差集及更丰富的操作,而且这些操作都是原子性的。

在 Redis 中可以使用 object encoding keyname 来判断一个值的类型,示例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
127.0.0.1:6379> set k1  str
OK
127.0.0.1:6379> set k2 123
OK
127.0.0.1:6379> Object encoding k1
"embstr"
127.0.0.1:6379> Object encoding k2
"int"
127.0.0.1:6379> lpush list1 1 2 3
(integer) 3
127.0.0.1:6379> Object encoding list1
"quicklist"
127.0.0.1:6379> hset testhash key1 009
(integer) 1
127.0.0.1:6379> object encoding testhash
"ziplist"
127.0.0.1:6379> hset testhash key2 00ososkskkalalkskskaaakasmasd,jansm,namsnasnda,msn,akdwj,kjallllllaaaaassjjjjjjjjacacascascascmnascaksc,ascmascna,klna,cksa,cksans,can,scamcs9
(integer) 1
127.0.0.1:6379> object encoding testhash
"hashtable"
127.0.0.1:6379>

那么 Redis 中基本数据结构有哪些呢?我们总结一下发现有如下这些:

数据结构定义常量
整数类型REDIS_ENCODING_INT“int”
embstr字符串类型REDIS_ENCODING_EMBSTR“embstr”
简单动态字符串REDIS_ENCODING_RAW“raw”
字典类型REDIS_ENCODING_HT“hashtable”
双端链表REDIS_ENCODING_LINKEDLIST“linkedlist”
压缩列表REDIS_ENCODING_ZIPLIST“ziplist”
整数集合REDIS_ENCODING_INTSET“intset”
跳表和字典REDIS_ENCODING_SKIPLIST“skiplist”

这些基本数据结构跟 Redis 数据类型对应如下:

数据类型数据结构
stringraw、embstr、int
listquicklist
hashziplist、hashtable
setintset、hashtable
zsetziplist、skiplist

下面我们依次分析基本数据结构原理。

SDS(Simple Dynamic String) 简单动态字符串

Redis 是一个开源的使用 ANSI C 语言编写的 key-value 数据库,我们可能会较为主观的认为 Redis 中的字符串就是采用了 C 语言中的传统字符串表示,但其实不然,Redis 没有直接使用 C 语言传统的字符串表示,而是自己构建了一种名为简单动态字符串(simple dynamic string SDS)的抽象类型,并将 SDS 用作 Redis 的默认字符串表示:

1
2
redis>SET msg "hello world"
OK

设置一个key = msg,value = hello world 的新键值对,他们底层是数据结构将会是:

  • 键(key)是一个字符串对象,对象的底层实现是一个保存着字符串 “msg” 的 SDS;
  • 值(value)也是一个字符串对象,对象的底层实现是一个保存着字符串 “hello world” 的 SDS

SDS 的结构定义如下:

1
2
3
4
5
6
7
8
9
10
11
struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;

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

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

其中参数意义:

  1. len 变量,用于记录 buf 中已经使用的空间长度(这里指出 Redis 的长度为 5)
  2. free 变量,用于记录 buf 中还空余的空间(初次分配空间,一般没有空余,在对字符串修改的时候,会有剩余空间出现)
  3. buf 字符数组,用于记录我们的字符串(记录 Redis)

SDS 和 C 字符串的区别

传统的 C 字符串 使用长度为 N+1 的字符串数组来表示长度为N 的字符串,这样做在获取字符串长度,字符串扩展等操作的时候效率低下。C 语言使用这种简单的字符串表示方式,并不能满足 Redis 对字符串在安全性、效率以及功能方面的要求 。

获取字符串长度(SDS O(1)/C 字符串 O(n)

传统的 C 字符串 使用长度为 N+1 的字符串数组来表示长度为 N 的字符串,所以为了获取一个长度为 C 字符串的长度,必须遍历整个字符串。

和 C 字符串不同,SDS 的数据结构中,有专门用于保存字符串长度的变量,我们可以通过获取 len 属性的值,直接知道字符串长度。

杜绝缓冲区溢出

C 字符串 不记录字符串长度,除了获取的时候复杂度高以外,还容易导致缓冲区溢出。

假设程序中有两个在内存中紧邻着的 字符串 s1 和 s2,其中 s1 保存了字符串 “redis”, s2 则保存了字符串 “MongoDb”:

如果我们现在将 s1 的内容修改为 redis cluster,但是又忘了重新为 s1 分配足够的空间,这时候就会出现以下问题:

我们可以看到,原本 s2 中的内容已经被 s1 的内容给占领了,s2 现在为 cluster,而不是 Mongodb。

Redis 中 SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性:当我们需要对一个SDS 进行修改的时候,redis 会在执行拼接操作之前,预先检查给定 SDS 空间是否足够,如果不够,会先拓展 SDS 的空间,然后再执行拼接操作 。

上述操作有点类似于 Java 中的 ArrayList 封装数组的操作。

减少修改字符串时带来的内存重分配次数

C语言字符串在进行字符串的扩充和收缩的时候,都会面临着内存空间的重新分配问题。

  1. 字符串拼接会产生字符串的内存空间的扩充,在拼接的过程中,原来的字符串的大小很可能小于拼接后的字符串的大小,那么这样的话,就会导致一旦忘记申请分配空间,就会导致内存的溢出。
  2. 字符串在进行收缩的时候,内存空间会相应的收缩,而如果在进行字符串的切割的时候,没有对内存的空间进行一个重新分配,那么这部分多出来的空间就成为了内存泄露。

举个例子:我们需要对下面的 SDS进行拓展,则需要进行空间的拓展,这时候 redis 会将 SDS 的长度修改为 13字节,并且将未使用空间同样修改为 1 字节

因为在上一次修改字符串的时候已经拓展了空间,再次进行修改字符串的时候会发现空间足够使用,因此无须进行空间拓展

通过这种预分配策略,SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次

惰性空间释放

我们在观察 SDS 的结构的时候可以看到里面的 free 属性,是用于记录空余空间的。我们除了在拓展字符串的时候会使用到 free 来进行记录空余空间以外,在对字符串进行收缩的时候,我们也可以使用 free 属性来进行记录剩余空间,这样做的好处就是避免下次对字符串进行再次修改的时候,需要对字符串的空间进行拓展。

然而,我们并不是说不能释放 SDS 中空余的空间,SDS 提供了相应的 API,让我们可以在有需要的时候,自行释放 SDS 的空余空间。

通过惰性空间释放,SDS 避免了缩短字符串时所需的内存重分配操作,并未将来可能有的增长操作提供了优化。

二进制安全

C 字符串中的字符必须符合某种编码,并且除了字符串的末尾之外,字符串里面不能包含空字符,否则最先被程序读入的空字符将被误认为是字符串结尾,这些限制使得 C 字符串只能保存文本数据,而不能保存想图片,音频,视频,压缩文件这样的二进制数据。

但是在 Redis 中,不是靠空字符来判断字符串的结束的,而是通过 len 这个属性。那么,即便是中间出现了空字符对于 SDS 来说,读取该字符仍然是可以的。

兼容部分 C 字符串函数

虽然 SDS 的 API 都是二进制安全的,但他们一样遵循 C 字符串以空字符串结尾的惯例。

总结
C 字符串SDS
获取字符串长度的复杂度为O(N)获取字符串长度的复杂度为O(1)
API 是不安全的,可能会造成缓冲区溢出API 是安全的,不会造成缓冲区溢出
修改字符串长度N次必然需要执行N次内存重分配修改字符串长度N次最多执行N次内存重分配
只能保存文本数据可以保存二进制数据和文本文数据
可以使用所有<String.h>库中的函数可以使用一部分<string.h>库中的函数

链表

概述

链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度。

链表在 Redis 中的应用非常广泛,比如列表键的底层实现之一就是链表。当一个列表键包含了数量较多的元素,又或者列表中包含的元素都是比较长的字符串时,Redis 就会使用链表作为列表键的底层实现。

链表的数据结构

每个链表节点使用一个 listNode 结构表示(adlist.h/listNode):

1
2
3
4
5
typedef struct listNode{
struct listNode *prev;
struct listNode * next;
void * value;
}

多个链表组成的双端链表:

我们可以通过直接操作 list 来操作链表会更加方便:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct list{
//表头节点
listNode * head;
//表尾节点
listNode * tail;
//链表长度
unsigned long len;
//节点值复制函数
void *(*dup) (void *ptr);
//节点值释放函数
void (*free) (void *ptr);
//节点值对比函数
int (*match)(void *ptr, void *key);
}

list 组成的结构图:

链表的特性

  • 双端:链表节点带有 prev 和 next 指针,获取某个节点的前置节点和后置节点的时间复杂度都是 O(n)
  • 无环:表头节点的 prev 指针和表尾节点的 next 都指向 NULL,对立案表的访问时以 NULL为截止
  • 表头和表尾:因为链表带有 head指针和 tail 指针,程序获取链表头结点和尾节点的时间复杂度为 O(1)
  • 长度计数器:链表中存有记录链表长度的属性 len
  • 多态:链表节点使用 void* 指针来保存节点值,并且可以通过 list 结构的 dup 、 free、 match 三个属性为节点值设置类型特定函数。

字典

概述

字典,又称为符号表(symbol table)、关联数组(associative array)或映射(map),是一种用于保存键值对的抽象数据结构。 

在字典中,一个键(key)可以和一个值(value)进行关联,字典中的每个键都是独一无二的。在 C 语言中,并没有这种数据结构,但是 Redis 中构建了自己的字典实现

举个简单的例子:

1
2
redis > SET msg "hello world"
OK

创建这样的键值对(“msg”,“hello world”)在数据库中就是以字典的形式存储 。

字典的定义

哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义:

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;

//哈希表大小掩码,用于计算索引值
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}

一个空的字典的结构图如下:

我们可以看到,在结构中存有指向 dictEntry 数组的指针,而我们用来存储数据的空间既是 dictEntry

哈希表节点

dictEntry 结构定义:

1
2
3
4
5
6
7
8
9
10
11
typeof struct dictEntry{
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}
struct dictEntry *next;
}

在数据结构中,我们清楚 key 是唯一的,但是我们存入里面的 key 并不是直接的字符串,而是一个 hash 值,通过 hash 算法,将字符串转换成对应的 hash 值,然后在 dictEntry 中找到对应的位置。

这时候我们会发现一个问题,如果出现 hash 值相同的情况怎么办?Redis 采用了链地址法:

当 k1 和 k0 的 hash 值相同时,将 k1中的 next 指向 k0 形成一个链表。

字典
1
2
3
4
5
6
7
8
9
10
11
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privedata;
// 哈希表
dictht ht[2];
// rehash 索引
in trehashidx;

}

type 属性 和 privdata 属性是针对不同类型的键值对,为创建多态字典而设置的。

ht 属性是一个包含两个项(两个哈希表)的数组

普通状态下的字典:

解决哈希冲突

在上述分析哈希节点的时候我们有讲到:在插入一条新的数据时,会进行哈希值的计算,如果出现了 hash值相同的情况,Redis 中采用了连地址法(separate chaining)来解决键冲突。每个哈希表节点都有一个 next 指针,多个哈希表节点可以使用next 构成一个单向链表,被分配到同一个索引上的多个节点可以使用这个单向链表连接起来解决 hash 值冲突的问题。

举个例子:

现在哈希表中有以下的数据:k0 和 k1

我们现在要插入 k2,通过 hash 算法计算到 k2 的 hash 值为 2,即我们需要将 k2 插入到 dictEntry[2] 中:

在插入后我们可以看到,dictEntry 指向了 k2,k2 的 next 指向了 k1,从而完成了一次插入操作(这里选择表头插入是因为哈希表节点中没有记录链表尾节点位置)

Rehash

随着对哈希表的不断操作,哈希表保存的键值对会逐渐的发生改变,为了让哈希表的负载因子维持在一个合理的范围之内,我们需要对哈希表的大小进行相应的扩展或者压缩,这时候,我们可以通过 rehash(重新散列)操作来完成。

目前的哈希表状态

我们可以看到,哈希表中的每个节点都已经使用到了,这时候我们需要对哈希表进行拓展。

为哈希表分配空间

哈希表空间分配规则:

  1. 如果执行的是拓展操作,那么ht[1] 的大小为第一个大于等于ht[0] 的2的n次幂
  2. 如果执行的是收缩操作,那么ht[1] 的大小为第一个大于等于ht[0] 的2的n次幂

因此这里我们为 ht[1] 分配 空间为 8

数据转移

将 ht[0] 中的数据转移到 ht[1] 中,在转移的过程中,需要对哈希表节点的数据重新进行哈希值计算

数据转移后的结果:

释放ht[0]

将 ht[0] 释放,然后将 ht[1] 设置成 ht[0],最后为 ht[1] 分配一个空白哈希表:

渐进式 hash

上面我们说到,在进行拓展或者压缩的时候,可以直接将所有的键值对 rehash 到 ht[1] 中,这是因为数据量比较小。在实际开发过程中,这个 rehash 操作并不是一次性、集中式完成的,而是分多次、渐进式地完成的。

渐进式 rehash 的详细步骤:

  1. 为 ht[1] 分配空间,让字典同时持有 ht[0] 和 ht[1] 两个哈希表

  2. 在几点钟维持一个索引计数器变量 rehashidx,并将它的值设置为 0,表示 rehash 开始

  3. 在 rehash 进行期间,每次对字典执行 CRUD 操作时,程序除了执行指定的操作以外,还会将 ht[0] 中的数据 rehash 到 ht[1] 表中,并且将 rehashidx 加一

  4. 当 ht[0] 中所有数据转移到 ht[1] 中时,将 rehashidx 设置成 -1,表示 rehash 结束

采用渐进式 rehash 的好处在于它采取分而治之的方式,避免了集中式 rehash 带来的庞大计算量。

跳跃表

概述

跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳跃表是一种随机化的数据,跳跃表以有序的方式在层次化的链表中保存元素,效率和平衡树媲美 ——查找、删除、添加等操作都可以在对数期望时间下完成,并且比起平衡树来说,跳跃表的实现要简单直观得多。

Redis 只在两个地方用到了跳跃表,一个是实现有序集合键,另外一个是在集群节点中用作内部数据结构

跳跃表的定义

我们先来看一下一整个跳跃表的完整结构:

Redis 的跳跃表 主要由两部分组成:zskiplist(链表)和 zskiplistNode (节点)

zskiplistNode(节点) 数据结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode{
   //层
struct zskiplistLevel{
     //前进指针
struct zskiplistNode *forward;
    //跨度
unsigned int span;
} level[];
  //后退指针
struct zskiplistNode *backward;
  //分值
double score;
  //成员对象
robj *obj;
}
  1. 层:level 数组可以包含多个元素,每个元素都包含一个指向其他节点的指针。
  2. 前进指针:用于指向表尾方向的前进指针
  3. 跨度:用于记录两个节点之间的距离
  4. 后退指针:用于从表尾向表头方向访问节点
  5. 分值和成员:跳跃表中的所有节点都按分值从小到大排序。成员对象指向一个字符串,这个字符串对象保存着一个 SDS 值
zskiplist 数据结构
1
2
3
4
5
6
7
8
9
typedef struct zskiplist {
//表头节点和表尾节点
structz skiplistNode *header,*tail;
//表中节点数量
unsigned long length;
//表中层数最大的节点的层数
int level;

}zskiplist;

从结构图中我们可以清晰的看到,header,tail 分别指向跳跃表的头结点和尾节点。level 用于记录最大的层数,length 用于记录我们的节点数量。

总结

  •  跳跃表是有序集合的底层实现之一
  • 主要有 zskiplist 和 zskiplistNode 两个结构组成
  • 每个跳跃表节点的层高都是 1 至 32 之间的随机数
  • 在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的对象必须是唯一的
  • 节点按照分值的大小从大到小排序,如果分值相同,则按成员对象大小排序

整数集合(Intset)

概述

《Redis 设计与实现》 中这样定义整数集合:“整数集合是集合建的底层实现之一,当一个集合中只包含整数,且这个集合中的元素数量不多时,redis 就会使用整数集合 intset 作为集合的底层实现。”

我们可以这样理解整数集合,他其实就是一个特殊的集合,里面存储的数据只能够是整数,并且数据量不能过大。

整数集合的实现

1
2
3
4
5
6
7
8
9
typedef struct intset{
//编码方式
uint32_t enconding;
// 集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];

}

我们观察一下一个完成的整数集合结构图:

  1. encoding:用于定义整数集合的编码方式
  2. length:用于记录整数集合中变量的数量
  3. contents:用于保存元素的数组,虽然我们在数据结构图中看到,intset 将数组定义为 int8_t,但实际上数组保存的元素类型取决于 encoding

整数集合的升级

在上述数据结构图中我们可以看到,intset 在默认情况下会帮我们设定整数集合中的编码方式,但是当我们存入的整数不符合整数集合中的编码格式时,就需要使用到Redis 中的升级策略来解决

Intset 中升级整数集合并添加新元素共分为三步进行:

  1. 根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间
  2. 将底层数组现有的所有元素都转换成新的编码格式,重新分配空间
  3. 将新元素加入到底层数组中

比如,我们现在有如下的整数集合:

我们现在需要插入一个 32 位的整数,这显然与整数集合不符合,我们将进行编码格式的转换,并为新元素分配空间:

第二步,将原有数据他们的数据类型转换为与新数据相同的类型:(重新分配空间后的数据)

第三部,将新数据添加到数组中:

整数集合升级的好处:

  • 提升灵活性
  • 节约内存

总结

  1. 整数集合是集合建的底层实现之一
  2. 整数集合的底层实现为数组,这个数组以有序,无重复的范式保存集合元素,在有需要时,程序会根据新添加的元素类型改变这个数组的类型
  3. 升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存
  4. 整数集合只支持升级操作,不支持降级操作

压缩列表

概述

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只把汗少量列表项,并且每个列表项要么就是小整数,要么就是长度比较短的字符串,那么 Redis 就会使用压缩列表来做列表键的底层实现。

压缩列表的构成

一个压缩列表的组成如下:

  1. zlbytes:用于记录整个压缩列表占用的内存字节数
  2. zltail:记录要列表尾节点距离压缩列表的起始地址有多少字节
  3. zllen:记录了压缩列表包含的节点数量。
  4. entryX:要说列表包含的各个节点
  5. zlend:用于标记压缩列表的末端

总结

  1. 压缩列表是一种为了节约内存而开发的顺序型数据结构
  2. 压缩列表被用作列表键和哈希键的底层实现之一
  3. 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值
  4. 添加新节点到压缩列表,可能会引发连锁更新操作。
如果这篇文章对您很有帮助,不妨
-------------    本文结束  感谢您的阅读    -------------
0%