参考：https://mp.weixin.qq.com/s/rv7qMyGQuVwiFfPUeKeQ2w

1. 概念

1.1. 节点

1.2 异常情况

    分布式环境下会遇到的问题

    机器宕机

    网路异常

    分布式三态：RPC调用执行的结果可能有三个情况：成功、失败、未知（超时）

    存储数据丢失：对于有状态的节点来说，内存数据丢失，则状态也会丢失，通常只能从其他节点读取、恢复。

    异常处理原则

1.3 副本

    在分布式视同中为数据或服务提供的冗余。

    副本一致性：几种一致性

            1. 强一致性

            2. 单调一致性。任何时刻，任何用户一旦读到某个数据在某次更新后的值，这个用户不会再读到比这个值更旧的值。

            3. 会话一致性。任何用户在某次会话内的单调一致性。

            4. 最终一致性。一旦更新成功，各个副本上的数据最终将达到完全一致的状态，但是达到的时间不能保证。

            5. 弱一致性。

1.4 衡量分布式系统的指标

    性能：主要是吞吐量、延迟、并发

    可用性：可以用正常提供服务的时间和总时间的比例或者某个功能成功的次数和失败次数的比例来衡量

    可扩展性：通过扩展集群里的机器数量来提供系统性能、存储容量、计算能力的特性。

    一致性：一致性越高，使用起来约简单。

---

2. 分布式系统原理

2.1 数据分布的方式

    哈希算法

    按数据范围分布：IDC与LDC的实践

    按数据量分布

    一致性哈希：1997年，MIT的论文。为了在移除或者添加新服务器时，能尽量减少影响。

    对存储节点的哈希值进行计算，将其存储空间抽象为一个闭环，将存储节点分配到环上。环上所有节点都有一个值。

    对数据进行哈希计算，按顺时针方向将其映射到离其最近的节点上去。

    如下图，节点计算的值如下，1，2，3，…… 0 .数据hash值为1.3。则将该数据分配给节点2处理。

    如果节点出现异常，影响范围则是从该故障节点开始逆时针方向到上个节点内的数据对象不可用。

    如果需要增加新节点，则影响的是该新增的节点逆时针到上个节点内的数据对象。

    缺点：1. 当节点规模很大时，遍历节点的时间复杂度是O(n)；2. 新增和移除节点还是需要进行数据迁移。

2.2. 基本副本协议

    分类：

    中心化副本控制协议：主要有primary-secondary协议。中心节点负责维护数据的更新、并发控制、协调副本的一致性。主要解决的问题：数据更新流程、数据读取方式、primary选择、数据同步。

    去中心化副本控制协议：

2.3 常见的分布式共识协议或机制

    1. lease机制。Lease 是由颁发者授予的在某一有效期内的承诺。颁发者一旦发出lease，则无论接受方是否收到，也无论后续接收方处于何种状态，只要lease 不过期，颁发者一定严守承诺；另一方面，接收方在lease 的有效期内可以使用颁发者的承诺，但一旦lease 过期，接收方一定不能继续使用颁发者的承诺。

    2. Quorum机制。一共有N个副本，每次更新操作会在W个副本上成功。则最多需要读取R个副本，其中R+W>N 则一定能读取到某次更新后的数据。(因为R和W一定有交集)。

        由于更新 操作需要在W 个副本上都成功，更新操作才能成功，所以一旦N-W+1 （因为W+N-W+1 = N+1> N）个副本异常，更新操作始终无法在W 个副本上成功，更新服务不可用。另一方面，一旦N-R+1 个副本异常，则无法保证一定可以读到与W 个副本有交集的副本集合，则读服务的一致性下降。所以N、W、R 控制了系统的可用性，也是系统对用户的服务承诺。

    3. 日志技术（应用在mysql中）

        redo log

        check point

    4. 两阶段提交协议（2PC）（中心化副本控制协议）、3PC、TCC（XTS是基于TCC的）

    5. MVCC（多版本并发控制，也是应用在DB中的 ）

    6. Paxos协议。强一致性、高可用的去中心化的分布式协议。

有一组完全对等的参与节点（称为accpetor），这组节点各自就某一事件做出决议，如果某个决议获得了超过半数节点的同意则生效。Paxos 协议中只要有超过一半的节点正常，就可以工作。

角色：Proposer、Acceptor、Listener

利用了Quorom机制：另W=R=N/2+1

      协议通过引入轮次，使得高轮次的提议抢占低轮次的提议来避免死锁。协议设计关键点是如何满足“在一次Paxos 算法实例过程中只批准一个Value”这一约束条件。

2.4 CAP理论

Consistency (一致性)：CAP 理论中的副本一致性特指强一致性；

Availiablity(可用性)：指系统在出现异常时已经可以提供服务；

Tolerance to the partition of network (分区容忍)：指系统可以在网络分区(节点间网络不通，整个集群被分成了多个区域)这种异常情况下，具有的容错能力；

无法设计一种分布式协议，使得同时完全具备CAP三个属性

                        C       A        P

Lease机制：满足    完全   部分

Quorum：    部分    部分   部分

两阶段：       完全   差      差

Paxos：        完全    部分    部分

在CAP之后，BASE理论（Basic Availiablity，Soft status，Eventually consistent）