分布式架构的必问理论

基础理论：

CAP理论：

CAP理论是分布式系统设计中最基础、也是最为关键的理论，它指出，分布式数据存储不可能同时满足以下三个条件。

1. 一致性（Consistency）：每次读取要么获得最近写入的数据，要么获得一个错误。
2. 可用性（Avaliability）：每次请求都能获得一个非错误的响应，但是不能保证返回的是最新写入的数据。
3. 分区容忍（Partition tolerance）：尽管任意数量的消息被节点间的网络丢失或者被延迟了，系统仍然可用运行。

也就是说，CAP定理表明，在存在网络分区的情况下，一致性和可用性必须二选一。而在没有网络故障的情况下，即分布式系统正常运行时，一致性和可用性是可以被同时满足的。这里需要注意的是，CAP定理中的一致性与ACID数据库的事务中的一致性不一样。

掌握CAP定理，能够正确的理解C、A、P的含义，对于系统架构来说非常重要。因为对于分布式系统来说，网络的故障在所难免的，如何在出现网络错误的时候，能够维持系统按照正常的行为逻辑运行就显得尤为重要了。具体的情况可以根据系统的实际业务需求来做相关的权衡。

举例说明，对于大多数互联网应用来说，因为机器数量庞大，部署的节点分散，网络故障是正常的情况，可用性就必须是要保证的，所以只能舍弃一致性来保证服务的AP。而对于银行、证券来说，需要保证一致性的场景，通常会权衡CA和CP的模型，CA模型网络故障时完全不可用，CP模型具备部分的可用性。

CA（Consistency+avaliability）

这样的系统关注一致性和可用性，需要非常严格的全体一致性的协议，比如说“两阶段提交”（2PC）。CA系统不能够容忍网络错误或者说节点错误，一旦出现这样的问题，整个系统就会拒绝写请求，因为它并不清楚对面的那个节点是否已经不能工作了，还是说只是网络的问题。唯一安全的做法就是把自己变成只读的。

CP（consistency+partition tolerance）

这样的系统关注一致性和分区容忍性。它关注的是系统里面大多数人的一致性协议，比如说Paxos算法。这样的系统只需要保证大多数节点的数据一致，而少数的节点会在没有同步到最新版本的数据时变成不可用的状态。这样能够提供一部分的可用性。

AP（availability+partion tolerance）

这样的系统来说，关心可用性和分区容忍性，因此，这样的系统就不能达成一致性，需要给出数据冲突，给出数据冲突就需要维护数据版本，Dynamo就是这样的系统。

然而，还有一些人会错误的认为CAP定理，甚至误用这个定理。

在设计分布式框架的时候一定要仔细思考下面这八种说法是错误的：

1. 网络是稳定的
2. 网络传输的延迟是零
3. 网络的带宽是无穷大的
4. 网络是安全的
5. 网络的拓扑不会改变
6. 只有一个系统管理员
7. 传输数据的成本为零
8. 整个网络是同构的

这八个错误的说法可以让我们可以更加清晰的认识到，在分布式系统中的错误是不可能避免的，我们要做的不是避免错误，而是把错误的处理当成功能写在代码中。错误出现的时候，也要保住系统的运行。

失败和时间（Failure and Time）。

分布式系统工程师面临的很多困难都可以归咎于两个根本问题：

1. 进程可能会失败
2. 没有好的方法表明进程失败，这就涉及到如何设置系统的时钟，以及进程之间的通讯机制，在没有任何共享时钟的情况下，如何确定一个事件发生在另一个事件中。

容错的压力（The basic tension of fault tolerance）。

能在不降级的情况下容错的系统一定要像没有错误发生那样运行。这就意味着，系统的某些部分必须冗余的工作，从而在性能和资源消耗两个方面带来成本。

基于原语（Basic primitives）

在分布式系统中几乎没有一致认同的基本构建模块，但是目前在越来越多地出现，比如Leader选举，分布式状态机复制处理。

基本结论（Fundamental Results）

某些事实是需要吸收理解的，有几点，如果进程之间可能丢失某些信息，那么不可能在实现一致性存储的同时响应所有的请求，这就是CAP定理；一致性不可能同时满足以下的条件

1. 总是正确
2. 在异步系统中只要有一台机器发生故障，系统总是能终止运行；

一般而言，消息交互少于两轮都不可能达成共识（Consensus）.

真实系统（Real System）

学习分布式系统架构最重要的是，结合一些真实系统的描述，反复思考和点评其背后的设计决策，如谷歌GFS、Spanner、Chubby等。

FLP Impossibility Result

FLP 不可能性的名称起源于它的三围作者。Fischer、Lynch和Paterson。理论的主要思想是能作出的功能最强的共识算法会受到怎样的限制的讨论。

所谓共识的问题，就是让网络上的分布式处理者最后都对同一个结果值达成共识。该解决方案对错误有恢复能力，处理者一旦崩溃以后，就不再参与计算了。在同步环境下，每个操作步骤的时间和网络通信的延迟都是有限的，要解决共识问题是可能的，方式是：等待一个完整的步长来检测某个处理者是否已经失败了。如果没有收到回复的话，那就假定它已经崩溃了。

共识问题有几个变种，他们在强度方面有所不同，通常一个更强问题的解决方案同时也能解决比该问题更弱的问题，共识问题的一个较强的形式如下，假定前提条件是“给出一个处理者的集合，其中每一个处理者都有一个初始值”：

1. 所有无措的进程最终都将决定一个值
2. 所有会做决定的无错误的进程决定的都是同一个值
3. 最终被决定的值必须被至少一个进程提出过

这三个特性分别被称为“终止”、“一致同意”和“有效性”。任何一个具备这三点特性的算法都被认为是解决了共识的问题。

FLP不可能性则讨论了异步模型下的情况，主要结论有两条。

1. 在异步模型下不存在一个完全正确的共识算法。不仅上述较强的形式共识算法不可能实现，FLP还证明了比他弱一些的、只需要有一些无错误的进程做决定就足够的共识算法也是不可能实现的。
2. 在异步模型下存在一个部分正确的共识算法，前提是所有无错误的进程都总能作出一个决定，此外没有进程会在他的执行过程中死亡，并且初始情况下超过半数进程都是存活的状态。

FLP的结论是，在异步模型中，仅一个处理者可能崩溃的情况下，就已经没有分布算法能解决共识的问题。这是该问题理论上界限。其背后的原因在于，异步模型下对于一个处理者完成工作然后再回复消息所需的时间没有上限。因此，无法判断出一个处理者到底是崩溃了，还是在较长的时间来回复，或者是网络有很大的延迟。

FLP不可能性对我们还有其他的启发。一个是网络延迟很重要，网络不能长时间处理拥塞的状态，否则的话共识算法将可能因为网络延迟过长导致超时失败。二是计算时间也很重要。对于需要计算共识的处理过程（进程）。如分布式数据库的提交来说，需要在短时间里面就计算出能否提交的结果，那就要保证计算结点资源充分，特别是内存容量、磁盘空闲时间和CPU时间方面要足够，并且在软件层面确保计算不超时。

另一个问题，像Paxos这样的共识算法为什么可行？实际上它并不属于FLP不 可能性证明所说的“完全正确”的算法，它的正确性会受到超时值的影响。但是并不妨碍它在实践中有效，因为我们可以通过避免网络拥塞等手段来保证超时值是合适的。

An introduction to distributed system

分布式系统基础课的提纲，也是一份很好的分布式系统介绍，几乎涵盖了所有的知识点，并辅简洁并且切中要害的说明文字，非常适合初学者提纲挈领地了解知识全貌，快速与现有知识结合，形成知识体系。