分布式系统
    分布式理论基础

    分布式理论基础

    经典拜占庭将军问题

    故事概要：多个军队之间的作战计划一致性的问题，即便某些军队的信使传递了错误的消息，也能够维持最后的投票结果一致性

    口信消息型解法：如果叛将人数为 m，将军人数不能少于 3m + 1 ，那么拜占庭将军问题就能解决了

    签名消息型解法：对发送的作战计划进行签名然后传递，这样就能够在不增加忠诚将军的情况下发现叛徒

    拜占庭问题是分布式系统问题中最困难和最复杂的，除了存在故障行为，还有恶意行为。因此在数字加密货币中必须使用拜占庭容错算法 BFT，常见的其他拜占庭算法有：PBFT和pow算法

    计算机世界的分布式问题更多的是非拜占庭问题，即故障容错算法CFT，常见的算法有 Paxos 算法、Raft 算法、ZAB 协议

    如何在实际场景选择合适的算法类型呢？答案是：如果能确定该环境中各节点是可信赖的，不存在篡改消息或者伪造消息等恶意行为（例如 DevOps 环境中的分布式路由寻址系统），推荐使用非拜占庭容错算法；反之，推荐使用拜占庭容错算法，例如在区块链中使用 PoW 算法。

    CAP理论

    • 一致性（Consistency）
    • 可用性（Availability）
    • 分区容错性（Partition Tolerance）

    一致性：不论向哪个节点查询，返回的结果都是最新一致的数据 可用性：不管访问哪个非故障节点，都能得到响应数据，但不保证是同一份最新数据（强调服务可用，但不保证数据正确），通过服务延迟来衡量 分区容错性：不管集群内部出现什么样的数据同步问题，集群会一直运行

    CAP不可能三角：三者不能兼得，只能在三个指标中选择两个

    如何进行选择？

    • 不存在网络分区的情况下，CA是可以同时保证的
    • 存在网络分区，必须C和A二选一，如果读到旧数据对业务会有不良影响，则选C，否则选A
    • 通常来说离最终落盘存储的集群越近，这部分集群对A的需求就越强烈

    CP模型案例：Etcd，Consul 和 Hbase AP模型案例：Cassandra 和 DynamoDB

    1. 如果业务需要强一致性，则只能牺牲可用性而选择CP模型
    2. 如果业务需要最终一致性即可，则优先满足可用性，选择AP模型

    ACID理论

    建议在开发实现分布式系统，如果不是必须，尽量不要实现事务，可以考虑采用最终一致性。

    实现强一致性必然会影响可用性 比如，在采用两阶段提交协议的集群系统中，因为执行提交操作，需要所有节点确认和投票。

    二阶段提交协议

    想要完成分布式事务，即所有不同节点的特定行为要么都发生，要么都不发生，可以使用二阶段提交协议进行解决。

    1. 客户端请求一个节点，然后该节点作为协调者来联系其他的节点进行投票 2. 提交执行阶段，从自己开始采取行动，成功后通知下一个节点进行行动，直到所有节点都完成了这个行动并通报

    在一个参与者投票要求提交事务之前，它必须保证能够执行提交协议中它自己那一部分，即使参与者出现故障或者中途被替换掉。 这个特性，是我们需要在代码实现时保障的。

    XA协议是MySQL使用的基于二阶段提交协议的分布式事务协议

    缺点：需要对资源进行锁定，影响并发性能

    TCC

    TCC 是 Try（预留）、Confirm（确认）、Cancel（撤销） 3 个操作的简称 本质是补偿事务，针对每个操作都要注册一个与其对应的确认操作和补偿操作（也就是撤销操作），确认操作和补偿操作必须是等幂的，因为这 2 个操作可能会失败重试

    TCC 不依赖于数据库的事务，而是在业务中实现了分布式事务 客户端向各个节点发送预留时间和资源的请求，没问题就进入确认阶段，客户端发出执行的请求，返回执行结果，如果有失败的，则执行撤销，没有则事务执行成功

    Base理论

    BASE 理论是 CAP 理论中的 AP 的延伸，是对互联网大规模分布式系统的实践总结，强调可用性，多用于NoSQL 核心：基本可用，最终一致性 通过服务降级，牺牲部分功能的可用性，保障系统的核心功能可用。 常见措施：流量削峰，延迟响应，体验降级，过载保护熔断 最终一致性指的是系统的所有数据副本在经过一段时间的同步后，最终能够达到一个一致的状态。

    如何保证最终一致性？ 读时修复，写时修复，异步修复（定时对账检测数据一致性并修复）

    写时修复实现：节点之间远程写数据的时候，如果写失败就将数据缓存下来，然后定时重传，修复数据的不一致性。这种方式**性能消耗较低，不需要做系统一致性比对

    读时修复和异步修复因为需要做数据的一致性对比，性能消耗比较多，在开发实际系统时，你要尽量优化一致性对比的算法，降低性能消耗，避免对系统运行造成影响。

    在最终一致性的实现上推荐同时实现自定义写一致性级别，让用户自主选择 对于任何集群而言，不可预知的故障的最终后果，都是系统过载

    Paxos算法

    理解角色是掌握paxos的核心 三种角色：

    • 提议者：收到客户端请求后，发起二阶段提交，进行共识协商
    • 接受者：每一个节点都是接受者，对提议者提议的值进行投票，并接受达成共识的值，存储保存
    • 学习者：只被动接受达成共识的值，通常是做数据备份的从机器

    Basic Paxos： 提案编号的大小代表着优先级，你可以这么理解，根据提案编号的大小，接受者保证三个承诺，具体来说：如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求；如果接受请求中的提案的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息。

    BP只是让大多数节点对某个键的值达成一个共识，达成共识（即提案通过）后值将不再改变，如果后续有更大的提案号，则只更新提案号，但是不再更新值。

    Multi-Paxos算法

    单个值的共识使用 basic paxos，一系列的值的共识才是能够最终落地的共识算法即 multi-paxos

    分布式哈希表 DHT架构演进