在映射化简框架中处理数据的制作方法
在映射化简框架中处理数据的制作方法
【专利摘要】本发明公开一种用于在映射化简框架中处理输入数据的计算机实现方法，包括：在所述映射化简框架中接收对于输入数据的数据处理请求；基于所述数据处理请求，启动由所述映射化简框架中的多个映射器在所述输入数据上进行的映射操作，每个所述映射器使用聚合器来部分地将所述输入数据聚合成一个或多个中间键/值对；启动由所述映射化简框架中的多个化简器在所述中间键/值对上进行的化简操作，其中，在不排序所述中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个所述化简器使用所述聚合器来将所述中间键/值对聚合成一个或多个输出值；以及响应于所述数据处理请求而提供所述输出值。
【专利说明】在映射化简框架中处理数据
[0001]相关申请的交叉引用
[0002]本申请要求于2011年4月I日提交的，标题为“PROCESSING DATA IN A MAPREDUCEFRAMEWORK”的美国专利申请序号N0.13/078，500的优先权，该申请的公开内容通过引用并入于此。
【技术领域】
[0003]本文涉及映射化简(mapreduce)框架中的数据处理。
【背景技术】
[0004]映射化简模型由Google Inc.开发作为一种简化大规模数据处理的方式。映射化简过程的实现是根据映射化简模型而完成的。
【发明内容】
[0005]在第一方面，一种用于在映射化简框架中处理输入数据的计算机实现方法包括:在映射化简框架中接收对于输入数据的数据处理请求；基于该数据处理请求，启动由映射化简框架中的多个映射器在输入数据上进行的映射操作，每个映射器使用聚合器来部分地将输入数据聚合成一个或多个中间键/值对；启动由映射化简框架中的多个化简器在中间键/值对上进行的化简操作，其中，在不排序中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个化简器使用聚合器来将中间键/值对聚合成一个或多个输出值；以及响应于数据处理请求而提供输出值。
[0006]在第二方面，一种有形地体现在计算机可读存储设备中的计算机程序产品包括当由处理器执行时执行用于在映射化简框架中处理输入数据的方法的指令。该方法包括:在映射化简框架中接收对于输入数据的数据处理请求；基于该数据处理请求，启动由映射化简框架中的多个映射器在输入数据上进行的映射操作，每个映射器使用聚合器来部分地将输入数据聚合成一个或多个中间键/值对；启动由映射化简框架中的多个化简器在中间键/值对上进行的化简操作，其中，在不排序中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个化简器使用聚合器来将中间键/值对聚合成一个或多个输出值；以及响应于数据处理请求而提供输出值。
[0007]在第三方面，一种系统包括:至少一个处理器；以及至少一个计算机可读存储设备，其包括当被执行时致使用于在映射化简框架中处理输入数据的方法的执行的指令。该方法包括:在映射化简框架中接收对于输入数据的数据处理请求；基于该数据处理请求，启动由映射化简框架中的多个映射器在输入数据上进行的映射操作，每个映射器使用聚合器来部分地将输入数据聚合成一个或多个中间键/值对；启动由映射化简框架中的多个化简器在中间键/值对上进行的化简操作，其中，在不排序中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个化简器使用聚合器来将中间键/值对聚合成一个或多个输出值；以及响应于数据处理请求而提供输出值。
[0008]实现可以包括以下特征中的任何或所有特征。所述数据处理请求标识所述输入数据中的键的数目，并且所述方法还包括执行所标识的键的数目关于输入数据尺寸的尺寸评估，其中基于尺寸评估来选择启动使用聚合器的映射操作和化简操作。映射器和化简器使用机器集群来实现，其中尺寸评估将一个或多个机器的存储器空间纳入考虑。尺寸评估将所标识的键的数目是否比输入数据的尺寸小三个数量级纳入考虑。映射操作和化简操作中的聚合器使用哈希表。聚合器基于交换聚合函数和关联聚合函数。
[0009]实现可以提供以下优点中的任何或所有有点。可执行高性能查询聚合。可以在框架的映射端和化简端二者上使用通用聚合器。聚合器可连续执行聚合(例如，一旦每个新值变得可用，就执行聚合)。可以消除针对化简操作而排序键/值对的需求。通过在存储器中仅保持针对给定键的聚合值，可以减少存储器使用量。可以例如通过禁用排序器和添加通用聚合器来重用映射化简框架。可以放松或消除对于所有针对相同键的值必须转到相同的化简调用的要求。聚合器可以代替映射端上的组合器。聚合可以使用哈希表来执行。
[0010]在以下附图和描述中阐述了一个或多个实现的详情。从描述和附图，以及从权利要求书中将会呈现出其他特征和优点。
【专利附图】
【附图说明】
[0011]图1不出具有映射化简框架的系统的不例。
[0012]图2示意性地示出在映射化简框架中处理输入数据的示例。
[0013]图3是不例方法的流程图。
[0014]图4是可以联系本文所述计算机实现方法来使用的示例计算系统的框图。
[0015]各附图中的相似参考符号表示相似元素。
【具体实施方式】
[0016]本文描述这样的系统和技术:通过所述系统和技术,可以通过在映射端和化简端二者上使用通用聚合器来实现映射化简框架中的输入数据的处理，而不需要在化简操作之前排序中间数据。在一些实现中，使用通用聚合器的方式可以基于评估输入数据与在处理输入数据中所涉及的键的相对尺寸来使用。例如，当仅在相对较大量的数据中寻找到相对较少的键(例如，词语的数目至少比键的数目大一千倍)时，可在映射操作中聚合针对键的值，并且可将具有相同键的键/值对转发至相同的化简器。化简器继而可在化简操作中使用相同的通用聚合器。这样可以显著减少从映射操作传递到化简操作的中间数据量，并且可以消除针对化简操作而排序中间数据的需要。
[0017]图1不出具有映射化简框架102的系统100的不例。映射化简框架102可用于执行根据映射化简模型的数据处理，例如，用于对大量数据执行某些类型的分析。本文中所使用的术语“映射化简框架”意指这样的系统，其配置用于执行:(i)根据输入数据而生成一个或多个中间键/值对的至少一个映射操作；以及(ii)根据中间键/值对而生成一个或多个输出值的至少一个化简操作。映射化简框架将映射操作分配在多个程序组件(有时称为“工作者(worker)”)之间，并向每个工作者指配一个或多个映射任务。映射化简框架将化简操作分成化简任务，并将它们指配给工作者。在一些实现中，映射化简框架运行于诸如商用PC网络之类的处理设备集群上。
[0018]这里，用户可以采用计算机设备104，通过诸如因特网或用于移动设备的网络(例如，蜂窝电话网络)等任何类型的网络106，来访问映射化简框架。映射化简处理可由计算机设备上的用户程序108来启动。在一些实现中，供应广告的组织可以使用程序108来分析与广告的一个或多个方面相关的大量数据。例如，映射化简操作可以确定针对上亿个或更多个在线页面中的每个页面的反向超链接，这意味着检测出链接到给定页面的所有页面。在此类情况下，用户程序108定义相关目标页面的组，并且指定正在寻找对应的源页面。作为另一示例，映射化简操作可以处理针对在线页面的请求日志，以确定每个页面被请求了多少次。在该情况下，用户程序108标识或以其他方式定义相关日志(例如，按日期，或者任何其他限制)，并指定正在寻找每页面的请求数目。
[0019]在一些实现中，配置用户程序108使得用户可以制定要在作为输入数据110存储的信息集中的一些或全部信息上执行的一个或多个查询(例如，使用结构化查询语言(SQL))。输入数据可以包括可在映射化简框架102中处理的任何适当信息。在一些实现中，由广告服务组织诸如通过将关联用户的在线请求记入日志，通过登记输入搜索引擎的查询，以及/或者通过自动爬行因特网上的可用页面，来收集输入数据110中的一些或所有数据。例如，但不限于:输入数据110可包括网络数据、销售数据、观测数据、科学数据、随机数据、人口数据、艺术数据、统计数据及其组合。对于在此讨论的系统依赖于关于用户的个人信息(例如，查询历史)的情况，可以向用户提供选择加入/退出可采集个人信息的程序或特征的机会。此外，在存储或使用某些数据之前可将该数据以一种或多种方式匿名化，以便移除可标识到个人的信息。例如，可以将用户的身份匿名化，从而不能确定针对该用户的任何可标识到个人的信息并且使任何标识出的用户偏好或用户交互一般化(例如，基于用户人口统计来加以一般化)，而不是关联于特定用户。作为另一示例，可以在预定时间段之后，删除查询日志中所存储的用户查询。
[0020]输入数据可具有适合于映射化简操作的任何数据格式，包括但不限于:二进制数据格式、纯文本格式、标记语言格式(例如，XML)或图像格式。
[0021]映射化简框架102包括映射操作112和化简操作114。在一些实现中，映射操作112配置用于处理输入数据110中的一些或所有数据，并从中生成至少一个中间键/值对。在一些实现中，化简操作114配置用于处理一个或多个中间键/值对的至少一部分，并从中生成至少一个输出值。一般而言，映射操作112可在输入数据110中检测到多个键中的每一个的出现，而化简操作114可将来自此类检测的数据累加或以其他方式聚合成有用的输出信息(例如，出现频率表)。
[0022]映射操作112和/或化简操作114可作为分布到一个或多个处理器的任务来执行。在一些实现中，映射化简框架112包括处理单元(诸如机器118)的集群116，或者以其他方式与之相联系地工作。例如，每个机器118可以是商用设备(例如，PC)，并且它们可使用任何适当的通信协议(例如，以太网)来联网。机器118中的每一个都具有至少一个存储器120——集成在设备之中或者通过适当连接(例如，系统总线)而通信地耦合至设备。例如，存储器120用于检测键在输入数据110中的出现，以及/或者用于为了生成输出信息而对数据进行累加。
[0023]映射化简框架102包括尺寸评估函数112。在一些实现中，尺寸评估函数122将输入数据110的尺寸与处理中所涉及的键的数目相比较。例如，可将数据存储库的尺寸与所寻找的不同词语或字母的数目相比较。
[0024]如果键的数目与数据量相比足够小，则映射化简框架102可在映射操作112和化简操作114的执行期间使用一个或多个聚合器124。聚合器124可基于任何交换和关联聚合函数，包括但不限于MAX、MIN、C0UNT或SUM。例如，对于输入数据110中的每个词语或字母，聚合器124在映射操作112中可以递增计数出现次数的关联值。作为另一示例，聚合器124在化简操作114中可以累加或以其他方式聚合具有相同的键的中间键/值对的值。下文讨论键与数据之间的尺寸关系的示例。
[0025]在一些实现中，可在映射操作112中或在化简操作114中或者同时在这二者中使用至少一个哈希表126。例如，哈希表可存储键和每个键的计数值。当在映射操作112中标识每个连续的键时，可以更新哈希表以递增一个或多个对应的值。在化简操作中，可由每个化简器使用哈希表126来聚合(例如，累加)每个特定键的值。
[0026]图2示意性地示出在映射化简框架中处理输入数据的示例。在一些实现中，可使用来自系统100 (图1)的一个或多个特征来执行过程200。例如，可在映射化简框架102(图1)中执行过程200。
[0027]这里，假设已接收到关于存储库202的处理请求，该存储库202是规模非常大的信息集。在一些实现中，存储库202包括数万亿(即，IO12)字节(也被称作太字节)或更多字节的数据。仅作为说明性示例，存储库202可对应于一年或多年来收集的在线数据，或者美国国会图书馆所存储文献的电子版本。而且，处理请求指定正在寻找的是一些特定键在这一海量信息中的出现，比如，数据中的词语或者甚至每个单独的字母。
[0028]在处理开始之前，可执行尺寸评估。例如，如果要在词语层面上进行频率确定，则评估应当把将要检测和登记的词语的总数纳入考虑。这样的数目在实际处理数据之前可能是或者可能不是确知的，但在一些实现中可以作为估计而得出。在一些实现中，假设存储库202含有单一语言(例如，英语或印地语)的信息，则可以使用该语言中词语总数的近似值作为对键的最大数目的估计。例如，一些对英语中词语数目的常见估计的范围从数十万个到超过一百万个词语。因此，当计数英语词语时，对键的总数的一般估计可以说是与IO5至IO6成正比。
[0029]作为另一示例，如果要确定存储库202中来自拉丁字母表的每个字母的频率，则键的总数将会是26个。使用来自前一示例的数值概念，对不同的键的总数的一般估计可以说是与IO1 (即，10)成正比。
[0030]尺寸评估可将存储库202的尺寸与不同的键的总数相比较。表I示出此类评估和确定的尺寸差异或关系的示例。
[0031]表I
[0032]
【权利要求】
1.一种用于在映射化简框架中处理输入数据的计算机实现方法，所述方法包括: 在所述映射化简框架中接收对于输入数据的数据处理请求； 基于所述数据处理请求，启动由所述映射化简框架中的多个映射器在所述输入数据上进行的映射操作，每个所述映射器使用聚合器来部分地将所述输入数据聚合成一个或多个中间键/值对； 启动由所述映射化简框架中的多个化简器在所述中间键/值对上进行的化简操作，其中，在不排序所述中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有 共同键的那些中间键/值对，每个所述化简器使用所述聚合器来将所述中间键/值对聚合成一个或多个输出值；以及 响应于所述数据处理请求而提供所述输出值。
2.根据权利要求1的计算机实现方法，其中所述数据处理请求标识所述输入数据中键的数目，所述方法还包括执行所标识的键的数目关于所述输入数据的尺寸的尺寸评估，其中基于所述尺寸评估来针对启动选择使用所述聚合器的所述映射操作和化简操作。
3.根据权利要求2的计算机实现方法，其中所述映射器和所述化简器使用机器集群来实现，并且其中所述尺寸评估将一个或多个所述机器的存储器空间纳入考虑。
4.根据权利要求2的计算机实现方法，其中所述尺寸评估将所标识的键的数目是否比所述输入数据的尺寸小三个数量级纳入考虑。
5.根据权利要求1的计算机实现方法，其中所述映射操作和所述化简操作中的所述聚合器使用哈希表。
6.根据权利要求1的计算机实现方法，其中所述聚合器基于交换聚合函数和关联聚合函数。
7.一种计算机程序产品，有形地体现在计算机可读存储设备之中并且包括当由处理器执行时执行用于在映射化简框架中处理输入数据的方法的指令，所述方法包括: 在所述映射化简框架中接收对于输入数据的数据处理请求； 基于所述数据处理请求，启动由所述映射化简框架中的多个映射器在所述输入数据上进行的映射操作，每个所述映射器使用聚合器来部分地将所述输入数据聚合成一个或多个中间键/值对； 启动由所述映射化简框架中的多个化简器在所述中间键/值对上进行的化简操作，其中，在不排序所述中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个所述化简器使用所述聚合器来将所述中间键/值对聚合成一个或多个输出值；以及 响应于所述数据处理请求而提供所述输出值。
8.根据权利要求7的计算机程序产品，其中所述数据处理请求标识所述输入数据中键的数目，所述方法还包括执行所标识的键的数目关于所述输入数据的尺寸的尺寸评估，其中基于所述尺寸评估来针对启动选择使用所述聚合器的所述映射操作和化简操作。
9.根据权利要求8的计算机程序产品，其中所述映射器和所述化简器使用机器集群来实现，并且其中所述尺寸评估将一个或多个所述机器的存储器空间纳入考虑。
10.根据权利要求8的计算机程序产品，其中所述尺寸评估将所标识的键的数目是否比所述输入数据的尺寸小三个数量级纳入考虑。
11.根据权利要求7的计算机程序产品，其中所述映射操作和所述化简操作中的所述聚合器使用哈希表。
12.根据权利要求7的计算机程序产品，其中所述聚合器基于交换聚合函数和关联聚合函数。
13.—种系统,包括: 至少一个处理器；以及 至少一个计算机可读存储设备，其包括当被执行时促使对用于在映射化简框架中处理输入数据的方法的执行的指令，所述方法包括: 在所述映射化简框架中接收对于输入数据的数据处理请求； 基于所述数据处理请求，启动由所述映射化简框架中的多个映射器在所述输入数据上进行的映射操作， 每个所述映射器使用聚合器来部分地将所述输入数据聚合成一个或多个中间键/值对； 启动由所述映射化简框架中的多个化简器在所述中间键/值对上进行的化简操作，其中，在不排序所述中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个所述化简器使用所述聚合器来将所述中间键/值对聚合成一个或多个输出值；以及 响应于所述数据处理请求而提供所述输出值。
14.根据权利要求13的系统，其中所述数据处理请求标识所述输入数据中键的数目，所述方法还包括执行所标识的键的数目关于所述输入数据的尺寸的尺寸评估，其中基于所述尺寸评估来针对启动选择使用所述聚合器的所述映射操作和化简操作。
15.根据权利要求14的系统，其中所述映射器和所述化简器使用机器集群来实现，并且其中所述尺寸评估将一个或多个所述机器的存储器空间纳入考虑。
16.根据权利要求14的系统，其中所述尺寸评估将所标识的键的数目是否比所述输入数据的尺寸小三个数量级纳入考虑。
17.根据权利要求13的系统，其中所述映射操作和所述化简操作中的所述聚合器使用哈希表。
18.根据权利要求13的系统，其中所述聚合器基于交换聚合函数和关联聚合函数。
【文档编号】G06F17/30GK103748579SQ201280023968
【公开日】2014年4月23日 申请日期:2012年3月28日 优先权日:2011年4月1日
【发明者】B·查托帕迪亚, 林亮, 刘蔚然, M·德沃尔斯基 申请人:谷歌公司
【专利摘要】本发明公开一种用于在映射化简框架中处理输入数据的计算机实现方法，包括：在所述映射化简框架中接收对于输入数据的数据处理请求；基于所述数据处理请求，启动由所述映射化简框架中的多个映射器在所述输入数据上进行的映射操作，每个所述映射器使用聚合器来部分地将所述输入数据聚合成一个或多个中间键/值对；启动由所述映射化简框架中的多个化简器在所述中间键/值对上进行的化简操作，其中，在不排序所述中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个所述化简器使用所述聚合器来将所述中间键/值对聚合成一个或多个输出值；以及响应于所述数据处理请求而提供所述输出值。
【专利说明】在映射化简框架中处理数据
[0001]相关申请的交叉引用
[0002]本申请要求于2011年4月I日提交的，标题为“PROCESSING DATA IN A MAPREDUCEFRAMEWORK”的美国专利申请序号N0.13/078，500的优先权，该申请的公开内容通过引用并入于此。
【技术领域】
[0003]本文涉及映射化简(mapreduce)框架中的数据处理。
【背景技术】
[0004]映射化简模型由Google Inc.开发作为一种简化大规模数据处理的方式。映射化简过程的实现是根据映射化简模型而完成的。
【发明内容】
[0005]在第一方面，一种用于在映射化简框架中处理输入数据的计算机实现方法包括:在映射化简框架中接收对于输入数据的数据处理请求；基于该数据处理请求，启动由映射化简框架中的多个映射器在输入数据上进行的映射操作，每个映射器使用聚合器来部分地将输入数据聚合成一个或多个中间键/值对；启动由映射化简框架中的多个化简器在中间键/值对上进行的化简操作，其中，在不排序中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个化简器使用聚合器来将中间键/值对聚合成一个或多个输出值；以及响应于数据处理请求而提供输出值。
[0006]在第二方面，一种有形地体现在计算机可读存储设备中的计算机程序产品包括当由处理器执行时执行用于在映射化简框架中处理输入数据的方法的指令。该方法包括:在映射化简框架中接收对于输入数据的数据处理请求；基于该数据处理请求，启动由映射化简框架中的多个映射器在输入数据上进行的映射操作，每个映射器使用聚合器来部分地将输入数据聚合成一个或多个中间键/值对；启动由映射化简框架中的多个化简器在中间键/值对上进行的化简操作，其中，在不排序中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个化简器使用聚合器来将中间键/值对聚合成一个或多个输出值；以及响应于数据处理请求而提供输出值。
[0007]在第三方面，一种系统包括:至少一个处理器；以及至少一个计算机可读存储设备，其包括当被执行时致使用于在映射化简框架中处理输入数据的方法的执行的指令。该方法包括:在映射化简框架中接收对于输入数据的数据处理请求；基于该数据处理请求，启动由映射化简框架中的多个映射器在输入数据上进行的映射操作，每个映射器使用聚合器来部分地将输入数据聚合成一个或多个中间键/值对；启动由映射化简框架中的多个化简器在中间键/值对上进行的化简操作，其中，在不排序中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个化简器使用聚合器来将中间键/值对聚合成一个或多个输出值；以及响应于数据处理请求而提供输出值。
[0008]实现可以包括以下特征中的任何或所有特征。所述数据处理请求标识所述输入数据中的键的数目，并且所述方法还包括执行所标识的键的数目关于输入数据尺寸的尺寸评估，其中基于尺寸评估来选择启动使用聚合器的映射操作和化简操作。映射器和化简器使用机器集群来实现，其中尺寸评估将一个或多个机器的存储器空间纳入考虑。尺寸评估将所标识的键的数目是否比输入数据的尺寸小三个数量级纳入考虑。映射操作和化简操作中的聚合器使用哈希表。聚合器基于交换聚合函数和关联聚合函数。
[0009]实现可以提供以下优点中的任何或所有有点。可执行高性能查询聚合。可以在框架的映射端和化简端二者上使用通用聚合器。聚合器可连续执行聚合(例如，一旦每个新值变得可用，就执行聚合)。可以消除针对化简操作而排序键/值对的需求。通过在存储器中仅保持针对给定键的聚合值，可以减少存储器使用量。可以例如通过禁用排序器和添加通用聚合器来重用映射化简框架。可以放松或消除对于所有针对相同键的值必须转到相同的化简调用的要求。聚合器可以代替映射端上的组合器。聚合可以使用哈希表来执行。
[0010]在以下附图和描述中阐述了一个或多个实现的详情。从描述和附图，以及从权利要求书中将会呈现出其他特征和优点。
【专利附图】
【附图说明】
[0011]图1不出具有映射化简框架的系统的不例。
[0012]图2示意性地示出在映射化简框架中处理输入数据的示例。
[0013]图3是不例方法的流程图。
[0014]图4是可以联系本文所述计算机实现方法来使用的示例计算系统的框图。
[0015]各附图中的相似参考符号表示相似元素。
【具体实施方式】
[0016]本文描述这样的系统和技术:通过所述系统和技术,可以通过在映射端和化简端二者上使用通用聚合器来实现映射化简框架中的输入数据的处理，而不需要在化简操作之前排序中间数据。在一些实现中，使用通用聚合器的方式可以基于评估输入数据与在处理输入数据中所涉及的键的相对尺寸来使用。例如，当仅在相对较大量的数据中寻找到相对较少的键(例如，词语的数目至少比键的数目大一千倍)时，可在映射操作中聚合针对键的值，并且可将具有相同键的键/值对转发至相同的化简器。化简器继而可在化简操作中使用相同的通用聚合器。这样可以显著减少从映射操作传递到化简操作的中间数据量，并且可以消除针对化简操作而排序中间数据的需要。
[0017]图1不出具有映射化简框架102的系统100的不例。映射化简框架102可用于执行根据映射化简模型的数据处理，例如，用于对大量数据执行某些类型的分析。本文中所使用的术语“映射化简框架”意指这样的系统，其配置用于执行:(i)根据输入数据而生成一个或多个中间键/值对的至少一个映射操作；以及(ii)根据中间键/值对而生成一个或多个输出值的至少一个化简操作。映射化简框架将映射操作分配在多个程序组件(有时称为“工作者(worker)”)之间，并向每个工作者指配一个或多个映射任务。映射化简框架将化简操作分成化简任务，并将它们指配给工作者。在一些实现中，映射化简框架运行于诸如商用PC网络之类的处理设备集群上。
[0018]这里，用户可以采用计算机设备104，通过诸如因特网或用于移动设备的网络(例如，蜂窝电话网络)等任何类型的网络106，来访问映射化简框架。映射化简处理可由计算机设备上的用户程序108来启动。在一些实现中，供应广告的组织可以使用程序108来分析与广告的一个或多个方面相关的大量数据。例如，映射化简操作可以确定针对上亿个或更多个在线页面中的每个页面的反向超链接，这意味着检测出链接到给定页面的所有页面。在此类情况下，用户程序108定义相关目标页面的组，并且指定正在寻找对应的源页面。作为另一示例，映射化简操作可以处理针对在线页面的请求日志，以确定每个页面被请求了多少次。在该情况下，用户程序108标识或以其他方式定义相关日志(例如，按日期，或者任何其他限制)，并指定正在寻找每页面的请求数目。
[0019]在一些实现中，配置用户程序108使得用户可以制定要在作为输入数据110存储的信息集中的一些或全部信息上执行的一个或多个查询(例如，使用结构化查询语言(SQL))。输入数据可以包括可在映射化简框架102中处理的任何适当信息。在一些实现中，由广告服务组织诸如通过将关联用户的在线请求记入日志，通过登记输入搜索引擎的查询，以及/或者通过自动爬行因特网上的可用页面，来收集输入数据110中的一些或所有数据。例如，但不限于:输入数据110可包括网络数据、销售数据、观测数据、科学数据、随机数据、人口数据、艺术数据、统计数据及其组合。对于在此讨论的系统依赖于关于用户的个人信息(例如，查询历史)的情况，可以向用户提供选择加入/退出可采集个人信息的程序或特征的机会。此外，在存储或使用某些数据之前可将该数据以一种或多种方式匿名化，以便移除可标识到个人的信息。例如，可以将用户的身份匿名化，从而不能确定针对该用户的任何可标识到个人的信息并且使任何标识出的用户偏好或用户交互一般化(例如，基于用户人口统计来加以一般化)，而不是关联于特定用户。作为另一示例，可以在预定时间段之后，删除查询日志中所存储的用户查询。
[0020]输入数据可具有适合于映射化简操作的任何数据格式，包括但不限于:二进制数据格式、纯文本格式、标记语言格式(例如，XML)或图像格式。
[0021]映射化简框架102包括映射操作112和化简操作114。在一些实现中，映射操作112配置用于处理输入数据110中的一些或所有数据，并从中生成至少一个中间键/值对。在一些实现中，化简操作114配置用于处理一个或多个中间键/值对的至少一部分，并从中生成至少一个输出值。一般而言，映射操作112可在输入数据110中检测到多个键中的每一个的出现，而化简操作114可将来自此类检测的数据累加或以其他方式聚合成有用的输出信息(例如，出现频率表)。
[0022]映射操作112和/或化简操作114可作为分布到一个或多个处理器的任务来执行。在一些实现中，映射化简框架112包括处理单元(诸如机器118)的集群116，或者以其他方式与之相联系地工作。例如，每个机器118可以是商用设备(例如，PC)，并且它们可使用任何适当的通信协议(例如，以太网)来联网。机器118中的每一个都具有至少一个存储器120——集成在设备之中或者通过适当连接(例如，系统总线)而通信地耦合至设备。例如，存储器120用于检测键在输入数据110中的出现，以及/或者用于为了生成输出信息而对数据进行累加。
[0023]映射化简框架102包括尺寸评估函数112。在一些实现中，尺寸评估函数122将输入数据110的尺寸与处理中所涉及的键的数目相比较。例如，可将数据存储库的尺寸与所寻找的不同词语或字母的数目相比较。
[0024]如果键的数目与数据量相比足够小，则映射化简框架102可在映射操作112和化简操作114的执行期间使用一个或多个聚合器124。聚合器124可基于任何交换和关联聚合函数，包括但不限于MAX、MIN、C0UNT或SUM。例如，对于输入数据110中的每个词语或字母，聚合器124在映射操作112中可以递增计数出现次数的关联值。作为另一示例，聚合器124在化简操作114中可以累加或以其他方式聚合具有相同的键的中间键/值对的值。下文讨论键与数据之间的尺寸关系的示例。
[0025]在一些实现中，可在映射操作112中或在化简操作114中或者同时在这二者中使用至少一个哈希表126。例如，哈希表可存储键和每个键的计数值。当在映射操作112中标识每个连续的键时，可以更新哈希表以递增一个或多个对应的值。在化简操作中，可由每个化简器使用哈希表126来聚合(例如，累加)每个特定键的值。
[0026]图2示意性地示出在映射化简框架中处理输入数据的示例。在一些实现中，可使用来自系统100 (图1)的一个或多个特征来执行过程200。例如，可在映射化简框架102(图1)中执行过程200。
[0027]这里，假设已接收到关于存储库202的处理请求，该存储库202是规模非常大的信息集。在一些实现中，存储库202包括数万亿(即，IO12)字节(也被称作太字节)或更多字节的数据。仅作为说明性示例，存储库202可对应于一年或多年来收集的在线数据，或者美国国会图书馆所存储文献的电子版本。而且，处理请求指定正在寻找的是一些特定键在这一海量信息中的出现，比如，数据中的词语或者甚至每个单独的字母。
[0028]在处理开始之前，可执行尺寸评估。例如，如果要在词语层面上进行频率确定，则评估应当把将要检测和登记的词语的总数纳入考虑。这样的数目在实际处理数据之前可能是或者可能不是确知的，但在一些实现中可以作为估计而得出。在一些实现中，假设存储库202含有单一语言(例如，英语或印地语)的信息，则可以使用该语言中词语总数的近似值作为对键的最大数目的估计。例如，一些对英语中词语数目的常见估计的范围从数十万个到超过一百万个词语。因此，当计数英语词语时，对键的总数的一般估计可以说是与IO5至IO6成正比。
[0029]作为另一示例，如果要确定存储库202中来自拉丁字母表的每个字母的频率，则键的总数将会是26个。使用来自前一示例的数值概念，对不同的键的总数的一般估计可以说是与IO1 (即，10)成正比。
[0030]尺寸评估可将存储库202的尺寸与不同的键的总数相比较。表I示出此类评估和确定的尺寸差异或关系的示例。
[0031]表I
[0032]
【权利要求】
1.一种用于在映射化简框架中处理输入数据的计算机实现方法，所述方法包括: 在所述映射化简框架中接收对于输入数据的数据处理请求； 基于所述数据处理请求，启动由所述映射化简框架中的多个映射器在所述输入数据上进行的映射操作，每个所述映射器使用聚合器来部分地将所述输入数据聚合成一个或多个中间键/值对； 启动由所述映射化简框架中的多个化简器在所述中间键/值对上进行的化简操作，其中，在不排序所述中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有 共同键的那些中间键/值对，每个所述化简器使用所述聚合器来将所述中间键/值对聚合成一个或多个输出值；以及 响应于所述数据处理请求而提供所述输出值。
2.根据权利要求1的计算机实现方法，其中所述数据处理请求标识所述输入数据中键的数目，所述方法还包括执行所标识的键的数目关于所述输入数据的尺寸的尺寸评估，其中基于所述尺寸评估来针对启动选择使用所述聚合器的所述映射操作和化简操作。
3.根据权利要求2的计算机实现方法，其中所述映射器和所述化简器使用机器集群来实现，并且其中所述尺寸评估将一个或多个所述机器的存储器空间纳入考虑。
4.根据权利要求2的计算机实现方法，其中所述尺寸评估将所标识的键的数目是否比所述输入数据的尺寸小三个数量级纳入考虑。
5.根据权利要求1的计算机实现方法，其中所述映射操作和所述化简操作中的所述聚合器使用哈希表。
6.根据权利要求1的计算机实现方法，其中所述聚合器基于交换聚合函数和关联聚合函数。
7.一种计算机程序产品，有形地体现在计算机可读存储设备之中并且包括当由处理器执行时执行用于在映射化简框架中处理输入数据的方法的指令，所述方法包括: 在所述映射化简框架中接收对于输入数据的数据处理请求； 基于所述数据处理请求，启动由所述映射化简框架中的多个映射器在所述输入数据上进行的映射操作，每个所述映射器使用聚合器来部分地将所述输入数据聚合成一个或多个中间键/值对； 启动由所述映射化简框架中的多个化简器在所述中间键/值对上进行的化简操作，其中，在不排序所述中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个所述化简器使用所述聚合器来将所述中间键/值对聚合成一个或多个输出值；以及 响应于所述数据处理请求而提供所述输出值。
8.根据权利要求7的计算机程序产品，其中所述数据处理请求标识所述输入数据中键的数目，所述方法还包括执行所标识的键的数目关于所述输入数据的尺寸的尺寸评估，其中基于所述尺寸评估来针对启动选择使用所述聚合器的所述映射操作和化简操作。
9.根据权利要求8的计算机程序产品，其中所述映射器和所述化简器使用机器集群来实现，并且其中所述尺寸评估将一个或多个所述机器的存储器空间纳入考虑。
10.根据权利要求8的计算机程序产品，其中所述尺寸评估将所标识的键的数目是否比所述输入数据的尺寸小三个数量级纳入考虑。
11.根据权利要求7的计算机程序产品，其中所述映射操作和所述化简操作中的所述聚合器使用哈希表。
12.根据权利要求7的计算机程序产品，其中所述聚合器基于交换聚合函数和关联聚合函数。
13.—种系统,包括: 至少一个处理器；以及 至少一个计算机可读存储设备，其包括当被执行时促使对用于在映射化简框架中处理输入数据的方法的执行的指令，所述方法包括: 在所述映射化简框架中接收对于输入数据的数据处理请求； 基于所述数据处理请求，启动由所述映射化简框架中的多个映射器在所述输入数据上进行的映射操作， 每个所述映射器使用聚合器来部分地将所述输入数据聚合成一个或多个中间键/值对； 启动由所述映射化简框架中的多个化简器在所述中间键/值对上进行的化简操作，其中，在不排序所述中间键/值对的情况下，由所述化简器中相同的一个化简器来处理所述中间键/值对中具有共同键的那些中间键/值对，每个所述化简器使用所述聚合器来将所述中间键/值对聚合成一个或多个输出值；以及 响应于所述数据处理请求而提供所述输出值。
14.根据权利要求13的系统，其中所述数据处理请求标识所述输入数据中键的数目，所述方法还包括执行所标识的键的数目关于所述输入数据的尺寸的尺寸评估，其中基于所述尺寸评估来针对启动选择使用所述聚合器的所述映射操作和化简操作。
15.根据权利要求14的系统，其中所述映射器和所述化简器使用机器集群来实现，并且其中所述尺寸评估将一个或多个所述机器的存储器空间纳入考虑。
16.根据权利要求14的系统，其中所述尺寸评估将所标识的键的数目是否比所述输入数据的尺寸小三个数量级纳入考虑。
17.根据权利要求13的系统，其中所述映射操作和所述化简操作中的所述聚合器使用哈希表。
18.根据权利要求13的系统，其中所述聚合器基于交换聚合函数和关联聚合函数。
【文档编号】G06F17/30GK103748579SQ201280023968
【公开日】2014年4月23日 申请日期:2012年3月28日 优先权日:2011年4月1日
【发明者】B·查托帕迪亚, 林亮, 刘蔚然, M·德沃尔斯基 申请人:谷歌公司
最新回复(0)