也算是一道常见的算法题:有十亿条 URL,来了一个新的 URL 判断是否在里面,提供在线服务
但是想着优先使用 mysql 查询,其次 ES, 想布隆过滤器等不适合在工程应用,要保证准确
现有思路,将 url 进行 md5 存储,作为主键 key 分表放在数据库。
但是不清楚具体这种情况下效率会是怎么样
1
liprais 2021-02-03 13:05:18 +08:00
为啥 bloom 过滤器不行?
|
2
Jooooooooo 2021-02-03 13:07:04 +08:00
"布隆过滤器等不适合在工程应用" "要保证准确"
没有理解布隆的精髓啊 |
3
rahuahua 2021-02-03 13:14:38 +08:00
@Jooooooooo 楼主这种情况确实不适合 bloom 呀
|
4
lanmoyingsheng 2021-02-03 13:20:14 +08:00 4
布隆过滤可以保证不存在。
感觉先布隆过滤,如果不存在直接返回;如果存在 再查 ES 或 mysql ; |
5
liuxu 2021-02-03 13:23:07 +08:00
用 crc64 可以小一点,md5 得 32 位 char 做索引,然后 hash 拆库
|
6
dongtingyue 2021-02-03 13:37:50 +08:00
es 为啥不能保证准确?
|
7
sampeng 2021-02-03 13:40:45 +08:00 via iPhone
请问…用数据库,es 实现了。还考个什么算法?
|
8
herozzm 2021-02-03 13:42:07 +08:00 via Android
@dongtingyue #6 es 更新不能及时体现,只能说接近即时
|
9
liuzhaowei55 2021-02-03 13:48:29 +08:00 via iPhone
热数据放缓存,key hash 后分表,数据库如果用 mongo 单表 2 亿数据,加个索引就行了基本不需要特殊优化。
|
10
swulling 2021-02-03 13:55:54 +08:00
不需要数据库,使用 Hash 表就可以了,先做 Hash,然后进行取模 Mod N,分布到 N 个 Hash 表里。
估计需要 3 台 128G 内存的物理机就足够了。 |
11
tisswb 2021-02-03 13:57:29 +08:00
url 的话 那就先格式化,然后 md5,然后 redis
|
12
fengpan567 2021-02-03 14:01:13 +08:00
ES 为啥不能保证准确性?更新延迟?
|
13
love 2021-02-03 14:19:29 +08:00
md5 太大了,64 位 hash 算法如 xxhash 足够,hash 加个索引 where hash = ? and url = ?就行了
|
14
THESDZ 2021-02-03 15:10:50 +08:00
拆分 模拟树结构就好了
|
15
aeli 2021-02-03 16:58:38 +08:00
10 亿 url,做成短链?
|
16
lambdaq 2021-02-03 17:01:44 +08:00
先申请 10 万台服务器,每个服务器存 1 万条数据。这样是不是就简单了。2333
|
17
chenqh 2021-02-03 17:02:40 +08:00
感觉可以 md5 hash,要是觉得长, 可以只存前 16 位呀
|
18
wangdashuai 2021-02-03 17:17:25 +08:00
可以构造前缀树,这样可以压缩数据大小.
|
19
abersheeran 2021-02-03 17:37:33 +08:00 1
@wangdashuai 压缩前缀树面对十亿这个量级还是不够用的。我之前试过。
楼主这个需求,如果只是判断是否在里面,布隆过滤器就够了。十亿数据,根据最优概率公式算出来,错误率控制在万分之一左右,我记得也就一个多 GB 。 一份之前用过的 Python 代码贴出来以供参考: https://gist.github.com/abersheeran/210f5c1a6f36721302f755e39a242e50 |
20
abersheeran 2021-02-03 17:41:05 +08:00
@abersheeran 如果要精准判断,这里就需要上一个 kv 索引了。这个参考一下 HBase 之类的数据库做法就行,也没啥别的好办法。
|
21
Lemeng 2021-02-03 17:55:58 +08:00
10 亿条,竟然 url
|
22
luozic 2021-02-03 17:59:50 +08:00 via iPhone
Cuckoo Filter 了解一下
|