[發(fā)明專利]在映射縮減過程中匯合表

有效

• 申請?zhí)枺?/td>: 201280031211.0
• 申請日: 2012-03-28
• 公開（公告）號: CN103620601B
• 公開（公告）日: 2017-04-12
• 發(fā)明（設(shè)計(jì)）人: B·查托帕迪亞;林亮
• 申請（專利權(quán)）人: 谷歌公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京市金杜律師事務(wù)所11256
• 代理人: 酆迅,辛鳴

相關(guān)申請的交叉引用

本申請要求對通過引用將其全部內(nèi)容結(jié)合于此、名稱為“Joining?Tables?in?a?Mapreduce?Procedure”、于2011年4月29日提交的第61/480,563號美國臨時(shí)申請和名稱為“Joining?Tables?in?a?Mapreduce?Procedure”、于2011年8月15日提交的第13/209,567號美國申請的優(yōu)先權(quán)。

技術(shù)領(lǐng)域

本公開內(nèi)容涉及在映射縮減（mapreduce）過程中匯合表。

背景技術(shù)

在Google公司開發(fā)映射縮減模型作為一種用于簡化大規(guī)模數(shù)據(jù)處理的方式。根據(jù)映射縮減模型完成映射縮減過程的實(shí)現(xiàn)方式。

發(fā)明內(nèi)容

實(shí)現(xiàn)方式可以提供以下優(yōu)點(diǎn)中的任何或者所有優(yōu)點(diǎn)?？梢愿焱瓿捎成淇s減框架中的數(shù)據(jù)處理?？梢詼p少將為映射縮減過程加載的數(shù)據(jù)量?？梢詧?zhí)行映射縮減過程中的表匯合而不進(jìn)一步分割數(shù)據(jù)。更少映射縮減操作可能是必要的，從而導(dǎo)致更少資源使用?？梢杂眉虞d到存儲器中的全部數(shù)據(jù)或者作為對排序的數(shù)據(jù)的兩個(gè)集合的合并匯合執(zhí)行映射縮減框架中的匯合過程。

在附圖和以下描述中闡述一個(gè)或者多個(gè)實(shí)施例的細(xì)節(jié)。其它特征和優(yōu)點(diǎn)將從描述和附圖以及從權(quán)利要求變得清楚。

附圖說明

圖1是示意地示出用于映射縮減過程的分割的示例的框圖。

圖2示意地圖示預(yù)組織來自第一表和第二表的數(shù)據(jù)的示例。

圖3是具有執(zhí)行映射縮減操作的示例的流程圖。

圖4是可以結(jié)合在本文中描述的計(jì)算機(jī)實(shí)施的方法使用的計(jì)算系統(tǒng)的框圖。

在各種附圖中的相似標(biāo)號指示相似要素。

具體實(shí)施方式

本文描述可以用來在映射縮減過程中匯合表的系統(tǒng)和技術(shù)。在一些實(shí)現(xiàn)方式中，在大的業(yè)務(wù)數(shù)據(jù)表（例如，具有十億個(gè)事務(wù)記錄或者更多）將與大的客戶數(shù)據(jù)表（例如，具有數(shù)億個(gè)客戶記錄）匯合時(shí)，則可以在映射縮減過程之前組織這兩個(gè)表以加速表匯合。例如，可以基于相同關(guān)鍵字將業(yè)務(wù)數(shù)據(jù)和客戶數(shù)據(jù)二者分別哈希分割成業(yè)務(wù)數(shù)據(jù)碎片（shard）和客戶數(shù)據(jù)碎片。在這兩組中的碎片數(shù)目相互具有整體關(guān)系：例如從而使得有用于每個(gè)客戶數(shù)據(jù)碎片的兩個(gè)業(yè)務(wù)數(shù)據(jù)碎片，或者反之亦然。這一預(yù)組織可以減少向存儲器中加載的數(shù)據(jù)量，并且也可以在映射縮減過程內(nèi)避免一些分割。

圖1示出具有映射縮減框架102的系統(tǒng)100的示例。映射縮減框架102可以用來根據(jù)映射縮減模型執(zhí)行數(shù)據(jù)處理以例如對大量數(shù)據(jù)執(zhí)行某些類型的分析。如在本文中所用，術(shù)語“映射縮減框架”指代如下系統(tǒng)，該系統(tǒng)被配置用于執(zhí)行（i）至少一個(gè)映射操作，該操作根據(jù)輸入數(shù)據(jù)生成一個(gè)或者多個(gè)中間關(guān)鍵字/值對；以及（ii）至少一個(gè)縮減操作，該操作根據(jù)中間關(guān)鍵字/值對生成一個(gè)或者多個(gè)輸出值。

映射縮減框架在多個(gè)程序部件（有時(shí)被稱為“工作器”）之間劃分映射操作并且向每個(gè)工作器指派一個(gè)或者多個(gè)映射任務(wù)。映射縮減框架將縮減操作劃分成縮減任務(wù)并且向工作器指派它們。在一些實(shí)現(xiàn)方式中，在處理設(shè)備群集（比如商品PC的網(wǎng)絡(luò)）上運(yùn)行映射縮減框架。例如，可以建立數(shù)據(jù)中心，該數(shù)據(jù)中心具有機(jī)架，這些機(jī)架具有數(shù)萬個(gè)處理模塊（例如，處理模塊可以是商品PC或者其部分），并且可以執(zhí)行映射縮減過程作為在數(shù)千個(gè)（或者更多）的處理單元之中分布的大規(guī)模數(shù)據(jù)作業(yè)。僅舉一個(gè)示例，映射縮減作業(yè)可以涉及到映射和縮減數(shù)萬億字節(jié)的數(shù)據(jù)或者更多。

這里，用戶可以運(yùn)用計(jì)算機(jī)設(shè)備104以通過任何類型的網(wǎng)絡(luò)106（比如因特網(wǎng)或者用于移動設(shè)備的網(wǎng)絡(luò)（例如，蜂窩電話網(wǎng)絡(luò)））接入映射縮減框架102。映射縮減處理可以由計(jì)算設(shè)備上的用戶程序108發(fā)起。在一些實(shí)現(xiàn)方式中，組織可以使用程序108以分析大量業(yè)務(wù)數(shù)據(jù)。例如，電信公司（比如無線服務(wù)提供商）可以具有參與與公司的許多事務(wù)的數(shù)億個(gè)客戶（例如，可以將無線設(shè)備的每次使用注冊為事務(wù)）。在這樣的情形中，用于某個(gè)時(shí)間段（例如，周、月或者年）的累計(jì)業(yè)務(wù)數(shù)據(jù)可以達(dá)到十億個(gè)記錄或者更多。映射縮減過程然后可以在分析業(yè)務(wù)數(shù)據(jù)時(shí)例如用來對源于具體國家的事務(wù)數(shù)目或者未成功事務(wù)數(shù)目計(jì)數(shù)。在這樣的情形中，用戶程序108標(biāo)識待使用的業(yè)務(wù)數(shù)據(jù)量，并且定義尋求的標(biāo)準(zhǔn)或者特性。