ccran 的个人博客 ccran 的个人博客

记录精彩的程序人生

目录
Redis设计与实现(5)对象
/  

Redis设计与实现(5)对象

Redis设计与实现(5)对象

1. 总览

Redis通过对SDS、双端链表、字典、整数集合、压缩列表之类数据结构进行封装来构成对象。

封装成对象可以根据具体场景来选择具体实现,优化使用效率。

对象系统内置引用计数的内存回收机制,并通过引用计数进行对象共享。

对象附带有访问时间记录信息,用于在服务器启用maxmemory功能情况下,可能会优先删除最久未使用对象。

每当在Redis中新建一个键值对时,至少会创建两个对象:键对象和值对象。

Redis对象robj:

typedef struct redisObject{
    unsigned type;//类型
    unsigned encoding;//编码
    void *ptr;//指向底层实现数据结构的指针
    //...
} robj;
  1. type记录了对象的类型,对应了Redis支持的五种基本数据类型。

通过TYPE命令可以获取值对象的数据类型

类型常量对象的名称TYPE命令输出
REDIS_STRING字符串对象"string"
REDIS_LIST列表对象"list"
REDIS_HASH哈希对象"hash"
REDIS_SET集合对象"set"
REDIS_ZSET有序集合对象"zset"
127.0.0.1:6379> set msg hello,world
OK
127.0.0.1:6379> type msg
string
  1. encoding指定了对象的具体数据类型。该值可以为如下表列出的常量之一。可以通过OBJECT ENCODING命令查看值对象编码。
编码常量编码对应底层数据结构OBJECT ENCODING输出
REDIS_ENCODING_INTlong类型整数"int"
REDIS_ENCODING_EMBSTRembstr编码的简单动态字符串SDS"embstr"
REDIS_ENCODING_RAW简单动态字符串SDS"raw"
REDIS_ENCODING_HT字典"hashtable"
REDIS_ENCODING_LINKEDLIST双端链表"linkedlist"
REDIS_ENCODING_ZIPLIST压缩列表"ziplist"
REDIS_ENCODING_INTSET整数集合"intset"
REDIS_ENCODING_SKIPLIST跳表和字典"skiplist"
127.0.0.1:6379> set msg hello,world
OK
127.0.0.1:6379> sadd nums 1 2 3 4 5 6
(integer) 6
127.0.0.1:6379> sadd info ccran 18 hello 20 world
(integer) 5
127.0.0.1:6379> object encoding msg
"embstr"
127.0.0.1:6379> object encoding nums
"intset"
127.0.0.1:6379> object encoding info
"hashtable"

每种类型的对象至少使用了两种不同的编码,每种类型的对象可以使用的编码如下表所示。

类型编码对象
REDIS_STRINGREDIS_ENCODING_INT整数值实现字符串对象
REDIS_STRINGREDIS_ENCODING_EMBSTRembstr编码的简单动态字符串SDS实现字符串对象
REDIS_STRINGREDIS_ENCODING_RAW简单动态字符串SDS实现字符串对象
REDIS_LISTREDIS_ENCODING_ZIPLIST压缩列表实现列表对象
REDIS_LISTREDIS_ENCODING_LINKEDLIST双端链表实现列表对象
REDIS_HASHREDIS_ENCODING_ZIPLIST压缩列表实现哈希对象
REDIS_HASHREDIS_ENCODING_HT字典实现哈希对象
REDIS_SETREDIS_ENCODING_INTSET整数集合实现集合对象
REDIS_SETREDIS_ENCODING_HT字典实现集合对象
REDIS_ZSETREDIS_ENCODING_ZIPLIST压缩列表实现有序集合对象
REDIS_ZSETREDIS_ENCODING_SKIPLIST跳表和字典实现有序集合对象

通过encoding属性指定对象使用编码,极大地提升了Redis的灵活性和效率。

2. 字符串对象

字符串对象的编码可以为int、embstr、raw

2.1 字符串编码

  1. 如果字符串是整数值并且可以用long来存储(不会溢出),则对象编码为int
127.0.0.1:6379> set num 10086
OK
127.0.0.1:6379> object encoding num
"int"
  1. 如果字符串长度大于32字节,使用SDS保存这个字符串值,则对象编码为raw
127.0.0.1:6379> set story "Long,long long ago there lived a king ..."
OK
127.0.0.1:6379> object encoding story
"raw"

strraw.png

  1. 如果字符串长度小于32字节,使用embstr编码保存字符串值,对象编码为embstr。
127.0.0.1:6379> set msg "hello"
OK
127.0.0.1:6379> object encoding msg
"embstr"

strembstr.png

1)embstr相比于raw两次分配redisObject与sdshdr,仅需一次分配;与之相对,embstr释放也仅需一次释放。

2)embstr编码的字符串对象保存在一块连续的内存中,根据局部性原理,能更好的利用缓存带来的优势。

  1. 浮点数的存储通过存储浮点数对应的字符串值实现,使用时需要进行字符串与浮点数之间的转换。
127.0.0.1:6379> set PI 3.1415926
OK
127.0.0.1:6379> object encoding PI
"embstr"
127.0.0.1:6379> set PI 3.141592611111111111111111333333333333111111111111111111111111111111
OK
127.0.0.1:6379> object encoding PI
"raw"

2.2 编码转换

  1. 通过APPEND命令对int编码的字符串对象追加字符串,导致编码转换为raw
  2. embstr编码字符串对象是只读的,修改embstr编码字符串,导致编码转换为raw
127.0.0.1:6379> set num 10086
OK
127.0.0.1:6379> object encoding num
"int"
127.0.0.1:6379> append num 123
(integer) 8
127.0.0.1:6379> object encoding num
"raw"
127.0.0.1:6379> set name ccran
OK
127.0.0.1:6379> object encoding name
"embstr"
127.0.0.1:6379> append name ".cool"
(integer) 10
127.0.0.1:6379> object encoding name
"raw"

2.3 命令的实现

strcommand.png

3. 列表对象

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

3.1 列表编码

  1. 使用压缩列表ziplist编码保存列表元素,每个列表元素为entry,entry中直接存储具体的列表元素值。
127.0.0.1:6379> rpush list 1 three 5
(integer) 3
127.0.0.1:6379> object encoding list
"ziplist"

listziplist.png

  1. 使用双向双端链表linkedlist编码保存列表元素,每个列表元素为node,node中的具体值为嵌套列表元素值的字符串对象。

listlinkedlist.png

3.2 编码转换

满足以下两个条件,列表对象使用压缩列表ziplist编码:

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

2)列表对象保存的元素数量小于512个

否则,使用linkedlist编码。

通过配置文件list-max-ziplist-value和list-max-ziplist-entries可以修改以上两个条件上限

以上两个条件任意一个不满足:压缩列表里面的所有列表元素会转移保存到双向双端链表里面。编码从ziplist转换为linkedlist。

# 所有元素的长度都小于 64 字节
redis> RPUSH blah "hello" "world" "again"
(integer) 3
redis> OBJECT ENCODING blah
"ziplist"
# 将一个 65 字节长的元素推入列表对象中
redis> RPUSH blah "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww"
(integer) 4
# 编码已改变
redis> OBJECT ENCODING blah
"linkedlist"

# 列表对象包含 512 个元素
redis> EVAL "for i=1,512 do redis.call('RPUSH', KEYS[1], i) end" 1 "integers"
(nil)
redis> LLEN integers
(integer) 512
redis> OBJECT ENCODING integers
"ziplist"
# 再向列表对象推入一个新元素,使得对象保存的元素数量达到 513 个
redis> RPUSH integers 513
(integer) 513
# 编码已改变
redis> OBJECT ENCODING integers
"linkedlist"

3.3 命令的实现

listcommand.png

4. 哈希对象

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

4.1 哈希编码

  1. 使用ziplist作为哈希编码:

1)键对象和值对象相邻存储,值对象在键对象后面

2)新加入的键值对对象会放在ziplist的表尾方向

redis> HSET profile name "Tom"
(integer) 1
redis> HSET profile age 25
(integer) 1
redis> HSET profile career "Programmer"
(integer) 1

hashziplist.png

hashziplist1.png

  1. 使用hashtable作为哈希编码:键对象和值对象都嵌套了字符串对象作为实现。

hashhashtable.png

4.2 编码转换

满足一下两个条件,哈希对象使用ziplist编码:

1)哈希对象保存的键对象和值对象字符串长度小于64字节

2)键值对数量小于512个

否则,使用hashtable编码。

通过配置文件hash-max-ziplist-value和hash-max-ziplist-entries可以修改以上两个条件上限

以上两个条件任意一个不满足:压缩列表里面的所有哈希元素会转移保存到哈希表里面。编码从ziplist转换为hashtable。

# 哈希对象只包含一个键和值都不超过 64 个字节的键值对
redis> HSET book name "Mastering C++ in 21 days"
(integer) 1
redis> OBJECT ENCODING book
"ziplist"
# 向哈希对象添加一个新的键值对,键的长度为 66 字节
redis> HSET book long_long_long_long_long_long_long_long_long_long_long_description "content"
(integer) 1
# 编码已改变
redis> OBJECT ENCODING book
"hashtable"

# 哈希对象只包含一个键和值都不超过 64 个字节的键值对
redis> HSET blah greeting "hello world"
(integer) 1
redis> OBJECT ENCODING blah
"ziplist"
# 向哈希对象添加一个新的键值对,值的长度为 68 字节
redis> HSET blah story "many string ... many string ... many string ... many string ... many"
(integer) 1
# 编码已改变
redis> OBJECT ENCODING blah
"hashtable"

# 创建一个包含 512 个键值对的哈希对象
redis> EVAL "for i=1, 512 do redis.call('HSET', KEYS[1], i, i) end" 1 "numbers"
(nil)
redis> HLEN numbers
(integer) 512
redis> OBJECT ENCODING numbers
"ziplist"
# 再向哈希对象添加一个新的键值对,使得键值对的数量变成 513 个
redis> HMSET numbers "key" "value"
OK
redis> HLEN numbers
(integer) 513
# 编码改变
redis> OBJECT ENCODING numbers
"hashtable"

4.3 命令的实现

hashcommand.png

5. 集合对象

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

5.1 集合编码

  1. 使用整数集合intset对集合对象编码:
redis> SADD numbers 1 3 5
(integer) 3

setintset.png

  1. 使用哈希表hashtable对集合对象编码:每个键是字符串对象,值为NULL
redis> SADD fruits "apple" "banana" "cherry"
(integer) 3

sethashtable.png

5.2 编码转换

集合对象满足以下两个条件使用intset编码:

  1. 所有元素值是整数值
  2. 元素个数不超过512个

否则,使用hashtable编码。

通过配置文件set-max-intset-entries可以修改元素个数上限

以上两个条件任意一个不满足:整数集合intset里面的所有集合元素会转移保存到哈希表里面。编码从intset转换为hashtable。

# 添加非整数值的元素
redis> SADD numbers 1 3 5
(integer) 3
redis> OBJECT ENCODING numbers
"intset"
redis> SADD numbers "seven"
(integer) 1
redis> OBJECT ENCODING numbers
"hashtable"

# 元素个数大于512个
redis> EVAL "for i=1, 512 do redis.call('SADD', KEYS[1], i) end" 1 integers
(nil)
redis> SCARD integers
(integer) 512
redis> OBJECT ENCODING integers
"intset"
redis> SADD integers 10086
(integer) 1
redis> SCARD integers
(integer) 513
redis> OBJECT ENCODING integers
"hashtable"

5.3 命令的实现

setcommand.png

6、有序集合对象

有序集合对象的编码可以为ziplist或者skiplist

6.1 有序集合编码

  1. 使用压缩列表ziplist编码:有序集合元素按照分值从小到大排列;分值紧挨集合元素;
redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3

szziplist.png

szziplist1.png

  1. 使用skiplist编码:
typedef struct zset {
    zskiplist *zsl; // 跳表
    dict *dict; // 字典
} zset;
  1. 跳表节点的score属性保存分值,object属性保存了元素;使用跳表来支持ZRANK、ZRANGE之类的分数范围查找
  2. 字典保存了元素映射分数的键值对;使用字典来支持ZSCORE之类的命令O(1)的时间复杂度用于查找元素的对应分数
  3. 跳表和字典通过指针共享元素和分数

szskiplist.png

szskiplist1.png

6.2 编码转换

当有序集合满足以下两个条件时,对象使用ziplist压缩列表编码:

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

否则,使用skiplist编码。

通过配置文件zset-max-ziplist-value和zset-max-ziplist-entries可以修改以上两个条件上限

以上两个条件任意一个不满足:压缩列表ziplist里面的所有有序集合元素会转移保存到zset结构里面。编码从ziplist转换为skiplist。

# 对象包含了 128 个元素
redis> EVAL "for i=1, 128 do redis.call('ZADD', KEYS[1], i, i) end" 1 numbers
(nil)
redis> ZCARD numbers
(integer) 128
redis> OBJECT ENCODING numbers
"ziplist"
# 再添加一个新元素
redis> ZADD numbers 3.14 pi
(integer) 1
# 对象包含的元素数量变为 129 个
redis> ZCARD numbers
(integer) 129
# 编码已改变
redis> OBJECT ENCODING numbers
"skiplist"

# 向有序集合添加一个成员只有三字节长的元素
redis> ZADD blah 1.0 www
(integer) 1
redis> OBJECT ENCODING blah
"ziplist"
# 向有序集合添加一个成员为 66 字节长的元素
redis> ZADD blah 2.0 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
(integer) 1
# 编码已改变
redis> OBJECT ENCODING blah
"skiplist"

6.3 命令的实现

szcommand.png

7、类型检查与命令多态

7.1 类型检查

  1. 命令可以对任意类型的值执行。比如DEL、EXPIRE、RENAME、TYPE、OBJECT等命令
  2. 命令可以对特定类型的值执行。比如SET设置字符串对象键值对,RPUSH在列表对象尾部添加元素

类型检查通过对redisObject的type字段的检查实现。

7.2 命令多态

命令多态指的就是即使不同对象的底层实现不同,命令也能确保正确。

如列表对象的底层实现encoding有ziplist和linkedlist,LLEN都能返回列表对象的长度。

tcce.png

8、内存回收

c语言不具备自动内存回收功能,Redis在自己的对象系统中构建了引用计数技术实现内存回收机制。

每个对象的引用计数信息由redisObject的refcount属性记录:

typedef struct redisObject {
    // ...
    int refcount;// 引用计数
    // ...
} robj;
  1. 创建新对象,引用计数值初始化为1
  2. 对象被新程序使用,引用计数值加1
  3. 对象不再被一个程序使用,引用计数减1
  4. 对象的引用计数值变为0,释放对象占用的内存

9、对象共享

由于存在引用计数计数,意味着对于不同的redisObject是可以通过指针共享的。

假设键A创建了一个整数值为100的字符串对象,如果键B也需要创建一个整数值为100的字符串对象。此时,可以通过将键B引用的值对象指向已经存在的整数值为100的字符串对象,并将引用计数+1,达到节省内存的目的。

目前来说,Redis会在初始化服务的时候创建整数值为0~9999的一万个字符串对象。

可以通过OBJECT REFCOUNT命令查看一个键对象对应的值对象的引用计数。

127.0.0.1:6379> keys *
(empty list or set)
127.0.0.1:6379> set num 100
OK
127.0.0.1:6379> object refcount num
(integer) 2

对象共享意味着需要验证已有的对象和需要创建的对象是否完全相同,越复杂的对象需要消耗更多的CPU时间。

只包含整数值的对象,只需要O(1)的时间复杂度。

包含字符串值的对象,需要O(N)的时间复杂度。

包含多值对象,需要O(N ^ 2)的时间复杂度。

10 、对象空转时长

通过lru记录对象最后一次被命令程序访问的时间。

typedef struct redisObject {
    // ...
    unsigned lru;// 空转时长
    // ...
} robj;

可以通过OBJECT IDLETIME命令查看键值对的空转时长,空转时长是通过将当前时间减去键的值对象lru时间计算得出的。

127.0.0.1:6379> set name ccran
OK
127.0.0.1:6379> object idletime name
(integer) 15
127.0.0.1:6379> object idletime name
(integer) 16
127.0.0.1:6379> get name
"ccran"
127.0.0.1:6379> object idletime name
(integer) 1

OBJECT IDLETIME命令不会导致值对象的lru更新

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


标题:Redis设计与实现(5)对象
作者:ccran
地址:https://ccran.online/articles/2020/07/27/1595847531388.html