巧用MapReduce+HDFS,海量数据去重的五大策略
HadoopSphere .MapReduceHDFSHadoop存储HbaseDedoop云计算. 摘要:随着收集到数据体积的激增,去重无疑成为众多大数据玩家面对的问题之一。重复数据删除在减少存储、降低网络带宽方面有着显著的优势,并对扩展性有所帮助。在存储架构中,删除重复数据的常用方法包括哈希、二进制比较和增量差分;而本文专注的是使用MapReduce和HDFS对数据进行去重。
随着存储数据信息量的飞速增长,越来越多的人开始关注存储数据的缩减方法。数据压缩、单实例存储和重复数据删除等都是经常使用的存储数据缩减技术。
重复数据删除往往是指消除冗余子文件。不同于压缩,重复数据删除对于数据本身并没有改变,只是消除了相同的数据占用的存储容量。重复数据删除在减少存储、降低网络带宽方面有着显著的优势,并对扩展性有所帮助。
举个简单的例子:在专门为电信运营商定制的呼叫详单去重应用程序中,我们就可以看到删除重复数据的影子。同样的,对于包含相同数据包的通信网络,我们可以使用这种技术来进行优化。
在存储架构中,删除重复数据的一些常用的方法包括:哈希、二进制比较和增量差分。在 HadoopSphere这篇文章中,将专注于如何利用MapReduce和HDFS来消除重复的数据。(下面列出的方法中包括一些学者的实验方法,因此把术语定义为策略比较合适)。
策略1:只使用HDFS和MapReduce
Owen O’Malley在一个论坛的帖子中建议使用以下方法:
让你的历史数据按照MD5值进行排序。 运行一个MapReduce的作业,将你的新数据按照MD5进行排序。需要注意的是:你要做所有数据的整体排序,但因为MD5是在整个密钥空间中是均匀分布的,排序就变得很容易。
基本上,你挑选一个reduce作业的数量(如256),然后取MD5值的前N位数据来进行你的reduce作业。由于这项作业只处理你的新数据,这是非常快的。 接下来你需要进行一个map-side join,每一个合并的输入分块都包含一个MD5值的范围。RecordReader读取历史的和新的数据集,并将它们按照一定方式合并。(你可以使用map-side join库)。你的map将新数据和旧数据合并。这里仅仅是一个map作业,所以这也非常快。
当然,如果新的数据足够小,你可以在每一个map作业中将其读入,并且保持新记录(在RAM中做了排序)在合适的数量范围内,这样就可以在RAM中执行合并。这可以让你避免为新数据进行排序的步骤。类似于这种合并的优化,正是Pig和Hive中对开发人员隐藏的大量细节部分。
策略2:使用HDFS和Hbase
在一篇名为“ 工程云系统中一种新颖的删除重复数据技术”的论文中,Zhe Sun, Jun Shen, Jianming Young共同提出了一种使用HDFS和Hbase的方法,内容如下:
•使用MD5和SHA-1哈希函数计算文件的哈希值,然后将值传递给Hbase
•将新的哈希值与现有的值域比较,如果新值已经存在于Hbase去重复表中,HDFS会检查链接的数量,如果数量不为零时,哈希值对应的计数器将增加1。如果数量是零或哈希值在之前的去重复表中不存在,HDFS会要求客户端上传文件并更新文件的逻辑路径。
•HDFS将存储由用户上传的源文件,以及相应的链接文件,这些链接文件是自动生成的。链接文件中记录了源文件的哈希值和源文件的逻辑路径。
要注意使用这种方法中的一些关键点:
•文件级的重复数据删除需要保持索引数量尽可能小,这样可以有高效的查找效率。
•MD5和SHA-1需要结合使用从而避免偶发性的碰撞。
策略3:使用HDFS,MapReduce和存储控制器
由Netapp的工程师AshishKathpal、GauravMakkar以及Mathew John三人联合,在一篇名为“ 在后期处理重复数据删除的分布式重复检测方式”的文章中,提出通过使用HadoopMapReduce的重复检测机制来替代Netapp原有的重复检测环节,文中提到的基于重复检测的Hadoop工作流包含如下几个环节:
•将数据指纹(Fingerprint)由存储控制器迁移到HDFS
•生成数据指纹数据库,并在HDFS上永久存储该数据库
•使用MapReduce从数据指纹记录集中筛选出重复记录,并将去重复后的数据指纹表保存回存储控制器。
数据指纹是指存储系统中文件块经过计算后的哈希索引,通常来说数据指纹要比它代表的数据块体积小的多,这样就可以减少分布式检测时网络中的数据传输量。
策略4:使用Streaming,HDFS,MapReduce
对于Hadoop和Streaming的应用集成,基本上包含两种可能的场景。以IBM Infosphere Streams和BigInsights集成为例,场景应该是:
1. Streams到Hadoop的流程:通过控制流程,将Hadoop MapReduce模块作为数据流分析的一部分,对于Streams的操作需要对更新的数据进行检查并去重,并可以验证MapReduce模型的正确性。
众所周知,在数据摄入的时候对数据进行去重复是最有效的,因此在Infosphere Streams中对于某个特定时间段或者数量的记录会进行去重复,或者识别出记录的增量部分。接着,经过去重的数据将会发送给Hadoop BigInsights用于新模型的建立。
2. Hadoop到Streams的流程:在这种方式中,Hadoop MapReduce用于移除历史数据中的重复数据,之后MapReduce模型将会更新。MapReduce模型作为Streams中的一部分被集成,针对mid-stream配置一个操作符(operator),从而对传入的数据进行处理。
策略5:结合块技术使用MapReduce
在莱比锡大学开发的一个原型工具Dedoop(Deduplication with Hadoop)中,MapReduce应用于大数据中的实体解析处理,到目前为止,这个工具囊括了MapReduce在重复数据删除技术中最为成熟的应用方式。
基于实体匹配的分块是指将输入数据按照类似的数据进行语义分块,并且对于相同块的实体进行限定。
实体解析处理分成两个MapReduce作业:分析作业主要用于统计记录出现频率,匹配作业用于处理负载均衡以及近似度计算。另外,匹配作业采用“贪婪模式”的负载均衡调控,也就是说匹配任务按照任务处理数据大小的降序排列,并做出最小负载的Reduce作业分配。
Dedoop还采用了有效的技术来避免多余的配对比较。它要求MR程序必须明确定义出哪个Reduce任务在处理哪个配对比较,这样就无需在多个节点上进行相同的配对比较。
分享到:
相关推荐
背景分布式一致性 hash 算法将哈希空间组织成一个虚拟的圆环,圆环的大小是,最终会得到一个 [0,] 之间的一个无符号整型,这个整数代表服务器的编号;多个服务
人工智能-hadoop
今天小编就为大家分享一篇关于海量数据去重排序bitmap(位图法)在java中实现的两种方法,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
对大数据文本文件读取(按行读取)的优化,目前常规的方案有三种,第一...代码提供在RandomAccessFile基础上,整合内部缓冲区,效率会有提高,测试过程中1000w行数据用时1秒,1亿行数据用时103(比1438秒快了13倍左右)
海量数据的索引与检索系统 .pdf海量数据的索引与检索系统 .pdf
我们可以用bitmap来解决,bitmap基本思想是一位表示一个整数,比如我们有6个数据: 1 7 3 1 5 6 4 假设bitmap容量为8,当插入7时 bit[7]=1,以此类推 bit[3]=1 bit[1]=1 bit[5]=1 …… bit[4]=1 这样我们查询5,...
简单易用,内置三种爬虫,可应对各种需求场景 AirSpider 轻量爬虫:学习成本低,可快速上手 Spider 分布式爬虫:支持断点续爬、爬虫报警、...支持断点续爬、数据防丢、监控报警、浏览器渲染下载、海量数据去重等功能
Simhash 使用Simhash对海量文本进行去重
由于Hadoop自身并不适合海量小文件处理, 目前的重复数据删除方法主要基于文件的二进制特征, 无法识别经过信号处理后的同一首歌曲, 也不能满足海量数据在线处理的要求。提出一种采用声学指纹去重的海量MP3文件存储...
基于PCL写的一个删除点云数据中的重复点的程序,也可以稍作修改删除数组中的重复点。目前测试一个四千万个点的点云数据,其中包含有一千万个重复点,运行时间为50s。 文件中是源码,其中包含CMakeLists.txt,可通过...
布隆过滤器在网页去重中的应用 , 海量数据处理中的一个绝好应用
这时候我们就要使用 Redis 提供的 HyperLogLog 数据结构来代替 set,它只会占用最多 12k 的存储空间就可以完成海量的去重统计。但是它牺牲了准确度,它是模糊计数,误差率约为 0.81%。 那么有没有一种不怎么浪费...
1. RTF简介 京东RTF实时数据湖,是一个从底层...我们强烈建议您使用正式版本,比单机版本更稳定,性能更好,并且能够在更短的时间处理海量数据。 4. Quick Start 根据使用的版本请参考配置方式 单机版本: 正式版本:
1.海量URL去重 2.海量数据排序 4. 已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数 5. 两个文件合并的问题:给定a、b两个文件
它可以帮助人们从海量数据中提取有价值的信息,及时发现并预测潜在的安全风险。未来的研究可以从以下几个方面展开:1)探讨更加有效的数据预处理方法,以减少数据污染和信息丢失等问题;2)研究更加智能化的算法和...
K-PageSearch是由Kwindsoft自主研发的专业网页搜索引擎系统,拥有先进的智能分析和海量数据检索技术,核心由多线程采集系统、智能分析系统、海量索引系统、全文检索系统四大部分构成。系统采用专业级的搜索引擎系统...
高速公路大数据解决方案旨在通过收集、整合、分析和应用高速公路运营过程中产生的海量数据,提升高速公路管理效率,优化出行体验,并助力相关决策制定。以下是一个高速公路大数据解决方案的概述: 一、数据收集与...
K-PageSearch是由Kwindsoft自主研发的专业网页搜索引擎系统,拥有先进的智能分析和海量数据检索技术,核心由多线程采集系统、智能分析系统、海量索引系统、全文检索系统四大部分构成。系统采用专业级的搜索引擎系统...
K风网页搜索(K-PageSearch)是由Kwindsoft自主研发的专业网页搜索引擎系统,拥有先进的智能分析和海量数据检索技术,核心由多线程采集系统、智能分析系统、海量索引系统、全文检索系统四大部分构成。系统采用专业级的...