分布式数据库、分布式一致性算法

分布式数据库

1. 关系型数据库分布式

MySQL高可用、分布式架构

• MySQL主从复制：主节点负责读写操作，从节点负责读操作。数据复制，基于状态复制机原理实现

• MySQL一主多从复制：多个从节点，可实现分摊读负载、专节点专用、便于冷热备份、高可用

• MySQL主主复制：两个主节点都可以写操作，两个主节点可以相互复制数据，但只能单写。

• MySQL主主失效恢复：如果主节点A故障可切换到主节点B进行写操作，同时所有读操作需迁移到主节点B的从机上



复制只增加了数据的读并发处理能力，并没有增加写并发、存储能力， 同时，更新表结构会导致巨大的同步延迟。那怎么解决写并发、存储能力呢？

数据分片

实现数据分片几种方式

• 硬编码实现：通过代码硬编码算法映射服务器节点

• 映射表外部存储：通过配置映射表映射服务器节点

• 分布式数据库中间件（MyCat）

Mycat/Cobar

整体架构



系统组件模型



扩容策略



数据库部署方案

• 单体数据库



• 主从复制数据库



• SOA服务部署（每个服务对应一组数据库）



• 混合部署（支持数据分片、主从复制、主主复制）



2. NoSQL



原理

CAP理论：见下文



HBase架构



查询数据的流程：

i) 应用程序 从 zookeeper中请求 HMaster地址；

ii) 输入key, 从HMaster中获取HRegionServer地址；

iii) 输入key, 从HRegionServer中查询数据；

iv) HRegionServer从HRegion实例查询数据；



HBase数据结构

LSM-Tree(Log Structed Merge Tree)

是 日志(WAL)+ 跳表(SkipList) + 分层有序表(SSTable) 的数据结构，优化写性能，同事兼顾查询性能



3. 海量分布式存储引擎实践

逻辑架构



关键技术点

i) 数据分区：基于虚拟节点的分区算法，key hash分配到virtual node, 然后通过查表法查询virtual node于物理节点的对应关系

ii)集群管理：健康检查和配置抓取，通过配置服务器仲裁故障

iii) 可用性关键场景处理：包含瞬时失效(重试)、临时失效(启动备用节点，恢复后迁移数据)、永久失效(下线)

iv) 扩容机器实施数据迁移

v) 扩容实时数据迁移：计算两个route算法，不相同则迁移



分布式一致性算法

1. 分布式理论基础

CAP

Consistency(一致性)：每次读取数据都应该是最近写入的数据或返回一个错误，而不是过期数据

Availability(可用性)：每次请求应该得到一个响应，而不是一个错误或失去响应

Partition tolerance(分区耐受性)：网络原因，部分服务器节点之间消息丢失或延迟，系统依然可以操作

在分布式系统必须满足分区耐受性的前提下，可用性和一致性无法同时满足。



CAP原理，在满足可用性时，可能存在数据一致性的冲突，怎么解决？达成最终一致性

• 基于时间戳解决最终一致性写冲突

• 客户端合并结果解决冲突

• Cassandar投票：至少半数以上节点响应

• Cassandar分布式解决方案：客户端连接任一节点，按照投票一致性写入行记录

ACID

关系型数据的事务特性，包含：

原子性(Atomicity):要么全部完成，要么全部取消

隔离性(Isotation):两个事务相互间的隔离，靠锁实现

持久性（Durability): 一旦事务提交，不管发生崩溃或出错，数据要保存数据库。

一致性（Consistency）：与CAP中一致性不同，是指合法数据(满足约束和完整性)才能写入

BASE

是NoSQL理论基础，包含：

基本可用(Basically Available)：允许部分可用性，如响应时间，功能损失

软状态(Soft State)：允许中间状态

最终一致性(Eventually Consistent)：系统保证数据能够达到一致，而不需要实时保证强一致性



2. 分布式一致性算法

只要脱离了单机系统，就会存在多机之间不一致的问题。多个节点保证具有相同的数据，解决这个问题，就需要一致性算法。一致性从强到弱分类为：线性一致性、顺序一致性、因果一致性、单调一致性、最终一致性。



可避免分布式系统脑裂（不同服务器获取相互冲突的数据信息或执行指令，导致整个集群陷入混乱，数据损坏）发生。



常见一致性协议算法

• Paxos：包含三个角色：Proposer, Acceptor, Learner

i) Prepare 阶段， Proposer向Acceptors发出Prepare请求，Acceptors进行Promise承诺；

ii) Accept阶段， Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，进行accept处理；

iii) Learn阶段，Proposer在收到多数Acceptors的accept之后，表示本次accept成功，决议形成，将决议发送给所有Learners;

• Raft：Paxos变种

多数派投票选举算法, 包含角色：Leader, Candidate, Follower

• ZAB：Paxos变种

具有优先级的民主投票，包含角色：Leader, Follower, Observer



Zookeeper

架构



协议



记录结构



应用场景

• 配置管理（配置中心）

Administrator通过setData维护配置信息，Consumer通过getData读取配置信息

• 选Master

通过getData("/servers/leader", true)获取master节点，如果获取失败，create("servers/leader", hostName, EPHEMERAL)取得master

• 集群管理（负载均衡）

watch getChildren(/nodes, true), trace节点故障