Online, Asynchronous Schema Change in F1

1. 背景

  1. 分布式的 DBMS，底层数据层是共享的分布式 KV store（Spanner），中间层是 F1 servers 保存有 schema 信息并用于承接 client 请求
  2. 底层共享的 KV store 支持 get/put/del 操作，并且使用 OCC 实现分布式特性，使每个键-值对都有一个最近修改自动更新的时间戳，且多个 get 和 put 操作可以原子执行
  3. 当进行 online table schema 变更时，无法做到所有 F1 servers 的 schema 同步变更的（除非整个集群对应表停服），不同 F1 servers 的 schema 不同会导致 DML 应用多个 schemas 去操作底层共享 KV store，导致数据错乱

2. F1 Schema 变更协议

2.1 转移状态机

论文的变更协议就是为了解决在分布式数据库共享数据访问下在线、异步 schema 变更所带来的问题。其核心是：确保在任一时刻，系统使用的 schema 版本不超过两个，并且这些 schema 版本身具有特定的状态属性，不需要在变更时实现全局成员间的隐式或显式同步，也不需要在 DDL 完成后保留旧的 schema。

F1 schema 内部包含 “tables, columns, indexes, constraints, and optimistic locks” 这些元素，其用作于关系型数据表和 KV 表间的映射。

F1 将一次 schema 变更变为系列 schema 状态机转换，去避免 schema 变更产生的数据不一致，限定最多只有两个 schema 的原因也是为了使 schema 变更状态更有限。

F1 把一次 schema 元素的变更拆解为多个逐步递进的中间状态，引入了两个中间状态，即 delete-only（只可删除的）和 write-only（只可写的）。同时，对于元素的非中间状态，定义为 absent（缺失的）和 public（共开的）。

1
2
3
4
5
6
7
8

定义1: 一个只可删除的（Delete-only）元素E（tables/columns/indexes）的 KV 数据，不可以被其他事务读取；
      并且：
      a）如果 schema 元素是一个 tables/columns，那么它只能够被 delete 操作修改；
      b）如果 schema 元素是一个 indexes，那么它只能够被 delete/update 操作修改，但是不能够 insert 新的 KV 数据。

定义2: 一个只可写的（Write-only）columns/indexes 的数据能够被 insert/delete/update 操作修改；但是这些数据不可以其他事务被读取。

定义3: 一个只可写的（Write-only）constraints 是对新写请求 insert/delete/update 应用的，但是不保证所有数据都满足约束。

2.2 状态一致性

任何从 schema S1 至 S2 的直接结构型元素变更，如果其添加或删除了一项 public schema 元素 E，此变更不能保持一致性。以添加 E 的情况，不论 E 是 table, column 或 index ，由 S2 定义的 insert 都将插入 S1 未定义的数据，经过 S1 的删除会导致 E 的数据残留，所以 S1 至 S2 的变更不能保持一致性。

但是，如果其中间添加了一项 delete-only schema 元素 E 的状态将 S1 和 S2 分离，可以保证同时对于 S1 和 S2 状态避免孤立数据异常或完整性异常，进而此两两状态变更过程保持一致。更细节的说明见论文定义和证明，paper 就是花了很多理论来证明这个结论。

当数据库在 schema（中间）状态能满足了上述定义约束后，通过这些状态去转移 schema 状态，分布式系统的数据与 schema 的一致性能够获得保证，

所有类型 DDL 操作的状态转移总结为下图，其中：Optional 是指该 schema 元素是可选的，不一定需要存在的；Required 是指该 schema 元素是必须存在的。

2.3 案例

文章中的例子：

1
2

Add an index:
absent(schema 中 index 不存在) --> delete only --> write only - (data reorg) --> public(schema 中 index 可公开访问)

由于系统允许最多只有两个 schema，因此（对 index element）存在的中间状态集合只有:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

1) absent + delete only：
    这一过程中完成 delete only 状态变更的节点，不再能够写入老结构元素，但同时这一过程不会新出现与此索引相关的任何数据记录；
2) delete only：
    所有节点进入 delete only 状态，表明整个系统不会再新增出现任一相应老结构元素的数据记录，并且不再使用 absent 状态的 schema；
3) delete only + write only：
    这一过程中完成 write only 状态变更的节点，开始出现新结构元素对应的数据记录，不会有 absent 的 schema 访问到不一致数据记录；
    由于不再存在 absent 状态，所有 delete-only 和 write-only 状态的节点能够保证删除记录正确，不会有删除操作因为 schema 元素缺失而残留的索引元素记录；
4) write only + (data reorg)
    因为前面 delete-only 的存在，保证了系统不会存在多余的索引元素记录；当所有 delete only 状态转移到 write only 状态，从这时起，所有节点的数据的变更都能正确地更新索引。
    之后进入 data reorg 阶段，reorg 要做的就是取到当前时刻的 snapshot，为每条数据补写对应的索引记录。
    reorg 开始之后数据可能发生变更，这种情况下底层 Spanner 提供的一致性能保证（时间戳判断），reorg 的写入操作要么失败（说明新数据已提前写入），要么被更新数据覆盖。
5) write only + public
    节点对应 reorg 完成时，索引重建完成，进入 public 状态。
  • 版权声明：如需转载或引用，请附加本文链接并注明来源。