7 分布式数据库
关系型数据库设计之初没有预见到 IT 行业发展如此之快，总是假设系统运行在单机 这一封闭系统上。
7.1 数据库中间层
最常见做法：应用层按照规则将数据拆分为多个 分片 ，分布到多个数据库节点，并 引入一个中间层 来对应用屏蔽后端的数据库拆分细节。
7.1.1 架构
以 MySQL Sharding 为例：
- 中间层 dbproxy 集群：解析客户端 SQL 请求并转发到后端的数据库。具体上：解析 MySQL 协议，执行 SQL 路由，SQL 过滤，读写分离，结果归并，排序以及分组等。由多个无状态的 dbproxy 进程组成，不存在单点的情况。另外，可以在客户端与中间层之间引入 LVS 对客户端请求进行负载均衡。需要注意的是，客户端请求需要额外增加一层通信开销，因此，常见的做法是直接在客户端配置中间层服务器列表，由客户端处理请求负载均衡以及中间层服务器故障等情况。
- 数据库组：每个 dbgroup 由 N 台数据库机器组成，其中一台为 Master，另外的为 Slave。Master 负责所有的写事务及强一致读事务，并将操作以 binlog 的形式复制到备机，备机可以支持有一定延迟的读事务。
- 元数据服务器：负责维护 dbgroup 拆分规则并用于 dbgroup 选主。dbproxy 通过元数据服务器获取拆分规则从而确定 SQL 语句的执行计划。另外，如果 dbgroup Master 出现故障，需要通过元数据服务器选主。元数据服务器本身也需要多个副本实现 HA，一般常见的方式是采用 Zookeeper 实现。
- 常驻进程 agents：用于实现监控，单点切换，安装，卸载程序等。
MySQL 客户端库：应用程序通过 MySQL 原生的客户端与系统交互，支持 JDBC。
假设数据库按照用户哈希分区，同一个用户的数据分布在一个数据库组上。如果 SQL 请求只涉及同一个用户（这对于大多数应用都是成立的），那么，中间层将请求转发给相应的数据库组，等待返回结果并将结果返回给客户端；如果 SQL 请求涉及多个用户，那么中间层需要转发给多个数据库组，等待返回结果并将结果执行合并、分组、排序等操作后返回客户端。由于中间层的协议与 MySQL 兼容，客户端完全感受不到与访问单台 MySQL 机器之间的差别。
7.1.2 扩容
MySQL Sharding 集群一般按照用户 id 进行 哈希分区，存在两个问题：
- 集群容量不足：双倍扩容的方案，从 2 -> 4 -> 8 …
- 单个用户的数据量太大：在应用层定期统计大用户，并且将这些用户的数据按照数据量拆分到多个 dbgroup。当然，定期维护这些信息对应用层是一个很大的代价。
常见扩容方式：（假设 2 个 dbgroup，第一个 dbgroup Master 为 A0，备机为 A1，第二个 dbgroup Master 为 B0， 备机为 B1. 按照用户 id 哈希模 2，结果为 0 的用户分布在第一个 dbgroup，结果为 1 的用户分布在第二个 dbgroup）
- 等待 A0 和 B0 的数据同步到其备服务器，即 A1 和 B1
- 停止写服务，等待主备完全同步后解除 A0 与 A1、B0 与 B1 的主备关系
- 修改中间层的映射规则，将哈希值模 4 等于 2 的用户数据映射到 A1， 哈希值模 4 等于 3 的用户数据映射到 B1
- 开启写服务，用户 id 哈希值模 4 等于 0/1/2/3 的数据将分别写入到 A0/A1/B0/B1。这就相当于有一半的数据分别从 A0、B0 迁移到 A1、B1.
- 分别给 A0、A1、B0、B1 增加一台备机
最终，集群由 2 个 dbgroup 变为 4 个 dbgroup。可以看到，扩容过程需要停一小会儿服务，另外，扩容执行过程中如果再次发生服务器故障，将使扩容变得非常复杂，很难做到完全自动化。
7.1.3 讨论
引入数据库中间层将后端分库分表对应用透明化在大型互联网公司内部很常见。这种做法实现简单，对应用友好，但是也有一些问题：
- 数据库复制：可能只支持异步复制，主库压力大可能产生很大的延迟，因此，主备切换可能会丢失一部分更新事务，这时需要人工介入
- 扩容问题：扩容涉及数据重新划分，整个过程复杂易出错
- 动态数据迁移问题：难自动化。
7.2 Microsoft SQL Azure
7.3 Google Spanner
Google 的 全球级分布式数据库（Globally-Distributed Database）。扩展性达到了全球级，可以扩展到数百个数据中心，数百万台服务器，上亿行记录。还能通过 同步复制和多版本控制 来满足外部一致性，支持跨中心事务。
7.3.1 数据模型
对于典型相册应用，存储用户和相册，建表语句如下：
CREATE TABLE Users { user_id int64 not null, email string } PRIMARY KEY(user_id), DIRECTORY; CREATE TABLE Albums { user_id int64, album_id int32, name string } PRIMARY KEY(user_id, album_id), INTERLEAVE IN PARENT Users; SQL |
Spanner 表是层次化的，最底层的表是目录表（Directory table），其他表创建时，可以用 INTERLEAVE IN PARENT 来表示层次关系。
实际存储时，Spanner 会将同一个目录的数据存放到一起，只要目录不太大，同一个目录的每个副本都会分配到同一台机器。因此，针对同一个目录的读写事务大部分情况下都不会涉及跨机器操作。
7.3.2 架构
Spanner 构建在 Google 下一代分布式文件系统 Colossus 之上。Colossus 是 GFS 的延续，相比 GFS，Colossus 主要改进点在于 实时性，且支持海量小文件
Spanner 概念：
- Universe：一个 Spanner 部署实例称为一个 Universe。 目前全世界有 3 个，一个开发，一个测试，一个线上。Universe 支持多数据中心部署，且多个业务可以共享同一个 Universe
- Zones： 每个 zone 属于一个数据中心，而一个数据中心可能有多个 zones。一般来说， Zone 内部的网络通信代价较低，而 Zone 之间通信代价很高。（zone 概念类似于 region）
Spanner 包含如下组件：
- Universe Master： 监控这个 Universe 里 Zone 级别状态信息。
- Placement Driver：提供跨 Zone 数据迁移功能。
- Location Proxy：提供获取数据的位置信息服务。客户端需要通过它才能知道数据由哪台 Spanserver 服务。
- Spanserver：提供存储服务，功能上相当于 Bigtable 系统中的 Tablet Server
每个 Spanserver 会服务多个子表，而每个子表又包含多个目录。客户端往 Spanner 发送读写请求时，首先查找目录所在的 Spanserver，接着从 Spanserver 读写数据。
7.3.3 复制与一致性
每个数据中心运行一套 Colossus，每个机器有 100 - 1000 个子表，每个子表会在多个数据中心部署多个副本。为了同步系统的操作日志，每个子表上会运行一个 Paxos 状态机。Paxos 协议会选出一个副本作为主副本，主副本默认寿命为 10s。 正常情况下，这个主副本会在快要到期的时候将自己再次选择为主副本；如果主副本宕机，其他副本会在 10s 后通过 Paxos 协议选举为新的主副本。
通过 Paxos 协议，实现了跨数据中心的多个副本之间的一致性。另外，每个主副本所在的 Spanserver 还会实现一个锁表用于并发控制，读写事务操作某个子表上的目录时需要通过锁表避免多个事务之间互相干扰。
除了锁表，每个主副本还有一个事务管理器。如果事务在一个 Paxos 组里面，可以绕过事务管理器。但是一旦事务跨多个 Paxos 组，需要事务管理器来协调。
锁表实现单个 Paxos 组内的单机事务，事务管理器实现跨多个 Paxos 组的分布式事务。为了实现分布式事务，需要实现两阶段提交协议。有一个 Paxos 组的主副本会成为两阶段提交协议中的协调者，其他 Paxos 组的主副本为参与者。
7.3.4 TrueTime
要给每个事务分配全局唯一的事务 id。Spanner 通过 全球时钟同步机制 Truetime 实现。
Truetime 返回时间戳 t 和误差 e。真实系统 e 平均下来只有 4 ms。
Truetime API 实现的基础是 GPS 和原子钟。
每个数据中心需要部署一些主时钟服务器（Master），其他机器上部署一个从时钟进程（Slave）来从主时钟服务器同步时钟信息。有的主时钟服务器用 GPS，用的用原子钟。
7.3.5 并发控制
支持以下事务：
- 读写事务
- 只读事务
- 快照读，客户端提供时间戳
- 快照读，客户端提供时间范围
考虑 TrueTime，为了保证事务顺序，事务 T1 会在 t1 + e 之后才提交，事务 T2 会在 t2 + e 之后才提交。意味着每个写事务的延迟至少为 2e。
