1_7_Redis设计与实现读书记-对象

对象

Redis使用基于字符串(SDS)、双端链表、字典、压缩列表、整数集合等数据结构创建了一个对象系统，包含字符串对象、列表对象、哈希对象、集合对象和有序对象这五种类型的对象。每种对象至少用了有种数据结构。

Redis对象系统实现了基于引用计数技术的内存回收机制，程序不再使用某对象时，对象所占用的内存就会被自动释放。Redis还通过引用计数技术实现了对象共享机制，可以再适当条件下，通过让多个数据库键共享同一个对象来节约内存。

1. 对象的类型与编码

Redis使用对象来表示数据库中的键和值，则在Redis中创建一个键值对时，至少会创建两个对象，一个对象作为键值对的键，另一个对象用作键值对的值。

redis> SET msg "hello world”

例如：在SET对象创建一个新的键值对，其中键值对的键是一个包含了字符串值“msg”的对象，而键值对的值则是一个包含了字符串的值“helloworld”。

typedef struct redisObject{
    // 类型
    unsigned type:4;
    // 编码
    unsigned ecoding:4;
    // 指向底层实现数据结构的指针
    void *ptr;
    // ....
}robj;

1.1 类型

type属性记录了对象的类型：

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

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

字符串键 ——> 数据库键所对应的值为字符串对象

列表键 ——> 数据库键所对应的值为列表对象

当执行TYPE命令时，返回的结果应该为数据库键对应的值对象类型，而不是键对象的类型：

# 键为字符串对象， 值为字符串对象
redis> SET msg "hello world"
OK

redis> TYPE msg
string

#键为字符串对象，值为列表对象
redis> RPUSH numbers 2 4 6
(integer) 3

redis> TYPE numbers
list

#键为字符串对象，值为哈希对象
redis> HMSET users name TOM age 25 career Programmer
OK

redis> TYPE users
hash

#键为字符串对象，值为集合对象
redis> SADD fruits apple banana cherry
(integer) 3

redis> TYPE fruits
set

#键为字符串对象，值为有序集合对象
redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3

redis> TYPE price
zset

1.2 编码和底层实现

对象 ptr 指针指向对象的底层实现数据结构，数据结构由对象encoding属性决定。

编码常量	编码所对应的底层数据结构
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 命令可以查看一个数据库键的值对象的编码。

embstr的好处有如下几点：

• embstr的创建只需分配一次内存，而raw为两次（一次为SDS分配对象，另一次为OBJECT分配对象，embstr省去了第一次）。

• 相对地，释放内存的次数也由两次变为一次。

• embstr的OBJECT和SDS放在一起，更好地利用缓存带来的优势。

**注意：**redis并未提供任何修改embstr的方式，即embstr是只读的形式。对embstr的修改实际上是先转换为raw再进行修改。

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的灵活性和效率。因此可以根据不同的使用场景来为一个对象设置不同的编码，从而优化对象在某一场景下的效率。

Redis在列表对象包含的元素比较少时，使用压缩表作为列表对象的底层实现；当对象元素越来越多时，将会转换为功能更强、更适合保存大量元素的双端链表作为底层实现。

2. 字符串对象

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

• 如果字符串对象保存的是整数值，并且这个值可以用long类型表示，则字符串对象会将这个值保存在字符串对象的ptr属性里（void*转换long），并将字符串对象的编码设置为int。

  

• 如果保存的是一个字符串值，并且这个值长度大于32字节，则字符串对象将使用一个简单动态字符（SDS）来保存这个字符串值，并将编码设置为raw。

• 如果保存的是一个字符串值，并且这个值的长度小于等于32字节，那么字符串对象将使用embstr编码的方式保存这个字符串值。

注：

1. embstr编码时专门用于保存短字符的一种优化编码的方式，这种方式和raw编码一样使用redisObject结构和sdshdr结构表示字符串对象。
2. raw编码会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构。
3. embstr编码通过调用一次内存分配函数来分配一块连续的空间，空间中依次包含redisObject和sdshdr两个结构。

   

   embstr编码的字符串对象在执行命令时，与raw编码的字符串对象执行命令时产生的效果是相同的。

embstr编码的字符串保存段字符串的好处：

1. embstr编码内存分配次数从raw编码的两次降为一次
2. 释放embstr编码对象只需要调用一次内存释放函数，raw需要调用两次
3. embstr保存的字符串对象都保存在一块连续的内存中，相比raw更能够利用缓存带来的优势。

   

   可用long double类型表示的浮点数在Redis中也是作为字符串保存的。

​ 浮点数 ——> 字符串值 ——> 保存字符串值

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

2.1 编码转换

int编码和embstr编码的字符串对象在满足条件下，会被转换成raw编码的字符串对象。

embstr编码字符串对象没有提供任何修改命令，则embstr编码对象实际是只读的。对象执行修改时，会先将embstr转换成raw，然后再执行修改命令。因此，embstr经过修改后，最终会变成一个raw编码的字符串对象。

2.2 字符串命令的实现

字符串键的值为字符串对象，则用于字符串键的所有命令都是针对于字符串对象构建的。

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

3. 列表对象

列表对象的编码可以是ziplist或者linkedlist。

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

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

**注意：**linkedlist 编码的列表对象在此次的双端链表结构中包含了许多字符串对象。嵌套字符串的行为在哈希对象、集合对象和有序集合对象中都会出现。字符串对象时Redis五种类型的对象中唯一会被其他四种类型对象嵌套的对象。

StringObject 结构：

3.1 编码转换

列表对象使用ziplist编码的条件：

1. 列表对象保存的元素数量小于512个
2. 列表对象保存的所有字符串元素的长度都小于64字节

否则，需要使用linkedlist编码。

3.2 列表的实现

因为列表键的值为列表对象，作为用于列表键的所有命令都是针对于列表对象构建。

4. 哈希对象

哈希对象的编码可以是ziplist或者是hashtable。

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

因此：

• 保存了同一键值对的两个节点总是紧挨一起，键在前，值在后。
• 先添加的键值对在压缩表的表头方向，后添加的在表尾。

hashtable 编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都是用一个字典键值对来保存：

• 字典的每个键都是一个字符串对象保存键值对的键
• 字典的每个值都是一个字符串对象保存键值对的值

  

  StringObject 对象（一个字符串对象）：

  

4. 1 编码转换

哈希表使用ziplist编码的条件：

• 哈希表对象保存的所有键值对的键和值的字符串长度都小于64字节
• 哈希表对象保存的键值对数量小于512个

否则，哈希表对象需要使用hashtable编码

4.2 哈希命令的实现

哈希键的值为哈希对象，则哈希键的所有命令都是针对于哈希对象来构建的。

5. 集合对象

集合对象的编码可以是intset或者hashtable。

intset编码的集合对象使用整数集合作为底层实现，所有元素都被保存在整数集合里面。

hashtable 编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值全部设置为NULL。

对于使用hashtable实现集合对象，有些疑问：

5.1 编码的转换

集合对象使用 intset 编码的条件

• 集合对象保存的所有元素都是整数值
• 集合对象保存的元素数量不超过512个

否则，若有一个条件不满足，则使用hashtable编码实现集合对象。

5.2 集合命令的实现

因为集合键的值为集合对象，则用于集合键的所有命令都是针对于集合对象来构建。

命令	intset编码的实现方法	hashtable编码的实现方法
SADD	调用intsetAdd函数，将新元素加到整数集合	调用dictAdd函数，以新元素为键，NULL为值，将键值对添加到字典里
SCARD	调用intsetLen函数，返回整数集合所包含的元素数量，即集合对象包含的元素数量	调用dictSize函数，返回字典所包含的键值对数量，即集合对象包含的元素数量
SISMEMBER	调用intsetFind函数，在整数集合中查找给定的元素，找到则存在，反之，元素不存在	调用dictFind函数，在字典的键中查找给定的元素，找到则存在，反之，元素不存在
SMEMBERS	遍历整个整数集合，使用intsetGet函数返回集合元素	遍历整个字典，使用dictGetKey函数返回字典的键作为集合元素
SRANDMEMBER	调用intsetRandom函数，在整数集合中随机返回一个元素	调用dictGetRandomKey函数，从字典中随机返回一个字典键
SPOP	调用intsetRandom函数，从整数集合中随机取出一个元素，将元素返回给客户端后，调用intsetRemove 函数，将随机元素从整数集合中删除	调用dictGetRandomKey函数，从字典中随机取出一个字典键，将字典键返回给客户端后，调用dictDelete函数，从字典中删除随机字典键对应的键值对
SREM	调用intsetRemove函数，从整数集合中删除所有给定的元素	嗲用dictDelete函数，从字典中删除所有键为给定元素的键值对

6. 有序集合对象

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

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

压缩列表内的集合元素按照分值从小到大进行排序，分值小靠近表头，分值大靠近表尾方向。

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

typedef struct zset{
    zskiplist *zsl;
    dict *dict;
}zset;

zset结构：

• zsl 跳跃表按分值从小到大保存了所有集合元素，每个跳跃表都保存了一个集合元素。（跳跃表节点的object属性保存了元素的成员，score属性则保存了元素的分值）

(ZRANGE,ZRANK 等命令就是基于跳跃表API实现)

• dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素。（字典的键保存元素的成员，值保存元素的分值）

通过使用字典，可以使用O(1)复杂度查找给定成员的分值（ZSCORE命令据此实现）。

有序集合中的元素成员都是一个字符串对象，每个元素的分值都是一个double类型的浮点数。

注意：zset结构虽然同时使用跳跃表和字典保存有序集合元素，但是都会通过指针来共享相同元素的成员和分值。因此，不会造成浪费额外的内存空间。

6.1 编码的转换

使用ziplist编码的条件：

• 有序集合保存的元素数量小于128个
• 有序集合保存的所有元素成员的长度都小于64字节

否则，以上任意一个条件不满足，则使用skiplist编码。

ziplist ==> skiplist （原本保存在压缩列表中的所有元素都会被转移并且保存到zset结构中，对象的编码也会从ziplist变为skiplist）

6.2 有序集合命令的实现

7. 类型检查与命令多态

Redis中的命令分两种类型：

1. 可以对任何类型的键执行：DEL、EXPIRE、RENAME、TYPE、OBJECT等
2. 只能对特定类型的键执行。

7.1 类型检查的实现

为了确保只有指定类型的键可以执行某些特定的定名，在执行一个类型特定命令之前，先检查输入键的类型，然后再决定是否执行给定的命令。

类型特定命令通过redisObject结构的type属性进行检查。

执行特定命令之前，服务器先会检查输入数据库键的值对象是否为执行命令所需的类型。是所需类型就执行。否则，拒绝执行命令，返回类型错误。

例如：执行 LLEN命令

7.2 多态命令的实现

除了根据值对象的类型来判断键是否能够执行指定命令外，还会根据值对象的编码方式选择正确的命令执行。

例子：对列表对象执行LLEN命令

• 如果列表编码为ziplist，则使用ziplistLen函数返回列表长度。

• 如果列表编码为linkedlist，则使用listLength函数返回双端链表的长度。

  

  多态命令的分类：

• 基于类型的多态：一个命令可以同时用于处理多种不同类型的键

• 基于编码的多态：一个命令可以同时用于处理多种不同编码

8. 内存回收

因为C语言不具备自动内存回收的功能。Redis在自己的对象系统中构建了一个引用计数器技术实现内存回收机制。通过跟踪对象的引用计数信息，对对象进行释放回收内存。

typedef struct redisObject{
    // 类型
    unsigned type:4;
    // 编码
    unsigned ecoding:4;
    // 指向底层实现数据结构的指针
    void *ptr;
    // 引用计数
    int refcount;
    // ...
}robj;

对象的引用计数信息会随着对象的使用状态不断变化：

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

对象的整个生命周期：创建对象、操作对象、释放对象三个阶段。

9. 对象共享

引用计数器除了实现对象回收机制，还带有对象共享的作用。

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

1. 将数据库键的值指针指向一个现有的值对象；
2. 将被共享的值对象的引用计数增一。

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

例：创建一个值为100的键A，使用OBJECT REFCOUNT命令查看键A的值对象的引用计数为2，包含； 服务器程序以及共享这个值对象的键A。若再创建一个值为100的键B，此时引用计数值变为3。

这些共享对象不但只有字符串键可以使用，在数据结构中嵌套了字符串对象的对象（linkedlist列表对象、hashtable哈希对象、hashtable集合对象、zset编码的有序集合对象）都可以使用共享对象。

10. 对象的空转时长

typedef struct redisObject{
    // 类型
    unsigned type:4;
    // 编码
    unsigned ecoding:4;
    // 指向底层实现数据结构的指针
    void *ptr;
    // 引用计数
    int refcount;
    // 最后一次被访问的时间
    unsigned lru:22;
    // ...
}robj;

lru属性：记录了对象最后一次被访问的时间。

OBJECT IDLETIME 可以打印出给定键的空转时长。通过将当前时间减去键的值对象的lru时间计算出的。

**注意：**此命令实现特殊，在访问键的值对象时，不会修改值对象的lru属性。

键的空转时长：当服务器打开了maxmemory选项时，服务器用于回收内存的算法为volatile-lru或者allkeys-lru，则当服务器占用的内存数超过maxmemory设置的上限值时，空转时长高的键会优先被释放，回收内存。

11. 回顾