Redis 存储类型
主要提供了 5 种数据结构: 字符串(String), 哈希(hash), 列表(list), 集合(set), 有序集合(short set);
Redis 底层实现的 8 种数据结构
SDS simple synamic string: 支持自动动态扩容的字节数组
list : 链表
dict : 使用双哈希表实现的, 支持平滑扩容的字典
zskiplist : 附加了后向指针的跳跃表
intset : 用于存储整数数值集合的自有结构
ziplist : 一种实现上类似于 TLV, 但比 TLV 复杂的, 用于存储任意数据的有序序列的数据结构
quicklist: 一种以 ziplist 作为结点的双链表结构, 实现的非常不错
zipmap : 一种用于在小规模场合使用的轻量级字典结构
其中 5 种存储类型与 8 种数据结构的桥梁, 是 redisObject;
Redis 中的 Key 与 Value 在表层都是一个 redisObject 实例, 所以该结构有所谓的 "类型", 即是 ValueType. 对于每一种 Value Type 类型的 redisObject;
其底层至少支持两种不同的底层数据结构来实现. 以应对在不同的应用场景中, Redis 的运行效率, 或内存占用等
底层数据结构分析
1,SDS - simple dynamic string
可以在安装目录的 src 文件夹下看到 sds.c 和 sds.h 的源码文件
- typedef char *sds;
- /* Note: sdshdr5 is never used, we just access the flags byte directly.
- * However is here to document the layout of type 5 SDS strings. */
- struct __attribute__ ((__packed__)) sdshdr5 {
- unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr8 {
- uint8_t len; /* used */
- uint8_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr16 {
- uint16_t len; /* used */
- uint16_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr32 {
- uint32_t len; /* used */
- uint32_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };
- struct __attribute__ ((__packed__)) sdshdr64 {
- uint64_t len; /* used */
- uint64_t alloc; /* excluding the header and null terminator */
- unsigned char flags; /* 3 lsb of type, 5 unused bits */
- char buf[];
- };s
sdshdr 的存储结构
sdshdr 是头部, buf 是真实存储用户数据的地方.(buf="数据" + "\0" );sds 有四种不同的头部. sdshdr5 未 使用, 未显示
en 分别以 uint8, uint16, uint32, uint64 表示用户数据的长度(不包括末尾的 \ 0)
alloc 分别以 uint8, uint16, uint32, uint64 表示整个 SDS, 除过头部与末尾的 \ 0, 剩余的字节数.
flag 始终为一字节, 以低三位标示着头部的类型, 高 5 位未使用.
创建一个 SDS 实例的三个接口
2,list
链表实现, 链表结点不直接持有数据, 而是通过 void * 指针来间接的指向数据. 其实现位于 src/adlist.h 与 src/adlist.c 中,
内存布局
list 在 Redis 除了作为一些 Value Type 的底层实现外, 还广泛用于 Redis 的其它功能实现中, 作为一种数据结构工具使用.
在 list 的实现中, 除了基本的链表定义外, 还额外增加了: 迭代器 listIter 的定义, 与相关接口的实现.
由于 list 中的链表结点本身并不直接持有数据, 而是通过 value 字段, 以 void * 指针的形式间接持有, 所以数据的生命周期并不完全与链表及其结点一致. 这给了 list 的使用者相当大的灵活性. 比如可以多个结点持有同一份数据的地址. 但与此同时, 在对链表进行销毁, 结点复制以及查找匹配时, 就需要 list 的使用者将相关的函数指针赋值于 list.dup, list.free, list.match 字段.
3,dict
dict 类似于 C++ 标准库中的 std::unordered_map, 其实现位于 src/dict.h 与 src/dict.c 中
dict 中存储的键值对, 是通过 dictEntry 这个结构间接持有的, k 通过指针间接持有键, v 通过指针间接持有值. 注意, 若值是整数值的话, 是直接存储在 v 字段中的, 而不是间接持有. 同时 next 指针用于指向, 在 bucket 索引值冲突时, 以链式方式解决冲突, 指向同索引的下一个 dictEntry 结构.
dict 即为字典. 其中 type 字段中存储的是本字典使用到的各种函数指针, 包括散列函数, 键与值的复制函数, 释放函数, 以及键的比较函数. privdata 是用于存储用户自定义数据. 这样, 字典的使用者可以最大化的自定义字典的实现, 通过自定义各种函数实现, 以及可以附带私有数据, 保证了字典有很大的调优空间.
字典为了支持平滑扩容, 定义了 ht[2]这个数组字段. 其用意是这样的:
一般情况下, 字典 dict 仅持有一个哈希表 dictht 的实例, 即整个字典由一个 bucket 实现.
随着插入操作, bucket 中出现冲突的概率会越来越大, 当字典中存储的结点数目, 与 bucket 数组长度的比值达到一个阈值 (1:1) 时, 字典为了缓解性能下降, 就需要扩容
扩容的操作是平滑的, 即在扩容时, 字典会持有两个 dictht 的实例, ht[0]指向旧哈希表, ht[1]指向扩容后的新哈希表.
内存布局
4,zskiplist
zskiplist 是 Redis 实现的一种特殊的跳跃表. 跳跃表是一种基于线性表实现简单的搜索结构, 其最大的特点就是: 实现简单, 性能能逼近各种搜索树结构.
zskiplist 的核心设计要点:
头结点不持有任何数据, 且其 level[]的长度为 32
每个结点, 除了持有数据的 ele 字段, 还有一个字段 score, 其标示着结点的得分, 结点之间凭借得分来判断先后顺序, 跳跃表中的结点按结点的得分升序排列.
每个结点持有一个 backward 指针, 这是原版跳跃表中所没有的. 该指针指向结点的前一个紧邻结点.
每个结点中最多持有 32 个 zskiplistLevel 结构. 实际数量在结点创建时, 按幂次定律随机生成(不超过 32). 每个 zskiplistLevel 中有两个字段.
内存布局
5,intset
用于存储在序的整数的数据结构, 也底层数据结构中最简单的一个, 其定义与实现在 src/intest.h 与 src/intset.c 中
inset 结构中的 encoding 的取值有三个, 分别是宏 INTSET_ENC_INT16, INTSET_ENC_INT32, INTSET_ENC_INT64. length 代表其中存储的整数的个数, contents 指向实际存储数值的连续内存区域
内存布局
intset 中各字段, 包括 contents 中存储的数值, 都是以主机序 (小端字节序) 存储的. 这意味着 Redis 若运行在 PPC 这样的大端字节序的机器上时, 存取数据都会有额外的字节序转换开销
当 encoding == INTSET_ENC_INT16 时, contents 中以 int16_t 的形式存储着数值. 类似的, 当 encoding == INTSET_ENC_INT32 时, contents 中以 int32_t 的形式存储着数值.
但凡有一个数值元素的值超过了 int32_t 的取值范围, 整个 intset 都要进行升级, 即所有的数值都需要以 int64_t 的形式存储. 显然升级的开销是很大的.
intset 中的数值是以升序排列存储的, 插入与删除的复杂度均为 O(n). 查找使用二分法, 复杂度为 O(log_2(n))
intset 的代码实现中, 不预留空间, 即每一次插入操作都会调用 zrealloc 接口重新分配内存. 每一次删除也会调用 zrealloc 接口缩减占用的内存. 省是省了, 但内存操作的时间开销上升了.
intset 的编码方式一经升级, 不会再降级.
总之, intset 适合于如下数据的存储:
所有数据都位于一个稳定的取值范围中. 比如均位于 int16_t 或 int32_t 的取值范围中
数据稳定, 插入删除操作不频繁. 能接受 O(lgn)级别的查找开销
6,ziplist
ziplist 是 Redis 底层数据结构中, 最苟的一个结构. 它的设计宗旨就是: 省内存, 从牙缝里省内存. 设计思路和 TLV 一致, 但为了从牙缝里节省内存, 做了很多额外工作.
ziplist 的内存布局与 intset 一样: 就是一块连续的内存空间. 但区域划分比较复杂
和 intset 一样, ziplist 中的所有值都是以小端序存储的
zlbytes 字段的类型是 uint32_t, 这个字段中存储的是整个 ziplist 所占用的内存的字节数
zltail 字段的类型是 uint32_t, 它指的是 ziplist 中最后一个 entry 的偏移量. 用于快速定位最后一个 entry, 以快速完成 pop 等操作
zllen 字段的类型是 uint16_t, 它指的是整个 ziplit 中 entry 的数量. 这个值只占 16 位, 所以蛋疼的地方就来了: 如果 ziplist 中 entry 的数目小于 65535, 那么该字段中存储的就是实际 entry 的值. 若等于或超过 65535, 那么该字段的值固定为 65535, 但实际数量需要一个个 entry 的去遍历所有 entry 才能得到.
zlend 是一个终止字节, 其值为全 F, 即 0xff. ziplist 保证任何情况下, 一个 entry 的首字节都不会是 255
在画图展示 entry 的内存布局之前, 先讲一下 entry 中都存储了哪些信息:
每个 entry 中存储了它前一个 entry 所占用的字节数. 这样支持 ziplist 反向遍历.
每个 entry 用单独的一块区域, 存储着当前结点的类型: 所谓的类型, 包括当前结点存储的数据是什么 (二进制, 还是数值), 如何编码(如果是数值, 数值如何存储, 如果是二进制数据, 二进制数据的长度) 最后就是真实的数据了
7,quicklist
如果说 ziplist 是整个 Redis 中为了节省内存, 而写的最苟的数据结构, 那么称 quicklist 就是在最苟的基础上, 再苟了一层. 这个结构是 Redis 在 3.2 版本后新加的, 在 3.2 版本之前, 我们可以讲, dict 是最复杂的底层数据结构, ziplist 是最苟的底层数据结构. 在 3.2 版本之后, 这两个记录被双双刷新了.
这是一种, 以 ziplist 为结点的, 双端链表结构. 宏观上, quicklist 是一个链表, 微观上, 链表中的每个结点都是一个 ziplist.
它的定义与实现分别在 src/quicklist.h 与 src/quicklist.c 中
这里定义了五个结构体:
quicklistNode, 宏观上, quicklist 是一个链表, 这个结构描述的就是链表中的结点. 它通过 zl 字段持有底层的 ziplist. 简单来讲, 它描述了一个 ziplist 实例
quicklistLZF, ziplist 是一段连续的内存, 用 LZ4 算法压缩后, 就可以包装成一个 quicklistLZF 结构. 是否压缩 quicklist 中的每个 ziplist 实例是一个可配置项. 若这个配置项是开启的, 那么 quicklistNode.zl 字段指向的就不是一个 ziplist 实例, 而是一个压缩后的 quicklistLZF 实例
quicklist. 这就是一个双链表的定义. head, tail 分别指向头尾指针. len 代表链表中的结点. count 指的是整个 quicklist 中的所有 ziplist 中的 entry 的数目. fill 字段影响着每个链表结点中 ziplist 的最大占用空间, compress 影响着是否要对每个 ziplist 以 LZ4 算法进行进一步压缩以更节省内存空间.
quicklistIter 是一个迭代器
quicklistEntry 是对 ziplist 中的 entry 概念的封装. quicklist 作为一个封装良好的数据结构, 不希望使用者感知到其内部的实现, 所以需要把 ziplist.entry 的概念重新包装一下.
quicklist 的内存布局图如下所示:
下面是有关 quicklist 的更多额外信息:
quicklist.fill 的值影响着每个链表结点中, ziplist 的长度.
当数值为负数时, 代表以字节数限制单个 ziplist 的最大长度. 具体为:
-1 不超过 4kb
-2 不超过 8kb
-3 不超过 16kb
-4 不超过 32kb
-5 不超过 64kb
当数值为正数时, 代表以 entry 数目限制单个 ziplist 的长度. 值即为数目. 由于该字段仅占 16 位, 所以以 entry 数目限制 ziplist 的容量时, 最大值为 2^15 个
quicklist.compress 的值影响着 quicklistNode.zl 字段指向的是原生的 ziplist, 还是经过压缩包装后的 quicklistLZF
0 表示不压缩, zl 字段直接指向 ziplist
1 表示 quicklist 的链表头尾结点不压缩, 其余结点的 zl 字段指向的是经过压缩后的 quicklistLZF
2 表示 quicklist 的链表头两个, 与末两个结点不压缩, 其余结点的 zl 字段指向的是经过压缩后的 quicklistLZF
以此类推, 最大值为 2^16
quicklistNode.encoding 字段, 以指示本链表结点所持有的 ziplist 是否经过了压缩. 1 代表未压缩, 持有的是原生的 ziplist, 2 代表压缩过
quicklistNode.container 字段指示的是每个链表结点所持有的数据类型是什么. 默认的实现是 ziplist, 对应的该字段的值是 2, 目前 Redis 没有提供其它实现. 所以实际上, 该字段的值恒为 2
quicklistNode.recompress 字段指示的是当前结点所持有的 ziplist 是否经过了解压. 如果该字段为 1 即代表之前被解压过, 且需要在下一次操作时重新压缩.
quicklist 的具体实现代码篇幅很长, 这里就不贴代码片断了, 从内存布局上也能看出来, 由于每个结点持有的 ziplist 是有上限长度的, 所以在与操作时要考虑的分支情况比较多. 想想都蛋疼.
quicklist 有自己的优点, 也有缺点, 对于使用者来说, 其使用体验类似于线性数据结构, list 作为最传统的双链表, 结点通过指针持有数据, 指针字段会耗费大量内存. ziplist 解决了耗费内存这个问题. 但引入了新的问题: 每次写操作整个 ziplist 的内存都需要重分配. quicklist 在两者之间做了一个平衡. 并且使用者可以通过自定义 quicklist.fill, 根据实际业务情况, 经验主义调参.
8,zipmap
dict 作为字典结构, 优点很多, 扩展性强悍, 支持平滑扩容等等, 但对于字典中的键值均为二进制数据, 且长度都很小时, dict 的中的一坨指针会浪费不少内存, 因此 Redis 又实现了一个轻量级的字典, 即为 zipmap.
zipmap 适合使用的场合是:
键值对量不大, 单个键, 单个值长度小
键值均是二进制数据, 而不是复合结构或复杂结构. dict 支持各种嵌套, 字典本身并不持有数据, 而仅持有数据的指针. 但 zipmap 是直接持有数据的.
zipmap 的定义与实现在 src/zipmap.h 与 src/zipmap.c 两个文件中, 其定义与实现均未定义任何 struct 结构体, 因为 zipmap 的内存布局就是一块连续的内存空间. 其内存布局如下所示:
zipmap 起始的第一个字节存储的是 zipmap 中键值对的个数. 如果键值对的个数大于 254 的话, 那么这个字节的值就是固定值 254, 真实的键值对个数需要遍历才能获得.
zipmap 的最后一个字节是固定值 0xFF
zipmap 中的每一个键值对, 称为一个 entry, 其内存占用如上图, 分别六部分:
len_of_key, 一字节或五字节. 存储的是键的二进制长度. 如果长度小于 254, 则用 1 字节存储, 否则用五个字节存储, 第一个字节的值固定为 0xFE, 后四个字节以小端序 uint32_t 类型存储着键的二进制长度.
key_data 为键的数据
len_of_val, 一字节或五字节, 存储的是值的二进制长度. 编码方式同 len_of_key
len_of_free, 固定值 1 字节, 存储的是 entry 中未使用的空间的字节数. 未使用的空间即为图中的 free, 它一般是由于键值对中的值被替换发生的. 比如, 键值对 hello <-> Word 被修改为 hello <-> w 后, 就空了四个字节的闲置空间
val_data, 为值的数据
free, 为闲置空间. 由于 len_of_free 的值最大只能是 254, 所以如果值的变更导致闲置空间大于 254 的话, zipmap 就会回收内存空间.
来源: http://stor.51cto.com/art/201910/605032.htm