# 6.824
# CAP定理
CAP是指一致性(C)，可用性(A),分区容错性(P),在异步网络模型中，不存在一个系统可以同时满足上面三个属性。
如果需要保证一致性，那当出现网络分区时，就不能快速的响应客户端，不能满足高可用
如果需要保证可用性，那当出现网络分区时，只能查询到的可能不是最新的数据，就不能满足一致性
一致性：要么读到一个最新的数据，要么读取失败
可用性：任何客户端的请求都能在合理的响应时间内得到响应，不会返回失败
分区容错性：系统可以出现网络分区，仍然能够继续运行，不会完全失败
# Raft
# 1.Leader 选举
# 1.Leader 选举
每个节点启动后，初始都为 follower，会随机生成一个心跳超时时间，如果没有收到心跳则会开启一轮新的选举，成为 candidate 增加自己的任期，并投票给自己，然后发送投票请求给其他节点， 候选者如果总票数超过一半，则成为 leader，并立即发送心跳(为了防止此时有follower超时成为leader)和 "no-op 日志"，然后定期向其他节点发送心跳和日志。否则成为 follower
# 2.投票处理
candidate会发送投票请求给 follower 节点,follower 收到投票请求后，如果candidate的任期比自己小，则拒绝投票，如果自己在当前任期没有投票并且 candidate 的 日志至少和自己的日志 "一样新" (up to date)，就投票给它，否则拒绝投票
# 3.心跳处理
leader定期向follower发送心跳，follower收到心跳后，如果leader的任期比自己小，则拒绝该心跳，否则接收该心跳并同步任期和重置心跳超时时间
# 4.up to date 的解释
如果它的最后一个日志的任期比我大，那么它的日志一定比我新(对于一个leader，对于同一任期，同一索引，最多添加一个日志，并且不能改变它的位置?)
如果它的最后一个日志的任期和我一眼，并且最后一个日志的下标不小于我，那么它的日志至少跟我一样新
# 2.日志复制
# 1.日志复制
leader 需要定期将 follower 需要的日志复制到 follower 上，follower 收到后首先判断 leader 任期是否比自己小，如果是则拒绝该日志，否则通过比对该日志的前一个索引的任期是否相同，相同则将其日志复制下来，并判断 leader 是否存在自己已经复制了但未提交的日志，将其提交，否则找到该任期的第一个日志的索引将其返回，用于 "快速回退"。 leader 收到响应后，如果 follower 拒绝了该日志，则调整需要发给该 follower 的日志索引。如果 follower 接收了该日志，并更新该 follower 接收的最后一个日志的索引，然后尝试进行日志提交。
# 2.日志提交
当有日志复制成功后，会进行日志提交。会将过半节点已经接收了的和 leader 任期相同的("leader 提交原则")日志进行提交，并更新 leader 最后一个提交的日志索引。
# 3.日志应用
会有一个协程专门负责应用日志,定期判断是否有已提交但未应用的日志，如果有，则将其应用到状态机,当一个日志应用到状态机后，更新 leader 最后一个应用的日志索引。
# 3.快速回退
当发生日志复制失败时，如果每次只回退一个位置，效率太低，所以可以回退到冲突任期的第一个日志，因为如果当前任期的日志发生冲突，那么当前任期的日志都会发生冲突
# 4.leader 提交原则
leader 只能提交自己任期的日志，否则会出现提交后的日志被覆盖的情况,因为当前 leader 不知道是否会存在比该日志任期更大的 follower 成为 leader 并将其覆盖，如果此时提交了该任期的日志，可能导致比该日志任期更大的 follower 成为 leader 后将其覆盖并提交
# 5.日志匹配原则
1.对于不同的日志中的两个条目的任期相同，索引相同，则存储的命令一定相同(因为每个leader只有一个任期，一个任期只能在相同索引添加一个日志) 2.对于不同的日志中两个条目的任期相同，索引相同，则之前的日志条目一定相同(因为日志复制时保证了只有前一个日志相同，才会将当前日志复制过去)
# 6.no-op日志
因为 leader 只能提交当前任期的日志，如果没有新的日志的到来，可能导致之前任期的日志一直不能被提交。所以当成为 leader 后需要立马发送一个 no-op日志(只有索引和任期,command未空)，以实现快速提交，响应客户端请求
# 3.持久化
因为节点宕机后所有信息都会丢失，所以需要将一些必要的信息进行持久化，如任期，日志文件，投票，快照对应的任期和索引。所以当这些信息发生变化时都需要进行持久化。 当节点宕机重启后，通过读取持久化信息以快速恢复到宕机前的状态
# 4.日志压缩
# 1.日志压缩
当日志达到一定大小后，会调用快照函数，然后将已经快照的日志删除，保留暂未被快照的日志 当进行日志复制时发现 follower 需要的日志已经被快照时，需要将自己的快照发送给 follower
# 2.安装快照
当收到 leader 的快照后，如果 leader 的任期比自己小，则拒绝该快照，如果该快照的最后一个索引不大于 follower 的最后一个提交的日志索引，则不需要安装。否则将当前日志中被快照的日志全部删除，并更新最后一个提交的日志索引
# KVServer
# 1.客户端：
一开始客户端因为不知道leader是谁，会向每一个节点发起请求，当请求成功后，会记录leader的id,以便下次请求的时候可以直接请求leader。对于rpc调用失败会直接进行重试，对于请求超时，可能是leader发生变化，又需要轮询每个节点。
# 2.服务端：
# 1.命令处理
对于GET命令，如果发现该请求的版本号是该客户端的旧的版本号，则直接从状态机中查询并返回。否则将日志写入 Raft，等待接收结果并设置计时器，超时后直接返回超时。
对于PUT APPEND命令 如果该请求的版本号是该客户端的旧的版本号，则直接返回，否则将其写入日志 Raft，等待响应并设置计时器，超时后直接返回超时
# 2.执行命令：
从chan中读取命令：
如果是日志命令，则根据距离日志的类型进行执行，并更新该客户端对应的最新版本号和执行的最后一个日志的下标，并将响应通过chan发送出去
如果是快照命令，则说明是leader发来的快照，则将其进行安装，更新当前的状态机和客户端对应的最新版本号
# 3.快照:
后台协程负责检测日志的大小，达到一定大小后将快照发送给Raft
# 额外优化
# 1.read Index
在raft中，如果读请求必须写入raft日志，会造成响应速度太慢，因为我们必须试图绕过raft日志，来读取数据
- 如果直接从leader读取数据，leader可能包含之前任期未提交的数据或当前节点是旧leader，因为不能直接读取数据
- 如果直接从follower读取数据，因为follower的数据总是落后于leader的，所以可能读取到旧的数据
因此我们需要采用 read Index 机制
- 当一个节点成为 leader 时，需要提交一个空日志，从而限制快速提交。
- 当 leader 收到读请求时，首先记录此时的提交索引，然后发送心跳给其他节点，从而确认自己是否为新leader，如果大多数节点进行了确认，这等待状态机应用到时提交索引，然后进行查询，返回结果。
- 当 follower 收到读请求时，首先去向 leader 获取提交索引，然后等待 leader 进行处理，当 follower 状态机应用到提交索引时，进行查询，返回结果。
# 2.lease read
如果每次读请求都需要等待一次心跳共识，那么会导致读请求的响应速度太慢，因此我们可以采用 lease read 机制 leader 在发送一次心跳之后，计算出 lease 时间，为 发送心跳时间 + 选举超时时间， 在到 lease 时间之前，都是不可能出现新的 leader 的，因此在此期间的读请求不需要发送心跳共识。
# 3.PreVote
当网络发生分区时，对于少数节点的分区，因为不能选举出 leader 会导致任期不断增加，然后当网络分区结束时，会导致原来的 leader 变成 follower，然后重新进行一轮选举，因此这样效率太低，我们考虑采用 PreVote机制 当一个节点要成为 candidate 时，首先不增大任期，先进行一轮预选举，如果能够得到多半选票，则增大任期，开启正式选举，否则放弃该轮选举，继续等待。 当然，也会存在缺点，如果 leader 节点崩溃，会导致选举新的 leader 需要两轮选举
# 4.leaderShip Expiration
当网络出现分区时，对于少数节点的分区的 leader，因为无法将日志同步到多数节点，因此无法提交日志，然后持续接收请求，所以我们应该进行优化
- Leader 给每个节点加上一个超时标签
- 每次收到从节点对于心跳的回复时，更新标签
- 当一定时间未收到回复时，标记未断连
- 如果多数节点断连时，则直接阻塞请求
# shardctrler
与lab3类似, 实现Join，Move，Leave，Query操作即可 Join：添加一些副本，并要进行负载均衡 Move： 将某个分片分配给某个副本组 Leave： 移除一些副本组，并要进行负载均衡，并进行负载均衡 Query： 查询某个版本的配置信息
# ShardKV
# 1.执行命令
从 chan 取出命令
对于普通的命令，通过请求id进行去重，然后执行即可
对于配置更新命令，判断配置版本是否为当前配置的下一个版本，如果是这进行将分片的状态进行更新
对于插入分片命令，首先判断版本号是否匹配，然后将每一个处于Pulling状态的分片插入，并修改为 GCing 状态, 然后将每个客户端对应的请求id复制过来。
对于删除分片命令，首先判断版本号是否匹配，然后将每一个处于 BePulling 状态的分片删除，改成一个处于 Serving 状态的空分片。将每一个处于 GCing 状态的分片改为 Serving 状态
# 2.配置更新
后台协程定期检测分片状态，如果状态不为 Serving 则说明有任务需要处理，那就不能进行配置更新。如果都为 Service 则查询当前配置的下一个版本是否存在,存在则将配置更新命令写入到 Raft。
# 3.分片迁移
后台协程定期检测是否存在Pulling状态的分片，如果存在，则开启多个协程去通过RPC调用拉取每一个分片 副本收到拉取分片的请求时，首先判断如果需要拉取的数据的配置版本号比当前配置的版本号要大，则拒绝拉取。否则所需将分片的键值对和客户端对应的请求id复制过去
# 4.分片清理
后台协程定期检测是否存在GCing状态的分片，如果存在，则开启多个协程去通过RPC调用删除每一个分片 副本收到删除分片的请求时，首先判断如果需要拉取的数据的配置版本号比当前配置的版本号要大，则拒绝删除。否则将所需要删除的分片命令写入 Raft
# 5.分片状态
Serving 服务状态，如果该分片属于该副本组，则可以提供读写服务，否则不能提供读写服务，但不影响配置更新 Pulling 该分片在当前配置版本属于该副本组，暂不可提供读写服务，但是需要从上一个配置版本负责该分片的副本组将分片拉取过来 BePulling 该分片在当前配置版本不属于该副本组，不可提供读写服务，但是在上一个配置版本属于该副本组，正在等待被当前配置版本负责该分片的副本组拉取 GCing 该分片在当前配置版本属于该副本组，可以提供读写服务，但是需要将上一个配置版本负责该分片的副本组的分片删除
# Gossip协议
Gossip协议是一种允许在分布式系统中共享状态的去中心化通信协议，通过这种协议，我们可以将信息传播给网络或集群中的所有成员。
# gossip协议消息传播模式
# 1.反熵
熵是指节点指节点之间数据的混乱程度/差异性，反熵是指消除不同节点中数据的差异，提升节点间数据的相似度。 集群中的节点，每隔一段时间就随机选择某个其他节点然后通过互相交换自己的所有数据来消除两者指将的差异，实现数据的最终一致性。 但是在节点过多或者动态变化的场景，不太适合反熵
# 2.谣言传播
集群中的节点，每隔一段时间就随机选择某个其他节点然后通过交换自己新增的数据来实现数据共享
# 3.消息传播方式
推方式：就是将自己的所有副本数据，推给对方。 拉方式：就是拉取对方的所有副本数据。 推拉方式：就是同时修复自己副本和对方副本。