前言
在上一篇关于redis的文章中，我们分析了redis用到的主要的数据结构，但是redis并没有直接使用这些数据结构来实现KV形式的数据库，而是基于这些数据结构又封装了一些对象。常用的基础对象包括字符串、列表、哈希、集合和有序集合5种，而每种对象底层的实现就是上一篇提到的数据结构中的一种或多种。参考《redis设计与实现》，redis这么设计有以下几点的好处：
- redis执行命令前可以根据对象的具体类型来判断是否可以执行，比如hset作用于字符串对象就会出错；
- 同一个对象底层可以有多种数据结构实现，可以针对不同的场景做动态替换，优化效率；
- redis的对象系统实现了引用计数方式的内存回收机制，对象不再使用时占用的内存会自动释放；
- redis的对象系统实现了基于引用计数的对象共享机制，某些情况下，多个数据库键可以共享同一个对象；
- redis对象带有访问记录信息，可以计算空转时长，方便内存淘汰。
对象类型和编码
redis中的每个对象都由redisObject结构表示：
typedef struct redisObject {
// 类型
unsigned type:4;
// 编码
unsigned encoding:4;
// 对象最后一次被访问的时间
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
// 引用计数
int refcount;
// 指向实际值的指针
void *ptr;
} robj;
type代表对象的类型，取值可以是以下几种，redis支持使用TYPE命令来查看数据库键对应的值对象的类型
| 对象 | 对象 type 属性的值 |
TYPE 命令的输出 |
|---|---|---|
| 字符串对象 | REDIS_STRING |
"string" |
| 列表对象 | REDIS_LIST |
"list" |
| 哈希对象 | REDIS_HASH |
"hash" |
| 集合对象 | REDIS_SET |
"set" |
| 有序集合对象 | REDIS_ZSET |
"zset" |
encoding属性记录了对象使用的编码，其实就是底层用了哪个数据结构，可以使用OBJECT ENCODING 命令来查看数据库键的值对象的编码。
| 类型 | 编码 | 对象 | OBJECT 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 |
使用压缩列表实现的有序集合对象。 | "ziplist" |
REDIS_ZSET |
REDIS_ENCODING_SKIPLIST |
使用跳跃表和字典实现的有序集合对象。 | "skiplist" |
字符串对象
从上一个表格中可以看到，redis中字符串的表示可以是int、embstr后者raw。具体以哪种方式存储是需要根据不同的条件来决定的。
| 值 | 编码 |
|---|---|
可以用 long 类型保存的整数。 |
int |
可以用 long double 类型保存的浮点数。 |
embstr 或者 raw
|
字符串值， 或者因为长度太大而没办法用 long 类型表示的整数， 又或者因为长度太大而没办法用 long double 类型表示的浮点数。 |
embstr 或者 raw
|
- long类型的整数用int类型
- 字符串小于等于32字节用embstr类型
- 字符串大于32字节用raw类型
- Long转为字符串的时候会从int转为raw类型(如对int类型做APPEND操作)
- embstr类型是只读的，如果对字符串变更，会转为raw类型(如APPEND操作)
附一个《redis设计与实现》中的字符串命令实现的表格：
| 命令 |
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 | 拷贝对象所保存的整数值， 将这个拷贝转换成字符串值， 然后取出并返回字符串指定索引上的字符。 | 直接取出并返回字符串指定索引上的字符。 | 直接取出并返回字符串指定索引上的字符。 |
列表对象
列表对象的编码可以是压缩列表或者双端链表，也就是ziplist或者linkedlist。压缩列表的存储结构可以参见上一篇介绍redis数据结构的文章，而双端链表底层每个节点都保存了一个字符串对象，字符串对象也是唯一一种会被其他对象嵌套引用的对象。
当列表对象可以同时满足以下两个条件时，列表对象使用 ziplist 编码，具体的长度和数量的限制值也可以通过配置文件进行配置：
- 列表对象保存的所有字符串元素的长度都小于 64 字节；
- 列表对象保存的元素数量小于 512 个；
同样附上列表命令的实现表格：
| 命令 |
ziplist 编码的实现方法 |
linkedlist 编码的实现方法 |
|---|---|---|
| LPUSH | 调用 ziplistPush 函数， 将新元素推入到压缩列表的表头。 |
调用 listAddNodeHead 函数， 将新元素推入到双端链表的表头。 |
| RPUSH | 调用 ziplistPush 函数， 将新元素推入到压缩列表的表尾。 |
调用 listAddNodeTail 函数， 将新元素推入到双端链表的表尾。 |
| LPOP | 调用 ziplistIndex 函数定位压缩列表的表头节点， 在向用户返回节点所保存的元素之后， 调用 ziplistDelete 函数删除表头节点。 |
调用 listFirst 函数定位双端链表的表头节点， 在向用户返回节点所保存的元素之后， 调用 listDelNode 函数删除表头节点。 |
| RPOP | 调用 ziplistIndex 函数定位压缩列表的表尾节点， 在向用户返回节点所保存的元素之后， 调用 ziplistDelete 函数删除表尾节点。 |
调用 listLast 函数定位双端链表的表尾节点， 在向用户返回节点所保存的元素之后， 调用 listDelNode 函数删除表尾节点。 |
| LINDEX | 调用 ziplistIndex 函数定位压缩列表中的指定节点， 然后返回节点所保存的元素。 |
调用 listIndex 函数定位双端链表中的指定节点， 然后返回节点所保存的元素。 |
| LLEN | 调用 ziplistLen 函数返回压缩列表的长度。 |
调用 listLength 函数返回双端链表的长度。 |
| LINSERT | 插入新节点到压缩列表的表头或者表尾时， 使用 ziplistPush 函数； 插入新节点到压缩列表的其他位置时， 使用 ziplistInsert 函数。 |
调用 listInsertNode 函数， 将新节点插入到双端链表的指定位置。 |
| LREM | 遍历压缩列表节点， 并调用 ziplistDelete 函数删除包含了给定元素的节点。 |
遍历双端链表节点， 并调用 listDelNode 函数删除包含了给定元素的节点。 |
| LTRIM | 调用 ziplistDeleteRange 函数， 删除压缩列表中所有不在指定索引范围内的节点。 |
遍历双端链表节点， 并调用 listDelNode 函数删除链表中所有不在指定索引范围内的节点。 |
| LSET | 调用 ziplistDelete 函数， 先删除压缩列表指定索引上的现有节点， 然后调用 ziplistInsert 函数， 将一个包含给定元素的新节点插入到相同索引上面。 |
调用 listIndex 函数， 定位到双端链表指定索引上的节点， 然后通过赋值操作更新节点的值。 |
哈希对象
哈希对象的编码可以是ziplist或者hashtable。
- 对于使用压缩列表来实现的哈希对象，每次增加新的键值对会先将代表键的压缩列表节点添加到表尾，然后再将代表值的压缩列表节点添加到表尾，所以键值总是连在一起。
- 对于使用字典实现的哈希对象，不管键和值都是一个字符串对象。
当哈希对象可以同时满足以下两个条件时， 哈希对象使用 ziplist 编码，同样，两个限制值是可以通过配置文件进行修改的：
- 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；
- 哈希对象保存的键值对数量小于 512 个；
附上哈希命令的实现表格：
| 命令 |
ziplist 编码实现方法 |
hashtable 编码的实现方法 |
|---|---|---|
| HSET | 首先调用 ziplistPush 函数， 将键推入到压缩列表的表尾， 然后再次调用 ziplistPush 函数， 将值推入到压缩列表的表尾。 |
调用 dictAdd 函数， 将新节点添加到字典里面。 |
| HGET | 首先调用 ziplistFind 函数， 在压缩列表中查找指定键所对应的节点， 然后调用 ziplistNext 函数， 将指针移动到键节点旁边的值节点， 最后返回值节点。 |
调用 dictFind 函数， 在字典中查找给定键， 然后调用 dictGetVal 函数， 返回该键所对应的值。 |
| HEXISTS | 调用 ziplistFind 函数， 在压缩列表中查找指定键所对应的节点， 如果找到的话说明键值对存在， 没找到的话就说明键值对不存在。 |
调用 dictFind 函数， 在字典中查找给定键， 如果找到的话说明键值对存在， 没找到的话就说明键值对不存在。 |
| HDEL | 调用 ziplistFind 函数， 在压缩列表中查找指定键所对应的节点， 然后将相应的键节点、 以及键节点旁边的值节点都删除掉。 |
调用 dictDelete 函数， 将指定键所对应的键值对从字典中删除掉。 |
| HLEN | 调用 ziplistLen 函数， 取得压缩列表包含节点的总数量， 将这个数量除以 2 ， 得出的结果就是压缩列表保存的键值对的数量。 |
调用 dictSize 函数， 返回字典包含的键值对数量， 这个数量就是哈希对象包含的键值对数量。 |
| HGETALL | 遍历整个压缩列表， 用 ziplistGet 函数返回所有键和值（都是节点）。 |
遍历整个字典， 用 dictGetKey 函数返回字典的键， 用 dictGetVal 函数返回字典的值。 |
集合对象
集合对象的编码可以是intset或者hashtable，也就是整数集合或者字典。intset实现的集合所有元素都是整数，而hashtable实现的集合元素则每个键都是字符串对象，每个值都是NULL，类似于Java中HashSet的实现。
当集合对象可以同时满足以下两个条件时，对象使用 intset 编码，数量上限同样可配置：
- 集合对象保存的所有元素都是整数值；
- 集合对象保存的元素数量不超过 512 个；
集合命令的实现表格：
| 命令 |
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 函数， 从字典中删除所有键为给定元素的键值对。 |
有序集合对象
有序集合的编码可以是 ziplist 或者 skiplist，即跳跃表或者压缩列表。跟哈希对象使用压缩列表实现类似，每个有序集合元素使用相连的两个压缩列表节点分别表示成员和分值，分值按从小到大的顺序排序。
而使用跳跃表实现的有序集合底层使用了zset结构，zset包含了一个跳跃表和一个字典：
typedef struct zset {
zskiplist *zsl;
dict *dict;
} zset;
zset 结构中的 zsl 跳跃表按分值从小到大保存了所有集合元素， 每个跳跃表节点都保存了一个集合元素： 跳跃表节点的 object 属性保存了元素的成员， 而跳跃表节点的 score 属性则保存了元素的分值。
zset 结构中的 dict 字典为有序集合创建了一个从成员到分值的映射， 字典中的每个键值对都保存了一个集合元素： 字典的键保存了元素的成员， 而字典的值则保存了元素的分值。
同时使用两个数据结构综合了两种结构的优点，通过跳跃表能够方便的执行范围查询，而通过字典能够方便的进行元素分数查询。
有序集合每个元素的成员都是一个字符串对象， 而每个元素的分值都是一个 double 类型的浮点数。跳跃表和字典底层通过指针会共享这些对象，所以不会浪费额外的内存。
当有序集合对象可以同时满足以下两个条件时，对象使用 ziplist 编码，可通过配置文件设置限制值：
- 有序集合保存的元素数量小于 128 个；
- 有序集合保存的所有元素成员的长度都小于 64 字节；
有序集合命令的实现集合：
| 命令 |
ziplist 编码的实现方法 |
zset 编码的实现方法 |
|---|---|---|
| ZADD | 调用 ziplistInsert 函数， 将成员和分值作为两个节点分别插入到压缩列表。 |
先调用 zslInsert 函数， 将新元素添加到跳跃表， 然后调用 dictAdd 函数， 将新元素关联到字典。 |
| ZCARD | 调用 ziplistLen 函数， 获得压缩列表包含节点的数量， 将这个数量除以 2 得出集合元素的数量。 |
访问跳跃表数据结构的 length 属性， 直接返回集合元素的数量。 |
| ZCOUNT | 遍历压缩列表， 统计分值在给定范围内的节点的数量。 | 遍历跳跃表， 统计分值在给定范围内的节点的数量。 |
| ZRANGE | 从表头向表尾遍历压缩列表， 返回给定索引范围内的所有元素。 | 从表头向表尾遍历跳跃表， 返回给定索引范围内的所有元素。 |
| ZREVRANGE | 从表尾向表头遍历压缩列表， 返回给定索引范围内的所有元素。 | 从表尾向表头遍历跳跃表， 返回给定索引范围内的所有元素。 |
| ZRANK | 从表头向表尾遍历压缩列表， 查找给定的成员， 沿途记录经过节点的数量， 当找到给定成员之后， 途经节点的数量就是该成员所对应元素的排名。 | 从表头向表尾遍历跳跃表， 查找给定的成员， 沿途记录经过节点的数量， 当找到给定成员之后， 途经节点的数量就是该成员所对应元素的排名。 |
| ZREVRANK | 从表尾向表头遍历压缩列表， 查找给定的成员， 沿途记录经过节点的数量， 当找到给定成员之后， 途经节点的数量就是该成员所对应元素的排名。 | 从表尾向表头遍历跳跃表， 查找给定的成员， 沿途记录经过节点的数量， 当找到给定成员之后， 途经节点的数量就是该成员所对应元素的排名。 |
| ZREM | 遍历压缩列表， 删除所有包含给定成员的节点， 以及被删除成员节点旁边的分值节点。 | 遍历跳跃表， 删除所有包含了给定成员的跳跃表节点。 并在字典中解除被删除元素的成员和分值的关联。 |
| ZSCORE | 遍历压缩列表， 查找包含了给定成员的节点， 然后取出成员节点旁边的分值节点保存的元素分值。 | 直接从字典中取出给定成员的分值。 |
类型检查和命令多态
redis中的命令分为两种：对所有类型的键都可以执行以及只能对特定的键执行，而只能对特性键执行的命令需要进行键的类型检查。
回顾一下redisObject机构，其中有个属性是type，redis在执行类型特定命令前就是通过这个type属性来判断能够继续执行的。
对于某种redis对象来说，底层会有多种实现，比如列表对象就可以有压缩列表和双端链表两种实现，而对于同一个命令，不同的实现应该都能够响应，针对不同的数据结构来做不同的处理，这就是命令的多态。
内存回收
C语言不像Java拥有虚拟机和垃圾回收器，所以redis自己实现了一个基于引用计数的内存回收机制。每个redisObject里都有一个refcount的属性，这个属性值会随着对象的使用状态不同而不断变化：
- 在创建一个新对象时， 引用计数的值会被初始化为 1 ；
- 当对象被一个新程序使用时， 它的引用计数值会被增一；
- 当对象不再被一个程序使用时， 它的引用计数值会被减一；
- 当对象的引用计数值变为 0 时， 对象所占用的内存会被释放。
对象共享
对于不同的键引用了相同的值对象，redis实现了对象共享机制，通过将指针指向相同的对象来实现内存的高效利用。同时refcount属性记录了引用的数量。
默认redis会在初始化服务器的时候就创建一万个字符串对象，包含从0到9999的所有整数值。
redis实现对象共享只针对于整数型的字符串对象，原因如下：
- 如果共享对象是保存整数值的字符串对象， 那么验证操作的复杂度为 O(1) ；
- 如果共享对象是保存字符串值的字符串对象， 那么验证操作的复杂度为 O(N) ；
- 如果共享对象是包含了多个值（或者对象的）对象， 比如列表对象或者哈希对象， 那么验证操作的复杂度将会是 O(N^2) 。
因此， 尽管共享更复杂的对象可以节约更多的内存， 但受到 CPU 时间的限制， Redis 只对包含整数值的字符串对象进行共享。
对象的空转时长
对象的空转时长可以通过redisObject中的lru属性实现，OBJECT IDLETIME 命令可以通过将当前时间减去lru的值来计算对象的空转时长。并且使用 OBJECT IDLETIME 命令并不会更新对象的lru的值。
对象的lru还被用于实现redis的特定内存淘汰策略，这里就不详述了。
网友评论