Redis 设计解析

一、客户端与服务器连接

在使用Redis的时候，通常是多个客户端连接Redis服务器，然后各自发送命令请求(例如Get、Set)到Redis服务器，最后Redis处理这些请求返回结果。





那Redis服务端是使用单进程单线程来处理客户端请求。

有10000个客户端需要连上一个服务器并保持TCP连接，客户端会不定时的发送请求给服务器，服务器收到请求后需及时处理并返回结果。我们应该怎么解决?

方案一：我们使用一个线程来监听，当一个新的客户端发起连接时，建立连接并new一个线程来处理这个新连接。





缺点：当客户端数量很多时，服务端线程数过多，即便不压垮服务器，由于CPU有限其性能也极其不理想。因此此方案不可用。


方案二：我们使用一个线程监听，当一个新的客户端发起连接时，建立连接并使用线程池处理该连接。





优点：客户端连接数量不会压垮服务端。

缺点：服务端处理能力受限于线程池的线程数，而且如果客户端连接中大部分处于空闲状态的话服务端的线程资源被浪费。

因此，一个线程仅仅处理一个客户端连接无论如何都是不可接受的。那能不能一个线程处理多个连接呢？该线程轮询每个连接，如果某个连接有请求则处理请求，没有请求则处理下一个连接，这样可以实现吗？

答案是肯定的，而且不必轮询。我们可以通过I/O多路复用技术来解决这个问题。


Redis 数据库里面的每个键值对(key-value pair)都是由对象(object)组成的，其中
1.数据库键总是一个字符串对象(string object)
2.数据库键的值则可以是字符串对象(string object)、列表对象(list object)、哈希对象(hash object)，集合对象(set object)、有序集合对象(sorted set object)这五种对象中的其中一种

二、Redis 数据结构

1. SDS(Simple Dynamic String) 简单动态字符串

当Redis需要的不仅仅是一个字符串字面量，而是一个可以被修改的字符串值时，Redis就会使用SDS来表示字符串值，比如在Redis的数据库里面，包含字符串值得键值对在底层都是由SDS实现的。

SDS(Simple Dynamic String) 简单动态字符串类型的结构:
struct sdshdr {

   //记录buf数组中已使用字节的数量
   //等于SDS所保存字符串的长度
   long len;

   //记录buf数组中未使用字节的数量
   long free;

   //字节数组，用于保存字符串
   char buf[];

};

len 是buf 数组的长度。
free 是数组中剩余可用字节数，由此可以理解为什么string 类型是二进制安全的了，因为它
本质上就是个byte 数组，当然可以包含任何数据了。
buf 是个char 数组用于存贮实际的字符串内容。

通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略
1.空间预分配
  1）如果对SDS进行修改之后，SDS的长度（也就是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。
  2）如果对SDS进行修改之后，SDS的长度（也就是len属性的值）将大于等于1MB，那么程序会分配1MB的未使用空间。
  通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。

2.惰性空间释放
  惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录下来，并等待将来使用。


2. 链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。
链表在Redis中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。

链表节点和链表的结构

typedef struct listNode{

   //前置节点
   struct listNode *prev;

   //后置节点
   struct listNode *next;

   //节点的值
   void *value;

}listNode;

typedef struct list{

   //表头节点
   listNode *head;

   //表尾节点
   listNode * tail;

   //链表所包含的节点数量
   unsigned long len;

   //节点值复制函数
   void *(*dup)(void *ptr);

   //节点值释放函数
   void (*free)(void *ptr);

   //节点值对比函数
   void (*match)(void *ptr,void *key);

}list;

list 结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，而dup、free和match成员则是用于实现多态链表所需的类型特定函数
dup函数用于复制链表节点所保存的值
free函数用于释放链表节点所保存的值
match函数则用于对比链表节点所保存的值和另一个输入值是否相等

链表实现的特性如下：

双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)

无环：表头节点的prev指针和表尾节点的next指针都指向NULL,对链表的访问以NULL为终点

带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O(1)

多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值


3. 字典

字典是一种用于保存键值对（key-value pair）的抽象数据结构

在字典中，一个键（key）可以和一个值（value）进行关联，这些关联的键和值就成为键值对

字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对等等

Redis的数据库就是使用字典来作为底层实现的。对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

字典的实现：
    Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

哈希表：

typedef struct dictht{

   //哈希表数组
   dictEntry **table;
  
   //哈希表大小
   unsigned long size;
  
   //哈希表大小掩码，用于计算索引值
   //总是等于size - 1
   unsigned long sizemask;
  
   //该哈希表已有节点的数量
   unsigned long used;

}dictht;

table属性是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存着一个价值对。


哈希表节点：

每个dictEntry结构都保存着一个键值对

typedef struct dictEntry{

   //键
   void *key;

   //值
   union{
       void *val;
   uint64_tu64;
   int64_ts64;
   }v;
  
   //指向下个哈希表节点，形成链表
   struct dictEntry *next;

}dictEntry;


字典结构：

typedef struct dict{

   //类型特定函数
   dictType *type;
  
   //私有数据
   void *privdata;
  
   //哈希表
   dictht ht[2];
  
   //rehash 索引
   //当rehash不在进行时，值为 -1
   int trehashidx;
  
}dict;

4. 跳跃表（skiplist）

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。
Redis使用跳跃表作为有序结合键的底层实现之一，如果一个有序集合包含的元素数量表较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

跳跃表节点结构：

typedef struct zskiplistNode{

   //层
   struct zskiplistLevel{
  
      //前进指针
  struct zskiplistNode *forward;
 
  //跨度
  unsigned int span;
  
   }level[];
  
   //后退指针
   struct zskiplistNode *backward;

   //分值
   double score;
  
   //成员对象
   robj *obj;
 
}zskiplistNode;


跳跃表结构：

typedef struct zskiplist{

   //表头节点和表尾节点
   struct zskiplistNode *header,*tail;

   //表中节点的数量
   unsigned long length;
  
   //表中层数最大的节点的层数
   int level;
 
}zskiplist;


header和tail 指针分别指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头节点和表尾节点的复杂度为O(1)。
通过使用length熟悉来记录节点的数量，程序可以在O(1)复杂度内返回跳跃表的长度。
level熟悉则用于在O(1)复杂度内获取跳跃表中层高最大的那个节点的曾数量（表头节点的层高并不计算在内）。


整数集合(intset)

整数集合(intset)是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现

整数集合(intset)是Redis用于保存整数值得集合抽象数据结构，它可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素

typedef struct intset{

   //编码方式
   uint32_t encoding;
  
   //集合包含的元素数量
   uint32_t length;
  
   //保存元素的数组
   int8_t contents[];
  
}intset;

contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数据项(item)，各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要的时候，程序会根据新添加元素的类型，改变这个数组的类型。

整数集合只支持升级操作，不支持降级操作。


5. 压缩列表（ziplist）

压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表要么就是小整数值，要么就是长度比较短的字符串，那么Reids就会使用压缩列表来做列表键的底层实现。

压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。


三、Redis 对象

Redis 基于以上这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种我们前面介绍的数据及结构。

通过这五种不同类型的对象，Redis可以在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令。使用对象的另一个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用频率。

Redis 的对象系统还实现了基于引用计数计数的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放；另外，Redis还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存。

Redis的对象带有访问时间记录信息，该信息可以用于计算数据库键的空转时长，在服务器启用了maxmemory功能的情况下，空转时长较大的那些键可能会优先被服务器删除。

Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。

Redis中的每个对象都由一个redisObject结构表示，该结构中和保存数据有关的三个属性分别是type属性、encoding属性和ptr属性

typedef struct redisObject{

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


对象的type 属性记录了对象的类型，这个属性的值可以是下表列出的其中一个：





对于Redis数据库保存的键值对来说，键总是一个字符串对象，而值则可以使字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种。因此，当我们对一个数据库键执行type命令时，命令返回的结果为数据库键对应的值对象的类型，而不是键对象的类型，键对象的类型总是字符串对象类型。如下表：





对象的ptr指针指向对象的底层实现数据结构，而这些数据机构由对象的encoding属性决定。encoding属性记录了对象所使用的编码，也即是说这个对象使用了什么数据结构作为对象的底层实现，encoding属性值如下表：





每种类型的对象都至少使用了两种不同的编码，如下表：





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