F1的在线异步DDL

介绍F1的在线异步DDL schema变更。

简要问题

定义问题

我们需要处理DDL执行进度不一致的问题,比如:

  1. Node A已经处理了a/b/c三个DDL
  2. Node B刚处理完a这个DDL

假定c是创建一个表,那么Node A能看见这个表,而Node B则看不见。那么分别从Node A和B查询,就会发现数据不一致的情况。

具体来说,有两类不一致问题需要考虑:

  1. orphan data anomaly
    违反1/3/5/7
  2. integrity anomaly
    违反2/4/6

其中:

  1. 所有 ColumnKV 都能找到一个包含它的 Row 和 Table。
  2. 所有 Row 都包含所有非空列的 ColumnKV。
  3. 所有 IndexKV 都能找到一个包含它的 Index。
  4. 所有 Index 都是完整的(不存在某个 Row 缺少指向它的 IndexKV)。
  5. 所有 IndexKV 都指向有效的 Row。
  6. 没有违反 Constraint 的数据。
  7. 不存在未知的 KV(特指除上述 1,3 以外的未知 KV)。

分步解决问题

目标1:在同一时刻改变所有Node的状态。很遗憾,因为各种延迟并不能做到。
妥协后的目标1:在某一时刻修改Schema,在确定的时间长度T之后,整个集群中不会有使用旧Schema的Node继续提供服务。这样在T之后这个修改就是确定生效的了。
方案:

  1. 定时刷新
    每个节点会按照固定时间刷新自己的Schema。
    例如,可以选举出一个Owner,每个节点定时向Owner请求当前的Schema。
  2. 强制失败
    如果刷新失败,则停止服务,而不是继续按照旧Schema服务。

目标1.1:在集群间同步最新的Schema
方案:借助于Spanner

  1. 每次刷新时,从Spanner上的某个固定位置加载Schema。

在实现目标1后,发现还是有问题。例如,虽然a/b在a+T/b+T时刻被完成,但在a+T之前的某个时刻,我们仍然不知道当前状态是a已生效,还是ab都已生效。如果在加上个c,那么情况更复杂。

目标2:在同一时刻,只会有最多两个Schema生效。例如在同一时刻内,最多只有DDL a之前的状态和DDL a之后的状态生效。
分析:直接Bruteforce搞就行,比如插一个barrier,等到DDL a确定生效(等到a+T)后,再执行DDL b。
方案:

  1. 引入Lease,长度等于DDL确定生效的时间
  2. 每个Lease中只能执行一个DDL
  3. 我们在T+2个Lease时一定可以执行DDL b

目标2.1:不会产生不合法的DML。
方案:write fencing

  1. 事务允许跨越多个Lease。
  2. 但是,如果事务中有写操作,写操作只允许在当前Lease中进行:
    1. 写操作在他们submit时,转换为Spanner上的KV操作
    2. 如果写操作跨Lease,可能会违反同一时刻集群中最多只有两个Schema版本生效的限制。

通过实现之前的目标进行了问题的分解,不需要处理多个DDL的进度不一致问题了。但仍然存在问题,考虑一个add index的DDL,Node A上已经执行完了,Node B则没有开始执行,然后考虑此刻开始执行的两个DML:

  1. 通过Node A添加一个Row:会添加数据和索引
  2. 通过Node B删除一个Row:只会删除数据

现在如果从Node A索引读,那么会读到一开始被写入的索引,但对应的数据却被删除了。于是这里产生了孤儿索引的问题,这破坏了数据库的完整性。这是因为不同Node之间同一DDL的进度不同产生的不一致,如何解决呢?

目标3:将这一个DDL拆成多个Schema Change的步骤。由于Update可以看做是Delete+Insert,所以实际需要考虑Insert、Delete和Query三种操作。

从孤儿索引的问题可以看出,delete操作需要和insert操作分离,要拆出一个Delete Only状态,这个状态下该DDL的只对Delete操作可见,即该索引只对Delete操作可见:

  1. 从None到Delete Only
    增和查都不会使用索引。删会使用索引。
  2. 从Delete Only到Public
    不会出现孤儿索引问题了。假如Node A在Delete Only状态,它会在删除时一并删除索引;Node B在Public状态,在查询时发现索引被一并删除了。
    但有个新的问题,索引不会“多出来”,但却可能缺。这就得需要有个操作帮忙补索引,也就是reorg。
    这个补索引的过程能发生在Delete Only到Public之间么?假设Node A在Delete Only阶段,它只能响应删除,然后开始为既有数据补索引,直到补完变成Public,同时可以处理增删改查。问题是这个过程中的insert,对应的索引并没有被补上啊。因此,需要引入新的状态Write Only。

于是引入Write Only状态,这个过程只不允许读:

  1. 从Delete Only到Write Only
  2. 从Write Only到Public
    假如Node A在Write Only状态,它的所有写操作都会涉及索引。而Node B在Public状态,它也能读到Node A的修改。

考虑所有节点都到达了Write Only状态,现在就可以做Reorg补上之前的索引数据了,方式很简单,就是取一个现在的Snapshot,然后照着补。此时可能有并发写的冲突问题,但Spanner的Percolator协议可以解决。

目标4:缩短Lease长度。Lease长度一般都会很长,F1中是分钟级,TiDB中也有45秒。如果完全走Lease的方案,那么一次DDL的时间就是分钟级的了,这显然很难被接受
方案1:直接将Lease长度缩短,例如改为1s。
这个方案是有问题的:

  1. 在每个Lease结束后,Node需要去加载最新的Schema,这个伴随网络开销,需要时间。如果加载Schema的时间大于Lease的时间,那么就会导致刚加载的又失效了,从而重新加载,极大地降低了性能。

既然方案1不行,那么就有了方案2
方案2:

  1. Owner在修改完DDL后,主动通知其他节点,并统计ack。如果其他节点都回复了,那么就主动确定了这个ddl在所有节点上都生效了。
  2. 如果有节点没有回复,那么再主动等2个Lease。

Reference

  1. http://zimulala.github.io/2016/02/02/schema-change-implement/
  2. https://github.com/zimulala/builddatabase/blob/master/f1/schema-change.md
  3. https://disksing.com/understanding-f1-schema-change/
  4. https://tongtianta.site/paper/57876
    Online, Asynchronous Schema Change in F1
  5. https://www.zenlife.tk/schema-lease.md
  6. https://hhwyt.xyz/2021-03-27-online-async-schema-change-in-f1/