领导权禅让

有的时候leader必须下台，比如他可能出现重新启动，或者已经从集群中删除

在某些情况下，一台或多台服务器可能比其他的服务器更适合领导集群。比如数据中心中的服务器，用来减少客户端和领导者之间的延迟

过程如下

• 当前leader停止接受客户请求
• 当前leader完整更新目标服务器的日志以使其与自己的日志匹配
• 当前leader将timeoutNow请求发送到目标服务器，目标服务器将开始新的选举

集群成员更改

和论文中不同的是，这里的集群更改是一个更加简单的算法

核心思路就是禁止会导致多数成员不相交的成员更改。所以这种更改方法一次只能从集群中添加或者删除一个服务器

当领导者收到从当前配置（Cold）中添加或删除服务器的请求时，它将新配置（Cnew）作为一个条目添加到其日志中，并使用常规的 Raft 机制复制该条目。新配置一旦添加到服务器的日志中，就会在这个服务器上生效：Cnew 条目被复制到 Cnew 指定的服务器上，而大部分服务器的新配置生效被用于确定 Cnew 条目的提交。这意味着服务器不会等待配置条目被提交，并且每个服务器总是使用在其日志中找到的最新配置。

一旦提交了 Cnew 条目，配置更改就完成了。此时，领导者知道大多数的 Cnew 指定的服务器已经采用了 Cnew。它还知道，没有收到 Cnew 条目的任意服务器都不能再构成集群的大多数，没有收到 Cnew 的服务器也不能再当选为领导者。Cnew 的提交让三件事得以继续:

• 领导可以确认配置更改的成功完成。
• 如果配置更改删除了服务器，则可以关闭该服务器。
• 可以启动进一步的配置更改。在此之前，重叠的配置更改可能会降级为不安全的情况

但是由于我们是在接受到配置日志以后直接apply，所以这个日志是有可能被删除掉的，我们需要保存之前的日志来做恢复

在Raft中，我们是通过caller的配置来达成共识的

• server会接收来自leader的AppendEntries RPC，无论这个leader是不是在这个server的最新configuration中。
• server还允许投票给不属于服务器当前最新配置的candidate以保证集群可用。但是由于我们可以保证新旧成员的相交，所以这是安全的操作

所以服务器是直接处理RPC请求，而不需要查询他的配置（配置只在发起RPC时使用）

可用性

当服务器被添加到集群中的时候，他的日志可能需要相当长的一段时间才能赶上leader的log

在此期间集群容易出现不可用的状况，比如本来3台机器，可以容忍一个机器宕掉。现在新加入了一台机器，majority变成4台。然后原本的机器宕掉一台，而新的机器没有追上log。就出现了不可用的状态

追赶

添加一个新的阶段，新的服务器作为无投票权的成员加入集群。leader复制日志给他，但是他不计入majority。当新的服务器赶上了集群的其余部分，就可以按照之前的方法进行重新配置

我们需要让leader确定什么时候新的服务器已经赶上了进度从而可以继续进行配置修改。我们的目标是将暂时的不可用性保证在一个election timeout下。所以当复制新日志的时间大于一个election timeout的时候，说明新的server还没有能够追赶上来的能力

作为新服务器追赶的第一步，leader必须发现新服务器的日志是空的。如果通过在AppendEntries中不断的失败来将leader的nextIndex下降到1，会影响性能。所以可以在AppendEntries中返回其日志的长度

破坏性服务器

有的服务器可能不在新的配置中，但是他自己并不知道，所以他会不断的超时并进行RequestVote RPC

消除干扰的第一个思路就是，如果一个服务器要考试election，他会首先检查他会不会浪费其他人的时间——他是否有机会赢得选举

引入pre-vote phase，只有candidate相信自己可以从集群中或的大多数投票的时候，他才会开始真正的选举

但是某些情况下，干扰服务器已经足够新，他仍然会造成干扰

比如这种情况

Raft的解决方案是使用心跳来确定何时存在有效的leader。在raft中，如果leader可以保持跟随着的心跳状态，则他被认为是活跃的。因此服务器不应该干扰一个活跃的leader

所以如果服务器从当前leader哪里听到的最小选举超时内收到RequestVote请求，则他可以放弃请求，拒绝投票或者延迟投票

正常情况下，每个服务器应该等待最小选举超时时间再开始新的选举。对于切换配置的这种情况，我们拒绝小于最小选举超时时间的RequestVoteRPC即可。因为这说明请求的服务器是不正常的

最后是一个小总结

1. 可以在配置更改的所有步骤中选举一位领导者。

• 如果新集群中具有最新日志的可用服务器具有 Cnew 条目，它可以从大多数 Cnew 那里收集选票并成为领导者。
• 否则，Cnew 条目必然尚未提交。 在旧集群和新集群中，具有最新日志的可用服务器可以收集大多数 Cold 和大多数 Cnew 的投票，因此，无论使用哪种配置，它都可以成为领导者。

2. 领导一经选举便得到维持，假设他的心跳达到了正常状态， 除非它因不在 Cnew 中但已提交 Cnew 而有意退出。

• 如果领导者可以可靠地将心跳发送到其自己的跟随者，则它或其跟随者都不会接受更高的任期：他们不会超时开始任何新的选举，并且他们将忽略来自其他服务器的更高任期的任何 RequestVote 消息。因此，领导者不会被迫下台。
• 如果不在 Cnew 中的服务器提交 Cnew 条目并退出，则 Raft 将选出新的领导者。这个新领导者很可能将成为 Cnew 的一部分，从而完成配置更改。 但是，下台的服务器可能会再次成为领导者，这存在一些（较小）风险。 如果它再次当选，它将确认 Cnew 条目的提交并很快下台，并且 Cnew 中的服务器下次可能再次成功。

3. 在整个配置更改期间，领导者将为客户端请求提供服务。

• 领导者可以在整个更改过程中继续将客户请求添加到他们的日志中。
• 由于在将新服务器添加到集群之前对其进行了跟踪，因此领导者可以提前提交其提交索引并及时回复客户端。

4. 领导者将通过提交 Cnew 来推进并完成配置更改，并在必要时退出以允许 Cnew 中的服务器成为领导者。

Log Compaction

Memory-Based Snapshots

这里指状态机是存在memory中

这个方法在Raft的论文中有提到，这里就不说细节了。说一下实现上的问题

为了避免可用性缺口，我们需要保证在写入快照时和正常的操作是并发进行的。

写时复制技术可以支持这种操作，有两种方法

• 状态机可以用不可变的数据结构来支持这一点，快照保存某一刻状态机的引用，并复制即可（可持久化数据结构）
• 利用操作系统的写时复制，用fork来复制服务器整个地址空间，然后子进程写入快照

服务器需要额外的内存来创建快照，并且由于false sharing（不相关的数据项恰好在一页内存中，即使只更改了第一项，第二项也要复制）导致我们需要更多的内存。所以在snapshot的时候可能出现内存耗尽的情况。所以最好准备流接口，让我们可以在snapshot的时候不必把整个快照都放在内存中

何时进行snapshot？

让快照的大小和日志的大小进行比较，如果快照小很多，那么就值得进行snapshot。但是计算快照的大小却比较复杂，因为我们会压缩快照文件。我们可以用上一个快照的大小来预估下一个的大小。

其实也可以对集群中的少数进行快照，因为正常的提交只需要大多数即可。让少数服务器暂时停止响应并进行snapshot。这样我们可以获得更大的吞吐量。（但是我感觉应该是所有人都需要snapshot）

实现问题

• 保存和加载快照： 从状态机到磁盘上文件的流接口有助于避免将整个状态机状态缓存到内存中。通过将快照写入临时文件，然后在写入完成后重命名文件来保证服务器不会从中间状态加载数据
• 传输性能可能不是很重要，因为他不涉及到新条目的提交，但是如果出现故障我们就希望尽快跟上以恢复可用性
• 消除不安全的日志访问并丢弃日志条目，这个是因为丢弃log后以前的log就访问不到了，所以要保证不会越界等问题

还有两个我认为用处不大就没写

Disk-Based Snapshots

这里的状态机是存在磁盘中的

这些状态机总是在磁盘上存储他的状态。每次apply日志都会更改磁盘上的状态，并且获得新的快照。所以一旦apply了entry，我们就可以丢弃这个entry

或者是在内存中缓存写操作，以此来提高磁盘效率（LSM）

主要的问题就是改变磁盘上的状态会导致性能下降。因为我们会用到若干个随机的磁盘写

基于磁盘的状态机也需要COW技术，来传输他给follower

Linux上的LVM可以用于创建整个磁盘分区的快照。

通过一些算法来避免开销：

• 跟踪每个磁盘块上次修改的时间
• 将磁盘内容传输给follower，并记录他的最后修改时间
• 对于磁盘块上的内容，用COW保存一致性快照并传输给follower
• 最后重传那些在上次传输后修改过的磁盘块

LSM Tree

LSM Tree做状态机的算法

某些系统会为每个run创造一个bloom filter。从而加速键的查找

在Raft中使用LSM是相当容易的。每次apply新的log就把它放到内存的树结构中

我们用raft日志大小作为限制来做合并。当raft日志到达一个阈值的时候，我们就可以把当前的状态机序列化为一个Run，然后把log都清理掉。

发送给follower的时候，只需要发送所有的Run即可。内存中的树不需要，因为他们的信息存储在log中。并且因为Run是不可变的，所以我们可以很方便的传输Run（但是run还是会合并，所以我们应该也需要一个一致性的快照）

最后就是一个log compaction的总结

• 每个服务器都独立的压缩其log
• 状态机和Raft之间的基本交互涉及到把log compaction的责任从raft转移到状态机中。一旦状态机将command持久化了以后，他就要通知raft去discard对应的log
• 一旦raftdiscard了log，那么状态机就需要负责两个新的任务：重启时加载快照，并提供一个一致性的快照用来发送给其他慢的follower

Client

可以通过这几个RPC看到，主要是我们需要防止重复

clientID用来标识用户ID，然后对于每个用户跟踪sequenceNum

对于查询来说就不需要去重了，直接查就可以。但是由于读操作没有用log，所以我们需要保证这个leader是真的leader，也就是需要与majority交换一次心跳

• 领导者：服务器可能处于领导者状态，但是如果它不是当前领导者，则可能不必要地延迟了客户端请求。例如，假设一个领导者已和集群的其余部分进行了分区，但是它仍然可以与特定的客户端进行通信。如果没有其他机制，它可能会永远延迟来自该客户端的请求，无法将日志条目复制到任何其他服务器。期间可能还有另一个新任期的领导者能够与大多数集群成员通信，并且能够提交客户的请求。因此，如果没有在其大部分集群中成功进行一轮心跳，选举超时就结束了，Raft 领导者就会下台。这样，客户端可以通过另一台服务器重试其请求。
• 跟随者：跟随者保持跟踪领导者的身份，以便他们可以重定向或代理客户端的请求。他们在开始新的选举或更改任期时必须放弃此信息。否则，它们可能不必要地延迟客户端（例如，两台服务器可能会彼此重定向，从而使客户端陷入无限循环）。
• 客户端：如果客户端失去与领导者（或任何特定服务器）的连接，则应仅简单随机重试一个服务器。如果该服务器发生故障，则坚持联系最后一位已知的领导者将导致不必要的延迟。

最主要的就是不要让过期的leader一直认为自己是leader，所以我们需要用lease机制，让leader与majority交换心跳

为了提供exactly-once语义，我们就需要去重的操作

去重的操作还可以更加普遍一些。我们不去跟踪每个client最后的sequence number，而是去跟踪一个sequenceNumber和回复的集合

每次request，client把他没收到回复的最小的sequenceNumber附带上。那么状态机就可以把更小的那些sequence和reply删除掉

但是client与server之间的会话不能永久的保存下去。server必须在某一时刻删除掉这个session。那么带来了两个问题：服务器之间怎么达到删除session的共识呢？以及怎么处理session被过早关闭的情况？

比如我们有一个server关闭了这个session，然后就会重新apply这个client的操作，但是另一个server没有关闭，所以他成功去重了。这时候服务器的state就是不一致的。

所以我们需要找到一个确定性的方法来关闭client的session

一个选项就是用LRU，设置session的上限。然后用LRU做evicit

另一个选项是leader会将他的时间加入到log中，其他的follower都会根据这个时间来去expire不活跃的session。client通过发送keep-alive RPC来让leader提交一个log，从而防止他们的session被断掉

另一个问题则是如何区分client是新的还是我们曾经关闭了session的client。因为如果我们为每一个没有session的client都新分配一个session的话，就有可能导致duplicate execution。所以有了上面的RegisterClient RPC，来注册一个clientID，后续的操作都会使用这个clientID。当我们发现一个clientID对应的session已经被销毁了，我们就会返回一个error（可以让client重新分配ID或者crash）

优化读

我们可以绕过日志来达成线性化的读。这个在上面的图片中有描述了具体过程

核心思路就是对于一个读请求，我们需要让leader去与majority交换心跳，从而确定自己是一个最新的leader。这样读就可以直接进行

注意在leader当选的时候，他不清楚当前的commitIndex到哪里了。我们可以保证leader有最新的commitindex对应的log，但是leader不能确定他目前是在那个位置。所以通过让leader提交一个空的log。当这个空的log提交的时候，leader就可以确定当前的commitindex在哪里。换一个思路理解就是由于read不走log，但是我们又需要让read是最新的数据，所以要保证那些提交了的log已经被apply了。但是切换leader的时候可能follower还没及时apply。所以这里提交空log的目的就是相当于一次同步，让leader的状态机达到最新的状态。

我们还可以进一步优化一下，通过一轮心跳来确认积累的任意个读请求

follower也可以进行优化，他可以去询问leader当前的readIndex。然后leader可以发送readIndex。这样当follower的状态机apply到readIndex的时候，他就可以处理读请求。

注意这里不需要考虑往返RPC之间可能出现的其他写操作。因为在我们收到leader的readIndex这一刻其实相当于我们进行了读操作，在这之前出现的写操作在client的角度看是发生在这个读之前的，在这个之后的写则是在读之后的。我们仍然可以满足线性化语义。因为那些操作都是并发的，可以被划分到读之前或之后。

利用租约来减少信息传输

一旦集群的majority已经认可了leader的心跳，leader将假定在选举超时期间没有其他的服务器成为leader。这样leader将在此期间直接回复只读查询而无需任何其他通信

我们还可以提供单调读。服务器可以将与状态机对应的索引返回给客户端，然后客户端每次请求时将这些信息提供给服务器。如果服务器发现客户端的索引大于他自己应用到的索引，他就不会为这次请求提供服务。

Optimization

用pipeline来并发执行RPC和disk write

我们可以让follower在利用网络资源接收RPC的同时，用disk资源来进行写入

为了使用pipeline，leader需要在发送一个log的RPC后立刻更新他的nextIndex，而不是等待RPC的回复

这样我们就可以pipeline下一个entry

当RPC超时的时候，我们就需要去减少对应的nextIndex。当consistency check失败的时候，leader就需要减少nextIndex并重新发送前面的entry，或者等待前面的entry发送成功

同时我们还需要支持对每一个peer的多个并发RPC，这需要我们对每个peer创建多个thread来支持

reorder的情况会导致pipeline的效率下降。所以如果我们可以去buffer out-of-order requests直到他们可以按照顺序append的话，就可以获得效率上的提升。（这就需要应用层的优化了，因为tcp层不知道我们的log谁先谁后）