一些著名的算法定理

written by Alex Stocks on 2018/10/08，

分布式领域有一些非常著名的定理和算法，构筑了当下一些著名分布式系统的基石。下面分别罗列之，以求集腋成裘之效。

1 CAP

这个定理鼎鼎大名， 参考文档2 对其描述如下：

• 一致性（Consistency）：每次读取要么获得最近写入的数据，要么获得一个错误;
• 可用性（Availability）：每次请求都能获得一个（非错误）响应，但不保证返回的是最新写入的数据，即单节点会在有限时间内对服务做出响应，不超时不假死;
• 分区容忍（Partition tolerance）：尽管任意数量的消息被节点间的网络丢失（或延迟），系统仍继续运行。

上面的描述其实也不甚清晰，换句话说就是：如果进程之间可能丢失某些消息，那么不可能在实现一致性存储的同时响应所有的请求。 三个特性中最重要的是数据一致性，一致性不可能同时满足以下条件：总是正确; 在异步系统中只要有一台机器发生故障，系统总是能终止运行——停止失败（FLP 不可能性）。一般而言，消息交互少于两轮都不可能达成共识（Consensus）。

在没有发生网络故障时，即分布式系统正常运行时，一致性和可用性是可以同时被满足的。CAP 定理表明，在存在网络分区的情况下，一致性和可用性必须二选一：

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

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

• AP (availability + partition tolerance)，这样的系统关心可用性和分区容忍性。因此，这样的系统不能达成一致性，需要给出数据冲突，给出数据冲突就需要维护数据版本。

以上内容大部分摘自 参考文档2 。下面分别描述一些著名系统的 CAP 取舍。

1.1 zookeeper

Zookeeper是基于CP来设计的，即任何时刻对Zookeeper的访问请求能得到一致的数据结果，同时系统对网络分割具备容错性，但是它不能保证每次服务请求的可用性。从实际情况来分析，在使用Zookeeper获取服务列表时， 如果zookeeper正在选主，或者Zookeeper集群中半数以上机器不可用，那么将无法获得数据。所以说，Zookeeper不能保证服务可用性。 涉及到数据存储的场景，数据一致性应该是首先被保证的，这也是zookeeper设计成CP的原因。但是对于服务发现场景来说，情况就不太一样了：针对同一个服务，即使注册中心的不同节点保存的服务提供者信息不尽相同，也并不会造成灾难性的后果。因为对于服务消费者来说，能消费才是最重要的——拿到可能不正确的服务实例信息后尝试消费一下，也好过因为无法获取实例信息而不去消费。（尝试一下可以快速失败，之后可以更新配置并重试）所以， 对于服务发现而言，可用性比数据一致性更加重要——AP胜过CP。 而Spring Cloud Netflix在设计Eureka时遵守的就是AP原则。 对于不经常变动的配置来说，CP是不合适的，而AP在遇到问题时可以用牺牲一致性来保证可用性，返回旧数据，缓存数据。

以上内容摘自 参考文档3 。

1.2 MongoDB

mongodb 的读写一致性由 WriteConcern 和 ReadConcern 两个参数保证,两者组合可以得到不同的一致性等级。指定 writeConcern:majority 可以保证写入数据不丢失，不会因选举新主节点而被回滚掉。readConcern:majority + writeConcern:majority 可以保证强一致性的读,readConcern:local + writeConcern:majority 可以保证最终一致性的读。mongodb 对configServer全部指定writeConcern:majority 的写入方式，因此元数据可以保证不丢失。对 configServer 的读指定了 ReadPreference:PrimaryOnly 的方式，在 CAP 中舍弃了A与P得到了元数据的强一致性读。

2 FLP

上文在描述 CAP 时候 顺带提到了 FLP，参考文档1 对 FLP 定位为：在存储系统中，任何一个副本意外崩溃，其自身无论重启后如何修复都是无法保证数据完整性的。除了一些存储系统，FLP 也是当前流行的区块链技术（可以认为是一种去中心化的存储系统）用到的共识算法的基石。

FLP论文 由Fischer, Lynch 和 Patterson三位分布式领域大牛于1985年发表，论文要表达的主题是：分布式异步模型中，没有一种一致性协议可以保证系统在某个进程(服务)挂掉后仍然是完全可靠的。一些经典论文，其描述是相当严谨的，其对应的工业实现对一些corner case则不会考虑。因为一些corner case可能发生概率极小，为了在有限时间内完成任务，可以先假设其不会发生，不予以处理，所以在有限时间内可以舍弃一些目标而完成一些核心目标，使得任务可控，bug也能快速收敛。但是，如果迭代了很多版本，时间也足够了，有一些问题是可以解决却不予以解决，这就无法原谅了。当然，还有一些确实难以解决或者为了解决一个很小问题却会导致代码复杂度急剧提高甚至不得不重构，这就要综合考虑各种客观情况譬如人力和时间成本后再考虑是否予以解决了。总之，要有一种严格的科学精神，不要太放低自己的身段放松对自己的要求。

FLP的前提是分布式和异步模型。在分布式系统中，异步模型都适用于 CAP 和 FLP。在工作任务重的部分考虑异步模型，在工作任务轻的部分譬如 metaserver 就可以考虑同步模型，一些一致性算法譬如 Paxos 和 Raft 本质都是运作在同步模型之上的，此时就可以认为一致性是可以达成的。

FLP 与 共识问题

共识问题，就是让网络上的分布式处理者最后都对同一个结果值达成共识。共识问题给出一个处理者的集合，其中每一个处理者都有一个初始值：

• 所有无错误的进程（处理过程）最终都将决定一个值；
• 所有会做决定的无错误进程决定的都将是同一个值；
• 最终被决定的值必须被至少一个进程提出过。

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

参考文档2 对 FLP 与共识问题之间的关系进行了探讨。其描述如下： FLP 不可能性则讨论了异步模型下的情况，主要结论有两条: 在异步模型下不存在一个完全正确的共识算法。不仅上述较“强”形式的共识算法不可能实现，FLP 还证明了比它弱一些的、只需要有一些无错误的进程做决定就足够的共识算法也是不可能实现的; 在异步模型下存在一个部分正确的共识算法，前提是所有无错误的进程都总能做出一个决定，此外没有进程会在它的执行过程中死亡，并且初始情况下超过半数进程都是存活状态。

参考文档

1 FLP 证明

2 分布式系统架构经典资料

3 ZooKeeper、Eureka对比

扒粪者-于雨氏

2018/10/08，于雨氏，于丰台。