海量日志数据提取某日访问百度次数最多的那个IP的Java实现
海量日志数据提取某日访问百度次数最多的那个IP的Java实现
前几天在网上看到july的一篇文章《教你如何迅速秒杀掉:99%的海量数据处理面试题》,里面说到百度的一个面试题目,题目如下:
海量日志数据,提取出某日访问百度次数最多的那个IP。
july里面的分析如下。
1、 分而治之/hash映射:针对数据太大,内存受限,只能是:把大文件化成(取模映射)小文件,即16字方针:大而化小,各个击破,缩小规模,逐个解决
2、 hash统计:当大文件转化了小文件,那么我们便可以采用常规的hash_map(ip,value)来进行频率统计。
3、 堆/快速排序:统计完了之后,便进行排序(可采取堆排序),得到次数最多的IP。
我的分析:
1、 见july的1st.
2、 见july的2nd.
3、 不用排序,直接在统计的时候,计算出次数最多的IP:在第2步的时候,求出ip的次数,实际上呢,次数最大的那个只可能是一个值,因此在计算每个IP次数的时候,与这个最大值作比较,计算完即可知道最大值的IP是….
1 机器配置:
CPU:I3-2330M 2.20GHZ
MEM:4G(3.16G可用)
OS:win7 32位
2 生成海量数据的大文件:2.1 总数据为1亿个IP数据,生成规则:以10.开头,其他是0-255的随机数。
/** * 生成大文件 * @param ipFile * @param numberOfLine */public void gernBigFile(File ipFile,long numberOfLine){BufferedWriter bw = null;FileWriter fw = null;long startTime = System.currentTimeMillis();try{fw = new FileWriter(ipFile,true);bw = new BufferedWriter(fw);SecureRandom random = new SecureRandom();for (int i = 0; i < numberOfLine; i++) {bw.write("10."+random.nextInt(255)+"."+random.nextInt(255)+"."+random.nextInt(255)+"\n");if((i+1) % 1000 == 0){bw.flush();}}bw.flush();long endTime = System.currentTimeMillis();System.err.println(DateUtil.convertMillsToTime(endTime - startTime));}catch (Exception e) {e.printStackTrace();}finally{try{if(fw != null){fw.close();}}catch (Exception e) {e.printStackTrace();}try{if(bw != null){bw.close();}}catch (Exception e) {e.printStackTrace();}}}
/* * 1、第一次生成1亿(实际上最多为16581375)的ip地址,需要时间为3分多钟不到4分钟。 */TooMuchIpFile tooMuchIpFile = new TooMuchIpFile();File ipFile = new File("e:/ipAddr.txt");try {ipFile.createNewFile();} catch (IOException e) {e.printStackTrace();}tooMuchIpFile.gernBigFile(ipFile, 100000000);
2.2 运行结果:
生成1亿行的Ip地址,大约耗时:3分多钟,大小1.27 GB (1,370,587,382字节)
3 分割大文件,
根据july的分析,取每个IP的hashCode,与1000取模,把IP散列到不同的文件中去。
3.1 第一种方法:
一边取每个IP的散列值,再模1000,得到一个值,然后写到此值对应的文件中去。大约耗时超过2个多小时,实在是太慢了,没跑完就直接断掉了。
/** * 大文件分割为小文件 * @param ipFile * @param numberOfFile */public void splitFile(File ipFile,int numberOfFile){BufferedReader br = null;FileReader fr = null;BufferedWriter bw = null;FileWriter fw = null;long startTime = System.currentTimeMillis();try{fr = new FileReader(ipFile);br = new BufferedReader(fr);String ipLine = br.readLine();while(ipLine != null){int hashCode = ipLine.hashCode();hashCode = hashCode < 0 ? -hashCode : hashCode;int fileNum = hashCode % numberOfFile;File file = new File("e:/tmp/ip/"+ fileNum + ".txt");if(!file.exists()){file.createNewFile();}fw = new FileWriter(file,true);bw = new BufferedWriter(fw);bw.write(ipLine + "\n");bw.flush();fw.close();bw.close();ipLine = br.readLine();}long endTime = System.currentTimeMillis();System.err.println(DateUtil.convertMillsToTime(endTime - startTime));}catch (Exception e) {e.printStackTrace();}finally{try{if(fr != null){fr.close();}}catch (Exception e) {e.printStackTrace();}try{if(br != null){br.close();}}catch (Exception e) {e.printStackTrace();}try{if(fw != null){fw.close();}}catch (Exception e) {e.printStackTrace();}try{if(bw != null){bw.close();}}catch (Exception e) {e.printStackTrace();}}}
3.2 第二种方法:
与第一次方法基本相同,不同的是减少流对象的创建,只是创建文件时,创建流对象,但还是需要每次都要判断文件存在与否。大约耗时超过1个多小时,也实在是慢呀,没等它运行完就断了。
/** * 大文件分割为小文件 * @param ipFile * @param numberOfFile */public void splitFile2(File ipFile,int numberOfFile){BufferedReader br = null;FileReader fr = null;BufferedWriter bw = null;FileWriter fw = null;long startTime = System.currentTimeMillis();try{fr = new FileReader(ipFile);br = new BufferedReader(fr);String ipLine = br.readLine();while(ipLine != null){int hashCode = ipLine.hashCode();hashCode = hashCode < 0 ? -hashCode : hashCode;int fileNum = hashCode % numberOfFile;File file = new File("e:/tmp/ip/"+ fileNum + ".txt");if(!file.exists()){file.createNewFile();fw = new FileWriter(file,true);bw = new BufferedWriter(fw);bwMap.put(fileNum, bw);}else{bw = bwMap.get(fileNum);}bw.write(ipLine + "\n");bw.flush();ipLine = br.readLine();}for(int fn : bwMap.keySet()){bwMap.get(fn).close();}bwMap.clear();long endTime = System.currentTimeMillis();System.err.println(DateUtil.convertMillsToTime(endTime - startTime));}catch (Exception e) {e.printStackTrace();}finally{try{if(fr != null){fr.close();}}catch (Exception e) {e.printStackTrace();}try{if(br != null){br.close();}}catch (Exception e) {e.printStackTrace();}try{if(fw != null){fw.close();}}catch (Exception e) {e.printStackTrace();}try{if(bw != null){bw.close();}}catch (Exception e) {e.printStackTrace();}}}
与第二种方法基本相同,在此基础上,优化一边取值,一边写文件的过程,而是先写到内存中,当达到1000后,再一起写入文件中。大约耗时52多分钟,这个是实际运行完的,在中午去吃饭的时候让它自己跑完的。
/** * 大文件分割为小文件 * @param ipFile * @param numberOfFile */public void splitFile3(File ipFile,int numberOfFile){BufferedReader br = null;FileReader fr = null;BufferedWriter bw = null;FileWriter fw = null;long startTime = System.currentTimeMillis();try{fr = new FileReader(ipFile);br = new BufferedReader(fr);String ipLine = br.readLine();while(ipLine != null){int hashCode = ipLine.hashCode();hashCode = hashCode < 0 ? -hashCode : hashCode;int fileNum = hashCode % numberOfFile;File file = new File("e:/tmp/ip/"+ fileNum + ".txt");if(!file.exists()){file.createNewFile();fw = new FileWriter(file,true);bw = new BufferedWriter(fw);bwMap.put(fileNum, bw);dataMap.put(fileNum, new LinkedList<String>());}else{List<String> list = dataMap.get(fileNum);list.add(ipLine + "\n");if(list.size() % 1000 == 0){BufferedWriter writer = bwMap.get(fileNum);for(String line : list){writer.write(line);}writer.flush();list.clear();}}ipLine = br.readLine();}for(int fn : bwMap.keySet()){List<String> list = dataMap.get(fn);BufferedWriter writer = bwMap.get(fn);for(String line : list){writer.write(line);}list.clear();writer.flush();writer.close();}bwMap.clear();long endTime = System.currentTimeMillis();System.err.println(DateUtil.convertMillsToTime(endTime - startTime));}catch (Exception e) {e.printStackTrace();}finally{try{if(fr != null){fr.close();}}catch (Exception e) {e.printStackTrace();}try{if(br != null){br.close();}}catch (Exception e) {e.printStackTrace();}try{if(fw != null){fw.close();}}catch (Exception e) {e.printStackTrace();}try{if(bw != null){bw.close();}}catch (Exception e) {e.printStackTrace();}}}
在第三种方法基础上作进一步优化,不同的是,把创建1000个流对象放到循环外面。大约耗时13分钟35秒。这个方法实在比第三种方法快了4倍左右,但在我觉得,这时间还是有点说不过去呀。
/** * 大文件分割为小文件 * @param ipFile * @param numberOfFile */public void splitFile4(File ipFile,int numberOfFile){BufferedReader br = null;FileReader fr = null;BufferedWriter bw = null;FileWriter fw = null;long startTime = System.currentTimeMillis();try{fr = new FileReader(ipFile);br = new BufferedReader(fr);String ipLine = br.readLine();//先创建文件及流对象方便使用for(int i=0;i<numberOfFile;i++){File file = new File("e:/tmp/ip1/"+ i + ".txt");bwMap.put(i, new BufferedWriter(new FileWriter(file,true)));dataMap.put(i, new LinkedList<String>());}while(ipLine != null){int hashCode = ipLine.hashCode();hashCode = hashCode < 0 ? -hashCode : hashCode;int fileNum = hashCode % numberOfFile;List<String> list = dataMap.get(fileNum);list.add(ipLine + "\n");if(list.size() % 1000 == 0){BufferedWriter writer = bwMap.get(fileNum);for(String line : list){writer.write(line);}writer.flush();list.clear();}ipLine = br.readLine();}for(int fn : bwMap.keySet()){List<String> list = dataMap.get(fn);BufferedWriter writer = bwMap.get(fn);for(String line : list){writer.write(line);}list.clear();writer.flush();writer.close();}bwMap.clear();long endTime = System.currentTimeMillis();System.err.println(DateUtil.convertMillsToTime(endTime - startTime));}catch (Exception e) {e.printStackTrace();}finally{try{if(fr != null){fr.close();}}catch (Exception e) {e.printStackTrace();}try{if(br != null){br.close();}}catch (Exception e) {e.printStackTrace();}try{if(fw != null){fw.close();}}catch (Exception e) {e.printStackTrace();}try{if(bw != null){bw.close();}}catch (Exception e) {e.printStackTrace();}}}
3.5 第五种方法:
使用多线程,未成功实现优化。只是给出思路如下:读取1亿数据的文件,循环读取每个IP,计算其散列值,取模1000,之后把其放到对应的队列中,当其队列超过1000时,启动一个服务线程把数据写入文件中。(也即主线程只负责计算,由其他线程负责写)
3.6 运行结果:
1、第一次分割1亿数据的大文件,实在是太慢,运行差不多一小时,才分割出300W数据,耗时超过2个钟头
2、第二次分割1亿数据的大文件,经过优化后,虽然比第一次有提升,但是还是很慢,耗时超过1个钟头.
3、第三次分割1亿数据的大文件,经过优化后,虽然比第二次有提升,但是还是很慢,需耗时52.0分3.6秒
4、第四次分割1亿数据的大文件,经过优化后,耗时13.0分35.10400000000004秒
4 统计各个文件中出现次数最多的IP(可能有多个):
采用的方法是一边统计各个IP出现的次数,一边算次数出现最大那个IP。
/** * 统计,找出次数最多的IP * @param ipFile */public void read(File ipFile){BufferedReader br = null;FileReader fr = null;long startTime = System.currentTimeMillis();try{fr = new FileReader(ipFile);br = new BufferedReader(fr);String ipLine = br.readLine();while(ipLine != null){ipLine = ipLine.trim();Integer count = ipNumMap.get(ipLine);if(count == null){count = 0;}count ++;ipNumMap.put(ipLine, count);if(count >= ipMaxNum){if(count > ipMaxNum){keyList.clear();}keyList.add(ipLine);ipMaxNum = count;}ipLine = br.readLine();}long endTime = System.currentTimeMillis();System.err.println(ipFile.getName()+":"+DateUtil.convertMillsToTime(endTime - startTime));totalTime += (endTime - startTime);}catch (Exception e) {e.printStackTrace();}finally{try{if(fr != null){fr.close();}}catch (Exception e) {e.printStackTrace();}try{if(br != null){br.close();}}catch (Exception e) {e.printStackTrace();}}}
4.1 运行结果:
1、从1000个文件中查询Ip次数最多的Ip,10.164.143.57:24,3.0分18.748999999999995秒
2、从1000个文件中查询Ip次数最多的Ip,10.164.143.57:24,3.0分27.366000000000014秒
3、从1000个文件中查询Ip次数最多的Ip,10.164.143.57:24,2.0分42.781000000000006秒
5 以上代码的公共变量
public final Map<Integer,BufferedWriter> bwMap = new HashMap<Integer,BufferedWriter>();//保存每个文件的流对象public final Map<Integer,List<String>> dataMap = new HashMap<Integer,List<String>>();//分隔文件用private Map<String,Integer> ipNumMap = new HashMap<String, Integer>();//保存每个文件中的每个IP出现的次数private List<String> keyList = new LinkedList<String>();//保存次数出现最多的IPprivate int ipMaxNum = 0;//次数出现最多的值private long totalTime = 0;//计算统计所耗的时间
6 Main
public static void main(String[] args) {/* * 1、第一次生成1亿(实际上最多为16581375)的ip地址,需要时间为3分多钟不到4分钟。 *//*TooMuchIpFile tooMuchIpFile = new TooMuchIpFile();File ipFile = new File("e:/ipAddr.txt");try {ipFile.createNewFile();} catch (IOException e) {e.printStackTrace();}tooMuchIpFile.gernBigFile(ipFile, 100000000);*///System.err.println("128.128.80.226".hashCode()%1000);//System.err.println("128.128.80.227".hashCode());//System.err.println("10.128.80.227".hashCode());//System.err.println("10.0.80.227".hashCode());/* * 1、第一次分割1亿数据的大文件,实在是太慢,运行差不多一小时,才分割出300W数据,耗时超过2个钟头 * 2、第二次分割1亿数据的大文件,经过优化后,虽然比第一次有提升,但是还是很慢,耗时超过1个钟头. * 3、第三次分割1亿数据的大文件,经过优化后,虽然比第二次有提升,但是还是很慢,需耗时52.0分3.6秒 * 4、第四次分割1亿数据的大文件,经过优化后,耗时13.0分35.10400000000004秒 */TooMuchIpFile tooMuchIpFile = new TooMuchIpFile();File ipFile = new File("e:/ipAddr.txt");tooMuchIpFile.splitFile4(ipFile, 1000);/* * 1、从1000个文件中查询Ip次数最多的Ip,10.164.143.57:24,3.0分18.748999999999995秒 * 2、从1000个文件中查询Ip次数最多的Ip,10.164.143.57:24,3.0分27.366000000000014秒 * 3、从1000个文件中查询Ip次数最多的Ip,10.164.143.57:24,2.0分42.781000000000006秒 *///TooMuchIpFile tooMuchIpFile = new TooMuchIpFile();//File ipFiles = new File("e:/tmp/ip1/");//for (File ipFile : ipFiles.listFiles()) {//tooMuchIpFile.read(ipFile);//tooMuchIpFile.ipNumMap.clear();//}//System.err.println("======================出现次数最多的IP==================");//for(String key: tooMuchIpFile.keyList){//System.err.println(key + ":" + tooMuchIpFile.ipMaxNum);//}//System.err.println(DateUtil.convertMillsToTime(tooMuchIpFile.totalTime));}