求救！限时 12 小时！ mongodb 存了 5 亿条 email，现有 100 万英文人名，想把包含人名的所有 email 找到，怎么办

[0x0208v0]

如题：
马上下班了，突然来了一个需求，

mongodb 存了 5 亿条 email，现有 100 万英文人名，想把包含人名的所有 email 找到，怎么办，

我想破脑子都没想明白应该怎么做，感觉这个除了遍历没有其他方法了，

如果遍历的话，是 O(mn)，也就是 100 百万 * 5 亿次匹配，这也太慢了，12 个小时也搞不完，求大佬帮忙想想办法。

多谢各位回答，补充一下问题，如果人名是 tom，email 是 [email protected] ，我想在数据库匹配出 该条 email 的数据

终于，跟老板说了一下自己做不了以后，就放弃做这个了。估计也会在老板脑海中留下能力不行的标签

[0x0208v0]

这种需求能实现吗，如果不能的话我就辞职了 :( 好难过，这数据量已经让我所有办法无效了

[leido]

email 根据人名排序, 然后二分查找.

[xupefei]

多开几台机器分块跑呗。mongo 那边只读，性能瓶颈就是那台机器的硬盘和网络带宽。

同时匹配所有人名用 Aho Corasick 算法。

[a719114136]

人名存字典

[AX5N]

建立索引+多线程？

[br00k]

有索引直接查库效率应该还可以。100w 开多个线程应该也挺快的。

[a719114136]

最好的方法还是临时起个数据库，人名都放进去，这样方便多台机器同时跑

[qq316107934]

每一封 email 不长的话分词然后用布隆过滤器，效率很高的，扫一遍就行。

[0x0208v0]

不行啊，如果人名是 tom，email 是 [email protected] 那么人名存字典是不行的

[qq316107934]

上面说要建索引的，我理解这是说正文包含指定人名的吧，建立全文索引太慢了。

[qq316107934]

@v2exblog #9 楼主得再说清楚点，是在哪个字段寻找人名，正文还是发件人还是 email，可以精确匹配，左匹配，可以分词，还是只能正则模糊匹配。

[0x0208v0]

在 email 字段寻找人名

[rrfeng]

有索引吗？

没有的话 100w 人名先 hash 一下，然后遍历 5 亿数据，对比只要 O(1)，也就是 5 亿次。
100w 人名也用不了太多存储

[heiheidewo]

先把 100 万英文人名建立好 AC 自动机，然后扫一遍 5 亿 email 用不了多久吧？

[matrix1010]

当然能实现，也不要 100 万 x5 亿次，但如果公司真限定你一个人 12 小时做完那你还是辞职吧

[0x0208v0]

@matrix1010 哭了，太难了

[whahuzhihao]

放到 es 里面搜？空间换时间

[loading]

只有两个字段吗？
排序然后二分不已经很快了吗？

[pcbl]

先随机给每一个邮箱找些出来交差，老板要是说数据不对的话，怼他让他 24 小时内核对下试试。。

[Mutoo]

100 万英文人名 先折分去重一下，不至于有这么多。英文重名率挺高的。

[atwoodSoInterest]

其实只能匹配，楼上说的二分法，其实没有作用，因为人名是可以包含在中间的。

我觉得思路应该放在优化上，适当的剪枝或许能有大作用，比如在写匹配算法的时候，遇到 @就停止匹配，一下就减少了差不多一半的匹配次数。你多看看数据，应该是有一些数据是可以很轻易就去掉的，比如 qq 邮箱全数字这种就直接去掉，一下子也能剪去不少。

[atwoodSoInterest]

人名可以做成字典树，在匹配上也能快不少

[qq316107934]

@atwoodSoInterest #21 12h，感觉代码写不完啊，有限时间内最快捷的方案是洗数据+ 堆机器查，公司要是有 HDFS 的话放里面用 Hive 查。

[0x0208v0]

@atwoodSoInterest 谢谢大佬！我准备用字典树+减树法试试

[iseki]

建 AC 自动机然后遍历全部数据是唯一方案吧…优化也只能从其他角度上走比如加机器什么的…

[murmur]

ac 自动机这数据量也有点巨大
什么需求能有五亿邮件

[iseki]

啊…人名是有点多，内存可能装不下…那…加机器？

[iseki]

我觉得人名库编译成自动机装得下没问题

[laminux29]

估算了一下，一台 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 类线，等等，这些都是坑。

我咋感觉，这需求，有点像是公司恶意辞退？

[iseki]

额，难道是 12 小时内让你搞定？我还以为是单次任务最多跑 12 小时 emmm 十二小时内写代码测试跑完基本不太可能吧 emmm

[my1103]

下班没（手动狗头）

[lizytalk]

首先扫描一遍所有邮件建立一个 k-tuple （例如序列 abcd，它的所有 2-tuple 就是 ab,bc,cd ）的索引。然后对于每一个人名，只需要在有共同的 k-tuple 的那些邮件里用字符串匹配算法就行了（因为如果名字在邮件里出现了，必然会有共同的 k-tuple ），这样可以过滤掉很多邮件。
k 的选择，可以多选择几个，对不同长度的名字应用不同的 k 。

[fushall]

这需求，字典树都够呛能在一台有限内存的机器上跑出来。就算能，也得代码也得非常好，要是用 Python 那种语言，估计内存就爆炸了。12 小时之内没希望能完成，看得出来，这种提问，应该是你自己一个人在硬着头皮搞。明天直接说一下吧，这东西搞不来，楼上 有位大神都帮你分析了，你品你细品

[oneisall8955]

额，想起这个月初那天通宵搞对接第三方接口+上线，楼主看着办吧🐶

[0bit]

如果允许损失一定精度，可以考虑使用 Bloom Filter （布隆过滤器）

1. 先把名字规整化，全部小写，去除多余字符，每个名字一个字符串
2. 创建一个 BloomFilter，写入全部的名字规则
3. 遍历 MongoDB 的记录，判断是否在 BloomFilter 中，找出符合条件的

PS：如果公司故意恶心你，还不如直接走了算了。

[iseki]

啊，我傻了，我算错了，要是字典树写得不够好 100G 内存真是够呛塞得下

[nuk]

hyperscan ？

[HunterPan]

5 亿数据按前缀打到数据库的分片上，10 个分片就够了，然后 100w 查询 就这样

[heiheidewo]

@iseki 想啥呢，100w 个英文名建 AC 自动机，怎么要 100G 内存，英文名全部转成小写，撑死 1G 内存

[imdong]

非专科，算法渣，我想的办法是：

把邮件名中按字母建立索引，然后用人名去对应的索引中查找（假设名字中没有数字和符号）。

比如：
[email protected] 同时进入：a t h o m 6 这几个的索引。

如果想加速，就每两两三三再建一层索引：

ha ah at to om 这样。

最后查询的话，拿 tom 去命中 t o m 或者 to om 中的数据。

然后再去检查，对比匹配的数量应该会少很多。

[iseki]

@heiheidewo 我傻了，计算时 0 写多了

[pcbl]

看到很多楼层完全就不审题就开干了，好奇工作中也是这样的吗

[raaaaaar]

别讲了，楼主已经被开除了

[iseki]

我感觉自己逐渐清醒了一点…100w 个人名…真的没有重复吗😅

[yuang]

收藏了，以备不时之需

[chihiro2014]

布隆过滤器了解下？

[swulling]

其实就是五亿个字符串和 100 万字符串做子串匹配。

如果是精确匹配，将 100 万字符串放 hash 表比如 python 的字典，然后对五亿字符串遍历一次，每个字符串查看是否在 hash 表就行。时间复杂度 O （ N ）。还是很快的，内存占用也就 1G 左右吧。

但是要做模糊匹配就麻烦了，上面的 bloomfilter 之类的办法全都不能用。

[swulling]

其实有大集群直接 grep 都行，测试了下，对一个邮件地址，通过 grep -F 从 100 万个子串中查找匹配，大约耗时 1s 。那么就是五亿秒总计算时间。

假如有 2000 台机器，每台机器 20 核 20 并发，那么就是 12500s，也就几个小时而已。

[pcbl]

@swulling 拥有 2000 台 20 核机器的老板一般不会提出这种需求出来

[Mangozhen]

@pcbl 思路清奇而有效。哈哈！

[xupefei]

讨论一天了，我来总结一下吧。首先，楼主的问题是是 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 从来没变过。

[levelworm]

问题你怎么确定是人名？ tom 也可以不是人名啊。。。比如说 tome666，这算人名不算？

[levelworm]

没用过 mongodb，如果是正常的数据库 join 可以么。。。没试过这么大的数据。。。有些数据库 join 规则可以写的比较复杂

[shakoon]

12 小时已经过去了，楼主凉了没？

[yngzij]

楼主估计已经辞职了
:dog

[IMCA1024]

这有点为难，钱没给够
凭什么 12 小时内出结果

[yuanse]

楼主辞职了吗🌚

[ccppgo]

楼主人还好吗?

[murmur]

楼主估计正在办手续

[xuanbg]

老板估计已经放弃了。

[Visitor233]

楼主昨天下班了吗？

[Geekerstar]

楼主凉了吗

[p1gd0g]

哈哈哈哈，楼上你们够了。

[vone]

楼主下家准备去哪里。

[itskingname]

不要被 MongoDB 这个要求给限制了。5 亿邮箱没多大。全部拉下来，放在一个文本文件里面。然后用 shell 命令执行 grep 去查询名字，查询结果 > 文件就好了。2 个小时搞定。

[qingxiangcool]

楼主在讨论 N+1 了吗? @xupefei 51 楼整理的不错, 厉害了.

[xmmmm]

家里空调舒服吗

[LuciferGo]

@pcbl 当然是这样的啦（手动狗头

[mmrx]

14h 39m ago 了...想念楼主

[nooper]

pandas 可以搞定，向量内存计算，可以协同 GPU.速度应该很快

[SbloodyS]

楼主还好吗

[kkjinping]

加班赔偿有吗

[iseki]

那个…我还是纠结，100 万人名是什么情况😅查了下英文单词数量不到 20w 个…

[robinlovemaggie]

12 小时已过，估计 LZ 已经。。。

[goodboy95]

字典树这招还真的厉害啊，邮箱长度只算 @前面的话，很难超过 20，这样的话一个邮箱最多做 400 次运算就能匹配到人名。
现在看见这种求助帖就感觉自己做了一道 leetcode :-)

[Conan1412]

楼主在补觉吗

[wangkun025]

加需求要加钱。

[goodboy95]

说错了，是 O(L^2)，不过常数项是 1/2，所以一般是 200 次字典树的节点匹配

[BadAngel]

1.弄个测试环境，建个邮件名的分片索引，启 100 个 MongoDB 分片集群遍历？
2.弄个 ES ？

[handsomeroger]

需求搞不定就要辞职吗？

[vickchen1992]

催更，有结果了通知我。。

[cyyself]

导出数据库然后 AC 自动机（字典树上跑 KMP ），几乎 O(n)复杂度就行。

只是 100 万英文名按照最简单的方法建立出来的 AC 自动机需要 2TB 内存，希望有足够大内存的服务器。

[atwoodSoInterest]

@xupefei ac 自动机其实不适用这个场景。email 地址是短字符串，而且在 100w 的密度下，几乎就是遍历，手写字典树查找是收益更高的做法。

[pushback]

楼主开始面试了🐎

[knva]

字典树是最好的方案.

[matrix67]

@xupefei #51

这个是不是和这个比较像 https://v2ex.com/t/125941 42 楼也有个类似的。

[lucybenz]

楼主带着 5 亿邮箱地址 和 100 万 人名 去找猎头了，谈的很顺利

[zwwlovezzh]

楼主已经成功入职下一家公司，正在和新同事友好的交流

[GtDzx]

@cyyself 为什么要 2TB 内存？ 我算的顶多几百 MB 就够了。
@atwoodSoInterest 我觉得这是个 AC 自动机的典型场景吧。字典树怎么搞？

[Felldeadbird]

我个人看法是，将 100 万名字，拆分成 每台机器跑 5 万个人名。 去开一推云计算服务器。 。。不过 5E 数据 迁移过去需要考量好最优办法。带宽要啊，SSD 要开足马力呀。

[gaogao321]

@vone 楼主，新公司怎么样？呆的还习惯吗？

[SelFree]

楼主已经解决了，升职加薪，今天请假在看房子

[martinsu]

确定是英文人名吗？
如果是的话，英文里常用人名应该没这么多。
大量数据、有限时间，只能靠降低精准度了。所以，跑完常用名，实际需要应该已经解决绝大部分了。

可能最热 2000 个名字已经能匹配出 80%，最热 10000 个名字 90%，剩下的 99 万个名字，慢慢来吧。

（后边 99 万个名字，活多产出少，可能有些人会选择直接不要了。）

只是，你老板怎么验证结果有效性呢？

[atwoodSoInterest]

@GtDzx ac 自动机其实就是在字典树上加了 kmp 算法，kmp 算法就是为了防止大量回溯，而这个场景短字符高密度的场景，几乎就是一个一个字符去匹配的，kmp 算法的优势就不能体现了。kmp 算法还是要在长字符串的场景下才会更优，因为会避免大量无效的回溯。
字典树就常规做法啊，只要能匹配到子节点就认为是匹配人名成功，如果没有匹配到子节点就换到下一个字符就行。

[baoshuo]

楼主解决了吗？或者说楼主已经找到下家了？

[NeezerGu]

如果是仅单次操作，无需多次查找。

首先注册一个 gsuite，把你这 5 亿 email 传进去。

其次，写代码实现确定单条 email 是否包含人名。

之后，将 5 亿条 email 挪到团队共享盘，不断注册 gmail 账户，开 colab，按上述单条 email 查询跑。
（当然实际情况可以是一次性取 1W 条 email 然后验证之类的，确保不要重了或者漏了就行）

印象里这种小脚本，一个账号可以开 5 个 colab 。我不确定单台电脑能开多少个这样的 gmail 而不被封号，需要你自己实测了。
总归，需要多快，只看你开了多少个 colab 就行

[AmberJiang]

所以楼主现在可好？

[xupefei]

@atwoodSoInterest 用字典树需要两层 for 循环，性能也不好说。可能还是 ac 自动机里带链接的字典树更快点儿。
谁有兴趣可以去实践比较一下😂

[ipwx]

建索引剪枝。一步步剪下来就行了。

比如你取固定长为 3 或者 4 个字母的片段做倒排索引。email 和人名都这么干。然后你可以直接根据人名的片段集合，去对 email 的集合做 join 。这样 join 出来，每个人名可以只和几百万甚至几万个 email 匹配，自然就快了。

[ipwx]

倒排索引根据 email 的序号升序排序。对两个排序过的 int 数组做 join 很快的，可以借助二分搜索（变形）直接跳跃着进行 join 。