引言

当只有一台计算机的时候，也就是单机系统，我们不需要考虑通信、容错、一致性等等问题，只需要将应用部署在这台计算机上，它的正确运行是显而易见的——就像我们平时所做的那样，自己编写一个C++程序并运行。

但是单机系统的弊端也是很明显的——它的资源很有限。它的硬盘、CPU、内存都是有限的，当我们的应用需要更多的资源时，一台计算机难以支撑它的运行。

一个很直观的想法是:增加更多的计算机，这样我们就有更多资源了！

这就是分布式系统: 很多台计算机组成一个系统，协作运行大型的应用。

但是一个问题随之而来，那就是，在系统中增加了计算机之后，整个系统的性能也是随之增加的吗？可用性不随着系统的扩展而变化吗？未必。因为引入更多台计算机使得系统复杂度提升，就会带来额外的开销，影响整个系统的性能；而系统中的计算机可能会出现故障而导致整个系统不可用。

这就引出了分布式系统的目标: 可扩展性(Scalability)。

可扩展性(Scalability)

可扩展性是系统、网络或进程以一种有能力的方式处理不断增长的工作量的能力，或者是其扩大以适应这种增长的能力。

可扩展系统是指随着规模的增加而不断满足用户需求的系统。我们重点关注两个方面: 性能(Performance)和可用性(Availability)。

性能(Performance)

性能被刻画为计算机系统完成的有用工作的数量与所使用的时间和资源的比例。

根据具体情况，这可能被刻画为一个或多个目标:

  • 短响应时间/低延迟
  • 高吞吐量
  • 计算资源的利用率低

可用性(Availability)

可用性:系统处于正常工作状态的时间比例。如果一个用户不能访问系统，就称为不可用。

可用性也就是容错性，这展现出分布式系统相比于单机系统得天独厚的优势，一台计算机是没有容错性的，但是分布式系统可以在一堆不可靠的组件上构建一个可靠的系统。

但是发生故障的概率是随着计算机数量的增加而增加的，我们需要设计好的容错算法，使得系统可用性更高。

分区(partition)与复制(replicate)技术是完成上述目标的关键技术。

分区与复制

分区将数据拆分到不同的节点上，以便进行更多的并行处理；复制将一份数据复制或缓存到不同的节点上，以减小客户端和服务器之间的距离，并提升容错能力。如图所示:
pPapMVI.png

有许多实现复制和分区的算法，各有优缺点，需要结合具体问题选择。

分区

分区通过限制要检查的数据量以及将相关的数据放在同一分区来提高性能。

分区通过允许分区独立故障来提高可用性，即一个分区故障不会影响其他的分区，可以容忍多个分区故障。

复制

复制使额外的计算能力和带宽适用于数据的新副本，从而提高了性能。

复制通过创建数据的额外副本来提高可用性，可以允许一定数量的节点故障。

复制使我们能够实现可扩展性、性能和容错性。

但是复制同样带来很多问题，最重要的，如何保持多个副本之间的数据一致性？

要保障系统满足不同程度的一致性，核心过程往往需要通过共识算法来达成。

共识问题

如果几台计算机(或节点)在某个值上达成一致，它们就会达成共识。更正式地:

  1. Agreement(协定性): 所有正确的进程必须在同一个值上达成一致。
  2. Termination(终止性): 所有正确的进程最终都会认定某个值。
  3. Integrity(完整性): 每个正确的进程最多决定一个值，如果决定了某个值，那么它一定是某个进程提出来的。
  4. Validity(有效性): 如果所有正确进程提出了同样的值，那么所有正确进程决定这个值。

共识问题是许多商业分布式系统的核心问题。

两个不可能性定理的其中一个是关于共识问题的，即FLP impossibility。

FLP impossibility

1985年，Fischer、Lynch 和 Paterson(FLP)证明了: 在一个异步系统中，即使只有一个进程出现了故障，也没有算法能保证达成共识。

后世的研究者为了绕开这个定理达成共识，不得不选择(1)将异步系统转换为同步系统 (2)使用随机性算法。

另一个不可能性定理为CAP定理，指导我们对于分布式系统性质的取舍。

CAP定理

该定理指出，在这三个性质中:

  1. 一致性(Consistency): 所有节点在同一时间看到相同的数据(强一致性)。
  2. 可用性(Availability): 节点故障不会阻止幸存者继续操作(任何时候都可用)。
  3. 分区容忍度(Partition tolerance): 尽管由于网络和/或节点故障导致消息丢失，系统仍能继续运行。

只能同时满足其中的两个。

于是我们就得到了三种不同的系统类型:

  1. CA(Consistency+Availability): 包括full strict quorum protocols，例如2PC.
  2. CP(Consistency+Partition tolerance): 包括少数分区不可用的大多数仲裁协议，如Paxos以及Raft。
  3. AP(Availability+Partition tolerance): 包括使用冲突解决的协议，例如Dynamo。

CAP定理中的一致性为强一致性，因此尽管AP系统无法实现强一致性，但是仍然有弱一致性可供实现。CAP的可用性也为强可用性，因此尽管Raft算法是CP算法，但并不意味着没有可用性，而是大多数时间可用。

Raft算法是目前最成功的分布式共识算法，是非拜占庭容错的，在分布式系统的下一篇文章，我将会写一下Raft算法。

参考文献

[1] Jay Kreps. Distributed systems[EB/OL]. [2023-8-28]. https://book.mixu.net/distsys/index.html.
[2] 苏小乐. 分布式系统的一致性与共识性[EB/OL]. [2023-08-28]. https://zhuanlan.zhihu.com/p/35596768.
[3] Fischer, M. J., Lynch, N. A. & Paterson, M. S. Impossibility of distributed consensus with one faulty process. J Acm Jacm 32, 374–382 (1985).