数据类型实现

default

Redis 数据类型的内部实现

Redis 内部实现如下数据结构[2,3,4,10]: 1 String 2 Hash Table 3 Doubly Linked List 4 Skip List 5 Zip List 6 Int Sets 7 Zip Maps (从 2.6 版本开始废弃)

Redis 在收到客户端的请求后,为每一个参数创建一个 robj 对象,type 定义为 REDIS_STRING,encoding 为 REDIS_ENCODING_RAW。接下来 Redis 根据第一个 robj 对象(也就是命令名)查找对应的函数,并调用查找到的函数,命令执行过程可参 考[7]。 String

如果一个 String 类型的 value 能够保存为整数,则将对应 robj 对象的 encoding 修改为 REDIS_ENCODING_INT,将对应 robj 对象的 ptr 值改为对应的数值。如果不能转为整数,保持原有 encoding 为 REDIS_ENCODING_RAW。 因此 String 类型的数据可能使用原始的字符串存储(实际为 sds - Simple Dynamic Strings[9],对应 encoding 为 REDIS_ENCODING_RAW)或者整数存储。 具体查看某一个 key 的 encoding,参考 Redis 命令 object[8]

下面是具体的例子: redis 127.0.0.1:6379> set hello 1 OK redis 127.0.0.1:6379> OBJECT ENCODING hello "int" redis 127.0.0.1:6379> set hello world OK redis 127.0.0.1:6379> OBJECT ENCODING hello "raw"

List

List 类型的 key 创建时使用 zip list 结构存储,robj 对象的 encoding 字段设置为 REDIS_ENCODING_ZIPLIST。zip list 实现细节可参考[3]。概况来讲,zip list 通过一个连续的内存块实现 list 结构,其中的每个 entry 节点头部保存前后节点长度信息,实现双向链表功能。这个头部可根据前后 entry 长 度进行内存压缩,而如果直接使用指针的话则至少需要两个指针,对 64 位系统来说将占用 16 个字节,使用 zip list 时最好情况下只需要两个字节,这在具有大量 list 类型的 key-value 对且各个 value 较小的应用来说,可以节省大量内存。 当 list 的 elem 数小于配置值: hash-max-ziplist-entries 或者 elem_value 字符串的长度小于 hash-max-ziplist-value, 可以编码成 REDIS_ENCODING_ZIPLIST 类型存储,以节约内存;但由于在 zip list 添加和删除元素会涉及到数据移动,因此当 list 内容较多时,转而使用双向链表。双向链表的实现可参考数据结构相关教科书。 相关内存优化说明请参考[11]。

Hash

新建的 Hash 类型也使用 ziplist 存储 value,保存数据过多时,转而使用 hast table。

Set

创建 Set 类型的 key-value 时,如果 value 能够表示为整数,则使用 intset 类型保存 value。intset 使用和 ziplist 相似的实现方式保存整数[4]。数据量大时,切换为使用 hash table 保存各个 value。

Zset

zset 指排序的 set,如果新建的 zset 包含 value 数大于配置或者 value 长度大于配置值[11],则直接使用 hash table 和 skip list[12]存储 value,skip list 实现对 value 的排序;否则直接使用 skip list 存储 value。Redis 可以保存相同 score 的 value 值,其实现可参考源代码[1]以及文献[12],Redis 是参考[12]中伪代 码实现的。

Zip List

Skip List