redis设计与实现之对象篇

Redis并没直接使用这些数据结构去实现key-value pair数据库,而是基于这些数据结构实现了一系列对象.这些对象有:字符串对象,列表对象,集合对象,有序集合对象,哈希对象 五种基本对象,redis是如何表示对象的?

1
2
3
4
5
6
7
typedef struct redisObject {
unsigned type:4; // 类型
unsigned encoding:4;// 编码方式
void *ptr; // 指向对象的值
int refcount;// 引用计数,可用来对象回收与共享
unsigned lru:22;//对象最后一次被访问的时间
} robj;

type详解

对象的 type 属性记录了对象的类型(利用命令:type key即可获取)
| 对象 | 对象type属性的值 | TYPE 命令的输出 |
| :—: | :—-: | :——-: |
| 字符串对象 | REDIS_STRING | string |
| 列表对象 | REDIS_LIST | list |
| 哈希对象 | REDIS_HASH | hash |
| 集合对象 | REDIS_SET | set |
| 有序集合对象 | REDIS_ZSET | zset |

encoding详解

对象的 ptr 指针指向对象的底层实现数据结构, 而这些数据结构由对象的 encoding 属性决定,encoding 属性记录了对象所使用的编码, 也即是说这个对象使用了什么数据结构作为对象的底层实现,每种类型的对象都至少使用了两种不同的编码(利用object encoding key 可获取)
| 类型 | 编码 | 对象 | BJECT ENCODING|
| :— | :—- | :——-| :——-|
| REDIS_STRING | REDIS_ENCODING_INT | 使用整数值实现的字符串对象 | int |
| REDIS_STRING | REDIS_ENCODING_EMBSTR | 使用 embstr 编码的简单动态字符串实现的字符串对象 | embstr |
| REDIS_STRING | REDIS_ENCODING_RAW | 使用简单动态字符串实现的字符串对象 | raw |
| REDIS_LIST | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的列表对象 | ziplist |
| REDIS_LIST | REDIS_ENCODING_LINKEDLIST | 使用双端链表实现的列表对象 | linkedlist |
| REDIS_HASH | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的哈希对象 | ziplist |
| REDIS_HASH | REDIS_ENCODING_HT | 使用字典实现的哈希对象 | hashtable |
| REDIS_SET | REDIS_ENCODING_INTSET | 使用整数集合实现的集合对象 | intset |
| REDIS_SET | REDIS_ENCODING_HT | 使用字典实现的集合对象 | hashtable
| REDIS_ZSET | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的有序集合对象 | intset |
| REDIS_ZSET | REDIS_ENCODING_SKIPLIST | 使用跳跃表和字典实现的有序集合对象 | skiplist |

字符串对象

字符串对象的编码可以是 int 、 embstr 或者 raw,下面看下存储结构是怎么样的?

1
2
3
4
5
6
7
#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39
robj *createStringObject(char *ptr, size_t len) {
if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)
return createEmbeddedStringObject(ptr,len);
else
return createRawStringObject(ptr,len);
}

set一个整型之后的结构


如果字符串对象保存的是一个字符串值, 并且这个字符串值的长度小于等于 39 字节, 那么字符串对象将使用 embstr 编码的方式来保存这个字符串值,embstr 编码是专门用于保存短字符串的一种优化编码方式, 这种编码和 raw 编码一样, 都使用 redisObject 结构和 sdshdr 结构来表示字符串对象, 但 raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构, 而 embstr 编码则通过调用一次内存分配函数来分配一块连续的空间, 空间中依次包含 redisObject 和 sdshdr 两个结构

如果字符串对象保存的是一个字符串值, 并且这个字符串值的长度大于 39 字节, 那么字符串对象将使用一个简单动态字符串(SDS)来保存这个字符串值, 并将对象的编码设置为 raw

为什么是39字节,而不是别的?

embstr 编码的字符串对象在执行命令时, 产生的效果和 raw 编码的字符串对象执行命令时产生的效果是相同的, 但使用 embstr 编码的字符串对象来保存短字符串值有以下好处

  • embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次
  • 释放 embstr 编码的字符串对象只需要调用一次内存释放函数, 而释放 raw 编码的字符串对象需要调用两次内存释放函数
  • 因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面, 所以这种编码的字符串对象比起 raw 编码的字符串对象能够更好地利用缓存带来的优势

编码的转换

  • 对于 int 编码的字符串对象来说, 如果我们向对象执行了一些命令, 使得这个对象保存的不再是整数值, 而是一个字符串值, 那么字符串对象的编码将从 int 变为 raw
  • Redis 没有为 embstr 编码的字符串对象编写任何相应的修改程序 (只有 int 编码的字符串对象和 raw 编码的字符串对象有这些程序), 所以 embstr 编码的字符串对象实际上是只读的: 当我们对 embstr 编码的字符串对象执行任何修改命令时, 程序会先将对象的编码从 embstr 转换成 raw , 然后再执行修改命令; 因为这个原因, embstr 编码的字符串对象在执行修改命令之后, 总会变成一个 raw 编码的字符串对象

列表对象

列表对象的编码可以是 ziplist 或者 linkedlist
ziplist的结构如下(执行rpush numbers 1 “three” 5)


linkedlist的结构如下

其中StringObject就是图8.4的结构
当列表对象可以同时满足以下两个条件时, 列表对象使用 ziplist 编码

  • 列表对象保存的所有字符串元素的长度都小于 64 字节(可通过配置文件里 list-max-ziplist-value 调节)
  • 列表对象保存的元素数量小于 512 个 (可通过配置文件里 list-max-ziplist-entries 调节)

哈希对象

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

  • 保存了同一键值对的两个节点总是紧挨在一起, 保存键的节点在前, 保存值的节点在后
  • 先添加到哈希对象中的键值对会被放在压缩列表的表头方向, 而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向

ziplist结构(执行HSET profile name “Tom”;HSET profile age 25;HSET profile career “Programmer”)



hashtable结构

当哈希对象可以同时满足以下两个条件时, 哈希对象使用 ziplist 编码

  • 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节(可通过配置文件里 hash-max-ziplist-value 调节)
  • 哈希对象保存的键值对数量小于 512 个(可通过配置文件里 hash-max-ziplist-entries 调节)

集合对象

集合对象的编码可以是 intset 或者 hashtable
inset结构(SADD numbers 1 3 5)


hashtable结构(SADD fruits “apple” “banana” “cherry”)

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

  • 集合对象保存的所有元素都是整数值
  • 集合对象保存的元素数量不超过 512 个(可通过配置文件里 set-max-intset-entries 调节)

有序集合对象

有序集合的编码可以是 ziplist 或者 skiplist

1
2
3
4
typedef struct zset {
zskiplist *zsl;//跳跃表
dict *dict;//字典
} zset;

ziplist 编码的有序集合对象使用压缩列表作为底层实现, 每个集合元素使用两个紧挨在一起的压缩列表节点来保存, 第一个节点保存元素的成员(member), 而第二个元素则保存元素的分值(score),压缩列表内的集合元素按分值从小到大进行排序, 分值较小的元素被放置在靠近表头的方向, 而分值较大的元素则被放置在靠近表尾的方向
ziplist结构(执行ZADD price 8.5 apple 5.0 banana 6.0 cherry)



skiplist结构

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

  • 有序集合保存的元素数量小于 128 个(可通过配置文件里 zset-max-ziplist-entries 调节)
  • 有序集合保存的所有元素成员的长度都小于 64 字节(可通过配置文件里 zset-max-ziplist-value 调节)

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

在理论上来说, 有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现, 但无论单独使用字典还是跳跃表, 在性能上对比起同时使用字典和跳跃表都会有所降低。

举个例子, 如果我们只使用字典来实现有序集合, 那么虽然以 O(1) 复杂度查找成员的分值这一特性会被保留, 但是, 因为字典以无序的方式来保存集合元素, 所以每次在执行范围型操作 —— 比如 ZRANK 、 ZRANGE 等命令时, 程序都需要对字典保存的所有元素进行排序, 完成这种排序需要至少 O(N \log N) 时间复杂度, 以及额外的 O(N) 内存空间 (因为要创建一个数组来保存排序后的元素)。

另一方面, 如果我们只使用跳跃表来实现有序集合, 那么跳跃表执行范围型操作的所有优点都会被保留, 但因为没有了字典, 所以根据成员查找分值这一操作的复杂度将从 O(1) 上升为 O(\log N) 。

因为以上原因, 为了让有序集合的查找和范围型操作都尽可能快地执行, Redis 选择了同时使用字典和跳跃表两种数据结构来实现有序集合。

类型检查与命令多态

Redis 中用于操作键的命令基本上可以分为两种类型
针对任何key都可以执行

  • DEL 命令
  • EXPIRE 命令
  • RENAME 命令
  • TYPE 命令
  • OBJECT 命令

特定key才能执行

  • SET 、 GET 、 APPEND 、 STRLEN 等命令只能对字符串键执行
  • HDEL 、 HSET 、 HGET 、 HLEN 等命令只能对哈希键执行
  • RPUSH 、 LPOP 、 LINSERT 、 LLEN 等命令只能对列表键执行
  • SADD 、 SPOP 、 SINTER 、 SCARD 等命令只能对集合键执行
  • ZADD 、 ZCARD 、 ZRANK 、 ZSCORE 等命令只能对有序集合键执行

如何针对特定的key才可以检查的流程图如下

内存回收

Redis 在自己的对象系统中构建了一个引用计数(reference counting)技术实现的内存回收机制, 通过这一机制, 程序可以通过跟踪对象的引用计数信息, 在适当的时候自动释放对象并进行内存回收(refcount支配),对象的整个生命周期可以划分为创建对象、操作对象、释放对象三个阶段

  • 在创建一个新对象时, 引用计数的值会被初始化为 1
  • 当对象被一个新程序使用时, 它的引用计数值会被增一(api -> incrRefCount)
  • 当对象不再被一个程序使用时, 它的引用计数值会被减一(api -> decrRefCount)
  • 当对象的引用计数值变为 0 时, 对象所占用的内存会被释放(api -> resetRefCount)

对象共享

创建共享字符串对象的数量可以通过修改 redis.h/REDIS_SHARED_INTEGERS 常量来修改
OBJECT REFCOUNT key 命令来查看共享数量

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

  • 将数据库键的值指针指向一个现有的值对象
  • 将被共享的值对象的引用计数增一

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

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

当服务器考虑将一个共享对象设置为键的值对象时, 程序需要先检查给定的共享对象和键想创建的目标对象是否完全相同, 只有在共享对象和目标对象完全相同的情况下, 程序才会将共享对象用作键的值对象, 而一个共享对象保存的值越复杂, 验证共享对象和目标对象是否相同所需的复杂度就会越高, 消耗的 CPU 时间也会越多:

  • 如果共享对象是保存整数值的字符串对象, 那么验证操作的复杂度为 O(1)
  • 如果共享对象是保存字符串值的字符串对象, 那么验证操作的复杂度为 O(N)
  • 如果共享对象是包含了多个值(或者对象的)对象, 比如列表对象或者哈希对象, 那么验证操作的复杂度将会是 O(N^2)

因此, 尽管共享更复杂的对象可以节约更多的内存, 但受到 CPU 时间的限制, Redis 只对包含整数值的字符串对象进行共享

对象的空转时长

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

OBJECT IDLETIME 命令的实现是特殊的, 这个命令在访问键的值对象时, 不会修改值对象的 lru 属性

除了可以被 OBJECT IDLETIME 命令打印出来之外, 键的空转时长还有另外一项作用: 如果服务器打开了 maxmemory 选项, 并且服务器用于回收内存的算法为 volatile-lru 或者 allkeys-lru , 那么当服务器占用的内存数超过了 maxmemory 选项所设置的上限值时, 空转时长较高的那部分键会优先被服务器释放, 从而回收内存