Online, Asynchronous Schema Change in F1

背景

分布式数据库 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.