从1亿个ip中找出访问次数最多的IP

标签: ip 访问 次数 | 发表时间:2014-02-17 02:48 | 作者:foolsheep
出处:http://blog.csdn.net

看了 教你如何迅速秒杀掉:99%的海量数据处理面试题一文,的确是挺有收获的,特别是对这种海量数据的处理,的确是有了一个挺清晰的思路,特别感谢原文博主July。

处理海量数据问题存在的原因就在于1)数据量太大,无法在短时间内解决;2)内存不够,没办法装下那么多的数据。

而对应的办法其实也就是分成1)针对时间,合适的算法+合适的数据结构来提高处理效率;2)针对空间,就是分而治之,将大数据量拆分成多个比较小的数据片,然后对其各个数据片进行处理,最后再处理各个数据片的结果。

原文中也给出一个问题,“从1亿个ip中访问次数最多的IP”,就试着来解决一下吧。

1)首先,生成1亿条数据,为了产生更多的重复ip,前面两节就不变了,只随机生成后面的2节。

	private static String generateIp() {
		return "192.168." + (int) (Math.random() * 255) + "."
				+ (int) (Math.random() * 255) + "\n";
	}
	private static void generateIpsFile() {
		File file = new File(FILE_NAME);
		try {
			FileWriter fileWriter = new FileWriter(file);
			for (int i = 0; i < MAX_NUM; i++) {
				fileWriter.write(generateIp());
			}
			fileWriter.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}	
1个char是一个Byte,每个ip大概是15Btye,所以生成的ip文件,大概是1,500,000,000Byte = 1,500,000 KB,如下:


2)文件生成了,那么我们现在就要假设内存不是很够,没有办法一次性装入那么多的数据,所以要先把文件给拆分成多个小文件。

在这里采取的是就是Hash取模的方式,将字符串的ip地址给转换成一个长整数,并将这个数对1000取模,将模一样的ip放到同一个文件,这样就能够生成1000个小文件,每个文件就只有1M多,在这里已经是足够小的了。

首先是hash跟取模函数:

	private static String hash(String ip) {
		long numIp = ipToLong(ip);
		return String.valueOf(numIp % HASH_NUM);
	}

	private static long ipToLong(String strIp) {
		long[] ip = new long[4];
		int position1 = strIp.indexOf(".");
		int position2 = strIp.indexOf(".", position1 + 1);
		int position3 = strIp.indexOf(".", position2 + 1);

		ip[0] = Long.parseLong(strIp.substring(0, position1));
		ip[1] = Long.parseLong(strIp.substring(position1 + 1, position2));
		ip[2] = Long.parseLong(strIp.substring(position2 + 1, position3));
		ip[3] = Long.parseLong(strIp.substring(position3 + 1));
		return (ip[0] << 24) + (ip[1] << 16) + (ip[2] << 8) + ip[3];
	}
2.1)将字符串的ip转换成长整数

2.2)对HASH_NUM,这里HASH_NUM = 1000;

下面是拆文件的函数:

	private static void divideIpsFile() {
		File file = new File(FILE_NAME);
		Map<String, StringBuilder> map  = new HashMap<String,StringBuilder>();
		int count = 0;
		try {
			FileReader fileReader = new FileReader(file);
			BufferedReader br = new BufferedReader(fileReader);
			String ip;
			while ((ip = br.readLine()) != null) {
				String hashIp = hash(ip);
				if(map.containsKey(hashIp)){
					StringBuilder sb = (StringBuilder)map.get(hashIp);
					sb.append(ip).append("\n");
					map.put(hashIp, sb);
				}else{
					StringBuilder sb = new StringBuilder(ip);
					sb.append("\n");
					map.put(hashIp, sb);
				}
				count++;
				if(count == 4000000){
					Iterator<String> it = map.keySet().iterator();					
					while(it.hasNext()){
						String fileName = it.next();
						File ipFile = new File(FOLDER + "/" + fileName + ".txt");
						FileWriter fileWriter = new FileWriter(ipFile, true);
						StringBuilder sb = map.get(fileName);				
						fileWriter.write(sb.toString());;
						fileWriter.close();
					}
					count = 0;
					map.clear();
				}
			}
			br.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
2.3)在这里,我们如果每读取一个ip,经过hash映射之后,就直接打开文件,将其加到对应的文件末尾,那么有1亿条ip,我们就要读写文件1亿次,那IO开销的时候就相当大,所以我们可以先拿一个Map放着,等到一定的规模之后,再统一写进文件,然后把map清空,继续映射,这样的话,就能够提高折分的速度。而这个规模,就是根据能处理的内存来取的值的,如果内存够大,这个值就可以设置大点,如果内存小,就要设置小一点的值,IO开销跟内存大小,总是需要在这两者之间的取个平衡点的。


可以看到,这样我们拆分成了1000个小文件,每个文件只有1500KB左右,所耗的时间如下,7分钟到8分钟左右:

Start Divide Ips File: 06:18:11.103
End:                   06:25:44.134
而这种映射可以保证同样的IP会映射到相同的文件中,这样后面在统计IP的时候,就可以保证在a文件中不是最多次数的ip(即使是第2多),也不会出现在其它的文件中。

3)文件拆分了之后,接下来我们就要分别读取这1000个小文件,统计其中每个IP出现的次数。

	private static void calculate() {
		File folder = new File(FOLDER);
		File[] files = folder.listFiles();
		FileReader fileReader;
		BufferedReader br;
		for (File file : files) {
			try {
				fileReader = new FileReader(file);
				br = new BufferedReader(fileReader);
				String ip;
				Map<String, Integer> tmpMap = new HashMap<String, Integer>();
				while ((ip = br.readLine()) != null) {
					if (tmpMap.containsKey(ip)) {
						int count = tmpMap.get(ip);
						tmpMap.put(ip, count + 1);
					} else {
						tmpMap.put(ip, 0);
					}
				}	
				fileReader.close();
				br.close();
				count(tmpMap,map);
				tmpMap.clear();
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		
		count(map,finalMap);		
		Iterator<String> it = finalMap.keySet().iterator();
		while(it.hasNext()){
			String ip = it.next();
			System.out.println("result IP : " + ip + " | count = " + finalMap.get(ip));
		}
		
	}		

	private static void count(Map<String, Integer> pMap, Map<String, Integer> resultMap) {
		Iterator<Entry<String, Integer>> it = pMap.entrySet().iterator();
		int max = 0;
		String resultIp = "";
		while (it.hasNext()) {
			Entry<String, Integer> entry = (Entry<String, Integer>) it.next();
			if (entry.getValue() > max) {
				max = entry.getValue();
				resultIp = entry.getKey();
			}
		}
		resultMap.put(resultIp,max);	
	}

3.1)第一步要读取每个文件,将其中的ip放到一个Map中,然后调用count()方法,找出map中最大访问次数的ip,将ip和最多访问次数存到另外一个map中。

3.2)当1000个文件都读取完之后,我们就会产生一个有1000条记录的map,里面存储了每个文件中访问次数最多的ip,我们再调用count()方法,找出这个map中访问次数最大的ip,即这1000个文件中,哪个文件中的最高访问量的IP,才是真正最高的,好像小组赛到决赛一样。。。。

3.3)在这里没有用到什么堆排序和快速排序,因为只需要一个最大值,所以只要拿当前的最大值跟接下来的值判断就好,其实也相当跟只有一个元素的堆的堆顶元素比较。

下面就是我们的结果 。

Start Calculate Ips: 06:37:51.088
result IP : 192.168.67.98 | count = 1707
End: 06:44:30.229
到这里,我们就把这个ip给查找出来了。

其实理解了这个思路,其它的海量数据问题,虽然可能各个问题有各个问题的特殊之处,但总的思路我觉得应该是相似的。

作者:foolsheep 发表于2014-2-16 18:48:56 原文链接
阅读:113 评论:0 查看评论

相关 [ip 访问 次数] 推荐:

从1亿个ip中找出访问次数最多的IP

- - CSDN博客互联网推荐文章
看了 教你如何迅速秒杀掉:99%的海量数据处理面试题一文,的确是挺有收获的,特别是对这种海量数据的处理,的确是有了一个挺清晰的思路,特别感谢原文博主July. 处理海量数据问题存在的原因就在于1)数据量太大,无法在短时间内解决;2)内存不够,没办法装下那么多的数据. 而对应的办法其实也就是分成1)针对时间,合适的算法+合适的数据结构来提高处理效率;2)针对空间,就是分而治之,将大数据量拆分成多个比较小的数据片,然后对其各个数据片进行处理,最后再处理各个数据片的结果.

nginx限制某个IP同一时间段的访问次数

- - 企业架构 - ITeye博客
如何设置能限制某个IP某一时间段的访问次数是一个让人头疼的问题,特别面对恶意的ddos攻击的时候. 其中CC攻击(Challenge Collapsar)是DDOS(分布式拒绝服务)的一种,也是一种常见的网站攻击方法,攻击者通过代理服务器或者肉鸡向向受害主机不停地发大量数据包,造成对方服务器资源耗尽,一直到宕机崩溃.

提取出某日访问百度次数最多的那个IP

- - CSDN博客推荐文章
问题描述:海量日志数据,提取出某日访问百度次数最多的那个IP.     假设一天之内某个IP访问百度的次数不超过40亿次,则访问次数可以用unsigned表示.用数组统计出每个IP地址出现的次数,  即可得到访问次数最大的IP地址..     IP地址是32位的二进制数,所以共有N=2^32=4G个不同的IP地址, 创建一个unsigned count[N];的数组,即可统计出每个IP的访问次数,而sizeof(count) == 4G*4=16G, 远远超过了32位计算机所支持的内存大小,因此不能直接创建这个数组.下面采用划分法解决这个问题..

海量日志中统计次数最多的100个IP

- - SegmentFault 最新的文章
由于标题长度限制,原题是这样:某系统QPS100万,每十分钟统计一下请求次数最多的100个IP. ip请求写到日志的话,其实就是超大文件中统计top k问题. 10分钟6亿条记录,大约是10G级别,所以对于一般单机处理来讲不能一次性加载到内存计算. 所以分治算法是处理这类问题的基本思想. 思路就是把大文件分割成多个可以内存处理的小文件,对每个小文件统计top k问题,最后再对所有统计结果合并得到最终的top k.

通过GeoIP2分析访问者IP获取地理位置信息

- - CSDN博客推荐文章
原文链接:http://blog.csdn.net/johnnycode/article/details/42028841. MaxMind GeoIP2 服务能识别互联网用户的地点位置与其他特征,应用广泛,包括个性化定制内容、诈欺检测、广告定向、网站流量分析、执行规定、地理目标定位、地理围栏定位 (geo-fencing)以及数字版权管理.

tcp/ip调优

- Lucseeker - 在路上
在TCP/IP协议中,TCP协议提供可靠的连接服务,采用三次握手建立一个连接. 第一次握手:建立连接时,客户端发送syn包(syn=x)到服务器,并进入SYN_SEND状态,等待服务器确认;. 第二次握手:服务器收到syn包,必须确认客户的SYN(ack=x+1),同时自己也发送一个SYN包(syn=y),即SYN+ACK包,此时服务器进入SYN_RECV状态;.

获取 WAN IP

- 狗尾草 - LinuxTOY
如果你在 router 或者 firewall 后面,你直接查询 interface ,拿到可能不是 WAN 的 IP. 很久很久以前的一个版本,把它们贴到 .bashrc (Bash 专用) 或者 .profile (非 Bash 专用)里面去. .profile 即可生效,输入 myip 就能拿到 WAN IP.

TCP/IP分享——链路层

- Goingmm - 弯曲评论
在张国荣自尽8周年纪念日,也就是愚人节的前几十分钟,终于把第二章弄完了. 首席似乎不是特别有空,我就斗胆在这里自己发了,从前面2期的反响来看,相当热烈,我也是摆出一副要杀要剐,悉听尊便的架势,这可能是受最近流行霸气外露的影响,批评几句又伤不了皮毛,也影响不了我的工作和正常生活,只要给大家带来快乐,我就很开心,似乎历史上很多想法都是在争吵中诞生的.

一些IP查询网站

- 19GHz - iGFW
一些境内服务器的IP查询网站:. 一些境外服务器的IP查询网站:. https://whoer.net/ (支持https). 各网站查询到的IP归属地可能有差异,以apnic.net为准. 本文原始地址:http://igfw.tk/archives/5611.

TCP/IP重传超时--RTO

- dennis - 一个故事@MySQL DBA
Shared by 子非鱼 安知余(褚霸). 概述:本文讨论主机在发送一个TCP数据包后,如果迟迟没有收到ACK,主机多久后会重传这个数据包. 主机从发出数据包到第一次TCP重传开始,RFC中这段时间间隔称为retransmission timeout,缩写做RTO. 本文会先看看RFC中如何定义RTO,然后看看Linux中如何实现.