乐趣区

关于java:100台机器上海量IP如何查找出现频率-Top-100

场景题

有 100 机器,每个机器的磁盘特地大,磁盘大小为 1T,然而内存大小只有 4G,当初每台机器上都产生了很多 ip 日志文件,每个文件假如有 50G,那么如果计算出这 100 太机器上访问量最多的 100 ip 呢?也就是 Top 100。

思路

其实,一开始我有往布隆过滤器那边思考,然而布隆过滤器只能大抵的判断一个 ip 是否曾经存在,而不能去统计数量,不合乎该场景。

那么个别这种大数据的问题,都是因为一次不能齐全加载到内存,因而须要拆分,那怎么拆呢?ip 是 32 位的,也就是最多就 232 个,常见的拆分办法都是 哈希

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

下面所说,一台机器的内存必定不能把所有的 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, 那么就可能存在另一台机器 C2192.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 源码解析JDBCMybatisSpringredis 分布式 剑指 OfferLeetCode等,认真写好每一篇文章,不喜爱题目党,不喜爱花里胡哨,大多写系列文章,不能保障我写的都完全正确,然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处,还望斧正。

剑指 Offer 全副题解 PDF

2020 年我写了什么?

开源编程笔记

退出移动版