972
大規模數據存儲集群數據存放的設計，分布式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，或者同類業務的數據，盡量分布到同樣的主機分組中。確保在進行數據分析時，數據的移動較小。
最後更新：2017-07-14 09:04:05