100 台机器上海量 IP 如何查找出现频率 Top 100？

场景题

有 100 机器，每个机器的磁盘特别大，磁盘大小为 1T，但是内存大小只有 4G，现在每台机器上都产生了很多 ip 日志文件，每个文件假设有 50G，那么如果计算出这 100 太机器上访问量最多的 100 ip 呢？也就是 Top 100。

思路

其实，一开始我有往布隆过滤器那边考虑，但是布隆过滤器只能大致的判断一个 ip 是否已经存在，而不能去统计数量，不符合该场景。

那么一般这种大数据的问题，都是因为一次不能完全加载到内存，因此需要拆分，那怎么拆呢？ip 是 32 位的，也就是最多就 2³² 个， 常见的拆分方法都是 哈希：

• 把大文件通过哈希算法分配到不同的机器

• 把大文件通过哈希算法分配到不同的小文件

上面所说，一台机器的内存肯定不能把所有的 ip 全部加载进去，必须在不同机器上先 hash 区分，先看每台机器上，50G 文件，假设我们分成 100 个小文件，那么平均每个就 500M，使用 Hash 函数将所有的 ip 分流到不同的文件中。

这个时候相同的 ip 一定在相同的文件中，当然不能排除数据全部倾斜于一个文件的情况，也就是虽然 hash 了，但是由于个别 ip 或者 hash 值相同的 ip 太多了，都分到了个别文件上，那么这个时候分流后的文件依旧很大。这种情况我能想到的就是要是文件还是很大，需要再 hash，如果基本属于同一个 ip，那么这个时候就可以分批次读取，比如一次只读 1G 到内存。

在处理每个小文件时，使用 HashMap 来统计每个 ip 出现的频率，统计完成后，遍历，用最小根堆，获取出现频率最大的 100 个 ip。这个时候，每个小文件都获取到了出现频率最大的 100 个 ip，然后每个文件的 Top 100 个 ip 再进行==排序==即可（每个文件的 top100 都是不一样的，因为前面进行 hash 之后保证相同的 ip 只会落到同一个文件里）。这样就可以得到每台机器上的 Top 100。

不同机器的 Top 100 再进行 加和 并 排序,就可以得到 Top 100 的 ip。

为什么加和？ 因为不同机器上可能存在同样的 ip，前面的 hash 操作只是确保同一个机器的不同文件里面的 ip 一定不一样。

但是上面的操作有什么瑕疵么？当然有！

假设我们又两台机器，有一台机器 C1 的 top 100 的 ip 是 192.128.1.1，top 101 是 192.128.1.2,那么就可能存在另一台机器 C2 上 192.128.1.1 可能从来没有出现过，但是 192.128.1.2 却也排在 top 101,其实总数上 192.128.1.2 是超过192.128.1.1，但是很不幸的是，我们每台机器只保存了 top100，所以它在计算过程中被淘汰了，导致结果不准确。

解决方案：

先用 hash 算法，把 ip 按照 hash 值哈希到不同的机器上，保证相同的 ip 在相同的机器上，再对每个机器上的 ip 文件再 hash 成小文件，这个时候再分别统计小文件的出现频次，用最小根堆处理，不同文件的结果排序，就可以得到每台机器的 top 100，再进行不同机器之间的结果排序，就可以得到真正的 top 100。

一般而言，像这种海量数据，比如 有一个包含100亿个URL的大文件,假设每个URL占用64B,请找出其中所有重复的URL. ,内存一次性读不下，只能通过 ==分而治之==。

hash 到不同的小文件，一直这样划分，直到满足资源的限制：

• hash 分流

• hash 表统计

• 最小堆/外部排序

如果允许一定的误差存在，其实还可以考虑使用布隆过滤器（Bloom filter）,将 URL 挨个映射到每一个 Bit，在此之前判断该位置是否映射过，来证明它是否已经存在。（有一定的概率出现误判，因为其他的URL也可能会映射到同一位置）

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

剑指Offer全部题解PDF

2020年我写了什么？

开源编程笔记