本文内容参考《redis设计与实现》一书总结归纳而得。

 

对象

前面我们介绍了简单动态字符串、双端链表、字典、整数集合和压缩列表等数据结构。redis没有裸用这些数据结构来实现redis的数据库，而是封装了一个对象系统，这个对象系统包括字符串对象、列表对象、哈希对象、集合对象和有序集合对象这5种类型的对象。

 

对象系统中的每种对象都被封装为redis的redisObj对象，通过使用这个对象有以下好处：

1.可以针对不同使用场景为对象设置不同的底层数据结构从而优化其在不同场景下的使用效率。

2. redis的对象系统还实现了基于引用计数的内存回收机制，当程序不再使用该对象时其占用的内存会被自动释放。

3. redis通过引用计数实现了对象共享机制，可以让多个key共享同一个对象节约内存。

 

下面我们看看redisObj对象的结构

typedef struct redisObject{
    unsigned type:4;	// 类型
    unsigned encoding:4;	// 编码
    void *ptr;		// 指向底层数据结构（SDS、双向链表、跳跃表等）的指针
    int refcount;	// 引用计数
    unsigned lru:22;	// 该对象最后一次被命令访问的时间
    // ... 其他属性
}

当我们创建一个键值对时，redis会为键和值都创建一个RedisObj对象，以下我们称为键对象和值对象。

 

type的值如下：

 

执行TYPE命令时其实就是获取一个键值对的值对象的type属性。

 

 

encoding属性记录了对象的底层实现结构是什么，如下：

 

每种type可以对应多种encoding：

 

用 object encoding命令可以查看一个值对象的encoding。

 

也就是说，type记录的是对象的类型，而encoding记录的是对象底层结构的类型，一个type对应多个encoding，意味着一个对象可以对应多种底层数据结构，这极大地提升了redis的灵活性。

 

接下来我们介绍每种对象类型的底层类型以及该对象从一种编码转换为另一种编码的所需条件。

 

1. 字符串对象

字符串对象的底层数据结构是整型或者SDS，字符串对象的编码可以是int、raw和embstr。

int：当一个字符串对象保存的是整数。此时对象的底层结构是一个long类型，ptr的实际类型是一个long型指针。

 

raw：当一个字符串对象保存的是字符串而且长度大于32字节。此时对象的底层结构是一个SDS对象。ptr是一个指向SDS对象的指针。

 

embstr：当一个字符串对象保存的是字符串而且长度小于32字节。此时对象的底层结构是一个SDS对象。

但是和raw不同的是，对于raw而言，redis需要调用2次内存分配函数分别为SDS对象和RedisObj对象分配内存，SDS和RedisObj是两块独立的内存空间（不连续的两块内存），彼此不相连，而是通过ptr指针引用。

对于embstr而言，redis只需调用分配1次内存，SDS对象和RedisObj对象紧密相连的放在同这一块内存中。而且ptr指针直接指向SDS中的buf数组的开始地址。

对于3.14这种浮点数而言，redis会先将其转为字符串，在存到SDS中。对于incrbyfloat这种自增命令而言，会把3.14字符串转为浮点数再运算。

 

字符串编码转化

对int类型编码的键追加字符串（append命令）时会转为raw类型。

对embstr编码的键做任意改动都会转为raw类型，这是因为embstr实际上是只读的，对embstr的字符串执行任何修改都会转为raw。

 

 

2. 列表对象

列表对象的底层实现类型是压缩列表或者双向链表，编码可以是ziplist或linkedlist。

 

当满足以下2个条件，列表对象使用ziplist编码（压缩列表为底层结构）；

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

 

不满足以上任意一个条件则以linkedlist编码（双向链表为底层结构）或者从ziplist编码转为linkedlist编码。以上条件可以在redis配置文件中修改。

 

以压缩列表为底层实现结构

上图的1/"three"/5是用entry节点包裹着的，entry节点还有encoding和previous_entry_length属性。

 

rpush是往压缩列表的右侧添加一个元素，复杂度为O(1)。lpush则为O(n)，因为会造成所有元素的右移。

 

以双向链表为底层实现结构

由于链表首位都有指针，因此rpush和lpush都是O(1)。

每个StringObject是一个字符串的redisObj。而且这是一个双向链表，图中化成了单向。

 

 

 

3. 哈希对象

哈希对象的底层实现结构是压缩列表或者字典，编码为ziplist或者hashtable。

哈希对象的编码转换条件和列表相同，当满足以下2个条件，哈希对象使用ziplist编码（压缩列表为底层结构）；

1. hash对象保存的键和值长度都小于64字节
2. 保存的键值对个数小于512

 

不满足以上任意一个条件则以hashtable编码（字典为底层结构）或者从ziplist编码转为hashtable编码。以上条件可以在redis配置文件中修改。

 

 

以压缩列表为底层实现结构

 

和列表不同的是，哈希对象的ziplist中既要保存key也要保存value，而且key和value是作为压缩列表的节点紧密相连的，每次往hash键添加一个键值对时会往压缩列表的尾部插入：

 

 

 

以字典为底层实现结构

dict结构的如下

k0和k1保存到的是stringObject字符串对象而非裸SDS。

 

4. 集合对象

集合对象的底层实现结构是整数集合或者字典，编码为intset或者hashtable。

当满足以下2个条件，哈希对象使用intset编码（整数集合为底层结构）；

1. 集合保存的元素都是整数
2. 保存的元素个数小于等于512

 

不满足以上任意一个条件则以hashtable编码（字典为底层结构）或者从intset编码转为hashtable编码。以上条件可以在redis配置文件中修改。

 

以整数集合为底层实现结构

 

以字典作为底层实现结构

需要注意的是，集合保存的是单个元素而非键值对，所以集合元素会作为字典中dictEntry的key属性，而value属性为null。

 

5. 有序集合对象

有序集合对象的底层实现结构是压缩列表或者跳跃链表+字典，编码为ziplist或者skiplist。

当满足以下2个条件，哈希对象使用ziplist编码（整数集合为底层结构）；

1. 所有元素的长度小于64字节
2. 保存的元素个数小于等于128个

 

以压缩列表为底层实现结构

 

 

需要注意的是由于有序结合保存了成员和分值，所以成员和分值会作为两个压缩列表节点紧密相连，并且每个分值节点在压缩列表中是有序的。

 

以字典+跳跃表作为底层实现结构

该情况下，有序集合的对象的ptr指针指向的是一个zset结构，zset结构体包含一个zskiplist跳跃链表和dict字典。

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

 

 

字典中以成员作为key，以score作为值。

使用跳跃表是为了使元素具有有序性，并且提高根据score分值查找某个成员的效率（O(log n)复杂度）以及根据score范围获取多个成员的效率（O(log n)复杂度，因为它是有序的）。

使用字典是为了提高根据成员查找score分值的效率（O(1)复杂度）。

如果不使用跳跃表会要至少O(nlog n)的时间复杂度来排序和额外的O(n)的内存空间（要创建一个数组来保存排序后的元素）。

 

score的类型是一个double型浮点数，而成员则是一个StringObject字符串对象。

 

zset结构同时使用了跳跃表和字典保存有序集合元素，但是两种数据结构会通过指针共享相同的成员和分支以节省内存。

 

 

 

 

类型检查和命令多态

类型检查：在执行某个命令时，redis会先检查键值对的类型是否正确，如果某个键的类型是字符串对象但是对它调用llen命令就会报类型错误。

命令多态：如果一个键值对类型是列表对象，当这个列表的编码为ziplist和linkedlist的情况下执行llen命令的底层操作会不同，对于ziplist会调用ziplistLen函数返回列表长度，对于linkedList会调用listLength函数返回列表长度。此时我们称llen是多态的。其他命令同理。

 

 

内存回收

redis使用引用计数来实现内存回收机制，在检测到对象的引用计数为0时释放对象回收内存。这个引用计数有redisObj的refcount属性记录。

 

在创建一个新对象时，引用计数的值会被初始化为1；

当对象被一个新程序使用时，它的引用计数值会被增一；

当对象不再被一个程序使用时，它的引用计数值会被减一；

当对象的引用计数值变为0时，对象所占用的内存会被释放。

 

 

对象共享

当多个对象引用某个值对象时，该值对象的refcount引用计数会增加，并且会共享该值对象（但是仅限整数）。

例如键A和键B都创建一个整数100，此时有两种做法：分别创建一个100整型的字符串对象，或者只创建一个100整型的字符串对象，并让A和B同时引用该对象。明显后者更节省内存。

 

现实中，redis会初始化服务器时创建0~9999这1万个int编码的字符串对象（此时这些键的引用计数为1），当服务器的键需要用到0~9999时就会让键共享这些对象而无需新建。

如下：

 

引用100这个字符串对象的分别是服务器程序和键A。像其他复合类型对象都可以共享这些整数。

引用100这个字符串对象的分别是服务器程序和键A。像其他复合类型对象都可以共享这些整数。

 

 

redis的键目前只能共享整数，而不能共享raw和embstr编码的字符串对象，列表对象，哈希对象等复合类型对象。

原因是要将一个共享变量设为键的值对象时，程序需要比对共享对象和创建的目标对象是否完全相同，只有完全相同才可以将共享对象设为键的值对象。对于整数而言我们很好预测客户端只能设置0~9999这些整数，但是对于哈希对象、集合、raw字符串对象等我们完全无法预测客户端会设置为什么值。而且校验共享对象和目标对象是否相同所需的复杂度也高，如果共享对象是int型字符串则验证操作为O(1)，raw和embstr字符串则验证操作为O(n)，如果是包含了多个字符串对象的对象如列表和哈希对象，那么验证操作的复杂度为O(n^2)。

 

因此共享更复杂的对象可以节省更多内存，但是会消耗更多CPU资源用于比对共享对象和目标对象。

 

 

 

对象的空转时长

对象的空转时长指的是某个对象有多久没有被访问过。用当前时间减去值对象的lru属性（该属性记录了对象最后一次被命令访问的时间）可以得出空转时长（执行 object idletime命令可得）。

 

每次执行增改查的命令都会更新对象的lru属性。除了获取对象的空转时间外，lru属性还可以用于redis的内存回收策略，如果选择服务器回收内存的算法为volatile-lru或者allkeys-lru，那么当redis占用的内存超过了配置文件中maxmemory选项时空转时长高的键会被优先释放。