August's Box

Redis设计与实现笔记-章8.对象

前面7章介绍了redis在底层用到的所有数据结构:SDS双端链表字典skiplist整数集合ziplist。redis没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构实现了一个对象系统,包括以下五种类型:字符串对象列表对象哈希对象集合对象有序集合对象。每种对象系统使用了至少一种前面的数据结构。对象系统带给redis的好处主要有以下几个方面:

  • 通过这五种不同类型的对象,redis在执行不同命令的时候可以对对象的类型进行检查,看该命令是否可以执行
  • 在不同的应用场景中,同一类对象可以针对不同的应用场景选择不同的数据结构实现,优化使用效率
  • 对象系统实现了基于引用技术的内存回收机制,对不再使用的对象进行回收。另外,通过引用技术可以实现对象共享机制,在适当的条件下达到对象共享,节约内存
  • 对象带有访问时间记录,可以计算数据库键的空转时长,在服务器启用maxmemory功能时来确定删除优先级

对象的定义

redis使用对象来表示数据库中的键和值,当我们在redis中新建一个键值对时,至少会创建两个对象(例:SET msg "hello world"会创建包含字符串值”msg”的对象和包含字符串值”hello world”的对象)。键总是一个字符串对象,而值可以是五种对象中的任意一个。

redis.h/redisObjectlink
1
2
3
4
5
6
7
typedef struct redisObject {
unsigned type:4;//类型
unsigned encoding:4;//编码
unsigned lru:REDIS_LRU_BITS; // 对象最后一次被访问的时间
int refcount;//引用计数
void *ptr;// 指向实际值的指针
} robj;

类型

对象的type属性记录了对象的类型,类型可以是以下几个常量:

redis.h/redisObjectlink
1
2
3
4
5
6
// 对象类型
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4

在redis中,用TYPE命令对键进行操作时,返回的是值的类型。五种类型返回值分别为:stringlisthashsetzset。例如:
1
2
3
4
5
6
7
8
redis> SET msg "hello world"
OK
redis> TYPE msg
string
redis> RPUSH numbers 1 3 5
(integer) 6
redis> TYPE numbers
list

编码和底层实现

对象的encoding属性记录了对象所使用的编码,不同的编码代表了不同的底层数据结构实现。编码可以是以下几个常量,对应的数据结构如下:

编码常量 对应底层数据结构
REDIS_ENCODING_RAW 0 简单动态字符串SDS
REDIS_ENCODING_INT 1 long类型的整数
REDIS_ENCODING_HT 2 字典
REDIS_ENCODING_ZIPMAP 3 zipmap表示小hash,redis2.6后用ziplist代替
REDIS_ENCODING_LINKEDLIST 4 双端链表
REDIS_ENCODING_ZIPLIST 5 压缩列表
REDIS_ENCODING_INTSET 6 整数集合
REDIS_ENCODING_SKIPLIST 7 跳表
REDIS_ENCODING_EMBSTR 8 embstr编码的简单动态字符串SDS

通过对象的type属性和encoding属性,可以确定该对象是用何种底层数据结构实现的何种对象类型。事实上,每种类型的对象都至少有两种不同的编码,即存在至少两种不同的底层数据结构实现,具体在后面描述。

在redis中,用OBJECT ENCODING命令来查看数据库键的值对象的编码。返回值为:rawinthashtablelinkedlistziplistintsetskiplistembstr。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
redis> SET msg "hello world"
OK
redis> OBJECT ENCODING msg
"embstr"
redis> SET story "long long ago, ..."
OK
redis> OBJECT ENCODING story
"raw"
redis> SADD numbers 1 3 5
(integer) 3
redis> OBJECT ENCODING numbers
"intset"
redis> SADD numbers "seven"
(integer) 1
redis> OBJECT ENCODING numbers
"hashtable"

使用不同的底层数据结构来实现不同的对象,在元素较少时可以节约内存,连续的存储可以快速载入等。至于具体在哪种场景下使用哪种编码、什么时候切换、相同命令在不同编码下的实现等,按不同对象来进行分析。

字符串对象

字符串对象的编码可以是intrawembstr

  • 当一个字符串对象保存的是整数值,且这个整数值可以用long类型来表示时,会将编码设置成int,ptr指向该整数,不在LONG_MIN~LONG_MAX范围的转string用SDS保存(sdsfromlonglong)。另外,在0~10000(REDIS_SHARED_INTEGERS)范围内的用共享整数对象
  • 当保存对象是一个字符串,且字符串长度大于39字节(REDIS_ENCODING_EMBSTR_SIZE_LIMIT)时,使用SDS来保存这个字符串,编码设置为raw
  • 当保存对象是一个字符串,且字符串长度不大于39字节时,使用embstr编码方式来保存。这种编码方式和raw一样,也是用SDS来保存,不同的是,在分配对象内存和sdshdr内存的时候是一次分配连续的空间(createEmbeddedStringObject),依次包含redisObjectsdshdr。好处是分配和销毁都只需要一次内存操作,缓存时也更有优势
  • 可以用long double类型表示的浮点数也是作为字符串来保存的,编码为rawembstrcreateStringObjectFromLongDouble)。在某些针对浮点数的运算操作时,会先把保存的字符串转成浮点数运算,运算完再转成字符串保存

编码的转换

int编码的字符串对象执行某些命令时,当修改后保存的不再是整数值时会转换成raw编码;redis中对于embstr编码的字符串对象不能进行修改,只读状态,执行修改命令时总会转成raw编码的字符串对象。

字符串命令的实现

针对字符串对象的命令可参见redis commands,下表给出了各个命令在不同编码下的实现(t_string.c):

命令 int编码 embstr编码 raw编码
SET/SETNX/SETEX/PSETEX 根据值选择相应编码
GET 拷贝对象的整数值,转成字符串(ll2string)返回 直接返回 直接返回
GETSET SET+GET
SETRANGE raw处理 raw处理 设置字符串特定索引上的值,长度不够时扩展(sdsgrowzero
GETRANGE 拷贝对象的整数值,转成字符串(ll2string)返回指定索引上的值 返回指定索引上的值
MGET 遍历key,其他和GET类似
MSET/MSETNX/MSETEX 遍历key/value,其他和SET类似
INCR/INCRBY/DECR/DECRBY 调用incrDecrCommand,参数不同,整型或可以转整型时(getLongLongFromObjectOrReply)work,计算完按结果set
INCRBYFLOAT 整型转或字符串可以转long double时(getLongDoubleFromObjectOrReply)work,计算完按结果set(embstrraw
APPEND raw处理 raw处理 调用sdscatlen追加字符串到末尾
STRLEN 转字符串,返回字符串长度 直接返回长度 直接返回长度

列表对象

列表对象的编码可以是ziplistlinkedlist,不同的编码ptr指针指向不同的对象。其中,在linkedlist编码的列表对象里,listNode的value指针实际上是指向一个字符串对象(并非SDS的直接地址,后面几种对象嵌套字符串对象相同),字符串对象里保存的是列表节点的值。

编码转换

当列表满足以下两个条件时,使用ziplist编码,否则会转换成linkedlist编码(listTypeTryConversion):

  • 保存的所有字符串元素的长度小于64字节(list_max_ziplist_value
  • 保存元素数量小于512个(list_max_ziplist_entries

列表命令的实现

针对列表对象的命令可参见redis commands,下表给出了各个命令在不同编码下的实现(t_list.c):

命令 ziplist编码 linkedlist编码
LPUSH/RPUSH/LPUSHX/RPUSHX 调用ziplistPush,pos头节点或尾节点 调用listAddNodeHeadlistAddNodeTail
LPOP/RPOP ziplistIndex定位头或尾,为弹出元素创建对象,调用ziplistDelete删除 获取头节点或尾节点对象,调用listDelNode从链表删除
LLEN 调用ziplistLen 调用listLength
LINDEX 调用ziplistIndex 调用listIndex
LINSERT 实现了列表的迭代器listTypeInitIterator,通过迭代器先查找插入位置,调用ziplistInsert 先通过迭代器查找插入位置,调用listInsertNode
LRANGE 调用ziplistGetziplistNext遍历 遍历next
LREM 通过迭代器遍历listTypeNext,比较listTypeEqual和删除listTypeDeleteziplistDelete 同(listDelNode
LSET 查找ziplistIndex,删除ziplistDelete,插入ziplistInsert 查找listIndex,删除旧对象,指向新对象
LTRIM 调用ziplistDeleteRange两次,删除左端元素和右端元素 遍历两次调用listDelNode

哈希对象

哈希对象的编码可以是ziplisthashtable。用ziplist保存哈希对象时,会将包含键的节点和值的节点依次加入表尾,所以哈希的键值对总是紧挨在一起存在压缩列表中。用字典保存哈希对象时,键值对的键和值都是以对象的形式保存在dictEntry中。

编码转换

当哈希对象满足以下两个条件时,使用ziplist编码,否则会转换成hashtable编码(hashTypeTryConversion):

  • 保存的所有键值对的长度小于64字节(hash_max_ziplist_value
  • 保存键值对数量小于512个(hash_max_ziplist_entries

哈希命令的实现

针对哈希对象的命令可参见redis commands,下表给出了各个命令在不同编码下的实现(t_hash.c):

命令 ziplist编码 hashtable编码
HSET/HMSET 查找ziplistFind,找到的话删除旧值ziplistDelete,插入新值ziplistInsert,找不到的话添加键和值对象到尾部ziplistPush 调用dictReplace替换或者添加
HSETNX HEXISTS + HSET
HGET/HEXISTS/HMGET 调用hashTypeGetFromZiplist,函数内调用ziplistFind查找 调用hashTypeGetFromHashTable,函数内调用dictFind
HGETALL/HKEYS/HVALS 实现了哈希的迭代器hashTypeInitIterator,通过迭代器迭代hashTypeNext获取
HDEL 查找ziplistFind,删除ziplistDelete 调用dictDelete
HLEN 调用ziplistLen 调用dictSize
HINCRBY/HINCRBYFLOAT 查找,转long/long double,计算完set

集合对象

集合对象的编码可以是intsethashtableintset编码使用整数集合作为底层实现,hashtable编码则使用字典作为底层实现,字典的键是一个字符串对象,作为集合的元素,值则全部设置为NULL。

编码转换

当集合对象满足以下两个条件时,使用intset编码,否则会转换成hashtable编码(setTypeConvert):

  • 保存的所有元素都是整数值
  • 保存的元素数量小于512个(set_max_intset_entries

集合命令的实现

针对集合对象的命令可参见redis commands,下表给出了各个命令在不同编码下的实现(t_set.c):

命令 intset编码 hashtable编码
SADD 检查isObjectRepresentableAsLongLong,可以的话调用intsetAdd,不行的话编码转换 调用dictAdd
SREM 调用intsetRemove 调用dictDelete
SCARD 调用intsetLen 调用dictSize
SISMEMBER 调用intsetFind 调用dictFind
SMEMBERS 实现了集合的迭代器setTypeIterator,通过迭代器迭代获取setTypeNext(intsetGet) 同(dictNext
SRANDMEMBER/SPOP 调用intsetRandom 调用dictGetRandomKey
SMOVE SREM + SADD
SDIFF/SDIFFSTORE/SUNION/SUNIONSTORE 调用sunionDiffGenericCommand,通过迭代器访问所有元素,union插入所有到结果集,diff两种算法:1. 遍历set[0]里的元素,比较这个元素是否在其他集合中再添加到结果集 2. 添加set[0]所有元素到结果集,遍历其他集合元素,挨个删除结果集
SINTER/SINTERSTORE 按集合大小排序,遍历最小集合,看元素是否存在其他集合中,都存在加到结果集

有序集合对象

有序集合对象的编码可以是ziplistskiplistziplist编码使用压缩列表作为底层实现,每个集合元素使用两个紧挨在一起的节点保存,第一个是member,第二个是score,元素按照分值从小到大保存。skiplist编码则使用zset结构作为底层实现,zset结构同时包含一个字典和一个跳表。如下:

redis.h/zsetlink
1
2
3
4
5
6
7
8
9
10
11
12
typedef struct zset {
// 字典,键为成员,值为分值
// 用于支持 O(1) 复杂度的按成员取分值操作
dict *dict;
// 跳跃表,按分值排序成员
// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
// 以及范围操作
zskiplist *zsl;
} zset;

zset通过dict可以在O(1)复杂度的情况下获取成员的分值(ZSCORE),通过跳表可以在平均复杂度为 O(log N) 的情况下按分值定位成员(ZRANGEZRANK等)。所有元素并非保存两份在dict和跳表中,而是通过共享元素的成员和分值,不会造成内存浪费。

编码转换

当有序集合对象满足以下两个条件时,使用ziplist编码,否则会转换成skiplist编码(zsetConvert相互转换):

  • 保存的所有元素长度小于64字节(zset_max_ziplist_value)
  • 保存的元素数量小于128个(zset_max_ziplist_entries

有序集合命令的实现

针对有序集合对象的命令可参见redis commands,下表给出了各个命令在不同编码下的实现(t_zset.c):

命令 ziplist编码 skiplist编码
ZADD 集合不存在创建createZsetZiplistObject,查找zzlFind,存在先删除zzlDelete,插入zzlInsert 不存在创建createZsetObject,查找dictFind,存在先删除跳表中元素zslDelete,插入zslInsert,更新字典值(存在更新指针,不存在添加dictAdd
ZREM 查找zzlFind,删除zzlDelete 查找dictFind,删除zslDelete+dictDelete
ZCARD 调用zzlLengthziplistLen/2) 返回skiplist的length属性
ZCOUNT 调用zzlFirstInRange获取范围内第一个元素,往后遍历zzlNext,超过范围跳出 调用zslFirstInRange获取范围内第一个元素和最后一个元素,zslGetRank获取首尾rank相减+1
ZRANK/ZREVRANK 从前往后遍历zzlNext,比较直到相同ziplistCompare(刚开始对这个函数理解有误,还以为是个bug) 从字典获取score,调用zslGetRank得到rank
ZSCORE 调用zzlFind 调用dictFind
ZRANGE/ZREVRANGE 调用ziplistIndex定位到start位置元素,根据方向遍历zzlPrevzzlNext 调用zslGetElementByRank定位到start位置元素,根据方向遍历(backward/forward)
ZLEXCOUNT 调用zslParseLexRangeparse range,调用zzlFirstInLexRange定位到开始位置,迭代zzlNext和判断zzlLexValueLteMax是否超出 调用zslParseLexRangeparse range,调用zslFirstInLexRange定位到开始位置,zslLastInLexRange定位到结束位置,调用zslGetRank获取两位置rank,相减
ZRANGEBYLEX/ZREVRANGEBYLEX ZLEXCOUNT类似 调用zslParseLexRangeparse range,调用zslFirstInLexRange定位到开始位置,根据方向遍历和判断(zslLexValueGteMin/zslLexValueLteMax)
ZRANGEBYSCORE/ZREVRANGEBYSCORE 调用zslParseRangeparse range, 根据迭代方向定位开始位置zzlFirstInRange/zzlLastInRange,迭代zzlPrev/zzlNext和判断zslValueGteMin/zslValueLteMax 调用zslParseRangeparse range, 根据迭代方向定位开始位置zslFirstInRange/zslLastInRange,迭代和判断zslValueGteMin/zslValueLteMax
ZREMRANGEBYLEX/ZREMRANGEBYRANK/ZREMRANGEBYSCORE parse range,删除zzlDeleteRangeByRank/zzlDeleteRangeByScore/zzlDeleteRangeByLex parse range,删除zslDeleteRangeByRank/zslDeleteRangeByScore/zslDeleteRangeByLex
ZUNIONSTORE/ZINTERSTORE 实现了有序集合的迭代器zuiInitIterator,按集合大小排序,union迭代遍历zuiNext所有集合,插入,保存为skiplist编码;inter迭代遍历zuiNextsrc[0],判断元素是否存在其他集合,计算插入,保存为skiplist编码

类型检查和命令多态

redis用于操作键的命令基本分为两种,一种是通用的对于任何类型的键都适用(DELEXPIRERENAMETYPEOBJECT等);另一种只适用于特定类型的。

类型检查是通过redisObject里的type属性来实现的,在执行一条命令之前,服务器会检查输入的键对象是否符合执行命令的类型checkType,是的话执行,否的话返回类型错误。

命令多态是根据redisObject里的type属性来判断和实现的,在执行命令的时候,根据type属性实现对不同底层编码进行操作。

内存回收

redis通过引用计数来实现内存回收机制,信息保存在redisObjectrefCount属性里。程序在执行过程中可以追踪对象的引用计数信息,在适当的时候释放对象进行内存回收:

  • 创建对象的时候,引用计数会被初始化为1
  • 对象被新程序使用时,引用计数会加1incrRefCount
  • 对象不再被一个程序使用时,引用计数会减1decrRefCount
  • 对象引用计数为0时,对象所占内存会被释放

其中还有一个apiresetRefCount,作用是reset引用计数为0,但不释放对象,通常用于需要重新设置对象的引用计数值

对象共享

通过引用计数还可以对对象进行共享,比如:A -> 100,新建B也指向100,包含100的对象引用计数从1变成2,A和B共享了这个对象。

redis在初始化服务器的时候,会生成0~9999(REDIS_SHARED_INTEGERS)个字符串对象,当服务器需要用到0~9999范围内的对象时(直接使用或其他数据结构嵌套使用),就会使用这些共享对象,而不会新建。通过命令OBJECT REFCOUNT可以查看键的值对象的引用计数。

对象的空转时长

redisObject还有最后一个属性lru,记录了对象最后一次被命令程序访问的时间。通过命令OBJECT IDLETIME可以计算打印出指定键的空转时长。另外,如果服务器打开了maxmemory选项,且服务器用于回收内存的算法是volatile-lruallkeys-lru时,当服务器内存数超过了maxmemory设置的上限值时,会优先释放空转时长较高的那部分键。