一、数据结构

主要记录几个比较独特的数据结构。

1、字典

   整个Redis的键值对存储可以说就是两个哈希表;键冲突解决采用的开链,新节点总是在链表的头部;计算键哈希值使用的是MurmurHash2算法。
Redis的哈希表比较厉害的是他的rehash方法,因为整个数据库的数据量一般都会很大,一次rehash完肯定会阻塞数据库很长一段时间,所以其rehash使用的渐进式rehash:
  (1)首先,哈希表中有两个数组ht[0]和ht[1],其中ht[0]为平时使用的哈希表。如果是扩展操作,ht[1]的大小会扩展成第一个大于等于ht[0].used*2的2n 。如果是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2n 。
  (2)在字典中维持了一个计数器rehashidx,并将它设为0,表示开始rehash。
  (3)每次对字典执行添加、删除、查找或者更新操作时,还会顺便将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]上面,然后++rehashidx。
  (4)最后所有键值对都迁移完毕后,将ht[0]设置为ht[1],将ht[1]设置成ht[0],然后将rehashidx设为-1,表示rehash完毕。

  扩展时机:
  服务器没有执行BGSAVE命令或者BGREWRITEAOF命令时负载因子大于等于1时,反之负载因子大于等于5时,执行扩展操作。原因是这两个命令创建了子进程,而大多数操作系统都采用copy on write,所以创建了子进程后尽量避免不必要的写操作。
  收缩时机:
  当哈希表的负载因子小于0.1时执行收缩操作。

2、跳跃表

  Redis的跳跃表节点包含后退指针,分值(可以相同),成员对象(必须不同),和层。每次创建一个新的跳跃表节点时候,都根据幂次定律随机生成一个介于1和32之间的值作为level(层)数组的大小(levelDB的跳表最大是12层,和这里不同),层又包含前进指针和跨度。

3、整数集合

  整数集合保证集合中不会出现重复元素,整数集合中的整数有int16,int32,int64三种编码方式,为了节省内存,会优先使用最小的编码方式,当插入了当前编码方式不能接收的整数时会进行升级,将整个整数集合中所有数据升级成更大的编码方式。目前不支持降级。

4、压缩列表

  Redis中使用得非常多的数据结构,给我的震撼程度甚至比渐进式rehash还要大。
  一个压缩列表节点主要由previous_entry_length,encoding,content组成。
  previous_entry_length:前一个entry的长度,如果前一节点长度小于254字节,那么该属性为1字节。如果前一字节长度大于等于254字节,该属性为5字节,其中第一个字节为0xFE(254),后四字节为长度。
  encoding:保存数据的类型和长度。
  content:内容。
  压缩列表存在一个问题,就是连锁更新:前面一个entry的长度发生了变化,导致后面一连串的长度发送了变化,从而导致多次重新分配内存。

5、对象

图片12.png
(1)REDIS_STRING中的EMBSTR和RAW
字符串长度小于等于39字节使用EMBSTR,否则使用RAW。raw编码会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构,embstr则一次分配连续空间。

(2)REDIS_LIST中的ZIPLIST和LINKEDLIST
若列表对象中保存的所有字符串元素的长度都小于64字节,且元素数量小于512个,则使用ziplist,否则使用linkedlist编码。

(3)REDIS_HASH中的ZIPLIST和HT
若哈希对象中保存的所有键或者值的字符串元素的长度都小于64字节,且元素数量小于512个,则使用ziplist,否则使用hashtable编码。
这里ziplist存储键值对的方式如下:
图片13.png

(4)REDIS_SET中的INTSET和HT
集合对象全是整数,元素数量不超过512个的时候使用intset,否则使用hashtable。
使用hashtable编码的集合对象如下,value值为NULL:
图片14.png

(5)REDIS_ZSET中的ZIPLIST和SKIPLIST
有序集合保存的元素数量小于128个且所有元素的长度都小于64字节时使用ziplist,否则使用skiplist。
这里使用skiplist实际还使用了一个字典存储字符串和分值的映射:
图片15.png
字符串使用的是指针,并没有拷贝一份,所以没有造成内存浪费。

二、单机数据库

1、过期键删除策略

  首先,上面也提到了,整个Redis的键值对存储可以说就是两个哈希表,其中一个存的是键值对,一个存的是键——过期时间。有了这个字典,redis每次就可以找到过期的键值对了。
  Redis采用的是惰性删除和定期删除两种策略:
惰性删除就是执行操作前判断一下当前键有没有过期,过期了就将其删除。
定期删除就是每当服务器周期性执行serverCron函数时,就会在规定时间内,分多次便利服务器中的各个数据库,从数据库中的过期字典中检查一部分键的过期时间,并删除其中的过期键。

2、RDB持久化

  执行SAVE或BGSAVE(创建子进程进行写RDB文件)命令可以创建一个新的RDB文件,保存数据库中所有的键值对,其中已过期的键不会被保存在新的RDB文件中。
  若以主服务器模式运行载入RDB时,过期键会被忽略,从服务器则都会载入。
  可以配置多个自动执行RDB的条件:n秒内对数据库进行了至少m次修改则执行BGSAVE命令。主要实现就是有两个变量dirty和lastsave,dirty记录距离上次成功执行SAVE或BGSAVE命令之后数据库进行了多少次的修改;lastsave记录上次SAVE或BGSAVE的时间。然后服务器每隔一定时间(默认100ms),将这两个变量与参数数组(记录了配置值)进行比较,,满足配置条件就BGSAVE。
  RDB文件结构如下:
图片16.png
  其中的database部分结构如下:
图片17.png
  其中key_value_pairs的结构如下:
图片18.png
图片19.png
  当开启了RDB文件压缩功能的情况下,对于字符串长度大于20字节的对象会被压缩后再保存(使用的LZF算法),对于ziplist也会先转换成一个字符串对象,再压缩保存。

3、AOF持久化

  AOF文件实际上就是将每一条指令都记录了下来(可以设置为每条指令来了都flush到磁盘也可以设置为定期flush到磁盘),使用AOF文件载入还原数据也就是相当于重新输指令了。那么这就可能产生很多冗余数据,所以redis提供AOF文件重写功能BGREWRITEAOF,该功能可以理解成用指令记录数据库目前的键值对,这样一个键值对就只对应一条指令了。
  那么,子进程进行AOF重写期间新的命令对现有的数据库状态进行了修改怎么办呢?Redis设置了一个AOF重写缓冲区,会记录AOF重写期间的写命令,最后追加到新的AOF文件中。

4、事件

  Redis服务器是一个事件驱动程序,包含文件事件和时间事件,使用的reactor模型。其中时间时间分为定时事件和周期性事件,实现方法是将所有时间事件放在一个无序链表中,每当时间事件执行器运行时,就遍历整个链表,查找已到达的时间事件,并调用相应的事件处理器。

5、客户端

  服务器使用clients链表连接起多个客户端状态,用flags属性表示客户端角色和状态。服务器中一个客户端对象包含一个输入缓冲区和一个输出缓冲区:输入缓冲区记录了客户端发送的命令请求,不能超过1GB,命令参数记录在argc和argc中;输出缓冲区分为固定大小和可变大小两种,固定大小的最大为16KB,可变大小的不能超过服务器设置的硬性限制,否则立刻关闭该客户端,另外,日过一定时间内一直超过服务器设置的软性限制,那么客户端也会被关闭。

##6、服务端
  主要是一个serverCron函数,该函数默认每隔100毫秒执行一次,它的工作主要包括更新服务器状态信息,处理服务器接收的SIGTERM信号(先进行持久化操作,在关闭服务器),管理客户端资源和数据库状态,检查执行持久化操作。

三、多机数据库

1、复制

  Redis的复制功能主要分为命令传播和同步(sync)。
  命令传播:
  主服务器接收到的写命令会发送给从服务器。
  同步PSYNC功能,分为完全重同步和部分重同步:
  完全重同步:主服务器执行BGSAVE命令,并记录从此刻起的所有写命令。然后将生成的RDB文件和记录的写命令发送给从服务器,即完成同步。
  部分重同步:用于断线处理,即只发送断线期间的写命令。

  部分重同步的实现主要就是依赖一个复制偏移量,一个复制积压缓冲区,主从服务器偏移量不同则说明发生了断线,则根据复制挤压缓冲区内容恢复从服务器,若复制积压缓冲区数据不够就进行完全重同步。另外,从服务器是会保存主服务器id的,若断线后发现主服务器的id和当前保存的主服务器id一致才进行部分重同步。

2、Sentinel

  由一个或多个Sentinel实例组成的Sentinel系统可以监视任意多个主服务器,在主服务器下线时,自动将下线主服务器属下的某个从服务器升级为新的主服务器。
  首先,sentinel会想主服务器建立两条连接(一条用于发送命令,一条用于订阅频道),然后默认会以十秒一次的频率通过命令连接想监视的主服务器发送INFO命令获取主服务器的信息来更新主服务器实例对象。也会默认以十秒一次的频率想从服务器发送INFO命令更新从服务器实例对象。不仅如此,sentinel还会为同样监视这个主服务器的其它sentinel创建一个字典来保存其它sentinel的资料,并与之创建命令连接(没有订阅连接)。
  默认情况下,seninel会以每秒一次的频率向所有与它创建了连接的实例发送PING命令来判断是否下线。当足够多的sentinel判定主服务器主观下线(各sentinel可能有不同的配置,比如有的sentinel认为30000ms为下线标准而有的认为5000ms)后,就认为其客观下线。
  当一个主服务器被判断为客观下线后,监视这个主服务器的各个sentinel就会进行协商,选出一个领头Sentinel(Raft共识算法的一个实现):
(1)所有sentinel平等。
(2)最先向目标sentinel发送设置要求的源sentinel将成为目标sentinel的局部领头sentinel(也就是先到先得,先到先得也就说明了自己的网络状态相对来说是比较好的),之后的设置要求都会被忽略。
(3)一定时间内,如果有某个sentinel被半数以上的sentinel设置成局部领头,那这个sentinel就成为领头sentinel,进行故障转移操作。若没有,则重新进行选举。
  最后,则进行故障转移,即挑选一个从服务器为主服务器,然后将已下线的主服务器设置为新的主服务器的从服务器。筛选方法如下:
(1)删除下线的从服务器。
(2)删除最近五秒没有回复过INFO命令的从服务器。
(3)删除所有与已下线主服务器连接断开超过down-after-milliseconds * 10毫秒的从服务器,即保证剩余的从服务器保存的数据都比较新。
(4)根据优先级排序,挑选第一个从服务器。

3、集群

  通过CLUSTER MEET加入集群(使用的Gossip协议传播给集群其它节点,简单来说就是每秒都会随机向其他节点发送自己所拥有的节点列表,以及需要传播的消息。任何新加入的节点,就在这种传播方式下很快地被全网所知道)。
Redis集群通过分片的方式来保存数据库中的键值对:集群的整个数据库被分为16384个槽,每个键都属于这16384个槽的其中一个,集群中的每个节点可以处理0到16384个槽。
  每个节点如何记录自己处理哪些槽呢,使用的是二进制数(bitmap)。同时还会保存集群所有槽的指派信息,即集群中的每个节点都会知道数据库中的16384个槽分别被指派给了集群中的哪些节点。
  当客户端向节点发送与数据库键有关的命令时,接收命令的节点会计算出命令要处理的数据库属于哪个槽,并检查这个槽是否指派给了自己,若没有指派给自己,就会像客户端返回一个MOVED错误,指引客户端转向正确的节点。
  节点计算键的CRC-16校验和然后&16383即可得到键所属槽号。
  当需要重新分片(将任意数量已经指派给某个节点的槽改为指派给另一节点)时,由redis-trib负责执行,主要就是命令源节点原子地将键值对迁移到目标节点。这时如果客户端发送命令,源节点会首先从自己的数据库找指定的键,若没有则返回ASK错误引导客户端转向正确的节点。这里ASK和MOVED错误的区别在于,产生MOVED错误后,客户端之后都会将命令发送至修改后的目标节点,而产生ASK命令后,客户端今后还是会发送到之前发送的节点,因为其它的键还是有可能存在源节点的。
  那么,如何处理节点的异常下线呢,实际和sentinel的处理方式很像。首先半数以上负责处理槽的主节点都将某个主节点x报告为疑似下线后,这个主节点就将被标记为已下线(FAIL),然后标记为已下线的节点会向集群广播一条关于主节点x的FAIL消息,所有收到这条消息的节点都将立即标记x已下线。接下来就是选举新的主节点,方法和选举sentinel头领类似,当从节点发现自己的主节点下线,会向集群广播一条消息,其它主节点会票选自己第一个收到消息的从节点,某个从节点获得N/2 + 1张投票时它成为主节点(其实这也说明它的网络状况最好)。