网站开发php有哪些,权威发布型舆情回应,教做高级料理的网站,极家装修口碑好不好概念
所谓数据发生器#xff0c;最典型的就是 Oracle 的 sequence#xff0c;用户通过 sequence.nextval 可以取得一组连续的值。
但是#xff0c;一般实现里#xff0c;sequence.nextval 是依赖于单线程生成#xff0c;无法做到并发。
一个优秀的分布式顺序数据发生器…概念
所谓数据发生器最典型的就是 Oracle 的 sequence用户通过 sequence.nextval 可以取得一组连续的值。
但是一般实现里sequence.nextval 是依赖于单线程生成无法做到并发。
一个优秀的分布式顺序数据发生器需要满足三个条件
分布式生成有序稠密
算法
本文探讨一种实现方法它由“分布式行生成器” 和“分布式序列生成函数” 两部分组成。同时为了支持分布式生成需要引入 worker id 的概念取值从 0 到 N - 1N为并发度。提供给用户的接口为
select nextval() from table(generator(100));其中table(generator(100)) 为分布式行生成器nextval() 为分布式序列生成函数。 为了实现分布式的行生成则需要
规划好 N 个线程里每个 table(generator(100)) 实例能生成多少个数字。规划好 N 个线程里nextval() 实例能生成哪些数字
先看最简单的场景N10, Rows100我们有两种生成策略。
策略1:
Worker IdRowsValues0100,1,2,3…,911010,11,12,…,19………91090,91,92,…,99
策略2:
Worker IdRowsValues0100,10,20,30…,901101,11,21,…,91………9109,19,29,…,99
稍微复杂一点的场景N10, Rows103就会给我带来一些疑问
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 IdRowsValues0110,10,20,30…,90,1001111,11,21,…,91,1012112,12,22,…,92,1023103,13,23,…,934104,41,21,…,91………9109,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 IdRowsValues0100,1,2,3…,911010,11,12,…,19………91390,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 值。
基于这个算法每个线程要生成多少数字生成什么数字都是预先约定的无需线程之间的通信是一种高效的无锁并行算法。
