V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Rocketer
V2EX  ›  程序员

求个尽量均匀的分区算法

  •  
  •   Rocketer · 2021-03-19 05:06:59 +08:00 · 3871 次点击
    这是一个创建于 1327 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

    33 条回复    2021-03-20 09:12:56 +08:00
    ETiV
        1
    ETiV  
       2021-03-19 05:25:47 +08:00 via iPhone
    数据的主键是长度为 12 的字符串

    特征得再详细点:是递增的吗?是随机的吗?是 uuid/guid 算出来的吗?中间有表示 timestamp 含义的吗?等等…
    MegrezZhu
        2
    MegrezZhu  
       2021-03-19 05:50:09 +08:00
    hash 取模?
    Rocketer
        3
    Rocketer  
    OP
       2021-03-19 05:51:27 +08:00
    @ETiV 前 3 位是表示数据类型的,相对集中,我看了一下大概只有 10 几种在用的组合。后 9 位是递增的。
    Rocketer
        4
    Rocketer  
    OP
       2021-03-19 05:52:42 +08:00
    @MegrezZhu 我求的本质上就是个 hash 算法呀,还是说你指的是那些通用 hash 算法,md5 之类的?
    abcdabcd987
        5
    abcdabcd987  
       2021-03-19 05:54:41 +08:00
    uniform hash % 100?
    MegrezZhu
        6
    MegrezZhu  
       2021-03-19 05:56:44 +08:00
    @Rocketer 嗯对
    Rocketer
        7
    Rocketer  
    OP
       2021-03-19 06:05:11 +08:00
    @abcdabcd987 我求的就是这个 uniform hash,有没有具体的思路或代码呢?
    Rocketer
        8
    Rocketer  
    OP
       2021-03-19 06:11:28 +08:00
    @MegrezZhu 试过 md5,确实均匀多了,但有点用 40 米的大砍刀杀鸡的感觉,一个分区算法不应该用那么大的计算量
    xuegy
        9
    xuegy  
       2021-03-19 06:17:49 +08:00
    多迭代几次就均匀了。打个比方:你放一坨面里面放一个无限小的小球,然后开始拉面。拉上几次你就不知道那个小球在哪了。
    abcdabcd987
        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
    aec4d
        11
    aec4d  
       2021-03-19 08:08:44 +08:00 via iPhone
    找一致性 hash 算法,虚拟节点,siphash
    Rocketer
        12
    Rocketer  
    OP
       2021-03-19 08:38:15 +08:00 via iPhone
    @aec4d 谢谢,概念问题我都懂,就是需要一个具体的好用的算法
    shuax
        13
    shuax  
       2021-03-19 08:46:07 +08:00
    crc16 也能用嘛
    LessonOne
        15
    LessonOne  
       2021-03-19 09:15:17 +08:00
    参考下 Java 8 HashMap hash 算法
    0ZXYDDu796nVCFxq
        16
    0ZXYDDu796nVCFxq  
       2021-03-19 09:17:48 +08:00 via Android
    每个区存 100 万,存满了再用下一个
    对于一些按时间区域查询,效率更高
    knightdf
        17
    knightdf  
       2021-03-19 09:21:19 +08:00
    fnv1a hash
    qqq8724
        18
    qqq8724  
       2021-03-19 09:25:35 +08:00
    RangePartitioner
    FakNoCNName
        19
    FakNoCNName  
       2021-03-19 09:43:20 +08:00
    你是想做类似: 分区 Id = Num % 100 。这种能快速简单计算的运算吗?

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

    如果你的字符串后 9 位不是 10 进制的,也可以按照类似的逻辑转化处理下,当然要注意分区数量是进制的整数倍,不然就会出现一部分数据过于集中的情况。
    yeguxin
        20
    yeguxin  
       2021-03-19 09:58:14 +08:00
    首先查询的场景多不多,如果只是考虑单纯的均匀度合适问题要不要考虑 HashMap 处理 key 落到具体的桶的算法?
    (h = key.hashCode()) ^ (h >>> 16) 通过高低位扰动来提高随机性。
    linvon
        21
    linvon  
       2021-03-19 10:19:07 +08:00
    找一个固定 key,把 key+字符串做 MD5 或者 hash,然后取固定位数模,基本差不多了
    bugmakerxs
        22
    bugmakerxs  
       2021-03-19 10:23:33 +08:00
    @Rocketer md5 速度贼快,不然不会运用这么广泛
    securityCoding
        23
    securityCoding  
       2021-03-19 10:35:40 +08:00
    核心在于哈希均衡
    1.hashMap 的 hash 算法: 先让高低位异或 & n-1
    2.哈希算法 md5 再取模
    3.一致性哈希,专门解决这个问题...
    macttt
        24
    macttt  
       2021-03-19 11:54:01 +08:00
    哈希环分片的区尽量多,把这些区视为逻辑分区,多个逻辑分区对应一个物理分区。
    learningman
        25
    learningman  
       2021-03-19 12:26:29 +08:00 via Android
    MD5 不是可以硬件加速吗,问题不大吧
    wowboy
        26
    wowboy  
       2021-03-19 14:27:19 +08:00
    建议 hash 环分片,openstack 项目就是这么做得。
    hejw19970413
        27
    hejw19970413  
       2021-03-19 15:24:43 +08:00
    其实没有办法做到完全的平均。我记得 google sre 那本书上好像有这样的例子
    telnetning
        28
    telnetning  
       2021-03-19 16:00:05 +08:00
    @wowboy 嗯?求教,OpenStack 在哪里用的这个环分片啊,我想看看代码学习下
    scemsjyd
        29
    scemsjyd  
       2021-03-19 16:28:53 +08:00 via iPhone
    一致性哈希+murmur
    xuanbg
        30
    xuanbg  
       2021-03-19 17:24:27 +08:00
    自增取模即可
    AItsuki
        31
    AItsuki  
       2021-03-19 22:04:51 +08:00
    B 树不适用吗……
    kaflash
        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);
    Rocketer
        33
    Rocketer  
    OP
       2021-03-20 09:12:56 +08:00 via iPhone
    @FakNoCNName 后 9 位不是严格递增的,还有一些规则在里面,所以分布并不均匀。

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

    思路说起来也很简单,对字符串中的每一位,越常变化的权重越低,比如最活跃的权重是 C,第二活跃的权重是 C*C……各字符加权求和后再%100,就行了。权重常数 C 从 2 到 100 用真实数据测一遍,就能找到最适合的了。现在各区都在正负 10%内,很满意了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2955 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 14:47 · PVG 22:47 · LAX 06:47 · JFK 09:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.