前言

在上一篇文章 Redis的几种数据类型 我们学习了Redis的value的几种数据类型,string字符串类型、list列表类型、set集合类型、sortedset(zset)有序集合类型、hash类型等。本篇我们来深入研究下这些数据结构的底层实现,从而对Redis有更深层次的认识。

Redis底层数据结构

Redis没有表的概念,Redis实例所对应的db以编号区分,db本身就是key的命名空间。 比如:user:1000作为key值,表示在user这个命名空间下id为1000的元素,类似于user表的id=1000的 行。

对于常见的几种数据类型,分别对应的底层实现如下图:

对于每种数据类型,redis都有不止一种的实现方式,目的是为了提高效率:

  • 连续内存空间 - 数据量少时,节省空间。(占用空间小于某个阈值(默认512kb),元素个数少于某个阈值(默认64个))
  • 正常实现 - 数据量大时。

RedisDB结构

Redis中存在“数据库”的概念,该结构由redis.h中的redisDb定义。 当redis 服务器初始化时,会预先分配 16 个数据库 所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中 redisClient中存在一个名叫db的指针指向当前使用的数据库 RedisDB结构体源码:

1
2
3
4
5
6
7
8
9
typedef struct redisDb {
int id; //id是数据库序号,为0-15(默认Redis有16个数据库)
long avg_ttl; //存储的数据库对象的平均ttl(time to live),用于统计
dict *dict; //存储数据库所有的key-value
dict *expires; //存储key的过期时间
dict *blocking_keys; //blpop 存储阻塞key和客户端对象
dict *ready_keys; //阻塞后push 响应阻塞客户端 存储阻塞后push的key和客户端对象
dict *watched_keys; //存储watch监控的的key和客户端对象
} redisDb;

RedisObject结构

Redis中value是一个对象,里面包含了字符串对象、列表对象、哈希对象、集合对象和有序集合对象等。

RedisObject的结构体信息如下:

1
2
3
4
5
6
7
8
9
10
typedef struct redisObject {
unsigned type:4;//类型 五种对象类型
unsigned encoding:4;//编码
void *ptr;//指向底层实现数据结构的指针
//...
int refcount;//引用计数
//...
unsigned lru:LRU_BITS; //LRU_BITS为24bit 记录最后一次被命令程序访问的时间
//...
}robj;

下面我们对其中的变量一一进行介绍:

type

type表示对象的类型,占4位

取值主要有如下几种类型:

REDIS_STRING(字符串)、REDIS_LIST (列表)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有 序集合)。

当我们执行 type 命令时,便是通过读取 RedisObject 的 type 字段获得对象的类型 ,如下所示:

1
2
3
4
5
6
7
8
9
10
127.0.0.1:6379> keys *
1) "hit:1"
2) "user:001"
3) "age"
4) "set:1"
5) "list:1"
127.0.0.1:6379> type age
string
127.0.0.1:6379> type hit:1
zset

字符串对象

C语言: 字符数组 (以"\0" 结尾)

Redis 使用了 SDS(Simple Dynamic String),用于存储字符串和整型数据。

结构体代码:

1
2
3
4
5
6
7
8
struct sdshdr{
//记录buf数组中已使用字节的数量
int len;
//记录 buf 数组中未使用字节的数量
int free;
//字符数组,用于保存字符串
char buf[];
}

示意图如下:

buf[] 的长度=len+free+1

sds在Redis中是实现字符串对象的工具,并且完全取代char*..sds是二进制安全的,它可以存储任意二进制数据,不像C语言字符串那样以‘\0’来标识字符串结束,因为传统C字符串符合ASCII编码,这种编码的操作的特点就是:遇零则止 。即,当读一个字符串时,只要遇到’\0’结尾,就认为到达末尾,就忽略’\0’结尾以后的所有字符。因此,如果传统字符串保存图片,视频等二进制文件,操作文件时就被截断了。

SDS表头的buf被定义为字节数组,因为判断是否到达字符串结尾的依据则是表头的len成员,这意味着它可以存放任何二进制的数据和文本数据,包括’\0’.

SDS 和传统的 C 字符串获得的做法不同,传统的C字符串遍历字符串的长度,遇零则止,复杂度为O(n)。而SDS表头的len成员就保存着字符串长度,所以获得字符串长度的操作复杂度为O(1)

SDS的优势:

1、SDS 在 C 字符串的基础上加入了 free 和 len 字段,获取字符串长度:SDS 是 O(1),C 字符串是 O(n)。

2、 SDS 由于记录了长度,在可能造成缓冲区溢出时会自动重新分配内存,杜绝了缓冲区溢出。

3、可以存取二进制数据,以字符串长度len来作为结束标识

C字符串: \0作为字符串结束的标志,由于二进制数据包括空字符串,所以没有办法存取二进制数据

SDS : 非二进制数据用\0来标识结束,二进制数据用字符串长度来标识,所以可以存二进制数据

总结下SDS的特点是:可动态扩展内存二进制安全快速遍历字符串与传统的C语言字符串类型兼容

SDS的应用场景:存储字符串和整型数据、存储key、AOF缓冲区和用户输入缓冲。

跳跃表

跳跃表是有序集合(sorted-set)的底层实现,效率高,实现简单。

跳跃表的基本思想:将有序链表中的部分节点分层,每一层都是一个有序链表。

查找功能举例:

思路:在查找时优先从最高层开始向后查找,当到达某个节点时,如果next节点值大于要查找的值或next指针 指向null,则从当前节点下降一层继续向后查找。

比如我们要查找元素9,按道理我们需要从头结点开始遍历,一共遍历8个结点才能找到元素9。

我们对这个链表进行分层,如下:

此时我们只需遍历5次找到元素9(红色的线为查找路径)

沿着这个思路,我们继续进行第二次分层:

我们只需遍历4次便能找到元素9

继续第三次分层:

可以发现,此时我们还是需要遍历4次才能找到元素9,跟第二次分层的效果一样。

像上面这种数据结构,就是跳跃表,和二分查找有点类似。

思考一个问题:我们如何确定哪个元素分层,哪个元素不分层呢?

我们上面的例子中9个元素一共分了4层,接近二分之一,是比较理想的跳跃表。

通常我们通过抛硬币(概率为1/2)的方式来确定某个元素是否需要分层。

正面:插入上层

背面:不插入

另一个问题:如何删除某个元素呢

由链表的结构我们知道,只需要删除每层每个链表中的该元素即可。

总结下跳跃表的特点:

  1. 每层都是一个有序链表
  2. 查找次数近似于层数(1/2)
  3. 底层包含所有元素
  4. 空间复杂度 O(n) 扩充了一倍

跳跃表的优势:

  1. 可以快速查找到需要的节点
  2. 可以在O(1)的时间复杂度下,快速获得跳跃表的头节点、尾结点、长度和高度。

应用场景:有序集合的实现

字典

字典dict又称散列表(hash),是用来存储键值对的一种数据结构。 Redis整个数据库是用字典来存储的。(K-V结构) 对Redis进行CURD操作其实就是对字典中的数据进行CURD操作。

Redis字典实现包括:字典(dict)、Hash表(dictht)、Hash表节点(dictEntry) ,他们之间的关系如下:

Hash表(dictht)
1
2
3
4
5
6
typedef struct dictht {
dictEntry **table; // 哈希表数组
unsigned long size; // 哈希表数组的大小
unsigned long sizemask; // 用于映射位置的掩码,值永远等于(size-1)
unsigned long used; // 哈希表已有节点的数量,包含next单链表数据
} dictht;

注意:

  1. hash表的数组初始容量为4,随着k-v存储量的增加需要对hash表数组进行扩容,新扩容量为当前量 的一倍,即4,8,16,32
  2. 索引值=Hash值&掩码值(Hash值与Hash表容量取余)
Hash表节点(dictEntry)
1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry {
void *key; // 键
union { // 值v的类型可以是以下4种类型
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // 指向下一个哈希表节点,形成单向链表 解决hash冲突
} dictEntry;

key字段存储的是键值对中的键 v字段是个联合体,存储的是键值对中的值。 next指向下一个哈希表节点,用于解决hash冲突

示意图如下:

dict字典
1
2
3
4
5
6
7
typedef struct dict {
dictType *type; // 该字典对应的特定操作函数
void *privdata; // 上述类型函数对应的可选参数
dictht ht[2]; /* 两张哈希表,存储键值对数据,ht[0]为原生哈希表,ht[1]为 rehash 哈希表 */
long rehashidx; /*rehash标识 当等于-1时表示没有在rehash,否则表示正在进行rehash操作,存储的值表示hash表 ht[0]的rehash进行到哪个索引值(数组下标)*/
int iterators; // 当前运行的迭代器数量
} dict;

type字段,指向dictType结构体,里边包括了对该字典操作的函数指针 ,源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct dictType {
// 计算哈希值的函数
unsigned int (*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;

Redis字典除了主数据库的K-V数据存储以外,还可以用于:散列表对象、哨兵模式中的主从节点管理等 在不同的应用中,字典的形态都可能不同,dictType是为了实现各种形态的字典而抽象出来的操作函数 (多态)。

完整的Redis字典数据结构如下所示:

字典扩容

字典达到存储上限,需要rehash(扩容)

扩容流程:

说明:

  1. 初次申请默认容量为4个dictEntry,非初次申请为当前hash表容量的一倍。
  2. rehashidx=0表示要进行rehash操作。
  3. 新增加的数据在新的hash表h[1]
  4. 修改、删除、查询在老hash表h[0]、新hash表h[1]中(rehash中)
  5. 将老的hash表h[0]的数据重新计算索引值后全部迁移到新的hash表h[1]中,这个过程称为 rehash。

压缩列表

压缩列表(ziplist)是由一系列特殊编码的连续内存块组成的顺序型数据结构,是一个字节数组,可以包含多个节点(entry)。每个节点可以保存一个字节数组或一个整数。 压缩列表的数据结构如下:

zlbytes:压缩列表的字节长度

zltail:压缩列表尾元素相对于压缩列表起始地址的偏移量

zllen:压缩列表的元素个数

entry1..entryX : 压缩列表的各个节点

zlend:压缩列表的结尾,占一个字节,恒为0xFF(255)

entryX元素的编码结构:

previous_entry_length:前一个元素的字节长度

encoding:表示当前元素的编码

content:数据内容

应用场景

  1. sorted-set和hash元素个数少且是小整数或短字符串(直接使用)
  2. list用快速链表(quicklist)数据结构存储,而快速链表是双向列表与压缩列表的组合。(间接使用)

问题:压缩列表中如何定位第n个元素?

由于压缩列表是连续内存块组成的数据结构,前面几个数据的长度固定,所以我们可以从前往后数,数到存放数据的位置,是起始位置第1个元素,要查找第n个位置的元素, 往后数即可。

整数集合

整数集合(intset)是一个有序的(整数升序)、存储整数的连续存储结构 。

当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内(2^64),使用该结构体存储。

举例如下:

1
2
3
4
5
6
7
8
127.0.0.1:6379> sadd set:001 1 3 5 6 2
(integer) 5
127.0.0.1:6379> object encoding set:001
"intset"
127.0.0.1:6379> sadd set:004 1 100000000000000000000000000 9999999999
(integer) 3
127.0.0.1:6379> object encoding set:004
"hashtable"

intset的结构图如下:

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

应用场景: 可以保存类型为int16_t、int32_t 或者int64_t 的整数值,并且保证集合中不会出现重复元素。

快速列表

快速列表(quicklist)是Redis底层重要的数据结构。是列表的底层实现。(在Redis3.2之前,Redis采 用双向链表(adlist)和压缩列表(ziplist)实现。)在Redis3.2以后结合adlist和ziplist的优势Redis设 计出了quicklist。

举例如下:

1
2
3
4
127.0.0.1:6379> lpush list:001 1 2 5 4 3
(integer) 5
127.0.0.1:6379> object encoding list:001
"quicklist"

先来说下双向链表(adlist),如下图所示:

双向链表优势

  1. 双向:链表具有前置节点和后置节点的引用,获取这两个节点时间复杂度都为O(1)。
  2. 普通链表(单链表):节点类保留下一节点的引用。链表类只保留头节点的引用,只能从头节点插 入删除
  3. 无环:表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结 束。 环状:头的前一个节点指向尾节点
  4. 带链表长度计数器:通过 len 属性获取链表长度的时间复杂度为 O(1)。
  5. 多态:链表节点使用 void* 指针来保存节点值,可以保存各种不同类型的值。

快速列表

quicklist是一个双向链表,链表中的每个节点时一个ziplist结构。quicklist中的每个节点ziplist都能够存 储多个数据元素。

quicklist的结构定义如下:

1
2
3
4
5
6
7
8
typedef struct quicklist {
quicklistNode *head; // 指向quicklist的头部
quicklistNode *tail; // 指向quicklist的尾部
unsigned long count; // 列表中所有数据项的个数总和
unsigned int len; // quicklist节点的个数,即ziplist的个数
int fill : 16; // ziplist大小限定,由list-max-ziplist-size给定(Redis设定)
unsigned int compress : 16; // 节点压缩深度设置,由list-compress-depth给定(Redis设定)
} quicklist;

quicklistNode的结构定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct quicklistNode {
struct quicklistNode *prev; // 指向上一个ziplist节点
struct quicklistNode *next; // 指向下一个ziplist节点
unsigned char *zl; // 数据指针,如果没有被压缩,就指向ziplist结构,反之指向 quicklistLZF结构
unsigned int sz; // 表示指向ziplist结构的总长度(内存占用长度)
unsigned int count : 16; // 表示ziplist中的数据项个数
unsigned int encoding : 2; // 编码方式,1--ziplist,2--quicklistLZF
unsigned int container : 2; // 预留字段,存放数据的方式,1--NONE,2--ziplist
unsigned int recompress : 1; // 解压标记,当查看一个被压缩的数据时,需要暂时解压,标记此参数为 1,之后再重新进行压缩
unsigned int attempted_compress : 1; // 测试相关
unsigned int extra : 10; // 扩展字段,暂时没用
} quicklistNode;

quicklist的数据压缩

quicklist每个节点的实际存储结构为ziplist,这种结构的优势在于节省存储空间。为了进一步降低 ziplist的存储空间,还可以对ziplist进行压缩。

Redis采用的压缩算法是LZF。其基本思想是:数据与前面重复的记录重复位置及长度,不重复的记录原始数据。

应用场景:列表(List)的底层实现、发布与订阅、慢查询、监视器等功能 。

流对象

流对象主要是用作stream的底层实现。stream我们平时用的不对,此处就不做过多研究了。

encoding

encoding 表示对象的内部编码,占 4 位 每个对象有不同的实现编码,Redis 可以根据不同的使用场景来为对象设置不同的编码,大大提高了 Redis 的灵活性和效率。 通过 object encoding 命令,可以查看对象采用的编码方式 ,举例如下:

1
2
3
4
5
6
7
8
9
10
127.0.0.1:6379> keys *
1) "hit:1"
2) "user:001"
3) "age"
4) "set:1"
5) "list:1"
127.0.0.1:6379> object encoding age
"int"
127.0.0.1:6379> object encoding hit:1
"ziplist"

下面我们对不同的 对象常见的几种encoding进行介绍。

String

String 对应int、raw、embstr 三种编码。

int

REDIS_ENCODING_INT(int类型的整数)

1
2
3
4
127.0.0.1:6379> set n1 123
OK
127.0.0.1:6379> object encoding n1
"int"

embstr

REDIS_ENCODING_EMBSTR(编码的简单动态字符串)

用途:编码小字符串(长度小于44个字节 )

1
2
3
4
127.0.0.1:6379> set name:001 zhangfei
OK
127.0.0.1:6379> object encoding name:001
"embstr"

raw

REDIS_ENCODING_RAW (简单动态字符串)

用途:编码大字符串(长度大于44个字节)

1
2
3
4
5
6
127.0.0.1:6379> set address:001
asdasdasdasdasdasdsadasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdas
dasdasdas
OK
127.0.0.1:6379> object encoding address:001
"raw"
encoding描述
raw存储大于 44 个字节的字符串,需要分配两次内存空间(分别为 Redis Object 和 SDS 分配空间)。
embstr存储小于 44 个字节的字符串,只分配一次内存空间(直接在redisObject和 SDS 是连续的)。
int存储 8 个字节的长整型(long,2^63-1)

embstr 与 raw的区别示意图:

SDS扩容策略

字符串在长度小于 1M 之前,扩容空间采用加倍策略,也就是保留 100% 的冗余空间。当长度超过 1M 之后,为了避免加倍后的冗余空间过大而导致浪费,每次扩容只会多分配 1M 大小的冗余空间。

list

redis3.2之前的底层实现是压缩列表(ziplist)与双向链表分别实现的,redis3.2之后的列表的底层实现是quicklist。

对于压缩列表与双向链表的区别,总结如下:

encoding描述
ziplist优点:省空间; 缺点:连锁更新; 牺牲了时间,换空间
linkedlist优点:更新快; 缺点:占用空间大; 牺牲空间,换时间

REDIS_ENCODING_QUICKLIST(快速列表)

1
2
3
4
127.0.0.1:6379> lpush list:001 1 2 5 4 3
(integer) 5
127.0.0.1:6379> object encoding list:001
"quicklist"

hash

散列的编码是字典和压缩列表。

简单总结如下:

**hashtable(字典)**实现hash结构示意图:

dict 结构内部包含两个 hashtable,通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时,需要分配新的 hashtable,然后进行渐进式搬迁,这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后,旧的 hashtable 被删除,新的 hashtable 取而代之。

需要注意两点:

  1. rehash期间,可能需要两个hashtable进行查找

  2. 为什么需要渐进式hash?

    大字典的扩容是比较耗时间的,需要重新申请新的数组,然后将旧字典所有链表中的元素重新挂接到新的数组下面,这是一个O(n)级别的操作,作为单线程的Redis表示很难承受这样耗时的过程。步子迈大了会扯着蛋,所以Redis使用渐进式rehash小步搬迁。虽然慢一点,但是肯定可以搬完。

ziplist实现hash结构示意图:

案例:

dict

REDIS_ENCODING_HT(字典)

当散列表元素的个数比较多或元素不是小整数或短字符串时。

1
2
3
4
5
6
7
127.0.0.1:6379> hmset user:003
username111111111111111111111111111111111111111111111111111111111111111111111111
11111111111111111111111111111111 zhangfei password 111 num
2300000000000000000000000000000000000000000000000000
OK
127.0.0.1:6379> object encoding user:003
"hashtable"

ziplist

REDIS_ENCODING_ZIPLIST(压缩列表)

当散列表元素的个数比较少,且元素都是小整数或短字符串时。

1
2
3
4
127.0.0.1:6379> hmset user name lizh
OK
127.0.0.1:6379> object encoding user
"ziplist"

set

集合的编码是整形集合和字典(hashtable)。

intset简单示意图:

用hashtable实现set时value为空。

intset REDIS_ENCODING_INTSET(整数集合)

当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内(<18446744073709551616)

1
2
3
4
127.0.0.1:6379> sadd set:001 1 3 5 6 2
(integer) 5
127.0.0.1:6379> object encoding set:001
"intset"

dict REDIS_ENCODING_HT(字典)

当Redis集合类型的元素都是整数并且有处在64位有符号整数范围外的元素(>18446744073709551616)

1
2
3
4
127.0.0.1:6379> sadd set:004 1 100000000000000000000000000 9999999999
(integer) 3
127.0.0.1:6379> object encoding set:004
"hashtable"

zset

有序集合的编码是压缩列表跳跃表+字典

压缩列表实现zset的结构示意图如下:

第二种是跳跃表+字典共同来实现zset。这种实现方案下:

  • 和有序性相关的命令,如zrangebyscore,通过skiplist实现
  • 和字典相关的命令,如zrem,通过hashtable实现

ziplist

REDIS_ENCODING_ZIPLIST(压缩列表)

当元素的个数比较少,且元素都是小整数或短字符串时。

1
2
3
4
127.0.0.1:6379> zadd hit:1 100 item1 20 item2 45 item3
(integer) 3
127.0.0.1:6379> object encoding hit:1
"ziplist"

skiplist+dist

REDIS_ENCODING_SKIPLIST(跳跃表+字典)

当元素的个数比较多或元素不是小整数或短字符串时。

1
2
3
4
5
6
127.0.0.1:6379> zadd hit:2 100
item1111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111 20 item2 45 item3
(integer) 3
127.0.0.1:6379> object encoding hit:2
"skiplist"

LRU

lru 记录的是对象最后一次被命令程序访问的时间,( 4.0 版本占 24 位,2.6 版本占 22 位)。

高16位存储一个分钟数级别的时间戳,低8位存储访问计数(lfu:最近访问次数)

lru----> 高16位: 最后被访问的时间

lfu----->低8位:最近访问次数

refcount

refcount 记录的是该对象被引用的次数,类型为整型。

refcount 的作用,主要在于对象的引用计数和内存回收。Redis 为了节省内存,当有一些对象重复出现时,新的程序不会创建新的对象,而是仍然使用原来的对象。

当对象的refcount>1时,称为共享对象。

ptr

ptr 指针指向具体的数据,比如:set hello world,ptr 指向包含字符串 world 的 SDS(Simple Dynamic String)。

总结

我们深入剖析了Redis的底层数据结构,主要对几种type及encoding进行了详细的解读,包含了跳跃表、字典等一些比较深入的数据结构。