如题:
马上下班了,突然来了一个需求,
mongodb 存了 5 亿条 email,现有 100 万英文人名,想把包含人名的所有 email 找到,怎么办,
我想破脑子都没想明白应该怎么做,感觉这个除了遍历没有其他方法了,
如果遍历的话,是 O(mn),也就是 100 百万 * 5 亿次匹配,这也太慢了,12 个小时也搞不完,求大佬帮忙想想办法。
1
0x0208v0 OP 这种需求能实现吗,如果不能的话我就辞职了 :( 好难过,这数据量已经让我所有办法无效了
|
2
leido 2020-08-27 18:55:39 +08:00
email 根据人名排序, 然后二分查找.
|
3
xupefei 2020-08-27 18:56:06 +08:00 via iPhone
多开几台机器分块跑呗。mongo 那边只读,性能瓶颈就是那台机器的硬盘和网络带宽。
同时匹配所有人名用 Aho Corasick 算法。 |
4
a719114136 2020-08-27 18:56:50 +08:00 via Android
人名存字典
|
5
AX5N 2020-08-27 18:58:05 +08:00
建立索引+多线程?
|
6
br00k 2020-08-27 19:00:55 +08:00
有索引直接查库效率应该还可以。100w 开多个线程应该也挺快的。
|
7
a719114136 2020-08-27 19:00:58 +08:00 via Android
最好的方法还是临时起个数据库,人名都放进去,这样方便多台机器同时跑
|
8
qq316107934 2020-08-27 19:01:57 +08:00 1
每一封 email 不长的话分词然后用布隆过滤器,效率很高的,扫一遍就行。
|
9
0x0208v0 OP 不行啊,如果人名是 tom,email 是 [email protected] 那么人名存字典是不行的
|
10
qq316107934 2020-08-27 19:02:50 +08:00
上面说要建索引的,我理解这是说正文包含指定人名的吧,建立全文索引太慢了。
|
11
qq316107934 2020-08-27 19:04:17 +08:00
@v2exblog #9 楼主得再说清楚点,是在哪个字段寻找人名,正文还是发件人还是 email,可以精确匹配,左匹配,可以分词,还是只能正则模糊匹配。
|
12
0x0208v0 OP 在 email 字段寻找人名
|
13
rrfeng 2020-08-27 19:06:41 +08:00
有索引吗?
没有的话 100w 人名先 hash 一下,然后遍历 5 亿数据,对比只要 O(1),也就是 5 亿次。 100w 人名也用不了太多存储 |
14
heiheidewo 2020-08-27 19:20:16 +08:00
先把 100 万英文人名建立好 AC 自动机,然后扫一遍 5 亿 email 用不了多久吧?
|
15
matrix1010 2020-08-27 20:04:32 +08:00 via Android
当然能实现,也不要 100 万 x5 亿次,但如果公司真限定你一个人 12 小时做完那你还是辞职吧
|
16
0x0208v0 OP @matrix1010 哭了,太难了
|
17
whahuzhihao 2020-08-27 20:22:47 +08:00
放到 es 里面搜?空间换时间
|
18
loading 2020-08-27 20:28:21 +08:00 via Android
只有两个字段吗?
排序然后二分不已经很快了吗? |
19
pcbl 2020-08-27 20:28:59 +08:00 12
先随机给每一个邮箱找些出来交差,老板要是说数据不对的话,怼他让他 24 小时内核对下试试。。
|
20
Mutoo 2020-08-27 20:36:26 +08:00
100 万英文人名 先折分去重一下,不至于有这么多。英文重名率挺高的。
|
21
atwoodSoInterest 2020-08-27 20:39:43 +08:00
其实只能匹配,楼上说的二分法,其实没有作用,因为人名是可以包含在中间的。
我觉得思路应该放在优化上,适当的剪枝或许能有大作用,比如在写匹配算法的时候,遇到 @就停止匹配,一下就减少了差不多一半的匹配次数。你多看看数据,应该是有一些数据是可以很轻易就去掉的,比如 qq 邮箱全数字这种就直接去掉,一下子也能剪去不少。 |
22
atwoodSoInterest 2020-08-27 20:42:15 +08:00 1
人名可以做成字典树,在匹配上也能快不少
|
23
qq316107934 2020-08-27 20:44:23 +08:00
@atwoodSoInterest #21 12h,感觉代码写不完啊,有限时间内最快捷的方案是洗数据+ 堆机器查,公司要是有 HDFS 的话放里面用 Hive 查。
|
24
0x0208v0 OP @atwoodSoInterest 谢谢大佬!我准备用字典树+减树法试试
|
25
iseki 2020-08-27 21:22:57 +08:00 via Android
建 AC 自动机然后遍历全部数据是唯一方案吧…优化也只能从其他角度上走比如加机器什么的…
|
26
murmur 2020-08-27 21:26:57 +08:00
ac 自动机这数据量也有点巨大
什么需求能有五亿邮件 |
27
iseki 2020-08-27 21:28:49 +08:00 via Android
啊…人名是有点多,内存可能装不下…那…加机器?
|
28
iseki 2020-08-27 21:29:49 +08:00 via Android
我觉得人名库编译成自动机装得下没问题
|
29
laminux29 2020-08-27 21:39:58 +08:00 5
估算了一下,一台 16 核 140GB 服务器,120GB * 250MB,C++纯内存跑大概需要 27-40 个小时。
这种服务器如果来一打,抛开数据交换时间,算一次的时间估计能压缩在 3 个小时内。 但问题是: 1.你们需要足够的服务器资源,以及足够强劲的内网带宽。服务器不够,或者内网带宽只有百兆,那就 GG 了。 2.你们需要经验丰富的分布式 C++数据处理经验。不然跑一次 3 小时,发现有问题,改下程序重新跑一次,3 小时又过去了。 3.从 MongoDB 的数据导出,再到 C++的分布式数据导入,需要全程不能踩坑。 比如,MongoDB 导出时,导出工具有 bug,导致处理了半个小时突然卡死; 或者 MongoDB 是分布式架构且数据导出对于磁盘甚至网络是随机 IO 操作; 或者 C++导入数据时忘了用 cache 提速导致导入时瓶颈在机械硬盘的随机 IO 上; 甚至,MongoDB 导出时,发现早期数据录入阶段,因为写策略没使用安全策略且踩了 MongoDB 的性能 bug 导致丢数据; 就算前面都顺利,在最后把这 120GB 均分到不同服务器时,发现交换机的带宽居然不够。或者早期图便宜只用了超 5 类线,等等,这些都是坑。 我咋感觉,这需求,有点像是公司恶意辞退? |
30
iseki 2020-08-27 21:42:07 +08:00
额,难道是 12 小时内让你搞定?我还以为是单次任务最多跑 12 小时 emmm 十二小时内写代码测试跑完基本不太可能吧 emmm
|
31
my1103 2020-08-27 21:46:59 +08:00
下班没(手动狗头)
|
32
lizytalk 2020-08-27 21:52:19 +08:00
首先扫描一遍所有邮件建立一个 k-tuple (例如序列 abcd,它的所有 2-tuple 就是 ab,bc,cd )的索引。然后对于每一个人名,只需要在有共同的 k-tuple 的那些邮件里用字符串匹配算法就行了(因为如果名字在邮件里出现了,必然会有共同的 k-tuple ),这样可以过滤掉很多邮件。
k 的选择,可以多选择几个,对不同长度的名字应用不同的 k 。 |
33
fushall 2020-08-27 22:07:55 +08:00
这需求,字典树都够呛能在一台有限内存的机器上跑出来。就算能,也得代码也得非常好,要是用 Python 那种语言,估计内存就爆炸了。12 小时之内没希望能完成,看得出来,这种提问,应该是你自己一个人在硬着头皮搞。明天直接说一下吧,这东西搞不来,楼上 有位大神都帮你分析了,你品你细品
|
34
oneisall8955 2020-08-27 22:11:14 +08:00 via Android
额,想起这个月初那天通宵搞对接第三方接口+上线,楼主看着办吧🐶
|
35
0bit 2020-08-27 22:15:11 +08:00
如果允许损失一定精度,可以考虑使用 Bloom Filter (布隆过滤器)
1. 先把名字规整化,全部小写,去除多余字符,每个名字一个字符串 2. 创建一个 BloomFilter,写入全部的名字规则 3. 遍历 MongoDB 的记录,判断是否在 BloomFilter 中,找出符合条件的 PS:如果公司故意恶心你,还不如直接走了算了。 |
36
iseki 2020-08-27 22:46:55 +08:00
啊,我傻了,我算错了,要是字典树写得不够好 100G 内存真是够呛塞得下
|
37
nuk 2020-08-27 22:51:30 +08:00
hyperscan ?
|
38
HunterPan 2020-08-27 23:16:22 +08:00 via iPhone
5 亿数据按前缀打到数据库的分片上,10 个分片就够了,然后 100w 查询 就这样
|
39
heiheidewo 2020-08-27 23:26:29 +08:00
@iseki 想啥呢,100w 个英文名建 AC 自动机,怎么要 100G 内存,英文名全部转成小写,撑死 1G 内存
|
40
imdong 2020-08-27 23:30:53 +08:00
非专科,算法渣,我想的办法是:
把邮件名中按字母建立索引,然后用人名去对应的索引中查找(假设名字中没有数字和符号)。 比如: [email protected] 同时进入:a t h o m 6 这几个的索引。 如果想加速,就每两两三三再建一层索引: ha ah at to om 这样。 最后查询的话,拿 tom 去命中 t o m 或者 to om 中的数据。 然后再去检查,对比匹配的数量应该会少很多。 |
41
iseki 2020-08-27 23:42:13 +08:00
@heiheidewo 我傻了,计算时 0 写多了
|
42
pcbl 2020-08-27 23:55:59 +08:00 2
看到很多楼层完全就不审题就开干了,好奇工作中也是这样的吗
|
43
raaaaaar 2020-08-28 00:08:51 +08:00 via Android
别讲了,楼主已经被开除了
|
44
iseki 2020-08-28 00:20:01 +08:00 via Android
我感觉自己逐渐清醒了一点…100w 个人名…真的没有重复吗😅
|
45
yuang 2020-08-28 00:23:03 +08:00 via Android
收藏了,以备不时之需
|
46
chihiro2014 2020-08-28 00:29:42 +08:00
布隆过滤器了解下?
|
47
swulling 2020-08-28 00:41:37 +08:00 via iPad 1
其实就是五亿个字符串和 100 万字符串做子串匹配。
如果是精确匹配,将 100 万字符串放 hash 表比如 python 的字典,然后对五亿字符串遍历一次,每个字符串查看是否在 hash 表就行。时间复杂度 O ( N )。还是很快的,内存占用也就 1G 左右吧。 但是要做模糊匹配就麻烦了,上面的 bloomfilter 之类的办法全都不能用。 |
48
swulling 2020-08-28 00:44:57 +08:00 via iPad 2
其实有大集群直接 grep 都行,测试了下,对一个邮件地址,通过 grep -F 从 100 万个子串中查找匹配,大约耗时 1s 。那么就是五亿秒总计算时间。
假如有 2000 台机器,每台机器 20 核 20 并发,那么就是 12500s,也就几个小时而已。 |
51
xupefei 2020-08-28 06:19:18 +08:00 39
讨论一天了,我来总结一下吧。首先,楼主的问题是是 substring matching:有输入(邮箱,集合 N )和一个字典(集合 D )。要求找到一个集合 R,使[D 中存在一项 d]是[R 中任意一项 r]的子字符串。
楼上提出了多种解法: 1. 人名排序二分查找:不适用 substring matching 问题。 2. Bloom filter 布隆过滤器:不适用 substring matching 问题。Bloom filter 只能解决字符串整体匹配的问题,除非你有完美的分词方法。 3. k-tuple / n-gram 定长索引:适用于此问题。这方法在数据库领域用的很多,关键词是 inverted list matching 和 filtering and verification 。这个办法一般用来加速 M*N 的 JOIN 问题。它的原理是一个必要不充分条件:“如果字符串 a 是 b 的子串,那么两者的 n-gram 集合 gram(a)和 gram(b)中必定有一个重复项,反之不成立”。这个条件不充分,所以用它来 filtering 后的结果存在假阳性( false positive ),需要一个额外的 verification 步骤来对结果逐个确认真实性。 在 verification 这一步中,我们能拿到的是一个邮箱 n 和若干潜在匹配的字典项集合 D',只能循环 n*|D'| 次来逐个验证。 4. 多层定长索引:false positive 比解法 3 少一点点,但是 filtering 这一步比解法 3 慢很多。总体还是慢了。 4. 特殊字符剪枝:恭喜你重新发明了一个简化版的解法 5😂 5. Aho Corasick,AC 自动机:解决此问题的正确答案。具体原理中文维基百科的例子不错,推荐看一看。它的特点是能在线性时间内同时尝试匹配所有字典项目。LZ 的问题写代码的话就是这样的: R = 空集 T = buildTrie(D) for n in N: __if(T.lookup(n)): ____R = R + {n} return R 注意,整个 for 循环都是可以同步跑的,多线程或分布式都没有问题,因为字典树 T 从来没变过。 |
52
levelworm 2020-08-28 08:11:39 +08:00 via Android
问题你怎么确定是人名? tom 也可以不是人名啊。。。比如说 tome666,这算人名不算?
|
53
levelworm 2020-08-28 08:14:51 +08:00 via Android
没用过 mongodb,如果是正常的数据库 join 可以么。。。没试过这么大的数据。。。有些数据库 join 规则可以写的比较复杂
|
54
shakoon 2020-08-28 08:23:02 +08:00
12 小时已经过去了,楼主凉了没?
|
55
yngzij 2020-08-28 08:27:34 +08:00
楼主估计已经辞职了
:dog |
56
IMCA1024 2020-08-28 08:52:14 +08:00
这有点为难,钱没给够
凭什么 12 小时内出结果 |
57
yuanse 2020-08-28 08:54:42 +08:00 via Android
楼主辞职了吗🌚
|
58
ccppgo 2020-08-28 08:55:37 +08:00
楼主人还好吗?
|
59
murmur 2020-08-28 08:56:35 +08:00
楼主估计正在办手续
|
60
xuanbg 2020-08-28 09:05:17 +08:00
老板估计已经放弃了。
|
61
Visitor233 2020-08-28 09:06:07 +08:00
楼主昨天下班了吗?
|
62
Geekerstar 2020-08-28 09:07:42 +08:00
楼主凉了吗
|
63
p1gd0g 2020-08-28 09:14:27 +08:00
哈哈哈哈,楼上你们够了。
|
64
vone 2020-08-28 09:26:33 +08:00
楼主下家准备去哪里。
|
65
itskingname 2020-08-28 09:26:40 +08:00
不要被 MongoDB 这个要求给限制了。5 亿邮箱没多大。全部拉下来,放在一个文本文件里面。然后用 shell 命令执行 grep 去查询名字,查询结果 > 文件就好了。2 个小时搞定。
|
66
qingxiangcool 2020-08-28 09:26:40 +08:00
楼主在讨论 N+1 了吗? @xupefei 51 楼整理的不错, 厉害了.
|
67
xmmmm 2020-08-28 09:26:51 +08:00
家里空调舒服吗
|
69
mmrx 2020-08-28 09:36:52 +08:00
14h 39m ago 了...想念楼主
|
70
nooper 2020-08-28 09:47:19 +08:00
pandas 可以搞定,向量内存计算,可以协同 GPU.速度应该很快
|
71
SbloodyS 2020-08-28 09:53:28 +08:00
楼主还好吗
|
72
kkjinping 2020-08-28 09:54:10 +08:00
加班赔偿有吗
|
73
iseki 2020-08-28 09:58:12 +08:00 via Android
那个…我还是纠结,100 万人名是什么情况😅查了下英文单词数量不到 20w 个…
|
74
robinlovemaggie 2020-08-28 09:59:36 +08:00
12 小时已过,估计 LZ 已经。。。
|
75
goodboy95 2020-08-28 10:04:08 +08:00 2
字典树这招还真的厉害啊,邮箱长度只算 @前面的话,很难超过 20,这样的话一个邮箱最多做 400 次运算就能匹配到人名。
现在看见这种求助帖就感觉自己做了一道 leetcode :-) |
76
Conan1412 2020-08-28 10:05:05 +08:00 via Android
楼主在补觉吗
|
77
wangkun025 2020-08-28 10:05:11 +08:00
加需求要加钱。
|
78
goodboy95 2020-08-28 10:06:05 +08:00
说错了,是 O(L^2),不过常数项是 1/2,所以一般是 200 次字典树的节点匹配
|
79
BadAngel 2020-08-28 10:17:11 +08:00 via Android
1.弄个测试环境,建个邮件名的分片索引,启 100 个 MongoDB 分片集群遍历?
2.弄个 ES ? |
80
handsomeroger 2020-08-28 10:17:36 +08:00
需求搞不定就要辞职吗?
|
81
vickchen1992 2020-08-28 10:32:00 +08:00
催更,有结果了通知我。。
|
82
cyyself 2020-08-28 10:38:21 +08:00
导出数据库然后 AC 自动机(字典树上跑 KMP ),几乎 O(n)复杂度就行。
只是 100 万英文名按照最简单的方法建立出来的 AC 自动机需要 2TB 内存,希望有足够大内存的服务器。 |
83
atwoodSoInterest 2020-08-28 10:38:44 +08:00
@xupefei ac 自动机其实不适用这个场景。email 地址是短字符串,而且在 100w 的密度下,几乎就是遍历,手写字典树查找是收益更高的做法。
|
84
pushback 2020-08-28 10:42:06 +08:00
楼主开始面试了🐎
|
85
knva 2020-08-28 10:48:07 +08:00
字典树是最好的方案.
|
86
matrix67 2020-08-28 10:59:47 +08:00
|
87
lucybenz 2020-08-28 11:01:04 +08:00
楼主带着 5 亿邮箱地址 和 100 万 人名 去找猎头了,谈的很顺利
|
88
zwwlovezzh 2020-08-28 11:13:04 +08:00
楼主已经成功入职下一家公司,正在和新同事友好的交流
|
89
GtDzx 2020-08-28 11:24:03 +08:00
|
90
Felldeadbird 2020-08-28 11:32:59 +08:00
我个人看法是,将 100 万名字,拆分成 每台机器跑 5 万个人名。 去开一推云计算服务器。 。。不过 5E 数据 迁移过去需要考量好最优办法。带宽要啊,SSD 要开足马力呀。
|
92
SelFree 2020-08-28 12:22:01 +08:00
楼主已经解决了,升职加薪,今天请假在看房子
|
93
martinsu 2020-08-28 13:17:45 +08:00 via iPhone
确定是英文人名吗?
如果是的话,英文里常用人名应该没这么多。 大量数据、有限时间,只能靠降低精准度了。所以,跑完常用名,实际需要应该已经解决绝大部分了。 可能最热 2000 个名字已经能匹配出 80%,最热 10000 个名字 90%,剩下的 99 万个名字,慢慢来吧。 (后边 99 万个名字,活多产出少,可能有些人会选择直接不要了。) 只是,你老板怎么验证结果有效性呢? |
94
atwoodSoInterest 2020-08-28 13:18:48 +08:00
@GtDzx ac 自动机其实就是在字典树上加了 kmp 算法,kmp 算法就是为了防止大量回溯,而这个场景短字符高密度的场景,几乎就是一个一个字符去匹配的,kmp 算法的优势就不能体现了。kmp 算法还是要在长字符串的场景下才会更优,因为会避免大量无效的回溯。
字典树就常规做法啊,只要能匹配到子节点就认为是匹配人名成功,如果没有匹配到子节点就换到下一个字符就行。 |
95
baoshuo 2020-08-28 13:19:20 +08:00
楼主解决了吗?或者说楼主已经找到下家了?
|
96
NeezerGu 2020-08-28 14:16:03 +08:00
如果是仅单次操作,无需多次查找。
首先注册一个 gsuite,把你这 5 亿 email 传进去。 其次,写代码实现确定单条 email 是否包含人名。 之后,将 5 亿条 email 挪到团队共享盘,不断注册 gmail 账户,开 colab,按上述单条 email 查询跑。 (当然实际情况可以是一次性取 1W 条 email 然后验证之类的,确保不要重了或者漏了就行) 印象里这种小脚本,一个账号可以开 5 个 colab 。我不确定单台电脑能开多少个这样的 gmail 而不被封号,需要你自己实测了。 总归,需要多快,只看你开了多少个 colab 就行 |
97
AmberJiang 2020-08-28 14:55:49 +08:00
所以楼主现在可好?
|
98
xupefei 2020-08-28 15:21:52 +08:00 via iPhone
@atwoodSoInterest 用字典树需要两层 for 循环,性能也不好说。可能还是 ac 自动机里带链接的字典树更快点儿。
谁有兴趣可以去实践比较一下😂 |
99
ipwx 2020-08-28 15:30:35 +08:00
建索引剪枝。一步步剪下来就行了。
比如你取固定长为 3 或者 4 个字母的片段做倒排索引。email 和人名都这么干。然后你可以直接根据人名的片段集合,去对 email 的集合做 join 。这样 join 出来,每个人名可以只和几百万甚至几万个 email 匹配,自然就快了。 |
100
ipwx 2020-08-28 15:31:24 +08:00
倒排索引根据 email 的序号升序排序。对两个排序过的 int 数组做 join 很快的,可以借助二分搜索(变形)直接跳跃着进行 join 。
|