大规模数据存储集群数据存放的设计，分布式shardid的生成 - 如何指定范围随机数, 分组随机数
背景
在一些分布式数据库系统中，通常会有多个数据节点，用户的数据分布策略通常有一致性哈希、按列哈希、随机分布等。
除了随机分布，其他的分布方法数据和数据节点是一对一的关系。
上当节点数变得特别特别多的时候，数据如果依旧按照全局进行哈希分布，可能会带来一个问题，例如节点数到达1万个，一张1亿的表，会分布到1万个节点中，那么多个表进行JOIN时，会涉及到1万个节点的运算，这里面可能还涉及节点和节点之间的交互，网络会话也会特别的多。
实际上并不是每张表都需要分布到1万个（所有节点）的。如何解决节点数过多的问题呢？如何让数据落到某些节点，而不是所有节点。这样可以使得集群更加庞大。
例如HDFS，通过NAME NODE来记录每个BLOCK在什么机器上。
NAME NODE的问题是，当集群特别大的时候，NAME NODE会成为瓶颈，不利于扩展。
还有一些方法可以解决大集群的问题，例如多级数据节点、分组数据节点。
大集群的分组设计举例
计算节点分组
例如有1万台主机，对应一万个数据库单元，划分为一些分组，例如每100个主机（数据库实例），一共100个分组。
当然，不一定要求每个分组的主机数一致。
给每个数据库实例一个唯一编号。
1、例子1，如果每个分组的主机数固定，通过这种方法，可以得到某个分组内的一个随机ID。
（适合这样的场景，我已经知道某个表应该在哪个分组内，然后这个表在这个分组内是随机存放的，那么通过这种方法，可以得到一个组内随机的主机ID）
create or replace function get_gp_rid1(gid int, gsz int) returns int as $$
select gsz*gid + (ceil(random()*gsz))::int;
$$ language sql strict;
随机概率如下
postgres=# select id, count(*) from (select get_gp_rid1(0,10) id from generate_series(1,10000) ) t group by 1 order by 1;
id | count
----+-------
1 | 949
2 | 965
3 | 1012
4 | 1064
5 | 1029
6 | 970
7 | 964
8 | 1035
9 | 1018
10 | 994
(10 rows)
postgres=# select id, count(*) from (select get_gp_rid1(1,10) id from generate_series(1,10000) ) t group by 1 order by 1;
id | count
----+-------
11 | 993
12 | 1023
13 | 986
14 | 981
15 | 978
16 | 994
17 | 1002
18 | 1019
19 | 976
20 | 1048
(10 rows)
postgres=# select id, count(*) from (select get_gp_rid1(2,10) id from generate_series(1,10000) ) t group by 1 order by 1;
id | count
----+-------
21 | 1009
22 | 985
23 | 988
24 | 1040
25 | 988
26 | 1065
27 | 986
28 | 957
29 | 993
30 | 989
(10 rows)
postgres=# select id, count(*) from (select get_gp_rid1(2,10) id from generate_series(1,10000000) ) t group by 1 order by 1;
id | count
----+---------
21 | 999704
22 | 999015
23 | 1001106
24 | 999979
25 | 999599
26 | 999417
27 | 1000242
28 | 1000675
29 | 999423
30 | 1000840
(10 rows)
Time: 4629.229 ms
2、例子2，对于组的机器数不一致，但是主机ID连续的场景，可以使用这种方法得到一个组内的随机ID。
create or replace function get_gp_rid2(f int, c int) returns int as $$
select f - 1 + (ceil(random()*(c-f+1)))::int;
$$ language sql strict;
随机分布均匀
postgres=# select id, count(*) from (select get_gp_rid2(2,10) id from generate_series(1,10000000) ) t group by 1 order by 1;
id | count
----+---------
2 | 1111981
3 | 1112798
4 | 1110522
5 | 1111070
6 | 1111159
7 | 1109720
8 | 1109822
9 | 1111450
10 | 1111478
(9 rows)
Time: 4631.884 ms
3、例子3，组的机器数不一致，同时主机ID不连续，可以通过这种方法得到一个组内的随机ID。
create or replace function get_gp_rid3(id int[]) returns int as $$
select id[ceil(array_length(id,1)*random())];
$$ language sql strict;
数据分布均匀
postgres=# select id,count(*) from (select get_gp_rid3(array[1,2,3,4,5,7,8,9,100,199]) id from generate_series(1,1000000)) t group by 1 order by 1;
id | count
-----+--------
1 | 100898
2 | 99818
3 | 99434
4 | 100085
5 | 100461
7 | 100361
8 | 99725
9 | 100002
100 | 99646
199 | 99570
(10 rows)
表和分组的映射关系
表和分组的映射关系，可以使用类似name node的方法。
因为分组数可能发生变化，不推荐使用一致性算法类的MAPPING方法，确保表不需要随着分组的变化而变化。
分组内数据分布设计
1 完全随机分布
如果数据在分组内完全随机分布，那么就可以像前面写的几个函数那样，获得分组内主机的随机ID。
2 虚拟BLOCK分布
首先需要将数据存放规划为虚拟BLOCK聚集的方式（例如100000条记录一个BLOCK，举例而已）。每个BLOCK有对应的编号。
每个BLOCK落在不同的数据库实例（主机）中，这个映射关系依旧建议使用类似name node的方法。
因为分组内的主机（数据库实例）数可能发生变化，不推荐使用一致性算法类的MAPPING方法，确保表不需要随着分组内主机(数据库实例）数的变化而变化。
数据记录和虚拟BLOCK的关系
1、哈希，例如按某列进行哈希，根据哈希值决定记录写入哪个BLOCK。
建议使用一致性哈希分布，确保在扩展或收缩BLOCK数量时，数据的移动最小。
2、范围，适合自增、时间、序列等类型，例如每100000一个block，等等。
3、固定哈希，这种方式比较暴力，例如一开始就设计好一个固定的哈希数，如65536。
固定哈希的扩容不太方便，扩容时移动的数据可能较多。建议按2的N或者N的N次方哈希和扩容。这样的话，扩展只是分裂BLOCK，也蛮简单的。
虚拟BLOCK的迁移
采用NAME NODE记录了BLOCK和分组内主机的映射关系，因此MOVE block也变得很简单，只要移动，并更新NAME NODE。
小结
要管理特别大的集群，数据分布只是其中很小的一个部分。
但是数据分布是一个非常重要的缓解，分布规则没有涉及好，可能导致将来扩展、迁移、性能、稳定性等带来不便。
分组是一个将大化小的方法，因为往往一个业务、或者一个表，不需要离散到所有主机。离散到过多的主机上可能会导致连接、数据重分布，数据JOIN等一些问题。
通常的做法是将需要JOIN，或者同类业务的数据，尽量分布到同样的主机分组中。确保在进行数据分析时，数据的移动较小。