HashFile

Seeking top IP frequency in 100 GB URL files or even more files.

问题描述

100GB url 文件，使用 1GB 内存计算出现次数 top 100 的 url 和出现的次数

解决思路

1. 从内存的限制的角度来思考，把所有的文件一次性的计算出来显然是不合理的，其次 Linux 32 位系统显然是不能支持这么大的内存。即可以采用 hash 散列和分而治之的方法，将相同的 url 哈希到同一个文件。基于内存限制可以使用非线性的存储结构来存储 url ，进而来统计每个 url 的出现次数，并且维护一个小根堆记录 top 100 url
2. 从性能的角度来思考，统计 url 的性能瓶颈来自磁盘 io，如何充分的利用或者解决 磁盘 io 将是性能最关键的问题。其次排序算法的选择，以及是否采用并行的方式充分利用磁盘 io 也是影响因素

Corner case

1. url 不合法
2. url 极端异常导致统计的异常，如: url 全相同，url 全不相同

扩展与思考

1. 假设数据集更加庞大，又应该采取什么样的策略是最优的
2. 思考分布式应该采取什么样的方案，分布式的解决方式是不是对效率的提升是显著的
3. 如何从各个方面逐步的逼近最优的效率呢