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

大佬们,来寻求个方案,对比查询怎么才能最快

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

    有这样一个需求,首先是有 100 万个 md5 值(不重复,提前录入)

    然后每隔 10 秒会产生 300 个新的 md5 值

    现在的要求是拿这 300 个去与 100 万个对比,查询出这 300 个里面哪些是包含在那 100 万个里面的,需要极致的速度,越快完成越好。

    之前同事用 redis 集合处理,据说好像是 30-40 毫秒(我不确定这个时间是否准确),依旧说还没达到要求,还能不能再极限一点

    对了,还有个要求,就是那 100 万个 md5 值,不能丢,需要持久化保存,系统重启之后依旧要在。

    求大佬们指点一下思路,主要是速度要快,快,快。

    先提前感谢各位大佬的思路。

    第 1 条附言  ·  91 天前
    确实是自己想复杂了,这个数量级确实不大,直接走内存怎么来都快,感谢大家指点
    20 条回复    2024-09-04 14:44:31 +08:00
    tool2dx
        1
    tool2dx  
       92 天前
    md5 是 16 个字节,100 万也才 16,000,000 字节,约合 16M 内存。

    redis 已经很快了,再快怕只有手搓一个 hash 查找表了。
    sky497134710
        2
    sky497134710  
       92 天前
    md5 -> 二进制 -> redis 位图
    MoYi123
        3
    MoYi123  
       92 天前
    速度 30-40 毫秒的话, 我觉得很有可能是用 for 循环查了 300 次 redis, 或者是连 redis 的网络不行. 想个办法写成一句查询, 一次性返回 300 个结果.

    如果新 md5 大概率不在这 100 万个里面, 可以外面套一层 bloomfilter, 减少查询量.
    Kaiv2
        4
    Kaiv2  
       92 天前
    直接预加载到机器内存中,消耗时间 0 毫秒
    sagaxu
        5
    sagaxu  
       92 天前
    redis pipeline 了解一下
    aflow
        6
    aflow  
       92 天前
    查询的时候和布隆过滤器组合使用,过滤下应该可以快不少
    sagaxu
        7
    sagaxu  
       92 天前
    新版 redis 有 SMISMEMBER
    PTLin
        8
    PTLin  
       92 天前
    那就加载到本机然后前缀树匹配不行吗,我试了下 6800h 单线程匹配也就 1 毫秒
    fruitmonster
        9
    fruitmonster  
       92 天前
    布隆不行么?
    yagamil
        10
    yagamil  
       92 天前
    我觉得 mysql 都够用了,索引+ in 语句
    bugmakerxs
        11
    bugmakerxs  
       92 天前
    把数据加载到内存生成字典树。
    wxf666
        12
    wxf666  
       92 天前
    就 16MB 内存数据,你直接用语言自带的 Hash / HashMap / Dict / Object / Unordered_map / Table ,不行吗?
    GeekGao
        13
    GeekGao  
       92 天前
    30-40 毫秒 都不能满足要求? 那就只能自己撸数据结构了:使用 Bloom Filter + Bit Array 组合 ,用 C/C++实现。还要考虑利用 SIMD 指令加速。
    sillydaddy
        14
    sillydaddy  
       92 天前 via Android   ❤️ 1
    楼上都是看见问号就开始解题的,你这根本就是无效需求:10 秒才产生 300 个数据,只花 30 毫秒的处理时间还嫌慢,剩下的时间去睡觉吗?这种需求就像原本的目标是从北京到拉萨,却问怎么提高长跑速度。
    duosqs
        15
    duosqs  
       91 天前
    可以结合归并排序的思路,只会扫一遍 100 万的数据。
    netnr
        16
    netnr  
       91 天前
    用 JS 写了个例子,大概在 2 ms 完成匹配

    https://www.netnr.com/run/code/4824312705648666717
    RandomJoke
        17
    RandomJoke  
       91 天前
    100w 的数据要是不变的,直接启动进内存 hashmap 就行了,布隆主要解决空间问题,你这要是不变的直接 hashmap
    lyxxxh2
        18
    lyxxxh2  
       91 天前
    刚想说加载为内存变量,大家都是这么想的。
    otakustay
        19
    otakustay  
       91 天前
    才 100 万个,1000 万以下我直接内存开 HashMap
    xuelu520
        20
    xuelu520  
       91 天前
    redis pipeline 应该就行了,现在主要耗时在连接 redis 上。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3568 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 04:48 · PVG 12:48 · LAX 20:48 · JFK 23:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.