《5MapReduce设计模式》由会员分享，可在线阅读，更多相关《5MapReduce设计模式（32页珍藏版）》请在金锄头文库上搜索。
1、MapReduce设计模式龚玲龚玲103994127知识回顾掌握map任务的四个阶段掌握reduce任务的四个阶段vmap任务主要负责数据的载入、解析、转换和过滤,即： record reader mapper combiner partitionervreduce任务主要为混排、排序、reducer和输出格式 shuffle sort reducer output format数值概要：是计算数据聚合统计值的一般性模式应用：p单词计数p记录计数p最大值/最小值/计数p平均值/中位数/标准差掌掌握握倒倒排排索索引引的的基基本本概概念念掌掌握握倒倒排排索索引引概概要要工工作作模式模式了了解解概概
2、要要模模式式的的三三种种模模式应用式应用掌掌握握技技术术器器计数计数学习要求单词文档矩阵单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型。搜索引擎的索引其实就是实现“单词-文档矩阵”的具体数据结构。可以有不同的方式来实现上述概念模型，比如“倒排索引”、“签名文件”、“后缀树”等方式。但是各项实验数据表明，“倒排索引”是实现单词到文档映射关系的最佳实现方式。倒排索引基本概念文文档档(Document)(Document)：一般搜索引擎的处理对象是互联网网页，而文档这个概念要更宽泛些，代表以文本形式存在的存储对象，相比网页来说，涵盖更多种形式，比如Word，PDF，html，XML等不同
3、格式的文件都可以称之为文档。再比如一封邮件，一条短信，一条微博也可以称之为文档。文文档档集集合合(Document (Document Collection)Collection)：由若干文档构成的集合称之为文档集合。比如海量的互联网网页或者说大量的电子邮件都是文档集合的具体例子。文文档档编编号号(Document (Document ID)ID)：在搜索引擎内部，会将文档集合内每个文档赋予一个唯一的内部编号，以此编号来作为这个文档的唯一标识，这样方便内部处理，每个文档的内部编号即称之为“文档编号”，后文有时会用DocID来便捷地代表文档编号。单单词词编编号号(Word (Word ID)ID
4、)：与文档编号类似，搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一表征。倒倒排排索索引引(Inverted Index)：倒排索引是实现“单词-文档矩阵”的一种具体存存储储形式，通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单单词词词词典典”和和“倒倒排文件排文件”。单单词词词词典典：搜索引擎的通常索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。倒排列表 倒排列表用来记录有哪些文档包含了某个单词。一般在文档集合里会有很多文档包含某个单词
5、，每个文档会记录文档编号（DocID），单词在这个文档中出现的次数（TF）及单词在文档中哪些位置出现过等信息，这样与一个文档相关的信息被称做倒排索引项（Posting），包含这个单词的一系列倒排索引项形成了列表结构，这就是某个单词对应的倒排列表。 在实际的搜索引擎系统中，并不存储倒排索引项中的实际文档编号，而是代之以文档编号差值（D-Gap）。文档编号差值是倒排列表中相邻的两个倒排索引项文档编号的差值，一般在索引构建过程中，可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号，所以文档编号差值总是大于0的整数。如图所示的例子中，原始的 3个文档编号分别是187、196和199，通过编号差
6、值计算，在实际存储的时候就转化成了：187、9、3。所以要对文档编号进行差值计算，主要原因是为了更好地对数据进行压缩，原始文档编号一般都是大数值，通过差值计算，就有效地将大数值转换为了小数值，而这有助于增加数据的压缩率。倒倒排排文文件件(Inverted File)：所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称之为倒排文件，倒排文件是存储倒排索引的物理文件。建立倒排索引简单索引构建 索引的构建相当于从正排表到倒排表的建立过程。当我们分析完网页时 ,得到的是以网页为主码的索引表。当索引建立完成后 ,应得到倒排表 ,具体流程如图所示：流程：1）将文档分析称单词term标记，2
7、）使用hash去重单词term3）对单词生成倒排列表倒排列表就是文档编号DocID，没有包含其他的信息（如词频，单词位置等），这就是简单的索引。这个简单索引功能可以用于小数据，例如索引几千个文档。然而它有两点限制：1）需要有足够的内存来存储倒排表，对于搜索引擎来说， 都是G级别数据，特别是当规模不断扩大时 ,我们根本不可能提供这么多的内存。2）算法是顺序执行，不便于并行处理。倒排索引简单实例假设文档集合包含五个文档，每个文档内容如图所示，在图中最左端一栏是每个文档对应的文档编号。我们的任务就是对这个文档集合建立倒排索引。中文和英文等语言不同，单词之间没有明确分隔符号，所以首先要用分词系统将文档
8、自动切分成单词序列。这样每个文档就转换为由单词序列构成的数据流，为了系统后续处理方便，需要对每个不同的单词赋予唯一的单词编号，同时记录下哪些文档包含这个单词，在如此处理结束后，我们可以得到最简单的倒排索引。实用的倒排索引还可以记载更多的信息，下图所示索引系统除了记录文档编号和单词频率信息外，额外记载了两类信息，即每个单词对应的“文档频率信息” 以及在倒排列表中记录单词在某个文档出现的位置信息。倒排索引概要经常被用作MapReduce分析的示例目的： 可以产生一个数据集的索引以提供更快的搜索或数据丰富能力适用场景： 通常用在需要快速搜索查询相应的场景。可以对一个查询的结果进行预处理并存储在一个数
9、据库中。结构：结果最终输出结果是一系列的文件，每个文件包含的是字段值到一系列包含这些字段值的记录的唯一ID的映射。输入输入输出输出keyvaluekeyvaluemap文档URI单词单词+文档URI词频combiner单词+文档URI词频单词+文档URI单个文档的中出现的词频汇总reducercombiner的结果keyvalue-list单词文档URI:词频并行与分布式建立索引在搜索引擎-网络爬虫, 使用Map/Reduce并行计算模型，对文档生成倒排索引列：对于建立倒排索引这个任务来说，输入数据也是网页，以网页的DOCID作为输入数据 的Key, 网页中出现的单词集合是输入数据的 Valu
10、e; Map 操作将输入数据转化为 (word，DOCID)的形式，即某个单词作为Key， DOCID作为中间数据的value，其含义是单词 word在DOCID这个网页出现过；Reduce操作将中间数据中相同Key的记录融合，得到某 个单词对应的网页ID列表： 。这就是单词word对应的倒排列表。通过 这种方式就可以建立简单的倒排索引，在Reduce阶段也可以做些复杂操作，获得形式更为复杂的倒排索引。倒排索引示例维基百科应用倒排索引倒排索引的建立大部分的操作是分组，这部分工作由MapReduce框架完成。例： 假如打算在每一个被StackOverflow评论引用的维基百科页面上添加Stack
11、Overflow链接步骤：1、分析每一个StackOverflow的评论以找出到Wikipedia的超链接；2、如果存在超链接，输出这个链接与对应的评论ID，生成倒排索引；3、reduce阶段，所有引用同一超链接的评论ID会分到一组；4、这些组会使用空格做分割链接在一起形成一个字符串直接输出到文件系统；5、此时，这个输出的数据文件可以用作更新引用维基百科页面的所有评论。计数器计数Hadoop为每个作业维护配置若干内置计数器, 以描述该作业的各项指标。例如，某些计数器记录已处理的字节数和记录数，使用户可监控已处理的输入数据量和已产生的输出数据量，并以此对 job 做适当的优化。计数器是一种收集作
12、业统计信息的有效手段，用于质量控制或应用级统计。计数器还可辅助诊断系统故障。如果需要将日志信息传输到map或reduce任务，更好的方法通常是尝试传输计数器值以监测某一特定事件是否发生。计 数 器 被 与 它 们 相 关 的 任 务 维 护 ， 并 定 期 发 送 到tasktracker，然后发送到jobtracker，这样就能全局范围内汇总这些计数器在许多情况下，一个用户需要了解待分析的数据，尽管这并非所要执行的分析任务的核心内容。以统计数据集中无效记录数目的任务为例，如果发现无效记录的比例相当高，那么就需要认真思考为何存在如此多无效记录。是所采用的检测程序存在缺陷，还是数据集质量确实很低
13、，包含大量无效记录？如果确定是数据集的质量问题，则可能需要扩大数据集的规模，以增大有效记录的比例，从而进行有意义的分析。模式描述：模式描述：使用MapReduce框架自身的计数器在不产生任何输出的情况下，在map端计算一个全局的计数。目的：目的：得到大数据集计数概要的一种高效方法。动机：动机：一个计数或者总和可以让你了解到关于数据的某些字段，以至于整个数据集的很多信息。不需要像MapReduce程序那样输出键/值对，只需要简单地使用框架的计数机制来跟踪输入记录数。整个过程不需要reduce阶段和汇总处理。例：寻找某个公司员工登录到公共网站页面的次数信息。假定有几十个员工，在解析web日志是可以
14、使用过滤条件。简单地创建一个以员工ID为名字的计数器，并将其每次登录加1，作业结束时，直接获取框架的计数器信息并将其写到任意地方，如：日志、本地系统文件、HDFS等。除了框架中已经内置了一些计数器的支持，例如输入、输出的记录数和字节数。Hadoop支持开发者根据自己的需要创建自定义计数器。这个模式阐述的就是如何使用这些自定义计数器来收集和汇总数据集的指标信息。使用计数器的好处是整个计数的过程都可以在map阶段完成。适用场景：在一个大数据集上收集计数或者汇总；需要创建的计数器数目很小两位数字以内。结构：结构：Mapper在每次处理每个输入记录时，按照既定的条件对计数器进行累加。计数器在对单个实例
15、进行计数时会加1，在执行汇总时会增加一个指定的值。这些计数器信息会被负责执行这个任务的TaskTracker聚合并增量汇报给JobTracker,以在工作完成的时候做整体聚合。对应失败任务的计数器，JobTracker会最终的汇总中将其剔除。所有的工作只需要在map过程完成，不需要combiner、partitioner或者reducer过程。结果：结果：最终输出是这个任务框架中所得到的所有计数器信息的集合，并不是分析任务的真实输出结果。但是，作业执行总是需要一个输出目录，这个目录会存在并包含一系列与map任务数目相同的空part文件。已知应用：已知应用：统计记录数简单地对指定时间段的记录数进
16、行统计统计小数量级的唯一实例计数计数器还可以通过一个字符串变量来创建。已经知道值是什么，但不需要预先创建计数器。通过一个字段值来创建计数器并完成累计，就可以解决这个问题汇总汇总计数器可以用来对数据的某些字段进行汇总。不是在reduce端执行汇总，而是通过创建一个新的计数器并使用它对字段值进行汇总。计数器计数示例计数器计数示例问题：使用Hadoop用户计数器计算每个州的用户数Mapper代码读入每一个用户记录并获取用户的位置信息。位置信息通过空格分隔并从中查找是否属于某个州的信息。由于位置信息是用户创建的非结构化的简单字符串，为避免创建过多的计数器，内存中保存所有州的缩写的集合。使用分组和名称对计数器进行标识。如果一个州被识别，那么这个州的计数器会加1并中断循环。注意：所有计数器的信息都是存储在JobTracker的内存中，在每个map任务中计数器被序列化，并通过状态更新同步到JobTracker。为了不对JobTracker的正常工作产生影响，计数器的数目最好控制在几十个以内，最多100个。
