|
|
written by Alex Stocks on 2018/10/08，版权所有，无授权不得转载
分布式领域有一些非常著名的定理和算法，构筑了当下一些著名分布式系统的基石。下面分别罗列之，以求集腋成裘之效。
之所以先提及这个定律，是为了说明一个道理：计算机科学很多定律仅仅是经验的总结，存在一定的先决条件，当条件改变后，它也就失效了。也即：没有一成不变的放之四海而皆准的计算机定律。
参考文档5 在大中型计算机时代，有一个 Grosch 定律：计算机性能随着成本的平方而增加。如果计算机 A 的成本是计算机 B 的两倍，那么计算机 A 的速度应该是计算机 B 的四倍，这个定律简单而有效，在大型机时代工程师想的是如何提高单个大型机的性能，使用方则尽其所能购买预算范围内的最贵的大型机。
到 1965 年微型处理器（CPU）出现后，Gordon Moore 提出了摩尔定律，这意味着计算机性能的提升除了金钱这一因素外，还要考虑时间这一因素，其结果就是参考文档5提到的：如果你的系统需承载的计算量的增长速度大于摩尔定律的预测，那么在未来的某一个时间点，集中式系统将无法承载你所需的计算量。
摩尔定律说明单机的性能取决于金钱和时间，在时间恒定的一个时刻，即使金钱再多，其性能也有一个天花板极限。聪明如人类，必然会想到计算机互联，即他通过多个单机构成一个分布式系统的方法，以系统性能提升的方式达到提升计算机性能的目的。
分布式系统的另一个好处就是系统稳定性的提升。两台计算机互联并不是 1 + 1 > 2，不能带来两倍的计算机性能的提升，甚至是 1.5 倍的性能提升都很难，但是却能提高系统的可靠性：即使其中一台计算机出现故障，整体系统还是具备可用性，虽然牺牲了系统的性能。
这个定理鼎鼎大名，参考文档2 对其描述如下：
上面的描述其实也不甚清晰，换句话说就是：如果进程之间可能丢失某些消息，那么不可能在实现一致性存储的同时响应所有的请求。 三个特性中最重要的是数据一致性，一致性不可能同时满足以下条件：总是正确; 在异步系统中只要有一台机器发生故障，系统总是能终止运行——停止失败（FLP 不可能性）。一般而言，消息交互少于两轮都不可能达成共识（Consensus）。
在没有发生网络故障时，即分布式系统正常运行时，一致性和可用性是可以同时被满足的。CAP 定理表明，在存在网络分区的情况下，一致性和可用性必须二选一：
CA (consistency + availability)，这样的系统关注一致性和可用性，它需要非常严格的全体一致的协议，比如“两阶段提交”（2PC）。CA 系统不能容忍网络错误或节点错误，一旦出现这样的问题，整个系统就会拒绝写请求，因为它并不知道对面的那个结点是否挂掉了，还是只是网络问题。唯一安全的做法就是把自己变成只读的。
CP (consistency + partition tolerance)，这样的系统关注一致性和分区容忍性。它关注的是系统里大多数人的一致性协议，比如：Paxos 算法 (Quorum 类的算法)。这样的系统只需要保证大多数结点数据一致，而少数的结点会在没有同步到最新版本的数据时变成不可用的状态。这样能够提供一部分的可用性。
AP (availability + partition tolerance)，这样的系统关心可用性和分区容忍性。因此，这样的系统不能达成一致性，需要给出数据冲突，给出数据冲突就需要维护数据版本。
以上内容大部分摘自 参考文档2。下面分别描述一些著名系统的 CAP 取舍。
Zookeeper是基于CP来设计的，即任何时刻对Zookeeper的访问请求能得到一致的数据结果，同时系统对网络分割具备容错性，但是它不能保证每次服务请求的可用性。从实际情况来分析，在使用Zookeeper获取服务列表时，如果zookeeper正在选主，或者Zookeeper集群中半数以上机器不可用，那么将无法获得数据。所以说，Zookeeper不能保证服务可用性。涉及到数据存储的场景，数据一致性应该是首先被保证的，这也是zookeeper设计成CP的原因。但是对于服务发现场景来说，情况就不太一样了：针对同一个服务，即使注册中心的不同节点保存的服务提供者信息不尽相同，也并不会造成灾难性的后果。因为对于服务消费者来说，能消费才是最重要的——拿到可能不正确的服务实例信息后尝试消费一下，也好过因为无法获取实例信息而不去消费。（尝试一下可以快速失败，之后可以更新配置并重试）所以，对于服务发现而言，可用性比数据一致性更加重要——AP胜过CP。而Spring Cloud Netflix在设计Eureka时遵守的就是AP原则。对于不经常变动的配置来说，CP是不合适的，而AP在遇到问题时可以用牺牲一致性来保证可用性，返回旧数据，缓存数据。
以上内容摘自 参考文档3。
mongodb 的读写一致性由 WriteConcern 和 ReadConcern 两个参数保证,两者组合可以得到不同的一致性等级。指定 writeConcern:majority 可以保证写入数据不丢失，不会因选举新主节点而被回滚掉。readConcern:majority + writeConcern:majority 可以保证强一致性的读,readConcern:local + writeConcern:majority 可以保证最终一致性的读。mongodb 对configServer全部指定writeConcern:majority 的写入方式，因此元数据可以保证不丢失。对 configServer 的读指定了 ReadPreference:PrimaryOnly 的方式，在 CAP 中舍弃了A与P得到了元数据的强一致性读。
上文在描述 CAP 时候 顺带提到了 FLP，参考文档1 对 FLP 定位为：在存储系统中，任何一个副本意外崩溃，其自身无论重启后如何修复都是无法保证数据完整性的。除了一些存储系统，FLP 也是当前流行的区块链技术（可以认为是一种去中心化的存储系统）用到的共识算法的基石。
FLP论文 由Fischer, Lynch 和 Patterson三位分布式领域大牛于1985年发表，论文要表达的主题是：分布式异步模型中，没有一种一致性协议可以保证系统在某个进程(服务)挂掉后仍然是完全可靠的。一些经典论文，其描述是相当严谨的，其对应的工业实现对一些corner case则不会考虑。因为一些corner case可能发生概率极小，为了在有限时间内完成任务，可以先假设其不会发生，不予以处理，所以在有限时间内可以舍弃一些目标而完成一些核心目标，使得任务可控，bug也能快速收敛。但是，如果迭代了很多版本，时间也足够了，有一些问题是可以解决却不予以解决，这就无法原谅了。当然，还有一些确实难以解决或者为了解决一个很小问题却会导致代码复杂度急剧提高甚至不得不重构，这就要综合考虑各种客观情况譬如人力和时间成本后再考虑是否予以解决了。总之，要有一种严格的科学精神，不要太放低自己的身段放松对自己的要求。
FLP的前提是分布式和异步模型。在分布式系统中，异步模型都适用于 CAP 和 FLP。在工作任务重的部分考虑异步模型，在工作任务轻的部分譬如 metaserver 就可以考虑同步模型，一些一致性算法譬如 Paxos 和 Raft 本质都是运作在同步模型之上的，此时就可以认为一致性是可以达成的。
共识问题，就是让网络上的分布式处理者最后都对同一个结果值达成共识。共识问题给出一个处理者的集合，其中每一个处理者都有一个初始值：
这三个特性分别被称为“终止”、“一致同意”和“有效性”。任何一个具备这三点特性的算法都被认为是解决了共识问题。
参考文档2 对 FLP 与共识问题之间的关系进行了探讨。其描述如下：FLP 不可能性则讨论了异步模型下的情况，主要结论有两条: 在异步模型下不存在一个完全正确的共识算法。不仅上述较“强”形式的共识算法不可能实现，FLP 还证明了比它弱一些的、只需要有一些无错误的进程做决定就足够的共识算法也是不可能实现的; 在异步模型下存在一个部分正确的共识算法，前提是所有无错误的进程都总能做出一个决定，此外没有进程会在它的执行过程中死亡，并且初始情况下超过半数进程都是存活状态。
广播算法（Gossip）就是在一个无中心节点的群集中把一个数据通知给所有节点，典型的应用实例就是 Redis Sentinel 之间在进行 Failover 沟通过程中使用了这个算法进行主节点由 sdown 状态到 odown 状态转换以及执行 Failover 时 Sentinel Leader 选举，都使用了广播算法进行通信。
正如 参考文档4 文中给出的示例，Gossip 算法的关键是：如何选择路径来给其他主机发送广播内容时避免重复发送形成广播风暴。
最简单的方法是广播内容的源头节点在进行全群集广播时候带上所有目的节点的地址，进行有目的地广播，虽然可以避免广播风暴，但是效率极低，多个广播包传输路径会有很多节点路径是重合的。
另一种解决方法是每个节点收到广播包后只发送给其邻居节点，但是无法避免广播风暴。参考文档4 指出：一种很简单的方法，就是给这一份广播分组做一个标记。例如，源节点(发起广播的节点)可以将其地址以及广播序号放入这个广播分组中，然后发送给他的所有邻居节点，每个节点会维护它已经收到的、转发的源地址和广播分组的序号列表。当节点收到一个广播分组时，会检查这个广播分组是否之前接收过(可以通过源地址、报文序号来检查)，如果接收过，那么就把该广播分组丢弃，否则，把该广播分组接收，且向所有邻居节点转发。
这个方法足够简单有效，Redis Sentinel 就是使用了这个方法，但是其缺点依然避免不了部分广播包传播过程有广播路径重合。还有更简单的算法：生成树广播。其核心内容是：先选出一个中心节点，然后其他节点向这个中心节点发送加入树报文，加入树报文经过的路径，都会被嫁接到生成树上。
据维基百科上讲，复杂性守恒定律源自人机交互设计计算机科学：在人机交互应用开发时，相关复杂性要么被应用处理掉，要么被用户处理掉，无法被消灭。
软件系统的复杂性就像打地鼠，从一个洞口打下去，它会在另一个洞口迅速再次冒出来。或者说，就像在毯子下的蛇， 当你一个摊子的某个地方踩下去，它会从另一个地方鼓起来。
复杂性最好在软件系统内被处理掉，否则就会传导到其相关的级联的下一级系统。譬如从存储系统级联到逻辑系统，或者级联到接口系统，或者级联到用户 APP，最终直至用户。
|
|
|