由于数据量庞大,打算分区存储,希望有个高效且尽量均匀的分区算法。
比如有 1 亿条数据,100 个区,那最好每个区都能分到 100 万条左右的数据,越接近越好。
数据的主键是长度为 12 的字符串,我试过把每个字符的 ASCII 码加起来再取模,结果发现均匀度很差,热区能比冷区多 50 倍。
求各位大神推荐个算法,不胜感谢
1
ETiV 2021-03-19 05:25:47 +08:00 via iPhone
数据的主键是长度为 12 的字符串
特征得再详细点:是递增的吗?是随机的吗?是 uuid/guid 算出来的吗?中间有表示 timestamp 含义的吗?等等… |
2
MegrezZhu 2021-03-19 05:50:09 +08:00
hash 取模?
|
5
abcdabcd987 2021-03-19 05:54:41 +08:00
uniform hash % 100?
|
7
Rocketer OP @abcdabcd987 我求的就是这个 uniform hash,有没有具体的思路或代码呢?
|
8
Rocketer OP @MegrezZhu 试过 md5,确实均匀多了,但有点用 40 米的大砍刀杀鸡的感觉,一个分区算法不应该用那么大的计算量
|
9
xuegy 2021-03-19 06:17:49 +08:00
多迭代几次就均匀了。打个比方:你放一坨面里面放一个无限小的小球,然后开始拉面。拉上几次你就不知道那个小球在哪了。
|
10
abcdabcd987 2021-03-19 06:19:11 +08:00 3
@Rocketer 我觉得可以先试试常用的 non-crypto hash % 100 看均匀不均匀吧,比如像 libstdc++ 用的就是 Murmur Hash,或者简单粗暴好实现的 FNV Hash 。实在不行也可以试试看 MD5,虽然 MD5 在密码学上面看不太行,但是作为普通的 hash function 来用一般还是认为挺均匀的。
刚刚搜了一下,这里有篇文章做了一下实验,结论是 Murmur Hash 和 MD5 都挺均匀的: https://www.rolando.cl/blog/2018/12/how_uniform_is_md5.html |
11
aec4d 2021-03-19 08:08:44 +08:00 via iPhone
找一致性 hash 算法,虚拟节点,siphash
|
13
shuax 2021-03-19 08:46:07 +08:00
crc16 也能用嘛
|
14
binux 2021-03-19 08:46:16 +08:00 via Android
|
15
LessonOne 2021-03-19 09:15:17 +08:00
参考下 Java 8 HashMap hash 算法
|
16
0ZXYDDu796nVCFxq 2021-03-19 09:17:48 +08:00 via Android
每个区存 100 万,存满了再用下一个
对于一些按时间区域查询,效率更高 |
17
knightdf 2021-03-19 09:21:19 +08:00
fnv1a hash
|
18
qqq8724 2021-03-19 09:25:35 +08:00
RangePartitioner
|
19
FakNoCNName 2021-03-19 09:43:20 +08:00
你是想做类似: 分区 Id = Num % 100 。这种能快速简单计算的运算吗?
看你在 3 楼说的字符串后 9 位是递增的,这样的话就简单了,取字符串最后 2 位,转成数字 Num,用 Num % 100 就是你想要的结果。 如果你的字符串后 9 位不是 10 进制的,也可以按照类似的逻辑转化处理下,当然要注意分区数量是进制的整数倍,不然就会出现一部分数据过于集中的情况。 |
20
yeguxin 2021-03-19 09:58:14 +08:00
首先查询的场景多不多,如果只是考虑单纯的均匀度合适问题要不要考虑 HashMap 处理 key 落到具体的桶的算法?
(h = key.hashCode()) ^ (h >>> 16) 通过高低位扰动来提高随机性。 |
21
linvon 2021-03-19 10:19:07 +08:00
找一个固定 key,把 key+字符串做 MD5 或者 hash,然后取固定位数模,基本差不多了
|
22
bugmakerxs 2021-03-19 10:23:33 +08:00
@Rocketer md5 速度贼快,不然不会运用这么广泛
|
23
securityCoding 2021-03-19 10:35:40 +08:00
核心在于哈希均衡
1.hashMap 的 hash 算法: 先让高低位异或 & n-1 2.哈希算法 md5 再取模 3.一致性哈希,专门解决这个问题... |
24
macttt 2021-03-19 11:54:01 +08:00
哈希环分片的区尽量多,把这些区视为逻辑分区,多个逻辑分区对应一个物理分区。
|
25
learningman 2021-03-19 12:26:29 +08:00 via Android
MD5 不是可以硬件加速吗,问题不大吧
|
26
wowboy 2021-03-19 14:27:19 +08:00
建议 hash 环分片,openstack 项目就是这么做得。
|
27
hejw19970413 2021-03-19 15:24:43 +08:00
其实没有办法做到完全的平均。我记得 google sre 那本书上好像有这样的例子
|
28
telnetning 2021-03-19 16:00:05 +08:00
@wowboy 嗯?求教,OpenStack 在哪里用的这个环分片啊,我想看看代码学习下
|
29
scemsjyd 2021-03-19 16:28:53 +08:00 via iPhone
一致性哈希+murmur
|
30
xuanbg 2021-03-19 17:24:27 +08:00
自增取模即可
|
31
AItsuki 2021-03-19 22:04:51 +08:00
B 树不适用吗……
|
32
kaflash 2021-03-20 00:00:33 +08:00
unsigned int seed = 131;
unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); |
33
Rocketer OP @FakNoCNName 后 9 位不是严格递增的,还有一些规则在里面,所以分布并不均匀。
这个 hash 要求速度极快,所以还是要在基本算法上做文章。最后采取了反向活跃加权再取模的办法,目前测试效果还不错。 思路说起来也很简单,对字符串中的每一位,越常变化的权重越低,比如最活跃的权重是 C,第二活跃的权重是 C*C……各字符加权求和后再%100,就行了。权重常数 C 从 2 到 100 用真实数据测一遍,就能找到最适合的了。现在各区都在正负 10%内,很满意了。 |