ip地址开发场景问题

        这种问题一般是出现在我们的项目日志中，可能想去收集某一个时间段内，或者说时某一个时间点的ip地址，或者说是想从大量数据中，选出ip地址出现次数最多的ip。大概是分为这几个问题。

1.亿万级数据中如何快速取出某一天的ip地址。

        这里面提到了如何快速取出某一天的ip地址，那么这里面我们是不去考虑缓存redis，或者说是数据库性能包括读写分离，主从集群这样的设计的。那么如何能够在这个基础之上，去进行优化。

        因此我们需要从数据结构的角度去入手，快速定位的结构，肯定首先想到的就是hashmap，那么这个节点的key和value怎么设计？这里就可以将key设定为某一天，然后节点就是一个链表，让他这样定位进行存储就可以了。

2.亿万级数据中如何快速取出某一个时间段的ip地址。

        当遇到这个问题的时候，因为是范围查询，我的第一个想法就是b+树，但是这个b+树无论是在代码里实现起来还是说维护起来都是成本很高，并且很占内存。因此我第二个想法是跳表skiplist，但是对于说是利用原生态的代码进行实现，还是也有一定的成本。所以我们把思路回到第一个问题，能否直接将map节点的key改成一个范围值，对应的范围全部映射到这个节点里面，这样还能提高查询效率，不免为一个很好的角度。

3.亿万级数据中，内存有限的情况下，如何快速统计出ip出现次数最多的ip地址。

        当遇到这个问题的时候，我的第一反应是这类似于topk问题。首先明确的一点，想要快速统计，那么就是外边redis这样的缓存。那么这里是直接利用操作系统的内存，应该如何设计？可能第一个想法就是处理top几？一般就是采用堆的流式计算，外加多线程去提高效率。但是有个前提就是，内存是不够的，无法一次性去放入很多数据。因此我们需要采用外部设备，例如硬盘来相互配合。所以，我们不得不将这整体的数据先放到硬盘里面，再将硬盘里的数据读入到缓存里面进行计算。

        好了大概思路有了，那么问题来了？我们把数据分散存储在硬盘中，bane输入内存的数据是什么呢，输入之后又是如何进行计算的，输出的数据是什么，输出的数据如何进行存储，最后的数据又如何进行汇总统计，其实这都是问题。

        如果说，我们的数据可以在内存里面全部存放，那ok，直接流式计算，输入数据，如果最小堆没有满，如果堆里没有该数据，则放入，如果堆满了，就将该数据的计数加1，如果当前元素计数大于堆顶元素，则堆顶元素移除，当前元素放进去。

        好了，那么现在我们硬盘里的数据已经分好了，输入内存进行计算，输出的数据是排好序的，我们再对排好序的前几行数据进行汇总，再次形成多个排好序的文件，重复输入内存计算的操作，那么最后得出来的那个文件是不是就是出现次数最多的呢？

        其实答案不是的，因为我们忘记考虑了一点，就是假如A地址有100个，B地址有20个，如果分为10个文件，其中A被平均的分配到10个文件里面，但是B却集中在了其中的一个里面，结果就会出现，其中1个A文件的ip地址在计算次数的过程中会被过滤，那么如果出现类似B的C，D等地址，最终的统计结果将会导致不正确。所以，我们在对文件进行初次分片的时候，就应该将相同的ip地址放到一起，那么如何做到呢？第一个想法就是对ip地址进行模运算就可以了，这样就可以做到相同的ip地址放到一个文件里，最后再进行堆的计算就可以了。