MapReduce下的双向等价连接算法分析

沙特国王大学学报MapReduce下的双向等价连接算法分析Amer F.萨拉赫？阿特夫？拉巴？巴达尔奈赫约旦科技大学计算机信息系统系Box 3030，Irbid 22110，Jordan阿提奇莱因福奥文章历史记录：2020年1月21日收到2020年4月21日修订2020年5月10日接受2020年5月15日网上发售保留字：大数据MapReduceEqui-JoinHadoopA B S T R A C T从异构源收集的大规模数据集通常需要连接操作来提取有价值的信息。MapReduce是一种用于大规模数据处理的高效编程模型。然而，它在处理异构数据集时存在一定的局限性。在这项研究中，我们回顾了最先进的战略，连接两个数据集的基础上的equi-join条件，并提供了每个策略的详细实现。我们还提出了一个深入的分析，连接策略，并讨论其特点和局限性，以帮助读者选择最有效的策略。最后，我们概述了未来的连接处理系统有趣的方向©2020作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。内容1.导言. 10742.背景工作10752.1.MapReduce概述10752.2.相关工作10763.MapReduce 1076中的Equi-Join算法3.1.MapReduce 1076中的标准equi-joins3.1.1.地图侧连接10763.1.2.还原侧接头10773.2.基于过滤器的连接10783.2.1.半连接10783.2.2.Bloom加入10803.2.3.自适应过滤器连接10813.3.不对称连接10823.4.MapReduce变体10824.MapReduce 1083中的equi-Join算法分析5.结论1084竞争利益声明参考文献1085*通讯作者。电子邮件地址：amerb@just.edu.jo（A.F.Al-Badarneh），sarababa13@cit.just.edu.jo（S.A. Rababa）。沙特国王大学负责同行审查1. 介绍许多技术趋势的进步，例如智能设备、物联网（IoT）、云计算服务、基于web的服务和社交网络，已经促成了每天以前所未有的速度生成大量数据。这些技术导致了一个时代的出现，https://doi.org/10.1016/j.jksuci.2020.05.0041319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comA.F. Al-Badarneh，S.A.Rababa/ Journal of King Saud University1075大数据，处理千兆字节，兆字节，甚至千万亿字节数据的时代。值得注意的是，大数据分析已经成为计算机科学领域最热门的话题之一。在这个充满挑战的新世界中，数据无处不在，驱动力是访问不断增加的数据量以及我们不断提高的技术能力，以挖掘这些数据以获得商业见解（Marr，2015）。根据国际数据公司（IDC）的报告（Reinsel等人，2018年），卷我们在2018年创建的数据达到约19泽字节（Zetta =1021），预计到2025年，我们创建和复制的数据将达到163泽字节。在大数据革命之前，企业使用传统的数据库管理系统来存储和分析数据。在大数据的背景下，这样的系统经历了糟糕的性能和有限的存储容量。这是由于大数据的特点以及这些系统缺乏可扩展性和灵活性。工业界和学术界已经开发了各种框架来克服传统数据库管理系统处理大规模 数 据 的 局 限 性 。 其 中 包 括 ： Google MapReduce （ Dean 和Ghemawat ， 2008 ） ， Yahoo PNUTS （ Cooper 等 人 ， 2008 ） 、Microsoft SCOPE （ Chaiken 等 人 ，2008 ） 和 Apache Spark（Zaharia等人，2016年）。这些框架结合了商品机器的基础设施，可以扩展到数百万台服务器，并可以存储高达EB（Exa = 1018）的数据库。此外，这些框架具有强大的故障处理功能，可以在一个合理的时间，以获取有价值的信息。MapReduce（Dean and Ghemawat，2008）是一种高效的编程模型，运行在无共享集群上，用于处理大规模数据。它最初是为处理和生成大规模数据而设计的，有两个功能 ：map和reduce。事实上，MapReduce是最流行的框架之一，在大数据技术领域。这是因为它提供了显著的特性，包括编程的简单性、高可伸缩性、容错性和灵活性。然而，尽管MapReduce具有这些特性，但它在执行需要处理异构数据集的分析操作方面存在一些限制。其中一个重要的操作是连接，它将来自两个或多个数据集的相关记录组合在一起。MapReduce中join操作的主要问题是大量与join无关的记录通过网络连接从map阶段转移到reduce阶段。在这项研究中，我们主要集中在双向equi-join算法在MapReduce的上下文中，这是最常见的类型的连接条件。多路连接可以使用一系列双向连接来实现。因此，本文分析的连接策略本研究的主要目的是为MapReduce中等价连接方法的研究和未来连接优化的研究提供参考此外，我们的分析比较国家的最先进的equi-joins协助读者采用最有效的连接方法，根据他们的应用程序。本文的其余部分组织如下：第2提供了MapReduce框架的概述，并简要回顾了分析MapReduce中连接算法的相关工作第三介绍了MapReduce环境下等价连接算法的具体实现。第4节对这些算法进行了分析，并总结了它们的优缺点。最后，我们在第5中总结并讨论未来的工作。2. 背景相关工作在本节中，我们将提供MapReduce框架的概述，并简要回顾分析MapReduce中连接算法的相关工作。2.1. MapReduce概述MapReduce 是 一 种 用 于 处 理 海 量 数 据 集 的 高 效 编 程 模 型 。MapReduce框架的简单性在于将大规模数据处理为简单的工作单元，即map和reduce函数。程序员只需要集中在这些简单接口的逻辑上，把复杂的任务并行化、负载平衡、故障处理和数据分发留给框架。要创建MapReduce作业，程序员只需要在map和reduce函数中定义逻辑。然后，该框架在一个商用机器集群上并行运行这些函数的多个实例。 当提交MapReduce作业时，会发生以下步骤序列（Dean和Ghemawat，2008），如图所示。一曰：a) MapReduce将输入数据分成M个固定大小的块，称为输入拆分，并在集群中复制三次。然后，将M个分割传递到集群中的参与节点。随后，MapReduce框架在这些节点上启动程序的许多副本b) 集群的主节点挑选空闲的worker，并为每个worker分配一个map任务或reduce任务。注意，map任务需要在任何reduce任务开始之前完成它们的执行，因为map任务的输出最终会被馈送到reduce任务。c) 每个分配了map任务的worker遍历输入拆分的每个记录。它从每个记录中解析出一个键/值对，并应用用户定义的映射函数来产生另一个键/值对，称为中间键/值对。然后，map任务的输出被写入workerd) 内存缓冲区的内容定期写入工作节点的本地磁盘，并通过分区函数划分为R个区域。然后将R区域的位置传递给主节点，主节点又将这些位置转发给reduceworker。e) 每个reduce worker使用远程进程从map worker的本地磁盘读取其保留的Fig. 1. MapReduce程序的扩展名。1076A.F. Al-Badarneh，S.A.Rababa/ Journal of King Saud University在通话期间。当所有的中间数据都被复制到reduce worker的目录中时，它开始按键对数据进行排序，以便将所有出现的相同键组合在一起。如果中间数据不适合存储器，reduce worker，则需要外部排序f) 然后，每个reduce worker遍历排序的中间数据的每个键，并应用用户定义的reduce函数。换句话说，reduce worker处理一组中间键/值对以产生一组精简的键/值对。最后，reduce函数的输出被附加到reduce任务的最终输出文件2.2. 相关工作连接操作是关系数据库查询处理中最基本、最昂贵、最常用的操作之一（Mishra and Eich，1992：Graefe，1993）。基本上，它是一个重要的操作，根据预定义的条件组合来自两个或多个数据集的记录。已经进行了许多研究来讨论MapReduce环境中大规模数据的这种操作的技术、性能和优化（Afrati和Ullman，2010：Zhanget al.， 2012 年： Bruno 等人，2014 年：Gavagsaz 等人， 2019年）。 Blanas等人（2010）提供了MapReduce中用于日志处理的几种等价连接算法的详细实现。具体来说，在MapReduce的上下文中引入了重新划分连接、广播连接、半连接和每拆分半连接。作者在一个100节点的Hadoop集群上对上述连接算法进行了实验评估，并提出了几种预处理技术，以进一步提高连接性能。然而，这项研究只考虑了五个连接算法的equi-joins上下文中的MapReduce。作者（Lee et al.，2012 a，b）描述了MapReduce框架的各种技术方面，并讨论了其优缺点。此外，还回顾了MapReduce优化，并讨 论 了 几 个 并 行 数 据 处 理 问 题 ， 例 如 连 接 运 算 符 。 他 们 将MapReduce中的连接策略大致分为两类：Map端连接和Reduce端连接 ， 并 简 要 解 释 了 这 些 策 略 。 DoulkerandNrvåg （ 2014 ） 在MapReduce框架的背景下扩展了查询处理方面的范围，并提供了对MapReduce限制的深入分析。他们讨论了不同类型的连接条件，包括equi-join，并简要介绍了每个类别下的几种方法。分析了基于不同阶段的连接算法，提高了连接性能。Phan等人（2016）提供了一种系统的方法来比较几种基于过滤器的equi-join算法，并强调了在I/O，CPU和通信成本方面早期删除冗余数据的有效性。他们从理论上和实验上研究了在MapReduce中使用过滤器扩展equi-join算法的影响，并描述了过滤器非常有效的情况。在我们的工作中，我们扩大了MapReduce中的equi- join算法的范围，并对算法进行了深入的分析。3. MapReduce中的Equi-Join算法在本节中，我们将提供MapReduce中最先进的equi-join算法的详细实现，并解决其特性和局限性。我们将equi-join算法分为四类：MapReduce中的标准Equi-Joins、基于过滤器的Joins、对斜不敏感的Joins和MapReduce变体。3.1. MapReduce中的标准equi-joinsMapReduce中的标准连接算法可以根据连接操作的执行阶段进行粗略映射端连接在映射阶段产生连接结果，因为没有从映射器发送到归约器的中间记录。相比之下，reduce端的连接发送大量的中间记录，并在reduce阶段产生连接结果在这些连接算法的性能和可行性之间存在一个折衷，性能越好，可行性越小。在本小节中，我们将介绍最先进的映射端和归约端连接算法。3.1.1. 地图端连接Hadoop框架为映射端连接（White，2015）提供了默认实现，也称为映射合并连接（Leeet al.，2012年a、b）。映射合并连接由三个MapReduce作业组成，其中第一个和第二个作业作为完整的MapReduce作业运行它们基于连接键将输入数据集划分和排序到相等数量的分区中，使得具有相同连接键的所有记录驻留在相同分区中。虽然这听起来是一个严格的要求，但MapReduce作业的输出符合其描述。因此，映射合并连接可以从处理来自先前MapReduce作业的输入数据集的输出中受益，这些作业具有相同数量的归约器，相同的连接键和相同的分区函数。映射合并连接在第三个作业（仅映射作业）中执行连接操作。第三个作业中的每个映射器处理来自一个输入数据集的一个分区，并将另一个数据集的对应分区加载到内存中的哈希表中。然后，map函数执行合并联接并将联接结果写入Hadoop分布式文件系统（HDFS）。图2示出了使用映射合并联接的联接操作的示例。如图所示，对输入数据集进行划分和排序使第三个作业更容易实现，因此提高了连接性能。然而，如果输入数据集没有预先分区和排序，那么第一个和第二个MapReduce作业会降低算法的整体性能。地图端分区合并连接（Pigul，2012）是一个改进映射合并联接的。其主要目标是使用第二数据集的按需读取来避免内存溢出。然而，除了离散读取的开销之外，它继承了其祖先算法的相同缺点。地图合并联接和地图端分区合并联接适用于大型输入数据集。相反，如果至少有一个输入数据集足够小，可以放入节点的缓存中，那么片段复制连接（Andreas，2010：Gates，2011）就例如，考虑两个数据集R和L，一个参考表和一个日志表，分别。在大多数数据集连接应用程序中，引用表的大小远小于日志表的大小，即， |R||L|. 片段复制连接作为仅映射作业运行。它将较小的数据集R复制到较大数据集L的所有映射器，并在映射阶段执行连接操作。图3示出了使用片段复制连接的R和L的连接处理的示例。首先，Hadoop框架将R分配给L的所有地图任务。其次，L的每个map任务读取分布式R，并在map函数开始之前，在设置函数期间使用连接键构建内存中的哈希表。最后，在map函数中，每个map任务遍历L的每个记录，并探测哈希表中记录片段复制连接算法是一种有效的地图端连接算法然而，它只能在输入数据集之一的大小足够小以适合节点的内存的情况下执行为了解决这个问题，有几种方法A.F. Al-Badarneh，S.A.Rababa/ Journal of King Saud University1077图二. 映射合并连接实现。见图4。标准的重新分区连接实现。图三.片段复制连接实现。已经介绍了，其中一些是反向映射连接（Luo和Dong，2010）和广播连接（Blanas等人， 2010年）。反向映射连接为映射函数中L的每个输入分割构建一个哈希表，然后，它在清除函数中迭代R的每个记录，并探测哈希表中记录最后，它将连接结果写入HDFS。广播连接结合了片段复制连接和反向映射连接的实现。如果R的大小大于L的输入分割的大小，则执行反向映射连接否则，执行片段复制连接。虽然反向映射连接和广播连接扩展了输入大小的容量，但随着输入大小的增加和复杂性的增加，连接性能会下降所有map端连接算法都消除了中间结果的网络传输开销，这与reduce端连接不同。因此，映射端连接优化了连接性能。但是，对于输入数据集的特征有一些限制，并且大多数情况下，需要额外的MapReduce作业来满足这些限制。3.1.2. 减少边连接Reduce端连接是MapReduce中最常见的连接算法。 标准再分配连接（Blanas等人， 2010）是常用的reduce-side join算法之一。Hadoop提供了标准重新分区连接的默认实现（White，2015），它在一个MapReduce作业中运行。考虑图中所示的例子。 4、假设R和S是输入数据集，并且Reduce任务的数量等于2。在映射阶段，每个映射器遍历输入拆分的每个记录，并输出连接属性作为键，输出标记以及其他属性作为值，记录标记的目的确定其来源。换句话说，每个映射器为每个输入记录输出一个键、标记值>对然后，MapReduce框架对map阶段的输出进行分区、排序和合并，使得具有相同连接键的所有记录被分组在一起，并最终馈送到reducer。接下来，对于每个连接键，reduce函数根据标记将记录分为两个集合，并缓冲每个集合的记录最后，它在缓冲的记录之间执行叉积，并将连接结果输出到HDFS。标准的重划分连接是一个通用的算法，它对输入数据集没有限制，不像地图端连接算法。然而，它也有一些缺点。标准重分区连接的主要缺点是所有的输入记录都必须发送到reducer，包括与连接操作无关的记录。这些记录通过网络连接传输到归约器，在归约阶段需要额外的处理时间因此，可能发生性能下降和Blanas等人（2010年）介绍了改进的重划分连接，对标准的重新划分连接进行优化，以解决缓冲问题。标准reparti-tion join的缺点之一是，来自两个数据集的给定键的所有记录必须在reducer的内存中缓冲在输入数据集高度偏斜或者两个数据集中的键的数量相对较小的情况下，则很可能给定键的所有记录可能不适合于归约器改进的重分区连接通过引入三个关键更改来修复标准重分区连接的缓冲问题首先，每个映射器的输出它为每个输入记录输出关键字标签、标签值每个表的标记都是以这样一种方式生成的，即较小表的记录将被排序在较大表的记录第二，为了保证来自两个表的相同连接键将被trans-transform-1078A.F. Al-Badarneh，S.A.Rababa/ Journal of King Saud University在相同的reducer中，改进的重新分区连接覆盖分区函数的默认实现，使得仅从记录的连接键而不是复合键计算散列码reducer中的分组函数也被覆盖，以确保所有记录都基于连接键进行分组最后，由于来自较小表的记录被保证在来自较大表的那些记录之前，所以每个reducer将仅缓冲较小表的记录并且流式传输较大表的记录以针对每个联接键执行联接图5示出了使用改进的重新分区联接来联接R和S虽然改进的重划分连接解决了缓冲问题，但与标准版本相比，它增加了网络传输的开销，因为每个记录需要标记两次。此外，与标准版本一样，大量冗余记录通过网络传输。Atta（2010）介绍了一种混合方法，它是map端和reduce端连接的组合，称为Hybrid Hadoop Join。与映射合并连接一样，输入数据集应该根据连接键划分为相同数量的分区。与标准的重新划分连接一样，连接操作在reduce阶段执行。但是，与映射合并连接不同，它只需要预先划分一个输入数据集。与标准的重新分区连接不同，不需要标记中间记录。混合Hadoop连接在两个MapReduce作业中实现。第一个作业作为完整的MapReduce作业运行，它基于连接键将较小的数据集R划分和排序为i个分区。在第二份工作中。每个map- per遍历S的输入分割中的每个记录，并将键/值对传递给分区函数，分区函数又以与R分区相同的方式对S进行分区和排序。然后，图五. 改进了重新分区连接的实现。分割函数的输出被馈送到与R的分割数相等的多个缩减器，即，i减速器。接下来，在每个reduce任务中，setup函数根据reducer的编号将对应的分区Ri加载到内存中的哈希表中。最后，reduce函数探测哈希表对于Si的每个输入键，并执行连接。图6示出了使用混合Hadoop联接的联接处理的示例。混合Hadoop连接消除了标准重新分区连接中的标记开销。此外，它限制了映射合并连接的先决条件，因为只需要预先对输入数据集之一进行分区。但是，它也继承了映射端和归约端连接的缺点。此外，应适当确定分区的数量。3.2. 基于过滤器的连接通常，在等连接处理中，两个数据集中的许多记录对连接操作没有贡献。例如，考虑FaceBookR包含超过20亿用户，L包含给定时间段内活动用户的日志数据。在这种情况下，可以改进R和L的结合，因为在给定的时间段内，活动用户的数量可能远小于参考表R中的用户的总数。因此，过滤冗余记录可以显著减少通过网络连接传输的数据量，以及连接操作的处理时间。在归约端连接中，过滤冗余记录节省了将大部分R从映射器转移到归约器的成本，并改善了归约器的处理时间。在映射端联接中，过滤冗余记录减少了传输到映射器的数据量，并最大限度地减少了每个映射器使用的内存总量。但是，过滤冗余记录需要使用辅助数据结构，例如Bloom filter，并且需要额外的MapReduce作业来构建它们。使用辅助数据结构的连接算法可以分为三类：半连接，Bloom连接和基于自适应过滤器的连接。3.2.1. 半联接Semi-Join（Bernstein and Chiu，1981）是一个经典的连接算法，在分布式数据库处理中得到了广泛的应用。它由Blanas等人（ 2010 ） 改 编 为 MapReduce 。 使 用 MapReduce 的 半 连 接 由 三 个MapReduce作业组成。半连接的主要思想是通过使用另一个表的唯一键列表来过滤掉一个表中的冗余记录。考虑两个表R和L之间的等价连接，我们需要过滤掉引用表R中的冗余记录。第一个MapReduce作业为L的每个输入拆分运行一个map任务，并聚合一个reduce任务见图6。 混合Hadoop连接实现。A.F. Al-Badarneh，S.A.Rababa/ Journal of King Saud University1079映射器输出。在map函数中，每个映射器读取L的分割，并使用连接键构建内存中的哈希表在将每个连接键发送到reducer之前，每个映射器验证键是否已经存在于哈希表中，如果不存在，则将连接键添加到哈希表并将其发送到reducer。否则，键已经发送，映射器继续读取下一个记录。哈希表的主要好处是通过只发送map输入的唯一键来减少从mapper发送到reducer的数据总量。接下来，在reduce函数中，reducer输出每个唯一的连接键，并将其添加到名为L的输出文件中。英国. reducer的数量应该是一个的原因是将所有的唯一键合并到一个文件中，假设该文件适合节点半连接的第二个作业作为仅映射作业运行，类似于广播连接。每个映射器的设置函数加载L.uk文件到内存哈希表中。然后，map函数遍历R的每条记录并提取记录的键。最后，它探测哈希表中记录的键，并在匹配的情况下输出记录。第二个作业的输出是R中与连接操作相关的所有记录的列表，即，每个映射器输出Ri，其中Ri是R的第i个分裂中的可连接记录的列表。半连接的第三个也是最后一个作业使用广播连接在R和L当R的大小大于L的拆分大小时，标准的再划分连接是最佳选择。图7示出了使用MapReduce的半连接的示例。半连接过滤掉不与L的记录连接的R的冗余记录，并减少连接作业中传输的数据总量。然而，在R的过滤版本中仍然存在一些冗余记录，其不与L的特定分裂Li联接。例如图 7、中加入的记录数对于R1L1，R1等于1，R1中的其余记录是冗余的。 Per-Split Semi-Join是解决这个问题的一种方法，在Blanas et al. （2010年）。它分三个阶段实现与半连接相比，第一个和第二个作业涉及更多，而第三个作业使连接处理的实现成本更低。每拆分半连接的思想是根据L的每个拆分Li过滤出引用表R的记录。第一个作业作为仅映射作业运行，每个映射器迭代输入分割Li的每个记录，并输出唯一键Li的列表。uk，然后，它存储Li。文件到HDFS。第一作业的输出是文件的集合L1。uk第二个作业作为一个完整的MapReduce作业运行，它过滤掉R中的冗余记录。在map函数中，每个map- per读取输入拆分Ri的所有记录，并将它们加载到内存中的然后，map任务的cleanup函数加载每个Li。uk文件到内存中的哈希表中，并且对于每个Li. uk文件中，清除函数探测其哈希表中记录接下来，映射器的输出最终被馈送到一个缩减器，该缩减器又输出R的不同滤波版本，即，每个版本根据L的特定分裂L1被过滤。最后，第三作业运行仅映射作业以执行RLi和Li对之间的映射合并联接。图8示出了每拆分半连接的示例。半连接和每拆分半连接需要三个MapReduce作业来实现两个表之间的连接操作，这导致增加了I/O开销和网络传输量此外，多次向框架提交MapReduce作业的开销会降低整体性能。见图7。 半联接实现。见图8。 每拆分半连接实现。1080A.F. Al-Badarneh，S.A.Rababa/ Journal of King Saud University因此，Matono et al.（2015）引入了基于哈希和位置的每分裂半连接作为每分裂半连接的改进。它通过引入三个减少来扩展每分裂半连接：（1）通过传输一组散列值而不是一组唯一密钥来减少网络流量，(2)通过在第二个作业中实现join操作减少MapReduce作业的总数，（3）通过使用基于位置的方法减少磁盘I/O量基于散列和位置的每拆分半连接在两个MapReduce作业中实现连接，第一个作为仅映射作业运行，而第二个作为完整的MapReduce作业运行。图9通过示例描绘了算法的实现在第一作业的映射任务中，为了获得L的Li中的每个输入键/值对的位置信息p，运行函数被重写。然后，映射函数将每个键的散列值和键的位置P的集合最后，清除函数将每个分割的散列表HL存储为HDFS中的名为Li.hp在第二个作业中，映射函数构建散列表HRi以存储R的输入拆分Ri的记录的键/值对的散列值然后，清除函数遍历存储在HDFS中的Li.hp的每个文件，并过滤Ri的冗余记录。最后，它输出RLi作为键，r+P作为值，其中RLi是Ri的过滤版本，r+P是Ri 的可连接记录和L的分裂L i内将与r连接的一组记录接下来，reduce函数将输入值的数据结构从V这个步骤的目的是通过按位置顺序对HashMapM进行排序来提高读取L然后，reduce函数寻找位置p，以便读取Li的记录l，最后，它执行r和l之间的连接。3.2.2. Bloom加入半连接算法通过包含一个输入数据集的唯一键或其散列值的数据结构来然而，输入数据集的大小越大，构造的数据结构的大小就越大。这意味着在通过网络连接传输所构造的数据结构时将出现潜在的问题。为了解决这个问题，需要一种无论输入数据集大小如何都具有空间效率并且不会产生假阴性的数据结构。其中之一就是BloomFilter。布隆过滤器（Bloom filter，1970年）是一种用于测试集合中元素的成员资格的空间高效数据在Bloom过滤器中可能会出现假阳性，但 它 不 会 产 生 假 阴 性 。 Bloom Join （ Mackert and Lohman ，1986）是一种分布式连接算法，它使用Bloom过滤器，以可接受的误报概率过滤掉输入数据集中的冗余记录使用MapReduce的Bloom连接已经在（Palla，2009：Lam，2010）中引入考虑两个表R和S之间的等价连接操作。第一个作业为较小的表R构造布隆过滤器。在map函数中，为R的每个分割Ri构造局部布隆过滤器BFi。然后，所有的本地布隆过滤器最终被馈送到一个reducer，该reducer又使用按位OR操作合并它们，并将全局过滤器BFR写入HDFS。接下来，第二作业使用全局布隆过滤器BF_R过滤出S的每个输入分裂Si中的冗余记录，并且在归约阶段中执行联接图图10显示了Bloom join的一个例子。为了增强过滤过程，Palla（2009）和Atta（2010）使用具有不同过滤器大小的Bloom过滤器实现了reduce- join，并选择了导致最佳性能的大小，即，最小的尺寸，见图9。 减少端连接的基于哈希和位置的过滤。见图10。 Bloom join实现。A.F. Al-Badarneh，S.A.Rababa/ Journal of King Saud University1081导致最小的假阳性率。然而，这些方法没有讨论如何在MapReduce环境中有效地构建和使用Bloom过滤器。Zhang等人（2013）研究了Bloom过滤器在使用MapReduce的连接处理中的潜力。介绍了三种构建大规模数据集Bloom过滤器的策略策略1与图1所示的策略相同。 10（a）. 也就是说，每个映射器创建一个固定大小的本地Bloom过滤器，并将结果传递给一个reducer，该reducer依次合并所有本地过滤器并输出一个全局过滤器。所构造的滤波器的大小基于输入数据集R的大小来确定。策略2作为仅映射作业运行，其为R的每个输入分割Ri创建本地布隆过滤器并将其写入HDFS。 每个局部过滤器的大小取决于HDFS中每个输入分割的大小，而不是整个数据集的大小|R|. loggy3是策略1和策略2的组合，并作为一个完整的MapReduce作业运行。策略3中的每个映射器创建一个本地Bloom过滤器，并将中间过滤器传递给k个reducer。然后，每个reducer接收M/k个滤波器，其中M是映射器的数量，并且使用逐位OR操作合并它们，并且将合并的滤波器BFi写入HDFS。 图图11显示了策略2和策略3的示例。所有三种策略都被设计为保证输出滤波器具有相同的误报概率p。（Zhang等人， 2013）表明，与策略2和策略3相比，策略2在构建阶段具有最佳性能，因为它减少了过滤器的处理时间，并消除了将中间结果转移到缩减阶段的成本。然而，与其他策略相比，策略2在连接阶段的性能最差策略1在连接阶段的性能最好，但在构建阶段的性能最差与后一种策略相比，策略3在两个阶段都表现出最好的性能，如果k选择得当。到目前为止，所提到的Bloom连接算法通过过滤掉一个表中的冗余记录来有效地然而，仍然有许多中间记录，从其他表的映射器生成，实际上并不参与连接操作。因此，消除所有冗余的中间记录将显著提高连接性能。Phan等人（2013）介绍了一种解决这一问题的方法。设计了一个交集Bloom过滤器此外，介绍了三种构造交集Bloom过滤器的方法这三种方法与Zhang等人， 2013），但是具有容纳多个输入的扩展。方法1建立一对见图12。 使用方法2构造交集布隆过滤器的示例。全局布隆过滤器，BFR和BFS。方法2构建一个全局Bloom过滤器IBF;使用逐位AND运算的BFR和BFS的交集。方法3构建k个布隆过滤器;每个布隆过滤器是使用按位AND运算的R的M/k个布隆过滤器和S的M/k个布隆过滤器的交集。所有方法都保证创建的过滤器可以消除两个表中的冗余记录。然而，根据它们的成本比较，方法2是最有效的方法。图12示出了方法2的示例。使用交集过滤器的连接处理比使用R或S中的一个过滤器的连接处理更有效，因为它过滤掉了两个表中的大部分冗余记录，也提高了连接性能。然而，需要额外的I/O和处理操作来构建交集过滤器。Phan等人在（Phan等人，2016年）。通过分析成本模型和实际实验，研究了早期使用交集过滤器对双向连接、多向连接和递归连接的影响。对于双向连接算法，实现了交叉Bloom连接，并与标准的再划分连接和Bloom连接进行了比较，采用方法2建立了交叉过滤器。实验结果表明，交集Bloom连接的性能优于标准的重划分连接和Bloom连接.虽然交集滤波器可能会增加误报概率，需要更多的预处理，其过滤能力和空间效率超过其缺点。3.2.3. 基于自适应过滤器的连接Bloom连接算法通过在网络连接中传输数据之前过滤掉冗余记录，然而，独立见图11。构建Bloom过滤器的策略。1082A.F. Al-Badarneh，S.A.Rababa/ Journal of King Saud University需要MapReduce作业才能创建筛选器。因此，数据集必须被多次处理例如，交集Bloom连接处理输入数据集两次，一次用于构建交集过滤器，另一次用于执行实际连接。Koutris（2011）从理论上研究了如何在一个MapReduce作业中应用Bloom join。介绍了Bloom过滤器的两种构造和广播策略。策略A在一个节点上计算布隆过滤器，并将其广播到集群中的每个参与节点。策略B通过为所有节点并行计算本地Bloom过滤器并将它们发送到目标节点以便合并本地过滤器来克服策略A中的中央处理瓶颈。然而，与策略A相比，策略B将通信成本增加了n倍（节点数量）。虽然Koutris（2011）研究了在单个MapReduce作业中使用Bloom filter进行连接处理的几种技术，但没有提供足够的技术细节。Lee等人（2012a，b，2013）解决了实现问题，并提供了一个在单个MapReduce作业中使用Bloom过滤器进行连接处理的架构。在建议的架构中对Hadoop框架进行了两项内部修改。即，根据数据集的顺序分配映射任务的顺序，并且以分布式方式执行布隆过滤器的构造。Lee等人（2012）扩展了他们在Lee等人（2014）中的工作;Lee等人（2014）引入了基于索引的映射-过滤器-缩减连接（TMFR-Join），其测量所构造的Bloom过滤器的效率。 也就是说，如果假阳性率全局滤波器超过确定的阈值s，则它将被取消。启用，而实现reduce-side join。试验结果表明，该工艺性能稳定，接 近 缩 边 连 接 和 大 方坯 连 接 的 效 果 。 然 而 ， 引 入 的 架 构 需 要MapReduce框架的两个内部修改。3.3. 不倾斜联接基本上，MapReduce中连接操作的实现要经过四个基本阶段：映射、分区、洗牌和排序，以及reduce。在分区阶段，MapReduce框架默认调用分区函数，根据连接键的哈希值对映射器的输出进行分区。然后在混洗和排序阶段，中间结果被发送到归约器，归约器又聚集连接键并执行预定义的归约函数。因此，如果输入数据集充分偏斜，则潜在的障碍可能会降低连接性能，因为最长的运行任务决定了连接处理时间。已经进行了许多尝试来在MapReduce上下文中解决这个问题（Atta等人，2011年：Hassan和Bamha，2015年：Myung等人，2016年：Afrati 等 人 ， 2018 年 ， Gavagsaz 等 人 ， 2019 年 ） 。 Atta et al.（ 2011 ） 为 MapReduce 采 用 了 基 于 范 围 的 划 分 方 法 （ DeWitt ，1992），该方法主要将连接属性划分为记录数量大致相同的子范围，以便在后续处理中平衡工作负载。引入的偏斜处理算法（SAND Join）利用两种划分方法：简单范围划分器和虚拟处理器范围划分器（DeWitt和Ghandeharizadeh，1990）。简单范围分割器从每个输入分割中收集样本，并将它们合并到表T中。然后，它从T中检索p个样本以构造一个划分向量，该向量确定用于将连接键划分为p个划分的边界，其中p是归约器的数量。另一方面，虚拟处理器范围划分器创建n *p个 分区，其中n是整数，并以循环方式将它们分配给p个归约器。通过这种方式，处理变得更均匀地分布在还原器之间。然而，在这方面，由于没有考虑连接结果的大小，可能发生严重的负载不平衡。随 机 分 区 （ Okcan and Riedewald ， 2011 ） 是 一 种 在MapReduce中处理数据偏斜的替代方法。它已被用来实现不同类型的连接条件（Elseidy等人， 2014年：Vitorovic等人， 2016年）。该算法利用两个随机划分的数据集S和T之间的叉积，其中S被划分为m个块，T被划分为n个块。叉积空间中的行对应于m个块，列对应于n个块。然后，将空间划分为k个归约器，每个归约器覆盖空间中的一个矩形为了有效地平衡负载，以使得矩形具有近似相等的大小的方式选择k由于S和T是随机划分的，所以每个m的块必须与每个n的块连接。换句话说，随机划分以复制输入记录为代价实现了负载平衡。因此，它不适合更大的关系。Vitorovic等人（2016）试图通过引入一种称为EWH的多级负载平衡算法来避免高输入复制。它通过对连接矩阵进行采样来考虑输入和输出的属性提出了一类等权直方图，将连接矩阵划分为大小