超大文件（1TB）统计访问次数最多的来源IP及访问次数

题目解读

1. 文件格式：访问时间,来源IP,响应结果,响应耗时

2. 文件大小：超大规模，TB数量级

解题思路

首先，数据量过大，通过内存计算肯定是不可行的。

考虑采用分治，将大文件切割成小文件，再对小文件分析，找出访问次数最多的，此时将问题转化为：切割小文件算法

具体思路如下：

将1T的文件按照IP的高8位（代码是按照高8位实现的，ipv4的高位地址不均匀，按照低8位>比较合理）分隔成2^8份。每一份写入到文件名为"tmp_{高8位地址}"的文件中，文件中的数据为低24位的整型字符串（踢出了高8位，以方便用int类型表示）。 开始顺序处理每个"tmp_{高8位地址}"文件： 1. 申请一块2^24大小的int内存块（arr） 2. 初始化内存块为0值 3. 读取每一行数据，转换成整型值后做为下标i，将arr[i] ，表示出现了一次 4. 重复3操作，一直到处理完整个文件为止 5. 遍历arr，找出最大值的下标maxCountIndex 6. 遍历arr，找出所有与最大值相同的值，将ip和出现次数写入到maxIpCountMap（用于存储每个文件中出现次数最多的IP地址及出现次数）中 7. 重复2-6步骤，一直到所有切割文件处理完毕 8. 遍历一遍maxIpCountMap，找出IP最大次数max（所有IP中，出现最多的次数） 9. 重新遍历一遍maxIpCountMap，将所有出现次数等于max的IP和次数打印出来

上代码

import java.io.*;import java.net.URISyntaxException;import java.util.*;import java.util.regex.Matcher;import java.util.regex.Pattern;/** * 所有用到的辅助数据： * 1. 2^8个切割文件 * 2. 2^24个整数的数组，大小为64M * 3. 2^8个文件对象，用于加快查询 * 4. 用于存储每个文件中最大值的HashMap（没有考虑极端情况，如果1T的文件中所有IP出现次数相同，这个HashMap就太大了，方案得重新调整） * * Created by ronghantao on 2019/3/4. */public class TopN {    private static int MASK_TOP8 = 0XFF000000; //获取高8位的掩码    private static int MAST_LEFT24 = 0X00FFFFFF; //获取低24位掩码    //ip地址的pattern    private static String PATTERN_FILTER = "(2(5[0-5]{1}|[0-4]\\d{1})|[0-1]?\\d{1,2})(\\.(2(5[0-5]{1}|[0-4]\\d{1})|[0-1]?\\d{1,2})){3}";    //用于存储文件，再次读取的时候，用这里的数据    private File[] files = new File[0xFF];    //每个分隔文件中，数值最大的存储于此    private Map<String, Integer> maxIpCountMap = new HashMap<>();    private static Pattern r = Pattern.compile(PATTERN_FILTER);    /**     * 串接整个流程     */    public void printTopCountList(String fileName) throws IOException, URISyntaxException {        //开始切分文件        this.splitFile(fileName);        //针对每个文件，进行计算了，找出每个文件中数量最大的IP        this.countTopN();        //开始找出数量最多的ip列表        if (this.maxIpCountMap.size() == 0) {            //空的            System.out.println("empty list.");            return;        }        int max = 0;        for (String k : this.maxIpCountMap.keySet()) {            if (this.maxIpCountMap.get(k) > max) {                max = this.maxIpCountMap.get(k);            }        }        //开始打印所有的最大值列表了        for (String k : this.maxIpCountMap.keySet()) {            if (this.maxIpCountMap.get(k) == max) {                System.out.println("ip: "   k   ", count: "   this.maxIpCountMap.get(k));            }        }    }    /**     * 计算top1的IP地址     */    public void countTopN() throws IOException {        int[] arr = new int[0x00FFFFFF];        for (int i = 0; i < 0xFF; i  ) {            //先初始化buffer，都初始化成0            for (int j = 0; j < arr.length; j  ) {                arr[j] = 0;            }            //开始处理文件            File toProcessFile = this.files[i];            BufferedReader r = new BufferedReader(new InputStreamReader(new FileInputStream(toProcessFile)));            try {                String line;                boolean flag = false; //标识文件是否为空                while ((line = r.readLine()) != null) {                    //读到数据了，开始处理                    arr[Integer.valueOf(line)]  ; //直接将对应的下标 1即可                    flag = true;//有数据了                }                if (flag == false){                    continue; //没有读到数据，继续处理其他文件                }                //处理完后，找到本文件中最大的值的下标                int maxCountIndex = 0;                for (int j = 1; j < arr.length; j  ) {                    if (arr[j] > arr[maxCountIndex]) {                        maxCountIndex = j;                    }                }                //然后找出所有与此最大值相同的ip列表，写入到treeMap中                for (int j = 0; j < arr.length; j  ) {                    if (arr[j] == arr[maxCountIndex]) {                        //写入到treeMap，需要做IP转换                        this.maxIpCountMap.put(this.longToIp(((long) j)   (((long) (i   1) << 24))), arr[j]);                    }                }            } finally {                r.close();            }        }    }    public void splitFile(String fileName) throws URISyntaxException, IOException {        //todo 文件合法性校验        InputStreamReader inputStreamReader = new InputStreamReader(TopN.class.getClassLoader().getResourceAsStream(fileName));        BufferedReader reader = new BufferedReader(inputStreamReader);        BufferedWriter[] writers = new BufferedWriter[0xFF]; //保存每个文件是在什么位置，使用writer，不需要每次都打开了        for (int i = 0; i < 0xFF; i  ) {            File f = new File("tmp_"   Integer.toHexString(i 1).toUpperCase());            writers[i] = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(f)));            this.files[i] = f;        }        try {            String line;            //一行一行的读文件，然后找到第一个匹配的ip地址            while ((line = reader.readLine()) != null) {                Matcher m = r.matcher(line);                if (!m.find()) {                    System.out.println(line   " not match!");                    continue;                }                String ipString = m.group();                //将大文件按照高8位的规则进行分片，存储到分片文件中                //获取IP的分片信息                long ipLong = this.ipToLong(ipString);                int fileIndex = this.getTop8Int(ipLong) - 1; //下标从0开始，需要-1操作                BufferedWriter w = writers[fileIndex];                //将ip剩余的24位整型值写入到文件中                w.write(String.valueOf(this.getLeft24Int(ipLong)) "\n");            }        } finally {            //关闭所有文件            for (int i = 0; i < 0xFF; i  ) {                if (writers[i] != null) {                    try {                        writers[i].close();                    } catch (IOException e) {                        //todo nothing                    }                }            }            if (reader != null) {                reader.close();            }            if (inputStreamReader != null) {                inputStreamReader.close();            }        }    }    public int getLeft24Int(long ip) {        return (int) (ip & MAST_LEFT24);    }    public int getTop8Int(long ip) {        return (int) ((ip & MASK_TOP8) >> 24);    }    public long ipToLong(String ipStr) {        long result = 0;        String[] ipAddressInArray = ipStr.split("\\.");        for (int i = 3; i >= 0; i--) {            long ip = Long.parseLong(ipAddressInArray[3 - i]);            result |= ip << (i * 8);        }        return result;    }    /**     * long转换成ip地址格式     *     * @param ip ip的long表示     * @return 点分隔ip字符串     */    public String longToIp(long ip) {        return ((ip >> 24) & 0xFF)   "."                  ((ip >> 16) & 0xFF)   "."                  ((ip >> 8) & 0xFF)   "."                  (ip & 0xFF);    }}

遗留问题

对于以上算法，如果1TB的文件中，访问量最高的IP不多，不会出现问题，否则，也会占用较大的内存。

来源：http://www.icode9.com/content-4-142451.html