深入浅出Redis-redis底层数据结构
Redis 是一个基于键值对(key-value)的分布式存储系统,与Memcached类似,却优于Memcached的一个高性能的key-value数据库。
在《Redis设计与实现》这样描述:
Redis 数据库里面的每个键值对(key-value) 都是由对象(object)组成的:
数据库键总是一个字符串对象(string object);
数据库的值则可以是字符串对象、列表对象(list)、哈希对象(hash)、集合对象(set)、有序集合(sort set)对象这五种对象中的其中一种。
我们为什么会说Redis 优于Memcached 呢?
因为Redis 的出现,丰富了memcached 中key-value的存储不足,在部分场合可以对关系数据库起到很好的补充作用,而且这些数据类型都支持push/pop、add/remove及取交集并集和差集及更丰富的操作,而且这些操作都是原子性的。
我们今天探讨的并不是Redis 中value 的数据类型,而是他们的具体实现——底层数据类型。
底层数据结构有一下数据类型:
- 简单动态字符串(SDS simple dynamic string)
- 链表(linkedlist)
- 字典(hashtable)
- 跳跃表(skiplist)
- 整数集合(intSet)
- 压缩列表(ziplist)
也就是说,我们所使用的五种数据类型,是由以上6种底层数据类型实现的。
Redis 是一个开源的使用ANSI C语言编写的key-value 数据库.
以下是五种value类型与Redis底层C语言实现的6种底层实现类型的对应关系。
五种value类型 | 对应底层实现类型 |
---|---|
字符串: string | SDS |
集合: set | intSet/hashtable |
列表: list | ziplist/linkedlist |
哈希: hash | ziplist/hashtable |
有序集合:zset | ziplist/skiplist |
接下来我们会一步一步的探讨这些数据结构有什么特点,以及他们是如何构成我们所使用的value 数据类型。
1 简单动态字符串(simple dynamic string)SDS
Redis中的字符串并不是直接使用的C语言的字符串,而是自定义一个SDS类型,即Redis默认的字符串类型就是SDS。
如下,msg和”hello world”二者都是字符串对象,底层实现都是保存一条SDS类型的数据。
redis>SET msg "hello world"
OK
除了用来保存字符串以外,SDS还被用作缓冲区(buffer)AOF模块中的AOF缓冲区。
1.1 SDS 的定义
/*
* 保存字符串对象的结构
*/
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
len: 用于记录buf 中已经使用的空间长度(下图数据的长度为5)
free: 用于记录buf 中还空余的空间(初次分配空间,一般没有空余,在对字符串修改的时候,会有剩余空间出现)
buf: 字符数组,用于记录我们的字符串(记录Redis)
1.2 sds对比c语言string的优势
- 在Redis中,不是靠空字符来判断字符串的结束的,而是通过len这个属性。那么,即便是中间出现了空字符对于SDS来说,读取该字符仍然是可以的
- 获取字符串长度, O(1)
- Redis 中SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性:
当我们需要对一个SDS 进行修改的时候,redis 会在执行拼接操作之前,预先检查给定SDS 空间是否足够,如果不够,会先拓展SDS 的空间,然后再执行拼接操作
- 减少修改字符串时带来的内存重分配次数
- 特殊字符判读结束
2 链表(linkedlist)
当一个列表键包含了数量较多的元素,又或者列表中包含的元素都是比较长的字符串时,Redis 就会使用链表作为列表键的底层实现。
多个链表节点组成的双端链表.
2.1 链表的数据结构
每个链表节点使用一个 listNode结构表示(adlist.h/listNode):
typedef struct listNode{
struct listNode *prev;
struct listNode * next;
void * value;
}
双端链表: 多个链表节点组成的双端链表
2.2 列表list基于链表的定义
数据定义:
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三个属性为节点值设置类型特定函数。
3 字典(hashtable)
Redis中键值对(k-v)的存储和hash类型数据都是用hashtable实现。
如SET msg “hello world”,底层就是存储了一个(“msg”, “hello world”)的hashtable数据。
3.1 hashtable底层定义(哈希表和哈希表节点)
hashtable的底层结构是 数组 + 链表的形式;
一个空的字典结构如图所示:
数据是存在dictEntry数组中,然后以链表形式连接。
3.1.1 哈希表定义(数组)
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码,用于计算索引值
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}
3.1.2 哈希表节点(dictEntry)
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 想成一个链表。
注意如图,key是唯一的,不存在重复,只是两个key的hash值可能重复,所以数组索引可能一直,此时使用链地址法存放。
3 redis hash结构
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privedata;
// 哈希表
dictht ht[2];
// rehash 索引
in trehashidx;
}
4 跳跃表(skiplist)
总结
- 跳跃表是有序集合的底层实现之一
- 主要有zskiplist 和zskiplistNode两个结构组成
- 每个跳跃表节点的层高都是1至32之间的随机数
- 在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的对象必须是唯一的
- 节点按照分值的大小从大到小排序,如果分值相同,则按成员对象大小排序
4.1 什么是跳跃表?
如图,是跳跃表的存储结构,总结几点:
1 skiplist结构:
1. 提取极限: 同一层只有两个节点时,就没有比较的意义了
2. 每一层节点数是前一层的一般,所以添加节点时会判断是否提取(抛硬币)
2 如何插入?
新节点和各层索引节点逐一比较,确定原链表的插入位置。O(logN)
3 如何删除?
删除每一层的该节点即可,如果某一层只剩下该节点,那就干掉整个一层。
4 新节点是否提升为上一级索引?
利用抛硬币的随机方式,决定新节点是否提升为上一级索引。结果为“正”则提升并继续抛硬币,结果为“负”则停止。O(logN)
因为跳跃表删除和添加的节点是不可预测的,很难用一种有效的算法保证跳跃表的索引部分始终均匀。
随机抛硬币的方法虽然不能保证索引绝对均匀分布,却可以让大体趋于均匀。
5 skiplist和平衡树
skiplist的有点事维护平衡的成本比较低,完全是依靠随机。
二叉查找树在多次插入删除后,需要Rebalance来重新来调整结构平衡。
4.2 redis skiplist实现
Redis中使用跳跃表结构的有两个:
有序集合zset 和 在集群节点中用作内部数据结构。
4.2.1 跳跃表的数据结构定义
如下图,Redis 的跳跃表主要由两部分组成:zskiplist(链表)和zskiplistNode(节点)
Redis的跳跃表实现与传统跳跃表定义有三点不同:
- 允许重复分数;
- 排序不止根据分数,还可能根据成员对象(当分数相同时);
- 有一个前继指针,因此在第1层,就形成了一个双向链表,从而可以方便的从表尾向表头遍历,用于zrevrange命令的实现。
1 zskiplist
typedef struct zskiplist {
//表头节点和表尾节点
structz skiplistNode *header,*tail;
//表中节点数量
unsigned long length;
//表中层数最大的节点的层数
int level;
}zskiplist;
- header :指向跳跃表的表头节点。
- tail :指向跳跃表的表尾节点。
- level :记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)。
- length :记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)。
2 zskiplistNode
typedef struct zskiplistNode{
//分值
double score;
//成员对象
robj *obj;
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
} level[];
//后退指针
struct zskiplistNode *backward;
}
4.2.2 zskiplistNode属性成员解析
1、分值(double score)和成员对象(robj obj):(zset的value值)
obj是该结点的成员对象指针,score是该对象的分值,是一个浮点数,跳跃表中的所有结点,都是根据score从小到大来排序的。
成员对象obj指向一个字符串,这个字符串对象保存着一个SDS值.
同一个跳跃表中,各个结点保存的成员对象必须是唯一的,分值可以相同。
2、 节点之间关联结构实现:
1 zskiplistLevel level[] 数组:
如下图:
level数组对应的是该节点的层次信息,是一个数组,因为一个节点可能对应多个层次(翻硬币),很容易理解。
1、前进指针: level[i].forward,表示该节点所在层次的下一个节点.
如下图节点5在L1/L2/L3三层分布,
则节点5的level[1].forward是none,level[2].forward指向7,level[3].forward指向6
2、跨度:level[i].span 用于记录forward节点和当前节点的距离
如5的level[3].forward指向6,span是1;level[2].forward指向7,span是2;
如上图:
2、后退指针:backward 节点中用 BW 字样标记节点的后退指针,它指向位于当前节点的前一个节点。
这个并不是层次的,而是相邻查询。
5 整数集合(intSet)
整数集合是Set的底层实现之一,当一个集合中只包含整数,且这个集合中的元素数量不多时,redis就会使用整数集合intset作为集合的底层实现。
5.1 intSet结构定义
intset将数组定义为int8_t,但实际上数组保存的元素类型取决于encoding
typedef struct intset{
//编码方式
uint32_t enconding;
// 集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
}
5.2 升级
问题: intset有默认的enconding方式(intset_enc_int16),如果存储编码方式不同的数据时,就需要使用redis中的升级策略解决
Intset 中升级整数集合并添加新元素共分为三步进行:
- 根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间
- 将底层数组现有的所有元素都转换成新的编码格式,重新分配空间
- 将新元素加入到底层数组中
优势:
- 提升灵活性
- 节约内存
5.3 总结
- 整数集合是集合建的底层实现之一
- 整数集合的底层实现为数组,这个数组以有序,无重复的范式保存集合元素,在有需要时,程序会根据新添加的元素类型改变这个数组的类型
- 升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存
- 整数集合只支持升级操作,不支持降级操作
6 压缩列表(ziplist)
ziplist是redis list/hash/zset的实现之一。
6.1 使用场景
-
list:
当一个list只把含少量元素,并且每个列表元素要么就是小整数,要么就是长度比较短的字符串, 那么Redis 就会使用压缩列表来做列表键的底层实现。
-
hash:
当一个哈希键只包含少量键值对,并且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串, 那么Redis就会使用压缩列表来做哈希键的底层实现。
-
zset:
1) zset会根据zadd命令添加的第一个元素的长度大小来选择编码方式,满足zset_max_ziplist_entries的值不为0, 第一个元素的长度小于server.zset_max_ziplist_value,否则就使用skiplist。 2) 当待新加的新的字符串长度超过zset_max_ziplist_value(默认值64)时 或者ziplist保存的节点数量超过server.zset_max_ziplist_entries(默认值128)时使用skiplist。
6.2 ziplist结构定义
6.2.1 debug object key
可以用过debug object key 来查看redis数据存储使用的数据结构。
> zadd programmings 1.0 go 2.0 python 3.0 java
(integer) 3
> debug object programmings
Value at:0x7fec2de00020 refcount:1 encoding:ziplist serializedlength:36 lru:6022374 lru_seconds_idle:6 > hmset books go fast python slow java fast
OK
> debug object books
Value at:0x7fec2de000c0 refcount:1 encoding:ziplist serializedlength:48 lru:6022478 lru_seconds_idle:1
debug object 输出的 encoding 字段都是 ziplist,这就表示内 部采用压缩列表结构进行存储。
6.2.1 结构定义
struct ziplist<T> {
int32 zlbytes; // 整个压缩列表占用字节数
int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量,用于快速定位到最后一个节点
int16 zllength; // 元素个数
T[] entries; // 元素内容列表,挨个挨个紧凑存储
int8 zlend; // 标志压缩列表的结束,值恒为 0xFF
}
struct entry {
int<var> prevlen; // 前一个 entry 的字节长度
int<var> encoding; // 元素类型编码
optional byte[] content; // 元素内容
}
重点记忆:结合图
- ztail_offset: 用来快速定位到最后一个元素,然后倒着遍历(实现双向遍历)
- prevlen: 前一个 entry 的字节长度,当压缩列表倒着遍历时,需要通过这个字段来快速定位到下一个元素的位置。
- encoding: Redis 通过这个字段的前缀位来识别具体存储的数据形式.(为了节约存储空间)
6.2.2 操作
1 增加元素
因为 ziplist 都是紧凑存储,没有冗余空间 (对比一下 Redis 的字符串结构)。意味着插入一个新的元素就需要调用 realloc 扩展内存。
取决于内存分配器算法 和 当前的 ziplist 内存大小,realloc 可能会重新分配新的内存空间,
并将之前的内容一次性拷贝到新的地址,也可能在原有的地址上进行扩展,这时就不需要进行旧内容的内存拷贝。
如果 ziplist 占据内存太大,重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist 不适合存储大型字符串,存储的元素也不宜过多。
2 级联更新
前面提到每个 entry 都会有一个 prevlen 字段存储前一个 entry 的长度。如果内容小于 254 字节, prevlen 用 1 字节存储,否则就是 5 字节。
这意味着如果 某个 entry 经过了修改操作从 253 字节变成了 254 字节,那么它的下一个 entry 的 prevlen 字段就要更新,从 1 个字节扩展到 5 个字节;
如果这个 entry 的长度本来也是 253 字节,那么后面 entry 的 prevlen 字段还得继续更 新。
如果 ziplist 里面每个 entry 恰好都存储了 253 字节的内容,那么第一个 entry 内容的修改就会导致后续所有 entry 的级联更新,这就是一个比较耗费计算资源 的操作。
删除中间的某个节点也可能会导致级联更新,读者可以思考一下为什么? 因为prevlen会变