TiDB是支持MySQL语法的开源分布式混合事务/分析处理（HTAP）数据库。TiDB 可以提供水平可扩展性、强一致性和高可用性。它主要由 PingCAP 公司开发和支持，并在 Apache 2.0 下授权。TiDB 从 Google 的 Spanner 和 F1 论文中汲取了最初的设计灵感。

HTAP 是 Hybrid Transactional / Analytical Processing 的缩写。这个词汇在 2014 年由 Gartner 提出。传统意义上，数据库往往专为交易或者分析场景设计，因而数据平台往往需要被切分为 TP 和 AP 两个部分，而数据需要从交易库复制到分析型数据库以便快速响应分析查询。而新型的 HTAP 数据库则可以同时承担交易和分析两种智能，这大大简化了数据平台的建设，也能让用户使用更新鲜的数据进行分析。作为一款优秀的 HTAP 数据数据库，TiDB 除了优异的交易处理能力，也具备了良好的分析能力。

TiDB在整体架构基本是参考 Google Spanner 和 F1 的设计，上分两层为 TiDB 和 TiKV。 TiDB 对应的是 Google F1，是一层无状态的 SQL Layer，兼容绝大多数 MySQL 语法，对外暴露 MySQL 网络协议，负责解析用户的 SQL 语句，生成分布式的 Query Plan，翻译成底层 Key Value 操作发送给 TiKV，TiKV 是真正的存储数据的地方，对应的是 Google Spanner，是一个分布式 Key Value 数据库，支持弹性水平扩展，自动的灾难恢复和故障转移（高可用），以及 ACID 跨行事务。值得一提的是 TiKV 并不像 HBase 或者 BigTable 那样依赖底层的分布式文件系统，在性能和灵活性上能更好，这个对于在线业务来说是非常重要。

• TiDB Server：SQL 层，对外暴露 MySQL 协议的连接 endpoint，负责接受客户端的连接，执行 SQL 解析和优化，最终生成分布式执行计划。TiDB 层本身是无状态的，实践中可以启动多个 TiDB 实例，通过负载均衡组件（如 LVS、HAProxy 或 F5）对外提供统一的接入地址，客户端的连接可以均匀地分摊在多个 TiDB 实例上以达到负载均衡的效果。TiDB Server 本身并不存储数据，只是解析 SQL，将实际的数据读取请求转发给底层的存储节点 TiKV（或 TiFlash）。
• PD (Placement Driver) Server：整个 TiDB 集群的元信息管理模块，负责存储每个 TiKV 节点实时的数据分布情况和集群的整体拓扑结构，提供 TiDB Dashboard 管控界面，并为分布式事务分配事务 ID。PD 不仅存储元信息，同时还会根据 TiKV 节点实时上报的数据分布状态，下发数据调度命令给具体的 TiKV 节点，可以说是整个集群的“大脑”。此外，PD 本身也是由至少 3 个节点构成，拥有高可用的能力。建议部署奇数个 PD 节点。
• 存储节点
  • TiKV Server：负责存储数据，从外部看 TiKV 是一个分布式的提供事务的 Key-Value 存储引擎。存储数据的基本单位是 Region，每个 Region 负责存储一个 Key Range（从 StartKey 到 EndKey 的左闭右开区间）的数据，每个 TiKV 节点会负责多个 Region。TiKV 的 API 在 KV 键值对层面提供对分布式事务的原生支持，默认提供了 SI (Snapshot Isolation) 的隔离级别，这也是 TiDB 在 SQL 层面支持分布式事务的核心。TiDB 的 SQL 层做完 SQL 解析后，会将 SQL 的执行计划转换为对 TiKV API 的实际调用。所以，数据都存储在 TiKV 中。另外，TiKV 中的数据都会自动维护多副本（默认为三副本），天然支持高可用和自动故障转移。
  • TiFlash：TiFlash 是一类特殊的存储节点。和普通 TiKV 节点不一样的是，在 TiFlash 内部，数据是以列式的形式进行存储，主要的功能是为分析型的场景加速。

TiKV 基于 RocksDB，采用了 Raft 协议来实现分布式的一致性。TiKV 的系统架构如下图所示：

优点：

• 纯分布式架构，拥有良好的扩展性，支持弹性的扩缩容
• 支持 SQL，对外暴露 MySQL 的网络协议，并兼容大多数 MySQL 的语法，在大多数场景下可以直接替换 MySQL
• 默认支持高可用，在少数副本失效的情况下，数据库本身能够自动进行数据修复和故障转移，对业务透明
• 支持 ACID 事务，对于一些有强一致需求的场景友好，例如：银行转账
• 具有丰富的工具链生态，覆盖数据迁移、同步、备份等多种场景
• 智能的行列混合模式，TiDB 可经由优化器自主选择行列。这套选择的逻辑与选择索引类似：优化器根据统计信息估算读取数据的规模，并对比选择列存与行存访问开销，做出最优选择

缺点：

• 虽然兼容MySQL，但是不支持存储过程，触发器，自定义函数，窗口功能有限
• 不适用数据量小的场景，专门为大数据量设计

背景

分布式数据库 Schema 变更时，由于 Server 获取 Schema 元数据的时机不是同步的，不可避免地会使同一时刻一些 Server 上的 Schema 是旧的，如下图所示。而若变更时禁止 DML 让所有的 Server 都暂停服务，对于大规模分布式数据库，基本没法做到，因为 Schema 变更操作需要花费大量时间，而数据库需要保证 24 小时在线。

例如，增加一个索引 E，Schema 从 S1 变为 S2，有两个节点 A 和 B 分别使用 S1 和 S2：

1. B 添加一行数据，由于它按照 Index E 已经创建完成的 Schema，它会插入两个 KV，RowKV 和 IndexKV
2. A 删除该行数据，由于它按照 Index E 未创建的 Schema，它只会删除 RowKV，IndexKV 就成了孤儿，破坏了数据的完整性

论文思路

论文提出了一种 Schema 演进的协议，协议有两个特点：

1. Online——Schema 变更期间，所有 Server 仍然可以读写全部数据
2. Asynchronous——允许不同 Server 在不同时间点开始使用新版本 Schema

论文把从 Schema 0 到 Schema 1 的突变，替换为一系列相互兼容的小状态变化：

• 任意两个相邻的小状态（版本）都是兼容的
• 只有一个 Server 负责 DDL 的执行，其他 Server 只是定期刷新状态（拉取 Schema）
• 每次 Schema 版本变化间隔不小于一个 Lease 时间，任意时刻，集群中 Server 至多存在两个版本的 Schema。也就是说所有 Server 使用的 Schema 状态都相邻，都是兼容的，经过一系列小状态的转换，就可以实现 Schema 0 到 Schema 1 的变更

schema elements

• 包括 tables，columns，indexes，constraints，和 optimistic locks
• 每个 schema element 都有一个与之关联的 state

states

1. Absent 状态

• 完全不感知该 schema element，任何 DML 都不会涉及该 schema element

2. Delete Only 状态

• Select 语句不能使用该 schema element
• Delete 语句在删除时，如果​该 schema element​ 对应的条目存在，要一并删除
• Insert 语句在插入​时，不允许插入该 schema element​ 对应的条目
• Update 语句在修改时，只允许删除既存的该 schema element​ 对应的条目，但不能插入新的该 schema element​ 对应的条目

3. Write Only 状态

• Select 语句不能使用该 schema element
• 其他 DML 语句可以正常使用该 schema element、修改该 schema element​ 对应的条目

4. Reorg

• 不是一种 schema 状态，而是发生在 write-only 状态之后的一系列操作，保证在索引变为 public 之前所有旧数据的 schema element 都被正确地生成
• reorg 要做的就是取到当前时刻的 snapshot，为每条数据补写对应的 schema element 条目即可。当然 reorg 开始之后数据可能发生变更，这种情况下底层 Spanner 提供的一致性能保证 reorg 的写入操作要么失败（说明新数据已提前写入），要么被新数据覆盖

5. Public 状态

• 该 schema element 正常工作，所有 DML 都正常使用该 schema element

状态兼容说明

破坏一致性（兼容性）的场景有两种：

• orphan data anomaly：数据库中包含了按照当前 schema 下不应存在的 KV
• integrity anomaly：数据库中缺少当前 schema 下应该存在的 KV

1. 为什么 “Absent” 和 “Delete Only” 能够兼容

• Absent 状态的 Server 不知道该 schema element 因此不需要该 schema element，不会产生该 schema element 的条目
• Delete Only 状态的 Server 知道该 schema element（非 public）但也不需要该 schema element，不会产生该 schema element 的条目

2. 为什么 “Delete Only” 和 “Write Only” 能够兼容

• Delete Only 状态和 Write Only 状态的 Server 都知道该 schema element（非 public）但都不需要该 schema element

3. 为什么 “Write Only” 和 “Public” 能够兼容

• Write Only 状态的 Server 在该 schema element 的所有已经完整的情况下（通过 Reorg），可以与 Public 兼容

4. 为什么 “Absent” 和 “Write Only” 不兼容

• 因为 Write Only 会产生新的条目，破坏了 Absent 的条件

5. 为什么 “Delete Only” 和 “Public” 不兼容

• 因为 Public 有要求所有历史数据有完整的 schema element，Delete Only 状态下并不具备

6. 通俗点举例

• 假设在增加一个索引 E 的过程中，有如下执行顺序：1）Server A 插入一行 x；2) Server B 删除了行 x；3）Server A 查询 y；4) Server B 查询 y：
  (1) A 为 Delete Only 状态，B 为 Absent 状态：A 插入了一个 KV（RowKV），B 将 RowKV 删除，A 和 B 在查询时都不会用到 Index E，是兼容的
  (2) A 为 Write Only 状态，B 为 Delete Only 状态：A 插入了两个 KV（RowKV 和 IndexKV），B 将 RowKV 和 IndexKV 删除，A 和 B 在查询时都不会用到 Index E，是兼容的
  (3) A 为 Public 状态，B 为 Write Only 状态：A 插入了两个 KV（RowKV 和 IndexKV），B 将 RowKV 和 IndexKV 删除；查询时，A 会用到 Index E，B 虽然不会用到 Index E，但数据库中存在 A 的 schema 下应该存在的 IndexKV，所以是兼容的
  (4) A 为 Write Only 状态，B 为 Absent 状态：A 插入了两个 KV（RowKV 和 IndexKV），B 感知不到 IndexKV，因此只会删除 RowKV，这一行的 IndexKV 就成了孤儿数据，所以不兼容
  (5) A 为 Public 状态，B 为 Delete Only 状态：A 会用到 Index E，B 不会用到 Index E，并且数据库中也不存在 A 的 schema 下的 IndexKV，所以不兼容

参考

1. Ian Rae, Eric Rollins, Jeff Shute, Sukhdeep Sodhi and Radek Vingralek, Online, Asynchronous Schema Change in F1, VLDB 2013.

背景

Percolator 事务模型是 Google 内部用于 Web 索引更新的业务提出的分布式事务协议，构建在 BigTable 之上，总体来说就是一个经过优化的二阶段提交的实现。使用基于 Percolator 的增量处理系统代替原有的批处理索引系统后，Google 在处理同样数据量的文档时，将文档的平均搜索延时降低了50%。

2PC

传统的 2PC 简单描述一下就是两步：

1. 发起事务：事务管理器会发出 Prepare 请求，要求参与者记录日志，进行资源的检查和锁定
2. 确认/取消事务：当请求得到所有参与者的成功确认后，事务管理器会发出 Commit 请求，执行真正的操作；如果第一步中只要有一个执行者返回失败，则取消事务

这样会有两个问题，一个就是单点故障：如果事务管理器发生故障，数据库会一直阻塞下去。尤其是在第二阶段发生故障的话，所有参与者还都处于锁定事务资源的状态中，从而无法继续完成事务操作；另一个就是存在数据不一致的情况：在第二阶段，当事务管理器向参与者发送 Commit 请求之后，发生了局部网络异常，导致只有部分参与者接收到请求，但是其他参与者未接到请求所以无法提交事务，整个系统就会出现数据不一致性的现象。

Percolator 事务流程

Percolator 事务是一个经过优化的 2PC 的实现，进行了一个二级锁的优化，也分为两个阶段：预写（Pre-write）和提交（Commit）。另外，所有启用了 Percolator 事务的表中，每一个 Column Family 都会预先增加两个列，分别是：

• lock：存储事务过程中的锁信息
• write：存储当前行可见（最近一次提交）的版本号

另外，为了简化场景，假设存储用户数据的列只有一个，名为 data。

Pre-write

1. 客户端从 TSO 获取时间戳，记为 start_ts，并向 Percolator Worker 发起 Pre-write 请求。

2. 在该事务包含的所有写操作中选取一个作为主（primary）操作，其余的作为次（secondary）操作。主操作将作为整个事务的互斥点，标记事务的状态。

3. 先预写主操作，成功后再预写次操作。在预写过程中，对每一个写操作都要执行检查：

   • 检查写入的行对应的 lock 列是否有锁，如果有，说明其他事务正在写，直接取消整个事务
   • 检查写入的行对应的 write 列版本号是否晚于 start_ts，如果是，说明有版本冲突，直接取消整个事务

4. 检查通过后，以 start_ts 作为版本号将数据写入 data 列，对操作行加锁，即更新 lock 列的锁信息：主操作行的 lock 直接标为primary，次操作行的 lock 则标为主操作行的键和列名。不更新write列，亦即此时写入的数据仍然不可见。

Commit

1. 客户端从 TSO 获取时间戳，记为 commit_ts，并向 Percolator Worker 发起 Commit 请求。

2. 检查主操作行对应的 lock 列所在的 primary 标记是否存在，如果不存在则失败，取消事务；如果存在则继续。

3. 以 commit_ts 作为版本号，将 start_ts 更新到 write 列中。也就是说在本阶段完成后，预写阶段写入的数据将会可见。

4. 对该行解锁，即删除 lock 列的 primary 信息。

5. 若步骤 1~4 均成功，说明主操作行成功，代表整个事务实际上已经提交。接下来更新每个 secondary 即可，即重复步骤3、4的更新 write 列和清除 lock 列操作。secondary 的 commit 是可以异步进行的，只是在异步提交进行的过程中，如果此时有读请求，可能会需要做一下锁的清理工作。

案例

银行转账，Bob 向 Joe 转账 7 元。该事务于 start_ts=7 开始，commit_ts=8 结束，Key 为 Bob 和 Joe 的行可能在不同的分片上。具体过程如下：

1. 首先查询 write 列获取最新时间戳数据，获取到 data@5，然后从 data 列里面获取时间戳为 5 的数据，初始状态下，Bob 的帐户下有 10，Joe 的帐户下有 2。

2. 事务开始，获取 start_ts=7 作为当前事务的开始时间戳，将 Bob 行选为本事务的 primary，通过写入 lock 列锁定 Bob 的帐户，同时将数据 7:$3 写入到 data 列。

3. 同样，使用 start_ts=7，将 Joe 改变后的余额写入到 data 列，当前操作作为 secondary，因此在 lock 列写入 7:Primary@Bob.bal（当失败时，能够快速定位到 primary 操作，并根据其状态异步清理）。

4. 事务带着当前时间戳 commit_ts=8 进入 Commit 阶段：删除 primary 所在的 lock，并在 write 列中写入以提交时间戳作为版本号指向数据存储的一个指针 data@7。至此，读请求过来时将看到 Bob 的余额为 3。

5. 同样，使用 commit_ts=8，依次在 secondary 操作项中写入 write 列并清理锁。

6. 至此，整个当前 Percolator 事务已完成。

对比

相比 2PC 存在的问题，来看看 Percolator 事务模型有哪些改进。

1. 单点故障
   Percolator 通过日志和异步线程的方式弱化了这个问题。一是，Percolator 引入的异步线程可以在事务管理器宕机后，回滚各个分片上的事务，提供了善后手段，不会让分片上被占用的资源无法释放。二是，事务管理器可以用记录日志的方式使自身无状态化，日志通过共识算法同时保存在系统的多个节点上。这样，事务管理器宕机后，可以在其他节点启动新的事务管理器，基于日志恢复事务操作。

2. 数据不一致
   2PC 的一致性问题主要缘自第二阶段，不能确保事务管理器与多个参与者的通讯始终正常。但在 Percolator 的第二阶段，事务管理器只需要与 primary 操作所在的一个节点通讯，这个 Commit 操作本身就是原子的。所以，事务的状态自然也是原子的，一致性问题被完美解决了。

Snapshot Isolation

传统关系型数据库中定义的隔离级别有4种（RU、RC、RR、S），而 Percolator 事务模型提供的隔离级别是快照隔离（Snapshot Isolation, SI），它也是与 MVCC 相辅相成的。SI的优点是：

• 对于读操作，保证能够从时间戳/版本号指定的稳定快照获取，不会发生幻读
• 对于写操作，保证在多个事务并发写同一条记录时，最多只有一个会提交成功

如图，基于快照隔离的事务，开始于 start timestamp（图内为小空格），结束于 commit timestamp（图内为小黑球）。本例包含以下信息：

1. txn_2 不能看到 txn_1 的提交信息，因为 txn_2 的开始时间戳 start timestamp 小于 txn_1 的提交时间戳 commit timestamp
2. txn_3 可以看到 txn_2 和 txn_1 的提交信息
3. txn_1 和 txn_2 并发执行：如果它们对同一条记录进行写入，至少有一个会失败

参考

1. Peng D, Dabek F, Inc G . “Large-scale Incremental Processing Using Distributed Transactions and Notifications” (2010).