1 分布式数据库

1.1 数据分片

将大数据表数据拆分成若干片，每个服务器存储其中的一片或者几片，以提供超大表的存储。读写均操作对应的分片，以降低数据读写和存储压力。

分片方式：

• 硬编码实现数据分片

• 映射表外部存储

面临的挑战：

• 处理逻辑复杂，需要大量额外代码

• 无法执行多分片联合查询

• 无法使用数据库事务

• 随着数据增长，如何增加更多服务器



1.2 分布式数据库中间件

数据库中间件，根据一定的规则进行路由选择，找到对应的数据所在服务器。

Mycat/Amoeba/Cobar架构



2 NOSQL

2.1 CAP原理

https://xie.infoq.cn/article/be51dad73cbfac8c6e8c0bf9f

2.2 ACID与BASE

2.2.1 ACID

是指在数据库管理系统（DBMS）中，事务(transaction)所具有的四个特性：原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation，又称独立性)、持久性(Durability)。

• A - Atomicity 原子性

事务要么全部完成，要么全部取消。如果事务崩溃，需要事务回滚。

• C - Consistency 一致性

只有合法的数据（依照关系约束和函数约束）才能写入数据库，与CAP的一致性有区别。

• I - Isolation 隔离性

如果2个事务T1和T2同时运行，最终结果是相同的，不管谁先结束，隔离性主要依靠锁实现。

• D - Durability 持久性

一旦事务提交，不管发生什么，数据都要保存在数据库中。



2.2.2 BASE

接受最终一致性的理论支撑是BASE模型，BASE全称是BasicallyAvailable（基本可用）, Soft-state（软状态/柔性事务）, Eventually Consistent（最终一致性）。BASE模型在理论逻辑上是相反于ACID（原子性Atomicity、一致性Consistency、隔离性Isolation、持久性Durability）模型的概念，它牺牲高一致性，获得可用性和分区容忍性。

• Basically Available（基本可用）

分布式系统在出现不可预知故障的时候，允许损失部分可用性

• Soft state（软状态）

软状态也称为弱状态，和硬状态相对，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据听不的过程存在延时。

• Eventually consistent（最终一致性）

不保证任意时刻任意节点上的同一份数据都相同，但随着时间的迁移，不同节点上的同一份数据总是在向趋同的方向变化



3 分布式一致ZooKeeper

3.1 分布式脑裂



在分布式系统中，不同服务器获得了互相冲突的数据信息或者执行命令，导致整个集群陷入混乱，数据损坏，称作分布式系统脑裂。

3.2 分布式一致性算法Paxos

在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区）等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

有三种角色：

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。

• Acceptor：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。

• Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。



在多副本状态机中，每个副本同时具有Proposer、Acceptor、Learner三种角色。

Paxos算法通过一个决议分为两个阶段（Learn阶段之前决议已经形成）：



1. 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。

2. 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。

3. 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。



算法描述：



1. 获取一个Proposal ID n，为了保证Proposal ID唯一，可采用时间戳+Server ID生成；

2. Proposer向所有Acceptors广播Prepare(n)请求；

3. Acceptor比较n和minProposal，如果n>minProposal，minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回；

4. Proposer接收到过半数回复后，如果发现有acceptedValue返回，将所有回复中acceptedProposal最大的acceptedValue作为本次提案的value，否则可以任意决定本次提案的value；

5. 到这里可以进入第二阶段，广播Accept (n,value) 到所有节点；

6. Acceptor比较n和minProposal，如果n>=minProposal，则acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回minProposal。

7. 提议者接收到过半数请求后，如果发现有返回值result >n，表示有更新的提议，跳转到1；否则value达成一致。

3.3 ZooKeeper 架构

Paxos算法比较复杂，为了简化实现，ZooKeeper使用了一种叫ZAB(ZooKeeper原子消息广播协议)的算法使Zookeeper集群保证数据更新的一致性，并且通过集群方式保证Zookeeper系统高可用。但是Zookeeper集群Leader宕机后，在选举新Leader的过程中，是不提供外界服务的，不满足可用性。