• Redis并不会直接使用数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包括字符串对象，列表对象，哈希对象，集合对象，有序集合对象

使用对象的好处

• 这5种不同类型的对象，Redis可以在执行命令之前，根据对象类型来判断对象是否可以执行给定的命令
• 可以针对不同的场景来为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率
• Redis对象系统实现了基于引用计数技术的内存回收机制，这个机制的好处是当程序不使用某个对象的时候，这个对象所占用的内存会被自动释放，另外这个技术还可以实现对象共享机制，让多个数据库键共享同一个对象来节约内存
• Redis对象带有访问时间记录信息，这个信息可以用来计算数据库键的空转时长，服务器启用了maxmemory功能，空转时长较大的会优先被服务器删除

对象类型与编码

• 在Redis中创建键值对，至少创建两个对象，一个键对象，一个值对象

typedef struct redisObject{
  //类型
  unsigned type:4;
  //编码
  unsigned encoding:4;
  //指向底层实现数据结构的指针
  void *ptr;
  //.....
}robj;

类型

• 对象的type属性记录了对象的类型，Redis数据库来说，键总是一个字符串对象，值可以是字符串对象，列表对象，哈希对象，集合对象，有序集合对象
• 当我们说一个数据库键“字符串键”，其实是说这个键的值是字符串对象，说一个数据库键“列表键”，其实说这个键对应的值为列表对象，type命令就是这样的，执行type命令返回的是这个键所对应值的对象类型

SET msg "hello world"
TYPE msg
string

RPUSH number 1 3 5
TYPE number
list

HMSET profile name tom age 23 career programmer
TYPE profile
hash

SADD fruits apple banana cherry
TYPE fruits
set

ZADD price 8.5 apple 5.0 banana 6.0 cherry
TYPE fruits
zset

编码和底层实现

• ptr指针指向底层数据结构实现，使用哪种数据结构是由对象的encoding决定
• 使用OBJECT ENCODING key命令可以查看一个数据库键的值对象的编码

• 每种类型可以使用的编码

• 通过encoding属性来设定对象所使用的编码，而不是为特定类型的对象关联一定的编码，提高了Redis的灵活性和效率，因为Redis可以根据不同的使用场景为一个对象设置不同的编码，从而优化对象在某一个场景下的效率

• 比如，列表对象包含的元素较少的时候，底层使用压缩列表，因为这样更节约内存和更快被加载到缓冲中，当元素越来越多的时候，就使用双端列表了，因为这时候双端列表的功能更强，且压缩列表的优势没有了

字符串对象

• 字符串对象的编码：int，raw，embstr

• 如果一个字符串对象是整数，并且这个整数可以用long类型表示，字符串对象会将整数值保存到字符串对象结构的ptr属性中，将void*转换成long，将字符串编码设置为int
  SET msg 10086
OBJECT ENCODING msg
"int"

• 如果字符串对象保存的是一个字符串值，并且这个字符串的长度大于32字节，那么将用SDS来保存这个值，编码设置为raw

  
  
  raw编码的字符串对象

• 如果字符串对象保存的是一个字符串值，并且这个字符串的长度小于等于32字节，字符串对象将使用embstr编码方式来保存字符串值，embstr编码通过调用一次内存分配函数来分配一块连续的空间，空间一次包含redisObject和sdshdr两个结构

  
  
  embstr编码创建的内存块结构

• 使用embstr的好处：

• embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为1次
• 释放embstr编码的字符串对象只需要调用一次内存释放函数，而释放raw编码的字符串对象，需要调用两次内存是释放函数
• 因为embstr编码的字符串对象的所有数据都保存到一块连续的内存里面，所以这种编码的字符串对象比起raw编码的字符串对象能够更好的利用缓冲带来的优势

• 使用long double类型表示的浮点数在Redis中也是作为字符串值来保存的，如果我们保存浮点数到字符串对象中，那么程序会先将这个浮点数转换为字符串值，然后在保存转换所得的字符串值

编码的转换

• int,embstr类型的字符串对象在条件满足的情况下，被转化成为raw编码类型的字符串对象

SET number 10086
APPEND number " is a good number"
GET number
OBJECT ENCODING number

SET msg "hello world"
APPEND msg " again"
OBJECT ENCODING msg

字符串命令

列表对象

• 列表对象的编码可以是ziplist或者linkedlist

• RPUSH numbers 1 'three' 5

• 假设numbers使用ziplist编码，每个压缩列表节点都保存了一个列表元素

  
  
  ziplist编码的numbers列表对象

• 假设numbers使用linkedlist编码，每个双端链表节点都保存了一个字符串对象，而每一个字符串对象都保存了一个列表元素，字符串对象是5中类型的对象中唯一一种会被其他四种嵌套的对象

  
  
  简化的字符串对象
  
  
  完整的字符串对象表示
  
  
  linkedlist编码的numbers列表对象

编码转换

• 列表使用ziplist必须同时满足下面的两种条件，如果不满足就使用linkedlist编码，这两个条件的上限可以修改，list-max-ziplist-value和list-max-ziplist-entries

• 列表对象保存的所有字符串元素的长度都小于 65字节
• 列表对象保存的元素个数小于512个

• 对于ziplist编码来说，如果所需的两个条件有一个不满足了，那么就会转变为linkedlist编码

列表命令的实现

哈希对象

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

• ziplist编码，每当有新的键值对要加入到哈希对象的时候，程序会先将保存了键的压缩列表节点推入到压缩列表的表尾，然后在将保存了值的压缩列表节点推入到压缩列表的表尾，因此，保存了同一键值对的两个节点总是挨在一起，保存键的在前，值的在后，先添加到哈希对象中的键值对被放在压缩列表表头方向，后来的添加到表尾方向

• HSET profile name "tom"
• HSET profile age 25
• HSET profile career "programmer"

• 假设使用的是ziplist编码

  
  
  ziplist编码的profile哈希对象

• 假设使用hashtable编码的底层实现，每一个键值对都用一个字典键值对来保存

• 字典中每一个键和每一个值都是一个字符串对象

  
  
  hashtable编码实现的profile的哈希对象

编码转换

• 当哈希对象使用ziplist编码，必须满足下面的两个条件，否则使用的是hashtable编码

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

• ziplist编码在不满足任意一个条件的时候会转换为hashtable编码

哈希命令的实现

集合对象

• 集合对象的编码可以是intset或者hashtable

• SADD numbers 1 3 5
• SADD fruits "apple" "banana" "cherry"

• intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面
• hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象包含一个集合对象，而字典的值则全部被设置为NULL

intset编码的numbers集合对象

hashtable编码的fruits集合对象

编码的转化

• intset编码必须满足下面的两个条件，否则使用hashtable编码

• 集合对象保存的所有元素都是整数值
• 集合对象保存的元素数量不超过512个

• 当使用intset编码的集合对象来说，两个条件有一个不满足就会转换为hashtable编码

集合命令的实现

有序集合对象

• 有序集合对象的编码可以是ziplist或者skiplist

• ZADD price 8.5 apple 5.0 banana 6.0 cherry

• 使用ziplist编码的有序集合对象，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存成员，第二个节点保存分值，按分值大小，从小到大排序

  
  
  ziplist编码的有序集合对象

• skiplist编码的有序集合对象使用zset结构作为底层实现

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

• zsl跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存一个集合元素，跳跃表节点的object属性保存了元素的成员，跳跃表的score属性保存了分值，程序可以对有序集合进行范围型的操作，ZRANK,ZRANGE命令就是通过这一特性实现的
• dict字典为有序集合创建了一个从成员到分值的映射，字典中每个键值对都保存了一个集合元素，键保存了元素成员，值保存了分值，查找给定元素的分值O(1),ZSCORE命令就是通过这个特性实现的

• 有序集合的每个元素成员都是一个字符串对象，每个分值都是一个double型的浮点数
• zset结构同时使用跳跃表和字典来保存有序集合，但这两种数据结构通过指针来共享相同元素的成员和分值，不会浪费额为的内存

• 为什么同时使用跳跃表和字典来实现有序集合了？

• 因为单使用字典，那么保存的元素不会排序，而进行排序O(nlogn),以及额为的O(N)内存空间，因为排序后需要有一个地方存放
• 因为单使用跳跃表，那么根据成员查找分值O(logn)

• 所以为了查找和范围型操作尽可能快的执行，所以同时使用了跳跃表和字典

  
  
  skiplist编码的有序集合对象

编码的转化

• 当有序集合对象同时满足下面两个条件，对象使用的是ziplist编码，否则使用的是skiplist编码

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

• 对于ziplist编码的集合对象来说，有一个条件不满足，就会将所有集合元素被转移并保存到zset结构中，对象的编码也变为skiplist

有序集合命令的实现

类型检查和命令多态

Redis的命令分为两类

• 可以对任何类型的键执行的命令，DEL,EXPIRE,RENAME,TYPE,OBJECT等命令
• 只能对特定类型的键执行的命令，
  SET,GET,APPEND,STRLEN只能对字符串键执行
  HDEL,HSET,HGET,HLEN只能对哈希键执行
  RPUSH,LPOP,LINSERT,LLEN只能对列表键执行
  SADD,SPOP,SINTER,SCARD只能对集合键执行
  ZADD,ZCARD,ZRANK,ZSCORE只能对有序集合键执行

• 类型检查实现

在执行一个类型特定的命令之前，Redis会先检查输入键的类型是否正确，然后在决定是否执行这个命令，这个检查是通过redisObject对象的type属性来实现的，下面是对于LLEN命令来说的：

LLEN命令执行时的类型检查错误

• 多态命令的实现

根据值对象的编码方式，选择正确的命令实现代码来执行命令，比如列表对象的编码，有两种，ziplist和linkedlist可用，如果是ziplist编码，使用ziplistLen返回列表的长度，如果是linkedlist，使用listLength返回列表的长度，这个体现了基于编码的多态——一个命令可以同时用于处理多种不同的编码

使用DEL,EXPIRE,TYPE等命令，也是多态命令，无论输入的键是什么类型，这些命令都可以正确的执行，基于类型的多态——一个命令可以同时用于处理多种不同类型的键

LLEN命令执行过程

内存回收

c语言并没有自动内存回收功能，Redis自己的对象系统中构建了通过引用计数技术来实现内存回收机制，引用计数信息通过redisObject对象的refcount属性来实现

typedef struct redisObject{
   //引用计数
  int refcount;
}robj;

对象的引用信息随着对象的使用状态而不断变化

• 创建一个对象的时候，refcount=1
• 当对象被一个新程序使用，refcount加1 ，通过incrRefCount函数实现
• 当对象不再被一个程序使用，refcount减1，通过decrRefCount函数实现，当refcount=0的时候，释放对象
• 当refcount=0的时候，对象占用的内存释放
• resetRefCount函数将对象的refcount设置为0，但不释放对象，通常在需要重写设置refcount的时候使用

对象的生命周期，一般是创建对象，操作对象，释放对象

对象共享

• 使用refcount这个属性来实现对象共享，如果键A创建一个100的字符串，而键B也要创建一个100的字符串，此时100这个字符串对象已经存在内存了，我们只要让键A和键B共享这个字符串对象，就可以节省内存空间

• Redis让多个键共享同一个值对象步骤：

1. 将数据库键的值指针指向同一个现有的值对象

2. 将被共享的值对象的引用的计数加1

   
   
   未被共享的字符串对象
   
   
   被共享的字符串对象

Redis只包含整数值的字符串对象进行共享，因为这样共享对象和目标对象的验证的复杂度是O（1），如果是字符串值的字符串对象，O(N)，如果是多个值对象，比如列表对象或哈希对象，O（n^2）

目前，Redis在初始化服务器的时候，创建一万个字符串对象，从0到9999的所有整数值，当服务器需要用这些值的时候，服务器就共享这些对象，而不是创建对象

创建共享字符串对象的数量可以通过修改redis.h/REDIS_SHARED_INTEGERS进行修改

OBJECT REFCOUNT A可以查看对象的引用计数

对象的空转时长

redisObject对象的lru属性记录对象最后一次被命令程序访问的时间

typedef struct redisObject{
  unsigned lru:22;
}robj;

OBJECT IDLETIME 键可以打印键的空转时长，就是当前时间减去值对象的lru时间得出，这个命令在访问键的值对象的时候，不会修改这个对象的lru属性

当服务器打开了maxmemory选项，并且服务器用于回收内存的算法时volatile-lru或者allkeys-lru，那么当服务器占用的内存数超过了maxmemory选项所设置的值，空转时长较高的那部分键会优先被服务器释放，从而回收内存