分布式顺序数据发生器

概念

所谓数据发生器，最典型的就是 Oracle 的 sequence，用户通过 sequence.nextval 可以取得一组连续的值。

但是，一般实现里，sequence.nextval 是依赖于单线程生成，无法做到并发。

一个优秀的分布式顺序数据发生器，需要满足三个条件：

1. 分布式生成
2. 有序
3. 稠密

算法

本文探讨一种实现方法，它由“分布式行生成器” 和“分布式序列生成函数” 两部分组成。同时，为了支持分布式生成，需要引入 worker id 的概念，取值从 0 到 N - 1，N为并发度。提供给用户的接口为：

select nextval() from table(generator(100));

其中，table(generator(100)) 为分布式行生成器，nextval() 为分布式序列生成函数。
为了实现分布式的行生成，则需要：

• 规划好 N 个线程里，每个 table(generator(100)) 实例能生成多少个数字。
• 规划好 N 个线程里，nextval() 实例能生成哪些数字

先看最简单的场景，N=10, Rows=100，我们有两种生成策略。

策略1:

Worker Id	Rows	Values
0	10	0,1,2,3…,9
1	10	10,11,12,…,19
…	…	…
9	10	90,91,92,…,99

策略2:

Worker Id	Rows	Values
0	10	0,10,20,30…,90
1	10	1,11,21,…,91
…	…	…
9	10	9,19,29,…,99

稍微复杂一点的场景：N=10, Rows=103，就会给我带来一些疑问：

• table(generator(100)) 实例的行数生成算法是什么？
• nextval() 实例的数字生成公式是什么？

下面给出一个算法：

rows = worker_id * (Rows / N) + (worker_id < Rows % N ? 1 : 0)
initialize nextval.next = worker_id;
nextval.next = nextval.next + N;

基于这个算法，的到的数据表格为：

Worker Id	Rows	Values
0	11	0,10,20,30…,90,100
1	11	1,11,21,…,91,101
2	11	2,12,22,…,92,102
3	10	3,13,23,…,93
4	10	4,41,21,…,91
…	…	…
9	10	9,19,29,…,99

再给一个算法，剩余的数字由最后一个线程生成：

rows = worker_id * (Rows / N) + (worker_id == N -1 ? Rows % N : 0)
initialize nextval.next = worker_id * N;
nextval.next = nextval.next + 1;

Worker Id	Rows	Values
0	10	0,1,2,3…,9
1	10	10,11,12,…,19
…	…	…
9	13	90,91,92,…,99,100,101,102

考虑到 N 一般不大，两种算法看上去都还行。

但考虑到更少 corner case 的话，第一种算法的倾斜更少，更为推荐。第二种算法，一个典型的 corner case 就是：N = 10, total_rows = 9 的时候，所有行都是由最后一个线程（worker id = 9）生成。如果这是一个比较底层的驱动表，可能会导致后继非常严重的 skew。

结论

分布式顺序数据发生器算法如下

rows = worker_id * (Rows / N) + (worker_id < Rows % N ? 1 : 0)
initialize nextval.next = worker_id;
nextval.next = nextval.next + N;

值得注意的是，nextval() 函数此时是一个有状态函数，它需要记住上一次的 nextval 值。

基于这个算法，每个线程要生成多少数字，生成什么数字，都是预先约定的，无需线程之间的通信，是一种高效的无锁并行算法。