redis底层数据结构-CSDN博客

总所周知redis支持五种数据类型String、Hash、List、Set、ZSet。在支持这些复杂数据结构的同时redis不仅需要保证读写的性能还能提供各种微操作比如直接修改Hash字典中的某个field的值或者直接往ZSet中插入某个值redis也能快速地放到它对应顺序的位置那么redis是如何做到的呢。
首先上面所说的操作其实分两步第一步基于key找到对应的value即整个hash字典对象或整个ZSet的对象然后第二步再在hash字典中找到对应的field或者在ZSet中按权重顺序找到对应的位置插入数据。
上面两步也是基于两个不同的数据结构来实现快速访问的第一步是基于全局hash表来实现的所有redis的key->value都是通过这样的方式。第二步则有很多种情况底层的数据结构有这么些种类SDS(simple dynamic string)简单动态字符串、字典dict、压缩列表ziplist、快速列表quickList、inset、跳跃表skiplist对外表现的五种数据类型的底层会对应地使用其中的一种或两种来实现。

一、key的存储结构全局Hash表

Key的存储结构全局hash表读写检索到对应key的位置的时间复杂度都是O(1)。再通过rehash避免key的hash冲突保证不会存在链表过长的情况导致检索性能下降。
rehash参考《Redis中Rehash浅析》

二、Value存储结构

1. SDS(simple dynamic string)

redis中默认的字符串表示key和String类型的value都是用这个数据结构。有几个优点

1. len字段保证了获取字符串长度时时间复杂度是O(1)不用遍历计数。
2. 空间可以预分配开辟空间或者字符串变更需要增加空间时需要字符串长度len小于1M时预分配空间free长度=len。len大于1M时free=1M。
3. 空间惰性释放当字符串长度变小时不立即回收内存而是只调整len和free的大小。
4. 二进制安全针对一些二进制文件可能包含\0符号SDS不以\0为字符串结束符判断而是len+\0作为字符串是否结束判断。
5. 如果一个String类型的value的值是数字那么Redis内部会把它转成long类型来存储从而减少内存的使用。

//SDS数据结构
struct sdshdr{
     //记录buf数组中已使用字节的数量
     //等于 SDS 保存字符串的长度
     int len;
     //记录 buf 数组中未使用字节的数量
     int free;
     //字节数组用于保存字符串
     char buf[];
}

为了节省内存空间Redis 还做了如下优化
当保存 Long 类型整数RedisObject 中的指针直接赋值为整数数据这样就不用额外的指针指向整数。这种方式称为 int 编码方式。
当保存字符串数据且字符串小于等于 44 字节时RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域这样可以避免内存碎片。这种方式称为 embstr 编码方式。
当保存字符串数据且字符串大于 44 字节时Redis 不再把 SDS 和 RedisObject 放在一起而是给 SDS 分配独立的空间并用指针指向 SDS 结构。这种方式称为 raw 编码模式。
下图为 int、embstr 和 raw 这三种编码模式的对比

2. 字典dict

字典dict就是类似hashmap key-value的方式也就是数组+链表的方式。

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;    
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;
typedef struct dictEntry {
    // key键
    void *key;
    // v值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点形成链表
    struct dictEntry *next;
} dictEntry;

3. ziplist压缩列表

压缩列表ziplist是一块连续的内存空间元素之间紧挨着存储没有任何冗余空隙。元素的检索定位是通过偏移量来完成的。
压缩列表为了支持双向遍历所以才会有 ztail_offset 这个字段用来快速定位到最后一 个元素然后倒着遍历。

//ziplist数据结构
struct ziplist<T> {
	int32 zlbytes; // 整个压缩列表占用字节数
	int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量用于快速定位到最后一个节点
	int16 zllength; // 元素个数
	T[] entries; // 元素内容列表挨个挨个紧凑存储
	int8 zlend; // 标志压缩列表的结束值恒为 0xFF
}
//entry数据结构
struct entry {
	int<var> prevlen; // 前一个 entry 的字节长度当压缩列表倒着遍历时需要通过这个字段来快速定位到下一个元素的位置
	int<var> encoding; // 元素类型编码
	optional byte[] content; // 元素内容
}

4. 快速列表quickList

快速列表就是一个一个小的压缩列表串起来的双向链表 quicklist【quicklist = 链表+ziplist】

1. quickList就是一个标准的双向链表的配置有head 有tail;
2. 每一个节点是一个quicklistNode包含prev和next指针。
3. 每一个quicklistNode 包含 一个ziplist*zp 压缩链表里存储键值。
4. 所以quicklist是对ziplist进行一次封装使用小块的ziplist来既保证了少使用内存减少附加的指针空间并减少内存的碎片化也保证了性能。

5. 整数数组inset

typedf struct inset{
    uint32_t encoding;//编码方式 有三种 默认 INSET_ENC_INT16
    uint32_t length;//集合元素个数
    int8_t contents[];//实际存储元素的数组 
                      //元素类型并不一定是ini8_t类型柔性数组不占intset结构体大小
                      //并且数组中的元素从小到大排列
}inset;

编码格式encoding共有三种INTSET_ENC_INT16、INSET_ENC_INT32和INSET_ENC_INT64三种分别对应不同的范围。Redis为了尽可能地节省内存会根据插入数据的大小选择不一样的类型来进行存储。会且只在必要的时候进行升级操作节省内存升级过程耗费系统资源还有就是不支持降级一旦升级就不可以降级
元素数量length记录了保存数据的数组contents中共有多少个元素这样获取个数的时间复杂度就是O(1)。
数组contents真正存储数据的地方数组是按照从小到大有序排列的并且不包含任何重复项。

6. 跳跃表skiplist

跳跃表的逻辑类似于“树”型结构是将一个链表其中的元素间隔几个就向上抽取一层这样实现检索的过程时间复杂度达到O(logN)。

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;//跳表节点 头节点  尾节点
    unsigned long length;//节点数量
    int level;//目前表内节点的最大层数
} zskiplist;
 
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

typedef struct zskiplistNode{
	struct zskiplistLevel{
		struct zskiplistNode *forward; // 前进指针
		unsigned int span;	// 跨度 这个层跨越的节点数量
	} level[];
	struct zskiplistNode *backward;// 后退指针
	double score;// 分值
	robj *obj;// 成员对象
} zskiplistNode;

Redis跳跃表常用操作的时间复杂度

三、五种数据分别对应的数据结构

从上图可以看出除了string其它四种类型在底层实现上都有两种选择。

1. String只有一个中数据类型SDS但是可以选择整数的编码方式方便计数类操作。
2. Hash的底层实现中当数据量较小的时候采用zipList作为hash的底层实现否则使用字典dict来实现的。使用压缩列表的满足条件是
   ①哈希对象保存的所有键值对的键和值的字符串长度都小于64字节。
   ②哈希对象保存的键值对数量小于512个
3. list底层数据结构ziplist和quicklist首先在列表元素较少的情况下会使用一块连续的内存存储这个结构是 ziplist 即压缩列表 . 它将所有的元素紧挨着一起存储分配的是一块连续的内存当数据量比较多才会改成 quicklist。
4. set底层数据结构inset和dict当value是整数值时且数据量不大时使用inset来存储其他情况都是用字典dict来存储。
5. zset底层数据结构压缩列表ziplist和跳表skiplist有两个配置来判断使用哪一个数据结构
   ①zset-max-ziplist-entries 128zset采用压缩列表时元素个数最大值。默认值为128。
   ②zset-max-ziplist-value 64zset采用压缩列表时每个元素的字符串长度最大值。默认值为64。
   zset插入第一个元素时会判断下面两种条件zset-max-ziplist-entries的值是否等于0zset-max-ziplist-value小于要插入元素的字符串长度满足任一条件Redis就会采用跳跃表作为底层实现否则采用压缩列表作为底层实现方式。一般情况下不会将zset-max-ziplist-entries配置成0元素的字符串长度也不会太长所以在创建有序集合时默认使用压缩列表的底层实现。zset新插入元素时会判断以下两种条件zset中元素个数大于zset_max_ziplist_entries插入元素的字符串长度大于zset_max_ziplist_value。当满足任一条件时Redis便会将zset的底层实现由压缩列表转为跳跃表。转换为跳跃表后即使元素被逐渐删除也不会重新转为压缩列表。

参考一、redis原理之string底层数据结构SDS
二、redis原理之hash底层数据结构ziplist dict
三、redis原理之list底层数据结构
四、redis原理之set底层数据结构
五、redis原理之sort set底层数据结构
Redis的五种数据结构的底层实现原理