分布式系统至今是一个复杂混沌的问题，背景为近些年互联网需要为越来越多的用户提供服务，单个节点难以实现这些功能，为保证安全性、稳定性等目标因而构造出了分布式系统

该课程共需要完成四次编程实验：

• mapreduce
• replication using raft
• replicated K/V service
• sharded K/V service

其中后三个实验是循序渐进的

在分布式系统中有三个需要考虑的问题：容灾性（可用性和恢复）、持久性和性能（吞吐量、延迟），在一定情况下，三种问题无法完全同时解决

map reduce

用于解决多机计算时的故障问题

map reduce核心为两个步骤，map和reduce步骤（这里的reduce理解成归约）。一个简单的例子

对于一个字数统计功能，每个设备$f_1,f_2,f_3$都在本机做完map操作得到键值对，之后再通过一个shuffle的reduce操作对键值数据进行统计从而实现一个字数统计功能，其中成本最高的地方在于shuffle步骤的通信

mapreduce article 2004

map reduce的核心代码如下：

map负责统计键值，而reduce负责接受值和键进行规约。由于网络问题或故障问题，map操作和reduce操作可能并不一定只运行一次

可能存在的问题：

• 协调器故障，这种故障往往会带来更加严重的问题，但是我们在目前的状态暂且不考虑该问题（相较于上千个节点，协调器出现问题的可能性更小）
• 机器慢速（stragglers），当一些机器运行速度过慢时，协调器会控制这些机器上的任务到其他机器上进行运算

mapreduce论文解读

https://cuddly-myth-7ee.notion.site/map-reduce-e0238995041040a3a4d21b0d0db5625e?pvs=4

RPC and Thread

go语言可以非常轻易的构建线程，由于其线程成本较小，因此在能满足条件的情况下应考虑尽可能地使用线程。

使用go -race参数来捕捉竞争问题。

go可以通过两种方式进行条件控制：通道、条件变量

RPC远程过程调用，类似本地的过程调用，RPC只不过是客户端与服务器之间发生的：

https://zideapicbed.oss-cn-shanghai.aliyuncs.com/img/image-20230607143327158.png

RPC往往可能遇到两种问题：

• at-least-once 即客户端发送的请求由于网络因素并未接收到、或是服务器暂时宕机导致未接收到请求
• at-most-once为由于网络原因导致服务器端接收到了一个服务器的两个请求，因此需要做去重处理

GFS

指的是一个文件系统，用于提高本地程序的效率。但是设计起来难度很大：

• 需要高性能：对跨服务器数据分片（mapreduce）
• 多服务器：可能会有机器故障
• 高容错：需要数据备份
• 数据备份：数据一致性
• 强异质性：持久性

GFS实现了一个很优秀的存储系统，能够较好的协调一致性、复制和持久性，但是其同样有不符合标准的地方：只有一个主节点和不能完全保持一致性。

GFS具有非常强大的优点：数据庞大、快速、所有软件共享、高容错。

总体结构非常容易理解：

• 软件向master节点询问数据位置
• master节点向其告知数据块句柄和位置
• 软件并行的从不同GFS服务器中获取数据

其中master节点实现了从文件名到文件句柄块数组的映射 而文件句柄块包含了版本、块列表服务器等相关信息。为了防止master节点崩溃，每过一段时间其自己也会创建一个检查点。

知道了master节点所具有的功能，上述的功能数据中， 文件名到句柄的映射、文件句柄号的版本信息需要进行存储。

对于一个文件系统，需要注意的问题就是读取和写入数据。读取文件的操作如下：

• 客户端向master节点询问 文件+偏移量对应的数据块句柄
• master向客户端发送数据块句柄、服务器列表和版本号
• 客户端缓存这些数据（为了避免多次与客户端交互而增大网络延迟）
• 客户端从最近的服务器寻求相关数据
• 如果服务器查看版本正确就发送数据

写数据：

对于写数据（之所以强调增加操作，是因为mapreduce操作中的reduce操作绝大多数是添加数据而不是修改数据），操作如下：

• 与读数据相同，先获得了对应的句柄数据、以及到对应服务器的表
• master从所有可用的服务器中选择一个作为Primary，其余的为secondary，之后为s和p增加版本号，s和p把版本号写到磁盘中并告知master，master节点做相同的操作
• 客户端向p和s发送数据，检查有效期和版本，之后写到对应的偏移量中，之后把数据写道稳定存储中然后向s发消息

接下来就要考虑一致性的问题了：由于同一块数据可能由于网络延迟问题导致在不同的机子上出现p，因此设计了有效时间，当有效时间到达，对应的p就会歇掉、

那么如何获得很强的一致性，即对所有的p进行更新或对所有的p都不更新。

主从数据复制

什么情况下会产生复制的失败：

• Fail-stop failures 这种情况通常是指遇到较大问题导致直接计算机系统停机，因而不会发生其他奇怪事情。通常一种做法就是当出现一些轻微故障时对服务器进行断电操作以防止产生更加严重的影响。
• 逻辑错误，配置错误
• 恶意错误

因为需要讨论的情况过多，所以我们通常先考虑第一种情况，尽管如此其还是可以分为很多类别。

• p节点是否失败（当master无法与p连接但是p此时仍正常运作时）：这里需要设计一个split-brain系统，

• 保持主备同步，即使p节点崩溃，master向p提供的数据也需要是最新的

• 故障转移：在发生故障之后进行主备的转移（备机接管）

关于故障转移的挑战通常有两种解决方案：1、进行状态的迁移（每次p发生变化都把对应的记录发送给所有的backup节点从而方便的实现迁移）。2、复制状态机RSM，相较于复制变更，把操作发送过去。通常情况下使用的就是第二种。

对于复制状态机，需要用到的一种机制是VMware提出的VM FT（虚拟机监视器），这部分决定什么操作需要给硬件处理：

这里的VM-FT做了两件事，第一件事是控制什么中断需要硬件处理，第二件事是向备机做日志保存。当需要外界数据通讯时，VM-FT接受虚拟机的数据并通过虚拟网卡进行转发操作。

当p和备机或是与master节点断开连接时，此时就要执行前面的Fail-stop操作，立刻中断操作以防止带来问题。

为了控制两台主机的状态完全相同，需要控制起始点-指令-数据都完全相同，这里采用的解决方案是当p的VM-FT接收到一定数量的指令（100）条时向备机的VM-FT发送中断数据以及数据。但是对于一些非确定性指令，例如获取时间的指令，FT将会模拟执行指令，之后将发生变化的数据发送给备机

除此之外还有一种情况，如果在100条指令中间p崩溃了，但是有些改动未同步到b上。此时，如果p向b发送变动修改，如果未接收到b的回复，则其不会向客户端发送数据。

但是带来的问题就是，每次p都需要等待b发送过来的数据，从而造成性能上的下降：