大规模数据存储集群数据存放的设计,分布式shardid的生成 - 如何指定范围随机数, 分组随机数

标签

PostgreSQL , 分组ID生成 , 生成哈希映射 , sharding , shard


背景

在一些分布式数据库系统中,通常会有多个数据节点,用户的数据分布策略通常有一致性哈希、按列哈希、随机分布等。

除了随机分布,其他的分布方法数据和数据节点是一对一的关系。

上当节点数变得特别特别多的时候,数据如果依旧按照全局进行哈希分布,可能会带来一个问题,例如节点数到达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,或者同类业务的数据,尽量分布到同样的主机分组中。确保在进行数据分析时,数据的移动较小。

上一篇:可观测平台下告警降噪实践——GOPS分享


下一篇:如何使用Java、Servlet创建二维码