论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　标准重分区连接操作在一个单独的MapReduce工作中完成：Map阶段进行数据的预处理，Reduce阶段进行连接查询操作。其具体执行步骤如下。

　　⑴MapReduce框架将巨型表User和Log分割成M个大小固定的块。

　　⑵在Map阶段，每个Mapper读取一个块，继而提取出该块中每个记录的连接键值join-key；同时生成含有表标记tag的记录tagrecord，用以识别该记录来自于哪一张表。Mapper输出该块的（join-key，tagrecord）序列并存入缓存。

　　⑶MapReduce框架的Shuffle过程对（join-key，tagrecord）序列进行分组、排序和归并。相同join-key的记录被分到一组，并输出给Reducer。

　　⑷在Reduce阶段，每个Reducer首先按tagrecord信息（该记录来自于表User或Log）将输入的记录分为两组，并分别存入各自的缓存BU和BL中，然后将两组信息进行笛卡尔积运算，进而实现查询。

　　标准重分区连接中存在的问题是：User或Log表中的所有记录都必须写入缓存。然而若|User|<<|Log|时，来自于Log中的记录可能导致内存溢出。

　　2.2改进的重分区连接算法

　　为解决标准重分区连接中可能存在的缓存溢出问题，标准重分区算法可做如下改进。

　　⑴在map函数中，将输出的二元组序列（join-key，tagrecord）改为（join-key-tag，tagrecord），加入表标识tag保证来自于User的记录一定排列在Log的记录之前。

　　⑵在MapReduce框架的shuffle阶段自定义分区函数，使得后续所有计算只根据join-key-tag中的join-key部分来进行。

　　做出改进后，表User中的记录一定会在Log记录之前，所以只有User中的记录需要存入缓存BU，而Log中的记录则以数据流的形式快速读出并与相关的User中的记录进行连接并输出结果。

　　改进的重分区连接算法虽然有效地改进了标准算法中的缓存问题，降低了内存溢出的可能，但在mapreduce的shuffle阶段仍需对表User和Log进行排序并通过网络传输数据信息，该操作是连接查询的主要执行开销，会大幅降低其执行效率。

　　2.3改进重分区连接算法的预处理

　　在重分区连接中，如果表User和Log中的数据信息在进行连接操作之前已经按连接键值分区完成，则shuffle阶段的开销就能实现有效降低。该预处理可以通过以下方式实现：表Log在日志记录生成时根据join-key进行分区，而User表则在将其加载到分布式文件系统中时根据join-key进行预分区。从而在查询时，User和Log中相互匹配的分区就能直接进行连接查询。

　　对比平行关系数据库管理系统，由于分布式文件系统独立决定每一个数据块的存放位置，所以上述方法不能保证表User和Log的相互匹配的分区存放在同一个物理节点中。因此，查询时必须使用直接连接策略。即每个map任务在Log的一个片段Li上进行。在初始化阶段，Mapper从分布式文件系统中取出表User的一个片段Ui，若其尚未进入本地存储系统则将为其建立内存哈希表HUi；然后map函数扫描Li中的每个记录并尝试连接哈希表HUi。由于分区的数量是可选的，因此该方法确保每一个Ui都能装入内存。

　　3精简连接查询数据量的预筛选

　　上述三种重分区连接算法都是从如何减少运算过程中产生的缓存及传输的数据量的角度来提高连接查询效率，但却忽略了连接查询本身的计算数据量的精简，即无论使用上述哪一种算法进行重分区连接查询，其对应的关系代数都没发生实质性的优化，而始终为：

　　换言之，进入MapReduce框架的数据量即最初分块处理和Mapper都仍然面临着（mU×lenU）+（mL×lenL）字节的数据量，而Reduce阶段的笛卡尔积运算仍将产生具有（mU×lenU）×（mL×lenL）字节的庞大的中间结果，并需对其进行最终结果筛选。

　　但根据现实数据的处理情况可知，在MapReduce框架上实现的多个大型表之间的连接运算在大多数情况下仍是等值连接，并且最终从查询结果中获取的也只是其中某几个列的信息。因此，基于MapReduce框架的重分区连接算法还可以通过对大量数据信息进行筛预选处理的方法来降低进行连接查询的数据量，从而进一步减少缓存的使用空间并有效降低shuffle阶段的数据传输造成的网络开销。

　　根据关系代数优化的典型启发式规则，上述关系代数表达式可优化为：

　　若查询结果中不包含重复列的信息，则该关系代数能进一步优化为自然连接运算：

　　其中，为自然连接运算符。

　　上述优化表达式说明表User和Log在进入MapReduce框架进行连接查询之前，可以先对大量数据进行数据的预筛选，使与结果无关的数据不参与庞大的连接运算。根据传统MapReduce框架的工作原理，该筛选操作可以加载在该框架最初的文件分块阶段中。具体操作步骤如下。

　　⑴将表User分块的同时将其进行一遍扫描：筛选出满足查询条件CUser的行的同时，投影出该行中最终查询结果所需的分量Col1，Col2，…，Coln和连接列分量UserID，构成一个中间结果行，将其存入到分块中。当一个块放满后，将中间结果写入下一个块。

　　⑵同理地，将表Log分块的同时将其进行一遍扫描：筛选出满足查询条件CLog的行的同时，投影出该行数据中最终查询结果所需的分量Col1，Col2，…，Colm和连接列分量UserID构成一个中间结果行，将其存入到分块中。

　　⑶而后再将这些块分配给Mapper进行后续操作。

　　若表User中满足查询条件CUser的元组共有mU'行，每行所需的分量Col1，Col2，…，Coln和UserID的数据量为lenU'字节；表Log中满足查询条件CLog的元组共有mL'行，每行所需的分量Col1，Col2，…，Colm和UserID的数据量为lenL'字节。则由此可知，进入MapReduce框架的数据量减少为（mU'×lenU'）+（mL'×lenL'）字节，而最终的连接查询面对的中间结果也减少为（mU'×lenU'）×（mL'×lenL'）字节。

　　若有mU'<4未来工作展望

　　本文提出的预筛选的方法在一定程度上能提高整个MapReduce框架的连接查询的执行效率，但其算法复杂度并没有得到质的提升。即若表User或Log中所有的行都分别满足查询条件CUser和CLog，且要求查询两张表连接之后所有列，则预筛选方法对数据信息量的降低将起不到明显作用。后续的研究是对该问题进行深入探讨，以找出降低算法复杂度的方式，从本质上提高整个查询运算的效率。

　　参考文献（References）：

　　[1]VMwarevCAT团队.VMwarevCAT权威指南：成功构建云

　　环境的核心技术和方法[M].机械工业出版社，2014.

　　[2]董西成.Hadoop技术内幕：深入解析MapReduce架构设计

　　与实现原理[M].机械工业出版社，2013.

　　[3]DonaldMiner，AdamShook.MapReduce设计模式[M].人民

　　邮电出版社，2014.

　　[4]DeanJ，GhemawatS.MapReduce：SimplifiedData

　　ProcessingonLargeClusters[C].Proc.ofOSDI'04.SanFrancisco：[S.n.]，2004.

　　[5]BlanasS，RaoJ，TianY，eta1.Acomparisonof

　　joinalgorithmsforlogprocessinginMapReduce[C].Proceedingsofthe2010ACMSIGM0DInternationalConferenceonManagementofData，2010.