概述
在前文Redis 字符串类型内部编码剖析 之中已经剖析过 Redis 最基本的 String 类型的内部是怎么编码和存储的, 本文再来阐述 Redis 中使用 最为频繁的数据类型: 哈希(或称散列), 在 Redis 内部是怎么存的.
实验源码环境: Redis 4.0.10
注: 本文首发于 My Personal Blog http://www.codesheep.cn/ , 欢迎光临 小站 http://www.codesheep.cn/
本文内容脑图如下:
哈希类型内部编码详情
对于 Redis 的常用 5 种数据类型(String,Hash,List,Set,sorted set), 每种数据类型都提供了 最少两种 内部的编码格式, 而且每个数据类型内部编码方式的选择 对用户是完全透明的, Redis 会根据数据量自适应地选择较优化的内部编码格式.
如果想查看某个键的内部编码格式, 可以使用 OBJECT ENCODING keyname 指令来进行, 比如:
- 127.0.0.1:6379>
- 127.0.0.1:6379> set foo bar
- OK
- 127.0.0.1:6379>
- 127.0.0.1:6379> object encoding foo // 查看某个 Redis 键值的编码
- "embstr"
- 127.0.0.1:6379>
- 127.0.0.1:6379>
对于使用最为频繁的 Hash 类型, 其内部编码方式可能有两种:
- OBJ_ENCODING_ZIPLIST(压缩列表)
- OBJ_ENCODING_HT(哈希表)
Redis 会根据数据量的情况来自适应地选择这两种编码方式中 较优 的一种, 而这一切对用户完全透明.
在 数据条目较少, 数据值较小 的时候 Redis 会采用 压缩列表 (OBJ_ENCODING_ZIPLIST) 编码方式进行存储. 这里成员 "较少", 成员值 "较小" 的标准可以通过如下配置项进行配置:
- hash-max-ziplist-entries 512
- hash-max-ziplist-value 64
Redis 默认给出了默认值, 当然用户可根据实际情况自行配置.
当 Hash 类型键的字段个数 < hash-max-ziplist-entries 并且 每个字段名和字段值的长度 < hash-max-ziplist-value 时, Redis 会使用 OBJ_ENCODING_ZIPLIST 来存储该键, 反之则会转换为 OBJ_ENCODING_HT 的编码方式.
口说无凭, 我们不妨先来做个实验感受一下吧:
很明显该实验验证了当 字段值长度大于 64 时, 编码格式会由 ZIPLIST 方式切换为 Hashtable 方式.
源码之前, 了无秘密, 我们再来看一下 Redis 关于这部分切换的源码实现, 那就理解得更加清楚了:
下面详解 OBJ_ENCODING_ZIPLIST 和 OBJ_ENCODING_HT 这两种编码格式的内部存储模型, 知道了其各自特点和优缺点, 自然也就明白了 Redis 内部使用它们的意图.
OBJ_ENCODING_ZIPLIST 编码
Ziplist 压缩列表是一种紧凑编码格式, 总体思想是时间换空间, 即以部分读写性能为代价, 来换取极高的内存空间利用率, 因此只会用于 字段个数少, 且字段值也较小 的场景.
压缩列表内存利用率极高的原因与其连续内存的特性是分不开的, 其典型的内存结构可以用下图形象地展示出来:
所以如果用 Ziplist 来存储 Redis 的散列类型的话, 元素的排列方式就变成了如下图所示的形象示意图: 即 key 和 value 都是逻辑连续内存:
OBJ_ENCODING_HT 编码
OBJ_ENCODING_HT 这种编码方式内部才是真正的哈希表结构, 或称为字典结构, 其可以实现 O(1)复杂度的读写操作, 因此效率很高.
在 Redis 内部, 从 OBJ_ENCODING_HT 类型到底层真正的散列表数据结构是一层层嵌套下去的, 关系如下:
这一关系我们可以从 Redis 哈希表定义部分的源码来看出:
下面来详解一下各个部分:
关于哈希节点(dictEntry)
关于哈希表 (dictht) 和字典(dict)
关于 dictType
Redis 如何计算 Hash 值
Redis 计算 Hash 的源代码如下:
这是一个 C 语言宏定义, 其实幕后真正承担 Hash 值计算的是上面介绍的 dictType 结构体中的函数指针 hashFunction.
而该 hashFunction 函数指针在初始化时会对应被赋值为一个个真实的计算 Hash 值的实际函数, 就像下面这样:
Redis 如何计算存取索引 Index 值
Index 值的计算依赖于上面计算得出的 Hash 值, 代码如下:
到此, 还有一个一直非常值得关注的细节: 即字典 dict 里总是保存有两个 Hash 表结构 ht[2], 以及与其高度相关的 rehash 操作, 这在下一篇文章里详解.
来源: https://my.oschina.net/hansonwang99/blog/1934354