`
winnerbao
  • 浏览: 10379 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

统计海量数据中访问最多的IP (略有扩展)

 
阅读更多

[介绍]

这是一道经典的题目,而且也是比较贴近实际的一个问题。 在网上,已经有人给出了非常好的解决方式, 如 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之类的能帮忙做点什么么?
 

 

分享到:
评论

相关推荐

    常用大数据量,海量数据处理方法,算法总结

    2. 海量日志数据,提取出某日访问百度次数最多的那个 IP。 3. 如何根据输入元素个数 n,确定位数组 m 的大小及哈希函数个数 k。 这些问题可以使用上述方法来解决,例如使用 Bloom filter 或 Hashing 等方法来查找、...

    大数据量,海量数据_处理方法总结

    - 海量日志数据中,提取出某日访问百度次数最多的IP地址。由于IP地址总数有限,可以考虑使用哈希表将IP地址直接存入内存中,并进行统计。 #### 四、Bit-Map **适用范围**:适用于数据范围较小的情况,如电话号码等...

    c语言如何对海量数据进行处理

    4. **提取最多访问IP**: - **哈希分桶**:将IP地址映射到小文件,对每个文件统计IP频率,使用堆数据结构找出每个文件内的最高频IP,最后全局合并结果。 以上策略的核心在于合理利用内存,通过外部存储扩展处理...

    面试题目-大数据量海量数据处理.pdf

    这些面试题目聚焦于大数据量和海量数据的处理,涵盖了各种挑战,包括数据过滤、去重、排序、频率统计和热门元素提取。以下是对这些题目的详细解析和相关知识点: 1. **URL共现问题**:这是一个典型的集合交集问题,...

    常用大数据量、海量数据处理方法__算法总结.pdf

    而对于IP访问频率统计问题,则可以通过Hashing将IP存入内存,并进行快速计数;在处理海量电话号码去重时,使用Bit-Map可以高效地统计不重复的电话号码数量。 在处理大数据时,需要综合考虑空间复杂度、时间复杂度、...

    网易海量数据存储平台的构建和运维

    在当今互联网时代,数据量呈爆炸式增长,各大互联网公司面临着海量数据存储、管理以及高效利用的挑战。网易,作为一家领先的互联网技术公司,其海量数据存储平台的构建和运维,为我们提供了一个研究案例。根据提供的...

    大数据量,海量数据 处理方法总结.docx

    - 应用场景:如在海量日志数据中,可以通过哈希IP地址并存储在内存中,统计每个IP的访问次数以找出访问最频繁的IP。 3. **Bit-Map** Bit-Map是使用位数组来表示特定范围内的元素是否存在,适用于数据范围较小但...

    论文研究-基于Hadoop的海量日志数据处理 .pdf

    具体实验中,研究者对读取的数据文件进行处理,通过Hadoop程序提取记录中的IP地址,并统计不同IP地址出现的次数。整个处理流程包括数据的上传到HDFS、数据的读取、处理和最终的结果汇总。 文章通过对Hadoop的介绍和...

    基于Hadoop云平台的海量数据挖掘方法 (1).pdf

    HBase是建立在HDFS之上的一种分布式NoSQL数据库,支持海量数据的随机实时读写访问。HBase利用Hadoop的分布式存储机制,提供了水平扩展能力。 二、海量数据挖掘的概念和应用 海量数据挖掘是指利用计算机技术从大规模...

    大数据量,海量数据处理方法总结知识.pdf

    大数据量和海量数据处理是现代信息技术领域的重要议题,特别是在互联网巨头如百度、谷歌和腾讯等公司,它们需要处理的数据规模巨大。以下是对大数据处理方法的总结: 1. **布隆过滤器 (Bloom Filter)** 布隆过滤...

    面试中的大数据处理

    大数据量的问题是许多面试笔试中经常出现的问题,一些涉及到海量数据的公司,如baidu、google、腾讯等经常会问到。下面是一些常见的大数据处理方法。 1.Bloom filter: Bloom filter是一种常见的大数据处理方法,...

    OpenDNS数据统计的实现过程

    OpenDNS作为全球领先的DNS解析服务提供商,通过采用先进的技术和策略实现了海量数据的有效管理和利用。对于其他同样面临大数据挑战的企业来说,OpenDNS的成功实践提供了宝贵的经验和启示。未来,随着技术的发展和...

    希嘉数据中台体系--05--数据计算篇.pdf

    - 选用Spark作为核心计算组件,结合Hadoop集群的分布式存储和计算,处理海量数据运算。Spark具有强大的兼容性和并行处理能力,支持Java、Scala、Python等多种编程语言,简化大数据处理流程。 3. **希嘉中台体系的...

    数据湖+运维与监控技术教程

    - **数据访问**:数据湖提供更为灵活的数据访问方式,而数据仓库则提供更优化的查询性能。 ### 四、数据湖的运维与监控 **4.1 数据湖的部署与配置** 部署数据湖时,需要考虑多个方面,首先是选择合适的存储系统。...

    大数据处理方法

    - **海量日志数据分析:** 提取某日访问百度次数最多的IP。考虑到IP地址总数有限(2^32),可以使用哈希表将IP地址直接存入内存进行统计。 #### 三、Bit-Map(位图) **适用范围:** 位图适用于快速查找、去重和...

    季风流量统计系统_jfcountv1.0.rar

    例如,利用缓存技术减少数据库查询压力,通过异步处理提高系统响应速度,或者引入大数据处理框架如Hadoop或Spark,处理海量的访问日志。 通过深入研究和实践季风流量统计系统_jfcountv1.0,开发者不仅能掌握JSP编程...

Global site tag (gtag.js) - Google Analytics