总结

本周主要介绍了分布式数据库的分片及部署方案、CAP原理、数据最终一致性、HBase架构相关知识、ACID与BASE、ZooKeeper实现分布一致性以及一个Doris海量KV Engine的案例。

1       分布式数据库（下）

1.1     数据分片概念

当单表数据量很大的时候，或者有较高并发写数据的情况下，就需要进行数据分片技术了。

数据分片：

    把一张数据量很大的表拆分成若干“片”，分表存储在不同的服务器上。这样不管数据读还是写的时候，都只需访问对应的“片“所在的服务器即可，这样有效降低了单个服务器的负载压力，降低服务器数据存储的写和读的压力。

1.2     数据分片的实现

1.2.1     硬编码实现

1.2.2     映射表外部存储

可看作是对硬编码分片的一种优化方法，比硬编码更加灵活， 这种方式实际中也不太常用，因为数据量很大的情况下，外部存储映射表记录数也会很大；另外原本进行一次查找就变成了两次查找了（先要查映射表）；所以这种方案会增加复杂性以及可能导致数据不一致性。

1.2.3     分布式数据库中间件

前两种分片方案都需要应用程序来决定到底要访问哪台数据库服务器，这样其实会带来应用程序的复杂性。而基于分布式数据库中间件的分片可以做到对应用程序“透明“。

分布式数据库中间：

       是面向应用程序提供的访问数据的中间件，使应用程序可以向访问普通数据库一样的操作分布式数据库。由分布式数据库中间件实现数据的分片路由。

基础架构：



1.     SQL解析模块：

一条SQL提交进来后，首先要解析出待查询的表以及表的分片字段，拿到表和分片字段后发给SQL路由模块进行计算。

2.     SQL路由模块

根据获取到SQL解析模块传入的表和分片字段后，进行路由选择计算，以得到要真正访问的数据库服务器是哪个。

3.     SQL执行代理模块：

根据SQL路由模块计算结果，将SQL发送给对应的数据库服务器进行执行。（这里有可能根据SQL查询条件将SQL语句发送给多个数据库服务器进行执行）

4.     结果合并模块：

被发送给多个数据库服务器的SQL语句执行完毕后，数据库服务器都会将结果进行返回，所以需要结果合并模块进行最终返回结果的合并，最终返回给应用程序。

1.2.4     常见的分部式数据库中间件

MyCat：

       MyCat又是在Cobar基础上发展的版本，两个显著点是：

1.     后端由BIO改为NIO，并发量有大幅提高。

2.     增加了对Order By、Group By、limit等聚合功能的支持（虽然Cobar也可以支持Order By、Group By、limit语法，但是结果没有进行聚合，只是简单返回给前端，聚合功能还是需要业务系统自己完成）



1.3     数据库部署方案

1.3.1     单一服务与单一数据库

这是最简单的数据库部署方案，适用于数据库压力不大，可用性要求不高的简单场景。



1.3.2     主从复制实现伸缩

这是提供了读写分离的数据库部署方案，适用于数据库访问压力较大的情况。



1.3.3     两个Web服务及两个数据库

业务分库情况下的数据库部署方案，适用于应用进行业务分离的情况，对应的，不同业务应用访问的数据库服务器也需要进行分离了。

       注意:

              数据库在做分片之前，一般都需要先做业务分库哦！

1.3.4     综合部署

一般当数据库访问压力增大时，建议先做业务分库；

如果业务分库后如果有些库中的表记录数太多，则可以进行数据分片；

同时可以使用主从复制来实现数据库的读写分离，降低服务器读压力，分摊服务器负载；

也可以使用主主复制来实现数据库的高可用。



2       CAP原理

2.1     什么是CAP原理

CAP原理指的是一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区耐受性（Partition Tolerance）这三项中的两项：

C：Consistency：

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

A：Availability：

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

P：Partiton Tolerance：

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

当网络分区失效发生的时候，我们要么取消操作，这样数据就是一致的，但是系统却不可用;要么我们继续写入数据，但是数据的一致性就得不到保证。

对于一个分布式系统而言，网络失效一定会发生，也就是说，分区耐受性是必须要保证的，那么在可用性和一致性上就必须二选一。

当网络分区失效，也就是网络不可用的时候，如果选择了一致性，系统就可能返回一个错误码或者干脆超时，即系统不可用。如果选择了可用性，那么系统总是可以返回一个

数据，但是并不能保证这个数据是最新的。

所以，关于CAP原理，更准确的说法是，在分布式系统必须要满足分区耐受性的前提下，可用性和一致性无法同时满足。

3       数据最终一致性

3.1   最终一致性概念

存储系统可以保证：对于同一个数据对象，如果没有更多的更新产生，最终所有的访问都会返回最新更新的数据（版本）。

3.2   最终一致性写冲突处理策略

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

3.3   客户端冲突解决

客户端可根据具体业务进行不通客户端数据的合并。

3.4   投票解决冲突( Cassandra )

当客户端A写入数据时，尝试写入3份数据，这3份数据至少有2份数据写入成功时，就会返回操作成功的响应。

当客户端B去读取数据时，尝试读取3份数据，这3份数据至少2份数据读取成功并一致时，才算做读取成功；如果返回的2份数据不一致，则还是要等第3份数据恢复后再次读取，然后比较所读取到的总共这3份数据的一致性，最终通过投票确定返回的数据。



4       HBase架构

HBase是一个分布式的、面向列的开源数据库，它在Hadoop之上提供了类似于Bigtable的能力。HBase是Apache的Hadoop项目的子项目。HBase不同于一般的关系数据库，它是一个适合于非结构化数据存储的数据库。用HBase技术可在廉价PC Server上搭建起大规模结构化存储集群。



HBase利用Hadoop HDFS作为其文件存储系统；

HBase通过Hadoop HDFS的数据复制实现数据存储的高可用。

HBase访问过程如下所示: ？？？？



这张图其实是有问题的，访问过程应该不涉及HMaster的才对

寻找 RegionServer

• ZooKeeper–> -ROOT-(单 Region)–> .META.–> 用户表

-ROOT-表

• 表包含.META.表所在的 region 列表，该表只会有一个 Region；

• root region 永远不会被 split，保证了最多需要三次跳转，就能定位到任意 region 。

• Zookeeper 中记录了-ROOT-表的 location。

.META.表

• 表包含所有的用户空间 region 列表，以及 RegionServer 的服务器地址

• .META.表每行保存一个 region 的位置信息，row key 采用表名+表的最后一行编码而成。

• 为了加快访问，.META.表的全部 region 都保存在内存中。

联系 regionserver 查询目标数据

regionserver 定位到目标数据所在的 region，发出查询请求

region 先在 memstore 中查找，命中则返回

如果在 memstore 中找不到，则在 storefile 中扫描（可能会扫描到很多的 storefile----bloomfilter 布隆过滤器）布隆过滤器可以快速的返回查询的rowkey是否在这个storeFile中, 但也有误差, 如果返回没有,则一定没有,如果返回有, 则可能没有



5       ACID与BASE

ACID：指传统关系型数据库的事务机制，它具有以下特性：

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

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

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

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

BASE： BASE 是 Basically Available（基本可用） 、Soft-state（软状态） 和 Eventually Consistent（最终一致性） 三个短语的缩写：

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

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

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

6       分布一致性ZooKeeper

ZooKeeper是一个为分布式应用提供一致性服务的软件，提供的功能包括：配置维护、域名服务、分布式同步、组服务等。



6.1     分布式系统脑裂

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

Paxos 算法就是为了解决这个问题而生的。

6.2     分布式一致性算法Paxos

Paxos算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。

Paxos算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。

它利用大多数 (Majority) 机制保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。

Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner):



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

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

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

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。



Paxos算法流程中的每条消息描述如下：

       Prepare: Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。

Promise: Acceptors收到Prepare请求后，做出“两个承诺，一个应答”。

两个承诺：

1. 不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Prepare请求。

2. 不再接受Proposal ID小于（注意：这里是< ）当前请求的Propose请求。

一个应答：

不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。

·       

6.3     Zab协议

其原理是选择 数据最新 -》 服务编号最大的顺序选择，所以选主很快

7       案例：Doris-海量KV Engine的设计

Doris 是一种支持 Key、Value 数据结构的分布式存储系统，核心要解决的问题是分布式路由、分布式集群伸缩、分布式数据冗余与失效转移，它是阿里巴巴的一个内部产品。

Doris 的主要访问模型是，应用程序 KV Client 启动后，连接控制中心 Administration，从控制中心获得整个 Doris 集群的服务器部署信息及路由算法，Client 使用 Key 作为参数进行路由计算，计算得到集群中某些服务器作为当前 Key、Value 数据存储的服务器节点；然后 KV Client 使用自定义的通信协议将数据和命令传输给服务器上的 Data Server 组件，DataServer 再调用本地的 Berkeley DB 将数据存储到本地磁盘。

Doris 的核心技术就是这个架构模型上创新性地实现了自己独特的分区路由算法、失效转移策略、集群伸缩设计方案。并在项目开发过程中，将这个三个技术创新申请了技术专利。

7.1     Doris基本访问架构

Doris 将存储服务器集群分成多个 group（默认情况下为 2 个 group），数据写操作的时候，根据分区路由算法，在每个 group 里计算一个服务器地址，异步并发同时向多个 group 的服务器上写入数据，以此保证数据有多个备份。



7.2     分区路由算法

Doris 采用一种基于虚拟节点的分区路由算法，Key 使用余数 Hash 算法计算得到虚拟节点下标。（虚拟节点下标 = hash(md5(key)) mod 虚拟节点个数）

虚拟节点和物理服务器节点之间计算建立一个映射关系，通过映射关系查找实际要访问的物理服务器 IP 地址。

路由算法在初始化的时候就预先设立一个较大的数字，比如 100000，当存储服务器集群需要伸缩的时候，要增加一个服务器，虚拟节点和下标计算算法不变，仅仅调整虚拟节点和物理服务器节点的映射关系就可以了。

这种基于虚拟节点的分区路由算法相对于传统的一致性 Hash 路由算法，可以获得更好的数据负载均衡，即数据在各个服务器上的存储分布更加均衡。在集群伸缩、增加服务器的时候可以做到更少迁移数据。

在实践中，这种算法的一个更大优势是，如果将物理存储的文件系统和虚拟节点关联，即一个虚拟节点对应一个物理存储文件，那么当集群扩容，进行数据迁移的时候，就可以以文件为单位进行数据拷贝，这样迁移速度和运维成本都非常低。

这里有一个问题需要注意，在增加服务器的时候，如何重新计算虚拟节点与物理节点的映射关系，使新的映射关系依然处于负载均衡的状态？

其实可以采用节点轮询的方式实现，即添加新的服务器后，按余数法重新计算下每个服务器应该对应多少虚拟节点，假设计算结果为n，则轮询各个原有节点上的虚拟节点个数，个数超过n的虚拟节点都应该迁移到新增加的服务器上去。

7.3     失效转移策略

当 KV Client 访问某台服务器失败的时候，Doris 会启动失效转移策略。具体来说，Doris 将失效分为三种情况：瞬时失效、临时失效、永久失效。

不同情况采用不同的失效转移策略，具体过程如下：

当第一次不能访问服务器的时候，Doris 认为这是瞬时失效，会进行访问重试；

如果三次重试后仍然失败，就会把失败信息提交给控制中心。

控制中心检测该服务器心跳是否正常，并进行尝试访问，如果访问失败，就将该服务器标记为临时失效，并通知所有 KV Client 应用程序。



KV Client 应用程序收到服务器失效通知的时候，启动临时失效策略，将原本需要写入到失效节点（图中的物理节点 2）的数据写入临时日志节点（图中的物理节点 X），而读操作则只访问正常的物理节点 1。

当临时失效节点 2 恢复正常运行，系统会将失效期间写入临时日志节点 X 的数据合并恢复到物理节点 2，这段时间物理节点 2 只提供写服务，不提供读服务。当所有数据恢复完毕，集群访问恢复正常。

而对于永久失效的节点，需要添加新的服务器以代替下线的服务器，基本策略就是将另一个 group 正常使用的服务器数据拷贝到新添加的服务器上即可。

需要说明的是，上述三种失效转移过程，除了服务器永久失效后，需要工程师手动添加服务器，并到控制中心添加新服务器配置、激活启用外，其他情况不需要任何人工干预，全部自动化完成。

7.4     集群伸缩设计

分布式系统的一个重要设计目标是集群弹性可伸缩，如果当前的服务器数目不能满足业务的负载压力要求，那么就添加更多的服务器去增强处理能力。

对于分布式数据存储服务器的伸缩性扩容而言，必然伴随着数据的迁移，就是将原先服务器中的部分数据迁移到新的服务器上。



具体过程为：

1. 向集群中一个分组 group 添加新的物理服务器，部署并启动 Doris 服务器进程。

2. 将这个 group 的所有服务器设置为临时失效。

3. 使用路由算法重新计算加入服务器后的虚拟节点分布，并把需要迁移的虚拟节点对应的物理文件拷贝到新服务器上。

4. 设置 group 所有服务器临时失效恢复，将扩容期间的数据更新写回到这些服务器。