[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN106484879A - 一种基于MapReduce的Map端数据的聚合方法 - Google Patents

一种基于MapReduce的Map端数据的聚合方法 Download PDF

Info

Publication number
CN106484879A
CN106484879A CN201610899802.XA CN201610899802A CN106484879A CN 106484879 A CN106484879 A CN 106484879A CN 201610899802 A CN201610899802 A CN 201610899802A CN 106484879 A CN106484879 A CN 106484879A
Authority
CN
China
Prior art keywords
key
value
polymerization
internal memory
map
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN201610899802.XA
Other languages
English (en)
Other versions
CN106484879B (zh
Inventor
郭方方
朱建文
吕宏武
王慧强
冯光升
刘慧姝
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Harbin Engineering University
Original Assignee
Harbin Engineering University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Harbin Engineering University filed Critical Harbin Engineering University
Priority to CN201610899802.XA priority Critical patent/CN106484879B/zh
Publication of CN106484879A publication Critical patent/CN106484879A/zh
Application granted granted Critical
Publication of CN106484879B publication Critical patent/CN106484879B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/28—Databases characterised by their database models, e.g. relational or object models
    • G06F16/284—Relational databases
    • G06F16/285—Clustering or classification
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本发明提供的是一种基于MapReduce的Map端数据的聚合方法。包括测试阶段和聚合阶段。测试阶段，通过测试阶段来验证所使用Map端的Map函数中的算法是否适合进行内聚合。内聚合方法是在内存中Map函数的计算过程中进行的，计算完一部分后就进行聚合；外聚合方法是在Map函数将所有数据计算完存入磁盘后，再调入内存进行聚合。聚合阶段，若测试通过，使用内聚合方法对Map端计算后的数据进行聚合；若测试未通过，使用外聚合方法对Map端计算的后的数据进行聚合。本发明根据数据的特点，保证计算结果正确的前提下，选择相应的聚合方式，在减少I/O的访问次数的同时，减少传输<Key,Value>的通信量。

Description

一种基于MapReduce的Map端数据的聚合方法
技术领域
本发明涉及的是一种分布式计算方法，具体涉及一种基于MapReduce的Map端数据的聚合方法。
背景技术
当前处理大数据应用问题时，比较重要的两个思想：并行和分治。通过将大规模的数据合理的拆分成多个小部分，通过并行思想和分治思想相结合的计算方法，使得问题得到的相对满意的解决。MapReduce为我们提供了一种有效、快速的并行编程框架。
MapReduce实现了两个主要功能：Map和Reduce。Map是把一个函数应用于集合中的所有成员，然后返回一个基于这个处理的结果集。Reduce是把两个或更多个Map中一些结果，通过多个线程、进程或者独立系统并行处理的结果集进行分类和归纳。
在MapReduce模型中，用户需要定义Map和Reduce函数，输入是一个键值对列表，键值对是由键和值组成的二元组(Key,Value)，排序和分组都是基于Key。Map函数的输入时键值对，对每个键值对进行计算，产生的结果也是中间键值对列表。在Map和Reduce中间这个键值列表，基于键进行聚集。Reduce函数的输入是基于键的键值对分组，其中每个分组都是独立的，这样就可以使用分布式大规模并行的方式进行处理，总输入能远大MapReduce的结点的内存。
然而在真正的处理方面，处理的速度并不是和所投入的资源成正比的，比如：用2台主机处理数据的效率并不会比用1台主机的提高1倍。而是少于1；因为大数据处理过程中，如何将数据从产生端(Map的输出)传输到使用端(Reduce输入)是一个很重要的问题。因为传输一般会涉及I/O操作以及网络传输，而两者都相对耗时。Hadoop中，中间结果一般先写回磁盘，然后在通过网络传输给Reduce端。所以，提高算法运行效率，减少通信量，Map端需要尽可能少的结果。
为了解决Map端计算结果中的键值对过多的问题，一种方法是引入Combine组件，将中间结果聚合，相当于做了一小的Reduce。但这样做将会进行两次I/O，因为Map计算完后会立刻写入磁盘，然后将磁盘中数据读出来进行的使用Combine来聚合。
另一种方法将Map端计算结果中的键值对在内存中聚合，一次计算，一次I/O。这种方法的优点是速度快。内聚合要求Map端的Map函数中的算法在内存中保留计算的中间结果。但不是所有的算法都是适用于将计算结果在内存中聚合，因为在内存中的聚合操作在计算的过程中进行的，对于与数据的输入顺序有关的算法，如果使用内聚合，最终的计算结果可能和外聚合的结果不同，所以，在内聚合前需要进行验证Map函数中算法是否能够进行内聚合。
综上所述，目前在对基于MapReduce的Map端聚合机制的研究中，内聚合即在内存中聚合，是通过编写MapReduce程序时用户自己实现的，基本方法是简单设置临时变量来存储合并Map计算后的键值对，外聚合即通过Hadoop中提供的Combine组件实现的。现存的聚合方法过于简单，在内存中不能有效的对Map计算后的键值对进行聚合，效率低。
发明内容
本发明的目的在于提供一种能够解决MapReduce计算框架下Map端数据聚合方法效率低、Map端计算结果过多等问题的基于MapReduce的Map端数据的聚合方法。
本发明的目的是这样实现的：
(1)分别通过外聚合和内聚合计算出相应的结果；
(2)比较两个结果是否相同；
(3)若相同则进行内聚合，若不相同则进行外聚合；
所述内聚合具体包括：
(3.1.1)建立<Key,Value>倒排索引：根据读入的<Key,Value>中Key值建立倒排索引，在索引中记录<Key,Addresss>,Address为<Key,Value>在内存中的地址值；
(3.1.2)对Address建立指向Count的索引，进行匹配，将匹配成功的<Key,Value>进行合并；
(3.1.3)在进行下次匹配之前，查看内存是否足够，如果内存不足够，将内存中Count值小的部分<Key,Value>写回磁盘；如果内存足够查看是否还有未计算的<Key,Value>，如果有未计算的<Key,Value>，将未计算的<Key,Value>调入内存进行计算并返回(3.1.1)继续执行；如果没有未计算的<Key,Value>则结束；
所述外聚合具体包括：
(3.2.1)将<Key,Value>调入内存进行计算，将计算结果写入磁盘，记为S<Key,Value>；
(3.2.2)将磁盘中的S<Key,Value>重新调回内存，执行内聚合的操作。
本发明的有益效果体现在：
(1)本发明通过建立倒排索引，提升检索速度的同时，使<Key,Value>在内存中进行有效的聚合，建立索引，提升匹配速度。同时考虑到，在进行内聚合时，防止内存溢出的问题，在合并的过程中检查内存是否足够，如果内存不够，则将部分进行合并次数较少的<Key,Value>，即Count值较小的<Key,Value>，先写回磁盘来防止内存溢出。
(2)本发明根据数据的特点，保证计算结果正确的前提下，选择相应的聚合方式，在减少I/O的访问次数的同时；减少生成的<Key,Value>数量，从而减少传输<Key,Value>的通信量。
附图说明
图1为基于MapReduce的Map端数据的聚合方法的测试阶段流程图。
图2为基于MapReduce的Map端数据的聚合方法的内聚合方法流程图。
图3为基于MapReduce的Map端数据的聚合方法的外聚合方法流程图。
具体实施方式
下面结合附图举例对本发明作进一步描述。
本发明旨在解决MapReduce计算框架下Map端数据聚合方法效率低和Map端计算结果过多的问题。提出了一种基于MapReduce的Map端数据的聚合方法，在内存中对Map计算后的键值对进行有效的聚合，在确保输出结果正确的前提下，减少I/O的访问次数；同时减少生成的键值对，来减少传输的通信量。
如图1所示，该方法包括以下两个阶段，测试阶段和聚合阶段。
测试阶段：通过测试阶段来验证所使用Map端的Map函数中的算法是否适合进行内聚合。因为有些Map函数中的算法对输入数据的输入顺序敏感，可能会导致计算结果出错。而内聚合方法和外聚合方法不同之处就是数据的输入顺序的不同。内聚合方法是在内存中Map函数的计算过程中进行的，计算完一部分后就进行聚合；外聚合方法是在Map函数将所有数据计算完存入磁盘后，在调入内存进行聚合的。
聚合阶段：若测试通过，则进行内聚合，即使用内聚合方法对Map端计算后的数据进行聚合；若测试未通过，则进行外聚合，即使用外聚合方法对Map端计算的后的数据进行聚合。
两个阶段具体的步骤如下：
1.测试阶段。测试阶段的任务是测试Map端计算后的数据是否能够进行内聚合方法，具体做法是将要进行计算的部分数据通过内聚合方法和外聚合方法计算后，比较得到的结果是否相同。因为使用的数据少，所以时间测试阶段使用的时间将很短，相对于整个MapReduce的计算总时间，可以忽略不计。如图1所示，具体步骤如下：
(1)分别通过外聚合和内聚合计算出相应的结果。
(2)比较两个结果是否相同。
(3)若相同则进行内聚合，若不相同则进行外聚合。
2.聚合阶段。包括内聚合方法和外聚合方法。
(1)内聚合方法：内聚合方法的作用是将聚合操作放置到内存中进行。首先，基于对内存的<Key,Value>中的Key建立倒排索引，即<Key,Address>，其中Address是<Key,Value>在内存中的地址。其次，为了在内存不足时，能够及时的将匹配次数少的部分<Key,Value>调出内存，对Address建立匹配次数Count的索引。经过匹配后，将匹配到的<Key,Value>进行合并。每完成一次<Key,Value>的内聚合后，当有新的<Key,Value>调入内存时，要对内存容量进行检查，如果内存足够，查看是否还有未计算的<Key,Value>，如果有将未计算的<Key,Value>，将未计算的<Key,Value>调入内存继续计算；如果内存当前容量不足够，要将内存中Count值小的部分<Key,Value>写回磁盘。如图2所示，具体步骤如下：
1)建立<Key,Value>倒排索引：根据读入的<Key,Value>中Key值建立倒排索引，在索引中记录<Key,Address>,Address为<Key,Value>在内存中的地址值。
2)对Address建立指向Count的索引：为了在内存不足时，能够及时的将匹配次数少的<Key,Value>调出内存，对Address建立匹配次数Count的索引。
进行匹配，将匹配成功的<Key,Value>进行合并。
3)在进行下次匹配之前，查看内存是否足够，如果内存不足够，将内存中Count值小的部分<Key,Value>写回磁盘；如果内存足够查看是否还有未计算的<Key,Value>，如果有未计算的<Key,Value>，将未计算的<Key,Value>调入内存进行计算并返回1)继续执行；如果没有未计算的<Key,Value>则结束。
(2)外聚合方法：<Key,Value>外聚合模块的作用是将聚合操作放在Map端的Map函数计算完成后统一进行。如3所示，具体步骤如下：
1)将<Key,Value>调入内存进行计算，将计算结果写入磁盘。记为S<Key,Value>。
2)将磁盘中的S<Key,Value>重新调回内存，执行内聚合的操作。
具体实例为：将1000个<Key,Value>随机分成10份，平均每个Map端进行100个<Key,Value>的相关计算，使用传统的方法则每个Map端需要2次I/O的访问，即一共需要20次I/O访问，使用改进的方法则每个Map端在最好情况下，只需要1次I/O的访问，即一共需要10次I/O访问。虽然部分情况是需要2次I/O的访问，但总体的I/O的平均访问次数为15次。同时在只需要1次访问I/O的情况下，可以节省1次所有<Key,Value>在内存中装载和卸载时所耗费的时间，系统的整体性能可以得到进一步提升。

Claims (1)

1.一种基于MapReduce的Map端数据的聚合方法，其特征是：
(1)分别通过外聚合和内聚合计算出相应的结果；
(2)比较两个结果是否相同；
(3)若相同则进行内聚合，若不相同则进行外聚合；
所述内聚合具体包括：
(3.1.1)建立<Key,Value>倒排索引：根据读入的<Key,Value>中Key值建立倒排索引，在索引中记录<Key,Address>,Address为<Key,Value>在内存中的地址值；
(3.1.2)对Address建立指向Count的索引，进行匹配，将匹配成功的<Key,Value>进行合并；
(3.1.3)在进行下次匹配之前，查看内存是否足够，如果内存不足够，将内存中Count值小的部分<Key,Value>写回磁盘；如果内存足够查看是否还有未计算的<Key,Value>，如果有未计算的<Key,Value>，将未计算的<Key,Value>调入内存进行计算并返回(3.1.1)继续执行；如果没有未计算的<Key,Value>则结束；
所述外聚合具体包括：
(3.2.1)将<Key,Value>调入内存进行计算，将计算结果写入磁盘，记为S<Key,Value>；
(3.2.2)将磁盘中的S<Key,Value>重新调回内存，执行内聚合的操作。
CN201610899802.XA 2016-10-14 2016-10-14 一种基于MapReduce的Map端数据的聚合方法 Active CN106484879B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201610899802.XA CN106484879B (zh) 2016-10-14 2016-10-14 一种基于MapReduce的Map端数据的聚合方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201610899802.XA CN106484879B (zh) 2016-10-14 2016-10-14 一种基于MapReduce的Map端数据的聚合方法

Publications (2)

Publication Number Publication Date
CN106484879A true CN106484879A (zh) 2017-03-08
CN106484879B CN106484879B (zh) 2019-08-06

Family

ID=58269694

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201610899802.XA Active CN106484879B (zh) 2016-10-14 2016-10-14 一种基于MapReduce的Map端数据的聚合方法

Country Status (1)

Country Link
CN (1) CN106484879B (zh)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110399397A (zh) * 2018-04-19 2019-11-01 北京京东尚科信息技术有限公司 一种数据查询方法和系统
CN114265849A (zh) * 2022-02-28 2022-04-01 杭州广立微电子股份有限公司 数据聚合方法及系统

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101183368A (zh) * 2007-12-06 2008-05-21 华南理工大学 联机分析处理中分布式计算及查询海量数据的方法和系统
CN103198099A (zh) * 2013-03-12 2013-07-10 南京邮电大学 基于云计算的面向电信业务的数据挖掘应用方法
CN103440246A (zh) * 2013-07-19 2013-12-11 百度在线网络技术（北京）有限公司 用于MapReduce的中间结果数据排序方法及系统
US20140215178A1 (en) * 2013-01-31 2014-07-31 International Business Machines Corporation Resource management in mapreduce architecture and architectural system

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101183368A (zh) * 2007-12-06 2008-05-21 华南理工大学 联机分析处理中分布式计算及查询海量数据的方法和系统
US20140215178A1 (en) * 2013-01-31 2014-07-31 International Business Machines Corporation Resource management in mapreduce architecture and architectural system
CN103198099A (zh) * 2013-03-12 2013-07-10 南京邮电大学 基于云计算的面向电信业务的数据挖掘应用方法
CN103440246A (zh) * 2013-07-19 2013-12-11 百度在线网络技术（北京）有限公司 用于MapReduce的中间结果数据排序方法及系统

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
YANFENG ZHANG，QIXIN GAO，ET AL.: "《imapreduce: A distributed computing framework for iterative computation》", 《JOURNAL OF GRID COMPUTING》 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110399397A (zh) * 2018-04-19 2019-11-01 北京京东尚科信息技术有限公司 一种数据查询方法和系统
CN114265849A (zh) * 2022-02-28 2022-04-01 杭州广立微电子股份有限公司 数据聚合方法及系统

Also Published As

Publication number Publication date
CN106484879B (zh) 2019-08-06

Similar Documents

Publication Publication Date Title
WO2022105805A1 (zh) 数据的处理方法及存算一体芯片
CN110308980A (zh) 数据的批量处理方法、装置、设备及存储介质
CN107391268A (zh) 服务请求处理方法及装置
CN107392308A (zh) 一种基于可编程器件的卷积神经网络加速方法与系统
CN113821332B (zh) 自动机器学习系统效能调优方法、装置、设备及介质
CN114186693B (zh) 一种量子操作系统的调度方法、系统、装置及计算机介质
CN110362409A (zh) 基于多种类型的资源分配方法、装置、设备及存储介质
CN115150471B (zh) 数据处理方法、装置、设备、存储介质及程序产品
CN106325756A (zh) 一种数据存储、数据计算方法和设备
CN103425536A (zh) 一种面向分布式系统性能测试的测试资源管理方法
WO2022188575A1 (zh) 一种超参数调优方法、装置及存储介质
CN109191287A (zh) 一种区块链智能合约的分片方法、装置及电子设备
CN114429195B (zh) 混合专家模型训练的性能优化方法和装置
US12126547B2 (en) Method and system for resource governance in a multi-tenant system
CN111949681A (zh) 数据的聚合处理装置、方法和存储介质
CN105930417A (zh) 一种基于云计算的大数据etl交互式处理平台
CN106484879B (zh) 一种基于MapReduce的Map端数据的聚合方法
CN109240644A (zh) 一种用于伊辛芯片的局部搜索方法及电路
EP4044014A1 (en) Data reduction method and apparatus, computing device, and storage medium
CN107395708A (zh) 一种处理下载请求的方法和装置
CN117971906B (zh) 一种多卡协同数据库查询方法、装置、设备及存储介质
WO2019104844A1 (zh) 货币基金系统自动性能测试方法、装置、设备及存储介质
CN110765082B (zh) Hadoop文件处理方法、装置、存储介质及服务器
CN109829678A (zh) 一种回滚处理方法、装置以及电子设备
CN110019043A (zh) 一种区块链数据存储方法

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant