redis简介

redis是典型的NOSQL数据库，也是一个高性能的key-value型数据库。通过源码对redis的实现进行分析，有助于学习优秀的源码设计思想。

redis底层数据结构

1、简单动态字符串：

简单动态字符串是redis内部实现的一种抽象数据类型，源码如下：

 * 保存字符串对象的结构  
 */  
struct sdshdr {  
      
    // buf 中已占用空间的长度  
    int len;  
  
    // buf 中剩余可用空间的长度  
    int free;  
  
    // 数据空间  
    char buf[];  
};

其中len表示数据空间buf中已经存储的字符串长度；free表示数据空间buf中未占用的空间长度。
通过SDS的数据结构，可以发现其与string的不同可以归纳为：

2、链表：

链表是redis中最常用的数据结构（redis中的链表是双端链表），redis中列表键、发布和订阅等功能的底层结构都是通过链表来链接的。

3、字典：

字典也叫map，是key-value的抽象数据结构。redis中定义为：

typeof struct dictEntry{
   //键
   void *key;
   //值
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;
}
typedef struct dictht {
   //哈希表数组
   dictEntry **table;
   //哈希表大小
   unsigned long size;

   //哈希表大小掩码，用于计算索引值
   unsigned long sizemask;
   //该哈希表已有节点的数量
   unsigned long used;
}
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privedata;
    // 哈希表
    dictht  ht[2];
    // rehash 索引
    in trehashidx;
}

通过源码和结构图，可以理解字典的实现就是通过hash，找到对应的dictEntry，然后通过链表来解决冲突。
在源码中，ht容量为2，其中ht[1]是用来进行rehash，通过rehash渐进式动态拓展字典空间。

4、跳跃表：

typedef struct zskiplistNode{
　　　//层
     struct zskiplistLevel{
　　　　　//前进指针
        struct zskiplistNode *forward;
　　　　//跨度
        unsigned int span;
    } level[];
　　//后退指针
    struct zskiplistNode *backward;
　　//分值
    double score;
　　//成员对象
    robj *obj;
}
typedef struct zskiplist {
     //表头节点和表尾节点
     structz skiplistNode *header,*tail;
     //表中节点数量
     unsigned long length;
     //表中层数最大的节点的层数
     int level;
}zskiplist;

跳跃表是一种有序数据结构，通过level来区分大小。

5、整数集合：

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

}

intset的源码如上，其中encoding：用于定义整数集合的编码方式，通过encoding可以存储多种类型的int，length：用于记录整数集合中变量的数量，contents：用于保存元素的数组，虽然我们在数据结构图中看到，intset将数组定义为int8_t，但实际上数组保存的元素类型取决于encoding

6、压缩列表：

压缩列表是一种比较简单的数据结构，通过entry保存少量数据，具体结构见上两图，通过图结构基本能够理解具体的实现方式。

redis支持的value数据类型

redis支持五种数据类型分别为：字符串、列表（list）、哈希（hash）、集合（set）、有序集合（sort set）。这几种数据类型在底层的实现基本都是有上章所述的底层结构组成，明确了redis的底层数据结构，现对redis支持的数据类型的具体实现进行分析，并整理redis常用命令。
redis中使用对象用键值对表示，其中健只有字符串一种类型，值为redis支持的五种数据类型，键、值对象具体结构为：

typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
int refcount;
void *ptr;
} robj;

其中，type表示对象类型，encoding表示对象编码，也就是该对象使用什么底层数据结构实现，ptr指向对象的底层数据结构，具体类型表示为：

现对值对象进行分析：

1、字符串对象：

字符串对象有三种，分别为int、raw、embstr，具体结构如下：

如果一个字符串时整数，并且可用long型表示，那么该字符串对象编码就是int。如果字符串长度大于39字节，那么将使用一个简单动态字符串(sds)保存，并将对象编码设置为raw。如果字符串长度小于等于39字节，则字符串以编码方式embstr来保存该字符串值。
redis支持字符串命令如下：

2、列表对象：

列表对象底层可以是ziplist（压缩列表）或者linkedlist（链表），列表对象保存的所有字符串长度都小于64字节并且列表保存的元素数量小于512个时使用ziplist编码实现，否则使用linkedlist编码实现，具体结构如下图。

redis支持列表命令如下：

3、哈希对象：

哈希对象的底层可以是ziplist（压缩列表）和hashtable（字典），列哈希象保存的所有字符串长度都小于64字节并且列表保存的元素数量小于512个时使用ziplist编码实现，否则使用hashtable编码实现。

redis支持哈希命令如下：

4、集合对象：

集合对象的底层为intset（整数）和hashtable（字典），集合对象所有的元素都是整数值并且集合对象数量不超过512个时使用intset实现，否则使用hashtable实现。

redis支持集合命令如下：

5、有序集合对象：

有序集合的底层为ziplist（压缩列表）和skiplist（字典和跳跃表组成的结构体）。

skiplist结构：

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

redis支持有序集合命令如下：

5、redis的键命令

服务器对键空间的维护包括：
1)对一个键的读取命中次数和未命中次数，在INFO stats命令的keyspace_hits属性和keyspace_misses属性中查看。
2）读取一个键之后，服务器会更新键的LRU时间，这个值可以用于计算键的闲置时间。
3）读取一个键发现键已经过期了，那么服务器会删除这个过期键，然后才执行余下的其他操作。
4）如果有客户端使用WATCH命令监视某个键，被修改之后会记为脏（dirty），让事务程序注意到这修改。
5）每次修改一个键之后，都会对脏（dirty）键计数器的值增1，这个计数器会触发服务器的持久化以及复制操作。
6）键的修改触发数据库通知功能。

redis数据的持久化

redis的数据是存储在内存中的，这样的好处是增删改查比较快，问题是易造成数据的丢失，为解决该问题，redis支持持久化。redis的持久化有两种分别是：RDB方式（RDB文件的方式保存到硬盘）和AOF方式（写命令保存的方式保存到硬盘）。

1、RDB方式

RDB方式是采用快照的方式来实现，通过快照生成RDB文件保存在硬盘，重启的时候，从RDB读取文件恢复数据。
RDB方式的主要几个关键点：
1、配置方式
1）SAVE（阻塞）、BGSAVE（非阻塞）命令
2）配置规则
3）复制（主从模式时，Redis会在复制初始化时进行自动快照）
4）FLUSHALL命令（无意义，执行 flushall 命令，也会产生dump.rdb文件，但里面是空的）
2、RDB方式有缺点
①、优势
1）RDB是一个非常紧凑(compact)的文件，它保存了redis 在某个时间点上的数据集。这种文件非常适合用于进行备份和灾难恢复。
2）生成RDB文件的时候，redis主进程会fork()一个子进程来处理所有保存工作，主进程不需要进行任何磁盘IO操作。
3）RDB 在恢复大数据集时的速度比 AOF 的恢复速度要快。
②、劣势
1）RDB方式数据没办法做到实时持久化/秒级持久化。因为bgsave每次运行都要执行fork操作创建子进程，属于重量级操作(内存中的数据被克隆了一份，大致2倍的膨胀性需要考虑)，频繁执行成本过高(影响性能)
2）RDB文件使用特定二进制格式保存，Redis版本演进过程中有多个格式的RDB版本，存在老版本Redis服务无法兼容新版RDB格式的问题(版本不兼容)
3）在一定间隔时间做一次备份，所以如果redis意外down掉的话，就会丢失最后一次快照后的所有修改(数据有丢失)
3、自动保存原理
源码：

struct redisService{
     //1、记录保存save条件的数组
     struct saveparam *saveparams;
     //2、修改计数器
     long long dirty;
     //3、上一次执行保存的时间
     time_t lastsave;
}
struct saveparam{
     //秒数
     time_t seconds;
     //修改数
     int changes;
};

在 redis.conf 配置文件中进行了关于save 的配置：
save 900 1：表示900 秒内如果至少有 1 个 key 的值变化，则保存
save 300 10：表示300 秒内如果至少有 10 个 key 的值变化，则保存
save 60 10000：表示60 秒内如果至少有 10000 个 key 的值变化，则保存
代码中结构如下图：

saveparams数组里保存了配置参数后，Redis 服务器有一个周期性操作函数 severCron ,默认每隔 100 毫秒就会执行一次，该函数会遍历并检查 saveparams 数组中的所有保存条件，只要有一个条件被满足，那么就会执行 bgsave 命令，当服务器成功执行一次修改操作，那么dirty 计数器就会加 1，而lastsave 属性记录上一次执行save或bgsave的时间。

2、AOF方式

Redis 默认不开启。它的出现是为了弥补RDB的不足（数据的不一致性），所以它采用日志的形式来记录每个写操作，并追加到文件中。Redis 重启的会根据日志文件的内容将写指令从前到后执行一次以完成数据的恢复工作。
1、配置方式
打开 redis.conf 文件，找到 APPEND ONLY MODE 对应内容
1 ）redis 默认关闭，开启需要手动把no改为yes：
appendonly yes
2）指定本地数据库文件名，默认值为 appendonly.aof
appendfilename "appendonly.aof"
3）指定更新日志条件（同步频率）
appendfsync always
appendfsync everysec
appendfsync no
4）配置重写触发机制
auto-aof-rewrite-percentage 100
auto-aof-rewrite-min-size 64mb
AOF 文件的生成过程具体包括命令追加，文件写入，文件同步三个步骤。 Redis 打开 AOF 持久化功能后，Redis 在执行完一个写命令后，都会将执行的写命令追回到 Redis 内部的缓冲区的末尾。这个过程是命令的追加过程。 接下来，缓冲区的写命令会被写入到 AOF 文件，这一过程是文件写入过程。对于操作系统来说，调用write函数并不会立刻将数据写入到硬盘，为了将数据真正写入硬盘，还需要调用fsync函数，调用fsync函数即是文件同步的过程。只有经过文件同步过程，AOF 文件才在硬盘中真正保存了 Redis 的写命令。appendfsync 配置选项正是用来配置将写命令同步到文件的频率的。
2、AOF优缺点
优点：数据的完整性和一致性更高
缺点：因为AOF记录的内容多，文件会越来越大，数据恢复也会越来越慢。

单机和集群的实现

1、单机redis的实现

1）数据库

服务器中的数据库结构：

redisClient切换数据库：
redis客户端默认目标数据库为0号数据库，可以通过SELECT命令来切换目标数据库。客户端状态redisClient结构的db属性记录了客户端当前的目标数据库，这个属性是指向redisdb结构的指针。

typedef struct redisClient{
    //记录客户端当前正在使用的数据库
    redisDb *db;
} redisClient;

数据库键空间：
Redis是一个键值对数据库服务器，服务器中的每个数据库都由一个redis.h/redisDb结构表示，其中redisDB的dict字典保存了数据库中的所有键值对，我们将这个字典称为键空间。

typedef struct redisDb{
    // 数据库键空间，保存着数据库中的所有键值对
    dict *dict
} redisDb;

具体可见前文。

2）持久化

持久化分为RDB和AOF持久化，前章已经总结完。

3）事件

事件分为文件事件和时间事件。
文件事件是基于Reactor模式实现的，主要包括套接字、I/O多路复用程度、文件事件分派器、事件处理器：

I/O多路复用程序总是会将所有产生事件的套接字都放在一个队列里面，并串行化地向文件事件分派器传送套接字，并由对应的事件处理器进行处理。

定时事件：让一段程序在指定的时间之后执行一次。
周期性事件：让一段程序每隔指定时间就执行一次。
时间事件应用实例包括：
1）更新服务器的各类统计信息，比如时间、内存占用、数据库占有情况等
2）清理数据库的过期键值对
3）关闭和清理连接失效的客户端
4）尝试执行AOF和RDB持久化操作
5）如果服务器是主服务器，对从服务器进行同步
6）如果服务器是集群模式，对集群进行定期同步和连接
事件的具体执行流程如：

4）客户端

客户端源码：

struct redisServer{
    //一个保存所有client的链表
    list *clients;
}
typedef  struct redisClient{
    //套接字描述符：客户端状态的fd属性记录了客户端正在使用的套接字描述符，-1（伪客户端），>-1（普通客户端）
    int fd;
    //名字：CLIENT SETNAME命令可以为客户端设置名字
    robj *name;
    //标志：客户端的标志属性flags记录了客户端的角色，以及客户端目前所处的状态
    int flag;
   //输入缓冲区 用于保存客户端发出的命令请求
    sds querybuf;
   //命令参数：在服务器将客户端发送的命令请求保存到客户端状态的querybuf属性之后，服务器将对命令请求的内容进行分析，并将得出的命令参数以及命令参数的个数分别保存到客户端状态的argv属性和argc属性：
    int argc;
    robj **argv;
  //输出缓存区：buf是一个大小为REDIS_REPLY_CHUNK_BYTES字节的字节数组，而bufpos属性则记录了buf数组目前已使用的字节数量。REDIS_REPLY_CHUNK_BYTES常量目前的默认值为16*1024，也即是说，buf数组的默认大小为16KB，reply为可变大小缓冲区由链表和一个或多个字符串对象组成
    int bufpos;
    char buf[REDIS_REPLY_CHUNK_BYTES];
    list *reply;
   //身份验证标志：客户端状态的authenticated属性用于记录客户端是否通过了身份验证，authenticated的值为0，表示客户端尚未通过身份认证，authenticated的值为1，表示客户端已通过认认证   
    int authenticated;
   //客户端的时间关键字：ctime属性记录了创建客户端的时间，lastinteraction属性记录了客户端与服务器最后一次进行互动（interaction）的时间，lastinteraction属性可以用来计算客户端的空转时间
    time_t ctime;         
    time_t lastinteraction;
    time_t obuf_soft_limit_reached_time;
}redisClient;

客户端的创建与关闭：

当客户端与服务器通过网络建立连接时，服务器就会调用连接处理事件，为客户端创建相应的客户端状态，并将新的客户端状态添加到服务器状态结构clients链表的尾链。当客户端与服务端断开网络连接时，从clients链表去掉。
客户端的类型：
普通客户端、伪客户端（Lua脚本的伪客户端、AOF文件的伪客户端）

5）服务端

redis服务器主要实现以下几个功能：
1）服务器初始化，开始接受命令。
　　初始化服务器全局状态。
　 载入配置文件。
　　创建 daemon 进程。
　　初始化服务器功能模块。
　　载入数据。
　　开始事件循环。
2）服务器为每个已连接的客户端维持一个客户端结构，这个结构保存了这个客户端的所有 状态信息。
3）客户端向服务器发送命令，服务器接受命令然后将命令传给命令执行器，执行器执行给 定命令的实现函数，执行完成之后，将结果保存在缓存，最后回传给客户端。

2、多机redis的实现

1）复制

用户通过执行slaveof命令或者设置slaveof选项，可以让一个服务器去复制另外一个服务器，形成主从关系。被复制的服务器为主服务器，对主服务器进行复制的服务器称为从服务器。
旧版本复制功能：1）同步：将从服务器的数据库状态更新至主服务器当前所处的数据库状态。2)命令传播：主服务器的数据库状态被修改，导致主从数据库的状态不一致，让主从服务器的数据库从新回到一致状态。
1、同步

2、命令传播
主服务器把写命令传播到从服务器，使得主从服务器的数据库状态一致。比如当主服务器执行DEL key时，会异步的把该命令发送给从服务器，使两者状态最终一致。存在如果从服务器中途短线，重连后需要重新执行一遍同步操作，效率较低（生产RDB文件需要耗费大量I/O、CPU资源）的问题。
新版本复制功能：
新版本使用PSYNC命令替代SYNC，该命令具有完整重同步和部分重同步两种模式。其中部分重同步实现原理如下：
新版本的实现中，主从服务器分别维护一份复制偏移量，记录当前复制的进度。当主服务器向从服务器发送N个字节的数据时就把自己的偏移量加上N，当从服务器接收到N个字节的数据时就把自己的偏移量也加上N，如果主从服务器数据处于一致，那么它们的偏移量也是一致的。

psync 分为完全同步，部分同步
(1)复制偏移量
主服务器每次想从服务器创博N个字节数据时，同时将自己的复制偏移量加N.从服务器接收N个字节数据，同时更新自己的偏移量加N.　　　　　　　
(2)复制积压缓冲区
主服务器将缓冲区命令发送给从服务器，同时更新复制积压缓冲区，标记命令字节的偏移量。主服务器会根据这个积压偏移量，选择同步命令的方式。　　　　　　　　　　　　　　
(3)同步服务器ID
根据ID和存储的ID对比选择不同的同步方式。

2）哨兵

哨兵策略是redis高可用的解决方案（一个或者多个哨兵实例组成的哨兵系统），可以监视多个主服务器。例如：

哨兵的主要功能如下：
1、Sentinel启动与初始化

1. 初始化服务器
2. 使用Sentinel专用代码
3. 初始化Sentinel状态
4. 初始化Sentinel状态的masters属性
5. 创建连向主服务器的网络连接
   2.2 获取主服务器信息
   Sentinel默认每10s通过命令连接向被监视的主服务器发送INFO命令。
   2.3 获取从服务器信息
   Sentinel发现主服务器有新的从服务器出现，除了会为这个新的从服务器创建相应的实例结构外，还会创建连接到从服务器的命令连接和订阅连接。创建命令连接后，Sentinel默认每10s通过命令连接向从服务器发送INFO命令。
   2.4 向主服务器和从服务器发送信息
   Sentinel默认每2s通过命令连接向所有被监视的主服务器和从服务器的sentinel:hello频道发送消息。
   2.5 接收来自主服务器和从服务器的频道消息
   Sentinel与一个主服务器或者从服务器建立起订阅连接后，Sentinel就会通过订阅连接，向服务器发送：SUBSCRIBE sentinel:hello
   当sentinel接收到一条消息时，sentinel会提取出Sentinel IP，Sentinel端口号，Sentinel运行ID：
   1）若消息中的运行ID与自身一样，则忽略；
   2）若不一样，接受消息的Sentinel将根据消息，更新相应的主服务器的实例结构。首先更新Sentinel字典，然后创建连向其他Sentinel的命令连接。
   2.6 检测主观下线状态
   Sentinel每秒向与之创建了命令连接的实例发送PING命令，并通过回复来判断实例是否在线。
   如果一个实例在down-after-milliseconds毫秒内，连续向Sentinel返回无效回复，那么Sentinel会修改这个实例结构，表示该实例已主观下线。
   2.7 检测客观下线状态
   Sentinel使用命令：SENTINEL is-master-down-by-addr <ip> <port> <current_epoch> <runid> 询问其他Sentinel是否同意主服务器下线；
   目标Sentinel会分析并取出命令请求中包含的各个参数，检查主服务器是否已下线，然后向源Sentinel返回一个包含三个参数的Multi Bulk回复；
   根据其他Sentinel发回的命令回复，Sentinel将统计其他Sentinel同意主服务器已下线的数量，当该数量达到配置指定的参数时，Sentinel会将主服务器实例结构的flags属性SRI_O_DOWN打开，表示主服务器已经下线。
   2.8 选举领头Sentinel
   2.9 故障转移
   1）选出新的主服务器(依次排除下线或断线的->最近5s内没有回复领头Sentinel的INFO命令的->与已下线主服务器连接断开超过down-after-milliseconds*10的->优先级->复制偏移量->运行ID)；
   2）修改从服务器的复制目标；
   3）将旧的主服务器变为从服务器。

3）集群

1）集群的数据结构

clusterNode记录自己的状态,并为集群中的其他节点(包括主节点和从节点)都创建了一个相应的clusterNode结构,以此来记录其他节点的状态。
具体握手过程如图：

3）在集群中执行命令

PING消息：检测节点是否在线。
PONG消息：接收者收到发送者的MEET消息或者PING消息时，返回PONG消息以向发送者确认收到了该消息。
FAIL消息：当主节点A判断另一主节点B已进入FALL状态，节点A会向集群广播一条关于B的FALL消息，其他节点收到后立即将B标记为已下线。
PUBLISH消息：接收者立即执行这个命令，并向集群广播一条PUBULISH消息。

redis的发布与订阅

Redis 发布订阅(pub/sub)是一种消息通信模式：发送者(pub)发送消息，订阅者(sub)接收消息。

常用命令如下：

redis的发布与订阅分为频道订阅和模式订阅两种，具体内容如下：
1）频道订阅
每个 Redis 服务器进程都维持着一个表示服务器状态的 redis.h/redisServer 结构， 结构的 pubsub_channels 属性是一个字典， 这个字典就用于保存订阅频道的信息：

struct redisServer {
    // ...
    dict *pubsub_channels;
    // ...
};

具体结构如下图：

struct redisServer {
    // ...
    list *pubsub_patterns;
    // ...
};
typedef struct pubsubPattern {
    redisClient *client;
    robj *pattern;
} pubsubPattern;

redis事务

redis事务常用命令如下：

从redis支持的事务命令中可以看出，基于watch命令，事务分为带watch和不带watch的事务。其中不带watch的事务就是正常命令的执行（“将多个命令打包， 然后一次性、按顺序地执行”）。
带watch的事务执行原理：
在每个代表数据库的 redis.h/redisDb 结构类型中， 都保存了一个 watched_keys 字典， 字典的键是这个数据库被监视的键， 而字典的值则是一个链表， 链表中保存了所有监视这个键的客户端。具体如图所示：