参考地址: 《【Redis】redis各类型数据存储分析》 《一文深入了解 Redis 内存模型,Redis 的快是有原因的!》
Redis 常用的数据类型主要有:String, List, Hash, Set, ZSet 五种,它们分别对应的底层数据结构有:
redisObject 对象非常重要,Redis 对象的类型、内部编码、内存回收、共享对象等功能,都需要 redisObject 支持。这样设计的好处是,可以针对不同的使用场景,对五种常用类型设置多种不同的数据结构实现,从而优化对象在不同场景下的使用效率。
例如当我们执行set hello world命令时,会有以下数据模型:
dictEntry:Redis 给每个 key-value 键值对分配一个 dictEntry,里面有着 key 和 val 的指针,next 指向下一个 dictEntry 形成链表,这个指针可以将多个哈希值相同的键值对链接在一起,由此来解决哈希冲突问题(链地址法)。
sds:键 key “hello” 是以 SDS(简单动态字符串)存储,后面详细介绍。
redisObject:值val “world” 存储在 redisObject 的 ptr 中。实际上,redis 常用五种类型都是以 redisObject 来存储的;而 redisObject 中的 type 字段指明了 Value 对象的类型,ptr 字段则指向对象所在的地址。
注:无论是 dictEntry 对象,还是 redisObject、SDS 对象,都需要内存分配器(如jemalloc)分配内存进行存储。jemalloc作为Redis的默认内存分配器,在减小内存碎片方面做的相对比较好。比如jemalloc在64位系统中,将内存空间划分为小、大、巨大三个范围;每个范围内又划分了许多小的内存块单位;当Redis存储数据时,会选择大小最合适的内存块进行存储。
前面说过,Redis 每个对象由一个 redisObject 结构表示,它的 ptr 指针指向底层实现的数据结构,而数据结构由 encoding 属性决定。比如我们执行以下命令得到存储“hello”对应的编码:
redis所有的数据结构类型如下:
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[]; // ’\0’空字符结尾
};
字符串对象的底层实现可以是int、raw、embstr(上面的表对应有名称介绍)。
embstr编码是通过调用一次内存分配函数来分配一块连续的空间,而raw需要调用两次。
int 编码字符串和 embstr 编码字符串在一定条件下会转化为 raw 编码字符串。
如果对一个SDS进行修改,分为一下两种情况:
hashtable 又名字典,是 Redis 中应用十分广泛的数据结构。除了基础数据结构 Hash, Set 之外,Redis 的全局字典,过期时间的 Key 集合,ZSet 中 value 与 score 的映射,都是基于 hashtable 完成的。
Hashtable 可以简化成如下结构:
可以看出,HashTable 与 Java 1.7 中的 HashMap 实现原理基本相同。代码如下:
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时,值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在运行的安全迭代器的数量
int iterators; /* number of iterators currently running */
} dict;
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
typedef struct dictEntry {
void *key;
union {void *val;uint64_t u64;int64_t s64;} v;
// 指向下个哈希表节点,形成链表
struct dictEntry *next;
} dictEntry;
在 dict 的定义中,可以看出有两个 dictht 字典对象。每个字典会带有两个哈希表,一个平时使用,另一个仅在rehash(重新散列)时使用。随着对哈希表的操作,键会逐渐增多或减少。为了让哈希表的负载因子维持在一个合理范围内,Redis会对哈希表的大小进行扩展或收缩(rehash)。只有在扩展与收缩时,ht[0] 里面所有的键值对会多次、渐进式的 rehash 到 ht[1] 里。
Hash 可以使用 Hashtable 或者 ziplist 结构来实现。Hash对象只有同时满足下面两个条件时,才会使用ziplist(压缩列表):
较大数量的 Set 同样也是 HashTable ,但实现的时候 value 全部置为 NULL。
注:
当 hash 与 zset 数据很少时,为了节省空间,Redis 就使用 ziplist(压缩列表)做列表键的底层实现。 ziplist 是 Redis 为了节约内存而开发的,是由一系列特殊编码的连续内存块(而不是像双端链表一样每个节点是指针)组成的顺序型数据结构,是一个可以双向遍历的压缩链表。ziplist 空间压缩的非常紧凑,所以只适合小数据量的情况。
ziplist 的数据结构如下所示:
每一个 entry 的数据内容是由 encoding 字段决定的,内容十分复杂,根据不同的 encoding 值,可以决定 entry 的 content 是哪种长度的 int,哪种长度的字符串。
ziplist 的空间压缩十分紧密,所以占用空间很小。但相应的,增删改时代价较大。插入数据时,都需要用 realloc 重新申请内存,申请内存可能是重新分配整个新 ziplist 的内存,也可能是在 ziplist 尾部申请空间。更新数据时,由于每个 entry 都有前一个 entry 占用空间大小的信息(prevlen 字段),所以更新数据时会触发前向数据的级联更新。综上所述,ziplist 只适合小数据集。
注:
Redis 的 List 结构就是 linkedList 与 ziplist 结合而成的。LinkedList 结构比较像 Java 的 LinkedList,源码如下:
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 节点值复制函数
void *(*dup)(void *ptr);
// 节点值释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
// 链表所包含的节点数量
unsigned long len;
} list;
从图中可以看出 Redis 的 linkedlist 双端链表有以下特性:
所以获取前置节点、后置节点、表头节点和表尾节点的复杂度都是 O(1)。len属性获取节点数量也为O(1)。
与双端链表相比,压缩列表可以节省内存空间,但是进行修改或增删操作时,复杂度较高;因此当节点数量较少时,可以使用压缩列表;但是节点数量多时,还是使用双端链表划算。
注:
List 对象的底层实现是 quicklist(快速列表,是 ziplist 压缩列表 和 linkedlist 双端链表的组合)。Redis 中的列表支持两端插入和弹出,并可以获得指定位置(或范围)的元素,可以充当数组、队列、栈等。
quicklist 将 linkedList 按段切分,每一段使用 zipList 来紧凑存储,多个 zipList 之间使用双向指针串接起来。因为链表的附加空间相对太高,prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节),另外每个节点的内存都是单独分配,会加剧内存的碎片化,影响内存管理效率。
quicklist 默认的压缩深度是 0,也就是不压缩。为了支持快速的 push/pop 操作,quicklist 的首尾两个 ziplist 不压缩,此时深度就是 1。为了进一步节约空间,Redis 还会对 ziplist 进行压缩存储,使用 LZF 算法压缩。
注:通常每个 ziplist 的长度为 8KB,该长度可以通过配置文件进行配置。
跳跃表是一种随机化数据结构,基于并联的链表,其效率可以比拟平衡二叉树,查找、删除、插入等操作都可以在对数期望时间内完成,对比平衡树,跳跃表的实现要简单直观很多。
以下是一个跳跃表的例图(来自维基百科):
从图中可以看出跳跃表主要有以下几个部分构成:
跳跃表的遍历总是从高层开始,然后随着元素值范围的缩小,慢慢降低到低层。
跳跃表保持平衡使用的是【随机抛硬币】的方法。因为跳跃表删除和添加的节点是不可预测的,很难用一种有效算法保证跳表索引分布始终是均匀的。随机抛硬币的方法虽然不能保证所以的绝对均匀分布,但是随着数据量的增大,该算法可以使跳跳结构大体趋于均匀。
Redis 作者为了适合自己功能的需要,对原来的跳跃表进行了一下修改: