type
status
date
slug
summary
tags
category
icon
password
00 | Lab 4 整体介绍
在 Lab 2 中我们实现了 Raft 协议，保证了多个节点之间的步调一致，Lab 4 的任务就是在 Lab 2 的基础上，实现一个分片 KV 存储系统。不幸的是，Lab 4 的难度相比 Lab 2 更上了一个台阶。Lab 2 虽然实现起来琐碎繁杂，但是 Raft 论文已经将实现步骤和细节嚼碎了喂到我们嘴边。然而，对于 Lab 4，我们没有现成的资料，需要自己思考如何实现系统的所有功能。但幸运的是，我们不需要从零开始，Lab 4 已经为我们搭好了框架。虽然只是一个外壳，里面仍是空空如也，但有总比没有好，不是吗？接下来，我会简单介绍一下这个框架，但是在此之前，我们需要先搞清楚三个基本问题。
- 什么是「分片」？
我们可以将所有键值对分组，每一组就是一个分片。分组的策略有很多，比如，以 key 的开头字母为依据，所有「a」开头的键值对组成一个分片，所有「b」开头的键值对组成另一个分片，以此类推。
- 分片如何存储？
为了提高系统的可用性，提供容错保障，每一个分片只存储在一个副本组中，而一个副本组则可以存储多个分片。一个副本组由多台服务器组成，服务器之间通过 Raft 协议保证彼此之间的状态保持一致。这么一来，只要组中的大多数服务器存活且可以互相通信，这个组就可以持续处理客户端请求。
- 为什么要分片？
为了提高系统的吞吐量。如果不进行分片，那么所有键值对都存储在一个副本组中，难以并行处理多个键值对的读写请求。相反，将键值对分片处理后，假设分片 A 存储在副本组 R1 中，分片 B 存储在副本组 R2 中，那么，对分片 A 和分片 B 中键值对的请求就会由各自的副本组处理，因为不同的副本组彼此独立，因此可以并行处理，从而提高吞吐量。
好了，搞清楚上面三个基本问题后，让我们来看看 Lab 4 搭建好的系统框架。框架的整体结构如下图所示：
可以看到，整个系统包含两个部分：分片控制器（The Shard Controller）和副本组（Replica Group），每个部分都有各自的客户端（Client）。分片控制器负责决定分片和副本组之间的分配关系，当一个分片被分配给一个副本组时，意味着由这个副本组负责该分片的存储和读写请求。分片控制器会将这种分配关系保存在配置（Config）中。通过获取最新的配置，客户端可以知道对一个分片中的键值对进行读写时，应该向哪个副本组发出请求，每个副本组则可以通过配置得知自己目前所负责的所有分片，对这些分片的读写请求进行处理。值得注意的是，分片控制器和副本组都由多台服务器组成，这些服务器之间通过 Raft 协议通信，以提供系统的容错性。
除了上面提到的分片分配、存储和读写请求等功能，Lab 4 还有额外的要求：
- 数据读写需要保证线性一致性。（关于线性一致性的解释，可以参考文章《条分缕析分布式：浅析强弱一致性》）
- 分片和副本组之间的分配关系需要考虑动态负载均衡。副本组可能会加入或离开系统，此时需要重新调整分配关系，尽可能平均地将分片分配给系统中的所有副本组，同时，还应该尽可能减少分片的变动。
- 副本组之间需要互相迁移分片数据。由于分片会进行重新分配，因此副本组需要从其他副本组获取最新分配给自己的分片数据，同时也需要将自己不再负责的分片数据传输给对应的副本组。
同时，Lab 4 保证分片数量不会改变，只有副本组的数量会变。
看到这里，相信我们已经对 Lab 4 有了一个简单的认识，和系统的整体框架一样，Lab 4 也被分为了两个部分。在 Part A 中，我们需要实现分片控制器的功能，处理分片和副本组之间的分配关系。在 Part B 中，我们需要实现副本组的功能，存储分片数据并处理读写请求。这篇文章会介绍 Part A 的实现思路，而 Part B 则会放在下一篇文章中。
01 | Lab 4A 任务目标
Part A 需要我们实现分片控制器的功能。简单来说，分片控制器就是一个高可用的配置管理器。每个配置都是一个分配方案，其中保存了每个分片被分配到了哪一个副本组，以及每个副本组各自包含的所有服务器的地址。由于副本组会被动态的增删，因此每当副本组发生变动时，分片控制器会创建新的配置，并保存之前生成的所有配置。当客户端和副本组想要查询某个配置时，调用分片控制器的查询接口即可。
分片控制器需要向外提供下面 4 个接口用于管理和获取配置：
- Join：用于管理员添加多个新的副本组。添加之后需要重新调整分配关系以负载均衡，并保存在新的配置中。
参数：
Servers map[int][]string新的副本组的 id 及其各自的所有服务器的地址。
响应：
WrongLeader bool处理请求的服务器是否是 Leader 节点。
Err Err处理请求过程中产生的错误。
- Leave：用于管理员删除多个副本组。删除之后需要重新调整分配关系以负载均衡，并保存在新的配置中。
参数：
GIDs []int被删除的副本组的 id。
响应：
WrongLeader bool处理请求的服务器是否是 Leader 节点。
Err Err处理请求过程中产生的错误。
- Move：用于管理员将一个分片指派给一个副本组。不需要再次负载均衡，但需要将新的分配关系保存在新的配置中。
参数：
Shard int分片编号。
GID int副本组的 id。
响应：
WrongLeader bool处理请求的服务器是否是 Leader 节点。
Err Err处理请求过程中产生的错误。
- Query：用于管理员、客户端和副本组查询指定的配置。不需要重新负载均衡，也不需要生成新的配置。
参数：
Num int查询的配置的 id。
响应：
WrongLeader bool处理请求的服务器是否是 Leader 节点。
Err Err处理请求过程中产生的错误。
Config Config查询的配置。
此外，实现上面的接口时，不要忘记还需要满足下面 2 个要求：
- 数据读写需要保证线性一致性。
- 在重新调整分配关系以实现负载均衡时，应该尽可能减少分片的变动。
02 | Lab 4A 实现思路
现在，我们已经明确了我们需要完成的工作：实现 4 个接口，同时满足 2 个要求。「凡事预则立，不预则废」，在开始代码实现之前，让我们思考一下如何实现上述 6 个任务。我们应该从哪里入手呢？4 个接口可以看做是对「配置」这一数据的读写操作，因此它们依赖于第 1 个要求：保证数据读写的线性一致性。那么就让我们从如何保证线性一致性开始，逐步理清我们的实现思路。
如何保证线性一致性？
在 Lab 4 的架构图中可以看到，分片控制器由多台服务器组成，它们之间通过 Raft 协议进行通信。但是，只是在系统底层应用了 Raft 协议就可以保证线性一致性吗？答案是否定的。Raft 是一个共识算法而不是线性一致性算法，它只能保证系统中的服务器可以按照相同的顺序执行相同的指令，进而保证每台服务器中保存的数据最终会趋于相同，但是这只是站在了服务器的角度来保证数据一致。线性一致性更多的是站在外部用户的角度对数据一致性所提出的要求，需要分布式系统在用户的眼中表现得好像单机一样，用户读取一个对象的值时，得到的必须是该对象最近一次被写入的值。因此，要保证线性一致性，需要在上层做进一步的处理。
接下来，我们会讨论一些特殊情况，以此说明我们应该如何保证线性一致性，但是在此之前，先介绍一下这些情况的背景。我们的系统由 3 个服务器组成，它们之间通过 Raft 通信，分别是 S1（Leader）、S2（Follower）和 S3（Follower）。我们要写入的对象是变量 x，x 的初始值是「A」。用户通过客户端向系统发送请求，请求可能会被发送到系统中的任意服务器。
我们先从最简单的写请求开始。显而易见，对于客户端的写请求，因为涉及到了数据的修改，所以系统必须通过 Raft 让这条写请求在服务器间达成共识，以保证大部分服务器都会执行这条写指令（注意，每个服务器执行的时间可能是不同的），进而保证服务器中的数据相同。由于只有 Leader 节点有资格在 Raft 中发起日志同步，因此只有 Leader 可以接受写请求，Follower 节点会拒绝该请求。
那么对于读请求呢？读请求不涉及数据的修改，可以直接通过非 Leader 节点读取数据吗？让我们考虑这样一个情形，客户端向系统发送了一个写请求，请求将变量 x 的值修改为「B」，请求被分流到了 Leader 节点，也就是 S1，在这个请求达成共识后，S1 将 x 修改为 「B」并返回了「执行成功」的响应，但是 S2 和 S3 都还没有执行。客户端收到「执行成功」的响应后，接着向系统发送了一个读请求，请求读取 x 的值，这次这个请求被分流到了 S2，由于此时 S2 还没有执行之前的写请求，因此 S2 中 x 的值仍为「A」。如果此时 S2 直接返回 x 的值，那么客户端就会收到 x 的旧值「A」，从而违背了线性一致性。究其原因，是因为在上面的情形中，读请求本应在写请求之后执行，但实际上读请求却发生在了写请求之前。因此，在执行读请求之前，我们需要保证之前的写请求都已经执行了才行。实现方式有很多，其中最简单的实现方式，就是读写请求都通过 Leader 节点受理，等到请求通过 Raft 共识后再执行，目前让我们采用这种方式。
在系统正常运行的情况下，上面的实现方式已经可以保证线性一致性，但是分布式的恐怖之处就在于系统并不总是正常的。考虑下面这样的情况，客户端向系统提交了写请求 W1，但是客户端迟迟没有收到系统的响应，于是客户端进行了重试，再次发送了 W1 请求。现在，让我们看看中间可能发生的情况：
- 第一次请求的消息丢失，系统未执行请求。在这种情况下，即使客户端重发了请求，请求仍只被执行了一次。
- 第一次请求的消息未丢失，系统执行后，响应消息丢失。那么请求被重发后，系统会再次执行请求，请求被执行两次。
可以看到，请求可能会被执行一次，也可能会被执行两次，如果重试的次数变多，执行的次数可能会更多。如果请求不是幂等的，那么可能会造成严重的问题。那么如果请求是幂等的呢？是不是就不会有问题了？很遗憾，如果我们的目标是保证线性一致性，即使是幂等的请求仍无法达成目标。比如下面这一个场景，x 的初始值为「A」，现在有两个客户端 C1 和 C2，C1 发送了幂等的写请求 W1-1 执行
put(x, “B”) ，在等待响应的同时，C2 发送了读请求 R2-1 get(x) 并收到响应，随后 C2 发送了写请求 W2-1 put(x, “C”)，收到响应后，C2 发送了读请求 R2-2 get(x) 。根据线性一致性的定义，C2 两次读请求的结果可以是 (B, C) 、(A, C) 、(A, B) 和 (A, C) 。但是，如果 W1-1 发生了重试，那么 C2 的结果可能是 (B, B) ，R2-1 的结果为「B」，意味着 W1-1 已经执行且发生在 R2-1 之前，后续不会再执行，而 R2-2 的结果仍为「B」，说明 W1-1 在 W2-1 和 R2-2 之间又执行了一次，这就违背了线性一致性。因此，无论请求是幂等还是非幂等的，无论请求在 Raft 中被同步了多少次，我们都需要保证请求只被执行一次。解决方案也十分容易理解：给每个客户端一个唯一标识，在客户端中，每个请求也有一个唯一的 id，这两个标识可以唯一确定一个请求，系统通过结果集保存每个请求的执行结果，在执行请求时，首先在结果集中查找是否是已执行过的请求，如果是，则直接返回保存的结果，如果不是，再执行请求并保存结果。
最后，总结一下应该如何保证线性一致性，主要有两点：
- 读写请求都由 Leader 节点进行处理，Leader 将请求通过 Raft 同步后再执行。
- 为每一个请求增加一个唯一标识，系统通过该标识保证请求只被执行一次，执行请求后保存请求的标识及结果。
实现 4 个接口
为了保证线性一致性，4 个接口在实现时有相同的算法框架：
- 将请求提交给 Raft 进行同步。
- 同步成功后执行接口功能。
- 将请求的标识符和执行的结果保存在结果集中。
- 将结果发送给客户端。
其中第 2 步需要我们根据接口的类型采用不同的实现。
Query 最为简单，只需要返回指定的配置。
Move 会创建一个新配置，随后将旧配置中的分配关系拷贝到新配置中，最后在新配置中将指定的分片分配给指定的副本组。
Join 的思路是，在负责分片数较多的副本组中，取一部分分片交给新加入的副本组。算法如下：
- 创建一个新的配置。
- 将旧配置中的分配关系拷贝到新配置中。
- 将接口参数中的新副本组加入到新配置中。
- 计算新配置中每个副本组应该负责的平均分片数。如果不能平均分配，则优先让 id 较小的副本组多负责一个分片，即前半部分副本组的分片数为「平均数 + 1」，后半部分副本组的分片数为「平均数」。比如 5 个分片，3 个副本组，则每个副本组负责的分片数依次为 2、2、1。
- 遍历所有副本组，如果一个副本组当前的分片数大于平均分片数，将多出的分片分配给新加入的副本组。
Leave 的思路是，将被删除副本组的分片一一分配给其他副本组。算法如下：
- 创建一个新的配置。
- 将旧配置中的分配关系拷贝到新配置中。
- 除了被删除的副本组，将其它副本组按照 id 从小到大的顺序排序。根据 Join 的算法可知，id 较小的副本组可能会多负责一个分片。
- 找到第一个分片数为之前「平均数」的副本组，以它为起点，取一个被删除副本组的分片分配给它。随后取一个分片分配给它的下一个副本组，以此类推。如果到达了最后一个副本组（id 最大），则回到第一个副本组（id 最小）。循环执行，直到被删除副本组的分片都分配给了其他副本组。
- 在新配置中删除要被删除的副本组。
- Author:LINKSEE
- URL:https://www.linksee.top//article/186f44a0-eb9d-8094-8e44-c064e0c0df9a
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
