redis数据结构上层--对象系统

    redis没有直接使用数据结构来实现键值对的数据库，而是基于这些数据结构创建了一个对象系统，包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象五种类型。

    对redis数据库键值对来说，键永远都是字符串对象，而值可以 是字符串对象、列表对象、哈希对象、集合对象和有序集合对象五种类型，故接下来所说的几种对象，都是键值对的值对象。

type: 对象类型，五种类型之一。

encoding：对象所使用的编码，也即对象使用了什么数据结构作为底层实现。

每种类型的对象都至少使用了两种不同编码（数据结构）。

字符串对象：

        整数值、embstr、简单动态字符串

列表对象：

        压缩列表、双端列表

哈希对象：

        压缩列表、字典实现

集合对象：

        整数集合、字典实现

有序集合对象：

        压缩列表实现、跳跃表和字典实现

一 字符串对象

    字符串对象保存的是整数值，且可以用long表示，值会保存在pre属性里，并将字符串对象的编码设置为int。

    字符串对象是唯一一种会被其他四种对象嵌套的对象。

    字符串对象保存的是字符串值，且值的长度大于32字节，则以SDS来保存这个字符串值，并将对象编码设置为raw。

     字符串对象保存的是字符串值，且值的长度小于等于32字节，则以SDS来保存这个字符串值，并将对象编码设置为embstr。

    raw和embstr的区别在于，raw会调用两次内存分配来分别创建redisObject结构和sdshdr结构，而embstr则只调用一次内存分配函数来分配一块连续的空间。同理，释放对象内存的时候，raw需要调用两次，而embstr只需调用一次。

    embstr编码的字符串对象在执行命令时，效果和raw编码字符串对象效果一样。

    embstr编码字符串对象只读，一旦修改，则会变为raw编码字符串。

二 列表对象

列表对象的编码是ziplist或linkedlist。

ziplist编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点保存了一个列表元素。

linkedlist编码的列表对象使用双端链表作为底层实现，每个双端链表节点都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素。

为了简化字符串对象表示，实际StringObject的结构如下图：

StringObject

列表对象在压缩列表和双端链表间的转换：

1,列表对象保存的所有字符串元素的长度都小于64字节。

2，列表对象保存的元素数量小于512个。

满足上述两个条件，列表对象使用ziplist编码，否则使用linkedlist编码。

注：以上两个条件的上限可配置修改，list-max-ziplist-value 和 list-max-ziplist-entries 。

三 哈希对象

哈希对象的编码可以是ziplist 或 hashtable 。

ziplist编码的哈希对象使用压缩列表作为底层实现，有新键值对（指值是键值对形式）进入时，先把保存了键的压缩列表节点放到压缩列表表尾，然后再把保存了值的压缩列表节点放到压缩列表表尾，故同一键值对的两个节点总是连在一起。

hashtable编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存。

哈希对象两种编码间的转换：

1，哈希对象所保存的所有键值对的键和值的字符串长度都小于64字节。

2，哈希对象的键值对的数量小于512个。

满足上述两个条件，哈希对象使用ziplist编码，否则使用hashtable编码。

注：以上两个条件的上限可配置修改，hash-max-ziplist-value 和 hash-max-ziplist-entries 。

四 集合对象

集合对象编码可以用intset 或者 hashtable 。

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

hashtable编码的集合对象使用字段作为底层实现，字典的每一个键都是字符串对象，每个字符串对象包含了一个集合元素，而字典的值全部被置为null 。

intset编码 hashtable编码

集合对象两种编码间转换：

1，集合对象保存的所有元素都是整数值 。

2，集合对象保存的元素个数不超过512 。

满足上述条件，则使用intset编码，否则，使用hashtable编码 。

注：以上第二个条件的上限可配置修改， set-max-intset-entries 。

五 有序集合对象

有序集合的编码可以用ziplist 或 skiplist 。

ziplist编码的有序集合对象使用压缩列表作为底层实现，每个集合元素使用 两个紧挨在一起的压缩列表节点保存，第一个节点保存元素成员（member），第二个节点保存元素的分值（score）。

压缩列表内的集合元素按分值从小到大排序，分值小的元素靠近表头，分值大的靠近表尾。

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

zset结构中的zs1跳跃表按分值从小到大保存所有集合元素，每个跳跃表节点都保存了一个集合元素，跳跃表节点的object属性保存了元素成员，而跳跃表节点的score属性则保存了元素的分值。

zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典汇中的每个键值对都保存了一个集合元素，字典的键保存了元素的成员，字典的值保存了元素的分值。

理论上，有序集合可以单独使用字典或跳跃表一种数据结构来实现，但无论单独用哪种，性能上总是比不上同时使用。比如查找指定成员分值，直接使用dict，而查找成员排名，则使用跳跃表。

有序集合ziplist和zset编码间的转换：

1，有序集合保存的元素数量小于128个。

2，有序集合保存的所有元素成员长度小于64字节。

满足上述两个条件，则使用ziplist ，否则，使用zset 。

注：以上两个条件的上限可配置修改，zset-max-ziplist-value 和 zset-max-ziplist-entries 。

五 内存收回

因C语言没有自动内存收回功能，所以redis自己构建了一个引用计数技术实现内存回收机制。

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

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

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

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

六 对象共存

对象引用计数的属性还带有对象共存的作用。

redis中，多个键共享同一个值时，数据库键的值指针指向一个现有的值对象，同时被共享的值对象的引用计数增一。

目前来说，redis初始化服务器时，会创建一万个字符串对象，包含从0-9999所有整数值，所以当用到0-9999的字符串对象时，服务器会共享这些对象，而不会再创建新对象。

七 对象的空转时长

lru：记录了对象最后一次被命令程序访问的时间。

redisObject 完整结构：

参考文献《redis设计与实现第二版》