项目整体业务逻辑阐述

可以将整个系统的工作流程分为两条主线：写请求 和 读请求，并辅以领导者选举这一维持系统正常运行的基础机制。

核心组件与角色：

①KVServer（Raft节点）：每个服务器节点都包含两个核心部分：Raft共识模块和状态机部分。

        Raft共识模块：负责节点间的状态同步、领导选举和日志复制。

        状态机（SkipList KV存储）：真正存储键值对数据的地方，只有已提交的日志条目才能被应用到状态机。

②MRPC通信框架：节点间（包括客户端与服务器）通信的桥梁，基于Protobuf定义消息格式，实现高效的序列化/反序列化和网络传输。

③Client（客户端）：向集群发起读写请求，并处理重试与响应。

业务逻辑流程：

（1） 领导者选举（系统启动或领导者宕机时）

        ①触发：所有节点启动时都是Follower。Follower在预定的选举超时时间内没有收到来自Leader的心跳，就会转变为Candidate，发起新一轮选举。

        ②选举：

        Candidate递增自己的任期号，并给自己投票。

        它通过MRPC向其他所有节点发送RequestVote RPC，请求投票。

        其他节点收到请求后，会判断Candidate的日志是否比自己更新，并且在本任期内尚未投票，如果满足条件则投赞成票。

        如果Candidate收到超过半数的投票，则晋升为Leader。

        ③维持统治：

        Leader开始周期性地向所有Follower发送AppendEntries RPC（心跳），以维持自己的权威并阻止新的选举。

（2）写请求流程（核心，体现线性一致性）

        ①客户端请求：

        客户端生成一个唯一的请求ID（由客户端IP和序列号组成）。

        客户端随机或通过某种服务发现机制选择一个节点，通过MRPC发送写请求（如 Put(key, value, request_id)）。

        ②领导者的处理：

        如果接收到请求的节点不是Leader，它会拒绝并告知客户端当前Leader的地址。

        Leader收到请求后：
        a. 将请求中的命令（如 SET x 1）封装成一个新的日志条目，附加到自己的本地日志中。
        b. 在下一次心跳时，通过AppendEntries RPC将这个新日志条目并行地发送给所有Follower。

        ③日志复制与提交：

        Follower收到RPC后，进行一致性检查（前一条日志的索引和任期是否匹配），如果通过，则将新日志条目追加到自己的日志中，并返回成功。

        Leader收到超过半数节点的成功响应后，就认为该日志条目是已提交的。

        Leader将这条日志条目应用到自己的状态机（SkipList） 中，执行SET x 1操作。

        ④响应客户端：

        Leader应用成功后，将操作结果通过MRPC返回给客户端。

        关键点：在返回响应前，Leader会记录这个request_id和对应的结果。如果客户端因超时等原因重试，携带相同的request_id，Leader可以直接返回之前的结果，避免了重复执行，从而保证了线性一致性。

（3）读请求流程（优化，同样保证线性一致性）

        一个朴素的读请求是直接查询Leader的状态机。但这在发生网络分区时可能导致返回过期数据（旧Leader可能不知道自己已经过时）。

        为了保证线性一致性，读请求也必须经过Raft的日志复制流程。但这会带来巨大的性能开销。

面试中可能会问到的问题大纲

关于Raft共识算法（核心难点）

基础知识

（1）用你自己的话解释一下Raft算法是如何工作的？它的核心目标是什么？

Raft是一个用于管理复制状态机日志一致性的共识算法。

它的核心目标是让一个分布式集群中的所有节点，在面对网络延迟、分区、丢包和节点宕机等故障时，能够就一系列操作指令的执行顺序达成一致，从而让每个节点的状态机最终状态完全相同。

为了实现这个目标，Raft将问题分解为三个相对独立的子问题：

选举：集群中任何时候都必须有一个且只有一个Leader节点。Leader负责接收客户端请求、管理日志复制。其他节点作为Follower，被动地响应Leader的指令。如果Leader宕机，系统能自动选举出新的Leader。

日志复制：Leader将客户端的每个操作（如SET x=1）作为一个日志条目，并持久化到本地。然后，它通过RPC将这个条目复制到所有Follower节点。当这个条目被超过半数的节点成功复制后，Leader就将其标记为已提交，并应用到自己的状态机中，同时通知客户端操作成功。

异常处理：这是Raft最核心的保障。它确保任何已提交的日志条目在任何Term的Leader上都不会被覆盖。这主要通过两条规则实现：

选举限制：只有日志足够新的Candidate才能当选Leader。

提交限制：Leader只能提交当前Term的日志条目，间接地提交之前Term的日志。

简单来说，Raft通过“一切听从Leader”的原则来简化流程，并通过“多数派”机制来保证在各种故障场景下的安全性和活性。

（2）Raft中的三种状态（Leader、Follower、Candidate）是如何转换的？触发条件是什么？

当集群中领导者节点出现宕机是，跟随者心跳时间超时，察觉到此时的领导者下线，他会自动将自己的身份转换为参与者，并向其他跟随者发送争取投票的结构化信息，当来自其他跟随者的赞同票数超过集群数量的一半时，其从参与者身份转换为领导者身份，并执行领导者应当执行的日志复制、日志提交、心跳等任务。

（3）什么是任期（Term）？它在Raft中起什么作用？

每一个新的任期都代表一个新的选举的开始。同时，其也是跟随者节点判断自己是否应当把票投递给参与者的重要考量因素。

当跟随者节点接受到来自参与者的投票请求时，其拆开结构信息，读取其中的任期，当个参与者节点的任期小于自身的任期，其不会投票给该参与者。当参与者的任期与自身任期相同，其又会参考结构化信息中的index信息，如果参与者的index信息小于自身，其也不会投票给参与者。

（4）为什么需要“超过半数”（Majority）的同意？这解决了分布式中的什么问题？（防止脑裂）

“超过半数”同意，主要解决了分布式中的分区容错性问题。与此同时，还可以防止脑裂，即集群中存在有多个leader。（脑裂的解决办法，针对当leader从宕机中恢复导致的脑裂，它再向其他节点发送心跳或复制日志请求时，其他跟随者节点发现报文中的任期比自己小，其会拒绝这个请求，并让旧领导者节点更新自己的任期，此时的旧领导节点察觉到自己的term小，就会自动更换自己的身份为跟随者）

若不采用超过半数的统一，而是所有节点的同意，那么在存在有一个节点瘫痪时，整个集群都会陷入瘫痪，无法对外提供服务。

若少于半数，则会存在出现集群脑裂的问题，即存在有多个领导节点，因此，超过半数是最好的结果。

选举机制

（1）详细描述一下选举的流程。一个节点在什么情况下会变成Candidate？

跟随者节点在超过心跳计时器还没有将接收到来自领导者节点的复制日志请求或心跳请求，其认为此时的领导者已经出现异常，并自动将自己的身份变为参与者。

变为参与者后，其向剩下的跟随者节点发送投票请求，当来自跟随者节点的投票同意请求超过半数之后，他的身份由参与者转变为领导者，承担领导者的任务。

（2）如何保证在同一个任期内最多只有一个Leader被选举出来？

这主要依赖于Raft的两个核心设计：任期（Term） 和 多数派投票（Quorum）。

任期是单调递增的：每个Term都是一个连续递增的编号，类似于逻辑时钟。它标识了Leader的统治时期。每个节点都维护自己见过的最大Term。

一个节点在一个Term内只能投一票：这是为了防止票数分散。当一个Candidate发起选举时，它必须递增Term，然后向其他节点请求投票。每个节点在收到RequestVote RPC时，会检查请求中的Term。如果请求的Term比自己的当前Term大，并且自己在本Term内还没投过票，并且Candidate的日志至少和自己一样新，它才会投出这一票。

多数派原则：Candidate必须获得超过半数的投票才能当选Leader。在一个由N个节点组成的集群中，“超过半数”意味着至少需要 N/2 + 1 张票。

数学保证：由于一个节点在一个Term内只能投一票，那么在一个给定的Term内，最多只可能有一个Candidate获得超过半数的票数。因为票数是不可分割的，两个Candidate不可能同时获得超过半数的票。这样就严格保证了同一任期内Leader的唯一性。

（3）如果选举超时，会发生什么？如何避免频繁的选举？

当出现选举超时后，会对当前任期加一，并开始新的选举。为了避免频繁的选举，会随机等待一段时间再进行选举，这便是随机回退。

（4）如果一个Follower的日志比Candidate的还要新，它会投票吗？为什么？（日志新旧比较规则）

如果一个跟随者节点的日志比参与者还要新的话，它不会给参与者投票。因为设置的投票规则是：

①若报文中的任期大于自身任期，则投票给此参与者。

②若报文中包含的任期与自身任期相等，则比较index，若自身index较短，则投票给参与者.

日志复制与一致性

（1）详细描述一条写请求从客户端发出到成功返回的完整过程。

当接收到来自客户端的请求，其调用客户端桩方法与服务端建立一个rpc连接，将数据依据proto文件中的格式进行打包后，对其进行序列化，并经由rpcChannel类发送至服务器，服务器端接收到数据后，对其进行反序列化，rpcprovider在自身已经注册的服务中匹配对应的服务并调用，依据不同的服务调用对应的方法，并将产生的响应信息进行序列化，重新经由rpcchanne类发送至客户端，客户端又经由反序列化操作来实现对响应信息的读取。

（2）什么是日志提交（Commit）？什么是日志应用（Apply）？

在Raft中，日志提交（Commit） 和 日志应用（Apply） 是两个不同但紧密关联的概念，它们分别代表了日志的 “持久化保证” 和 “状态机执行” 阶段。

日志提交

定义：一条日志条目被标记为 已提交，意味着Raft算法保证这条日志已经被超过半数的节点持久化，并且永远不会被回滚或覆盖。

发生时机：当Leader节点将一条日志条目复制到集群中的大多数（包括Leader自己） 节点上之后，Leader就会在本地将这条日志标记为已提交。

核心意义：

安全性承诺：这是Raft对客户端的最终承诺。一旦Leader告诉客户端一个写操作成功（即对应的日志已提交），就意味着这个操作的结果是持久化的，即使后续发生节点宕机、网络分区，这个结果也不会丢失。

全局可见性：提交状态是集群范围的。一个已提交的日志条目，在后续的任何Leader选举中都会被新的Leader所继承，因为选举规则要求Leader必须拥有所有已提交的日志。

日志应用

定义：一条日志条目被应用，是指将该条目中包含的命令（例如 SET x = 1）真正执行在节点的状态机 上。

发生时机：一个节点（无论是Leader还是Follower）在得知某条日志条目已被提交后（Leader会通过后续的AppendEntries RPC通知Follower哪些日志已提交），就会将这条日志应用到其本地状态机（在我的项目中就是SkipList数据库）。

核心意义：

数据可见：只有被应用的日志，其操作结果（如x的值被设置为1）才对该节点本地的读请求可见。在应用之前，即使日志已经持久化在本地，状态机中的数据也还是旧值。

响应客户端：对于写请求，Leader总是在应用了对应的日志条目之后，才将结果返回给客户端。

总结关键区别：

日志提交是分布式共识，关乎日志的安全性和持久性。

日志应用是本地执行，关乎状态机的状态更新和客户端响应。

提交一定发生在应用之前。一个操作必须先被确保不会丢失（提交），然后才能被执行（应用）。

（3）当网络发生分区时，Raft如何保证一致性？举个例子。

当发生网络分区时，raft通过其领导者选举和日志提交的规则，确保只有在包含多数派的分区中才能进行写操作，从而保证了整个系统数据的一致性，即不会出现“脑裂”导致数据冲突。

核心原则：只有多数派的分区才能选举出leader并提供服务。

举例说明：

假设我们有一个5节点的集群：[S1, S2, S3, S4, S5]。初始时，S1是Leader。

场景： 发生了网络分区，将集群分割成两部分：

分区A（多数派）：包含 [S1, S2, S3]。（假设S1是Leader）

分区B（少数派）：包含 [S4, S5]。

①分区A（多数派）的行为：

S1仍然是Leader，因为它能与分区A内的S2和S3保持通信，构成了3个节点的多数派（3 > 5/2）。

客户端写请求（如 SET balance 100）可以正常进行：

客户端将请求发送给S1。

S1将日志复制给S2和S3。

获得S2和S3的响应后（加上自己，共3个节点，超过半数），S1提交日志，应用到状态机，并返回成功给客户端。

这个分区是完全可用的，可以安全地处理读写请求。

② 分区B（少数派）的行为：

S4和S5失去了与Leader S1的联系。

它们的选举计时器会超时，然后转变为Candidate，尝试发起选举。

但是，它们无法成功选出Leader！

S4可能投票给自己，然后向S5请求投票。S5可能投票给它。

但是，要赢得选举需要至少3张票（5/2 + 1 = 3）。分区B只有2个节点，永远无法获得3张票。

因此，分区B无法选举出Leader，会持续进行选举失败。

客户端发送到分区B（比如发送到S4）的任何写请求都会失败，因为这里没有Leader来处理请求。读请求同样无法被处理（因为需要Leader）。

这个分区是不可用的，但它保证了不会产生不一致的数据。

③分区恢复后：

网络恢复，两个分区重新合并。

分区B的节点（S4, S5）会与分区A的节点通信，并发现S1的Term更高或者日志更完整。

S4和S5会自动回滚它们可能存在的、未提交的日志（如果有的话），然后从Leader S1那里同步所有已提交的日志（包括 SET balance 100）。

最终，所有节点的状态机都与S1保持一致，数据没有任何冲突。

总的来讲，raft优雅的解决了网络分区。

保证了安全性：整个集群中，只有一个分区能进行写操作，避免了数据分裂。少数派分区虽然不可用，但不会将诶胡搜任何会导致数据不一样的操作。

体现了CAP理论，在发生分区时，raft优先保证一致性和分区容错性，而牺牲了少数派分区的可用性，这是CP系统的典型行为。

（4）如果一个新的Leader上任，它发现Follower的日志和自己不一致，它会怎么做？（日志匹配机制和冲突解决）

这是Raft日志恢复机制的核心。新Leader上任后，并不会简单地覆盖Follower的日志，而是通过一种强制覆盖的方式来让Follower的日志与自己保持一致。

具体流程如下：

Leader为每个Follower维护一个 nextIndex，表示下一条要发送给该Follower的日志条目索引。

初始时，Leader会假设所有Follower的日志都和自己的最新日志一样，所以 nextIndex 被初始化为自己最后一条日志的索引 + 1。

当Leader向Follower发送AppendEntries RPC时，会携带上一条日志的索引（prevLogIndex）和任期（prevLogTerm）。

Follower收到后，会检查自己的日志在prevLogIndex处是否存在，并且任期号是否与prevLogTerm匹配。

如果匹配：Follower接受新的日志条目，追加到本地，并返回成功。

如果不匹配：Follower会拒绝这次请求，并返回失败。

Leader收到失败响应后，就知道这个Follower的日志在某个点与自己的不一致。于是，Leader会将对应Follower的 nextIndex 减1，然后重新发送AppendEntries RPC。

这个过程会一直重复（nextIndex不断递减），直到找到Leader和Follower日志一致的那个点。此时，Follower会接受请求，Leader就从这里开始，强制覆盖Follower之后所有不一致的日志，用Leader的日志来替换。

这个机制保证了Leader的日志是“唯一真相”，最终所有Follower的日志都会与Leader完全一致。

（5）什么是线性一致性？你的项目是如何保证读写操作的线性一致性的？（重点考察请求ID和读请求优化）

线性一致性要求系统表现得像只有一个数据副本，且每个操作都在调用和完成之间的某个时间点原子性地完成。我的项目通过以下机制来保证：

对于写请求：

所有写请求都必须由Leader处理。

写操作必须经过Raft日志复制的完整流程：追加日志 -> 复制到多数派 -> 提交 -> 应用到状态机。

只有在日志被提交并应用到状态机后，Leader才将结果返回给客户端。

关键点：幂等性处理。在客户端协议中，我为每个请求加入了由(client_id, seq_num)组成的请求ID。Leader在应用一个命令到状态机之前，会检查这个请求ID是否已经被处理过。如果处理过，它会直接返回之前缓存的结果，而不会重复执行命令。这防止了因客户端超时重试而导致的重复更新，保证了“仅执行一次”的语义。

对于读请求：

如果直接读取Leader的状态机，在网络分区时，一个旧的Leader可能还在服务读请求，但它已经不知道自己被隔离了，这会返回过期数据，违反线性一致性。
因此，实现了Raft论文中提到的租约读优化：

领导者在处理读请求前，首先需要确认自己仍然是合法的Leader。它通过向所有Follower发送一次不包含日志条目的心跳来实现。

只有当它收到了超过半数的心跳响应，并且确认自己的租约（在心跳超时时间内）仍然有效时，它才认为自己仍然是Leader。

然后，它从已应用到状态机的数据中读取值并返回给客户端。

通过这种方式，读请求也间接地与多数派进行了交互，确保了读取到的数据是最新的、已提交的数据，从而满足了线性一致性。

关于RPC通信框架

（1）为什么选择自己实现RPC框架而不是用现成的（如gRPC）？有什么考虑？

主要有两个层面的考虑：学习目的和控制力。

学习目的：

这个项目的核心目标之一是深入理解分布式系统的底层原理。RPC是分布式系统的基石。通过亲手实现一个RPC框架，我能更深刻地理解序列化/反序列化、网络编解码、连接管理、超时重试等机制，而不是把它们当作一个黑盒。

控制力：

gRPC等功能强大，但有时也显得笨重。自己实现的MRPC可以做得非常轻量，并且完全根据Raft算法的需求进行定制。例如，我可以为Raft的RPC消息（如AppendEntries, RequestVote）设计最精简的Protobuf消息格式，可以精细地控制线程模型（比如使用一个独立的线程池来处理RPC请求），可以定制超时和重试策略来匹配Raft的心跳和选举超时。这避免了引入不必要的复杂性和依赖。

RPC主要可以用于公司内部的微服务，不需要针对外部提供服务，当针对外部提供服务时，最好采用HTTP，因为其存在有统一的规范和标准。

（2）MRPC的通信模型是什么？是同步阻塞还是异步非阻塞？你是如何处理的？

MRPC的通信模型整体是基于事件驱动的异步非阻塞IO模型，但在用户接口层面同时提供了同步和异步两种调用方式。

主要依赖于底层实现的probuf协议和muduo库，最终依赖的是epoll（通过muduo库封装）和线程池。

底层网络模型：同步非阻塞IO+多路复用

Epoll是一种IO复用模型，本质上来讲是一种同步非阻塞IO。其工作模式为：主线程（少数IO线程）通过epoll同步地监视所有连接上的可读、可写等时间。这里的同步指的是调用epoll_wait的线程会阻塞等待事件发生。但所有的socket都被设置为非阻塞模式。这意味着当有数据可读或可写时，线程去执行IO操作不会阻塞而是立即返回。采用epoll的优势是：单个或者少量县城就能处理成千上万的并发连接，资源利用率极高，非常适合高并发的rpc场景。

线程模型：Reactor+线程池

这是构建在底层IO模型之上的架构：

Reactor反应堆：由一个或多个IO线程组成，主要负责：监听网络事件（通过epoll），接收新的连接、读取已到达的请求数据包，将响应数据写入socket。Reac本身不处理业务逻辑，其只负责IO的搬运（对应于RPCprovider类），其就相当于一个反应器。

线程池：当reactor线程完成的读取到一个RPC请求数据包后，它会将这个请求包装成一个任务（Task），投递到一个专门的业务线程池中。线程池中的工作线程负责：解析请求，查找并调用对应的服务方法，执行具体的业务逻辑，生成响应。

但实际上来讲，在具体的实现中并未采用线程池的方法，因为服务提供方提供的服务相对较少（读服务和写服务），且均有raft节点来进行处理，因此其没有采用线程池的方法，而是在reactor反应器中依据请求数据包中的服务方法，调用已经在rpcprovider已经注册的服务方法。

在Raft中的应用：

对于心跳这类周期性的、不关心具体响应的RPC，更适合使用异步调用，避免阻塞主循环。

对于日志复制和选举投票这类需要等待结果才能进行下一步状态转换的RPC，我主要使用了同步调用+超时，因为Raft的逻辑本身就需要等待响应，同步的代码更易于理解和实现。当然，也可以用异步+回调，但状态机管理会更复杂。

总结： RPC的通信模型是一个典型的主从Reactor多线程模型。底层是同步非阻塞IO，通过线程池实现业务处理的并行化，并为上层用户提供了同步和异步两种编程接口。

（3）你如何设计和定义RPC消息？Protobuf在这里扮演了什么角色？

RPC消息主要存在有三种类型的消息，也对应着三种不同的proto文件：（1）kvServer.proto文件（2）rafRPCc.proto文件（3）rpcheader.proto文件。

在kvserver的proto文件中，其主要存储了需要对KV数据库进行操作的结构化数据，整体对KV数据库的操作分为读操作和写操作，也对应了两类不同的结构化数据，分别为读信息，读操作响应信息，写信息，写操作响应信息，对应于getArgs、getreply、putappendargs、putappendreply。

Getarg信息中包含有查询数据的key值，客户端id和请求id。Getreply中包含有error字段。

Putappendargs信息中包含有需要更新或追加的键值对数据，Options字段，判断是追加还是更新，客户端id和请求id。

在raft节点之间流通的结构数据对应着raft算法的三个子部分：

首先是日志实体logentry信息，其包含有指令（类型为bytes，可以任意编码）、任期和索引。

其次是复制日志信息appendentriesargs和响应信息appendentriesreply。这也是leader节点发送心跳过程中使用的结构化信息，只是发送心跳时entries内数据为null。

Appenentriargs中包含有数据项：term、leaderid、prevlogindex、prevlogterm、entries、leaderconmit。Term表示leader的当前任期，leaderid表示leader的id，方便跟随者将客户端氢气重定向到leader，previndex表示新日志条目之前的一个日志的索引，用于一致性检查，确保follower的日志在prevlogindex处和leader一致。Pervlogterm，prevlogindex日志条目对应的任期，并一起用于一致性检查。Entries表示要追加的日志条目列表，如果为心跳，则为空列表。Leaderconmit，leader的提交索引，跟随者会根据这个值来判断是否提交本地日志。

Appendentriesreply表示追加日志响应信息，包含有以下数据项：term、success、updatenextindex、appstate。Term表示follwer当前的任期。如果leader发现这个任期比自己的大，则leader会更新自己的任期并转为follwer。Success，如果跟随者在prevlogindex处有日志并且任期与prevlogterm匹配，并且成功追加了entries，则为true，否则为false。Updatenextindex是一个优化字段，可能用于在失败时告诉leader下一个应该发送的日志索引，相比较标准raft一个个回退，这种方法更边界。Appstate表示节点的应用状态，如是否正常，是否正在安装快照等。

之后是选举对应的请求投票信息requestvoteargs和投票响应信息requestvotereply。

Requestvoteargs包含有数据项：term、candidateid、lastlogindex、lastlogterm。Term表示候选者当前任期，candidateid为候选者表示，lastlogindex和lastlogterm分别表示候选人最后日志条目的索引值和候选人最后日志条目的任期号，这也是跟随者决定投票的关键，确保日志比自己新的候选人才能当选。

Requestvotereply包含有数据项：term、votergranted、votestate。Term表示接收投票节点的当前任期，votegranted表示是否给与投票，votestate表明投票的状态（如已投给他人，日志不够新等）

 Installsnapshotrequest安装快照请求，作用是领导者向日志严重落后的跟随者发送快照，用于日志压缩和快速同步。包含有以下数据项：leaderid、term、lastsnapshotincludeindex、lastsnapshotincludeterm、data，分别表示领导者id，领导者的任期，快照中包含的最后一条日志的索引，快照中包含的最后一条日志的任期，快照原始字节数据（序列化后的状态机状态）

Installsnapshotresponse:快照安装响应。包含数据项term。作用是跟随者对快照安装请求的响应。

整体设计分析

1. Raft算法完整性

这个proto文件完整覆盖了Raft算法的三大核心机制：

领导选举：RequestVoteArgs/RequestVoteReply

日志复制：AppendEntriesArgs/AppendEntriesReply + LogEntry

安全性：通过Term字段和日志索引保证

2. 优化设计

快速索引恢复：UpdateNextIndex字段避免了Raft论文中的逐条回退

状态标识：AppState和VoteState提供了详细的错误诊断信息

快照支持：完整的快照RPC支持日志压缩

3. 数据一致性保证

所有消息都包含Term字段，这是实现线性一致性的关键：

防止过期领导者的操作

确保只有拥有最新日志的节点才能当选

维护集群的全局一致性视图

这个协议设计很好地平衡了Raft算法的理论正确性和工程实践中的性能优化需求。

（4）如何处理网络异常、超时和重试？在你的Raft实现中，RPC失败是如何处理的？

关于KV存储与系统设计

（1）为什么选择跳表（SkipList）作为底层的存储引擎？相比B+树、LSM-Tree它有什么优缺点？（读写性能、并发控制、实现复杂度）

选择跳表是基于本项目内存存储和并发性能的权衡。

性能：跳表的查询、插入、删除操作平均时间复杂度都是O(log n)，效率很高，与平衡树相当。

实现简单：相比红黑树或B+树，跳表的实现要直观和简单得多，这降低了项目的初始复杂度，让我能更专注于Raft算法本身。

出色的并发支持：这是选择跳表的一个关键原因。跳表非常适合通过无锁编程或读写锁来实现高并发。在我的实现中，我使用了读写锁。这样，可以允许多个读操作并发进行（因为Raft的状态机在应用命令后是只读的），而写操作（应用日志条目）则需要获取写锁。这种读写分离的模式非常适合Raft“一次写入，多次读取”的工作负载。

对比：

B+树：更适合磁盘存储，因为它的节点大小与磁盘页对齐。在纯内存场景下，其实现复杂性和锁的粒度可能成为瓶颈。

LSM-Tree：是LevelDB/RocksDB的基石，写性能极高，但读操作可能需要多次查找。对于我这个完全在内存中的项目来说，跳表的读性能更可预测也更优。

（2）你的SkipList是如何实现并发控制的？（例如读写锁）

采用锁队列来实现并发控制

（3）Raft的日志在现实中会无限增长，你的项目是如何处理的？有考虑过日志压缩（Snapshot）吗？如果没实现，可以谈谈你的设计思路。

在项目中使用了持久化机制，主要包含有raft节点的持久化和全部日志信息的持久化，在raft节点添加日志的过程中，当察觉到raft节点保存在内存的日志数量超过设定的指定大小之后，其就会触发日志压缩，将现有的日志持久化到磁盘文件中。与此同时，其也会固定时间保存节点的状态，当某一个节点的状态出现故障之后，其节点状态为未连接状态，此时其就会读取节点状态持久化文件中包含的内容。用于将节点从故障中恢复。

（4）集群的成员变更（增加或删除节点）是如何支持的？有实现吗？（这是一个高级话题，如果能回答会非常加分）

目前还没有实现集群节点的拓扑变更，还是将所有的节点信息保存在一个配置文件中的，无法实现动态的对节点的变更。后续可能考虑的优化方向，就是当需要对某个节点进行变更的时候，额外设定设定一个类来实现对节点配置文件中的信息进行增加和修改操作。（这种是一种停机变更）

一种就是Raft论文中出现的集群变更方法，采用动态变更，这种情况下，为了避免由于集群配置变更存在的新旧集群脑裂问题，采用二阶段来实现配置切换，在新旧之间引入一个成为新旧联合共识的特殊配置来作为迁移状态，该配置有如下性质：

1. 日志记录会同时备份到新旧节点上
2. 两份配置集中的任意机器都能成为leader
3. 选举或提交日志记录要求得到来自新旧两个不同的大多数的同意。

不停机变更：

（5）在你的测试中，系统的性能如何？瓶颈可能在哪里？（是网络、是磁盘I/O还是锁竞争？）

在测试中，主要采用了pref进行测试，测试之后发现整个系统的瓶颈在于RPC连接，主要的性能损耗也在于RPC连接，推测可能的原因是在系统整个服务的过程中，客户端需要和服务端的节点一一建立RPC连接，直至找到领导节点。除此之外，raft节点集群中也存在有节点之间的RPC连接，若存在有n个节点，则其需要建立N-1条RPC连接。

项目实现与调试

（1）在实现Raft的过程中，你遇到的最大挑战是什么？你是怎么解决的？

在实验过程中，遇到的最大挑战是代码当中可能存在的死锁和活锁问题，需要合适的去判断锁究竟应当加在哪段临界区代码段，对代码段进行加锁之后，有没有进行正常的锁释放。针对这种在临界区代码中存在有直接返回，而未执行到锁释放的问题，采用了锁的RAII机制来进行实现。

以及在最初的选举函数设置的时候，照搬了心跳计时器的设置，导致在一些特定情况下会存在多个节点同时开始选举，进而导致整个系统长时间的瘫痪，无法对外提供服务。

针对这个问题，后面采用了对每个线程设定随机选举超时时间来实现。

（2）你是如何测试和验证你的Raft实现是正确的？（这非常关键）

单元测试、分模块测试等

（3）如果让你继续优化这个项目，你下一步会做什么？（例如：实现日志快照、支持集群配置变更、优化性能等）

①实现日志压缩与快照：

问题：Raft的日志会无限增长，占用大量内存和网络带宽。

方案：实现快照功能。当日志增长到一定大小时，将当前状态机的完整状态持久化到一个快照文件中，并截断该点之前的日志。在Follower日志落后太多时，Leader可以直接发送快照，而不是重放所有历史日志，极大提升恢复效率。

②支持集群成员变更：

问题：目前集群节点是静态配置的，无法动态增删节点。

方案：实现Raft论文中提到的联合共识或更简单的单节点变更算法，允许在不停机的情况下安全地改变集群配置。

③性能优化：

批处理：将多个客户端请求打包成一个大的Raft日志条目进行复制，减少RPC次数。

Pipeline：让Leader无需等待上一条日志的响应，可以连续发送多条日志，充分利用网络带宽。

④MRPC异步化：将MRPC的客户端改为完全异步模式，减少阻塞，提高吞吐量。

其它

（1）这个项目可以在哪些领域可以应用，有哪些实际基于这种原理开发的成熟产品

Raft 算法核心解决的是分布式系统中的数据一致性问题。因此，任何需要高可用、强一致性、且能容忍部分性能损失的场景，都是其用武之地。具体应用领域包括：

微服务与云原生基础设施

服务发现与配置中心：这是最经典的应用。微服务需要知道彼此的网络地址，并且需要动态更新配置。基于 Raft 的 KV 存储（如 etcd）可以作为服务注册中心，保证服务列表和配置信息在所有节点间强一致，避免因数据不一致导致的服务调用错误或配置混乱。

分布式锁：在微服务架构中，经常需要协调多个服务实例对共享资源的访问（如防止定时任务重复执行、保证资源操作的互斥性）。基于 Raft 的 KV 存储可以轻松实现安全、可靠的分布式锁。

容器编排平台

Kubernetes 的后端存储：这是 etcd 最著名的应用案例。Kubernetes 将所有集群状态（如 Pod、Node、Service、ConfigMap 等）都存储在 etcd 中。Raft 协议保证了整个集群状态的一致性，这是 K8s 能够可靠地管理和调度容器的根本前提。

分布式数据库系统

元数据存储：许多分布式数据库（如 TiDB、CockroachDB）使用 Raft 来管理数据库的元数据，例如表结构、分区（Region/Range）的路由信息、数据分片的分布位置等。这保证了整个数据库集群的“大脑”是高度可用的。

底层存储引擎：像 TiKV（TiDB 的存储层）和 CockroachDB 的存储层，直接使用 Multi-Raft 模型来管理用户数据的多个分片，确保每个数据分片都在多个副本间保持强一致性和高可用。

中间件系统

消息队列：一些新一代的消息队列（如 Apache Pulsar）使用基于 Raft 的存储（如 Apache BookKeeper）来持久化消息，确保消息不丢失，并且在多个副本间同步。

命名服务与协调服务：例如 ZooKeeper 的替代品，如前面提到的 etcd 和 Consul，它们本身就是为分布式协调而生的。

边缘计算与物联网

在边缘场景中，网络可能不稳定。一些轻量级的、基于 Raft 的存储可以部署在边缘节点上，用于在局部网络内实现数据的可靠同步和服务的自动发现与恢复。

二、具体的成型产品

以下是一些非常成熟和广泛使用的基于 Raft 的分布式 KV 存储产品：

etcd

简介：由 CoreOS 开发，现在是 CNCF 的毕业项目。是当前云原生领域事实上的标准。

核心应用：Kubernetes 的默认后端存储。几乎所有基于 K8s 的云平台都依赖它。

特点：简单、可靠、性能出色，API 相对基础（提供原始的 KV 操作，支持租约和 Watch 机制）。

官网： https://etcd.io/

Consul

简介：由 HashiCorp 公司开发，是一个全功能的服务网格解决方案，其核心也使用了 Raft 协议。

核心应用：服务发现、配置、网络分段。它比 etcd 提供了更高级的服务发现功能（如健康检查、DNS 接口）。

特点：不仅仅是一个 KV 存储，更是一个服务网络和控制平面。

官网： https://www.consul.io/

TiKV

简介：由 PingCAP 公司开发的开源分布式事务 KV 存储数据库，是 CNCF 的毕业项目。

核心应用：作为 TiDB 的底层存储引擎，同时也能够直接作为高性能、支持事务的 KV 存储单独使用。

特点：使用了 Multi-Raft 模型，将数据分片（Region）并让每个分片独立运行 Raft 组，极大地提升了可扩展性和性能。支持跨行 ACID 事务。

官网： https://tikv.org/

Apache ZooKeeper

简介：虽然 ZooKeeper 使用的是自有的 ZAB 协议，而非 Raft，但 ZAB 与 Raft 解决的问题和设计思想非常相似，通常被归为同一类“共识系统”。它是这个领域的先驱和经典。

核心应用：Hadoop、HBase、Kafka（旧版本）等大数据生态系统的核心协调服务。

特点：非常成熟稳定，提供类似文件系统的树形数据模型。

官网： https://zookeeper.apache.org/

CockroachDB

简介：一个与 Spanner 类似的分布式 SQL 数据库。

底层机制：其底层存储使用 Raft 协议来复制数据范围，实现高可用和强一致性。

特点：全球部署、强一致性、兼容 PostgreSQL 协议。

官网： https://www.cockroachlabs.com/

（2）protobuf序列化协议是由哪个公司发明的，压缩算法的性能怎么样

        谷歌，压缩性能需要从底层的编码方式出发进行分析，此处略。

（3）里面有没有用到哪些设计模式

单例模式。远程RPC调用的返回信息时，其只创建了一个clousure的实例。

（4）底层如何处理来自客户端的并发的，如果采用epoll的话，其和select的区别有哪些。

主要可以从以下几个方面来进行描述：

①select能够监视的文件描述符数量存在最大限制，且其采用轮询的方式访问调用文件描述符，文件描述符数量越多，性能越差。

而epoll在linux内核中通过epoll_create来申请一个文件系统，采用B+树的方式来进行管理，大大的节省了磁盘IO效率。

②select将文件描述符从内核空间复制到用户空间，产生巨大的花销，扫描完调用文件描述符之后，返回的是含有整个文件描述的数据，应用程序需要遍历所有数据才能发现是哪些文件描述符发生了事件。

而epoll将select/poll的调用分成了三个部分：①首先调用epoll_create()方法创建一个epoll对象。②调用epoll_ctl()来向epoll对象中添加并发连接的多个文件描述符。③调用epoll_wait收集发生事件的文件描述符资源。因此，其不存在文件描述符复制花销，仅返回发生事件的文件描述符集合而不是全部的文件描述符集合。

③Select的触发方式是水平触发，即应用程序接收到返回的文件描述符集合后，可以并不立即处理，而是在应用程序下一次调用后，再次向其通告，直至被处理。

而epoll可以选择水平触发或者边缘触发，默认的工作模式是水平触发，边缘触发是指一旦epoll_wait返回发生事件的文件描述集合，应用程序必须立即处理，如应用处理未处理，后续的epoll_wait()也不会向其通告这个事件。ET的方式很好的提高性能，但还是没有LT的方式安全性更高、支持跨平台。

（5）Protobuf相比于其他序列化方式来讲，存在有哪些优势，与其他序列化方式的一个横向对比。

相比于XML和JSON的序列化方式来讲，Protobuf其主要存在有以下几个优点：

• 其底层是采用二进制流的形式进行传输，相对XML编码后体积更小，编解码速度更快；相对与JSON而言，其存在有更高的转化效率，时间效率和空间效率都是JSON的3-5倍。
• 其是语言无关的，可以支持多种语言，不管是c++、go、java还是python。而json和大部分用于java语言中。
• 其有代码生成机制，其底层存在有代码生成机制，可以根据提供的结构信息格式生成对应的类和服务桩，便于客户端和服务端的调用。

扩展问题：

为什么protobuf比xml和json的编解码速度更快，性能更高，底层的原理是什么

可以从以下几个方面来进行详细对比：

1）数据编码格式：二进制vs文本

二进制格式天生就比文本格式更紧凑，消除了所有不必要的冗余字符。

①可读性 ② 标记 ③数字编码

虽然文本格式人类可读性高，但这也是限制其性能瓶颈的根源。所有数据最终都被编码成字符串；且其内部包含有大量重复的字段名和结构符号；数字编码低效，如数字12345在json中需要5个字节来存储，而浮点数的可能更长。

    相较而言，二进制编码格式虽然文件的可读性不好，但对于机器来讲是友好的，机器可以很快的解读数据；并且其并不使用字段名，而是在编译时确定的，紧凑的字段标签和类型；同时，其还具有紧凑的数字编码，采用base128 varints编码整数，只用一个字节就可表示较小的整数，浮点数采用固定的4字节或8字节表示，无需转换字符串。

2）数据模型：强schema vs 无schema

Json和xml是无模式/弱模式。其在编码时需要将字段名和值一起序列化；解码时，解析器必须：（1）读取字符流（2）跳过空白字符（3）识别标记（4）将字段名字符串与值进行匹配（5）根据上下文推算值的类型。整个过程涉及大量的字符串比较、内存分配和类型推断，计算开销非常大。

Protobuf是强模式。在编译时，proto文件预定义了所有字段的标签和类型。编码时，不序列化字段名，只序列化标签和值；解码时，解析其根据预先生成的编解码代码（如c++类、java类）直接操作。

Protobuf采用的强模式，使得解码过程几乎没有字符串比较，内存操作时线性和预测性的，效率极高。

3）编解码过程：生成代码 vs 运行时解释

Json/XML通常使用映射和运行时解释库（如jackson、Gson）在运行时检查对象的属性，然后动态觉得如何序列化它们，这种动态性带来了灵活性，但牺牲了性能。

Protobuf有一个代码生成步骤（预编译步骤），定义好的proto文件会为你生成目标语言的高度优化的序列化/反序列化代码；生成的代码直接操作内存和字节流，避免反射与运行时解释的开销，如同手写一样高效。

4）数据体积

Protobuf采用二进制编码，省略了字段名，使用varints等压缩编码，序列化后的数据体积通常只有等效json的1/3到1/10，甚至是XML的1/10到1/20。更小的体积意味着更少的网络传输时间、更少的磁盘IO和更低的内存占用。

总体而言，protobuf性能更高的根本原因在于其“为机器设计”。

①二进制的编码格式，使得其对于机器易读，消除了文本格式的冗余和解析成本。

② 强模式和代码生成机制，使得其不需要保存字段，直接对数据进行编码，并将运行时解释的工作转移到了编译时，生成了高效、无反射的编解码代码。

③紧凑的编码方案使得其减少数据体积，对应这更小的磁盘IO和内存占用。

另一个扩展问题：protobuf底层的压缩算法是什么，性能如何？

Protobuf采用varints编码和zigzag编码来编码数据。

Varint编码主要针对于整型数据，存在有base64和base128，常用的是base64，具体说来，主要编码流程如下，需要传输的二进制数据按照6个bit为一组，剩余的少于6bit的低位补0，之后在每一组6bits的高位补0。Base64的对照表如图示：

由于base64一个字节中最多仅有75%的利用率，因此为了提高利用率，提出了base128。按照思路base128需要使用128+1个ascii个字符，但ASCII字符一共只有128中。且在ASCII码中包含有一些不可以正常打印的控制字符，编码之后的字符还可能包含会被不同操作系统转换的换行字符。

（6）RPC通信和HTTP通信的优点是什么，为什么选择RPC通信

RPC通信是一种远程调用方法，其使得客户端感知调用远程的方法就如同调用本地的方法一般，比较成熟的产品有gRPC和thrift。而HTTP是超文本传输协议，其传输的对象不仅限于文本，还有图像、音频等信息。HTTP1.0采用了长连接，HTTP2.0采用了多路复用和头部压缩的方式。

①RPC通信的优点主要包含有得益于高效的二进制序列化和连接复用机制的高性能、低延迟，得益于代码生成机制的开发体验好。多语言支持（系统事多语言的，需要严格的接口契约和代码生成来保持一致性）。适用场景为公司内部、微服务之间的高效通信。

而HTTP相对于RPC来讲性能与效率相对较低，其采用的序列化方式一般为JSON或者XML，体积大，解析效率低。但其并非流传输，因此文本格式易于阅读和调试。除此之外，还具有通用性与普试性：被所有编程语言和平台支持，适用于客户端多样，尤其是需要Web浏览器直接调用时。

②RPC不仅支持请求/响应，还支持流式通信（如客户端流、服务端流、双向流等）。而HTTP主要是请求/响应模型，虽然有WebSocket和Server Sent Event，但整体还是一个请求/响应模型。

（7）在项目中智能指针的应用

在c++11中智能指针主要可以分为两种一种是带引用计数的指针，一种是不带引用计数的指针。其中不带引用计数的常用的智能指针是unique_ptr，带引用计数的有shared、_ptr和weak_ptr。依据项目进行举例论述。

（8）在项目中锁的应用

项目中主要使用的锁为互斥量，通过灵活使用锁的包装器lock_guard和unique_guard，避免其在代码中出现死锁，需要注意是，出现条件变量的地方，使用的锁包装器必须为unique_guard。依据项目进行举例论述

（9）在项目中多线程的应用

项目中主要调用std::thread创建多个子线程，项目中主要的三个子线程为心跳子线程。选举子线程和日志应用子线程。三个子线程各自维护一个心跳计时器、选举计时器和日志应用计时器，并执行器其代码内部逻辑，当出现定时器超时之后，开启对应的心跳动作子线程，选举动作子线程。因为项目中存在有多个子线程，因此一定要注意相关临界资源的保护，及加锁释放锁的操作，合理设置粒度来减少多个线程之间的数据竞争。

（10）项目实现过程中遇到的问题及解决办法

项目实现过程中，

1. 第一个问题可能就是整个项目环境的搭建，由于RPC通信需要依赖于底层的protobuf协议和muduo网络库，因此需要下载导入对应的包。这个主要是通过参考网上教程来解决的。
2. 第二个问题就是protobuf结构化数据的一个设计，需要弄清楚客户端和服务端之间，服务端的raft节点和raft节点之间需要传递的消息类型有哪些，每个消息类型中包含有哪些数据。这种主要是根据raft论文中的消息来进行一定的更改实现的。
3. 第三个问题是raft共识算法实现过程中，对临界资源的一些锁的把握，判断哪些资源是临界资源，存在多线程访问的可能。同时，在代码逻辑中，也需要避免因为提前的函数返回导致的死锁问题。死锁问题主要采用锁的包装器来解决，其他的问题主要通过对代码进行一个整体的审计，梳理一遍整体流程，来判断哪些资源属于临界资源。

（11）六大设计原则以及常见的一些设计模式，简单介绍一个设计模式

常见的六大设计原则有：单一职责原则、开闭原则、里氏替换原则、依赖倒置原则、接口隔离原则、迪米特原则。项目中比较常用的设计原则是开闭，里式替换原则，接口隔离和依赖倒置。

常见的设计模式为单例模式，工厂模式，代理模式，适配器模式，装饰器模式等。

（12）项目在产生快照的时候能不能正常对外提供服务，如果它在快照期间触发了对快照数据的修改怎么办？

（13）线性一致性及其在项目中的体现

线性一致性确保操作在全局时间线上有序执行，表现得就像它们串行执行一样。

具体说来表现为一下两点：

1）任何读操作都会返回最近的写操作的结果

2）系统中的所有进程，看到的操作顺序，都与全局时钟下的顺序一致。

Raft算法对于一致性读给出了两种方案，来保证处理这次读请求的一定是leader：

①ReadIndex算法。

每次读操作的时候记录此时集群的commitindex。当状态机的apply_index大于或等于commit_index时才读取数据并返回。由于此时状态机的状态就可以反应读请求发起时的状态，符合每次读操作都会返回最新写操作的结果的要求。

为了确保commitindex的准确，采用以下三种方式：

1. 让leader来处理读请求
2. 如果Follower接收到读请求，将请求forward给leader。
3. 确保当前leader仍为leader。

②LeaseRead算法

        在项目中的体现为，采用ip号+请求号一同序列号唯一标识一个请求，保证整个系统的线性一致性。项目中实现线性一致性采用的算法就是readindex算法，维护了两个状态变量commit_index和applyu_index，并且为了保证commitindex的准确，将所有的请求都交由leader进行处理。但这样会导致两个问题：leader节点过载与当leader节点发生故障时，在选举期间无法对外提供任何服务。

（14）网络为什么分层，分层有哪些好处

        分层可以将庞大复杂的问题，转化为若干个较小的局部问题，这些局部的较小的问题就比较易于研究和处理。

        分层的优点：

1）网络分层使得各层之间是相互独立的，不用关心其他层次的内容。

2）灵活性好，任何一层发生变化都不会影响上下层。

3）架构上可分割开，每层都用最好的技术实现。

4）易于实现和维护，仅需维护独立的子系统

5）能促进标准化的工作，每层的功能，提供的服务有了精确的说明。

免责声明

此文章内容仅为个人总结记录所用，可能存在错误，敬请批评指正。