Redis数据库
一、Redis中的数据结构和对象
1、简单动态字符串
（1）Redis只会使用C字符串作为字面量，在大多数情况下，Redis使用SDS(Simple Dynamic String)作为字符串表示；
（2）SDS的定义：
struct sdshdr{
//记录buf数组中已使用字节的数量
//等于SDS所保存字符床的长度
int len;
//记录buf数组中未使用字节的数量
int free;
//字节数组，用于保存字符串
char buf[];
}
SDS遵循C字符串以空字符结尾的惯例，保存控制符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节控件，一节添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，所以这个空字符对于SDS的使用者来说是完全透明的。
（3）比起C字符串，SDS具有如下优点：
① 常数复杂度获取字符串长度；
② 杜绝缓冲区溢出；
③ 减少修改字符串长度时所需的内存重分配次数：
1）使用空间预分配策略优化SDS的字符串增长操作；
2）使用惰性空间释放策略优化字符串缩短操作；
3）同时SDS也提供了相应的API，让我们可以在有需要是，真正低释放SDS的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。
（4）二进制安全，所以的SDS API都会以处理二进制的方式来处理SDS存放在buf数组里面的数据，程序不会对其中的数据做任何限制，过滤、或者假设，数据在写入时是什么样的，它在被读取时就是什么样的。
（5）兼容部分C字符串函数。
2、链表
（1）链表和链表节点的实现：
//链表节点
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);
//节点值对比函数
int (*match)(void *ptr,void *key);
} list;（2）链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等；
（3）每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所有Redis的链表实现是双端链表；
（4）每个链表使用一个list结构来表示，这个结构钢带有表头节点的指针、表尾节点指针，以及链表长度等信息；
（5）因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表；
（6）通过为链表设置不同的类型特定函数，Redis的链表可以用于保存各种不同类型的值。
3、字典
（1）字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键；
（2）Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用；
（3）当字典被用作数据库的底层实现，或者哈希表的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值；
（4）哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表；
（5）在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是分多次、渐进式地完成的；
（6）哈希表扩展操作的条件：
① 服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1；
② 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5；
（7）当哈希表的负载因子小于0.1时，程序会自动开始对哈希表执行收缩操作。
4、跳表
（1）跳表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。调表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。
（2）跳表是有序集合的底层实现之一；
（3）Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于标识跳跃表节点；
（4）每个跳跃表节点的层高都是1至32之间的随机数；
（5）在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的；
（6）跳跃表中的节点按照分治大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
5、整数集合
（1）整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现；
（2）整数集合的底层实现为数组，这个数组以有序，无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型；
（3）升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存；
（4）整数集合只支持升级操作， 不支持降级操作。
6、压缩列表
（1）压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短字符串，那么Redis就会使用压缩列表来做列表键的底层实现。
（2）压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序性数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值；
（3）添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。
7、对象
（1）Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含了字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种类型都用到了至少两种前述的数据结构；
（2）通过这五种不同类型的对象，Redis可在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令。使用对象的另一个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。不同类型和编码的对象如下图所示：
（3）对应字符串对象，编码的转换：
① 对于可以用long类型保存的整数：int;
② 对于可以用long double类型保存的浮点数： embstr或raw;
③ 对于字符串值，或者因为长度太大而没办法用long类型表示的整数，又或者因为长度太大而没办法用long double类型表示的浮点数：embstr或raw。
int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下，会被转换为raw编码的字符串对象。
（4）对于列表对象，编码的转换：
当列表对象可以同时满足一下两个条件时，列表对象使用ziplist编码：
①列表对象保存的所有字符串元素的长度都小于64字节；
②列表对象保存的元素数量小于512个；
不能满足这两个条件的列表对象需要使用linkedlist编码。
（5）对于哈希对象，编码的转换：
当哈希表对象可以同时满足一下两个条件时，
哈希对象使用ziplist编码：
①哈希对象保存的所有键值对的检核值的字符串长度都小于64字节；
哈希对象保存的键值对数量小于512个；
不能满足这两个条件的哈希对象需要使用hashtable编码。
（6）对于集合对象，编码的转换：
当集合对象可以同时满足一下两个条件时，对象使用
intset编码
：
①集合对象保存的所有元素都是整数值；
② 集合对象保存的元素数量不超过512个；
不能满足这两个条件的集合对象需要使用hashtable编码。
（7）对于有序集合对象，编码的转换：
当有序集合对象可以同时满足以下两个条件时，对象使用ziplist编码：
①有序集合保存的元素数量小于128个；
②有序集合保存的所有元素成员的长度都小于64字节；
不能满足以上两个条件的有序集合对象将使用skiplist编码。
（8）服务器在执行某些命令之前，会先检查给定键的类型能否执行指定的命令，而检查一个键的类型就是检查键的值对象的类型；
（9）Redis的对象系统带有引用计数实现的内存回收机制，当一个对象不再被使用时，该对象所占用的内存就会被自动释放；
（10）Redis会共享值为0到9999的字符串对象；
（11）对象会记录自己的最后一次被访问的时间，这个时间可以用于计算对象的空转时间。
二、单机数据库的实现
1、数据库
（1）Redis服务器的所有数据库都保存在redisServer.db数组中，而数据库的数量则由redisServer.dbnum属性保存；
（2）客户端通过修改目标数据库指针，让它指向redisServer.db数组中的不同元素来切换不同的数据库；
（3）数据库主要因dict和expires两个字典构成，其中dict字典负责保存键值对，而expires字段则负责保存键的过期时间；
（4）因为数据库由字典构成，所有对数据库的操作都是建立在字典操作之上的；
（5）数据库的键总是一个字符串对象，而值则可以是任意一种Redis对象类型，包括字符串对象、哈希表对象、集合对象、列表对象和有序集合对象，分别对应字符串键、哈希表键、集合键、列表键和有序集合键；
（6）expires字典的键指向数据库中的某个键，而值则记录了数据库键的过期时间，过期时间是一个以毫秒为单位的UNIX时间戳；
（7）Redis使用
惰性删除和定期删除
两种策略来删除过期的键：惰性删除策略只在碰到过期键时才进行删除操作，定期删除策略则每隔一段时间主动查找并删除过期键；
（8）执行SAVE命令或者BGSAVE命令所产生的心RDB文件不会包含已经过期的键；
（9）执行BGREWRITEAOF命令所产生的重写AOF文件不会包含已经过期的键；
（10）当一个过期键被删除之后，服务器会追加一条DEL命令到现有AOF文件的末尾，显式地删除过期键；
（11）当主服务器删除一个过期键之后，它会向所有从服务器发送一条DEL命令，显式地删除过期键；
（12）从服务器即使发现郭其健也不会自作主张删除它，而是等待主节点发来的DEL命令，这种统一、中心化的过期键删除策略可以保证主从服务器数据的一致性；
（13）当Redis命令对数据库进行修改之后，服务器会根据配置向客户端发送数据库通知。
2、RDB持久化
（1）Redis持久化既可以手动执行，也可以根据服务器配置选项定期执行，该功能可以将某个时间点上的数据库状态保存到一个RDB文件中；RDB持久化功能所生成的RDB文件是一个经过压缩的二进制文件，通过该文件可以还原生成RDB文件时的数据库状态。
（2）RDB文件用于保存和还原Redis服务器所有数据库中的所有键值对数据；
（3）SAVE命令由服务器进程直接执行保存操作，所以该命令会阻塞服务器；
（4）BGSAVE命令由子进程执行保存操作，所以该命令不会阻塞服务器；
（5）服务器状态中会保存所有由save选项设置的保存条件，当一个任意保存条件被满足时，服务器会自动执行BGSAVE命令；
（6）RDB文件是一个经过压缩的二进制文件，由多个部分组成；
（7）对于不同类型的键值对，RDB文件会使用不同的方式来保存它们。
3、AOF持久化
（1）被写入AOF文件的所有命令都是以Redis的命令请求协议格式保存的。AOF持久化功能的实现可以分为命令追加、文件写入、命令同步三个步骤；
（2）AOF文件通过保存所有修改数据库的写明了来记录服务器的数据库状态；
（3）命令请求会先保存到AOF缓冲区里面，之后再定期写入并同步到AOF文件；
（4）appendfsync选项的不同值对AOF持久化功能的安全性以及Redis服务器的性能有很大影响；
（5）服务器只要载入并重新执行保存在AOF文件中的命令，就可以还原数据库本来的状态；
（6）AOF重写可以产生一个新的AOF文件买这个新的AOF文件和原有的AOF文件所保存的数据库状态一样，但体积更小；
（7）AOF重写是一个有歧义的名字，该功能是通过读取数据库中的键值对来实现的，程序无须对现有AOF文件进行任何读入、分析或者写入操作；
（8）在执行BGREWRITEAOF命令时，Redis服务器会维护一个AOF重写缓冲区，该缓冲区会在子进程创建新AOF文件器件，记录服务器执行的所有写命令；当子进程完成创建新的AOF文件的工作之后，服务器将会重写缓冲区中的所有内容追加到新的AOF文件的末尾，使得新旧两个AOF文件所保存的数据库状态一致。最后，服务器用新的AOF文件替换旧的AOF文件，以此来完成AOF文件重写操作。
4、事件
（1）Redis服务器是一个事件驱动程序，服务器处理的时间分为时间事件和文件事件两类；
（2）文件事件处理器是基于Reactor模式实现的网络通信程序；
（3）文件事件是对套接字操作的抽象：每次套接字变为可应答（acceptable）、可写入（writable）或者可读（readable）时，相应的文件事件就会产生；
（4）文件事件分为AE_READABLE事件（读事件）和AE_WRITABLE事件（写事件）两类；
（5）事件时间分为定时事件和周期性时间：定时时间只在指定的时间到达一次，而周期性时间则每隔一段时间到达一次；
（6）服务器一般情况下只执行serverCron函数一个时间时间，并且这个时间是周期性事件；
（7）文件事件和时间事件之间是合作关系，服务器会轮流处理这两种事件，并且处理事件的过程中也不会进行抢占；
（8）时间时间的实际处理时间通常会比设定的到达时间晚一些。
5、客户端
（1）Redis服务器是典型的一对多服务器程序：一个服务器可以与多个客户端简历网络连接，每个客户端可以向服务器发送命令请求，而服务器则接受并处理客户端发送的命令请求，并向客户端返回命令回复。
（2）通过使用I/O多路复用技术实现的文件事件处理器，Redis服务器使用单线程单进程的但是来处理命令请求，并与多个客户端进行网络通信。
（3）服务器状态结构使用clients链表连接起多个客户端状态，新添加的客户端状态会被放到链表的末尾；
（4）客户端状态的flags属性使用不同标志来表示客户端的角色，以及客户端当前所处的状态；
（5）输入缓冲区记录了客户端发送的命令请求，这个缓冲区大小不能超过1GB；
（6）命令的参数和参数个数会被记录在客户端状态的argv和argc属性里面，而cmd属性则记录客户端要执行命令的实现函数；
（7）客户端有固定大小缓冲区和可变大小缓冲区两种缓冲区可用，其中固定大小缓冲区大小为16KB，而可变大小缓冲区的最大大小不能超过服务器设置的硬性限制值；
（8）输出缓冲区限制值有两种，如果输出缓冲区的大小超过了服务器设置的硬性限制，那么客户端会被立即关闭；除此之外，如果在一定时间内，一直超过服务器设置的软性限制，那么客户端也会被关闭；
（9）当一个客户端通过网络连接连上服务器是，服务器会为这个客户端创建相应的客户端状态。网络连接关闭、发送了不合协议格式的命令请求、成为CLIENT KILL命令的目标、空转时间超时、输出缓冲区的大小超出限制，以上这些原因都会导致客户端被关闭；
（10）处理Lua脚本的伪客户端在服务器初始化时创建，这个客户端 会一直存在，知道服务器关闭；
（11）载入AOF文件时使用的伪客户端在载入工作开始时动态创建，载入工作完毕之后关闭。
6、服务器
（1）一个命令请求从发送到完成主要包括以下步骤：
① 客户端将命令请求发送给服务器；
② 服务器读取命令请求，并分析出命令参数；
③ 命令执行器根据参数查找命令的实现函数，然后执行实现函数并得出命令回复；
④ 服务器将命令回复返回给客户端。
（2）serverCron函数默认每个100毫秒执行一次，它的工作主要包括更新服务器状态信息，处理服务器接收的SIGTERM信号，管理客户端资源和数据库状态，检查并执行持久化操作等等；
（3）服务器从启动到能够处理客户端的命令请求需要执行以下步骤：
① 初始化服务器状态；
② 载入服务器配置；
③ 初始化服务器数据结构；
④ 还原数据库状态；
⑤ 执行时间循环。
三、多机数据库的实现
1、复制
（1）在Redis中，用户可以通过执行SLAVEOF命令或者设置slaveof选项，让一个服务器去复制另一个服务器；进行复制中的主从服务器双方的数据库将保存相同的数据，即数据库状态一致；
（2）Redis2.8以前的复制功能不能高效地处理断线后重新复制情况，但Redis2.8新添加的部分重同步功能可以解决这个问题；
（3）部分重同步通过复制偏移量、复制积压缓冲区、服务器运行ID三个部分来实现；
（4）在复制操作刚开始的时候，从服务器会成为主服务器的客户端，并通过向主服务器发送命令请求来执行复制步骤，而在复制操作的后去，主从服务器会互相成为对方的客户端；
（5）主服务器通过向从服务器传播命令来更新从服务器的状态，保持主从服务器一直，而从服务器则通过向主服务器发送命令来进行心跳检测，以及命令丢失检测。
2、Sentinel（哨兵）
（1）Sentinel哨兵是Redis高可用性解决方案：由一个或对个Sentinel实例组成的Sentine系统可以见识任意对个主服务器，以及这些主服务器属下的所有从服务器，并在被监视的主服务器进入下线状态时，自动将下线主服务器属下的某个从服务器升级为新的主服务器，然后由新的主服务器替代已下线的主服务器继续处理命令请求。
（2）Sentinel只是一个运行在特殊模式下的Redis服务器，它使用了和普通模式不同的命令表，所以Sentinel模式能使用的命令和普通Redis服务器能够使用的命令不同；
（3）Sentinel会读入用户指定的配置文件，为每个要被监视的主服务器创建相应的实例结构，并创建连向主服务器的命令连接和订阅练级哦，其中命令连接用于向主服务器发送命令请求，而订阅连接用于接收指定频道的消息；
（4）Sentinel通过向主服务器发送INFO命令来获得主服务器属下所有从服务器的地址信息，并未这些从服务器创建相应的实例结构，以及连向这些从服务器的命令连接和订阅连接；
（5）在一般情况下，Sentinel以每10s一次的频率向被监视的主服务器和从服务器发送INFO信息，当主服务器处于下线状态，或者Sentinel正在对主服务器进行故障转移操作时，Sentinel向从服务器发送INFO命令的频率就会改为每秒一次；
（6）对于监视同一个主服务器和从服务器的多个Sentinel来说，它们会以每两秒一次的频率，通过向北监视服务器的__sentinel__:hello频道发送消息来向其他Sentinel宣告自己的存在；
（7）每个Sentinel也会从__sentinel__：hello频道中接收其他Sentinel发来的信息，并根据这些信息为其他Sentinel创建相应的实例结构，以及命令连接。
（8）Sentinel只会与主服务器和从服务器创建命令连接和订阅连接，Sentinel与Sentinel之间则只会创建命令连接；
（9）Sentienl以每秒一次的频率向实例（包括主服务器、从服务器、其他Sentinel）发送PING命令，并根据实例对PING命令的回复来判断实例是否在线，当一个实例在指定的时长中连续向Sentienl发送无效回复时，Sentinel会将这个实例判断为珠光；
（10）当Sentinel将一个主服务器判断为主观下线式，它同样会监视这个主服务器的其他Sentinel进行询问，看它们是否同意这个主服务器进入主观下线状态；
（11）当Sentinel收集到足够多的主观下线投票之后，它会将主服务器判断为客观下线，并发起一次针对主服务器的故障转移操作。
3、集群
（1）Redis集群是Redis提供的分布式数据库方案，集群通过分片来进行数据共享，并通过复制提供故障转移功能。
（2）节点通过握手来将其他节点添加到自己所处的集群当中；
（3）集群中的16384个槽可以被分别指派给集群中的各个节点，每个节点都会记录那些槽指派给了自己，而哪些槽又被指派给了其他节点；
（4）节点在接到一个命令请求时，会先检查这个命令请求要处理的键所在的槽是否由自己负责，如果不是的话，节点将向客户端返回一个MOVED错误，MOVED错误携带的信息可以指引客户端转向至正在负责相关槽的节点；
（5）对Redis集群的重新分片工作是由redis-trib负责执行的，重新分片的关键是将属于某个槽的所有键值对从一个节点转移至另一个节点；
（6）如果节点A正在迁移槽i至节点B，那么当节点A没能在自己的数据库中找到命令指定的数据库键时，节点A会向客户端返回一个ASK错误，指引客户端到节点B继续查找指定的数据库键；
（7）MOVED错误表示槽的负责权已经从一个节点转移到另一个节点，而ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施；
（8）集群里的从节点用于复制主节点，并在主节点下线时，代替主节点继续处理命令请求；
（9）集群中的节点通过发送和接收消息来进行通信，常见的消息包括MEET、PING、PONG、PUBLISH、FAIL五种。
本文内容来源《Redis设计与实现》一书。
声明：本文部分内容整理来源于网络，仅做个人学习使用！侵删~