序

这个暑假开个新坑，学习一下分布式系统。

之前和 AI 聊过很多次，关于我的兴趣，所谓的「大规模复杂系统的稳定性」，其实想想，本质上就是传统的分布式系统。毕竟，分布式系统这个领域考虑的问题之一就是系统的容错，包括可用性和从错误中恢复。

MIT 6.824 是一门研究生核心课程，以论文和实验为核心，讲述分布式系统的抽象与实现。我想，在大三升大四的阶段，学习这样一门课比较合适，因为已经掌握了绝大多数本科水平的计算机知识。

网站上有疫情时期课程录像，可以学习。的不知道会不会把坑填完，慢慢来吧。

Intro

什么是分布式系统

首先，讨论什么是分布式系统。它的核心是四个关键词：

  • 许多
  • 通过网络连接
  • 协作的
  • 计算机

既然是分布式系统，自然有许多机器。这些机器之间需要连接，才能组成一个系统，因此网络出现在其中。它们需要相互合作来达成任务，否则，就是孤岛，没有系统什么事了。最后，组成分布式系统的是一群计算机。

为什么需要分布式系统

人们构建分布式系统出于以下几个目的：

  • 将物理分隔开的机器连接起来，达成共享的目的（如多拷贝的集群文件系统）；
  • 通过并行提升处理速率（人多力量大）；
  • 容错（防止单点故障，主备切换）；
  • 通过隔离确保安全（所有密钥单独存储在一个机器上，只需要保卫这台机器）。

难点

分布式系统能带来上面所说的种种好处，不是免费的午餐，难点是：

  • 存在许多并发的部分；
  • 必须处理局部故障的情形；
  • 想要发挥性能优势很困难。

具体阐述一下，人类的大脑生来不擅长处理并发任务（ADHD 除外），所以在大脑中建立一个并发模型，天然是困难的。

以及，既然是分布式系统，很可能系统中某一群机器失效，例如这个机器所在的交换机坏掉了。但是，整个系统不能因为局部失效就停摆，怎样处理这种局部故障的情形？

最后，分布式系统中的机器，能力差异或许很大，此外，统筹协调它们也需要开销。因此，想要实现 1 + 1 > 2 的效果，并没有那么容易。

历史视角

从历史的角度来看，分布式系统一直在发展。

在 80 年代，分布式系统主要在 LAN 中，比如 AFS 这个文件系统，以及整个互联网范围的 DNS、邮件服务等；90 年代，数据中心和大型网站出现了，网页搜索和网购对分布式系统有了新的要求；21 世纪初，云计算的出现让许多企业和个人把算力移动到云端，云服务商对分布式系统有更高的要求（这是我小学时课本上宣传的关键词）。

现如今，随着人工智能的兴起，我们需要使用千卡、万卡集群来完成训练。如何优化这里的性能瓶颈？怎样处理 GPU 失效的情况？这是我们现在要考虑的问题。

为什么上这门课

  • 有趣——困难的问题，但是有强大的解决方案；
  • 在现实世界中起到作用；
  • 研究的热门领域；
  • 可以亲自上手体验。

我想，第四点对我来说是最有吸引力的地方。诚然，炼丹，训练一个大模型，并让它在某些数据集上获得性能提升，这种数字变化对那些数字敏感同学很有成就感。但在我看来，还是上手搭个系统更有趣一些。

正题

Focus

聚焦 3 个板块：存储、计算与通信，其中核心是抽象。

主要的目标是，通过抽象的方法，隐藏分布式的复杂度。

Main Topics

首先，聚焦容错，也就是我所说的系统的稳定性。

在一个几千台服务器的集群中，总有机器损坏，怎样才能对应用层屏蔽底层的失败？

我们希望的容错有两方面的含义：

  • 可用性。即使存在失败，应用程序还可以运行；
  • 可恢复性。当错误被修复后，应用能够自我重启，正常运行。

为了达到可用性，核心想法是有多个服务器的副本。如果一个服务器出了故障，还可以使用其他的服务器。

不过，这一目的很难达到，比如，服务器可能没有故障，而是短暂时间无法从监控系统 ping 通，但是仍然在服务客户端。

而达到可恢复性，需要一些日志和事务的记录，这样可以在出现故障时，回放过去的操作。一些数据库就是这样处理崩溃的。

第二个主题是一致性。现在有这么多台机器，怎么才能保证它们对外像一台机器一样，不会存在冲突或不一致性？

比如，最近 Put(k, v) 很多次，希望执行 Get(k) 能返回最后一次 Put 的内容。如果这是一台机器，没问题，如果是并发执行的，那就无法保证了。

毕竟，如何同步许多台机器之间的信息呢？这里有同步的时延，而且根据 CAP 定理，在分布式系统中，如果既希望 Consistency 又希望 Patition-Tolerance，那只能牺牲一定的可用性了。

第三个主题是性能，目标是让吞吐率 scalable，可扩展。如果我有 $Nx$ 台服务器，我希望的是 CPU、磁盘、网络等多个组件能有 $Nx$ 被的吞吐率放大。

但是，愿望没有那么容易实现，我们会遇到：

  • 负载不均衡、掉队者以及长尾时延；
  • 无法并行化的代码，如初始化和交互；
  • 共享资源的瓶颈，如网络。

此外，有的问题并不能简单的用扩展的方法解决。例如，加快一个用户请求的处理速度，或者所有用户想要更新同一份数据（加锁）。这通常要求更好的设计，而不是无脑上更多电脑。

以及，上述容错、一致性、性能之间存在 trade-off。

这就是 CAP 定理所阐述的内容，三个字母最多只能达到两个。

排列组合一下，希望 CA，一致性和可用性，那么，就一台机器吧，假设机器不失败，那就一份数据，没有不一致性，也是高可用的。

希望 CP，一致性和可隔离，在北京和上海各一个数据中心，还希望每时每刻数据都一致，那在数据同步的时候，就要牺牲一下可用性，暂停服务，确保数据的一致。

希望 AP，可用性和可隔离，北京和上海两个数据中心，希望一直可用，那就没有停机的时间了，边服务边同步吧，可能会存在一定的数据不同步。

例如，jyy 在课上举的例子，你微信朋友圈拉黑你妈，在腾讯的北京数据中心操作的，而你妈在深圳。就算拉黑后，集群之间如果没有保证一致性，那你妈还是能看到你朋友圈的内容，直到数据定期同步。

回到这里的 trade-off，强容错对通信的要求很高，例如把数据发送给备份服务器；强一致性也要求通信，例如，Get 必须检查最新的 Put。通信就成为了性能瓶颈。

很多设计，都只保证了弱一致性，从而提升速率。例如，Get 在语义上并不一定保证是最新的 Put。再如小红书的笔记点赞数不一定是最新的。这对于应用程序员来说是很痛苦的，但是很好的 trade-off。

最后，一个系统总要实现，涉及到 RPC、线程和并发控制。实验用来完成这一目标。

案例：MapReduce

这门课以经典的 MapReduce 论文作为第一篇 case study。

背景

这篇文章的背景是，Google 存在需要花很多时间才能完成的大数据处理任务，例如网页索引。

目标是让那些不是分布式系统专家的用户能容易的写出处理代码。

实现手段有二：

  • 通过简化模型，限制了 map 和 reduce 两个处理函数的抽象；
  • 让 Master 结点处理任务分配。

流程

流程图

论文原图解释的很清楚。再叙述一下整体的流程吧。

  1. 首先，用户编写好 Map 函数和 Reduce 函数，指定输入文件位置，并调用 MapReduce 框架；
  2. 框架将 worker 进程分发到每个 worker 服务器上（服务器上一般只有一个 worker 进程），其中一个进程比较特殊，作为 Master 进程；
  3. 框架同时会把输入切分成 $M$ 个小块，当然，其实 GFS 本身已经把输入切分成小块了，或许这步并不需要。$M$ 表示 Map 进程的数量；
  4. 每个 Map 进程读取自己的那份数据，并做处理，将中间结果写入到本地磁盘中。中间结果通过哈希函数分别写入到 $R$ 个文件，$R$ 表示 Reduce 任务的数量；
  5. 从第一个 Map 任务完成开始，中间结果就开始从 Map 进程所在的机器传送给 Reduce 进程所在的机器，并做排序。这一步是大量网络通信出现的位置；
  6. 当一个 Reduce 任务获取其所有需要的中间结果后，它开始运行，并将结果写入到全局的 GFS 中；
  7. 最终，我们得到 $R$ 份在全局文件系统中的结果文件，且每个文件内部是有序的。

示例：WordCount

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Abstract view of a MapReduce job
  input is (already) split into M files
  Input1 -> Map -> a,1 b,1
  Input2 -> Map ->     b,1
  Input3 -> Map -> a,1     c,1
                    |   |   |
                    |   |   -> Reduce -> c,1
                    |   -----> Reduce -> b,2
                    ---------> Reduce -> a,2
  MR calls Map() for each input file, produces set of k2,v2
    "intermediate" data
    each Map() call is a "task"
  MR gathers all intermediate v2's for a given k2,
    and passes each key + values to a Reduce call
  final output is set of <k2,v3> pairs from Reduce()s

Example: word count
  input is thousands of text files
  Map(k, v)
    split v into words
    for each word w
      emit(w, "1")
  Reduce(k, v)
    emit(len(v))

例子引自课程的 notes。这里有 3 个 Map 任务和 3 个 Reduce 任务。

每个 Map 任务 emit 单词和数值 1 这个 KV pair，并分别存储到（最多）3 份文件中。之后，每个 Reduce 任务从 Map 任务的中间文件取得自己的那份，排序并合并，最终得到每个单词的次数。

小巧思

整个工程设计包含了很多妙处，如：

  • 容错；
    • 如果 worker 失联，则其上已经完成的 Map 任务需要重新跑，进行到一半的 Map/Reduce 任务也需要重新跑；
    • 但对于已经完成的 Reduce 任务，如果 worker 失联，不必重跑，因为已经反映到全局文件系统上了；
  • 局部性：尽量将 Map 任务放到距离任务的输入数据近的位置，从而节省网络带宽；
  • 任务数量多于 worker 服务器数量，这样可以实现负载均衡（能者多劳）；
  • 在一个 MapReduce 任务即将完成时，Master 把每个待完成的任务分配给多个 worker（有点类似于让流水线不要中断）。

除此之外，还有一些工程的优化问题，不再赘述了。