100 亿条 URL 去重

假定给你 100 亿条 URL，如何去除重复文档呢？这里重复的意思是指 URL 一样。

首先，我们估算下 100 亿条数据的体积。假设每个 URL 有 100 个字符，每个字符使用 2 个字节，那么存储这 100 亿条数据，需要 2T 的空间。我们或许没办法把所有的数据都放到内存里面。

我们先做一个简单的题目，假设 URL 条数很少，内存能放下，该如何去重呢。我们可以建立一个哈希表，把 URL 做哈希运算放到这个哈希表中。如果key，哈希之后的值，已经在哈希表中了，那么这条 URL 已经存在了。如果考虑到哈希碰撞的话，比较下两个字符串就好，也不是什么大事。另外可选的方案是排序去重，这花费的时间更多，而且没有太多额外的好处。

回到题目，2T 的数据，怎么办呢？

方案1

假设所有数据都在一台机器上。首先，我们可以把这 2T 的数据划分成 2000 块，这样每块就是 1G 的大小了。一个容易的划分方式是 Hash(URL) % 2000，这样，URL 一样的话肯定会被放入同一个文件中。从概率上说，不会每块都是 1G 大小，如果是随机数据的话，假定满足正态分布或者泊松分布，超过 2G 的概率就很小了。再说，现代机器能够使用的内存很大，这都不是事。这样，我们每块都能放入内存中了，采用之前说的方案进行去重。

方案2

假设把数据在多台机器上。处理的方式基本上是一致的。放到某个文件变成了发送 URL 到某台机器上。

多台机器的优势：速度快，2000 台机器可以并行计算。

多台机器的劣势：我们要依赖于不同的机器的稳定性，如果数据更大，机器也会更多，处理错误也更复杂。也就是说，增加了整个系统的复杂性。