关于后端:Raft-算法分布式-KV-面试汇总

本文选自《从零实现分布式 KV》课程的加餐文章。
从零开始，手写基于 raft 的分布式 KV 零碎，课程详情能够看这里：https://av6huf2e1k.feishu.cn/docx/JCssdlgF4oRADcxxLqncPpRCn5b

在简历上如何写这个我的项目？

我的项目概述

基于 MIT 6824 课程 lab 框架，实现一个基于 raft 共识算法、高性能、可容错的分布式 KV 存储系统，保证系统的一致性和可靠性。

设计细节

• 设计基于 Raft 一致性算法的分布式系统架构。
• 反对分布式数据存储和检索的 KV 存储引擎，采纳 Raft 协定确保数据的强一致性。
• 实现数据分片和主动故障转移机制，以实现零碎的高可用性和容错性。
• 应用 Go 语言编写，工程级代码可靠性和简洁性。

后果

• 参照 Raft 论文应用 Golang 实现了领导选举、日志同步、宕机重启和日志压缩等次要性能。相熟 Raft 算法的基本原理和实现细节，相熟 Golang 并发编程和分布式调试。
• 实现了一个高性能的分布式键值存储系统，保证数据的一致性和可靠性。
• 通过所有代码测试，在负载测试中体现出良好的性能和稳定性，可能无效地应答并发拜访和故障状况。

可能的面试问题 & 答复

以下咱们每个节点统称为 Peer，面试官可能会叫节点、正本(Replica)、Node 等等术语，记得和面试官对齐就好。

Raft 次要在什么场景中应用？

通常有两种用处：

1. 元信息服务，也称为配置服务（configuration services）、分布式协调服务（coordinator services）等等。如 etcd。用以追踪集群中元信息（比方正本地位等等）、多正本选主、告诉（Watch）等等。
2. 数据 复制（Data replication）。如 TiKV、CockroachDB 和本课程中的 ShardKV，应用 Raft 作为数据复制和冗余的一种伎俩。与之绝对，GFS 应用简略的主从复制的办法来冗余数据，可用性和一致性都比 Raft 要差。

注：在分布式系统中，数据指的是外界用户存在零碎中的数据；元数据指的是用户保护集群运行的外部信息，比方有哪些机器、哪些正本放在哪里等等。

Raft 为了简洁性做了哪些就义（即有哪些性能问题）？

1. 每个操作都要落盘。如果想进步性能可能须要将多个操作 batch 起来。
2. 主从同步数据较慢。在每个 Leader 和 Follower 之间只容许有一个曾经收回 AppendEntries；只有收到确认了，Leader 能力发下一个。相似 TCP 中的“停等协定”。如果写入速度较大，可能将所有的 AppendEntries Pipeline 起来性能会好一些（即 Leader 不等收到上一个 AppendEntries 的 RPC Reply，就开始发下一个）
3. 只反对全量快照。如果状态机比拟小这种形式还能够承受，如果数据量较大，就得反对增量快照。
4. 全量快照同步代价大。如果快照数据量很大，每次全量发送代价会过高。尤其是如果 Follower 本地有一些较老的快照时，咱们只须要发增量局部即可。
5. 难以利用多核。因为 log 只有一个写入点，所有操作都得抢这一个写入点。

Raft 在选举时是不能失常对外提供服务的，这在工程中影响大吗？

不太大，因为只有网络故障、机器宕机等事件才会引起宕机。这些故障的发生率可能在数天到数月一次，但 Raft 选主在秒级就能实现。因而，在实践中，这通常不是一个问题。

有其余不基于 Leader 的共识协定吗？

原始的 Paxos 就是无主的（区别于有主的 MultiPaxos）。因而不会有选举时的服务进展，但也有代价——每次数据同步时都要达成共识，则数据同步代价会更大（所须要的 RPC 更多，因为每次同步音讯都是两阶段的）。

论文提到 Raft 只在非拜占庭的条件下能力失常工作，什么是拜占庭条件？为什么 Raft 会出问题？

“非拜占庭条件”（Non-Byzantine conditions）是指所有的服务器都是“宕机 - 进行”（fail stop）模型（更多模型参见这里）：即每个服务器要么严格遵循 Raft 协定，要么进行服务。例如，服务器断电就是一个非拜占庭条件，此时服务器会进行执行指令，则 Raft 也会进行运行，且不会发送谬误后果给客户端。

拜占庭故障（Byzantine failure）是指有些服务器不好好干活了——可能是代码因为有 bug，也可能是混入了歹意节点。如果呈现这种类型节点，Raft 可能会发送谬误的后果给客户端。

通常来说，Raft 的所有节点都冀望部署在一个数据中心吗？

是的。跨数据中心的部署可能会有一些问题。有些零碎，如原始的 Paxos（因为是 Leaderless）能够跨数据中心部署。因为客户端能够和本地的 Peer 进行通信。

如果产生网络分区，Raft 会呈现两个 Leader，即脑裂的状况吗？

不会，被分到少数派分区的 Leader 会发现日志不能同步到大多数节点，从而不能提交任何日志。一种优化是，如果一个 Leader 继续不能分割到少数节点，就主动变为 Follower。

当集群中有些 Peer 宕机后，此时的“多数派”是指所有节点的少数，还是指存活节点的少数？

所有节点的少数。比方集群总共有五个 Peer，则多数派永远是指不低于 3 个 Peer。

如果是后者，思考这样一个例子。集群中有五个 Peer，有两个 Peer 被分到一个分区，他们就会认为其余三个 Peer 都宕机了，则这两个 Peer 依然会选出 Leader，这显著是不合乎预期的。

选举超时距离抉择的过短会有什么结果？会导致 Raft 算法出错吗？

选举超时距离选的不好，只会影响服务的可用性（liveness），而不会影响正确性（safety）。

如果选举距离过小，则所有的 Follower 可能会频繁的发动选举。这样，Raft 的工夫都耗在了选举上，而不能失常的对外提供服务。

如果选举距离过大，则当老 Leader 故障之后、新 Leader 入选之前，会有一个不必要的过长期待。

为什么应用随机超时距离？

为了防止多个 Candidate 始终呈现平票的状况，导致始终选不出主。

Candidate 能够在收到多数票后，不等其余 Follower 的回复就间接变成 Leader 吗？

能够的。首先，多数票就足够成为主了；其次，想等所有票也是不对的，因为可能有些 Peer 曾经宕机或者产生网络隔离了。

Raft 对网络有什么假如？

网络是不牢靠的：可能会失落 RPC 申请和回复，也可能会经验任意提早后申请才达到。

但网络是有界的（bounded）：在一段时间内申请总会达到，如果还不达到，咱们就认为该 RPC 失落了。

votedFor 在 requestVote RPC 中起什么作用？

保障每个 Peer 在一个 Term 中只能投一次票。即，如果在某个 term 中，呈现了两个 Candidate，那么 Follower 只能投其中一人。

且 votedFor 要进行长久化，即不能说某个 Peer 之前投过一次票，宕机重启后就又能够投票了。

即便服务器不宕机，Leader 也可能会上台吗？

是的，比如说 Leader 所在服务器可能 CPU 负载太高、响应速度过慢，或者网络呈现故障，或者丢包太重大，都有可能造成其余 Peer 不能及时收到其 AppendEntries，从而造成超时，发动选举。

如果 Raft 进群中有过半数的 Peer 宕机会产生什么？

Raft 集群不能失常对外提供服务。所有残余的节点会一直尝试发动选举，但都因为不能取得多数票而入选。

但只有有足够多的服务器恢复正常，就能再次选出 Leader，持续对外提供服务。

请简略说说 Raft 中的选举流程？

所有的 Peer 都会初始化为 Follower，且每个 Peer 都会有一个内置的选举超时的 Timer。

当一段时间没有收到领导者的心跳或者没有投给其余 Candidate 票时，选举时钟就会超时。

该 Peer 就会由 Follower 变为 Candidate，Term++，而后向其余 Peer 要票（带上本人的 Term 和最初一条日志信息）

其余 Peer 收到申请后，如果发现 Term 不大于该 Candidate、日志也没有该 Candidate 新、本 Term 中也没有投过票，就投给该 Term 票。

如果该 Peer 能收集到多数票，则为成为 Leader。

如果所有 Peer 初始化时不为 Follower、而都是 Candidate，其余局部放弃不变，算法还正确吗？

正确，然而效率会变低一些。

因为这相当于在原来的根底上，所有 Peer 的第一轮选举超时是一样：同时变为 Candidate。则谁都要不到多数票，会节约一些工夫。之后就又会变成原来的选举流程。

如何避免出现网络分区的 Peer 复原通信时将整体 Term 推高？

问题解释：如果某个 Peer（咱们无妨称其为 A）和其余 Peers 隔离后，也就是呈现了网络分区，会一直推高 Term，发动选举。因为继续要不到其余 Peer 的票，因而会继续推高 Term。一旦其之后某个时刻复原和其余 Peer 的通信，而因为 Term 是 Raft 中的第一优先级，因而会强制以后的 Leader 上台。但问题是，因为在隔离期间日志被落下很多，Peer A 通常也无奈成为 Leader。最终后果大概率是原来的 Leader 的 Term 被拉上来之后，从新入选为 Leader。有的人也将这个过程形象的称之为“惊群效应”。

解决办法：PrevVote。每次 Candidate 发动选举时，不再推高 Term，然而会拿着 Term+1 去跟其余 Peer 要票，如果能要到非法的票数，再去推高 Term（Term+1）。而如果能要到多数票，其实就保障该 Candidate 没有产生网络隔离、日志是最新的。如果要不到多数票，就不能推高 Term，这样会保障产生了网络隔离的 Peer 不会始终推高本人的 Term。

Raft 和 Paxos 有什么区别？

首先，Raft 和 Paxos 都是共识协定，而所有的共识协定在原理上都能够等价为 Paxos，所以才有共识协定实质上都是 Paxos 一说。

如 Raft 论文中提到的，Raft 是为了解决 Paxos 了解和实现都绝对简单的问题。将共识协定拆成两个绝对独立的过程：领导者选举和日志复制，以升高了解和实现的复杂度。当然，如果要想工程可用，Raft 的优化也是无止境的大坑，也并非像论文宣称的那么简略。因而，有人说，Raft 看起来简略只是因为论文叙述的更分明，而非算法自身更为简洁。

Raft 其实是和 Multi-Paxos 等价，因为 Paxos 只解决单个值的共识问题。

Raft 和 Paxos 的角色分法也不太雷同，Raft 的每个 Peer 都能够有 Leader，Candidate 和 Follower 三种状态；而 Paxos 是将零碎分为 Proposer，Acceptor 和 Learner 三种角色，实现时能够按需组合角色。

在 Paxos 中，一旦某个日志在少数节点存在后就能够平安的提交；但在 Raft 中，不总是这样，比方一条日志在少数节点中存在后，但不是以后 Leader 任期的日志，也不能进行间接提交；而只能通过提交以后任期的日志来间接提交。

在 Paxos 在选举时，Leader 可能须要借机补足日志，但 Raft 中选举过程齐全不波及日志复制（这也是 Raft 进行拆分的初衷）。这是因为 Raft 只容许具备最新日志的 Candidate 成为 Leader，而 Paxos 不限度这一点。

在 Paxos 中，容许乱序 commit 日志，而 Raft 只容许程序提交。

在 Paxos 中，每个 Peer 的 term 是不统一的，全局自增的；在 Raft 中 term 是每个 Peer 独立自增的，但须要对齐。

更多区别，能够参考文末给出的材料。

Raft 在工程中有哪些常见的优化？

因为领导者选举是个低频操作，次要 IO 门路优化还是集中在日志同步流程上。

• batch：Leader 每次攒一批再刷盘和对 Follower 进行同步。升高刷盘和 RPC 开销。
• pipeline：每次发送日志时相似 TCP 的“停 - 等”协定，收到 Follower 确认后才更新 nextIndex，发送前面日志。其实能够改成流水线式的，不等后面日志确认就更新 nextIndex 持续发前面的。当然，如果前面发现之前日志同步出错，就要回退 nextIndex 重发之前日志——而原始版本 nextIndex 在 同步阶段 是枯燥递增的。
• 并行 append：Leader 在 append 日志到本地前，就先发送日志给所有 Follower。

请简略形容基于 raft 的分布式 KV 零碎的架构？

一个基于 raft 的分布式 KV 零碎，实际上是由一组应用 raft 算法进行状态复制的节点组成。客户端会抉择将申请发送到 Leader 节点，而后由 Leader 节点进行状态复制，即发送日志，当收到少数的节点胜利提交日志的响应之后，Leader 会更新本人的 commitIndex，示意这条日志提交胜利，并且 apply 到状态机中，而后返回后果给客户端。

以上是单个 raft 集群的分布式 KV 零碎架构。

如果零碎中数据量较大，一个 raft 集群可能无奈接受大量的数据，性能也会受到影响。因而还基于此设计了可分片的分布式 shardkv 零碎。shardkv 由多个 raft 集群组成，每个集群负责一部分 shard 数据。

Shard 到 raft 集群的映射关系，保留在独立的配置服务中。

分布式系统中读数据的流程是什么样的，如何优化？

为了保障线性一致性，目前的实现是利用了 raft 算法，将读申请传入到 raft 并进行状态复制，这样可能保障读到的数据肯定是最新的。

然而因为读申请也进行了一次日志复制，执行效率会受到影响，业界罕用的两种优化形式是 ReadIndex 和 LeaseRead。

线性一致性和 Raft

查看更多

https://www.sofastack.tech/blog/sofa-jraft-linear-consistent-…

客户端发送申请的时候，如何晓得集群中的 Leader 节点是哪个？

在没有任何前置条件的状况下，客户端会轮询集群中的每个节点并发送申请，如果非 Leader 节点收到申请，会返回一个谬误给客户端。客户端而后筛选下一个 server 进行重试，直到失去了正确的响应。

而后会将 Leader 节点的 id 保存起来，下次发送申请的时候，优先选择这个节点发送。

如果 raft 集群的 Leader 节点产生故障，客户端如何解决？

对于一个可容错的分布式 KV 零碎，须要可能应答这种故障产生，并且在少数节点失常的状况下，须要仍然提供服务。

得益于 raft 共识算法的个性，在某个节点故障后，其余节点会因为收不到心跳音讯而超时，并从新发动选举。

所以客户端会在得不到失常响应的时候轮询重试，直到 raft 集群中的 Leader 节点从新选举实现并提供失常服务。

如何解决客户端的反复申请？

如果客户端的申请曾经提交，然而 server 返回的过程中后果失落，那么客户端会发动重试，导致这个申请在状态机中被执行了两次，会违反线性一致性。

因而咱们须要保障客户端的申请只能被状态机利用一次，咱们能够保护一个去重哈希表，客户端 ID + 命令 ID 组成一个惟一的标识符，如果判断到命令是曾经被执行过的，则间接返回对应的后果。

Shardkv 的问题：为什么须要对分布式 KV 零碎进行分片？

一是单个 raft 集群理论存储数据的引擎是单机的，可能存储的数据量无限。二是在不分区的状况下，所有数据的读写申请都会在一个分片中，这在并发量较大的状况下可能存在肯定的瓶颈。

如果对数据做了分区，那么不同分区之间的数据读写申请是能够并行的，这可能较大的晋升 KV 零碎的并发能力。

Shardkv 的配置怎么保留？

Shardkv 的配置是独自保留在一个服务中，客户端会向这个服务发动申请，查问 key 所属的 shard 应该在哪个 raft 集群中，并向这个集群发动申请。

配置服务也须要高可用个性，因为配置服务如果产生故障不可用的话，那么整个分布式 kv 服务都会无奈提供服务，因而也应用 raft 算法保障高可用，构建了一个单 raft 集群来存储配置信息。

Shard 数据如何迁徙？

启动一个后盾定时工作，定期从配置服务中获取最新的配置，如果检测到配置产生变更，则变更对应 shard 的状态，标记为须要进行迁徙。

同时启动另一个后盾定时工作，定期扫描 shard 的状态，如果检测到须要进行迁徙的 shard，则发送音讯，通过 raft 模块进行同步。而后在 Leader 节点中解决 shard 迁徙的申请，将 shard 数据从原所属的 raft 集群中迁徙到新的集群中。

Shard 迁徙的时候，客户端的申请会受到影响吗？

如果客户端申请的 key 所属的 shard 并没有在迁徙中，那么能够失常提供服务。

否则，阐明客户端申请的 key 在迁徙中，则返回谬误，让客户端进行重试。

如果有并发的客户端申请和 shard 迁徙申请，应该怎么解决？

客户端申请和 shard 迁徙申请确实存在并发状况，如果解决程序不统一，会违反线性一致性。

咱们将 shard 迁徙的申请也传入到 raft 模块进行同步，这样和客户端的申请是统一的，利用 raft 的一致性来保障两种不同申请的先后顺序，后面的执行后果肯定对后续的申请可见。

如果某个 Shard 曾经迁徙了，那么它还会占存储空间吗？

不会，咱们实现了 shard 清理的残缺流程，会启动一个后盾定时工作，定期扫描 shard 的状态，如果检测到 shard 是须要进行清理的，则也会发送 shard 清理音讯进行解决。

参考资料

1. Paxos vs Raft：https://ics.uci.edu/~cs237/reading/Paxos_vs_Raft.pdf
2. TiKV Raft 的优化：https://zhuanlan.zhihu.com/p/25735592
3. Raft FAQ：https://pdos.csail.mit.edu/6.824/papers/raft-faq.txt

本文由 mdnice 多平台公布