遵义住房和城乡建设局官方网站医院网站icp备案吗
概念
所谓数据发生器,最典型的就是 Oracle 的 sequence,用户通过 sequence.nextval 可以取得一组连续的值。
但是,一般实现里,sequence.nextval 是依赖于单线程生成,无法做到并发。
一个优秀的分布式顺序数据发生器,需要满足三个条件:
- 分布式生成
- 有序
- 稠密
算法
本文探讨一种实现方法,它由“分布式行生成器” 和“分布式序列生成函数” 两部分组成。同时,为了支持分布式生成,需要引入 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 值。
基于这个算法,每个线程要生成多少数字,生成什么数字,都是预先约定的,无需线程之间的通信,是一种高效的无锁并行算法。
