1 分布式数据库



1.1 数据分片



所谓数据分片就是将几十亿的大数据表数据拆分成若干片，每个服务器存储其中的一片或者几片，以提供超大表的存储。读写均操作对应的分片，使用此种方式以降低数据读写和存储压力。

1.2 实现方式

1.2.1 硬编码实现数据分片



即通过一定的计算规则，将数据记录插入到对应的服务器中，这种计算规则可以是奇偶、余数等。如下图所示通过对用户请求id进行奇偶判断，来确定记录输出的服务器位置，比如id=33是奇数，则将该记录存储到服务器2中，反之将其存储到服务器1中。



1.2.2 映射表外部存储



这种方式则是通过一个外部的映射表将每一条记录跟每一个服务器进行关联，形成一个字典表，当需要查询数据时先查询外部映射表找对对应服务器，然后再查询此服务器。



这种方式实际中使用的并不多，因为（1）需要查询两次才能找到数据，（2）映射表的引入增加了应用程序的复杂性，以及数据的不一致性。



1.2.3 分布式数据库中间件



通过数据库中间件，根据一定的规则进行路由选择，找到对应的数据所在服务器。这种方式封装了数据的读写和查询规则，使得应用程序不需要知道数据存储在哪个节点上，只需要将查询语句发送给中间件即可。

比如MyCat、Amoeba/Cobar等均属于数据库中间件。



1.3 实践中的扩容策略



在生产实践中，一开始就把规模规划好，多个schema放在一个服务器上，当扩容时只需要将schema迁移到新服务器上即可。这样仅需要迁移schema数据库，以及修改少量配置，而不必大动干戈修改数据库分片算法。



分库是对业务不同的表进行分库，分片则是对同一张表进行分库。

1.4 CAP原理



分布式系统，其可用性、一致性和分区耐受性三者不能同时满足的。



一致性（Consistency）是说，每次读取的数据都应该是最近写入的数据或者返回一个错误（Every read receives the most recent write or an error），而不是过期数据，也就是说，数据是一致性的。



可用性（Availablility）是说，每次请求都应该得到一个响应，而不是返回一个错误或者失去响应，不过这个响应不需要保证数据是最近写入的（Every request receives a (non-error) response, without the guarantee that it contains the most recent write），也就是说系统需要一直都是可以正常使用的，不会引起调用者的异常，但是并不保证响应的数据是最新的。



分区耐受性（Partition tolerance）是说，即使因为网络原因，部分服务器节点之间消息丢失或者延迟了，系统依然应该是可以操作的（The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes）。



一般来说，分布式系统不能完全保证，每台系统都可能因为网络或者其他原因导致数据丢失的情况。因此分区耐受性是无可避免的，因此可以认为CAP的P总是成立的。根据CAP原理可知，C和A不能同时做到。即如果想要做到系统的可用性，那么就要割舍一部分的数据一致性，反之亦然。



最终一致性



用户访问过程中可能是不一致的，但是随着时间的推移，最终的结果是一致的。



• 简单冲突处理策略：根据时间戳，最后写入覆盖。

• 客户端冲突解决：从业务角度进行数据合并。

• 投票解决冲突（Cassandra）：尝试写入三个节点，等待至少两个节点响应更新成功。尝试从三个节点读取，等待至少两个节点返回，取最新版本。

2 Hbase架构



首先一个Key只会有一个HRegionServer负责，不会出现写入多个位置，这样保证了数据一致性。



Habse可用性较差，当一个HRegionServer宕机，处在这台机器上的key将不可访问。



存储结构是：LSM树。

3 ACID与BASE

3.1 关系型数据库的ACID

• 原子性（Atomicity）：事务要么全部完成，要么全部取消。如果事物崩溃，状态回到事务之前（事务回滚）。

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

• 持久性（Durability）：一旦事务提交，不管发生什么（崩溃或者出错），数据要保存在数据库中。

• 一致性（Consistency）：只有合法的数据（依照关系约束和函数约束）才能写入数据库。



3.2 非关系型数据库的BASE



• 基本可用（Basically Available）系统在出现不可预知故障时，允许损失部分可用性，如响应时间上的损失或功能上的损失。

• Soft state（弱状态）软状态，指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

• Eventually consistent（最终一致性）指系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态，因此最终一致性的本质是需要系统保证数据能够达到一致，而不需要实时保证系统数据的强一致性。

4 Doris - 海量KV Engine

基于对等Node访问，双写单读保证可用性。

4.1 关键技术点 - 可用性关键场景



瞬时失效：由于JVM垃圾回收引起的STW（Stop The World）或者由于网络原因导致访问DataServer失败的现象，这种现象不会持续太久。



临时失效：

• 服务端升级或者网络暂时不可用

• 失效机器在短时间内可恢复（例如：2小时内）

• 恢复后数据和失效前一致



永久失效：机器下线。

4.2 临时失效及恢复过程



（1）KV客户端写入Data Server失败后，重试3次后依然失败的话，将失败状态报告给配置服务器。

（2）配置服务器尝试写入Data Server，如果写入成功则表示瞬时失效或者其他原因导致的KV客户端访问不了DS。否则，配置服务器将做出仲裁，将Data Server标记为临时失效。

（3）KV Client将不再写入失效的Data Server，而是通过将操作日志写入到备份服务器，临时存放失效节点的数据。

（4）待失效Data Server恢复后，将备份服务器的数据迁移回来，同时Data Server只写不读。

5 分布式一致Zookeeper

5.1 分布式脑裂



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

5.2 分布式一致性算法Paxos



三个角色：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达成一致。



5.2 Zookeeper如何保证一致性的？



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