求个尽量均匀的分区算法

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1353 天前的主题，其中的信息可能已经有所发展或是发生改变。

由于数据量庞大，打算分区存储，希望有个高效且尽量均匀的分区算法。

比如有 1 亿条数据，100 个区，那最好每个区都能分到 100 万条左右的数据，越接近越好。

数据的主键是长度为 12 的字符串，我试过把每个字符的 ASCII 码加起来再取模，结果发现均匀度很差，热区能比冷区多 50 倍。

求各位大神推荐个算法，不胜感谢

分区

算法

均匀

字符

33 条回复 • 2021-03-20 09:12:56 +08:00

ETiV

2021-03-19 05:25:47 +08:00 via iPhone

数据的主键是长度为 12 的字符串

特征得再详细点：是递增的吗？是随机的吗？是 uuid/guid 算出来的吗？中间有表示 timestamp 含义的吗？等等…

MegrezZhu

2021-03-19 05:50:09 +08:00

hash 取模？

Rocketer

2021-03-19 05:51:27 +08:00

@ETiV 前 3 位是表示数据类型的，相对集中，我看了一下大概只有 10 几种在用的组合。后 9 位是递增的。

Rocketer

2021-03-19 05:52:42 +08:00

@MegrezZhu 我求的本质上就是个 hash 算法呀，还是说你指的是那些通用 hash 算法，md5 之类的？

abcdabcd987

2021-03-19 05:54:41 +08:00

uniform hash % 100?

MegrezZhu

2021-03-19 05:56:44 +08:00

@Rocketer 嗯对

Rocketer

2021-03-19 06:05:11 +08:00

@abcdabcd987 我求的就是这个 uniform hash，有没有具体的思路或代码呢？

Rocketer

2021-03-19 06:11:28 +08:00

@MegrezZhu 试过 md5，确实均匀多了，但有点用 40 米的大砍刀杀鸡的感觉，一个分区算法不应该用那么大的计算量

xuegy

2021-03-19 06:17:49 +08:00

多迭代几次就均匀了。打个比方：你放一坨面里面放一个无限小的小球，然后开始拉面。拉上几次你就不知道那个小球在哪了。

abcdabcd987

2021-03-19 06:19:11 +08:00

@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

aec4d

2021-03-19 08:08:44 +08:00 via iPhone

找一致性 hash 算法，虚拟节点，siphash

Rocketer

2021-03-19 08:38:15 +08:00 via iPhone

@aec4d 谢谢，概念问题我都懂，就是需要一个具体的好用的算法

shuax

2021-03-19 08:46:07 +08:00

crc16 也能用嘛

binux

2021-03-19 08:46:16 +08:00 via Android

https://source.chromium.org/chromium/chromium/src/+/master:base/third_party/superfasthash/superfasthash.c

LessonOne

2021-03-19 09:15:17 +08:00

参考下 Java 8 HashMap hash 算法

0ZXYDDu796nVCFxq

2021-03-19 09:17:48 +08:00 via Android

每个区存 100 万，存满了再用下一个
对于一些按时间区域查询，效率更高

knightdf

2021-03-19 09:21:19 +08:00

fnv1a hash

qqq8724

2021-03-19 09:25:35 +08:00

RangePartitioner

FakNoCNName

2021-03-19 09:43:20 +08:00

你是想做类似: 分区 Id = Num % 100 。这种能快速简单计算的运算吗？

看你在 3 楼说的字符串后 9 位是递增的，这样的话就简单了，取字符串最后 2 位，转成数字 Num，用 Num % 100 就是你想要的结果。

如果你的字符串后 9 位不是 10 进制的，也可以按照类似的逻辑转化处理下，当然要注意分区数量是进制的整数倍，不然就会出现一部分数据过于集中的情况。

yeguxin

2021-03-19 09:58:14 +08:00

首先查询的场景多不多，如果只是考虑单纯的均匀度合适问题要不要考虑 HashMap 处理 key 落到具体的桶的算法？
(h = key.hashCode()) ^ (h >>> 16) 通过高低位扰动来提高随机性。

linvon

2021-03-19 10:19:07 +08:00

找一个固定 key，把 key+字符串做 MD5 或者 hash，然后取固定位数模，基本差不多了

bugmakerxs

2021-03-19 10:23:33 +08:00

@Rocketer md5 速度贼快，不然不会运用这么广泛

securityCoding

2021-03-19 10:35:40 +08:00

核心在于哈希均衡
1.hashMap 的 hash 算法: 先让高低位异或 & n-1
2.哈希算法 md5 再取模
3.一致性哈希,专门解决这个问题...

macttt

2021-03-19 11:54:01 +08:00

哈希环分片的区尽量多，把这些区视为逻辑分区，多个逻辑分区对应一个物理分区。

learningman

2021-03-19 12:26:29 +08:00 via Android

MD5 不是可以硬件加速吗，问题不大吧

wowboy

2021-03-19 14:27:19 +08:00

建议 hash 环分片，openstack 项目就是这么做得。

hejw19970413

2021-03-19 15:24:43 +08:00

其实没有办法做到完全的平均。我记得 google sre 那本书上好像有这样的例子

telnetning

2021-03-19 16:00:05 +08:00

@wowboy 嗯？求教，OpenStack 在哪里用的这个环分片啊，我想看看代码学习下

scemsjyd

2021-03-19 16:28:53 +08:00 via iPhone

一致性哈希+murmur

xuanbg

2021-03-19 17:24:27 +08:00

自增取模即可

AItsuki

2021-03-19 22:04:51 +08:00

B 树不适用吗……

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);

Rocketer

2021-03-20 09:12:56 +08:00 via iPhone

@FakNoCNName 后 9 位不是严格递增的，还有一些规则在里面，所以分布并不均匀。

这个 hash 要求速度极快，所以还是要在基本算法上做文章。最后采取了反向活跃加权再取模的办法，目前测试效果还不错。

思路说起来也很简单，对字符串中的每一位，越常变化的权重越低，比如最活跃的权重是 C，第二活跃的权重是 C*C……各字符加权求和后再%100，就行了。权重常数 C 从 2 到 100 用真实数据测一遍，就能找到最适合的了。现在各区都在正负 10%内，很满意了。