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

求个尽量均匀的分区算法

  •  
  •   Rocketer · 259 天前 · 2470 次点击
    这是一个创建于 259 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

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

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

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

    while (*str)
    {
    hash = hash * seed + (*str++);
    }

    return (hash & 0x7FFFFFFF);
    Rocketer
        33
    Rocketer  
    OP
       258 天前 via iPhone
    @FakNoCNName 后 9 位不是严格递增的,还有一些规则在里面,所以分布并不均匀。

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

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