Redis对象的数据结构基础理解

参考：黄健宏著. Redis设计与实现 (数据库技术丛书) . 机械工业出版社. Kindle 版本.

关于各种对象的实现方式：

	字符串对象	列表对象	哈希对象	集合对象	有序集合对象
实现	整数值简单动态字符串	压缩列表双端链表	压缩列表字典	整数集合字典	压缩列表跳跃表和字典
编码 REDIS_ENCODING_***	INT EMBSTR RAW	ZIPLIST LINKEDLIST	ZIPLIST HT	INTSET HT	ZIPLIST SKIPLIST

先来了解一下各种对象：

Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。

对于Redis数据库保存的键值对来说，键总是一个字符串对象，而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种，

当我们对一个数据库键执行TYPE命令时，命令返回的结果为数据库键对应的值对象的类型，

使用 OBJECT ENCODING 命令可以查看一个数据库键的值对象的编码：

通过 encoding 属性来设定对象所使用的编码，而不是为特定类型的对象关联一种固定的编码，极大地提升了 Redis 的灵活性和效率，因为 Redis 可以根据不同的使用场景来为一个对象设置不同的编码，从而优化对象在某一场景下的效率。

1》字符串对象

这几种编码格式会在什么情况下相互转换？

2》列表对象

ziplist编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点（ entry）保存了一个列表元素。

另一方面， linkedlist 编码的列表对象使用双端链表作为底层实现，每个双端链表节点（ node）都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素。

编码转换：

当列表对象可以同时满足以下两个条件时，列表对象使用 ziplist 编码：

·列表对象保存的所有字符串元素的长度都小于 64 字节；

·列表对象保存的元素数量小于 512 个；不能满足这两个条件的列表对象需要使用 linkedlist 编码。

注意

以上条件可以通过 list- max- ziplist- value 选项和 list- max- ziplist- entries 调整。

3》哈希对象

哈希对象的编码可以是 ziplist 或者 hashtable。 ziplist 编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾，

·哈希对象保存的所有键值对的键和值的字符串长度都小于64 字节；

·哈希对象保存的键值对数量小于512 个；不能满足这两个条件的哈希对象需要使用 hashtable 编码。

这两个条件的上限值是可以修改的，具体请看配置文件中关于hash- max- ziplist- value 选项和 hash- max- ziplist- entries 选项的说明。

4》集合对象

集合对象的编码可以是 intset 或者 hashtable。 intset 编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。

当集合对象可以同时满足以下两个条件时，对象使用 intset 编码：

·集合对象保存的所有元素都是整数值；

·集合对象保存的元素数量不超过512 个。

5》有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist。 ziplist 编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（ member），而第二个元素则保存元素的分值（ score）。

skiplist 编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表：

为什么有序集合需要同时使用跳跃表和字典来实现？

当有序集合对象可以同时满足以下两个条件时，对象使用 ziplist 编码：

·有序集合保存的元素数量小于128 个；

·有序集合保存的所有元素成员的长度都小于64 字节；

不能满足以上两个条件的有序集合对象将使用 skiplist 编码。

构成Redis对象的底层数据结构

一、简单动态字符串

SDS：当 Redis需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis就会使用SDS来表示字符串值，比如在Redis 的数据库里面，包含字符串值的键值对在底层都是由 SDS 实现的。

SDS 遵循C字符串以空字符结尾的惯例

遵循空字符结尾这一惯例的好处是， SDS可以直接重用一部分C字符串函数库里面的函数。比如打印/比较

·比起C字符串， SDS具有以下优点：

1）常数复杂度获取字符串长度。

2）杜绝缓冲区溢出。 SDS拼接字符串前会计算内存空间是否不足

3）减少修改字符串长度时所需的内存重分配次数。SDS有两种策略：空间预分配/用free属性记录回收的空间下次利用

4）二进制安全。由len属性决定字符串是否结束

5）兼容部分C字符串函数。

二、链表

·链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。

·每个链表节点由一个 listNode 结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以 Redis的链表实现是双端链表。

·每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针，以及链表长度等信息。

·因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL，所以 Redis 的链表实现是无环链表。

·通过为链表设置不同的类型特定函数， Redis的链表可以用于保存各种不同类型的值。

三、字典

字典，又称为符号表（symbol table）、关联数组（ associative array）或映射（ map），是一种用于保存键值对（ key- value pair）的抽象数据结构。

Redis 的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

除了用来表示数据库之外，字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时， Redis就会使用字典作为哈希键的底层实现。

·字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键。

·Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行 rehash 时使用。

·当字典被用作数据库的底层实现，或者哈希键的底层实现时， Redis 使用MurmurHash2 算法来计算键的哈希值。

·哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。

·在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面，并且这个 rehash 过程并不是一次性地完成的，而是渐进式地完成的。

什么时候rehash？

当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

1）服务器目前没有在执行BGSAVE命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于1。

2）服务器目前正在执行BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于5。

另一方面，当哈希表的负载因子小于0. 1时，程序自动开始对哈希表执行收缩操作。

什么是hash table的负载因子？

四、跳跃表

跳跃表（ skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

Redis 使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（ member）是比较长的字符串时， Redis就会使用跳跃表来作为有序集合键的底层实现。

·跳跃表是有序集合的底层实现之一。

·Redis的跳跃表实现由zskiplist和zskiplistNode 两个结构组成，其中 zskiplist 用于保存跳跃表信息（比如表头节点、表尾节点、长度），而 zskiplistNode 则用于表示跳跃表节点。

·每个跳跃表节点的层高都是 1 至 32 之间的随机数。

五、整数集合

整数集合（ intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时， Redis就会使用整数集合作为集合键的底层实现。

·整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。

整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，另一个是尽可能地节约内存。

整数集合不支持降级操作

六、压缩列表

压缩列表是Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（ sequential）数据结构。一个压缩列表可以包含任意多个节点（ entry），每个节点可以保存一个字节数组或者一个整数值。

压缩列表（ ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。

另外，当一个哈希键只包含少量键值对，比且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。

·添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

服务器的其它特性

1》类型检查与命令多态

Redis 中用于操作键的命令基本上可以分为两种类型。其中一种命令可以对任何类型的键执行，比如说 DEL 命令、 EXPIRE 命令、 RENAME 命令、 TYPE 命令、 OBJECT 命令等。

而另一种命令只能对特定类型的键执行，比如说： ·SET、 GET、 APPEND、 STRLEN 等命令只能对字符串键执行；

列表对象有 ziplist 和 linkedlist 两种编码可用，如果我们对一个键执行 LLEN 命令，会先检查类型，在根据编码选择不同的api

DEL、 EXPIRE 等命令和 LLEN 等命令的区别在于，前者是基于类型的多态—— 一个命令可以同时用于处理多种不同类型的键，而后者是基于编码的多态—— 一个命令可以同时用于处理多种不同编码。

2》内存回收

初始化为1，被新程序引用时加1，不再使用减1，为0时回收

3》对象共享

除了用于实现引用计数内存回收机制之外，对象的引用计数属性还带有对象共享的作用。

在 Redis 中，让多个键共享同一个值对象需要执行以下以下两个步骤：

1）将数据库键的值指针指向一个现有的值对象；

2）将被共享的值对象的引用计数增一。

目前来说， Redis会在初始化服务器时，创建一万个字符串对象，这些对象包含了从 0 到 9999 的所有整数值，当服务器需要用到值为 0 到 9999 的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象。

注意

创建共享字符串对象的数量可以通过修改 redis. h/ REDIS_ SHARED_ INTEGERS 常量来修改。

为什么 Redis 不共享包含字符串的对象？

4》对象空转时长

除了前面介绍过的 type、 encoding、 ptr 和 refcount 四个属性之外， redisObject 结构包含的最后一个属性为 lru 属性，该属性记录了对象最后一次被命令程序访问的时间：

OBJECT IDLETIME 命令可以打印出给定键的空转时长，这一空转时长就是通过将当前时间减去键的值对象的 lru 时间计算得出的：

如果服务器打开了 maxmemory 选项，并且服务器用于回收内存的算法为 volatile- lru 或者 allkeys- lru，那么当服务器占用的内存数超过了 maxmemory 选项所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。

重点回顾

·Redis 数据库中的每个键值对的键和值都是一个对象。

·Redis 共有字符串、列表、哈希、集合、有序集合五种类型的对象，每种类型的对象至少都有两种或以上的编码方式，不同的编码可以在不同的使用场景上优化对象的使用效率。

·服务器在执行某些命令之前，会先检查给定键的类型能否执行指定的命令，而检查一个键的类型就是检查键的值对象的类型。

·Redis 的对象系统带有引用计数实现的内存回收机制，当一个对象不再被使用时，该对象所占用的内存就会被自动释放。

·Redis 会共享值为0到9999的字符串对象。

·对象会记录自己的最后一次被访问的时间，这个时间可以用于计算对象的空转时间。

参考：黄健宏著. Redis设计与实现 (数据库技术丛书) . 机械工业出版社. Kindle 版本.