Redis设计与实现-对象系统

发表于 | 分类于
本文简单介绍redis五种不同类型的对象，及其对象系统介绍，总结优点和缺点，帮助大家理解和记忆。本书主要为这本书的读书笔记，有问题的地方欢迎指正

redis没有直接使用底层数据结构，如SDS,双向链表，字典，压缩列表，整数集合等等来实现键值数据库，而是基于这些数据结构创建了一个对象系统。

使用对象的好处是，可以针对不同的使用场景，为对象设置多种不同的数据结构，从而优化对象在不同场景下的使用效率。

对象定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct struct redisObject {

    //类型
    unsigned type:4;
    
    //编码
    unsigned encoding:4;
    
    //指向底层实现数据结构的指针
    void *ptr;
    
    //内存引用计数，初创建为1，使用＋1，不再使用－1，当为0时，则内存释放
    int refcount;
    
    //对象最后一次被访问的时间，用于回收算法，计算时间 
    unsigned lru:22;
}
  1. 类型。包括了字符串对象，列表对象，哈希对象，集合对象，有序集合对象
  2. 编码。表明了对象的底层实现数据结构，包括了long类型的整数，embstr编码的简单动态字符串，简单动态字符串，字典，双端列表，压缩列表，整数集合，跳跃表和字典

每种类型的对象都至少使用到了两种不同的编码。

接下来会介绍五种对象不同情况下所使用的编码方式，以及从一种编码转化为另一种编码所需要的条件。

字符串对象

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

知识要点：

  1. 一个字符串值的长度小于39字节，则使用embstr编码，否则使用raw编码
  2. embstr: 分配一次内存，内存是一块连续的空间，回收一次内存
  3. raw：分配两次内存，回收两次内存，内存块不一定连续
  4. long double类型的浮点数在存储时是embstr编码，如果进行了某些操作，比如数字运算，则会临时转化为浮点数，操作完成之后重新embstr编码存储
  5. embstr是一个只读对象，没有相关的操作api，一旦发生改变，就会变成一个raw对象

列表对象

列表对象的编码可以是ziplist， 也可以是linkedlist

ziplist编码的列表对象使用压缩列表作为底层实现

linkedlist编码的列表使用双端列表作为底层实现

当列表对象同时满足以下两个条件时，使用ziplist进行编码，否则编码转换为linkedlist：

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

哈希对象

哈希对象的编码可以是ziplist， 也可以是hashtable

ziplist编码的哈希对象，是一个压缩列表，会将每个新添加的键值对，按照键－值－键－值…的顺序推入压缩列表的末尾

当哈希对象同时满足以下两个条件时，使用ziplist进行编码，否则编码转换为hashtable：

  1. 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
  2. 哈希对象保存的键值对数量小于512个

集合对象

集合对象的编码可以是intset， 也可以是hashtable

intset编码的集合对象使用整数集合作为底层实现

hashtable编码的集合对象使用字段作为底层实现，字典的每个键都是一个集合元素，每个值都为null

当集合对象同时满足以下两个条件时，使用intset进行编码，否则编码转换为hashtable：

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

有序集合对象

有序集合对象的编码可以是ziplist， 也可以是skiplist

ziplist编码的有序集合对象，是一个压缩列表，会将每个新添加的集合元素，按照元素成员－分数－元素成员－分数…的顺序推入压缩列表的末尾（注意，按照分值从小到大的顺序排列）

1
2
3
4
5
typedef struct zset {
    
    zskiplist *zsl;
    dict *dict;
} zset

zsl跳跃表按照从小到大保存了所有的集合元素，每个节点的object属性保存元素的成员，score属性保存具体的分值

dict则创建了一个从成员到分值的映射。

注意，虽然zset同时使用跳跃表和字典来保存有序集合元素，但这两种数据结构都会通过指针来共享相同元素的成员和分值，因此不会产生重复的成员或者分值，也不会因此浪费额外的内存。

当有序集合对象同时满足以下两个条件时，使用ziplist进行编码，否则编码转换为skiplist：

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

内存回收

由于C语言不具备自动内存回收功能，redis自己构建了一个引用计数技术实现的内存回收机制。

对象共享

在redis中了节省内存，多个键可以共享一个值对象（注意，必须是值对象，比如100）

让多个键共享同一个值对象， 有两个步骤：

  1. 将数据库键的值指针指向同一个现有的值对象
  2. 将被共享的值对象的引用计数增一

redis在初始化服务器时，创建了0-9999这一万个字符串对象，当需要用到时，直接共享这些对象，而不是新创建。

注意，这些值对象不时只有字符串键可以使用，那些在数据结构中嵌套了字符串对象的复杂对象都可以使用这些共享对象。

为什么只共享值对象呢？

原因：

  1. 在使用共享对象之前，要先检查给定的共享对象和想要创建的对象是否一致，而这个检查的过程复杂度越高，CPU消耗时间也就越高
  2. 如果是值对象，复杂度O(1), 如果是保存字符串的字符串对象，复杂对为O(N), 如果是列表对象和哈希对象，则复杂度是O(N2)

因此，受到CPU限制，redis只对值对象进行共享