[介绍]
这是一道经典的题目,而且也是比较贴近实际的一个问题。 在网上,已经有人给出了非常好的解决方式, 如 CSDN July http://www.cnblogs.com/v-July-v/archive/2012/03/22/2413055.html。
我这里罗列出来,出于两方面考虑
1. 重复、加深记忆。我会把重点思路加以重复
2. 扩展。扩展到更多的场景,拓宽思路。
[解决]
重复一下题目
一个数据文件,非常大(如 100G),每行都是一条IP访问记录。计算器中重复最多的IP,即访问最多的IP。
分析
由于数据源太大,无法直接brute force的进行内存处理,那么从几个方面考虑
首先,贼心不死,看看能不能直接内存处理? 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。
显然,使用64位的OS,64G内存的机器的话,还是有可能的哦。但是如果是IPv6呢?歇菜了吧!
不过,这种把数据源的数据属性认真分析的方法,还是非常非常值得推荐的!!!!
然后,还是老实的把大文件分拆了吧。
大文件划分成若干小文件,如1024个小文件。划分时,把相同IP的条目分配到相同的文件中。这样分别统计小文件的IP,然后汇总即可。
注意:保证相同ip分配到相同小文件中。简单的hash就能达到这个效果。如果分配到不同文件中,则没有意义了。
注意:这里的思路是,分拆大数据量的时候,要注意,此时你可能可以做一些预处理的工作。预处理工作一方面保证你的工作可以完成,另一方面,可能可以加快处理过程。此预处理,要考虑当前数据的属性。
[扩展]
有些场景下,需要实时统计最大IP数。HOW?
重复一下场景:数据源是没有截止的,它源源不断的提供更多的IP访问记录。要求,得到当前时刻,访问最多的那个IP,以及它的数量。进一步要求,获得当前时刻,访问最多的Top K (e.g. K =100)个IP。
与上面的拆分思路一致,将数据源的条目分别送到N个服务器上分别处理。相同IP,会到达相同的服务器。
这些服务器在处理的时候,内部保存当前所有uniq IP的访问数量与一个Tree(TODO:何种Tree比较好?RB tree looks good)中.每次到达新的IP,则调整这个树。此树要求,1) 快速定位节点,以更新其value 2)更新某个节点值后,能够快速调整 3)方便获取Top K记录 注: priority Q怎么样?取最大值很方便,TopK则不行。快速定位也不太行。
继续思考:由于调整频繁(数据源更新过快),如200,000条数据/秒钟,会导致该树一直抖动 200,000次抖动每秒钟,如何处理? 此场景非常常见!
1)有没有别的更好的数据结构?
OR
2)缓存新入数据,譬如1秒钟,然后再更新树,这样,最多抖动60*uniq IP数量次/每分钟。注意:缓存的1秒钟数据,要进行uniq IP计数累加,这样1秒钟到达时,uniq IP只引起一次抖动。
OR
3) 还有什么别的办法么?Spark之类的能帮忙做点什么么?
相关推荐
从海量素剧中查找中位数,从海量数据中查找一个数,海量数据问题
NULL 博文链接:https://yueyemaitian.iteye.com/blog/1180299
海量数据是发展趋势,对数据分析和挖掘也越来越重要,从海量数据中提取有用信息重要而紧迫,这便要求处理要准确,精度要高,而且处理时间要短,得到有价值信息要快,所以,对海量数据的研究很有前途,也很值得进行...
海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化 SQL海量数据 优化...
一个简单的使用hash来实现从海量IP地址中查询是否存在待查找的IP地址。主要特点有: (1)使用批处理,一键自动编译,处理;可直接运行。 (2)完美的展示了hash在查询中的使用方法。
系统由五大模块组成,有系统管理模块、并行加载存储模块、并行查询模块、数据字典模块、备份恢复模块,能够实现存储海量海洋科学数据.系统模块实现结果表明,该系统安全可靠、易维护、具有良好的可扩展性.
西电海量数据管理大作业,有图,有设计思路
海量数据 海量数据 海量数据
将海量数据导入到sql中将海量数据导入到sql中
常用大数据量,海量数据处理方法,算法总结,非常好的书。
基于openlayers和canvas绘制海量数据的实现
详细介绍访问海量数据的步骤、方式;配合示例函数,包括详细的注释(C++)。
海量数据处理 !!!!!
数据量的问题是很多面试笔试中经常出现的问题,比如 baidu google 腾讯 这样的一些 涉及到海量数据的公司经常会问到。 下面的方法是我对海量数据的处理方法进行了一个一般性的总结, 当然这些方法可能并不能 完全覆盖...
海量数据面试题整理海量数据面试题整理海量数据面试题整理海量数据面试题整理
包含各种不常见的海量数据处理算法和相应的数据结构。确实是一本好资料啊
针对云计算环境中数据的海量性和分布性特点,以及现有的分布式B树索引方法存在访问效率较低的问题,提出一种云计算环境中海量数据高效索引方法,它在分布式B树的基础之上采用日志来记录节点的分裂历史,并基于节点...
基于海量图像数据管理的新难题和新的解决方案不断被提出的背景,本文在 分析了海量图像数据的产生与应用的具体背景之后,根据Hadoop系统在存储和 管理网页数据与日志数据等的成功,研究了基于Hadoop系统的大规模海量...
● 海量数据分库分表+文件存储:Mysql8.0+ShardingSphere多维度分库分表 + 阿里云OSS ● 实时计算+数据处理+存储可视化:Flink1.13 + ClickHouse + HDFS + 数据清洗分层 + Echart可视化数据 ● 分布式链路追踪+监控+...
Java海量数据分页Bean, 适用于Oracle(适当修改,适用于任何数据库).功能描述:传入到达页码(具有容错性)、每页记录数、Select查询语句,返回该页所有的记录(整页是List集合,每条记录是一个 HashMap)、总行数、总...