binlog 的并行重放问题

问题描述是这样的，假设一个大的数据库集群吧，要增量同步到下游，会走一个 binlog 的系统。

第一代的 binlog 系统的设计，把所有的 binlog 搜集到一个地方，然后重放，会形成一个单点。对于整个集群的负载，有这么一个单点是不能 scalable 的。第二代系统就要思考，如何让 binlog 并行起来，也就是今天的话题了。

整个 binlog 抽象成一个 stream，按 stream 的顺序重放，自然是没有问题的。但是顺序重放，这个同步速度太受限了，必须给它并行起来。

先来一个粗粒度的拆分，我们知道，一个表跟另一个表，binlog 同步过程是没有交集的，所以可以按表拆到不同的同步节点上，这是一个简单的拆分方法。

然后看表内怎么拆。假设表是有 pk 的，那么我们可以按 pk 拆分。

insert pk = 1
insert pk = 2
insert pk = 3
insert pk = 7

这几个修改是在不同的 pk 上面，相互是不影响的，可以 hash 到不同的 worker 中，然后并行执行是可以的。

但是数据库场景可能复杂一些，并不只有 pk，有可能还有唯一索引。我们看一个例子，表有两列 pk 和 uk，然后 binlog 是：

insert pk = 1, uk = 2
insert pk = 2, uk = 3
delete pk = 1, uk = 2
delete pk = 2, uk = 3
insert pk = 1, uk = 3

假设是按 pk 的不同进行划分的，pk = 1 和 pk = 2 拆分到不同任务并行：

insert pk = 1, uk = 2
delete pk = 1, uk = 2
insert pk = 1, uk = 3

insert pk = 2, uk = 3
delete pk = 2, uk = 3

这时，会发现 uk 上面有可能出现冲突。比如说一个在执行

insert pk = 1, uk = 3

另一个执行到了

insert pk = 2, uk = 3

则两个事务在写索引的时候会发生事务冲突。观察会发现，有多个唯一索引的时候，是会存在顺序依赖关系的，并不能够按 pk 无脑分片。

这种情况，可以把 binlog 内部的依赖顺序构造出来，对于无依赖顺序的依然可以并行，但是对于有依赖顺序的，需要前面依赖的 binlog 完成之后，才可以执行。只要在当前处理区间内的 binlog 是在同一节点上面，就可以在节点内部做重排，根据依赖顺序。那如果不是在同一节点上面呢？可以做一个 shuffle，原来会冲突的 value，经过 shuffle 之后，一定还是落在同个节点上面。比如 binlog 中的两条记录，其 uk = 3 跟 uk = 3 冲突，shuffle 完还是在同节点，可以判定冲突的。

对于 uk 的值，可以建一个并查集来比较，落在同一个集合中的不同语句是相互有依赖的；落在不同集合中的语句则相互无依赖。

感觉把问题再抽象一下，就可以变成一个面试题了。输入是有序的一条条数据，每条数据包含 a b c d 等多列，这样会构成一个矩阵，例如：

id	a	b	c	d
0	3	4	6	23
1	2	8	7	4
2	6	11	23	5
3	15	8	4	6
4	7	2	7	11
5	15	4	8	12
...

输出要求对这一条条数据进行分组，使得组与组之间，a b c d 列不会有相同的值。

按 a 分组 [0] [1] [2] [3 5] [4]

按 b 分组 [1 3] [0 5] [2] [4]

按 c 分组 [0] [1 4] [2] [3]

按 d 分组 [0] [1] [2] [3] [4] [5]

再组合起来的最后结果 [0 1 3 5] [4] [2]