计算机科学 ›› 2018, Vol. 45 ›› Issue (6A): 471-475, 505.

• 大数据与数据挖掘 • 上一篇    下一篇

基于列存储的MapReduce分布式Hash连接算法

张滨1,乐嘉锦2   

  1. 浙江财经大学 杭州 3100181
    东华大学计算机科学与技术学院 上海2016202
  • 出版日期:2018-06-20 发布日期:2018-08-03
  • 作者简介:张 滨(1978-),男,博士,讲师,CCF会员,主要研究方向为大数据,E-mail:zhangbin@zufe.edu.cn(通信作者)。
  • 基金资助:
    浙江省哲学社会科学规划课题基金(17NDJC179YB)资助

Hash Join in MapReduce Distributed Environment Based on Column-store

ZHANG Bin1,LE Jia-jin2   

  1. Zhejiang University of Finance & Economics,Hangzhou 310018,China1
    School of Computer Science and Technology,Donghua University,Shanghai 201620,China2
  • Online:2018-06-20 Published:2018-08-03

摘要: 大数据具有规模大、深度大、宽度大、处理时间短、硬件系统普通化、软件系统开源化的特点。传统关系型数据库在对大数据进行操作时存在系统性能严重下降、计算效率提升有限以及可扩展性差等问题,因此引入MapReduce并行计算模型,提出一种大数据上基于列存储的MapReduce分布式Hash连接算法。首先,设计面向大数据的分布式计算模型,在设计的分片聚集并行连接的基础上,利用Hash连接以及动态探测方法优化了数据并行连接处理效率;然后,针对该算法开发了基于Hadoop的原型系统。通过实验证明,在大数据分析处理中,所提算法在执行时间和负载能力上都有很好的性能表现,也能提供良好的可扩展性。

关键词: 大数据, 列存储, Hash连接, MapReduce, 并行计算

Abstract: The characters of big data are volume,variety,value,velocity,and common hardware and open source.Aiming at the system inefficiency and limited scalability of traditional relational database in big data analysis,this paper presented an algorithm of Hash joins in MapReduce distributed environment based on column-store by introducing MapReduce computing model.First of all,this paper proposed the design of large data-oriented distributed computing models.Then,it proposed the partition aggregation and the heuristic optimization strategy to realize the implementation of Hash join algorithm.Lastly,the experiments evaluated execution time and load capacity.The results show that the proposed method is effective and can provid good scalability in big data analysis.

Key words: Big data, Column-store, Hash join, MapReduce, Parallel computing

中图分类号: 

  • TP311
[1]DEAN J,GHEMAWAT S.MapReduce:Simplified Data Pro- cessing on Large Clusters.
[C]∥6th OSDI.San Francisco:USENIX Association,2004:137-150.
[2]ABADI D J,MADDEN S R,HACHEM N.Column-Stores vs.Row-Stores:How Different Are They Really? [C]∥The 2008 ACM SIGMOD Int Conf.Vancouver,BC,Canada:ACM,2008:967-980.
[3]STONEBRAKER M,ABADI D J,BATKIN A,et al.C-Store:A column-oriented DBMS.
[C]∥VLDB Conference.Trondheim,Norway:VLDB Endowment,2005:553-564.
[4]BONCZ P,ZUKOWSKI M,NES N.MonetDB/X100:Hyper- Pipelining Query Execution.
[C]∥The Biennial Conf on Innovative Data Systems Research (CIDR).Asilomar,CA,USA:ACM,2005:225-237.
[5]BLANAS S,PATEL J M,ERCEGOVAC V,et al.A comparison of join algorithms for log processing in MapReduce[C]∥The ACM SIGMOD International Conference on Management of Data.Indianapolis,Indiana,USA:ACM,2010:975-986.
[6]ABOUZEID A,BAJDA-PAWLIKOWSKI K,ABADI D J,et al.HadoopDB:An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads[C]∥VLDB Conference.Lyon,France,VLDB Endowment,2009:922-933.
[7]BAJDA-PAWLIKOWSKI K,ABADI D J,SILBERSCHATZ A,et al.Efficient Processing of Data Warehousing Queries[C]∥The ACM SIGMOD International Conference on Management of Data.Athens,Greece,ACM,2011:1165-1176.
[8]CHANG F,DEAN J,GHEMAWAT S,et al.Robert Gruber: Bigtable:A Distributed Storage System for Structured Data[C]∥OSDI.2006:205-218.
[9]MELNIK S,GUBAREV A,LONG J J,et al.Dremel:Interactive Analysis of Web-Scale Datasets[C]∥VLDB Conference.Singapore,VLDB Endowment,2010:330-339.
[10]LIN Y T,AGRAWAL D,CHEN C,et al.Llama:Leveraging Columnar Storage for Scalable Join Processing in the MapReduce Framework[C]∥The ACM SIGMOD International Conference on Management of Data.Athens,Greece:ACM,2011:961-972.
[11]FLORATOU A,PATEL J M,SHEKITA E J,et al.Column-Oriented Storage Techniques for MapReduce[J].PVLDB,2011,4(7):419-429.
[12]THUSOO A,SARMA J S,JAIN N,et al.Raghotham Murthy:Hive-A Warehousing Solution Over a Map-Reduce Framework.
[C]∥VLDB Conference.Lyon,France,VLDB Endowment,2009:1626-1629.
[13]HE Y Q,LEE R B,HUAI Y,et al.RCFile:A Fast and Space-efficient Data Placement Structure in MapReduce-based Warehouse Systems[C]∥IEEE International Conference on Data Engineering.Hannover,Germany,2011:1199-1208.
[14]HSIAO H,CHEN M S,YU P S.Parallel execution of hash joins in parallel databases[J].IEEE Trans.on Parallel and Distributed Systems,1997,8(8):872-883.
[15]BONCZ P,MANEGOLD S,KERSTEN M L.Database architecture optimized for the new bottleneck:memory access[C]∥The 25th Int’l Conf.on Very Large Data Bases.ACM Press,1999:231-246.
[16]O’NEIL P,O’NEIL B,CHEN X D.Star Schema Benchmark Revision[EB/OL].
[2010-2-9].http://www.cs.umb.edu/~poneil.
[1] 王童, 马文平, 罗维. 基于区块链的信息共享及安全多方计算模型[J]. 计算机科学, 2019, 46(9): 162-168.
[2] 徐磊, 陈荣亮, 蔡小川. 基于非结构化网格的高可扩展并行有限体积格子[J]. 计算机科学, 2019, 46(8): 84-88.
[3] 孔繁钰, 周愉峰, 陈纲. 基于时空特征挖掘的交通流量预测方法[J]. 计算机科学, 2019, 46(7): 322-326.
[4] 王震, 周颖, 黄赪东, 苗泉强. 面向大数据应用的区块链解决方案综述[J]. 计算机科学, 2019, 46(6A): 6-10.
[5] 张新, 胡晓东, 魏嘉伟. 基于云计算的地理信息服务技术[J]. 计算机科学, 2019, 46(6A): 532-536.
[6] 赵颖, 侯俊杰, 于成龙, 徐皓, 张伟. 面向生产管控的工业大数据研究及应用[J]. 计算机科学, 2019, 46(6A): 45-51.
[7] 刘胜娃, 孙俊明, 高翔, 王敏. 基于人工神经网络的钻井机械钻速预测模型的分析与建立[J]. 计算机科学, 2019, 46(6A): 605-608.
[8] 冯贵兰, 李正楠, 周文刚. 大数据分析技术在网络领域中的研究综述[J]. 计算机科学, 2019, 46(6): 1-20.
[9] 吕志泉, 李昊, 张宗福, 张敏. 基于主题模型的社交网络匿名用户重识别[J]. 计算机科学, 2019, 46(6): 143-147.
[10] 舒娜,刘波,林伟伟,李鹏飞. 分布式机器学习平台与算法综述[J]. 计算机科学, 2019, 46(3): 9-18.
[11] 刘颖. 供应链金融大数据分布特征的分析与洞见[J]. 计算机科学, 2019, 46(2): 1-10.
[12] 王旸, 蔡淑琴, 邹新文, 陈梓桐. 质量嵌入的大数据产品生产系统超图模型及其生产线决策研究[J]. 计算机科学, 2019, 46(2): 11-17.
[13] 毕娅, 原惠群, 初叶萍, 刘慧. 大数据环境下基于公共服务平台的资源多级智能寻租与匹配策略和价值创造[J]. 计算机科学, 2019, 46(2): 42-49.
[14] 杨德杰, 章宁, 袁戟, 白璐. 基于堆栈降噪自编码网络的个人信用风险评估方法[J]. 计算机科学, 2019, 46(10): 7-13.
[15] 柯昌博, 黄志球, 吴嘉余. 面向大数据的隐私发布暴露检测方法[J]. 计算机科学, 2019, 46(10): 148-153.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[3] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[4] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[5] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[6] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[7] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[8] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[9] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[10] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .