redis数据结构实现 对象 - ZhenLinTechnologySalon/- GitHub Wiki
redis数据结构实现--对象
redis基于sds, list ,set ,zskiplist ,intset这些数据结构创建了一个对象系统。 这个对象系统包括字符串对象，列表对象，哈希对象，集合对象和有序集合对象。
7.1 对象的类型与编码
每次在Redis中创建一对键值时，至少创建两个对象。即键对象和值对象。 每个对象由redisObject结构表示
typedef struct redisObjct{
//类型
unsigned type:4;
//编码
unsigned encoding:4;
//指向底层实现数据结构的指针
void *ptr;
//...
}robj;
7.1.1 类型
| 类型常量 | 对象名称 |
|---|---|
| REDIS_STRING | 字符串对象 |
| REDIS_LIST | 列表对象 |
| REDIS_HASH | 哈希对象 |
| REDIS_SET | 集合对象 |
| REDIS_ZSET | 有序集合对象 |
当我们对数据库键指向TYPE命令时，返回的是对应的值对象的类型
7.1.2 编码和底层实现
ptr指针指向对象底层实现的数据结构，这些数据结构由encoding决定
| 编码常量 | 底层数据结构 |
|---|---|
| REDIS_ENCODING_INT | long类型整数 |
| REDIS_ENCODING_EMBSTR | embstr编码的sds |
| REDIS_ENCODING_RAW | sds |
| 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编码的sds实现的字符串对象 |
| REDIS_STRING | REDIS_ENCODING_RAW | 用sds实现的字符串对象 |
| 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 | 用跳跃表实现的有序集合对象 |
通过encoding属性来设定对象编码，使对象在不同场景下设置不同编码，提高灵活性和效率。
7.2 字符串对象
字符串对象的编码可以是int,raw或者embstr
字符串对象是Redis五种对象中唯一可以被嵌套的。
字符串对象的编码转换
- 如果一个字符串对象保存的是整数值，且此值可以用long类型来表示，那么字符串对象会将整数值保存在ptr属性里（ * void转换成long ），将encoding改为int。
- 如果字符串对象保存了一个长度大于32字节的字符串值，底层将用sds来保存；
- 如果保存了一个长度小于32字节的字符串值，字符串对象将用embstr编码来保存；
- 可以用long double类型表示的浮点数在Redis中也是转换成字符串值来保存的，需要时将字符串值转换回浮点数，执行某些操作，然后再转换成字符串值；
- 一个embstr编码的字符串，Redis是没有相应的修改程序，所以embstr编码字符串是只读的，如果有响应的修改操作，需要把embstr转换成raw，所以embstr编码字符串在修改完之后都是一个raw字符串；
7.3 列表对象
列表对象的编码可以是ziplist或者linkedlist
列表对象编码的转换：
当列表对象可以同时满足以下两个条件，列表对象使用ziplist编码：
- 列表对象保存的所有字符串元素长度都小于64字节；
- 列表对象的元素数量小于512个
不满足这两个条件中任意一个的列表对象使用linkedlist编码
以上两个条件的上限值可以在配置文件修改
7.4 哈希对象
哈希对象的编码可以是ziplist或者hashtable
-
ziplist作为底层实现的哈希对象每次在新增键值对时，先将保存了键的列表节点推入到表尾，再将保存了值的列表节点推入到表尾，因此：
- 保存了同一键值对的两个节点总是紧挨在一起，保存了键的节点在前，保存了值的节点在后
- 先添加到哈希对象中的键值对会被放到列表头方向，后来的键值对在表尾方向
-
hashtable编码的哈希对象是由字典作为底层实现，哈希对象的每一个键值对由字典的键值对保存
哈希对象的编码转换
满足两个条件底层用ziplist实现
- 哈希对象保存的所有键值对的字符串元素长度都小于64字节；
- 哈希对象的键值对数量小于512个
不满足这两个条件之一则用hashtable编码
上限值可以在配置文件修改
7.5 集合对象
集合对象的编码可以是intset或者hashtable
用hashtable编码的集合对象底层实现是用字典，字典的每个键都是一个字符串对象，每个字符串包含了一个集合元素，而字典的值全部设为NULL (跟java中set复用hashmap实现类似)
集合对象的编码转换
满足两个条件底层用intset实现
- 集合对象保存的所有元素都是整数值
- 集合对象的元素数量小于512个
不满足这两个条件之一则用hashtable编码
上限值可以在配置文件修改
7.6 有序集合对象
有序集合对象的编码可以是ziplist或者skiplist
压缩列表实现的有序集合对象每个集合元素用紧挨在一起的两个节点来保存，第一个是元素的成员(member)，第二个是分值(score) 压缩列表内集合元素按分值从小到大排序，分值小的在表头，分值大的在表尾。
skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包括一个字典和一个跳表：
typedef struct zset{
zskiplist *zsl;
dict *dict;
}zset;
zset中跳表从小到大保存了集合元素，通过跳表可以对有序集合进行范围操作。 zset中字典也保存了集合元素，通过字典可以O(1)复杂度查找给定成员分值。
跳表和字典使用指针来共享相同元素的成员和分值，所以同时两个数据结构不会造成内存浪费
有序集合对象的编码转换
满足两个条件底层用ziplist实现
- 有序集合对象保存的所有元素长度小于64字节
- 有序集合对象的元素数量小于128个
不满足这两个条件之一则用skiplist编码
上限值可以在配置文件修改
7.7 类型检查与命令多态
redis里的命令分为两种：
- 一种可以对任何类型执行 如del expire rename
- 另一种只能对特定的类型
7.7.1 类型检查的实现
为了确保指定类型的键执行特定的命令，执行前，要确认类型是否正确
类型检查是通过redisObject的type属性实现的
- 在执行特定命令前，检查输入的键的值对象是否类型正确，如果正确，则执行命令
- 否则，服务器拒绝执行命令，向客户端返回错误类型
7.7.2 多态命令的实现
除了根据值对象类型来判断是否能执行命令外，还根据值对象的编码来选择正确的实现代码来执行命令。 因为一种值类型底层实现可能不同，所以执行时需要根据对象编码的不同选择不同的执行方案，我们称之为多态命令。 如此看来，可以对任何类型执行的命令如 del exipre rename 也是多态命令。
7.7.3 内存回收
因为c语言中不具备自动内存回收功能，所以Redis在对象系统中构建了引用计数（reference counting）来实现内存回收机制。 程序通过跟踪对象的引用计数信息，在适当的时候自动释放对象并内存回收
对象的引用计数信息会随着对象的使用状态而不断变化：
- 创建新对象时，引用计数值为1
- 对象被一个程序使用时，引用计数值增一
- 对象不再被一个程序使用时，引用计数减一
- 引用计数为0时，对象占用内存会被释放
7.7.4 对象共享
除了实现引用计数内存回收机制外，引用计数还有对象的共享功能。 如果创建键值对时，数据库已存在相同的值对象，为了节约内存，会出现多个键共享一个值对象的情况。
对象共享步骤：
- 将数据库键的值指针指向一个现有的值对象
- 将被共享的值对象引用计数增一
Redis会在初始化服务器的时候，创建一万个字符串，包含了从0到9999所有整数值，当服务器需要用到0-9999的字符串对象时，就会使用这些共享对象
当然，包含字符串的嵌套对象是不能共享的，一个共享对象保存的值越复杂，共享时验证所需要消耗的CPU时间也就越多，这样就得不偿失了。
7.7.5 对象的空转时长
redisObject还有一个属性：lru，该属性记录此对象最后一次被命令程序访问的时间。
object idletime命令可以打印出对象的空转时长，该时长就是将当前时间减去lru时间得出。 object idletime命令是特殊的，当它在访问对象的时候不会修改lru