Redis对象(二) - 对象实现

redis中的五种数据对象都使用了不同的底层编码方式、那相互之间是如何转化的呢 ?

字符串对象

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

若一个字符串对象保存的是整数值, 且这个整数值可以使用long类型来表示、则 字符串对象会将整数值保存在ptr属性 (将 void * 转换成 long), 将字符串的编码设置为 int.

int编码.png

若一个字符串对象保存的是一个字符串值, 且长度＞ 32字节, 那么该字符串对象会使用一个简单动态字符串 SDS 来保存、并将对象的编码设置为 raw

raw编码.png

若字符串值的长度≤32字节, 会使用embstr来保存, 它和raw编码一样、都使用redisObject结构和sdshdr结构来表示字符串对象, 但raw编码会调用两次内存分配来分表创建redisObject结构和sdshdr结构, 而embstr编码则调用一次内存分配分配一块连续的空间, 依次包含redisObject 和 embstr结构

embstr内存块.png

embstr编码的字符串对象在执行命令时、产生的效果与raw编码一致, 但获得的好处是:

1. emstr编码将创建对象时需要的内存分配次数从raw编码的两次降为1次
2. 释放时、也只需要调用一次内存释放函数, raw编码需要两次
3. embstr编码的字符串对象保存在连续空间, 比raw编码更好的利用缓存带来的优势

编码转换

int编码的字符串对象和embstr编码的字符串对象在满足条件的情况下, 会被转换为raw编码的字符串对象, 对于int编码的字符串对象来说、若向对象执行了一些明朗、使对象保存的不再是整数值、编码会从 int -> raw

eg. 通过append命令、向整数值的字符串对象追加一个字符串值, 因为追加操作指南对字符串值执行、所以会转为raw类型编码

因为redis没有为embstr编码的字符串对象编写修改程序(只有int和raw编码的字符串对象才有), 所以embstr编码的对象实际上是只读的, 当执行任何修改时、程序会先将对象的编码从embstr转化成raw, 再执行修改, 所以: embstr编码的对象在执行修改后、总会变成raw编码

字符串命令的实现

字符串命令的实现.png

列表对象

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

ziplist 编码的列表对象使用压缩列表作为底层实现, 每个压缩列表节点保存了一个列表元素, eg. 执行rpush命令

redis> rpush numbers 1 "three" 5
3

若使用的是ziplist编码、则值对象如下所示:

ziplist编码的列表对象.png

另外, linkedlist编码的列表对象使用双端链表作为底层实现, 每个双端链表节点保存一个字符串对象, 而每个字符串对象都保存了一个列表元素, eg. 上边numbers使用linkedlist编码如下:

linkedlist编码的列表对象.png

linkedlist编码的列表对象在底层的双端链表结构中包含了多个字符串对象

注意:

为了简化字符串对象的表示, 使用了 StringObject来标记, 完整表示如下:

完整的字符串对象表示.png

编码转换

列表对象满足下边两个条件时、使用ziplist编码

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

否则: 使用linkedlist编码

注意:

上限值可配置, list-max-ziplist-value 和 list-max-ziplist-entries 选项.

列表命令的实现

列表键的值为列表对象, 用于键操作的所有命令都是针对列表对象来构建的, 下边是部分实现

列表命令实现.png

hash对象

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

ziplist编码的hash对象使用压缩列表作为底层实现, 当有新的键值对要加入到hash对象时, 程序会先将保存了键的压缩列表节点推入表尾, 然后将保存了值的压缩列表节点推入到压缩列表表尾, 所以:

1. 保存了统一键值对的两个节点总是紧挨在一起, 保存键的节点在前、保存值的节点在后
2. 先添加到hash对象中的键值对会被放在压缩列表的表头方向, 后添加到hash对象中的键值对被放到表尾方向

eg. 执行hset命令

redis> hset profile name "test"
(integer) 1
redis> hset profile age 25
(integer) 1
redis> hset profile career "programmer"
(integer) 1

若profile使用的是ziplist编码, 值对象如下所示:

profile对象.png profile对象ziplist底层实现.png

另一方面: hashtable编码的hash对象使用字典作为底层实现, hash对象中的每个键值对都使用一个字典键值对保存,

1. 字典的每个键是一个字符串对象、保存了键值对中的键

2. 字典的每个值都是字符串对象、保存了键值对的值

   
   hash编码的profile对象.png

编码转换

当hash对象可以同时满足下边条件时、使用ziplist编码:

1. hash对象保存的所有键值对的键和值的长度都＜64字节
2. hash对象保存的键值对的数量＜512个

注意:

上限值可以使用hash-max-ziplist-value 和 hash-max-ziplist-entries选项配置

键和值的长度不满足、都会引起编码的转换.

hash命令的实现

因为hash键的值作为hash对象, 用于hash键的所有命令都是针对hash对象来构建的, 部分实现如下:

部分hash命令的实现.png

集合对象

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

intset编码的集合对象使用整数集合作为底层实现, 集合对象包含的所有元素都被保存在整数集合里. eg.

redis> SADD numbers 1 3 5
(integer) 3

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

eg. 以下代码将创建一个如图示的hashtable编码集合对象

redis> sadd fruits "apple" "banana" "cherry"
(integer) 3

intset编码的集合对象.png hashtable编码的集合对象.png

编码的转换

当集合对象满足下边两个条件时、使用intset编码:

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

注意:

第二个条件上限值可修改, set-max-intset-entries 选项, 当intset编码的集合对象任意条件不满足时、会执行对象的编码转换操作, 原本保存在整数集合中的所有元素会被转移并保存到字典里, 编码从intset -> hashtable, eg.

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"

集合命令的实现

集合命令的实现.png

有序集合对象

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

ziplist编码的压缩列表对象使用压缩列表作为底层实现, 每个集合元素使用两个紧挨着的压缩列表节点保存, 第一个节点保存元素的成员, 第二个元素保存元素的分值

压缩列表内的集合元素按照分值从小到大排序, 分值较小的元素放在靠近表头的方向.

eg. 执行 zadd命令、服务器将创建一个有序集合对象作为price键的值

redis> zadd price 8.5 apple 5.0 banana 6.0 cherry 
(integer) 3

若压缩列表的值对象使用的是ziplist编码, 则结构如下:

ziplist编码的有序集合对象.png

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

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

zset元素在zskiplist中按分值排序.png

zset结构中的zsl跳表按照分值从小到大保存了所有集合元素, 每个跳表节点都保存了一个集合元素, 跳表节点的 object属性 保存了元素的成员, 跳表节点的score属性 保存了元素的分值, 通过跳表可以对有序集合进行范围型操作, eg. zrank, zrange 等就是基于跳表实现的

此外, zset 结构中的dict字典为有序集合创建了一个从成员到分值的映射, 字典中的每个键值对都保存了一个集合元素: 字典的键保存了元素的成员, 字典的值保存了元素的分值, 通过字典, 程序可以使用 O(1) 复杂度查找给的成员的分支, zscore 命令就是根据这一特性实现的

有序集合每个元素的成员都是一个字符串对象, 而每个元素的分值都是一个double类型的浮点数, 注意: 虽然zset结构同时使用跳表和字典来保存有序集合元素, 但两者会通过指针共享相同元素的成员和分值, 所以不会产生重复的成员或者分值、也不存在额外的内存浪费

思考:

为什么有序集合需要同时使用跳跃表和字典来实现 ?

理论上, 有序集合可以单独使用字典或者跳表其中一种结构实现, 但无论使用字典还是跳表、都有各自的缺陷. 
eg. 若只使用字典实现, 以O(1)时间复杂度查找成员分值的特性会被保留、但因为字典以无序的方式来保存集合元素, 在执行`zrank`, `zrange` 时、需要对所有元素排序, 至少需要 O(Nlog N)的时间复杂度、及 O(n)的空间复杂度(创建一个数组保存排序后的元素).

若只是有跳表实现, 跳表执行范围查询的操作优点会被保留, 但因为没有字典, 根据成员查找分值的复杂度会从 O(1) 上升到 O(log N), 所以 redis选择了同时使用两种数据结构完成.

若price键创建的有序集合对象使用的是skiplist编码、结构如下:

skiplsit实现的有序集合对象.png 有序集合元素同时保存在dict和skiplist中.png

**注意: **

为展示方便、上图在字典和跳表中重复展示了各个元素的成员和分值、但在实际中、字典和跳跃表会共享元素的成员和分值、不会造成任何内存浪费

编码的转化

有序集合对象同时满足下边条件时、使用ziplist编码

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

注意

条件上限值可配置, zset-max-ziplist-entries 和 zset-max-ziplist-value 选项.

有序集合的命令实现

有序集合键的值为hash对象、用于有序集合键的所有命令都是针对hash键来构建的, 下边是部分实现:

image-有序集合的实现.png