Raft

Dingo KvStore 基于 Raft 算法。Raft 是一种管理复制日志的共识算法。它产生的结果等同于（多）Paxos，其效率不亚于 Paxos，但其结构与 Paxos 不同；这使得 Raft 比 Paxos 更容易理解，也为构建实用系统提供了更好的基础。为了提高可理解性，Raft 分离了共识的关键要素，如Leader选举、日志复制和安全性，并强制执行更强的一致性，以减少必须考虑的状态数量。一项用户研究结果表明，对于学生来说，Raft 比 Paxos 更容易学习。Raft 还包括一种新的集群成员变更机制，它使用重叠多数来保证安全性。Raft 算法允许机器集合作为一个连贯的群组工作，该群组可以在部分成员出现故障时继续工作。

Raft 在许多方面与现有的共识算法（最著名的是 Oki 和 Liskov 的 Viewstamped Replication）相似，但它有几个新的特点：

  1. Strong Leader: Raft 使用比其他共识算法更强的Leader形式。例如，日志条目只从Leader流向其他服务器。这简化了复制日志的管理，也使 Raft 更容易理解。

  2. Leader 选举： Raft 使用随机计时器选举Leader 。这只需在任何共识算法所需的心跳基础上增加少量机制，就能简单快速地解决冲突。

  3. 成员变更： Raft 更改集群中服务器集的机制采用了一种新的联合共识方法，在这种方法中，两种不同配置的多数在转换过程中重叠。这样，集群就能在配置变更期间继续正常运行。

Raft 出现在复制状态机中。在这种方法中，一组服务器上的状态机计算相同状态的相同副本，即使部分服务器宕机，状态机也能继续运行。Raft 管理着一个复制日志，其中包含来自客户端的状态机命令。状态机处理来自日志的相同命令序列，因此产生相同的输出。

Log Replication

只有Leader 服务于客户请求。每个客户请求都包含一个要由复制状态机执行的命令。Leader 将命令作为新条目添加到日志中，然后并行向其他每个服务器发送 AppendEntries RPC，以复制该条目。当条目被安全复制后，Leader 会将条目应用到其状态机中，并将执行结果返回给客户端。如果followers 崩溃或运行缓慢，或者网络数据包丢失，Leader 会无限期地重试 AppendEntries RPC（甚至在对客户端做出响应之后），直到所有followers 最终存储了所有日志条目。

每个日志条目都存储了一条状态机命令以及Leader收到该条目时的术语编号。日志条目中的术语编号用于检测日志之间的不一致性。每个日志条目还有一个整数索引，用于标识其在日志中的位置。

io.dingodb.raft.entity.LogId

Leader 决定何时可以安全地将日志条目应用于状态机；这样的条目被称为已提交条目。Raft 保证提交的条目是持久的，最终将由所有可用的状态机执行。一旦创建条目的Leader 在大多数服务器上复制了日志条目，该条目就会被提交。这也会提交Leader 日志中所有之前的条目，包括之前的Leader 创建的条目。Leader 在一个给定的任期内最多只能创建一个具有给定日志索引的条目，而且日志条目在日志中的位置永远不会改变。在发送 AppendEntries RPC 时，Leader 会在其日志中包含紧接新条目之前的条目的索引和术语。如果follower 在其日志中找不到具有相同索引和术语的条目，则会拒绝接收新条目。

Leader: io.dingodb.raft.core.Replicator#sendEntries
Follower: io.dingodb.raft.core.NodeImpl#handleAppendEntriesRequest
Leader: io.dingodb.raft.core.Replicator#onAppendEntriesReturned

Snapshot

快照是最简单的压缩方法。Raft 的日志在正常运行期间会不断增长，以纳入更多的客户端请求，但在实际系统中，日志的增长不可能无限制。日志越长，占用的空间就越大，重放所需的时间也就越长。如果没有某种机制来丢弃日志中积累的过时信息，这最终会导致可用性问题。在快照过程中，整个系统的当前状态会被写入稳定存储区的快照中，然后丢弃截至该点的整个日志。服务器用新快照替换日志中已提交的条目，新快照只存储当前状态。

每台服务器都独立拍摄快照，只覆盖其日志中已提交的条目。大部分工作包括状态机将其当前状态写入快照。Raft 还在快照中包含了少量元数据：最后包含的索引是快照替换的日志中最后一个条目的索引（状态机应用的最后一个条目），最后包含的术语是该条目术语。保留这些信息是为了支持快照后第一个日志条目的 AppendEntries 一致性检查，因为该条目需要之前的日志索引和术语。虽然服务器通常会独立拍摄快照，但Leader 偶尔也必须向落后的followers 发送快照。Leader 使用名为 InstallSnapshot 的新 RPC 向落后太多的followers 发送快照。当followers 通过该 RPC 收到快照时，它必须决定如何处理其现有的日志条目。通常，快照会包含接收者日志中尚未包含的新信息。在这种情况下，followers 会丢弃它的整个日志；因为所有日志都被快照取代了，而且可能有未提交的条目与快照冲突。相反，如果followers 收到的快照描述了其日志的前缀（由于重传或错误），那么快照所涵盖的日志条目将被删除，但快照之后的条目仍然有效，必须保留。

Each Server: io.dingodb.raft.core.NodeImpl#snapshotTimer
Each Server: io.dingodb.raft.core.NodeImpl#handleSnapshotTimeout
Leader: io.dingodb.raft.core.Replicator#installSnapshot
Follower:io.dingodb.raft.core.NodeImpl#handleInstallSnapshot
Leader: io.dingodb.raft.core.Replicator#onInstallSnapshotReturned

Membership Changes

Raft 集群包含多台服务器；典型的数量为五台，这样系统就能承受两次故障。在任何时候，每台服务器都处于三种状态之一：Leader、 follower 或 candidate。正常运行时，只有一个Leader，其他所有服务器都是follower 。follower 是被动的：它们自己不发出请求，只是响应Leader和candidate的请求。Leader处理所有客户请求（如果客户联系follower ，follower 会将其重定向到Leader）。第三个状态是候选状态，用于选举新的Leader。如果follower 没有收到任何通信，它就会成为candidate并发起选举。获得整个集群多数票的candidate将成为新的Leader。Leader通常一直运行到失败为止。 

io.dingodb.raft.core.State

  1. Raft 使用心跳机制来触发Leader 选举。当服务器启动时，它们从follower状态开始。只要服务器从Leader 或Candidate 那里接收到有效的 RPC，它就会保持Follower状态。Leader 会定期向所有Follower发送心跳（不携带日志条目的 AppendEntries RPC），以保持其权威性。如果Follower在一段被称为选举超时的时间内没有收到任何通信，那么它就会认为没有可行的Leader ，并开始选举新的Leader 。为了开始选举，follower会递增其当前任期，并过渡到候选状态。然后，它为自己投票，并向集群中的每个其他服务器发送并行的 RequestVote RPC。candidate会一直处于这种状态，直到发生以下三种情况之一：(a) 赢得选举，(b) 另一台服务器成为Leader ，或 (c) 一段时间后没有获胜者。 如果一个candidate从整个集群的大多数服务器中获得了同一任期的选票，那么它就赢得了选举。按照先到先得的原则，每台服务器在给定任期内最多只能为一名candidate投票。少数服从多数的规则确保了最多只有一名candidate能在特定任期的选举中获胜。candidate一旦赢得选举，就会成为Leader 。然后，它会向所有其他服务器发送心跳信息，以建立自己的权威，并防止出现新的选举。 在等待投票期间，candidate可能会收到来自其他服务器的自称为Leader 的 AppendEntries RPC。如果Leader 的任期（包含在其 RPC 中）至少与candidate当前任期一样大，那么candidate就会承认Leader 是合法的，并返回follower状态。如果 RPC 中的任期小于candidate当前任期，则candidate拒绝 RPC，继续保持candidate状态。第三种可能的结果是candidate既没有赢得选举，也没有输掉选举：如果很多follower同时成为candidate，选票可能会被分割，从而没有candidate获得多数票。当这种情况发生时，每个candidate都会超时，并通过递增任期和启动新一轮的请求投票 RPC 开始新的选举。但是，如果没有额外的措施，分裂投票可能会无限期地重复。Raft 使用随机选举超时来确保分裂投票的罕见性和快速解决。为了从一开始就防止分裂投票，选举超时是从一个固定间隔（如 150-300ms）中随机选择的。这样可以分散服务器，在大多数情况下，只有一台服务器会超时；它会赢得选举，并在其他服务器超时之前发送心跳。同样的机制也用于处理分裂投票。每个candidate都会在选举开始时重新启动其随机选举超时，并等待超时结束后再开始下一次选举；这就降低了在新的选举中再次出现分裂投票的可能性。

Follower: io.dingodb.raft.core.NodeImpl#preVote
Other: io.dingodb.raft.core.NodeImpl#handlePreVoteRequest
Follower: io.dingodb.raft.core.NodeImpl#handlePreVoteResponse
Candidate: io.dingodb.raft.core.NodeImpl#electSelf
Other: io.dingodb.raft.core.NodeImpl#handleRequestVoteRequest
Candidate: io.dingodb.raft.core.NodeImpl#handleRequestVoteResponse
Leader: io.dingodb.raft.core.NodeImpl#becomeLeader

  1. Follower/Candidate冲突 Follower和Candidate崩溃的处理要简单得多，两者的处理方式相同。如果Follower或Candidate崩溃，那么以后发送给它的 RequestVote 和 AppendEntries RPC 都将失败。Raft 会通过无限重试来处理这些失败；如果崩溃的服务器重新启动，那么 RPC 将成功完成。如果服务器在完成 RPC 后但在响应前崩溃，那么它将在重启后再次收到相同的 RPC。RPC 是幂等的，因此不会造成任何损害。例如，如果Follower收到的 AppendEntries 请求包含了其日志中已有的日志条目，那么它就会忽略新请求中的这些条目。

io.dingodb.raft.core.ReplicatorGroupImpl#checkReplicator
io.dingodb.raft.core.ReplicatorGroupImpl#stopReplicator
io.dingodb.raft.core.NodeImpl.ConfigurationCtx#addNewPeers
io.dingodb.raft.core.NodeImpl#onCaughtUp
io.dingodb.raft.core.Replicator#waitForCaughtUp

  1. Leader 崩溃 Leader 最终必须存储所有已提交的日志条目。日志条目只能单向流动，即从Leader 流向Follower，Leader 绝不会覆盖其日志中的现有条目。一旦大多数服务器上都存储了当前任期内的日志条目，Leader就会知道该条目已提交。如果Leader在提交条目前崩溃，未来的Leader会尝试完成条目的复制。但是，一旦上一任期的条目存储在大多数服务器上，Leader就不能立即断定该条目已被提交。Raft 从不通过计算复制次数来提交前一学期的日志条目。只有Leader当前任期内的日志条目才会通过计算副本的方式提交；一旦当前任期内的条目以这种方式提交，那么之前的所有条目都会因为日志匹配属性而间接提交。在某些情况下，Leader可以有把握地断定较早的日志条目已被提交（例如，如果该条目存储在每台服务器上），但为了简单起见，Raft 采用了更为保守的方法。Raft 在承诺规则中产生了这种额外的复杂性，因为当Leader复制前几期的条目时，日志条目会保留其原来的期号。而在其他共识算法中，如果新的Leader复制了之前 “术语 ”中的条目，则必须使用新的 “术语编号”。 Raft 的方法更容易推理日志条目，因为它们在不同时间和不同日志中都保持相同的任期编号。此外，与其他算法相比，Raft 中的新Leader发送的前一任期日志条目更少。 a. 在当选LeaderU 时，其日志中必须没有已提交的条目（Leader从不删除或覆盖条目）。 b. LeaderT 在集群的大多数服务器上复制了该条目，而LeaderU 收到了集群大多数服务器的投票。因此，至少有一台服务器（“投票者”）既接受了LeaderT 的条目，又把票投给了LeaderU。c. 投票者在投票给LeaderU 之前，一定接受了LeaderT 提交的条目，否则它就会拒绝LeaderT 的 AppendEntries 请求（它当前的任期会高于LeaderT）。e. 投票者把票投给了LeaderU，因此LeaderU 的日志一定和投票者的日志一样是最新的。这将导致两个矛盾中的一个。 f. 首先，如果投票人和LeaderU 共享相同的最后一个对数项，那么LeaderU 的对数项肯定至少和投票人的对数项一样长，所以它的对数项包含了投票人对数项中的每一个条目。g. 否则，LeaderU 的最后一个对数项一定比投票者的大。而且，它大于 T，因为投票者的最后一个对数项至少是 T（它包含了 T 项中的已提交条目）。创建 LeaderU 最后一个日志项的早期Leader的日志中一定包含了已提交的条目（根据假设）。那么，根据日志匹配属性，LeaderU 的日志也必须包含已提交条目，这是一个矛盾。因此，所有大于 T 的子项的Leaders 必须包含子项 T 中的所有条目，而这些条目是在子项 T 中提交的 i. 逻辑匹配属性保证了未来的Leaders 也将包含间接提交的条目。

io.dingodb.raft.core.NodeImpl#handleTimeoutNowRequest
io.dingodb.raft.core.NodeImpl#handleElectionTimeout
io.dingodb.raft.core.NodeImpl#checkStepDown
io.dingodb.raft.core.NodeImpl#resetLeaderId
io.dingodb.raft.core.FSMCallerImpl#onStopFollowing
io.dingodb.raft.core.NodeImpl#electSelf

Region

一个Region 组即为一个 Raft 组。Region 将整个 Key-Value 空间划分为一系列连续的 Key 段。每个 Region 可以用 [StartKey，EndKey]（一个左闭右开的区间）来描述。

io.dingodb.store.row.metadata.Region

Store

可包含一个或多个 Region 的物理存储节点。

io.dingodb.store.row.metadata.Store