06 技术选型（二）分布式数据库、CAP 、NoSQL

6.1 分布式关系数据库

MySQL 复制

1. MySQL 主从复制

MySQL 一主多从复制

• 分摊负载（读写分离）

• 专机专用（数据分析、数据读取）

• 便于冷备（间接实现数据冷备）

• 高可用（部分，读高可用）

2. MySQL 主主复制

保证写高可用

• 主主复制的两个服务器不能并发写入：可能写同一条数据，逻辑上没有办法保证不发生冲突

• 复制只能增加数据的读并发处理能力，不能增加写并发能力和存储能力：水平伸缩，增加服务器，可以增加并发能力，但是……

• 更新表结构会导致巨大的同步延迟：在实践中，关闭表结构的同步，由运维工程师来人工操作表结构的操作

数据分片

• 分片目标

• 分片特点

• 分片原理

10 亿数据分布在 100 台服务器上，高并发的计算和存储

分片实现方法

• 硬编码实现数据分片：利用用户 ID 的奇偶来对用户记录分片

• 映射表外部存储：

数据分片的挑战

• 需要大量的额外代码，处理逻辑因此变得更加复杂

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

• 无法使用数据库事务

• 随着数据的增长，增加更多的服务器比较困难

分布式数据库中间件

Amoeba/Cobar 架构

Cobar 系统组件模型

如何做集群的伸缩：需要在一开始就准备好数据库集群的模数——最多可容纳的数据库服务器数目

数据库部署方案

• 单一服务与单一数据库

• 主从复制实现伸缩

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

• 综合部署

6.3 CAP 原理与 NoSQL 数据库架构

CAP 定理（CAP theorem）又被称作布鲁尔定理（Brewer's theorem），是加州大学伯克利分校的计算机科学家埃里克·布鲁尔（Eric Brewer）在 2000 年的 ACM PODC 上提出的一个猜想。2002 年，麻省理工学院的赛斯·吉尔伯特（Seth Gilbert）和南希·林奇（Nancy Lynch）发表了布鲁尔猜想的证明，使之成为分布式计算领域公认的一个定理。

CAP theorem (Brewer's theorem, 2000 ACM PODC)

Consistency: Every read receives the most recent write or an error

Availability: 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 原理

• 一致性

• 可用性

• 分区耐受性

老师给出的是维基百科上的定义，极客时间《从零开始学架构》中，提到了 Rober Greiner 的阐述 http://robertgreiner.com/2014/08/cap-theorem-revisited/

In a distributed system (a collection of interconnected nodes that share data.), you can only have two out of the following three guarantees across a write/read pair: Consistency, Availability, and Partition Tolerance — one of them must be sacrificed.

其中强调了 interconnected 和 share data，分布式系统并不一定会互联和共享数据，比如 Memcached 集群，share nothing，不符合 CAP 理论探讨的范围；而 MySQL 集群是互联和数据复制的，属于 CAP 探讨的对象。

其次，强调了 write/read pair，也就是说 CAP 关注读写操作，而不是其他功能，比如 ZooKeeper 的选举机制，就不是 CAP 的探讨范围。

Consistency: A read is guaranteed to return the most recent write for a given client.

对某个指定的客户端来说，读操作保证能够返回最新的写操作结果。从客户端角度描述，read，从读写角度来描述一致性

Availability: A non-failing node will return a reasonable response within a reasonable amount of time (no error or timeout)

非故障节点在合理的时间内返回合理的相应（不是错误和超时的相应）。只有非故障节点才能满足可用性要求，并且明确不能超时、不能出错，结果不一定“正确”，但是合理。

Partition Tolerance: The system will continue to function when network partitions occur.

当出现网络分区后，系统能够继续“履行职责”。function 强调履行职责，即可用性；另外只要出现 network partitions 分区现象，不管什么原因，可能是丢包，也可能是连接中断，还可能是拥塞……

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

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

分布式系统理论上不可能选择 CA 架构，只能选择 CP 或者 AP 架构。

CAP 定理的使用场景是同构副本性（主从、多主）类型的架构，其中一致性是指顺序一致性、读写一致性。

HBase、MongoDB、ZooKeeper 属于 CP 架构，Cassandra、CounchDB 属于 AP 系统

zk 多数节点正常就可以正常运行，分区中的少数节点会进入 leader 选举状态，这个状态不能处理读写操作，因此不符合 A，如果不考虑实时一致性，zk 基本满足 CP 的要求

CAP 关注的粒度是数据，而不是系统。在实际设计过程中，每个系统不可能只处理一种数据，而是包含多种类型的数据，有的数据必须选 CP，有的数据必须选 AP。比如用户管理系统中，用户账号数据（用户 ID、密码） CP，而用户信息数据（昵称、兴趣、爱好、性别、自我介绍） AP

CAP 是忽略网络延迟的。CAP 理论中的 C 在实践中是不可能完美实现的，在数据复制的过程中，节点 A 和节点 B 的数据并不一致。

如果节点间的网络连接一切正常，也就是 P 不存在的情况下，没有必要放弃 C 或者 A，可以同时满足 CA。

放弃不等于什么都不做，CAP 理论的牺牲 sacrificed 只是说在分区过程中。在系统整个运行周期中，大部分时间都是正常的，99.99% 的可用性，一年不可用的时间只有 50 分钟，5 个 9 的可用性系统，一年下来不可用的时间只有 5 分钟。分区期间放弃 C 或者 A，并不意味着永远放弃 C 和 A，可以在分区期间进行一些操作（比如记录日志），当分区故障解决之后，系统重新达到 CA 状态。

最终一致性

• 最终一致写冲突

客户端冲突解决

投票解决冲突（Cassandra）

Cassandra 分布式架构

Hbase 架构

LSM 树 Log Structed Merge Tree

LSM 1996 年发明，2006 年在 Bigtable 的 Paper 中被提到

当数据写入时，延迟写磁盘，将数据先存放在内存中的树里，进行常规的存储和查询。当内存中的树持续变大达到阈值时，再批量地以块为单位写入磁盘的树中。因此，LSM 树至少需要由两棵树组成，一棵是存储在内存中较小的 C0 树，另一棵是存储在磁盘中较大的 C1 树。

• 在内存达到阈值时启动书合并 Merge Trees

• 用批量写入代替随机写入，用预写日志技术保证内存数据在系统崩溃后可以恢复

• 数据采取类似日志追加的方式写入 Log Structured 磁盘

WAL, Write Ahead Log 预写日志技术

1. 内存中的程序在处理数据时，先把对数据的修改作为一条记录，顺序写入磁盘 log 文件

2. 数据写入 log 文件后，备份成功

3. 系统周期性检查内存中的数据是否处理完成，并生成检查点 Check Point，可以删除 log 文件中处理完成的数据

4. 系统崩溃重启，从磁盘中读取检查点，就能知道最后一次成功处理数据在 log 文件中的位置，然后将检查点之后的数据修改，从 log 文件读出，重新加载到内存

使用清空块 Emptying Block 和填充块 Filling Block 进行滚动归并

在 C0 树到 C1 树的滚动归并过程中，几乎所有的读写操作都是以多页块 Multi-Pages Block 为单位，将多个叶子节点进行顺序读写（磁盘的顺序读写性能和内存几乎是一个数量级的）

LSM 树在检索的时候，先到内存中的 C0 树中查询，若果查到了，就不再查询 C1 树；如果没有查询到 key，那么就去磁盘中的 C1 树中查找。

如果一个系统的检索主要是针对近期数据的，那么大部分数据是可以在内存中查到的，检索效率就会非常高。

对于被删除的数据，将这些数据的 key 插入到 C0 树中，并且存入删除标记，在滚动归并时完成批量“数据删除”动作。

LSM 使用 Bloom filter 来提高查询性能，有可能 false positive，但不可能 false negative

基于 LSM 的存储引擎

• LevelDB

• RocksDB

• Pebble

• BadgerDB

• WiredTiger

ACID 与 BASE

ACID

• Atomicity 原子性：事务要么全部完成，要么全部取消。如果事务崩溃，状态回到事务之前（事务回滚），就像这个事务从来没有执行过一样。

• Consistency 一致性：只有合法的数据（依照关系约束和函数约束）才能写入数据库。在事务开始之前和事务结束以后，数据库的完整性没有被破坏。

• Isolation 隔离性：如果两个事务 T1、T2 同时运行，事务 T1 和 T2 最终的结果是相同的，不管 T1、T2 谁先结束，隔离性主要依靠锁来实现。隔离性可以防止多个事务并发执行时，由于交叉执行而导致数据的不一致。事务隔离的级别有：读未提交 Read Uncommitted、读提交 Read Committed、可重复读 Repeatable Read、串行化 Serializable

• Durability 持久性：一旦事务提交，不管发生什么（出错或崩溃），数据要保存在数据库中。事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

BASE

• Basically Available 基本可用：系统在出现不可预知故障时，允许牺牲部分可用性，如响应时间上的损失或功能上的损失，保证核心可用

• Soft state 弱状态、软状态：允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的正题可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。这里的中间状态就是 CAP 理论中的数据不一致。

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

BASE 理论本质上是对 CAP 理论的延伸和补充，更具体的说，是对 CAP 中 AP 方案的一步补充。

ACID 是数据库事务完整性的理论，CAP 是分布式系统设计理论，BASE 是 CAP 理论中 AP 方案的延伸。

ZooKeeper 的 ZAB 算法与 Paxos 的本质区别是什么？

https://time.geekbang.org/dailylesson/detail/100028458

ZAB, Zookeeper Atomic Broadcast

角色：逻辑概念，给及群众的每一个物理节点都赋予一个独特的身份。

• Leader 领导者

• Follower 跟随者

• Observer 观察者

Zookeeper 跨机房集群部署

事务操作：指能够改变 Zookeeper 状态的操作，一般包括 ZNode 节点的创建、删除、内容更新等操作。

ZNode：Zookeeper 中用来存储数据的基本单元，每一个 ZooKeeper 节点都会维护它本身需要存储的数据，创建和最后一次更新的时间戳，以及子节点数量等基本信息

在大数据生态圈中，保证一致性的算法，除了 ZAB 和 Paxos 之外，还有

1. 搜索引擎 ElasticSearch 中的 Hash 路由算法

2. 负载均衡 HaProxy 中的一致性 Hash 算法

3. 列式存储引擎 Cassandra 中的 Gossip 闲话算法

4. 键值存储引擎 Redis 中的 Raft 选举算法

Paxos 最先解决拜占庭将军问题的算法，利用过半选举机制，保证了集群副本的一致性；不过，针对微服务中服务注册与发现的场景，对集群写性能和可用性有较高的要求，Paxos 就已经不再适用了。

Raft 选举算法，Redis 使用 Raft 实现了自己的分布式一致性，Raft 本身和 Paxos 并没有场景上的区别，更多的是协议上的简化，使得其实现起来工程量会小很多

ZAB 原子广播协议，Hadoop 偏向于离线的海量数据处理，利用 Zookeeper 来保证数据副本的一致性，是最为合适的

Hash 路由算法，ElasticSearch 集群接收到为文档创建索引的请求时，需要选择在哪一个 Shard 上对文档进行索引，这里的 Shard 是指某一个完整且独立的 Lucene 索引实例。ElasticSearch 采用的是 djb2 哈希算法，俗称 times33，可以简单表示为 hash(key) % n，也就是对要索引的文档中，默认或指定的 Key 进行哈希操作，然后在对 ElasticSearch 集群中 Shard 的数量 n 进行取模，进而完成请求路由的操作。

一致性 Hash 算法，HaProxy 使用一致性 Hash 算法适用于对服务器连接进行负载均衡的算法，最新的进展是 Google 近几年发表的一篇《有界负载的一致性 Hash 算法》的论文 Consistent Hashing with Bounded Loads ：https://arxiv.org/abs/1608.01350

Gossip 算法，主要被 Cassandra 应用于实现它的分布式一致性特性，因为 Cassandra 框架跟看重去中心化和容错的特性，在不违背 CAP 定理的前提下，只能接受了最终一致性。

ZooKeeper 中实现的 ZAB 算法和传统 Paxos 算法两者之间最核心的区别就在于引入了 ZXID 的概念，解决了事务操作如何保证全局有序的难题，这也奠定了它在大数据分布式领域的霸主地位。