本周的主要内容

1、关系型数据库分片

1-1、为什么要做分片（问题）？

一般做数据库分片有两个原因：

• 单个数据库服务器数据量过大，单表的数据量太大；

• 单个数据库读写访问的 IO 已经达到上限；

单个数据库服务器达到物理极限，无法再通过升级硬件方式解决上面两个问题，这时候需要做数据分片；

1-2、数据分片的挑战

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

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

• 无法使用数据库事务；

• 随着数据量再增加，数据库服务器如何扩容；

1-3、数据分片的实现方法

1-3-1、硬编码实现

优点：实现较为简单

缺点：分片实现逻辑与代码耦合

1-3-2、使用映射表

优点：较为灵活，可以按多个方式进行分片，ID 和库的 Mapping 算法可以随意更改；

缺点：1、查询次数增加（先查映射表再查数据表）；2、实现复杂；3、映射表单点问题；

1-3-3、数据库中间件

常用的数据库中间件：MyCAT 和 Apache ShardingSphere

优点：对于应用程序比较透明；路由选择比侵入业务逻辑；不需要额外代码维护；

1、MyCAT 的架构

2、Apache ShardingSphere

Apache ShardingSphere 是一套开源的分布式数据库中间件解决方案组成的生态圈，它由 JDBC、Proxy 和 Sidecar（规划中）这 3 款相互独立，却又能够混合部署配合使用的产品组成。 它们均提供标准化的数据分片、分布式事务和数据库治理功能，可适用于如 Java 同构、异构语言、云原生等各种多样化的应用场景。

Apache ShardingSphere 定位为关系型数据库中间件，旨在充分合理地在分布式的场景下利用关系型数据库的计算和存储能力，而并非实现一个全新的关系型数据库。

2-1、Sharding JDBC 架构

定位为轻量级 Java 框架，在 Java 的 JDBC 层提供的额外服务。 它使用客户端直连数据库，以 jar 包形式提供服务，无需额外部署和依赖，可理解为增强版的 JDBC 驱动，完全兼容 JDBC 和各种 ORM 框架。

• 适用于任何基于 JDBC 的 ORM 框架，如：JPA, Hibernate, Mybatis, Spring JDBC Template 或直接使用 JDBC。

• 支持任何第三方的数据库连接池，如：DBCP, C3P0, BoneCP, Druid, HikariCP 等。

• 支持任意实现 JDBC 规范的数据库。目前支持 MySQL，Oracle，SQLServer，PostgreSQL 以及任何遵循 SQL92 标准的数据库。

2-2、Sharding Proxy 架构

定位为透明化的数据库代理端，提供封装了数据库二进制协议的服务端版本，用于完成对异构语言的支持。 目前先提供 MySQL/PostgreSQL 版本，它可以使用任何兼容 MySQL/PostgreSQL 协议的访问客户端(如：MySQL Command Client, MySQL Workbench, Navicat 等)操作数据，对 DBA 更加友好。

• 向应用程序完全透明，可直接当做 MySQL/PostgreSQL 使用。

• 适用于任何兼容 MySQL/PostgreSQL 协议的的客户端。

2-3、Sharding-JDBC 和 Sharding-Proxy 比较

1-3-4、数据库集群伸缩解决方案

基本实现算法：余数 Hash

具体操作：

1、一个数据库服务器上有多个实例；

2、当单个实例需要扩容时，只需要将对应 Schema 直接迁移到新的 SQL 上；

3、数据库迁移完成，再修改代码中的数据路由规则，数据库连接指向新的数据库；

1-4、数据库部署架构演化过程

1-4-1、单一服务与单一数据库

系统刚开始，访问和请求压力较小，业务逻辑也比较简单，此时只需要单个数据库就好；

1-4-2、读写分离

当数据库读写 IO 较大时，可以使用读写分离，主机负责写请求，丛机负责读请求；

1-4-3、业务服务数据库分离

当业务越来越复杂，在一个系统开发部署难度增大，代码变多时，这时就需要对业务进行拆分，数据库压力增大，也对业务数据拆分；

1-4-4、数据库分片

当一个业务的数据库读写压力达到瓶颈，此时就要对单个业务的数据库进行分片处理；

1-4-5、综合部署

对于访问量较大的业务，数据库需要进行数据库分片；

对于访问数据量较小，或者数据量较小的业务，只需要进行主从复制（读写分离）；

2、CAP 原理以及 NoSQL 如何实现 CAP

因为内容比较多，参考我的另一篇文章：https://xie.infoq.cn/article/78aef90c0e9b320b7bfa7940b

3、分布式一致性算法 Paxos

Paxos 是一个提高分布式系统容错性的一致性算法，解决【数据一致性】问题。

3-1、Paxos 中的角色

• Proposer：负责「Prepare」和「Accept」提案；

• Acceptor：负责【批准 Promise】和【通过 Accepted】提案；

• Learner：被动接收【通过的】提案；

3-2、Paxos 算法过程

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

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

3. 第三阶段：Learn 阶段。Proposer 在收到多数 Acceptors 的【Accepted】后，标志着本次提案通过，决议形成，将形成的决议发送给所有 Learners。

3-3、Paxos 算法详细描述

3-3-1、阶段一

3-3-1-1、准备-Prepare

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

3-3-1-2、承诺-Promise

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

两个承诺:

1. 不再应答(answer)【Proposal ID 小于等于】【已经承诺的】的 Prepare 请求的 ID。

2. 不再应答(answer)【Proposal ID 小于（< ）当前请求的 Propose 请求。

一个应答:

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

3-3-2、阶段二

3-3-2-1、Propose

Proposer 收到多数 Acceptors 的 Promise 应答后，从应答中选择 Proposal ID 最大的提案的 Value，作为本次要发起的提案。如果所有应答的提案 Value 均为空值，则可以自己随意决定提案 Value。然后携带当前 Proposal ID，向所有 Acceptors 发送 Propose 请求。

3-3-2-2、Accept

Acceptor 收到 Propose 请求后，在不违背自己之前作出的承诺下，接受并持久化当前 Proposal ID 和提案 Value。

3-3-2-3、Learn

多数 Acceptors 通过提案后，决议形成，将形成的决议发送给所有 Learners。

4、Zookeeper

Zookeeper 是一个开源的分布式协调服务，由雅虎创建，是 Google Chubby 的开源实现。Zookeeper 的设计目标是将那些复杂且容易出错的分布式一致性服务封装起来，构成一个高效可靠的原语集，并以简单易用的接口提供给用户使用。

4-1、Zookeeper 如何保证分布式一致性？

• 顺序一致性：从同一个客户端发起的事务请求，最终将会严格地按照其发起顺序被应用到 Zookeeper；

• 原子性：所有事务请求的处理结果在整个集群所有机器上的应用一致，要么整个集群所有机器都成功应用某一个事务，要么都没应用，一定不会出现部分机器应用，而另外一部分没有应用的情况；

• 单一视图：无论客户端连接的是哪个 Zookeeper 服务器，其看到的服务端数据模型都是一致的；

• 可靠性：一旦服务成功地应用一个事务，并完成对客户端的响应，那么该事务所引起的服务端状态变更将会被一致保留下来，除非有另一个事务又对其进行变更；

• 实时性：Zookeeper 保证在一定的时间段内，客户端最终一定能够从服务端上读取到最新的数据状态。

4-2、Zookeeper 的 ZAB 协议

Zookeeper 并没有采用 Paxos 算法，而是使用一种称为 Zookeeper Atomic Broadcast（ZAB，Zookeeper 原子消息广播协议）作为其数据一致性的核心算法。

ZAB 协议是为分布式协调服务 Zookeeper 专门设计的支持【崩溃恢复】的原子广播协议。

在 Zookeeper 中，主要依赖 ZAB 协议来实现分布式数据一致性，基于该协议，Zookeeper 实现一种【主备模式】的系统架构来保持集群中各副本之间数据的一致性。

4-2-1、ZAB 协议描述

ZAB 协议的核心是定义对那些会改变 Zookeeper 服务器数据状态的事务请求的处理方式，即：

所有的事务请求必须由一个【全局唯一】的服务器协调处理，这个服务器被称为【Leader】服务器，而其它服务器称为【Follower】服务器。

Leader 服务器负责将一个客户端事务请求转换成一个事务 Proposal（提议），并将该 Proposal 分发给集群中所有的 Follower 服务器。

之后 Leader 服务器需要等待所有 Follower 服务器反馈，当【超过半数】的 Follower 服务器进行正确反馈后，Leader 就会再次向所有 Follower 服务器 分发 Commit 消息，要求将 Proposal 进行提交。

集群有两种方式收到客户端的请求：

1、Leader 服务器直接接收到客户端的事务请求，生成提案进行一轮广播协议；

2、集群中的 Follower 服务器收到客户端请求，会将这个请求先发给 Leader 服务器处理；

4-2-2、ZAB 协议模式

4-2-2-1、消息广播

1. 发出提案：一个客户端请求发送到 Leader 服务器，Leader 服务器生产对应的 Proposal，并将其发送给集群中的 Follower 服务器；

2. 提交提案：Leader 收到集群中【超过一半】的 Follower 服务器反馈的 ACK 请求后，发送 Commit 请求将第一步发出的 Proposal 事务提交；

4-3、Zookeeper 集群

4-4、Zookeeper 的 Leader 选举过程

4-4-1、节点的状态

所有节点都有两个属性，

SID：节点 ID，zoo.cfg 中配置的 myid，

ZXID：节点当前的【最大事务 ID】

选举规则就是选目前所有节点中【拥有最大 ZXID】的节点作为 Leader，

如果拥有的 ZXID 相同，就选取 SID 最大的节点作为 Leader。

4-4-2、全新的集群 leader 选举

启动时，当集群没有 leader 时，每个机器会将票投给 SID 最大的机器（越晚加入的机器 SID 越大） 有 leader 时会将票投给 leader。 假设有五个节点，一开始 A 启动时之会将票投给自己，B 启动时之后将票投给 B，A 也投给 B，C 启动时，A，B，C 都投个 C C 得票超过半数，C 成为 leader，之后加入的 D，E 也只会投给 C。

4-4-3、非全新的集群 leader 选举

基本原则是

1.选 epoch 值大的，epoch 值小的投票结果会被忽略掉。

2.epoch 值相同时，把票投给 ZXID 大的节点。

3.ZXID 相同时，把票投给 SID（server id）大的节点。 得票超过半数的节点会成为 leader。 通常是数据越新的节点越有可能成为主节点。

投票阶段

1.初始化选票

将逻辑时钟+1，初始化选票， 每个节点都会投给自己，然后选票发给其他节点

2.处理选票信息

从其他节点 B 收到投票信息后，进行处理

2.1、如果本节点的逻辑时钟小于接受这条投票的逻辑时钟， 说明本节点之前错过了上一轮的投票，将当前存储的选票信息清空，

2.2、如果本节点的逻辑时钟大于接受的这条投票的逻辑时钟，那么忽略掉这条投票信息。

2.3、本节点的逻辑时钟等于接受的这条投票的逻辑时钟，那么进行处理，与本节点当前投票的结果进行比较：【先比较 ZXID】（数据 ID，越大代表数据越新），ZXID 越大的应该当 leader，ZXID 相同比较 SID，SID 越大的当 leader。

2.4、如果比较的结果跟当前节点的投票结果不一致，那么需要更改选票，将更改后的选票结果发送给其他节点。

2.5、将其他节点 B 的投票结果记录下来

3.统计选票

对当前收到的所有投票信息进行统计，看是否有节点获得半数以上的选票，有的话就将它设置为 leader，然后终止投票，否则继续投票，继续步骤 2。

4.发现阶段

所有 follower 会向 leader 发送 epoch 和 ZXID(最大事务 ID),然后 leader 选取最大的事务 ID 作为当前最新的 ID

5.同步阶段

通知其他 follower 节点进行同步，将数据更新到最大的事务 ID。

原子广播阶段

这时正式向客户端提供服务，leader 接受客户端的写请求后，会将请求通过队列发送个每个节点，每个节点收到消息后将记录写到磁盘， 并且返回 ACK 给 leader，当半数以上的从节点返回 ACK 后，leader 才 commit 这条更新。

4-5、Zookeeper 的应用

Zookeeper 的应用场景包括：

• 配置中心

• 负载均衡

• 命名服务

• 分布式协调/通知

• 集群管理

• Master 选举

• 分布式锁

• 分布式队列

5、本周总结

本周主要的收获：

1、了解数据库分片的目的，实现原理和解决方案；

2、掌握了 CAP 原理，并且了解 Cassandra（AP）和 HBase（CP）在 CAP 中进行取舍的；

3、了解分布式海量存储框架 Doris 的设计背景、目标和实现；

4、掌握分布式一致性算法 Paxos 的算法原理；

5、掌握 Zookeeper 这个开源的分布式协调服务的原理和在实践中的应用场景；