有这样一个需求,首先是有 100 万个 md5 值(不重复,提前录入)
然后每隔 10 秒会产生 300 个新的 md5 值
现在的要求是拿这 300 个去与 100 万个对比,查询出这 300 个里面哪些是包含在那 100 万个里面的,需要极致的速度,越快完成越好。
之前同事用 redis 集合处理,据说好像是 30-40 毫秒(我不确定这个时间是否准确),依旧说还没达到要求,还能不能再极限一点
对了,还有个要求,就是那 100 万个 md5 值,不能丢,需要持久化保存,系统重启之后依旧要在。
求大佬们指点一下思路,主要是速度要快,快,快。
先提前感谢各位大佬的思路。
1
tool2dx 92 天前
md5 是 16 个字节,100 万也才 16,000,000 字节,约合 16M 内存。
redis 已经很快了,再快怕只有手搓一个 hash 查找表了。 |
2
sky497134710 92 天前
md5 -> 二进制 -> redis 位图
|
3
MoYi123 92 天前
速度 30-40 毫秒的话, 我觉得很有可能是用 for 循环查了 300 次 redis, 或者是连 redis 的网络不行. 想个办法写成一句查询, 一次性返回 300 个结果.
如果新 md5 大概率不在这 100 万个里面, 可以外面套一层 bloomfilter, 减少查询量. |
4
Kaiv2 92 天前
直接预加载到机器内存中,消耗时间 0 毫秒
|
5
sagaxu 92 天前
redis pipeline 了解一下
|
6
aflow 92 天前
查询的时候和布隆过滤器组合使用,过滤下应该可以快不少
|
7
sagaxu 92 天前
新版 redis 有 SMISMEMBER
|
8
PTLin 92 天前
那就加载到本机然后前缀树匹配不行吗,我试了下 6800h 单线程匹配也就 1 毫秒
|
9
fruitmonster 92 天前
布隆不行么?
|
10
yagamil 92 天前
我觉得 mysql 都够用了,索引+ in 语句
|
11
bugmakerxs 92 天前
把数据加载到内存生成字典树。
|
12
wxf666 92 天前
就 16MB 内存数据,你直接用语言自带的 Hash / HashMap / Dict / Object / Unordered_map / Table ,不行吗?
|
13
GeekGao 92 天前
30-40 毫秒 都不能满足要求? 那就只能自己撸数据结构了:使用 Bloom Filter + Bit Array 组合 ,用 C/C++实现。还要考虑利用 SIMD 指令加速。
|
14
sillydaddy 92 天前 via Android 1
楼上都是看见问号就开始解题的,你这根本就是无效需求:10 秒才产生 300 个数据,只花 30 毫秒的处理时间还嫌慢,剩下的时间去睡觉吗?这种需求就像原本的目标是从北京到拉萨,却问怎么提高长跑速度。
|
15
duosqs 91 天前
可以结合归并排序的思路,只会扫一遍 100 万的数据。
|
16
netnr 91 天前
|
17
RandomJoke 91 天前
100w 的数据要是不变的,直接启动进内存 hashmap 就行了,布隆主要解决空间问题,你这要是不变的直接 hashmap
|
18
lyxxxh2 91 天前
刚想说加载为内存变量,大家都是这么想的。
|
19
otakustay 91 天前
才 100 万个,1000 万以下我直接内存开 HashMap
|
20
xuelu520 91 天前
redis pipeline 应该就行了,现在主要耗时在连接 redis 上。
|