从海量日志数据提取出某日访问次数最多的那个IP

本文的部分摘自下面的链接:
http://blog.csdn.net/v_JULY_v/article/details/6279498
海量数据处理：十道面试题与十个海量数据处理方法总结

这里只是记下题目,别人的想法. 以及我的想法.

这是我最近看到的一个传说中的面试题...

===海量日志数据，提取出某日访问百度次数最多的那个IP。
/*ME:
对问题的扩充,通过这个扩充可以更好地理解这个题目:
假定一个日志文件存储了一天之内所有对百度的访问的IP.
每一次访问都记录一个IP,并且存成单独的一行. 计算出"某日访问百度次数最多的那个IP".
这个原始的日志文件很大.
假定IP是ipv4.
*/

首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。

或者如下阐述（雪域之鹰）：
算法思想：分而治之+Hash
1.IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理；
2.可以考虑采用分而治之的思想，按照IP地址的Hash(IP)%1024值，把海量IP日志分别存储到1024个小文件中。这样，每个小文件最多包含4MB个IP地址；
3.对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址；
4.可以得到1024个小文件中的出现次数最多的IP，再依据常规的排序算法得到总体上出现次数最多的IP；

(ME:基本上对海量数据的处理都需要 先获得局部的结果, 然后综合得到最后的结果.
这个方法很粗糙,存在如下的问题:
因为有可能hash之后得到的结果是一样的,所以最后所有的记录都存放到一个小文件中. 所以这就需要hash函数的结果是均匀分布的.这是一个难点;
假设,现在假设记录能够被相对均匀地分布到各个小文件,那么小文件内如何快速排序..用普通的排序算法问题可以很好地解决.那如何最快呢?
)

===ME
每一个IPv4对应一个uint32的值,这个题目可以转化成,有一个大日志文件,每一行存着一个类型为uint32的整数, 求出现次数最多的那个整数.

假定这个文件有16G. 之所以这么假定是因为算法可能没有办法把数据一下子全部放到内存中.

我们知道基数排序是很快的, 如果我们在分割小文件时,把相邻的记录放到同一个小文件里,然后在对小文件排序的时候使用基数排序就很完美了。

32bit的数,我们可以分为[12,20]两个部分. 即概念上有4K个小文件.一个小文件中的数的高12bit的数一样(与OS的页目录一样).
这样对于一个数,我们可以很快知道它位于哪一个小文件.
这里有一个悲剧是,我们没有办法避免所有记录被放到一个小文件的命运.
(至于我们有没有必要再对20bit进行分割, 我觉得没有必要).
经过这一步,我们的数据被放到了小文件,并且他们的分布规律很好。

现在我们可以使用基数排序来对小文件排序. 对于每一个小文件中的数,可以使用该数的低20bit作为数组的下标,统计每一个数的出现次数.
我们知道每一个小文件中最多只有1M个不同的数,所以这个数组需要4MB(如果内存不大,那么在前一步的时候可以分的更小,从而创造更多的小文件.)

到这里,我们排序了所有的小文件. 那么取出每一个小文件中最大的值,然后从它们中取出最大值.


(注:我其实有点忘记了什么是 基数排序, 也许上面的基数排序应该说是计数排序)