数据结构

　整数集合

当一个集合只包含整数且数量不多时，redis就会使用整数集合作为底层实现。

typedef struct inset{
    //编码方式
    uint32_t encoding;

    //元素数量
    uint32_t length;

    //数组
    int8_t contents[];
}

contents是从小到大的set集合，contents的类型由encoding字段来确定，并不是int8_t。

升级和降级

升级有3步骤

  • 1.根据新元素类行扩展整数集合底层数组空间大小，并分配空间
  • 2.将底层数组现有的所有元素都转换为新元素类型，保持增序
  • 3.将新元素插入

如整数集合encoding从16位转32位，则首先将所有元素扩展为32位，然后移动元素进行插入。升级可以提升整数集合的灵活性同时节约内存。

整数集合不支持降级操作，一旦升级之后就会一直保持升级状态。

压缩列表

压缩列表是列表键和哈希键的底层实现之一。是为了节约内存开发的一种数据结构，组成如下：

[zlbytes,zltail,zllen,entry1,entry2,...,entryN,zlend]

zlbytes记录整个压缩列表占用的内存字节数；zltail记录尾节点距离起始地址有多少字节；zllen记录包含的节点个数；entry是节点；zlend标记节点末端；

压缩列表的每个节点，可以保存一个字节数组或整数值，由三部分构成

[previous_entry_length,encoding,content]

previous_entry_length记录前一个节点的长度，通过这个可以计算前一节点的起始地址。压缩列表的便利就是用这种方式实现的，可以基于这个字段不停的回溯到前面。

encoding记录节点content的数据类型和长度。

content则保存实际的entry值，根据encoding决定content的类型。

连锁更新问题：由于节点的previous_entry_length记录前一个节点的长度，一旦在小于254个字节的节点中插入一个大于254字节的新节点到表头，会诱发后续所有previous_entry_length进行更新，会产生O(N^2)级别的操作，但由于实际情形下，压缩列表长度并非特别长，更新节点不多，并不会影响性能。

对象

redis的所有数据结构，都是用于构造出可用的对象进行使用。内置的对象为字符串、列表、哈希、集合、有序集合五种。

typedef struct redisObject{
    unsigned type:4;//类型

    unsigned encoding:4;//编码
}

type属性记录对象的类型。encoding标识底层实现的数据结构，使用OBJECT ENCODING可以查看。

字符串对象

字符串的encoding可以是int，raw和embstr。embstr是一种短字符串保存的优化编码方式。浮点数在redis中也是以字符串值来保存的。

列表对象

列表的底层是ziplist或者linkedlist。list所有元素小于64字节使用ziplist，如果元素数量大于512个则转为linkedlist。具体的规则是可以修改的。

哈希对象

哈希对象底层是ziplist或hashtable。在ziplist中键值为紧挨的两个node，也是固定规则转hashtable。

集合对象

集合对象底层是intset或者hashtable。如果是字符串集合使用hashtable，如果是整型则为intset。只要集合包含字符串都换转hashtable。

有序集合对象

有序集合底层是ziplist或skiplist。这两个数据结构可能在zset中同时使用，同时使用可以提升性能。一般来说，字典和跳表共享元素值，并不会造成内存浪费。当有序集合元素小于128且所有长度小于64字节使用ziplist，否则使用skiplist。

命令

redis的命令分为两种类型，一种是任何对象（键）都可以执行（del、expire），另一种是特定的对象（键）可以执行（set，get对字符串；hdel，hset对哈希）。

这种实现依赖对redisObject结构的type属性判断，同时还会根据值对象的编码方式（encoding）来选择对应的命令。

内存回收

由于c语言本身不具备内存回收功能，redis在自己的对象系统中构建了一种引用计数实现内存回收。他由redisObject的refcount属性记录

typedef struct redisObject{
    int refcount;//计数
}

对象共享

类似于浅拷贝，多个指针指向一个对象的机制，可以有效的节约内存。但只有包含整数的字符串对象实现共享（带字符串的字符串对象不行）。

空转时长

redisObject有lru属性来判断对象最后一次被访问的时间。用于服务清除内存的算法。