

首页  思维导图  详情



Redis设计与实现

2021-09-20 23:35:56   0  举报





AI智能生成

Redis的设计与实现

学霸笔记

设计

Redis底层原理

Redis的设计与实现

模版推荐

作者其他创作

大纲/内容

多机数据库的实现

复制

旧版本复制功能的实现

同步

从服务器向主服务器发送SYNC命令

收到SYNC命令的主服务器执行BGSAVE命令，在后台生成一个RDB文件，并使用一个缓冲区记录从现在开始执行的所有写命令

主服务器将生成的RDB文件发送给从服务器

主服务器将记录在缓冲区里面的所有写命令发送给服务器

命令传播

Redis通过命令传播让主从节点再次保持一致性

缺陷

对于断线后复制，待从服务器重新上线后，从服务器发送SYNC命令，主服务器会重新生成一个全量的RDB文件发送给从服务器， 因此主服务器会旧版复制功能效率比较低

SYNC非常耗资源

主服务器执行BGSAVE命令，这个命令会耗费大量的CPU、内存和磁盘I/O资源

主服务器发送RDB文件给从服务器，这个操作会消耗大量的网络资源（宽带和流量）

从服务器接收RDB文件并载入RDB文件时，从服务器因为阻塞而没办法处理命令请求

新版本复制功能的实现

PSYNC代替SYNC，PSYNC有完整重同步和部分重同步

完整重同用于初次复制，同SYNC命令基本一致

部分重同步用于处理断线后重新复制，主服务器会将断线后的写命令发送给从服务器

部分重同步

主服务器的复制偏移量（replication offset）和从服务器的复制偏移量

主服务器每次向从服务器传播N个字节的数据时，就将自己偏移量的值+N

主服务器的复制积压缓冲区（replication backlog）

如果在主服务器发送从服务器A前，从服务器A断线了，假设从服务器A断线后立即重新上线后， 主服务器如何补偿从服务器A在断线期间丢失的那部分数据呢？

复制积压缓冲区是由主服务器维护的一个固定长度（fixed-size）先进先出（FIFO）队列，默认大小为1MB

主服务器进行命令传播时，不仅会将写命令发送给所有的从服务器，还会将写命令入队到复制积压缓冲区里面。

如果从服务器重新上线后发送PSYNC命令，如果offset偏移量之后的数据仍然存在于复制积压缓冲区里面， 执行部分重同步操作；否则执行完整重同步操作。

redis.conf/repl-backlog-size

默认1MB，如果主服务器执行大量的写操作，或者主服务器断线后重连接所需的时间比较长，大小可能不合适

计算：second * write_size_per_second，断线后未同步数据的总和

second：从服务器断线后重新连接上主服务器所需的平均时间

write_size_per_second：主服务器平均每秒产生的写命令数据量

服务器的运行ID（run ID）

运行ID在服务器启动时自动生成，由40个随机的十六进制字符组成。537759abddd858395aadddcb124376abbcda89765

如果从服务器保存的运行ID和上次断线重连的运行ID相同，主服务器可以继续执行部分重同步操作

如果从服务器保存的运行ID和上次断线重连的运行ID不同，主服务器执行完整重同步操作

PSYNC命令的实现

从服务器接收到客户端发来的SLAVEOF命令，判断是否是从服务器第一次执行复制？

如果是，向主服务器发送 PSYNC ? -1，如果不是，向主服务器发送 PSYNC runid  offset

如果是第一次执行复制，主服务器返回 +FULLRESYNC runid offset 执行完整同步操作

如果不是第一次执行复制，判断服务器是否返回 +CONTINUE？ 是：主服务器返回 +FULLRESYNC runid offset，执行完整同步，否：执行部分重同步

复制的实现

设置主服务器的地址和端口

建立套接字连接

发送PING命令

如果读取PING命令的回复超时或者主服务器返回了一个错误，则断开重连

身份验证

如果从服务器开启 masterauth <master-password>进行验证，否则不进行验证

主服务器设置了requirepass，从服务器也必须设置masterauth选项

发送端口信息

身份验证后，从服务器执行命令REPLCONF listening-port <port-number>，向主服务器发送从服务器的监听端口号

主服务器：INFO replication

role：master

connected_slaves:1

slave0：ip=127.0.0.1，port=12345，status=online，offset：1289，lag=1

master_repl_offset：1289

repl_backlog_active=1

repl_backlog_size：1048576

repl_backlog_first_byte_offset：2

repl_backlog_hlistlen：1288

同步

命令同步

心跳检测

在命令传播阶段，从服务器默认会以每秒一次的频率，向主服务器发送命令， REPLCONF ACK <replication_offset>

检测主从服务器的网络连接状态

主从服务器通过发送和接收REPLCONF ACK 命令来检查两者之间的网络连接是否正常

INFO replication 命令，lag表示服务器最后一次向主服务器发送REPLCONF ACK命令距离现在过了多少秒

辅助实现min-slaves配置选项

min-slaves-to-write 和 min-slaves-max-lag 防止主服务器在不安全的情况下执行写命令

min-slaves-to-write：3    min-slaves-max-lag：10

以上配置表示当从服务器的个数小于3，或者从服务器的延迟lag值都大于等于10秒时，主服务器将拒绝执行写命令

检测命令丢失

如果发生网络故障，主服务器传播给从服务器的写命令在半路丢失，那么当从服务器向主服务器发送REPLCONF ACK命令时， 主服务器会在复制积压缓冲区找到服务器缺少的数据，重新发送。

主服务器向从服务器补发数据和部分重同步原理非常像

补发缺失数据在主服务器没有断线的情况下执行

部分重同步在主从服务器断线并重连之后执行

Sentinel

当主服务器下线超过用户设定的下线时长上限时， Sentinel系统就会对服务器执行故障转移操作

Sentinel系统会挑选server属下的一个从服务器，将从服务器升级为主服务器

Sentinel系统向server属下的所有从服务器发送新的复制命令，让他们成为新的主服务器的从服务器， 当所有的从服务器开始复制新的主服务器的时候，故障转移操作执行完毕。

Sentinel系统会继续监视已下线的server，并在它重新上线时，将它设置为新的主服务器的从服务器

启动并初始化Sentinel

启动一个Sentinel命令

初始化服务器

将普通Redis服务器使用的代码替换成Sentinel专用代码

初始化Sentinel状态

根据给定的配置文件，初始化Sentinel的监视主服务器列表

创建连向主服务器的网络连接

初始化服务器

初始化Sentinel不会载入RDB文件或者AOF文件。

不使用一些常见命令，比如SET、DEL、FLUSHDB、MULTI、WATCH、EVAL、SAVE和BGSAVE、BGREWTITEAOF

因为服务器根本没有在命令表中载入这些命令

SLAVEOF、发布与订阅（除了PUBLISH只能在Sentinel内部使用）、文件事件处理、时间事件处理，Sentinel内部使用。

使用Sentinel专用代码

将一部分普通Redis服务器使用的代码替换成Sentinel专用代码。

普通服务器：redis.h/REDIS_SERVERPORT； Sentinel使用：sentinel.c/REDIS_SENTINEL_PORT

普通服务器：redis.c/redisCommandTable作为服务器命令表； Sentinel使用sentinel.c/sentinelcmds作为服务器的命令表

PING、SENTINEL、INFO、SUBSCRIBE、UNSCRIBE、PSUBSCRIBE、PUNSUBSCRIBE 七个命令就是客户端可以对Sentinel执行的全部命令。

初始化Sentinel状态

服务器会初始化一个sentinel.c/sentinelState结构（简称"Sentinel"状态）， 这个结构保存了服务器中所有和Sentinel功能有关的状态

初始化Sentinel状态的masters属性

Sentinel状态中的masters字典记录了所有被Sentinel监视的主服务器的相关信息，其中： 键：被监视主服务器的名字。值：被监视主服务器对应的sentinel.c/sentinelRedisInstance结构

对Sentinel状态的初始化将引发对masters字典的初始化， 而masters字典的初始化时根据载入的Sentinel配置文件来进行的

sentinelRedisInstance

char *name：主服务器由用户在配置文件配置；从服务器以及Sentinel的名字由Sentinel自动配置

sentinel * addr：实例地址，指向sentinelAddr

mstime_t down_after_period：实例无响应多少毫秒之后才会判断为主观下线

int quorum：判断这个实例为客观下线所需的支持投票数量

int parallel_syncs：在执行故障转移操作时，可以同时对新的主服务器进行同步的从服务器数量

mstime_t failover_timeout：刷新故障迁移状态的最大时限

创建连向主服务器的网络连接

对于每个被Sentinel监视的主服务器来说， Sentinel会创建两个连向主服务器的异步网络连接

一个是命令连接，这个连接专门用于向主服务器发送命令，并接收命令回复。

一个是订阅连接，这个连接专门用于订阅主服务器的_sentinel_: hello频道。

为什么有两个连接？

为了不丢失_sentinel_:hello频道的任何信息，Sentinel必须专门用一个订阅连接来接收该频道的信息

Sentinel还必须向主服务器发送命令，以此来与主服务器进行通信。

获取主服务器的状态

Sentinel默认会以10s一次的频率，通过命令连接向被监视的主服务器发送INFO命令， 通过分析INFO命令的回复来获取主服务器的当前信息（INFO带有从服务器的信息）

主服务器重启之后，Sentinel会对实例结构的运行ID进行更新

主服务器实例结构的flags属性的值为SRI_MASTER，从服务器的flags属性值为SRI_SLAVE

主服务器实例结构的name属性的值时用户使用Sentinel配置文件设置的， 而从服务器实例结构的name属性的值时Sentinel根据从服务器的IP地址和端口号自动设置的

获取从服务器的信息

Sentinel发现主服务器有新的从服务器出现时，Sentinel除了会为这个新的从服务器创建相应的实例结构之外， Sentinel还会创建连接到从服务器的命令连接和订阅连接。

在创建命令连接后，Sentinel在默认情况下，会以每10s/次的频率通过命令连接向从服务器发送INFO命令，更新实例结构

向主服务器和从服务器发送信息

PUBLISH _sentinel_:hello "<s_ip>,<s_port>,<s_runid>,<s_epoch>,<m_name>,<m_ip>,<m_port>,<m_epoch>"

默认情况下，Sentinel会以2s/次的频率，通过命令连接向所有被监视的主服务器和从服务器发送命令， 命令向服务器的_sentine_：hello频道发送了一条信息。

接收来自主服务器和从服务器的频道信息

当Sentinel与一个主服务器或者从服务器建立起订阅连接之后，Sentinel会通过订阅连接， 向服务器发送命令：SUBSCRIBE _sentinel_: hello, Sentinel对 _sentinel_: hello频道的订阅会一直持续到Sentinel与服务器的连接断开为止。

Sentinel既能通过命令向服务器的_sentinel_：hello 频道发送消息， 又能通过订阅连接从服务器的_sentinel_ : hello频道接收消息

假设有Sentinel1、Sentinel2、Sentinel3三个Sentinel在监视同一个服务器，那么 当sentinel向服务器的_sentinel_：hello频道发送一条信息时，所有订阅了_sentinel_：hello频道的Sentinel都会收到这条信息。

当一个Sentinel从_sentinel_：hello频道接收到一条信息时，Sentinel会对这条信息进行分析， 提取Sentinel IP地址、Sentinel端口、Sentinel运行ID等八个参数：

如果信息中记录的Sentinel运行ID和接收信息的Sentinel的运行ID相同， 说明这条信息时Sentinel自己发送的，Sentinel将丢弃这条信息，不做处理

相反，如果信息中记录的Sentinel运行ID和接收信息的Sentinel的运行ID不相同，那么 说明这条信息是监视同一个服务器的其他Sentinel发来的，接收信息的Sentinel将根据信息中的各个参数，对相应主服务器的实例结构进行更新。

更新sentinel字典

Sentinel为主服务器创建的实例结构中的sentinels字典保存了除Sentinel本身之外， 所有同样监视这个主服务器的其他Sentinel资料

sentinel字典的键是其中一个Sentinel的名字，格式为ip：port

sentinel字典的值则是键所对应Sentinel的实例结构

当一个Sentinel接收到其他Sentinel发来的信息时， 目标Sentinel会从信息中分析并提取出一下两方面参数

与Sentinel有关的参数

与主服务器有关的参数

根据信息中提取出的主服务器参数，目标Sentinel会在自己的Sentinel状态的masters字典中查找相应的主服务器实例结构， 然后根据提取出的Sentinel参数，检查主服务器实例结构的sentinel字典中，源sentinel的实例结构是否存在：

如果源Sentinel的实例结构已经存在，那么对源Sentinel的实例结构进行更新

如果源Sentinel的实例结构不存在，那么说明源Sentinel是刚刚开始监视主服务器的新Sentinel， 目标Sentinel会为源SentinelSentinel创建一个新的实例结构，并将这个结构添加到sentinels字典里面

用户在使用Sentinel的时候并不需要提供各个Sentinel的地址信息，监视同一个主服务器的多个Sentinel可以自动发现对方

创建连向其他Sentinel的命令连接

Sentinel之间不会创建订阅连接

Sentinel在连接主服务器或者从服务器时，会同时创建命令连接和订阅连接， 但在连接其他Sentinel时，却只会创建命令连接，而不创建订阅连接。

以上因为Sentinel需要通过接收主服务器或者从服务器发来的频道信息来发现未知的新的Sentinel， 所以才需要建立订阅连接，而相互已知的Sentinel只要使用命令连接来进行通信就足够了。

检测主观下线状态

默认情况下，Sentinel会以每秒一次的频率向所有与它创建了命令连接的实例发送PING命令， 并通过实例返回的PING命令回复来判断实例是否在线。

Sentinel在配置文件down-after-milliseconds选项制定了Sentinel判断实例进入主观下线所需的时间长度

如果一个实例在down-after-milliseconds毫秒内，连续向Sentinel返回无效回复，那么Sentinel会修改这个实例所对应的实例结构，在结构的flags属性中打开SRI_S_DOWN标识，以此来表示这个实例已经进入主观下线状态。

sentinel monitor master 127.0.0.1 6379 2 sentinel down-after-milliseconds master 50000

50000毫秒不仅会成为Sentinel判断master进入主观下线的标准，还会成为Sentinel判断master属下的所有从服务器， 以及所有同样监视master的其它Sentinel进入主观下线的标准。

多个Sentinel设置的主观下线时长可能不同

检测客观下线状态

当Sentinel将一个主服务器判断为主观下线之后，为了确认这个主服务器是否真的下线了，他会向同样监视主服务器的其他Sentinel进行询问。当Sentinel从其他Sentinel哪里接收到足够数量的已下线判断之后，Sentinel就会将从服务器判定为客观下线，并对主服务器进行故障转移操作。

发送SENTINEL is-master-down-by-addr命令

SENTINEL is-master-down-by-addr <ip> <port> <current_epoch> <runid>

命令询问其他Sentinel是否同意主服务器已下线

接收SENTINEL is-master-down-by-addr命令

<down_state>、<leader_runid>、<leader_epoch>

返回Sentinel是否同意主服务器下线

接收SENTINEL is-master-down-by-addr命令的回复

统计其他Sentinel同意主服务器已下线的数量，当这一数量达到配置指定的判断客观下线所需的数量时， Sentinel会将主服务器实例结构flags属性的SRI_O_DOWN标识打开，表示主服务器进入下线状态

客观下线的判定条件

sentinel monitor master 127.0.0.1 6379 2

只要有两个sentinel认为主服务器已经进入下线状态，那么当前sentinel就将主服务器判断为客观下线

不同Sentinel判断客观下线的条件可能不同

sentinel monitor master 127.0.0.1 6379 2 sentinel monitor master 127.0.0.1 6379 5

sentinel1认为只有两个sentinel认为主服务器下线，Sentinel1就会将主服务器判断为客观下线。

sentinel2认为只有五个sentinel认为主服务器下线，Sentinel2就会将主服务器判断为客观下线。

选举领头Sentinel

当一个主服务器被判断为客观下线时，监视这个下线主服务器的各个Sentinel会进行协商， 选举出一个领头Sentinel，并由领头Sentinel对下线主服务器执行故障转移操作

所有从服务器都有机会成为主服务器

每次进行领头Sentinel选举之后，不论选举是否成功，所有Sentinel的配置纪元的值都会自增一次。计数器

如果有某个Sentinel被半数以上的Sentinel设置成了局部领头Sentinel，那么这个Sentinel成为领头Sentinel。

如果在给定时限内，没有一个Sentinel被选举为领头Sentinel，那么各个Sentinel将在一段时间之后再次进行选举，直到选出领头Sentinel为止。

故障转移

在选举出领头Sentinel之后，领头Sentinel将对已下线的主服务器执行故障转移操作

在已下线主服务器属下的所有从服务器里面，挑选出一个从服务器，并将其转换为主服务器

让已下线主服务器属下的所有从服务器改为复制新的主服务器

将已下线主服务器设置为新的主服务器的从服务器，当这个旧的主服务器重新上线时，他就会成为新的主服务器的从服务器

选举出新的主服务器

向挑选的从服务器发送SLAVEOF no one命令，将这个从服务器转换为主服务器

新的主服务器时怎样挑选出来的？

修改从服务器的复制目标

让已下线主服务器属下的所有从服务器去复制新的主服务器，可以通过SLAVEOF命令实现

领头Sentinel向已下线主服务器server1的从服务器server3和server4发送SLAVEOF命令，让他们复制新的server2

将旧的主服务器变为从服务器

将已下线的主服务器设置为新的主服务器的从服务器

当旧的主服务器重上线时，Sentinel就会向它发送SLAVEOF命令，让他成为从服务器

Sentinel系统选举领头Sentinel的方法是对Raft算法的领头选举方法的实现

集群

Redis集群是Redis提供的分布式数据库方案，集群通过分片来进行数据共享，并提供复制和故障转移功能

节点、槽指派、命令执行、重新分片、转向、故障转移、消息

节点

连接各个节点的工作可以使用CLUSTER MEET命令完成：CLUSTER MEET <ip> <port>

CLUSTER MEET 127.0.0.1 7001 CLUSTER MEET 127.0.0.1 7002 CLUSTER MEET 127.0.0.1 7003

启动节点

cluster-enabled：是否开启集群

集群数据结构

clusterNode结构保存了一个节点的当前状态，比如节点的创建时间、节点的名字、 节点当前的配置纪元、节点的IP地址和端口号等

每个节点都会使用一个clusterNode结构来记录自己的状态，并为集群中的所有其他节点（包括住主节点和从节点） 都创建一个相应的clusterNode结构，以此来记录其他节点的状态

clusterLink结构的link属性是一个clusterLink结构，该结构保存了连接节点所需的有关信息， 比如套接字描述符，输入缓冲区和输出缓冲区

redisClient结构和clusterLink结构的相同之处和不同之处？

redisClient结构中的套接字和缓冲区是用于连接客户端的

clusterLink结构中的套接字和缓冲区则是用于连接节点的

CLUSTER MEET命令的实现

客户端、节点A、节点B

客户端发送命令CLUSTER MEET <B_ip> <B_port>；

节点A发送MEET消息到节点B；

节点B返回PONG消息；

节点A返回PING消息；

之后，节点A会将节点B的信息通过Gossip协议传播给集群中的其他节点， 让其他节点也与节点B进行握手，最终，节点B会被集群中的所有其他节点认识

槽指派

Redis集群通过分片的方式来保存数据库中的键值对：集群的整个数据库被分为16384个槽（slot）， 数据库中的每个键都属于这16384个槽的其中一个，集群中的每个节点可以处理0个或最多16385个槽

当数据库中的16384个槽都有节点在处理时，集群处于上线状态（ok）； 相反地，如果数据库中有任何一个槽没有得到处理，那么集群处于下线状态（fail）

使用CLUSTER MEET 命令将7000、7001、7002三个节点连接到了同一个集群里面， 不过这个集群目前仍然处于下线状态，因为集群中的三个节点都没有在处理任何槽：

将1-5000分配给7000：CLUSTER ADDSLOTS 0...5000； 将5001-10000分配给7001：CLUSTER ADDSLOTS 5001...10000； 将10001-16384分配给7002：CLUSTER ADDSLOTS 10001...16384；

记录节点的槽指派信息

clusterNode结构的slots属性和numslot属性记录了节点负责处理哪些槽

slots属性是一个二进制位数组（bit array），这个数组的长度为16384/8=2048个字节，对slots数组中的16384个二进制位进行编号， 并根据索引i上的二进制位的值来判断节点是否负责处理槽i：二进制位1：负责处理槽i。

传播节点的槽指派信息

一个节点除了会将自己负责处理的槽记录在clusterNode结构的slots属性和numslots属性之外， 他还会将自己的slots数组通过消息发送给集群中的其他节点，告知其他节点自己目前负责处理哪些槽。

集群中的而每个节点都会知道数据库中的16384个槽分别被指派给了集群中的哪些节点

记录集群所有槽的指派信息

clusterState.slots数组记录了集群中所有槽的指派信息

clusterNode.slots数组只记录了clusterNode结构所代表的节点的槽指派信息

CLUSTER ADDSLOTS命令

CLUSTER ADDSLOTS命令接受一个或多个槽作为参数，并将所有输入的槽指派给接收该命令的节点负责：CLUSTER ADDSLOTS <slot> <slot ...>

在集群中执行命令

对数据库16384个槽都进行了指派之后，集群就会进入上线状态，这是客户端就可以向集群中的节点发送数据命令了

当客户端向节点发送与数据库键有关的命令时，接收命令的节点就会计算出命令要处理的数据库键属于哪个槽， 并检查这个槽是否指派给了自己

如果键所在的槽正好就指派给了当前节点，那么节点直接执行这个命令

如果键所在的槽没有指派给当前节点，那么节点会向客户端返回一个MOVED错误， 指引客户端转向至正确的节点，并再次发送之前执行的命令。

计算键属于哪个槽

节点使用 CRC16(KEY) & 16383 来计算给定键key属于哪个槽

def slot_number(key)；            return CRC16(KEY) & 16383

CLUSTER KEYSLOT <key>：查看一个给定键属于哪个槽

判断槽是否由当前节点负责处理

当节点计算出键所属的槽i之后，节点就会检查自己在clusterState.slots数组中的项i， 判断键所在的槽是否由自己负责

如果 clusterState.slots[i] 等于 clysterState.myself，那么说明槽 i 由当前节点负责，节点可以执行客户端发送的命令。

如果 clusterState[i].slot[i] 不等于 clusterState.myself ，那么说明槽 i 并非由当前节点负责，节点会根据 clusterState.slots[i] 指向的 clusterNode 结构 所记录的节点 IP 和端口号，向客户端返回 MOVED 错误，指向客户端转向至正在处理槽 i 的节点。

MOVED 错误

当节点发现键所在的槽并非由自己负责处理的时候，节点就会向客户端返回一个MOVED错误， 指引客户端转向至正在负责槽的节点。

MOVED 错误的格式：MOVED <slot> <ip>:<port>

当客户端向节点7000发送SET命令，获得MOVED错误，转向至节点7001，并重新发送SET命令

一个集群客户端通常会与集群中的多个节点创建套接字连接，而所谓的 节点转向实际上就是换一个套节点来发送命令

被隐藏的MOVED错误

集群模式的redis-cli客户端在接收到MOVED错误时，并不会打印出MOVED错误，而是会根据MOVED错误自动进行节点转向， 并打印出错误信息，所以我们是看不见节点返回MOVED错误的

redis-cli -c -p 7000 #集群

单机模式的redis-cli客户端，再次向节点7000发送相同的命令，那么MOVED错误就会被客户端打印出来

redis-cli -p 7000 #单机模式

单机模式的redis-cli客户端不清楚MOVED错误的作用，所以它只会直接将MOVED错误直接打印出来，而不会自动转换

节点数据库的实现

集群节点保存键值对以及键值对过期时间的方式，与单机Redis服务保存键值对过期时间的方式完全相同

节点只能使用 0 号数据库，而单机Redis服务器则没有限制

除了将键值对保存在数据库里面之外，节点还会用 clusterState 结构中的 slots_to_keys 跳跃表来保存槽和键之间的关系

重新分片

Redis 集群的重新分片操作可以将任意数量已经指派给某个节点的槽改为指派给另一个节点， 并且相关槽所属的键值对也会从源节点被移动到目标节点。

重新分片操作可以在线进行，在重新分片的过程中，集群不需要下线，并且源节点和目标节点都可以继续处理命令请求

重新分片的实现原理

Redis集群的重新分片操作是由Redis的集群管理软件redis-trib负责执行的， redis-trib通过向源节点和目标节点发送命令来进行重新分片

redis-trib对集群的单个槽slot进行重新分片的步骤

redis-trib 给源节点发送命令 CLUSTER GETKEYSINSLOT <slot> <count>

源节点返回最多 count 个属于槽 slot 的键；

redis-trib 对于每个返回键向源节点发送一个 MIGRATE 命令；

源节点根据 MIGRATE 命令的指令将键迁移至目标节点；

ASK错误

在进行重新分片期间，源节点向目标节点迁移一个槽的过程中，可能出现一种情况： 属于被迁移槽的一部分键值对保存在源节点里面，而另一部分键值对则保存在目标节点。

当客户端向源节点发送一个与数据库键有关的命令，并且命令要处理的数据库键恰好就属于正在被迁移的槽时：

源节点先在自己的数据库查找指定的键，如果找到的话，就直接执行客户端发送的命令

如果源节点没能在自己的数据库里面找到指定的键，那么这个键有可能已经被迁移到了目标节点，源节点将会返回给客户端一个ASK错误， 指引客户端转向正在导入槽的目标节点，并再次发送之前想要执行的命令

被隐藏的ASK错误

和接收到MOVED错误时的情况类似，集群模式的redis-cli在接到ASK错误时也不会打印错误， 而是自动根据错误提供的IP地址和端口进行转向动作。单机模式会返回一个错误。

CLUSTER SETSLOT IMPORTING命令

CLUSTER SETSLOT MIGRATING命令

ASK错误

ASKING命令

打开发送该命令的客户端的REDIS_ASKING标识

客户端的REDIS_ASKING标识是一个一次性标识，当节执行了一个带有REDIS_ASKING标识的客户端发送的命令之后， 客户端的REDIS_ASKING标识就会被移除。

ASK错误和MOVED错误的区别

MOVED 错误代表槽的负责权已经从一个节点转移到另一个节点了

ASK 错误只是两个节点在迁移槽的过程中使用的一种临时措施，但这种转向不会对客户端今后发送关于槽i的命令请求产生任何影响

复制与故障转移

Redis集群中的节点分为主节点和从节点，主节点用户处理槽，从节点用于复制某个主节点， 并在被复制的主节点下线时，代替下线主节点继续处理命令请求。

设置主节点

CLUSTER REPLICATE <node_id>

可以让接收命令的节点成为 node_id 所指定节点的从节点，并开始对主节点进行复制

从节点复制主节点相当于向从节点发送命令 SLAVEOF <ip> <port>

故障检测

集群中的每个节点都会定期向集群中的其他节点发送PING消息，来检测对方是否在线，如果接收PING消息的节点没有在规定的时间内，向发送PING消息的节点返回PONG消息，那么发送PING消息的节点就会将接收PING消息的节点标记位疑似下线

集群中的各个节点会通过互相发送消息的方式来交换集群中各个节点的状态消息， 例如某个节点是否处理在线状态、疑似下线状态（PFAIL），还是已下线状态（FAIL）

如果在一个集群中，半数以上负责处理槽的主节点都将某个主节点x报告为疑似下线，那么这个主节点x将被标记位已下线（FAIL），将主节点x标记为已下线的节点会向集群广播一条关于主节点x的FAIL消息，所有收到这条FAIL消息的节点都会立即将主节点x标记为已下线。

故障转移

当一个从节点发现自己正在复制的主节点进入了已下线状态时，从节点将开始对下线主节点进行故障转移，以下是故障转移步骤：

复制下线主节点的所有从节点里面，会有一个从节点被选中；

被选中的从节点会执行 SLAVEOF no one 命令，成为新的主节点；

新的主节点会撤销所有对已下线主节点的槽指派，并将这些槽全部指派给自己；

新的主节点向集群广播一条PONG消息，可以让集群中的其他节点立即直到这个节点由从节点变为主节点， 并且主节点已经接管了原本由已下线节点负责处理的槽。

新的主节点开始接收和自己负责处理的槽有关的命令请求，故障转移完成

选举新的主节点

以下是主节点的选取方法：

子主题

消息

集群中的各个节点通过发送和接收消息来进行通信，发送消息的成为发送者，接收消息的成为接收者。

节点发送消息

MEET消息：发送者会向接收者发送MEET消息，请求接收者加入到发送者当前所处的集群

PING 消息：集群里的每个节点默认每隔1s就会从已知节点列表中随机选出五个节点，对这五个节点中最长时间没有发送过PING消息的节点发送PING消息，以此来检测被选中的节点是否在线。

如果节点A最后一次收到节点B发送的PONG消息的时间，距离当前时间已经超过了节点A的cluster-node-timeout 选项设置时长的一半，那么节点A也会向节点B发送PING消息，可以防止节点A因为长时间没有随机选中节点B作为PING消息的发送对象而导致对节点B的信息更新滞后

PONG消息：当接收者收到发送者发来的MEET消息或者PING消息时，为了向发送者确认MEET消息或PING消息已到达，接收者会返回一条PONG消息。

FAIL消息：当一个主节点A判断另一个主节点B已经进入FAIL状态时，节点A向集群广播一条节点B的FAIL消息，所有收到这条消息的节点都会立即将节点B标记为已下线。

PUBLISH消息：当节点接收到一个PUBLISH命令时，节点会执行这个命令，向集群广播一条PUBLISH消息，所有接收到这条PUBLISH消息的节点都会执行相同的PUBLISH命令

消息头

一条消息由消息头（header）和消息正文（data）组成

节点发送的所有消息都由一个消息头包裹，消息头除了包含消息正文之外，还记录了消息发送者自身的一些信息

MEET、PING、PONG消息的实现

Redis集群中的各个节点通过Gossip协议来交换各自关于不同节点的状态信息，其中Gossip协议由MEET、PING、PONG三种消息实现

FAIL消息的实现

子主题

PUBLISH消息的实现

子主题

独立功能实现

发布与订阅

PUBLISH、SUBSCRIBE、PSUBSCRIBE（模式订阅）

除了 SUBSCRIBE 订阅频道之外，客户端还可以通过执行 PSUBSCRIBE 命令订阅一个或多个模式

PSUBSCRIBE 可以匹配订阅多个频道

频道的订阅与退订

redisServer  dict *pubsub_channels；

Redis将所有频道的订阅关系都保存在服务器状态的pubsub_channels字典中， 键：某个被订阅的频道，值：记录了所有订阅这个频道的客户端链表

订阅频道

如果已经有订阅该频道的客户端，采用尾插法；

如果没有创建字典，添加客户端

退订频道

如果该频道存在，遍历删除；

如果频道字典的值删除后没有值了，也会删除频道字典

模式的订阅与退订

redisServer list *pubsub_pattrens； pubsubPattern  {redisClient *client; robj *pattern}：链表

订阅频道

新建一个pubsubPattern结构，将结构的pattern属性设置为被订阅者的模式，client属性设置为订阅模式的客户端

将pubsubPattern结构添加到pubsub_pattern链表的表尾

退订频道

遍历pubsubPattern结构，如果当前客户端和pubsubPattern记录的客户端相同， 并且要退订的模式也和pubsubPattern记录的模式相同，将这个结构从链表中删除

发送消息

将消息发送给频道订阅者

如果channel键不存在于pubsub_channels字典中，说明channel频道没有任何订阅者

否则至少由一个订阅者

将消息发送给模式订阅者

遍历链表，将消息发送给所有和channel频道相匹配的模式的订阅者

查看订阅信息

PUBSUB CHANNELS [pattern]

返回服务器当前被订阅的频道

PUBSUB NUMSUB [channel-1 channel-2 ... channel-n]

返回频道的订阅者数量

PUBSUB NUMPAT

返回服务器当前被订阅模式的数量

事务

Redis 通过 MULTI、EXEC、WATCH、DISCARD等命令来实现事务功能

事务提供了一种将多个命令请求打包，然后一次性、按顺序地执行多个命令的机制，在事务执行期间， 服务器不会中断事务而改去执行其他客户端的命令请求，它会将事务中的所有命令都执行完毕，然后采取处理其他客户端的命令请求。

事务的实现

一个事务经历的三阶段

事务开始

命令入队

事务执行 

事务开始

将执行该命令的客户端从非事务状态切换至事务状态

这一切换是通过在客户端状态的flags属性中打开 REDIS_MULTI 标识来完成的

命令入队

服务器接收到来自客户端的命令后，如果客户端处于非事务状态，执行这个命令；

如果客户端处于事务状态，继续判断这个命令是否EXEC、DISCARD、WATCH、MULTI，如果是执行命令， 如果不是，将命令放入事务队列，向客户端返回QUEUED

事务队列

每个Redis客户端都有自己的事务状态，事务状态保存在客户端状态的mstate属性里：redisClient{multiState mstate; // 事务状态，MULTI/EXEC state }

事务状态包含一个事务队列，以及一个已入队命令的计数器 multiState{multiCmd *commands；#事务队列，FIFO顺序}

执行事务

当一个处于事务状态的客户端向服务器发送EXEC命令时，这个EXEC命令将立即被服务器执行。遍历事务队列，执行，将结果返回给客户端。

WATCH 命令的实现

WATCH 命令是一个乐观锁，它可以在EXEC命令执行之前，监视任意数量的数据库键，在执行EXEC命令执行时，检查被监视的键是否至少有一个已经被修改过了，如果是，服务器拒绝执行事务，返回给客户端事务执行失败的空回复。

使用 WATH 命令监视数据库键

redisDb {dict *watched_keys； //正在被WATCH命令监视的键}

watched_keys字典的键：被WATCH命令监视的数据库键，值：监视数据库键的客户端链表

监视机制的触发

所有对数据库进行修改的命令，比如SET、LPUSH、SADD等，在执行之后都会调用multi.c/touchWatchKey函数对watched_keys字典进行检查， 查看刚刚被命令修改过的数据库键是否由客户端正在监视，如果有的话，那么touchWatchKey函数会将监视被修改键的客户端的REDIS_DIRTY_CAS标识打开，标识该客户端的事务安全性已经被破坏。

判断事务是否安全

客户端向服务器发送EXEC命令，判断客户端的REDIS_DIRTY_CAS标识是否已经打开？

如果是，拒绝执行客户端提交的事务；否则，执行客户端提交的事务

一个完整的 WATCH 事务的执行过程

client1> WATCH 'name'； client1> MULTI; client2> set 'name' 'perter'； client1> set 'name' 'john'； client1> EXEC； (nil)

事务ACID性质

原子性

Redis的事务和传统的关系型数据库事务的最大区别在于：Redis不支持事务回滚机制（rollback）

Redis因为命令入队出错而被服务器拒绝执行，事务中的所有命令都不会被执行

即使redis事务队列中的某个命令在执行期间出现了错误，整个事务也会继续执行下去

Redis为什么不支持事务？

Redis作者认为，Redis事务的执行时错误通常都是编程错误产生的，这种错误通常只会出现在开发环境中，很少会在实际的生产环境中出现，所以他认为没有必要为Redis开发事务回滚功能。

一致性

如果数据库在执行事务之前是一致的，那么在事务执行之后，无论事务是否成功，数据库也应该仍然是一致的。

“一致”指的是数据符合数据库本身的定义和要求，没有包含非法或者无效的错误数据

Redis事务可能出错的地方，如何妥善地处理这些错误，从而确保事务的一致性的？

入队错误

如果一个事务入队命令的过程中，出现了命令不存在，或者命令的格式不正确等情况，那么Redis将拒绝执行这个事务

因为服务器会拒绝执行入队过程中出现错误的事务，所以Redis事务的一致性不会被带由入队错误的事务影响

执行错误

执行过程中发生的错误都是一些不能在入队时被服务器发现的错误，这些错误只会在命令实际执行时触发，即使触发了，也不会影响事务剩下的命令

因为在事务的执行过程中，出错的命令会被服务器识别出来，进行相应的错误处理， 所以这些出错命令不会对服务器数据库做任何修改，也不会对事务的一致性产生任何影响。

服务器停机

如果Redis服务器在执行事务的过程中停机，那么根据服务器所使用的持久化模式：

如果服务器运行在无持久化的内存模式下，那么重启之后的数据库将是空白的，因为数据总是一致的

如果服务器运行在RDB或AOF模式下，那么在事务中途停机不会导致不一致性，因为服务器可以根据RDB或AOF文件恢复数据，将数据库还原到一个一致的状态。如果找不到RDB或AOF文件，那么重启之后的数据库是空白的，空白数据库是一致的

隔离性

即使数据中有多个事务并发的执行，各个事务之间也不会相互影响，并且在并发状态下执行的事务和串行执行的事务产生的结果完全相同。

因为Redis使用单线程的方式来执行事务（事务队列中的命令），并且服务器保证，执行事务期间不会对事务进行中断， 因此，Redis的事务总是以串行的方式运行的，并且事务也总是具有隔离性的

耐久性

当一个事务执行完毕后，执行这个事务所得的结果已经被保存到永久性存储介质（硬盘）里了， 即使服务器在事务执行完毕之后停机，执行事务所得的结果也不会丢失。

Redis事务的耐久性由Redis所使用的持久化模式所决定

当服务器在无持久化的内存模式下运作、RDB持久化模式运作、AOF持久化模式运作，都不会保证事务的耐久性

当服务器运行在AOF持久化模式下，并且 appendfsync 选项的值为always时，事务具有耐久性

no-appendfsync-on-rewrite 配置选项对耐久性的影响

no-appendfsync-on-rewrite 处于打开状态，并且 appendfsync always/everysec，这种情况下，事务不具有耐久性

因为当 no-appendfsync-on-rewrite 处于打开状态，在执行BGSAVE或BGREWRITEAOF命令期间， 服务器会暂时停止对AOF文件进行同步，从而尽可能地减少I/O阻塞。

在一个事务的最后加上SAVE命令总是可以保证事务的耐久性，但这种做法的效率太低，不具有实用性

Lua脚本

SCRIPT FLUSH、SCRIPT EXISTS、SCRIPT LOAD、SCRIPT KILL命令

Redis客户端可以使用LUA脚本，直接在服务器端原子地执行多个Redis命令

与LUA环境进行协作的两个组件，分别是负责执行LUA脚本中包含的Redis命令的伪客户端，以及负责保存传入服务器的LUA脚本的脚本字典。

了解伪客户端可以知道脚本中的Redis命令在执行时，服务器与LUA环境的交互过程

了解脚本字典有助于理解SCRIPT EXISTS命令和脚本复制功能的实现原理

创建Lua环境

Redis在服务器内嵌了一个Lua环境，并对这个Lua环境进行了一些列修改

创建Lua环境

服务器调用 Lua 的 C API 函数 lua_open，创建一个Lua环境

载入函数库

基础库：包含Lua的核心函数，比如assert、error、pairs、pcall等

表格库：处理表格的通用函数，比如table、concat等

字符串库：处理字符串函数的通用库

数学库：标准C语言数据库的接口

调试库：对程序进行调试所需的函数

Lua CJSON库：处理UTF-8编码的JSON格式

Struct库：在Lua值和C结构之间进行转换

Lua cmsgpack库：处理MessagePack格式的数据

创建Redis全局表格

服务器在Lua环境中创建一个redis表格，并将他设置为全局变量。redis表格包含以下函数：

执行Redis命令的redis.call和redis.pcall函数

用于记录Redis日志（log）的redis.log函数，以及相应的日志级别常量：redis.LOG_DEBUG、redis.LOG_VERBOSE、 redis.LOG_NOTICE、redis.LOG_WARNING

用于计算SHA1校验和的redis.sha1hex函数

返回错误信息的redis.error_replay函数和redis.status_replay函数

使用Redis自制的随机函数来替换Lua原有的随机函数

Redis为了保证相同的脚本可以在不同的机器上产生相同的结果，Redis要求传入服务器的Lua脚本，以及Lua环境中的所有函数，都必须是无副作用的纯函数。

防止带有副作用的函数令脚本产生不一致的数据

创建排序辅助函数

对于Lua脚本来说，另一个可能产生不一致数据的地方是那些带有不确定性质的命令。 集合元素可能即使两个集合的元素完全相同，但输出结果可能并不相同。

为了消除命令带来的不确定性，服务器会为Lua环境创建一个排序辅助函数__redis__compare_helper，当Lua脚本执行完一个带有不确定的命令之后，程序会使__redis__compare_helper作为对比函数，自动调用table.sort函数对命令的返回值做一次排序，保证相同的数据集总是产生相同的输出。

创建redis.pcall函数的错误报告辅助函数

服务器为Lua环境创建一个__redis++err+handler的错误处理函数，当脚本调用redis.pcall函数执行Redis命令，并且被执行的命令出现错误时，此函数就会打印出错代码和发生错误的行数。

保护Lua的全局环境

服务器将对Lua环境中的全局环境进行保护，确保传入服务器的脚本不会因为忘记使用local关键字而将额外的全局变量添加到Lua环境里面

因为全局变量保护的原因，当一个脚本试图创建一个全局变量时，服务器将报告一个错误

试图获取一个不存在的全局变量也会引发一个错误

注意：Redis并未禁止用户修改已存在的全局变量，所以在执行Lua脚本的时候，必须非常小心，以免错误地修改了已存在的全局变量

将lua环境保存到服务器状态的lua属性里面

Lua环境协作组件

Redis服务器创建了两个用于与Lua环境进行协作的组件，负责执行Lua脚本中的Redis命令的伪客户端，用于保存Lua脚本的lua_scripts字典

伪客户端

Lua脚本执行Redis命令时的通信步骤：

Lua环境将redis.call函数想要执行的Redis命令传送给伪客户端；

伪客户端将命令传给命令执行器执行；

命令执行器将返回命令的执行结果给到伪客户端

伪客户端将命令结果传回给Lua环境

lua_scripts字典

Lua 脚本有两个作用：一是实现SCRIPT EXISTS命令；另一个是实现脚本复制功能

字典的键：某个Lua脚本的SHA1校验和（checksum），字典的值：SHA1校验和对应的Lua脚本

Redis服务器会将所有被EVAL命令执行过的Lua脚本，以及所有被SCRIPT LOAD命令在如果Lua脚本都保存到 lua_scripts字典里面

EVAL命令的实现

定义脚本语言

当客户端向服务器发送EVAL命令，服务器首先在Lua环境中，为传入的脚本定义一个与这个脚本相对应的Lua函数，Lua函数的名字由f_前缀加脚本的SHA1校验和组成，函数的体则是脚本本身。

如果某个脚本所对应的函数在Lua环境中被定义过至少一次，那么只要记住这个脚本的SHA1校验和，服务器就可以在不知道脚本本身的情况下，直接通过调用Lua函数来执行脚本，这是EVALSHA命令的实现原理。

将脚本保存到 lua_scripts 字典

键：Lua脚本的SHA1校验和

值：Lua脚本本身

执行脚本函数

在为脚本定义函数，并且将脚本保存到 lua_scripts 字典之后，服务器还需要设置一些钩子、传入参数之类的准备工作，才能执行脚本，步骤如下：

将EVAL命令中传入的键名参数和脚本参数分别保存待KEYS数组和ARGV数组，然后将这两个数组作为全局变量传入到Lua环境里面

为Lua环境装载超时处理钩子（hook），它可以在脚本出现超时运行时，让客户端通过SCRIPT KILL命令停止脚本， 或者通过SHUTDOWN命令直接关闭服务器

执行脚本函数

移除之前装载的超时钩子

将执行脚本函数所得的结果保存到客户端状态的输出缓冲区里面，等待服务器将结果返回给客户端

对Lua环境执行垃圾回收操作

EVALSHA命令的实现

每一个被EVAL命令成功执行过的Lua脚本，在Lua环境里面都有一个与这个脚本相对应的Lua函数，函数名f_SHA1校验和。

只要脚本对应的函数曾经在Lua环境里面定义过，即使不知道脚本的本身内容，客户端也可以根据脚本的SHA1校验和来调用脚本对应的函数， 从而达到执行脚本的目的，这就是EVALSHA命令的实现原理。

脚本管理命令的实现

SCRIPT FLUSH

用于清楚服务器中所有和Lua脚本有关的信息，这个命令会释放并重建 lua_scripts 字典，关闭现有的 lua 环境并重新创建一个新的 Lua环境

SCRIPT EXISTS

根据输入的SHA1校验和，检查校验和对应的脚本是否存在于服务器中

通过检查给定的校验和是否存在于 lua_script 字典来实现的

SCRIPT LOAD

和EVAL命令执行脚本时所作的前两步完全一样

首先在Lua环境中为脚本创建相对应的函数，然后将脚本保存到 lua_scripts 字典里

SCRIPT KILL

如果服务器设置了 lua-time-limit配置选项，那么在每次执行 Lua 脚本之前，服务器都会在 Lua 环境里面设置一个超时处理钩子（hook）

如果钩子发现脚本的运行时间已经超过了 lua-time-limit 设置的时长，钩子将会查看是否有 SCRIPT KILL命令或SHUTDOWN命令到达服务器

如果超时运行的脚本未执行任何写操作，客户端可以通过SCRIPT KILL命令来指示服务器停止执行这个脚本，并向执行该脚本的客户端发送一个错误回复。处理完该命令，服务器可以继续运行。

如果脚本已经执行过写入操作，客户端只能使用 SHUTDOWN nosave 命令来停止服务器，防止不合法的数据被写入数据库中

脚本复制

和其他普通Redis命令一样，当服务器运行在复制模式之下时，具有写性质的脚本命令也会被复制到从服务器

复制EVAL、SCRIPT FLUSH、SCRIPT LOAD命令

当主服务器执行完以上三个命令之后，主服务器会直接将被执行的命令传播给所有的从服务器

复制 EVALSHA 命令

对于一个在主服务器被成功执行的 EVALSHA 命令来说，相同的 EVALSHA 命令在从服务器执行时可能会出现脚本未找到错误

为了防止以上假设的情况出现，Redis要求主服务器在传播 EVALSHA 命令的时候，必须确保 EVALSHA 命令要执行的脚本已经被所有从服务器载入过，如果不不能保证，那么主服务器将 EVALSHA 命令转换成一个等价的 EVAL 命令，然后通过传播 EVAL 命令来代替 EVALSHA 命令，以下是传播步骤：

判断传播 EVALSHA 命令是否安全的方法

主服务器使用服务器状态的repl_scriptcache_dict 字典记录自己已经将哪些脚本传播给了所有从服务器

清空 repl_scriptcache_dict字典

EVALSHA 命令转换成 EVAL 命令的方法

传播 EVALSHA 命令的方法

排序

二进制位数组

慢查询日志

Redis的慢查询日志功能用于记录执行时间超过给定时长的命令请求，用户可以通过这个功能产生的日志来监视和优化查询速度

slowlog-log-slower-than：指定执行时间超过多少微秒的命令请求会被记录到日志上； slowlog-max-len：指定服务器最多保存多少条慢查询日志（先进先出）

慢查询日志的保存

slowlog链表使用头插法来添加日志

SLOWLOG GET：查看服务器保存的慢查询日志

日志的唯一标识

命令执行时的UNIX时间戳

命令执行的时长，以微秒计算

命令以及命令参数

慢查询日志的阅览和删除

SLOWLOG LEN：查看日志数量（链表长度）

SLOWLOG REST：清除所有慢查询日志

添加新日志

每次执行命令的之前和之后，程序都会记录微秒格式的当前UNIX时间戳，用来记录执行命令前后的时间

检查是否需要创建新的慢查询日志，调用slowlogPushEntryIfNeeded函数

slowlogPushEntryIfNeeded函数会检查命令的执行时长是否超过xx选项设置的值，检查慢查询日志的长度是否超过xx选项设置的值

监视器

执行MONITOR命令，客户端可以将自己变为一个监视器，实时地接收并打印出服务器当前处理的命令请求的相关信息

成为监视器

打开客户端的监视器标志

将客户端添加到服务器状态的monitors链表的末尾

向客户端返回OK

<div>向监视器发送命令请求</div>

服务器在每次处理命令请求之前，都会调用replicationFeedMonitors函数，由这个函数将被处理的命令请求的相关信息发送给各个监视器

数据结构与对象

数据库的键总是一个字符串对象；而数据库键的值则可以是字符串字符串、列表、哈希、集合、有序集合对象

redis.c/main表示redis.c文件中的main函数；redis.c/redisDb表示redis.h中的redisDb结构

<unistd.h>/write表示unistd.h头文件的write函数；

redisDb.id表示redisDb结构的id属性。

简单动态字符串

SDS定义：简单动态字符串的抽象类型 每个sds.h/sdshdr结构：int len; int free; char buf[]三个属性

RPUSH fruits "apple" "banana" "cherry"

键值对的键：对象的底层是保存了一个字符串对象 键值对的值：列表对象的底层包含了三个字符串对象，分别有三个SDS实现

SDS 还被用作缓冲区：AOF模块中的AOF缓冲区

SDS 与 C 字符串的区别

STRLEN: 常数复杂度获取字符串长度（C字符串 O(N) ）

SDS 的空间分配策略 杜绝了缓冲区溢出（C字符串会出现缓冲区溢出）

SDS 实现了 空间预分配 和 惰性空间释放 两种优化策略。

空间预分配：用于优化SDS的字符串增长操作

如果SDS长度小于1MB，那么程序分配和len属性同样大小的未使用空间； 如果SDS长度大于1MB，那么程序分配1MB的未使用空间。

惰性空间释放：用于优化SDS的字符串缩短操作

如果SDS长度要缩短，程序不会使用内存分配来回收多出来的字节，而是使用free属性将这些字节记录起来，以后使用。

SDS的API都是 二进制安全的，可以保存 任意格式的二进制数据,  （SDS 保存的是二进制数据, 而不是字符数组）

兼容部分C字符串函数

链表

那些地方使用到了链表？列表键的底层、发布与订阅、慢查询、监视器等

每个链表由一个listNode结构表示，并且Redis的链表实现是双端链表

listNode  *head；头节点

listNode *tail；尾指针

unsigned long len；链表长度

void *（*dup）（void *ptr）：复制链表节点所保存的值；

void *（*free）（void *ptr）：释放链表节点保存的值

int （*match）（void *ptr，void *key）：对比链表节点所保存的值和另一个输入值是否相等

字典

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

哈希表节点: 键+值+指针

哈希算法

Redis使用MurmurHash2算法计算键的哈希值, 即使输入的键是有规律的,算法仍能给出一个很好的随机分布性.

index = hash & dict -> ht[0].sizemask = 8 & 3 == 0

http://code.google.com/p/smhasher

解决键冲突

头插法: 因为dicEntry节点组成的链表没有指向链表表尾的指针, 所以为了速度考虑, 新加的节点添加到链表的表头位置.

refresh 重新散列

为字典的 ht[1] 哈希表分配空间

如果执行的是 扩展操作, 那么 ht[1] 的大小为第一个 大于等于ht[0].used*2的2的n次幂

如果执行的是 收缩操作, 那么ht[1] 的大小为第一个 大于等于 ht[0].used 的2的n次幂

将保存在ht[0] 中的所有键值对refresh 到 ht[1] 上面: 重新计算哈希值和索引值

ht[0] 迁移到 ht[1] 后, 释放ht[0], 将 ht[1] 设置为 ht[0], 并在ht[1]新创建一个空白哈希表, 为下一次refresh准备.

扩展操作

服务器没有执行BGSAVE命令或者BGREWRITEAOF命令, 并且哈希表的扩展因子大于1

服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令, 并且哈希表的负载因子大于5

执行BGSABE或BGREWRITEAOF过程中, Redis需要创建进程的子进程, 而大多数操作系统采用写时复制技术来优化子进程的使用效率

尽量避免在子进程存在期间进行哈希表扩展操作, 可以避免不必要的内存写入操作, 最大限度地节约内存.

哈希表的负载因子小于0.1时, 程序自动开始对哈希表执行收缩操作.

渐进式rehash

在字典中维持了一个索引计数器变量 rehashidx, 并将它的值设置为 0, 表示rehash工作正式开始.

rehash期间, 每次对字典执行添加/删除/查找或者更新操作时, 会顺带将 ht[0] 哈希表在rehashidx索引上的所有键值对rehash 到 ht[1], 当rehash完成后, 程序将 rehashidx 属性值加1.

rehash完成后, rehashidx设置为-1

渐进式rehash执行期间的哈希表操作

在渐进式rehash进程期间, 字段的删除/查找/更新等操作会在两个哈希表上进行.

例如: 要在字典里面查找一个键的话, 程序会现在ht[0]里面查找, 如果没有找到的话, 就会继续在ht[1]查找.

跳跃表

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

跳跃表

redis.h/zskiplist{header；tail；level；length}：保存跳跃表节点的信息，比如节点的数量，以及指向表头节点和表尾节点的指针

redis.h/zskipNode{zskiplistNode *backward；double score；robj *obj；zskiplistLevel{zskiplistNode *forward；int span}level[]；}：跳跃表节点，

跳跃表节点

层

跳跃表节点的level数据可以包含多个元素，每个元素都包含一个指向其他节点的指针

每次创建一个新跳跃表节点的时候，程序都会根据幂次定律（越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的高度。

前进指针

每一层都有一个指向表尾方向的前进指针

用于记录两个节点之间的距离

后退指针

用于从表尾向表头方向访问节点

分值和成员

节点的分值是一个double类型的浮点数，跳跃表中的所有分值都是按从小到大排序的

节点的成员对象是一个指针，他指向一个字符串对象，而字符串对象则保存着一个SDS值

整数集合

整数集合:  inset.h/inset结构

编码方式: uint32_t encoding; 

集合包含的元素数量: uint32_t length; 

保存元素的数组: int8_t contents[];

按值大小排序, 具体存储数字的位数取决于 encoding

有序 / 无重复数组

整数升级

每当一个新元素添加到整数集合, 并且新元素的类型比整数集合所有的元素都要长, 整数集合就需要先进行升级.

例如: 数组有3个16位元素, 16*3 = 48位  插入65535后, 需要32 * 4 = 128位孔金, 最后从后往前分配元素.

升级的好处

提升灵活性

C语言是静态类型语言, 为了避免错误, 不会将两种不同类型的值放在同一个数据结构里面. INT16 类型的数组只存放 INT16类型的值.

尽可能节约内存

降级

整数集合只升级不降级

压缩列表

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

每个压缩列表可以包含任意多个节点, 每个节点可保存一个字节数组或一个整数值

zlbytes -> zltail -> zllen -> entry1 -> entry2 -> entry3 ... ->entryN -> zlend

内存字节数-> 压缩表起始位置和尾节点的距离->节点个数->节点1 -> 节点2 ...->标记压缩列表末端

添加或删除节点, 可能会发生连锁更新操作, 但几率不高.

对象

对象的优点

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

字符串对象、列表对象、哈希对象、集合对象、有序集合对象

Redis可以在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令。

Redis对象实现了 基于引用计数器技术的内存回收机制

Redis通过引用计数技术实现了对象共享机制，让多个数据库共享同一个对象

Redis对象带有访问时间，可以用于计算空转时长，在服务器设置了maxmemory功能的情况下，空转时长较大的键可能会被服务器删除。

对象的类型和编码

键（字符串对象），值（列表对象）： type 命令返回键对应值的类型

查看一个数据库键的值对象的编码：Object encoding key

字符串对象

字符串对象的编码可以是 int、raw、embstr

OBJECT ENCODING key

整数 int

字符串长度 <= 39字节：embstr

字符串长度 > 39字节：raw

int、embstr、raw区别

embstr 调用一次内存分配，包含redisObject 和 sdshdr，raw 调用两次内存分配，包括redisObject和sdshdr

可以用 long double 类型表示的浮点数在Redis是作为字符串值来保存的。

INCRBYFLOAT key 2.0 : 程序会先取出字符串，转为浮点数，自增2.0，再转回浮点数

列表对象

列表对象的编码可以是ziplist 和 linkedlist

ziplist

redisObject： type REDIS_LIST；

encoding REDIS_ENCODING_CIPLIST；

*ptr

zlbytes - zltail - zllen - 1 "three"  - 5 zlend

linkedlist

redisObject： type REDIS_LIST；

encoding REDIS_ENCODING_CIPLIST；

*ptr

StringObject：1、StringObject："three"；StringObject：5

每个StringObject都是SDS的简化

ziplist 条件

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

列表对象保存的元素数量小于512个

哈希对象

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

ziplist 压缩列表

保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点灾后；

先添加到哈希对象的键值对会被放在压缩列表的表头方向，而后来添加到哈希对象中的键值对会被放在压缩列表的表尾

hashtable

redisObject.*ptr -> {dict.k1->v1, dict.k2->v2...dict.kn->vn}

ziplist条件

哈希对象保存的所有键值对的键和值的字符串长度都小于64字节

哈希对象保存的键值对数量小于512个

配置文件可修改

集合对象

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

inset条件

集合对象保存的所有元素都是整数值

集合对象保存的元素数量不超过512个

有序对象

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

zset

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

zset结构包含一个字典和一个跳跃表

zset：zskiplist *zsl；dict *dict；

压缩列表

字典

为什么Redis使用跳跃表和字典两种数据结构来实现有序集合？

跳跃表和字典这两种数据结构都会通过指针来共享相同元素的成员和分值，所以不会产生任何重复成员或者分值，也不会浪费额外的内存

只使用字典保存集合元素。但在比如ZANK、ZRANGE等命令，程序需要对字典保存的所有元素进行排序。 需要额外的时间复杂度：O(nlogN)；空间复杂度：O(N)

只使用跳跃表保存集合元素，查找的时间复杂度O(1)上升到O(logN)

ziplist编码条件

有序集合保存的元素数量小于128个

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

类型检查与命令多态

类型检查

在执行一个类型特定命令之前，服务器会先检查输入数据库键的值对象是否为执行命令所需的类型，如果是的话，服务器就对键执行命令

检查redisObject对象结构的trpe属性值

否则，返回一个错误

命令多态

服务器除了要保证执行命令的列表键之外，还需要根据键的值对象所使用的编码来选择正确的LLEN命令

DEL、EXPIRE等和LLEN区别

前者是基于类型的多态——一个命令可以同时用于处理多种不同类型的键

后者是基于编码的多态——一个命令可以同时用于处理多种不同的编码

对象机制

内存回收

因为C语言不具备自动内存回收功能，所以Redis在自己的对象系统中构建了一个用技术技术实现的内存回收机制

每个对象的引用计数由redisObject结构的refcount属性记录

创建一个新对象时，引用技术的值初始化为1； 当对象的引用计数器值变为0时，对象所占用的内存会被释放；

redis对象之间没有深层次的嵌套，因此也就不存在循环引用

在Redis1.0之前，redis只有使用引用计数这一种回收机制，后续便使用了LRU算法

redis的8种回收策略

volatile-ttl：从已设置过期时间的数据集中挑选将要过期的数据淘汰；

volatile-random：从已设置过期时间的数据集中任意挑选数据淘汰；

volatile-lru 从设置了过期时间的数据中根据 LRU 算法挑选数据淘汰

volatile-lfu 从设置了过期时间的数据中根据 LFU 算法挑选数据淘汰（4.0及以上版本可用）

allkeys-lru：从数据集中挑选最近最早使用的数据淘汰；

allkeys-random：从数据集中任意选择数据淘汰；

allkeys-lfu 从所有数据中根据 LFU 算法挑选数据淘汰（4.0及以上版本可用）

noeviction 默认策略，不淘汰数据；大部分写命令都将返回错误（DEL等少数除外）

LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面! LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页!

对象共享

键A和键B可以共享一个相同类型的值对象

将数据库键的值指针指向一个现有对象，并将被共享值对象的引用计数器+1

优点：节省内存

为什么Redis不共享包含字符串的对象？

如果共享对象保存的是整数，验证操作的时间复杂度是O(1)

如果共享对象保存的是字符串对象，验证操作的时间复杂度是O(N)

如果共享对象保存的是多个值的对象，验证操作的时间复杂度是O(N²)

受到CPU的限制，Redis只对包含整数值的字符串对象进行共享。

对象的空转时长

redisObject除了type、encoding、ptr、refcount、lru属性，lru记录了对象最后一次被命令程序访问的时间

Object IDLETIME key

访问键的之后不会更改lru属性值

如果服务器打开maxmemory选项，并且服务器用于内存回收算法为volatile-lru或者allkeys-lru，那么当服务器占用的内存超过了maxmemory选择，服务器会优先删除空转时长较高的那部分键

maxmemory和maxmemory-policy

单机数据库的实现

数据库

服务器中的数据库

redis.h/redisServer结构

redisDb *db； //一个数组，保存着服务器中的所有数据库  

服务器的数据库数量  redisDb *dbnum；

SELECT命令：redis.h/redisClient结构：redisDb *db//记录客户端正在使用的数据库

redisClient结构：

dict *dict；//数据库键空间，保存着数据库中的所有键值对

*expire； //保存键的过期时间

数据库的键空间

数据库的键空间是一个字典，实际上都是通过对键空间字典进行操作来实现的

读写键空间时的维护操作

读取键，服务器会根据键是否存在来更新服务器的键空间命中次数或键（hit）空间不命中（miss）次数

INFO stats 命令：keyspace_hits、keyspace_misses属性

缓存命中率 = keyspace_hits / (keyspace_hits + keyspace_misses)

读取键，服务器会更新键的LRU时间，这个值可以用于计算键的闲置时间

如果服务器发现一个键已经过期，那么会先先删除这个键，然后做其他操作。

WATCH命令监视了某个键，那么服务器在对被监视的键进行修改之后，会将这个键标记为脏（dirty）

服务器每次修改一个键之后，都会对脏（dirty）键计数器的值增1，这个计数器会触发服务器的持久化以及复制操作。

设置键的生存时间或过期时间

设置键过期时间的命令：EXPIRE、PEXPIRE、EXPIREAT、PEXPIREAT命令

redisDb结构的dict *expires；过期字典

PERSIST 移除过期时间；TTL、PTTL 查看键的过期时间

Redis的过期时间严格依赖于系统时间

过期键删除策略

定时删除

设置键过期时间的同时，创建一个定时器（timer）

缺点：

占用太多CPU时间，影响服务器的响应时间和吞吐量

如果有大量的命令请求服务器，并且服务器不缺少内存，那么服务器优先将CPU时间用在处理客户端的命令请求上。

惰性删除

每次从键空间中获取键时，检查键是否过期

缺点：

浪费太多内存，有内存泄漏风险

无用的垃圾数据占用了大量的内存

比如日志，在某个时间点之后，对它的访问就大大减少，但这些键仍然保存在数据库中

定期删除

每个一段时间执行一次删除过期键操作，通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响

难点在于确定删除操作执行的时长和频率

redis是否存在内存泄露？

YES

过期键的删除策略

惰性删除：db.c/expireIfNeeded函数

定期删除：redis.c/activeExpireCycle函数

函数每次运行，都从一定数量的数据库中取出一定数量的随机键进行检查，并删除其中的过期键

AOF、RDB和复制功能对过期键的处理

RDB文件写入和载入

SAVE和BGSAVE命令创建一个新的RDB文件时，已过期的键不会被保存到RDB文件中

如果服务器以主服务器模式运行，过期键不会被载入到RDB文件

如果服务器以从服务器运行，所有键都会被载入RDB文件

因为主从服务器在进行数据库同步时，从服务器的数据库会被清空。

AOF文件的写入和重写

执行BGREWRITEAOF命令不会写入AOF文件过期键，当过期键被删除，会在AOF文件中追加一条DEL命令

已过期的键不会被重写到新的AOF文件

主从复制

服务器的过期删除策略由主服务器控制

从服务器在执行客户端发送的读命令时，即使碰到过期键也不会删除

从服务器只有接收到主服务器的DEL命令后，才会删除过期键

主从一致性：通过主服务器来控制从服务器统一地删除过期键

数据库通知

RDB持久化

RDB文件的创建与载入

SAVE会阻塞Redis服务器进程，直到RDB文件创建完毕为止

BGSAVE派生一个子进程，然后由子进程负责创建RDB文件，服务器进程继续处理命令请求

只有在AOF持久化功能关闭时，服务器才会使用RDB文件来还原数据库状态。

BGSAVE和SAVE命令不能同时执行，避免父子线程同时调用rdbSave函数

BGSAVE和BGSAVE命令不能同时执行

BGSAVE和BGREWRITEAOF命令不能同时执行，出于性能考虑（并且这两个子进程都同时执行大量的磁盘写入操作）

自动间隔性保存

save 900 1 save 300 10 save 60 10000

满足以上任一条件，服务器执行BGSAVE命令

dirty计数器：记录距离上一次成功执行SAVE或BGSAVE命令后，服务器对数据库状态

lastsave属性：记录服务器上一次成功执行SAVE或BGSAVE命令的时间

检查保存条件是否满足

serverCron函数默认每隔100毫秒就会执行一次

检查save选项所设置的保存条件是否已经满足，如果满足，执行BGSAVE

RDB文件结构

REDIS：检查载入的文件是否是rdb文件

db_version：记录RDB文件的版本号

database：0个或多个数据库，以及数据库中的键值对数据

EOF：常量标志RDB文件正文内容的结束，（读到这一位，标志数据库的所有键值对已经载入完毕）

check_sum：保存着一个校验和，将载入数据所计算出的校验和与check_sum所记录的校验和进行对，检查RDB文件是否损坏

分析RDB文件

二进制文件

od -cx dump.rdb

redis-check-dump：文件检查工具

AOF文件持久化

RDB通过保存数据库中的键值对来记录数据库状态的不同，AOF持久化是通过保存Redis服务器所执行的写命令来记录数据库状态的

被写入AOF文件的所有命令都是以Redis的命令请求协议格式保存的，因为Redis的命令请求协议是纯文本的

AOF持久化的实现

AOF持久化功能的实现可以分为追加（append） -> 文件写入 -> 文件同步（sync）

命令追加

写命令，以协议格式将被执行的写命令追加得到aof_buf缓冲区的末尾。

redisServer结构：AOF缓冲区 sds aof_buf；

AOF文件的写入与同步

Redis的服务器进程就是一个事件循环（loop）

文件事件：接收客户端的命令请求，发送命令回复

时间事件：负责执行像serverCron这样的函数

服务器每次在结束一个事件循环之前，它都会调用flushAppendOnlyFile函数

flushAppendOnlyFile函数行为由appendfsync决定

appendfsync  always appendfsync  everysec appendfsync  no

将aof_buf缓冲区中的所有内容写入并同步到AOF文件， 最多丢失一个事件循环中产生的命令

每秒同步，并且这个同步操作时由一个线程专门负责的 最多丢失一秒的命令数据

同步取决于操作系统 丢失上次同步AOF文件之后的所有写命令数据

AOF文件的载入与数据还原

服务器启动载入程序，会创建一个 不带网络连接的伪客户端，效果和客户端一样

因为Redis的命令只能在客户端的上下文执行

AOF重写

Redis将生成新AOF文件替换旧AOF文件的功能命名为"AOF文件重写"， 但AOF文件重写并不会对现有的AOF文件进行任何读取、分析或写入操作， 这个功能是通过 读取服务器当前数据的状态 来实现的。

为了避免在执行命令时造成客户端输入缓冲区溢出，在处理列表、集合、哈希表、有序集合时，会先检查所包含的元素数量， 如果元素数量超过了redis.h/REDIS_AOF_REWRITE_ITEMS_PER_CMD（64）时，重写程序会使用多条命令来记录键的值。

aof_rewrite函数

AOF后台重写

AOF重写程序aof_rewrite函数会进行大量写操作，调用这个函数的线程将被长时间阻塞。所以无法处理客户端发来的命令请求。

子进程进行AOF重写，服务器进程可以继续处理命令请求。

子进程带有服务器进程的数据副本，使用子进程而不是线程，可以在避免使用锁的情况下，保证数据的安全性

问题：子进程在进行AOF重写期间，服务器进程还需要继续处理命令请求，新的命令可能会对现有的数据库状态进行修改， 从而 使得服务器当前的数据库状态和重写后的AOF文件所保存的数据库状态不一致。

为了解决以上问题，Redis服务器设置了一个AOF重写缓冲区

子进程执行AOF重写期间，服务器进程要执行三个工作：

1.执行客户端命令；2.将执行后的写命令追加到AOF缓冲区；3.将执行后的写命令追加到AOF重写缓冲区；

当子进程完成AOF重写工作之后，向父进程发送一个信号，父进程在到该信号之后，调用信号处理函数。

将AOF重写缓冲区中的所有内容写入到新的AOF文件中。

对新的AOF文件进行改名，原子地覆盖现有的AOF文件，完成文件替换。

整个过程，只有信号处理函数会对父进程造成阻塞

事件

Redis服务器是一个事件驱动程序

文件事件

Redis服务器通过套接字与客户端进行连接，而文件事件就是服务器对套接字操作的抽象。

Redis基于Reactor模式开发了自己的网络事件处理器

文件事件处理器使用I/O多路复用程序来监听多个套接字，并根据套接字目前执行的任务来为套接字关联不同的事件处理器

当被监听的套接字准备执行连接应答（accept）、read、write、close时，与操作相对应的文件事件就会产生，调用套接字关联的事件处理器处理这些事件

文件事件处理器

套接字

套接字(Socket)，就是对网络中不同主机上的应用进程之间进行双向通信的端点的抽象。一个套接字就是网络上进程通信的一端，提供了应用层进程利用网络协议交换数据的机制。

如果一个套接字产生两个套接字，读和写，那么服务器将先读套接字，后写套接字

I/O多路复用程序

I/O多路复用程序通过队列向文件事件分派器传送套接字。

Redis的I/O多路复用程序的所有功能都是通过包装常见的select、epoll、evport和kqueue这些I/O多路复用函数库来实现的

I/O多路复用程序的底层实现是可以互换的，程序会在编译时选择系统中性能最高的I/O多路复用函数库来作为Redis的I/O多路复用程序的底层实现。

文件事件分派器（dispatcher）

事件处理器

本质是函数

连接应答处理器

命令请求处理器

命令回复处理器

一次完整的客户端与服务器连接事件示例

时间事件

Redis服务器中的一些操作需要在给定的时间点执行，而时间事件就是服务器对这类定时操作的抽象。

定时事件：让一段程序在指定的时间之后再执行一次。

周期性事件：让一段程序每隔指定时间就执行一次。

serverCron函数

更新服务器的各类统计信息，比如时间、内存占用、数据库占用情况等

清理数据库中的过期键值对

关闭和清理连接失败的客户端

尝试进行AOF或RDB持久化操作

如果服务器是主服务器，那么对从服务器进行定期同步

如果处理集群模式，对集群进行定期同步和连接测试

redis.conf/hz

客户端

输入缓冲区记录了客户端发送的命令请求，这个缓冲区的大小不能超过1GB

客户端有固定大小缓冲区和可变大小缓冲区，固定大小缓冲区的最大大小为16KB，而可变大小缓冲区的最大大小不能超过服务器设置的硬性限制值。

网络连接关闭、发送了不符合协议格式的命令请求、成为CLIENT KILL命令的目标、空转时间超时、输出缓冲区的大小超出限制，都会造成客户端被关闭。

服务器

serverCron函数默认每隔100毫秒执行一次，会更新服务器状态信息、处理服务器接收的SIGTREM信号，管理客户端资源和数据库状态，检查并执行持久化操作等。

服务器从启动到能够处理客户端的命令请求需要执行以下步骤：

初始化服务器状态

载入服务器配置

初始化服务器数据结构

还原数据库

执行事件循环

 Collect

Get Started

Redis设计与实现

 Collect

Get Started

基于redis实现验证码验证技术

 Collect

Get Started

Redis设计与实现

 Collect

Get Started

Redis思维导图





0 条评论

下一页