Redis设计与实现读书笔记——第8章 对象

Redis 并没有直接使用sds、dict等数据结构来实现键值对数据库， 而是基于这些数据结构创建了一个对象系统， 这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象， 每种对象都用到了至少一种前面所介绍的数据结构。

简介

对象的好处：

  • 根据对象的类型来判断是否可以执行给定的命令。
  • 针对不同的使用场景， 为对象设置多种不同的数据结构实现， 从而优化对象在不同场景下的使用效率。

对象的特性：

  • 基于引用计数技术的内存回收机制（和java的是否原理相似）
  • 通过引用计数技术实现对象共享机制，多个键共享同一个对象来节约内存
  • 带有访问时间记录信息，可以用来删除空转时长较大的键

8.1 对象的类型与编码

Redis 使用对象来表示数据库中的键和值，创建一个新的键值对的时候，至少包含两个对象：1. 键对象 2. 值对象

对象都由一个 redisObject 结构表示，保存数据相关的属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct redisObject {
    // 对象类型
    unsigned type:4;
    // 编码
    unsigned encoding:4;
    //lru 时钟 记录最后被访问的时间，也就是空转时长
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits decreas time). */
    // 引用计数 实现内存自动回收等。
    int refcount;
    // 指向底层实现数据结构的指针
    void *ptr;
} robj;

ptr指向的就是之前的sds，dict这些数据结构的内存地址。

变量申明加冒号的用法： 是C语言的位域的用法。:后面的数字用来限定成员变量占用的位数。冒号后面的数字说明只会用到对应多少个bit位。type只会用到4个bit，encoding 也只会用的4个bit。变量占用的内存不再是有类型决定，而是位域。

8.1.1 类型

type属性的值包括5种：

类型常量 对象的名称
REDIS_STRING 字符串对象
REDIS_LIST 列表对象
REDIS_HASH 哈希对象
REDIS_SET 集合对象
REDIS_ZSET 有序集合对象

键对象只能是字符串对象，而值对象则5种之一。所以执行TYPE命令返回的是键值对中值对象的类型。

type命令的

对象 对象 type 属性的值 TYPE 命令的输出
字符串对象 REDIS_STRING "string"
列表对象 REDIS_LIST "list"
哈希对象 REDIS_HASH "hash"
集合对象 REDIS_SET "set"
有序集合对象 REDIS_ZSET "zset"

8.2 编码和底层实现

ptr指向底层数据结构，而encoding则决定了具体应该指向什么样的数据结构实现。之所以不能用type来决定指向的具体数据结构，是因为同一种对象，但是底层实现会有不同的数据结构。

编码常量 编码所对应的底层数据结构
REDIS_ENCODING_INT long 类型的整数
REDIS_ENCODING_EMBSTR embstr 编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 双端链表
REDIS_ENCODING_ZIPLIST 压缩列表
REDIS_ENCODING_INTSET 整数集合
REDIS_ENCODING_SKIPLIST 跳跃表和字典

每种类型的对象都至少使用了两种不同的编码，对应关系为：

类型 编码 对象
REDIS_STRING REDIS_ENCODING_INT 使用整数值实现的字符串对象。
REDIS_STRING REDIS_ENCODING_EMBSTR 使用 embstr 编码的简单动态字符串实现的字符串对象。
REDIS_STRING REDIS_ENCODING_RAW 使用简单动态字符串实现的字符串对象。
REDIS_LIST REDIS_ENCODING_ZIPLIST 使用压缩列表实现的列表对象。
REDIS_LIST REDIS_ENCODING_LINKEDLIST 使用双端链表实现的列表对象。
REDIS_HASH REDIS_ENCODING_ZIPLIST 使用压缩列表实现的哈希对象。
REDIS_HASH REDIS_ENCODING_HT 使用字典实现的哈希对象。
REDIS_SET REDIS_ENCODING_INTSET 使用整数集合实现的集合对象。
REDIS_SET REDIS_ENCODING_HT 使用字典实现的集合对象。
REDIS_ZSET REDIS_ENCODING_ZIPLIST 使用压缩列表实现的有序集合对象。
REDIS_ZSET REDIS_ENCODING_SKIPLIST 使用跳跃表和字典实现的有序集合对象。

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

1
2
3
4
5
redis> SET msg "hello wrold"
OK

redis> OBJECT ENCODING msg
"embstr"

不同编码的对象所对应的OBJECT ENCODING输出：

表 8-5 OBJECT ENCODING 对不同编码的输出

对象所使用的底层数据结构 编码常量 OBJECT ENCODING 命令输出
整数 REDIS_ENCODING_INT "int"
embstr 编码的简单动态字符串（SDS） REDIS_ENCODING_EMBSTR "embstr"
简单动态字符串 REDIS_ENCODING_RAW "raw"
字典 REDIS_ENCODING_HT "hashtable"
双端链表 REDIS_ENCODING_LINKEDLIST "linkedlist"
压缩列表 REDIS_ENCODING_ZIPLIST "ziplist"
整数集合 REDIS_ENCODING_INTSET "intset"
跳跃表和字典 REDIS_ENCODING_SKIPLIST "skiplist"

使用encoding属性来设定对象指向的具体数据结构实现的好处：灵活与效率。根据不同场景来给同一种对象设置不同的数据结构实现。

举个例子， 在列表对象包含的元素比较少时， Redis 使用压缩列表作为列表对象的底层实现：

  • 因为压缩列表比双端链表更节约内存， 并且在元素数量较少时， 在内存中以连续块方式保存的压缩列表比起双端链表可以更快被载入到缓存中；
  • 随着列表对象包含的元素越来越多， 使用压缩列表来保存元素的优势逐渐消失时， 对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表上面；

是不是也可以理解成多态呢？

8.2 字符串对象

字符串对象的编码可以是 int 、 raw 或者 embstr 。

  1. 保存的对象是整数，而且可以用long类型表示：ptr指针指向一个long类型的内存地址。（是不是不用指向sdshdr了），然后将encoding 设置为REDIS_ENCODING_INT (应该在源码中有个宏定义)
  2. 保存的对象是字符串值，长度小于44字节（书上的39字节，但是先版本已经更新）。这种短字符串对象，直接只调用一次内存分配函数来分配一块连续的空间 依次包含redisObject和sdshdr两个结构。
  3. 字符串长度大于等于44字节的时候使用raw编码。会调用两次内存分配函数来创建redisObject结构和sdshdr结构。

embstr编码的好处：

  • 只用分配一次内存，raw编码需要两次
  • 释放embstr的sds也只需要一次内存释放函数，raw两次
  • embstr的所有数据（对象结构，字符串结构）在连续的一块内存里面，从而可以更好地利用缓存带来的优势

embstr和raw的示意图，摘自书上，但是注意sds的结构稍有变化。

raw编码：

embstr编码：

注意：

long double类型的浮点数是转换成字符串值来保存的。执行的时候取出字符串再转换成long double 类型。

值 编码
可以用 long 类型保存的整数。 int
可以用 long double 类型保存的浮点数。 embstr 或者 raw
字符串值， 或者因为长度太大而没办法用 long 类型表示的整数， 又或者因为长度太大而没办法用 long double 类型表示的浮点数。 embstr 或者 raw

8.2.1 编码的转换

当保存的值发生变化的时候会进行转换，比如保存的整数值变成了字符串，那么编码从int 变成raw或者embstr。

注意： Redis 没有为embstr编写任何修改程序，只有int和raw编码的字符串对象有这些程序，所以embstr编码的对象是只读，因此发生修改的话会从embstr变成raw。

发生修改的源码中应该是将原来的ptr指向的数据结构内存释放掉后，重新指向新创建的对象。

8.2.2 字符串命令的实现

所有命令都是针对字符串对象的。

命令 int 编码的实现方法 embstr 编码的实现方法 raw 编码的实现方法
SET 使用 int 编码保存值。 使用 embstr 编码保存值。 使用 raw 编码保存值。
GET 拷贝对象所保存的整数值， 将这个拷贝转换成字符串值， 然后向客户端返回这个字符串值。 直接向客户端返回字符串值。 直接向客户端返回字符串值。
APPEND 将对象转换成 raw 编码， 然后按 raw编码的方式执行此操作。 将对象转换成 raw 编码， 然后按 raw编码的方式执行此操作。 调用 sdscatlen 函数， 将给定字符串追加到现有字符串的末尾。
INCRBYFLOAT 取出整数值并将其转换成 longdouble 类型的浮点数， 对这个浮点数进行加法计算， 然后将得出的浮点数结果保存起来。 取出字符串值并尝试将其转换成long double 类型的浮点数， 对这个浮点数进行加法计算， 然后将得出的浮点数结果保存起来。 如果字符串值不能被转换成浮点数， 那么向客户端返回一个错误。 取出字符串值并尝试将其转换成 longdouble 类型的浮点数， 对这个浮点数进行加法计算， 然后将得出的浮点数结果保存起来。 如果字符串值不能被转换成浮点数， 那么向客户端返回一个错误。
INCRBY 对整数值进行加法计算， 得出的计算结果会作为整数被保存起来。 embstr 编码不能执行此命令， 向客户端返回一个错误。 raw 编码不能执行此命令， 向客户端返回一个错误。
DECRBY 对整数值进行减法计算， 得出的计算结果会作为整数被保存起来。 embstr 编码不能执行此命令， 向客户端返回一个错误。 raw 编码不能执行此命令， 向客户端返回一个错误。
STRLEN 拷贝对象所保存的整数值， 将这个拷贝转换成字符串值， 计算并返回这个字符串值的长度。 调用 sdslen 函数， 返回字符串的长度。 调用 sdslen 函数， 返回字符串的长度。
SETRANGE 将对象转换成 raw 编码， 然后按 raw编码的方式执行此命令。 将对象转换成 raw 编码， 然后按 raw编码的方式执行此命令。 将字符串特定索引上的值设置为给定的字符。
GETRANGE 拷贝对象所保存的整数值， 将这个拷贝转换成字符串值， 然后取出并返回字符串指定索引上的字符。 直接取出并返回字符串指定索引上的字符。 直接取出并返回字符串指定索引上的字符。

8.8 内存回收

Redis通过跟踪对象的引用计数信息，在适当的时候自动释放对象并进行内存回收。

计数信息由 redisObject 结构的 refcount 属性记录

  • 在创建一个新对象时， 引用计数的值会被初始化为 1 ；
  • 当对象被一个新程序使用时， 它的引用计数值会被增一；
  • 当对象不再被一个程序使用时， 它的引用计数值会被减一；
  • 当对象的引用计数值变为 0 时， 对象所占用的内存会被释放。

对应的API：

函数 作用
incrRefCount 将对象的引用计数值增一。
decrRefCount 将对象的引用计数值减一， 当对象的引用计数值等于 0 时， 释放对象。
resetRefCount 将对象的引用计数值设置为 0 ， 但并不释放对象， 这个函数通常在需要重新设置对象的引用计数值时使用。

对象生命周期可以划分为创建对象、操作对象、释放对象三个阶段

一个字符串对象从创建到释放的整个过程：

1
2
3
4
5
6
7
8
// 创建一个字符串对象 s ，对象的引用计数为 1
robj *s = createStringObject(...)

// 对象 s 执行各种操作 ...

// 将对象 s 的引用计数减一，使得对象的引用计数变为 0
// 导致对象 s 被释放
decrRefCount(s)

是不是通过计算指向对象这块内存的指针数量来实现的？

8.9 对象共享

对于整数值的字符串对象（int编码），在新创建一个字符串对象的时候如果有这个值的字符串对象存在，就不再为新键创建字符串对象，而是将这个新键指向之前已经存在了的字符串对象。然后将这个字符串对象的引用+1。主要目的是节约内存。

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

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

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

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

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

因此， 尽管共享更复杂的对象可以节约更多的内存， 但受到 CPU 时间的限制， Redis 只对包含整数值的字符串对象进行共享。 （时刻在空间与时间上做权衡）

8.9 对象的空转时长

lru 属性， 该属性记录了对象最后一次被命令程序访问的时间。

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

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

lru的主要作用就是配合maxmemory选项，淘汰不常用的键值对。

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

疑惑

  1. 为什么在一块连续的内存里面可以更好地利用缓存带来的优势？
  2. 引用计数的程序怎么定义？是指线程吗？
  3. 引用计数的具体实现？
  4. 对象共享的时候怎么去判断存不存在已经创建了这个整数值的对象？对整个数据库遍历吗？