100G的ip文件找出最多的100个ip

参考

• 教你如何迅速秒杀99%的海量数据处理面试题
• 计海量数据中访问最多的IP (略有扩展)

问题

100G大小的ip文件，每行都是一条IP访问记录。计算器中重复最多的IP，即访问最多的100个IP。

单文件直接处理可行吗？

首先，鉴于现在64位os的机器内存最多也就64G，我们不可能把整个100G的文件读入内存再计算。 我们得先分析一下数据源: ip这个东西，先假设是ipv4吧。

• IPv4的话，一共2^32个ip，即4G个，每个IP占用4个字节，加上每个计数所占用8个字节(long型),则需要至少 4G * (4+8)= 48G内存。
• IPv4中一些IP保留给内网以及广播网络(IGMP?), 所以实际总数小于4G个,其实是有3,706,452,992个,参考：http://stackoverflow.com/questions/2437169/what-is-the-total-amount-of-public-ipv4-addresses。 然后，就会占据3,706,452,992 * (12) / 1024/1024/1024 ≈ 41.4228G。

假如你的电脑有64G内存，我们是可以这样做的：

1. 为这个100G的文件开启一个流。
2. 每个ip在处理时都转化为一个int型变量。
3. 在内存里维护一个hashmap<int, long>，每个key都对应不同的ip(int型)，一个key对应的value就是这个ip的出现次数(long型)(注意，在这里，我们已经默认了一个ip出现的最大次数不超过long的最大值)。
4. 用这个流顺序读取文件，每读入一行记录，其ip对应的value数+1。

分割文件处理(2个)

可是，如果你的电脑只有32G内存呢？你没法放下所有不同的ip，因为ip加上其计数，占用空间有42G以上。为了方便计算，我们先假设所有ip是2^32个，且处理这些ip所维持的hashmap总共占48G吧。

其实把所有ip分为两组，ip%2==0和ip%2==1。 这样，维持每组ip对应的hashmap最多需要48G/2=24G。根据这个规则，我们可以把原文件拆分成两个小文件，再分别分析。具体做法如下：

1. 开始工作前，我们准备两个空文件: "0.txt"和"1.txt"。再开启100G文件的输入流，进行读取。
2. 每读取一行数据，将ip转为int型变量，再余2
   1. 如果余2结果为0，则将该行数据写入"0.txt"
   2. 如果余2结果为1，则将该行数据写入"1.txt"
3. 最后，所有ip记录被分散到两个小文件中。

对于这两个文件，其特征如下：

1. 同一个ip的所有记录都在一个文件内
2. 每个文件所覆盖的ip最多有2^32 / 2 = 2^31个，处理这些ip所维持的hashmap占48G / 2 = 24G。

所以，我们只需对每个txt分别处理一遍，得到每个文件的前100名ip，写到另一个文件里。(处理每个文件最多需要24G内存，而我们有32G内存。) 处理完两个文件后，这个文件会保存100*2=200条记录，再排序找出其频次最多的100个即可。

假如内存更少呢？

• 假如我们只有更少内存，比如16G，怎么办？分成4个文件即可，处理每个文件最多需要12G内存。
• 如果只有8G内存，那就再分，分成8个文件。
• 如果是4G、2G、1G...那就以此类推，分成16个、32个、64个文件。只要分多几份，总会够用的。也正是这样，你会看到很多人的答案说，分成1024份，因为这样你的内存总会够用了。

其它讨论

• 上文讨论的都是ipv4，如果是ipv6，虽然我没计算过，但分成1024份的时候，应该肯定够用了。
• 不过，依然要注意一个前提，即我们上面的讨论，都假设了每个ip最多出现的次数不超过long型最大值。如果超过的话，就得用更大的容量的变量来保存。不管怎样，你必须事先保证一个ip的最多出现次数，不超过其变量的类型的最大值。

纠正其它文章

最后，要在此纠正其它文章的一个观点。其它文章认为，"将100G的文件按照余100的结果，分成100份，每个文件就是1G左右，所以1G的内存够用"。这个理由是错误的，原因有二：

1. 100G在分割后，不一定刚好都是1G左右。有可能有的文件有十几G，而别的文件比较小。就算分割再多次，也有可能很多ip记录都集中在一个文件里，导致该文件大小超过了内存。
2. 我们读取文章时，并不是要把整个文件放入内存；而是读取流，一行一行地读取并处理。所以我们要计算的，是维持所有不同的ip可能最多需要的容量大小，而不是文件本身的大小。

所以，我们是无法确定分割后，一个文件的大小的。除非基于一个前提：ip的分布是较为均匀的，分割后的文件大小差别不大。否则，不管分割几次，一个文件都可能非常大。 那么，用本文的做法，即使一个文件较大，也可以处理，但这个做法得基于另一个前提：一个ip的出现次数不超过其变量保存类型的最大值。