F1 中在线异步Schema变更
Online, Asynchronous Schema Change in F1
简介
F1 的主要特性影响到schema变更的地方有：
- 大量的分布
- 关系型schema，每个F1服务都有schema的一份拷贝，变更必须让所有的F1服务更新，相当于一次分布式的变更。
- 共享的数据存储，F1可以访问所有存储在spanner中的数据。
- 无状态服务，F1服务必须容忍机器故障，被取代，丢失网络。所以是无状态的，客户端可以随意连接到任何一个F1。
- 没有全局成员关系，F1服务之间没有通信关系。
在F1上进行Schema变更的要求：
- 所有数据的可访问性，不能因为schema变更而导致系统下线，哪怕是一部分数据库下线都是不可接受的。（比如锁住一个列）
- 最小化性能影响，频繁的schema 变更，要最小化性能的影响，即对用户响应时间的影响。
- 异步schema变更，因为F1之间没有通信协议，所以不能通过F1服务之间通信来同步schema。意味着，不同的F1服务可能使用新的schema在不同的时间点上。
背景
F1提供了一个建立在key-value数据上的关系的视图。
key-value store提供三种操作，put,del,get。
put和del insert或者delete一个给定的key。
get获取前缀符合给定key的数据集合。
F1 提供了乐观并发控制，会给key-value添加两个需求。
- Commit timestamps（提交时间戳）。每个key-value对有一个最后修改时间戳。
- 多个get和put可以被以原子的方式执行。
F1 的schema是一系列表的定义，每个表的定义由一组列、一组耳机索引、一组完整型约束，和一组乐观锁。列可以是原始类型或者复杂类型，主键的类型被严格要求只能是原始类型。在每一行中，列的值可以是缺省的，也可是是必须存在的。使用required标识。
F1 使用一种基于时间戳的乐观并发控制，与Percolator相似。F1 的schema包含一个额外的元素在每个表上，即乐观锁。
一个表可能有多个锁，每个列关联一个确切的乐观锁。每个行有它自己的乐观锁实例基于schema的定义，且这些实例控制了对这些行中的列的事务并发访问。
F1实现行级别的锁，用户可以给表添加新的锁并关联它到一个任意的列中。F1的用户可以选择锁的粒度，可以是行级别的范围锁到列级别的锁。
Schema 是一个特殊的k-v对来表示的。通过一个版本来表示当前的schema版本，当该标本变化的时候，表示有schema变更发生了。
不同的服务使用的新schema的时机不同，同一时刻可能存在多个版本的schema在是使用。
当所有的F1服务都加载了新的schema完成的时候，表示schema change已经完成。
造成数据损坏的主要原因是由于schema变化太过突然了。一部分F1使用旧的，一部分使用新的schema造成了数据损坏。
（PS：通常情况下，一步解决不了问题，就可以拆成若干步来完成。一阶段不行就两阶段，三阶段，直到问题解决，每一阶段都使问题缩小化，朝着最终的目标前进即可解决）
因此，引入中间状态，将一次危险的schema变更，拆解成一系列安全的schema变更。
为了简化正确的实现，F1允许最多不超过2个schema版本在使用。意味着，存在一个短暂的时间窗口，有两个schema版本在使用。超过两个版本的存在会大大引入复杂性。
Schema变更
F1的schema有表、列、索引、约束和乐观锁。称为schema项。每个schema项目都有与之关联的状态。有两种没有中间状态的称为：absent和public。
- absent：当一个schema项不存在的时候，它是缺省的。
- public：当一个schema项存在，并且可以影响或者被所有操作应用的时候，它是public的。
F1也存在两种内部的，中间的状态： delete-only 和 write-only。
Definition 1：delete-only：一个delete-only 表、列、索引 不存在可以被用户读取的对应的k-v对。并且，如果 E 是一个表或者列，它仅仅可以被删除操作修改。如果E是一个索引， 它仅仅可以被delete和update操作修改，并且，update操作只能删除k-v对（当更新索引时），但不能创建新的k-v对。
Definition 2：write-only状态是为列和索引定义的，write-only：一个write-only的列或索引可以允许insert、delete和update操作修改k-v对，但是任何上述的k-v对都不能对用户的读可见。因此，write-only状态允许数据被写入，但不允许读取（就索引而言，F1服务不使用write-only的索引去加速寻找。）
Definition 3：write-only状态也定义了约束，write-only 约束：write-only 约束对于新的 insert、delete和update操作生效，但是它不保证对于所有已存在的数据也保持。
-
Definition 4：一个数据库d在schema S下是遵守一致性的，当且仅当：
- 不存在没有表和行的列数据存在
- 所有的数据行都必须存在必须存在的列数据
- 不存在表结构中没有索引的索引数据项
- 所有对外可见的索引必须有所有数据的完整的索引项
- 所有的索引项目必须指向合法的行数据
- 所有对外公开的约束必须是被遵守的
- 不存在未知的数据
-
Definition 5：一次schema变更，从S1 到 S2 是一致性保持的，当且仅当对于任何数据库d，要一致性遵守包括S1和S2
- 任何在S1下的操作，要维护遵守数据库d在S2下的一致性。
- 任何在S2下的操作，要维护遵守数据库d在S1下的一致性。
数据库的一致性
F1服务将强制新的操作满足约束，但读操作可能看到违背约束。
确保所有的F1服务对于数据库都有一个一致性视图是至关重要的。
- 不允许有孤儿数据。
- 不允许有违反完整性约束的数据。
添加或者删除schema element
可选结构化项
- 添加：absent -> delete only -> public
- 删除：public -> delete only -> database reorganization -> absent
按照上述的schema状态流程做schema变更，所有操作都会避免产生孤儿数据。并且由于添加的schema结构是可选的，所以也不存在完整性异常。
删除时候使用 database reorganization 来对列数据进行回收，清除那些删除掉的列对应的kv对。
必需的结构化项
- 添加：absent -> delete only -> write only -> database reorganization -> public
- 删除：public -> write only -> delete only -> database reorganization -> absent
对于约束
- 添加：absent -> write only -> public
- 删除：public -> write only -> absent
实现
- GC：对于删除列或者索引等，可以使用异步的GC机制来优化 database reorganization 阶段。通过异步删除，加快DDL的进度。
- Write fencing：写栅栏，Schema需要有Lease机制，不允许那些超过Lease的Schema的事务进行提交，以避免数据完整性被违反、或者有孤儿数据。每个Schema都存在一个版本号与之对应，当事务将要提交的时候，通过与内存中的Schema 仓库的接口进行校验，如果事务开始时使用的schema版本已经过时了，则该事务不能提交。必须重试。
F1使用了单独的Schema变更进程。通过版本控制仓库来保存schema变更记录，schema变更进程按照版本控制的更改记录进行schema变更，使其按顺序生效。
不变式：
如果schema S 在时间点t0 写入了，并且没有其它 schema 在 t0 -> t1 之间写入 (t1 > t0 + lease_period )，因此，在 t1 时刻，每个F1服务要么使用 S，要么不允许事务提交。
续Lease根据经验，一般在Lease过半的时候进行续Lease，续Lease的方式，通过周期性地重新读取schema从一个众所周知的位置在k-v store中。如果F1服务没办法续lease，则自行terminate。一般情况下，会再次拉起来，拉起来的时候会获取最新的schema。
对于执行Schema变更的进程，每个状态必须等待Lease时间之后，才能进行下一步状态，尽可能保证所有F1都使用到了最新的Schema。
续Lease可以优先检查Schema 的commit ts是否有变更，没有变更则不重新Load schema。有变更则才重新Load。
Data reorganization，数据重组
- 数据重组必须支持暂停/恢复，并且过程是需要幂等的。
- 在重组期间，所有的数据都是必须可以访问的。因此，重组过程，必须能够容忍并发的访问修改的数据。
- 减少不必要的数据写入。当用户的事务已经写入了需要重组的kv对时，重组执行时就不需要写入。
F1使用了MapReduce的框架的思路，MapReduce控制器将待重组的数据进行分组，将分组信息给到map 任务，map任务扫描分组内所有的行，使用一个快照时间戳（这个时间戳应该是重组执行的时候获取的）。更新每一行遵从新的schema。取决于对应的schema变更操作，可能添加key或者移除。
每个map任务读取每一行并确定它是否已经被用户事务更新过了。如果用户事务更新过了，则map任务不需要更进一步修改行。遵循了Thomas写规则。
The End;
