6.5840 Distributed Systems Note —— Introduction

This is a note for the course 6.824: Distributed Systems at MIT. The course is taught by Prof. Robert Morris, Prof. Frans Kaashoek, and Prof. Nickolai Zeldovich.

一、分布式系统的驱动力和挑战

1. 分布式系统的动机

1. 更高的计算性能：大量的计算机意味着大量的并行运算，大量 CPU、大量内存、以及大量磁盘在并行的运行。
2. 容错（tolerate faults）：比如两台计算机运行完全相同的任务，其中一台发生故障，可以切换到另一台。
3. 物理分布：例如银行转账，我们假设银行 A 在纽约有一台服务器，银行 B 在伦敦有一台服务器，这就需要一种两者之间协调的方法。所以，有一些天然的原因导致系统是物理分布的。
4. 安全：有一些代码并不被信任，但是你又需要和它进行交互，这些代码不会立即表现的恶意或者出现 bug。你不会想要信任这些代码，所以你或许想要将代码分散在多处运行，这样你的代码在另一台计算机运行，我的代码在我的计算机上运行，我们通过一些特定的网络协议通信。所以，我们可能会担心安全问题，我们把系统分成多个的计算机，这样可以限制出错域。

2. 分布式系统的挑战

1. 并发：多个计算机同时运行，多个计算机同时访问同一个资源，这就会导致遇到并发编程和各种复杂交互所带来的问题，以及时间依赖的问题（比如同步，异步）。这让分布式系统变得很难。
2. 部分失败：在分布式系统中，有可能出现部分失败，比如网络分区，硬件故障，软件故障等。这就需要我们设计一些机制来处理这些部分失败。
3. 性能：在分布式系统中，性能是一个很大的挑战，因为我们需要考虑到网络的延迟，网络的带宽，以及计算机的性能等。

二、分布式系统的抽象和实现工具

1. 分布式系统的抽象

分布式系统的三大基础架构: 存储、通信、计算。

存储和计算

目标是为了能够设计一些简单接口，让第三方应用能够使用这些分布式的存储和计算，这样才能简单地在这些基础架构之上，构建第三方应用程序， 也就是说将分布式特性隐藏在整个系统内，就像整个系统是一个非分布式的系统。

通信

通信是我们建立分布式系统所用的工具。比如计算机可能需要通过网络相互通信，但是可能需要保证一定的可靠性。

2. 构建分布式系统的工具

RPC（Remote Procedure Call）

一种通信机制，允许一个程序调用另一个地址空间（通常是共享网络的另一台计算机）的过程。RPC 是一种客户端-服务器模型，客户端发送一个请求，服务器返回一个响应。

线程

能够让程序并发执行，提高程序的性能。

锁

一种同步机制，用于控制多个线程对共享资源的访问。锁可以防止多个线程同时访问共享资源，从而避免数据竞争和数据不一致。

三、可扩展性（Scalability）

可扩展性

指系统在需要增加资源时，能够保持或提高性能的能力(如果我用一台计算机解决了一些问题，当我买了第二台计算机，我只需要一半的时间就可以解决这些问题，或者说每分钟可以解决两倍数量的问题)。

四、可用性（Availability）

在大型分布式系统中，一些很罕见的问题会被放大。所以大规模系统会将一些几乎不可能并且你不需要考虑的问题，变成一个持续不断的问题。

所以，因为错误总会发生，必须要在设计时就考虑，系统能够屏蔽错误，或者说能够在出错时继续运行。

可用性（Availability）

某些系统经过精心的设计，这样在特定的错误类型下，系统仍然能够正常运行，仍然可以像没有出现错误一样，为你提供完整的服务。

课程中所说的可用性更像 CAP 理论中的分区容错性

五、一致性（Consistency）

一致性

早期也叫（Agreement），在分布式系统领域中是指对于多个服务节点，给定一系列操作，在约定协议的保障下，使得它们对处理结果达成“某种程度”的协同。¹。

1. 一致性的要求

• 可终止性（Termination）：一致的结果在有限时间内能完成（可以保障提供服务的（Liveness））
• 约同性（Agreement）：不同节点最终完成决策的结果是相同的（意味着算法要么不给出结果，任何给出的结果必定是达成了共识的，即安全性（Safety））
• 合法性（Validity）：决策的结果必须是某个节点提出的提案（即达成的结果必须是节点执行操作的结果）

2. 一致性模型

• 强一致性模型 : 确保只能看到一致的状态。当查询一个对象的属性时，所有副本返回相同的值。这可能以成本高的延迟实现。
  • 顺序一致性：所有操作都以某种顺序原子执行，该顺序与各个节点上看到的顺序一致，并且在所有节点上都相等；可以基于 Lamport timestamp 逻辑时钟进行实现。
  • 线性一致性：所有操作都按照操作的全局实时顺序一致的顺序自动执行；在顺序一致性前提下加强了进程间的操作排序，形成唯一的全局顺序；依赖于全局的时钟或锁，有很强的原子性保证，但是比较难实现。
• 弱一致性模型 : 弱一致性适用于快速访问需求占主导地位时的场景。
  • 最终一致性：在未来的某个时间点进行冲突检测和修正，如 DNS
  • 客户端为中心型一致性：通过在 client 端库中建立额外的缓存来实现，如亚马逊 Dynamo

---

在一个分布式系统中，由于复制或者缓存，数据可能存在于多个副本当中，于是就有了多个不同版本的 key-value 对。

一致性有很多不同的定义。有一些非常直观，比如说 get 请求可以得到最近一次完成的 put 请求写入的值。这种一般也被称为强一致（Strong Consistency）。但是，事实上，构建一个弱一致的系统也是非常有用的。弱一致是指，不保证 get 请求可以得到最近一次完成的 put 请求写入的值。尽管有很多细节的工作要处理，强一致可以保证 get 得到的是 put 写入的最新的数据；而很多的弱一致系统不会做出类似的保证。所以在一个弱一致系统中，某人通过 put 请求写入了一个数据，但是你通过 get 看到的可能仍然是一个旧数据，而这个旧数据可能是很久之前写入的。

人们对于弱一致感兴趣的原因是，虽然强一致可以确保 get 获取的是最新的数据，但是实现这一点的代价非常高。几乎可以确定的是，分布式系统的各个组件需要做大量的通信，才能实现强一致性。如果你有多个副本，那么不管 get 还是 put 都需要询问每一个副本。在之前的例子中，客户端在更新的过程中故障了，导致一个副本更新了，而另一个副本没有更新。如果我们要实现强一致，简单的方法就是同时读两个副本，如果有多个副本就读取所有的副本，并使用最近一次写入的数据。但是这样的代价很高，因为需要大量的通信才能得到一个数据。所以，为了尽可能的避免通信，尤其当副本相隔的很远的时候，人们会构建弱一致系统，并允许读取出旧的数据。当然，为了让弱一致更有实际意义，人们还会定义更多的规则。

3. 共识算法

共识（Consensus）与一致性（Consistency）

一致性

含义比共识宽泛，在不同场景（基于事务的数据库、分布式系统等）下意义不同。在分布式系统场景下，一致性指的是多个副本对外呈现的状态。如之前提到的顺序一致性、线性一致性，描述了多节点对数据状态的共同维护能力。

共识

特指在分布式系统中多个节点之间对某个事情达成一致看法的过程。需注意达成某种共识并不意味着就保障了一致性。

在 LHR 的博客²中，有着对拜占庭将军问题、共识算法和 FLP 不可能定理、CAP 理论、ACID 原则与 BASE 原则的详细解释，在知乎上也有对共识、线性一致性、顺序一致性、最终一致性、强一致性概念讨论的详细文章³。

六、MapReduce 基本工作方式

MapReduce 思想：应用程序设计人员和分布式运算的使用者，只需要写简单的 Map 函数和 Reduce 函数，而不需要知道任何有关分布式的事情，MapReduce 框架会处理剩下的事情。

MapRedude 中的关键概念已经记录在我的MapReduce 笔记中。下面是MapReduce 论文和MapReduce 论文翻译