MapReduce 课程总结

2019-12-18发表2022-08-06更新NJU1 小时读完 (大约7601个字)0次访问

MapReduce 大数据分析课程总结

大数据技术简介

大数据的类型分类

结构特征
- 结构化数据
- 非结构化/半结构化数据
获取和处理方式
- 静态(线下数据)/非实时数据
- 动态(流式/增量式/线上)/实时数据
关联特征
- 无关联/简单关联数据(键值记录型数据)
- 复杂关联数据(图数据)

大数据处理的主要技术问题

存储：巨量数据如何存得下？数据存储问题
1. 数据规模导致难以应对的存储量，传统数据库技术失效
2. 需要研究开发有效的分布式大数据存储技术与系统
计算：巨量数据如何快速完成计算？计算性能问题
1. 数据规模导致传统算法失效
2. 复杂的数据关联性导致高复杂度的计算
3. 需要研究开发高效的大数据并行计算技术与系统
分析：如何发现大数据的深度价值？数据分析问题
1. 大数据隐含很多小数据时难以发现的深度价值
2. 需要研究开发有效的大数据分析挖掘技术与工具

大数据研究的基本途径

新算法：寻找新算法降低计算复杂度
降低尺度：寻找数据尺度无关近似算法
并行化：分而治之，并行化处理

？什么是大数据

Wiki百科：大数据意指一个超大的、难以用现有常规的数据库管理技术和工具处理的数据集

IDC报告：大数据技术描述了一种新一代技术和构架，用于以很经济的方式、以高速的捕获、发现和分析技术，从各种超大规模的数据中提取价值

“大数据”的真实含义：

大数据是以下内容的一个总称：

大数据带来了新的技术时代转型
大数据所带来的问题和技术挑战
大数据处理所需的新的技术和方法
大数据时代需要的大数据思维
大数据分析和应用所带来的新发明、新服务和新的发展机遇

GB -> Tb -> PB -> EB -> ZB

？大数据特点: 5V

Volume: 大容量：PB级规模
Variety: 多样性：结构化/非结构化
Velocity: 时效性：实时处理
Veracity: 准确性：结果准确
Value: 大价值：深度价值

？三个层面的挑战

大数据的技术挑战
- 数据存储能力大幅落后于数据增长速度
- 数据处理能力大幅落后于数据增长速度
企业应用的挑战
- 大企业内竖井式应用，大量系统相互隔离，形成信息孤岛
政府数据开放政策的挑战
- 政府机构掌握的大量数据不能开放使用

MapReduce 简介

为什么需要大规模数据并行处理

处理数据的能力大幅落后于数据增长
海量数据隐含着更准确的事实

什么是MapReduce？

MapReduce是Google公司发明的一种面向大规模大数据处理的高性能并行计算平台和软件编程框架，是目前最为成功和最易于使用的大规模大数据并行处理技术，广泛应用于搜索引擎（文档倒排索引，网页链接图分析与页面排序等）、Web日志分析、文档分析处理、机器学习、机器翻译等各种大规模数据并行计算应用领域

基于集群的高性能并行计算平台(Cluster Infrastructure)
- 允许用市场上现成的普通PC或性能较高的刀架或机架式服务器，构成一个包含数千个节点的分布式并行计算集群
并行程序开发与运行框架(Software Framework)
- 提供了一个庞大但设计精良的并行计算软件构架，能自动完成计算任务的并行化处理，自动划分计算数据和计算任务，在集群节点上自动分配和执行子任务以及收集计算结果，将数据分布存储、数据通信、容错处理等并行计算中的很多复杂细节交由系统负责处理，大大减少了软件开发人员的负担
并行程序设计模型与方法(Programming Model & Methodology)
- 借助于函数式语言中的设计思想，提供了一种简便的并行程序设计方法，用Map和Reduce两个函数编程实现基本的并行计算任务，提供了完整的并行编程接口，完成大规模数据处理

为什么MapReduce如此重要？

高效的大规模数据处理方法
改变了大规模尺度上组织计算的方式
第一个不同于冯诺依曼结构的、基于集群而非单机的计算方式的重大突破
目前为止最为成功的基于大规模计算资源的并行计算抽象方法

MapReduce在三个层面上的基本构思

如何对付大数据处理：分而治之

对相互间不具有计算依赖关系的大数据，实现并行最自然的办法就是采取分而治之的策略

什么样的计算任务可进行并行化计算？

不可分拆的计算任务或相互间有依赖关系的数据无法进行并行计算

一个大数据若可以分为具有同样计算过程的数据块，并且这些数据块之间不存在数据依赖关系，则提高处理速度的最好办法就是并行计算

上升到抽象模型：Mapper与Reducer

主要设计思想：为大数据处理过程中的两个主要处理操作：Map和Reduce提供了高层的并行编程抽象模型

典型的流式大数据问题的特征：

大量数据记录/元素进行重复处理
对每个数据记录/元素作感兴趣的处理、获取感兴趣的中间结果信息
排序和整理中间结果以利后续处理
收集整理中间结果
产生最终结果输出

Map Reduce：提供一种抽象机制，把做什么和怎么做分开，程序员仅需要描述做什么，不需要关心怎么做

Map: 对一组数据元素进行某种重复式的处理：(k1; v1) -> [(k2; v2)]
- 输入：键值对(k1; v1)表示的数据
- 处理：文档数据记录(如文本文件中的行，或数据表格中的行)将以“键值对”形式传入map函数；map函数将处理这些键值对，并以另一种键值对形式输出处理的一组键值对中间结果[(k2; v2)]
- 输出：键值对[(k2; v2)]表示的一组中间数据
Reduce: 对Map的中间结果进行某种进一步的结果整理：(k2; [v2]) -> [(k3; v3)]
- 输入：由map输出的一组键值对[(k2; v2)] 将被进行合并处理将同样主键下的不同数值合并到一个列表[v2]中，故reduce的输入为(k2; [v2])
- 处理：对传入的中间结果列表数据进行某种整理或进一步的处理,并产生最终的某种形式的结果输出[(k3; v3)] 。
- 输出：最终输出结果[(k3; v3)]

上升到构架：统一构架，为程序员隐藏系统层细节

主要需求、目标和设计思想
- 实现自动并行化计算
- 为程序员隐藏系统层细节
MapReduce提供统一的构架并完成以下的主要功能
- 任务调度：提交的一个计算作业(job)将被划分为很多个计算任务(tasks), 任务调度功能主要负责为这些划分后的计算任务分配和调度计算节点(map节点或reducer节点); 同时负责监控这些节点的执行状态, 并负责map节点执行的同步控制(barrier); 也负责进行一些计算性能优化处理, 如对最慢的计算任务采用多备份执行、选最快完成者作为结果
- 数据/代码互定位：为了减少数据通信，一个基本原则是本地化数据处理(locality)，即一个计算节点尽可能处理其本地磁盘上所分布存储的数据，这实现了代码向数据的迁移；当无法进行这种本地化数据处理时，再寻找其它可用节点并将数据从网络上传送给该节点(数据向代码迁移)，但将尽可能从数据所在的本地机架上寻找可用节点以减少通信延迟
- 出错处理：以低端商用服务器构成的大规模MapReduce计算集群中,节点硬件(主机、磁盘、内存等)出错和软件有bug是常态，因此,MapReducer需要能检测并隔离出错节点，并调度分配新的节点接管出错节点的计算任务
- 分布式数据存储与文件管理：海量数据处理需要一个良好的分布数据存储和文件管理系统支撑,该文件系统能够把海量数据分布存储在各个节点的本地磁盘上,但保持整个数据在逻辑上成为一个完整的数据文件；为了提供数据存储容错机制,该文件系统还要提供数据块的多备份存储管理能力
- Combiner和Partitioner:为了减少数据通信开销,中间结果数据进入reduce节点前需要进行合并(combine)处理,把具有同样主键的数据合并到一起避免重复传送; 一个reducer节点所处理的数据可能会来自多个map节点, 因此, map节点输出的中间结果需使用一定的策略进行适当的划分(partitioner)处理，保证相关数据发送到同一个reducer节点

主要设计思想与特点

向“外”横向扩展，而非向“上”纵向扩展
失效被认为是常态
把处理向数据迁移
顺序处理数据、避免随机访问数据
为应用开发者隐藏系统层细节
平滑无缝的可扩展性

Google/Hadoop MapReduce基本构架

借鉴函数式程序设计语言Lisp中的思想，定义了Map和Reduce两个抽象的操作函数：

map: (k1; v1) -> [(k2; v2)]
reduce: (k2; [v2]) -> [(k3; v3)]

特点：

描述了对一组数据处理的两个阶段的抽象操作
仅仅描述了需要做什么，不需要关注怎么做

Google MapReduce的基本工作原理

MapReduce 计算过程

失效处理

主节点失效

主节点中会周期性地设置检查点(checkpoint)，检查整个计算作业的执行情况，一旦某个任务失效，可以从最近有效的检查点开始重新执行，避免从头开始计算的时间浪费。
工作节点失效

工作节点失效是很普遍发生的，主节点会周期性地给工作节点发送心跳检测，如果工作节点没有回应，这认为该工作节点失效，主节点将终止该工作节点的任务并把失效的任务重新调度到其它工作节点上重新执行

带宽优化

问题

大量的键值对数据在传送给Reduce节点时会引起较大的通信带宽开销。
解决方案

每个Map节点处理完成的中间键值队将由combiner做一个合并压缩，即把那些键名相同的键值对归并为一个键名下的一组数值。

计算优化

问题

Reduce节点必须要等到所有Map节点计算结束才能开始执行，因此，如果有一个计算量大、或者由于某个问题导致很慢结束的Map节点，则会成为严重的“拖后腿者”。
解决方案

把一个Map计算任务让多个Map节点同时做，取最快完成者的计算结果。

用数据分区解决数据相关性问题

问题

一个Reduce节点上的计算数据可能会来自多个Map节点，因此，为了在进入Reduce节点计算之前，需要把属于一个Reduce节点的数据归并到一起。
解决方案

在Map阶段进行了Combining以后，可以根据一定的策略对Map输出的中间结果进行分区(partitioning)，这样即可解决以上数据相关性问题避免Reduce计算过程中的数据通信。
例如：有一个巨大的数组,其最终结果需要排序,每个Map节点数据处理好后,为了避免在每个Reduce节点本地排序完成后还需要进行全局排序,我们可以使用一个分区策略如:(d%R),d为数据大小，R为Reduce节点的个数，则可根据数据的大小将其划分到指定数据范围的Reduce节点上,每个Reduce将本地数据拍好序后即为最终结果

Hadoop MapReduce的基本工作原理

程序执行时的容错处理与计算性能优化

由Hadoop系统自己解决
主要方法是将失败的任务进行再次执行
TaskTracker会把状态信息汇报给JobTracker，最终由JobTracker决定重新执行哪一个任务
为了加快执行的速度，Hadoop也会自动重复执行同一个任务，以最先执行成功的为准（投机执行）
mapred.map.tasks.speculative.execution
mapred.reduce.tasks.speculative.execution

Hadoop MapReduce主要组件

文件输入格式InputFormat

定义了数据文件如何分割和读取
InputFormat提供了以下一些功能
- 选择文件或者其它对象，用来作为输入
- 定义InputSplits, 将一个文件分为不同任务
- 为RecordReader提供一个工厂，用来读取这个文件
有一个抽象的类FileInputFormat，所有的输入格式类都从这个类继承其功能以及特性。当启动一个Hadoop任务的时候，一个输入文件所在的目录被输入到FileInputFormat对象中。
FileInputFormat从这个目录中读取所有文件。然后FileInputFormat将这些文件分割为多个InputSplits。
通过在JobConf对象上设置JobConf.setInputFormat设置文件输入
的格式

InputFormat:	Description:	Key:	Value:
TextInputFormat	Default format; reads lines of text files	The byte offset of the line	The line contents
KeyValueTextInputFormat	Parses lines into key-val pairs	Everything up to the first tab character	The remainder of the line
SequenceFileInputFormat	A Hadoop-specific high performance binary format	user-defined	user-defined

输入数据分块InputSplits

InputSplit定义了输入到单个Map任务的输入数据
一个MapReduce程序被统称为一个Job，可能有上百个任务构成
InputSplit将文件分为64MB的大小
配置文件hadoop-site.xml中的mapred.min.split.size参数控制这个大小
mapred.tasktracker.map.taks.maximum用来控制某一个节点上所有map任务的最大数目

数据记录读入RecordReader

InputSplit定义了一个数据分块，但是没有定义如何读取数据记录
RecordReader实际上定义了如何将数据记录转化为一个(key,value)对的详细方法，并将数据记录传给Mapper类
TextInputFormat提供了LineRecordReader，读入一个文本行数据记录

Mapper

每一个Mapper类的实例生成了一个Java进程，负责处理某一个InputSplit上的数据
用Mapper.Context提供给每一个Mapper函数，用来提供上面两个对象的功能

Combiner

合并相同key的键值对，减少partitioning时候的数据通信开销
conf.setCombinerClass(Reduce.class);
是在本地执行的一个Reducer，满足一定的条件才能够执行。

Partitioner & Shuffle

在Map工作完成之后，每一个 Map函数会将结果传到对应的Reducer所在的节点，此时，用户可以提供一个Partitioner类，用来决定一个给定的(key,value)对传给哪个Reduce节点

Sort

传输到每一个Reducer节点上的、将被所有的Reduce函数接收到的Key,value对会被Hadoop自动排序（即Map生成的结果传送到某一个节点的时候，会被自动排序）

Reducer

做用户定义的Reduce操作
输出环境编程接口是Reducer.Context

文件输出格式OutputFormat

写入到HDFS的所有OutputFormat都继承自FileOutputFormat
每一个Reducer都写一个文件到一个共同的输出目录，文件名是part-nnnnn，其中nnnnn是与每一个reducer相关的一个号（partition id）
FileOutputFormat.setOutputPath()
JobConf.setOutputFormat()

OutputFormat:	Description
TextOutputFormat	Default; writes lines in “key \t value” form
SequenceFileOutputFormat	Writes binary files suitable for reading into subsequent MapReduce jobs
NullOutputFormat	Disregards its inputs

RecordWriter

TextOutputFormat实现了缺省的LineRecordWriter，以“key\t value”形式输出一行结果

Hadoop 分布式文件系统HDFS

HDFS的基本特征

模仿Google GFS设计实现
存储极大数目的信息（terabytes or petabytes），将数据保存到大量的节点当中；支持很大的单个文件。
提供数据的高可靠性和容错能力，单个或者多个节点不工作，对系统不会造成任何影响，数据仍然可用。通过一定数量的数据复制保证数据存储的可靠性和出错恢复能力。
提供对数据的快速访问；并提供良好的可扩展性，通过简单加入更多服务器快速扩充系统容量，服务更多的客户端。
与GFS类似，HDFS是MapReduce的底层数据存储支撑，并使得数据尽可能根据其本地局部性进行访问与计算。
HDFS对顺序读进行了优化，支持大量数据的快速顺序读出，代价是对于随机的访问负载较高。
数据支持一次写入，多次读取；不支持已写入数据的更新操作，但允许在文件尾部添加新的数据
数据不进行本地缓存（文件很大，且顺序读没有局部性）
基于块的文件存储，默认的块的大小是64MB
- 减少元数据的量
- 有利于顺序读写（在磁盘上数据顺序存放）
多副本数据块形式存储，按照块的方式随机选择存储节点，默认副本数目是3

HDFS可靠性与出错恢复

DataNode节点的检测
- 心跳：NameNode 不断检测DataNode是否有效
- 若失效，则寻找新的节点替代，将失效节点数据重新分布
集群负载均衡
数据一致性: 校验和checksum
主节点元数据失效
- Multiple FsImage and EditLog
- Checkpoint

HDFS文件系统操作命令

命令	说明
`-ls path`	显示所有目录与文件，包含拥有者、权限、修改时间等
`-lsr path`	同上，递归显示
`-put localSrc dest`	从Local传输文件、目录到HDFS
`-copyFromLocal localSrc dest`	同上
`-moveFromLocal localSrc dest`	同上，但会删除Local源文件、目录
`-get [-crc] src localDest`	从HDFS传输文件、目录到Local
`-copyToLocal [-crc] src localDest`	同上
`-moveToLocal [-crc] src localDest`	同上，但会删除HDFS源文件、目录
`-mv src dest`	在HDFS内移动文件、目录
`-cp src dest`	在HDFS内复制文件、目录
`-rm path`	删除文件、空目录
`-rmr path`	递归删除文件、空目录
`-mkdir path`	递归创建目录
`-touchz path`	以当前时间戳创建新文件，当已存在且大小不为0时返回0
`-cat filename`	显示文件内容
`-tail [-f] file`	显示文件最后1KB内容
`-test -[ezd] path`	当路径存在、大小不为0、为目录时返回1
`-chmod [-R] mode,mode,... path...`	更改文件权限
`-chown [-R] [owner][:[group]] path...`	更改文件拥有者
`-chgrp [-R] group path...`	更改文件拥有者的组
`-du path`	以Byte形式显示所有匹配文件的磁盘使用量
`-dus path`	显示总的磁盘使用量
`-getmerge src localDest [addnl]`	将所有匹配文件复制到LocalDest中
`-setrep [-R] [-w] rep path`	更改目标副本数目
`-stat [format] path`	显示文件、目录信息.
`-help cmd`	显示关于cmd的帮助信息。`-`可省略

在MapReduce程序中使用HDFS

通过fs.default.name的配置选项，Hadoop MapReduce程序可以自动从NameNode中获得文件的情况
HDFS接口包括：
- 命令行接口
- Hadoop MapReduce Job隐含的输入
- Java程序直接操作
- libhdfs从c/c++程序中操作

HDFS权限控制与安全特性

类似于POSIX的安全特性，不完全，主要预防操作失误
不是一个强的安全模型，不能保证操作的完全安全性
用户:当前登录的用户名, 即使用Linux自身设定的用户与组的概念
超级用户: 用于启动 bin/start-all.sh 或者 bin/start-dfs.sh 的用户名
超级用户组：配置参数：dfs.permissions.supergroup

Hadoop HDFS的编程

// TODO：暂时省略，有时间再加

编程示例

import java.util.Scanner;
import java.io.IOException;
import java.io.File;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FSDataInputStream;
import org.apache.hadoop.fs.FSDataOutputStream;
import org.apache.hadoop.fs.FileStatus;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path;
public class resultFilter
{
	public static void main(String[] args) throws IOException
    {
        Configuration conf = new Configuration(); // 以下两句中，hdfs和local分别对应HDFS实例和本地文件系统实例
        FileSystem hdfs = FileSystem.get(conf);
        FileSystem local = FileSystem.getLocal(conf);
        Path inputDir, localFile;
        FileStatus[] inputFiles;
        FSDataOutputStream out = null;
        FSDataInputStream in = null;
        Scanner scan; String str; byte[] buf; int singleFileLines; int numLines, numFiles, i;
        inputDir = new Path(args[0]);
        singleFileLines = Integer.parseInt(args[3]);
        try { 
            inputFiles = hdfs.listStatus(inputDir); //获得目录信息
            numLines = 0; 
            numFiles = 1; //输出文件从1开始编号
            localFile = new Path(args[1]);
            if(local.exists(localFile)) 
                local.delete(localFile, true); //若目标路径存在，则删除之
            for (i = 0; i<inputFiles.length; i++) {
            	if(inputFiles[i].isDir() == true) //忽略子目录
            		continue;
                System.out.println(inputFiles[i].getPath().getName());
            	in = hdfs.open(inputFiles[i].getPath());scan = new Scanner(in);
            	while (scan.hasNext()) {
            		str = scan.nextLine();
            		if(str.indexOf(args[2])==-1) 
                        continue; //如果该行没有match字符串，则忽略
            		numLines++;
            		if(numLines == 1) //如果是1，说明需要新建文件了
            		{
                        localFile = new Path(args[1] + File.separator + numFiles);
                        out = local.create(localFile); //创建文件
            			numFiles++;
            		}
            		buf = (str+"\n").getBytes();
            		out.write(buf, 0, buf.length); //将字符串写入输出流
            		if(numLines == singleFileLines) //如果已满足相应行数，关闭文件
                    { 
                        out.close(); 
                        numLines = 0; //行数变为0，重新统计 
                    }
            	}//end of while
            	scan.close();
                in.close();
            }//end of for
            if(out != null) 
                out.close();
        } //end of try
        catch (IOException e) { e.printStackTrace();}
    } //end of main
} //end of resultFilter

Hadoop系统安装运行与程序开发

// TODO: 暂时省略

MapReduce算法设计

MapReduce可解决哪些算法问题？

MapReduce 可广泛应用于搜索引擎（文档倒排索引，网页链接图分析与页面排序等）、Web日志分析、文档分析处理、机器学习、机器翻译等各种大规模数据并行计算应用领域各类大规模数据并行处理算法。

基本算法

各种全局数据相关性小、能适当划分数据的计算任务，如：

分布式排序
分布式GREP(文本匹配查找)
关系代数操作：如：选择，投影，求交集、并集，连接，成组，聚合…
矩阵向量相乘、矩阵相乘
词频统计(word count)，词频重要性分析(TF-IDF)
单词同现关系分析：典型的应用如从生物医学文献中自动挖掘基因交互作用关系
文档倒排索引
…

复杂算法或应用

Web搜索:：网页爬取、倒排索引、网页排序、搜索算法
Web访问日志分析：分析和挖掘用户在Web上的访问、购物行为特征、以定制个性化用户界面或投放用户感兴趣的产品广告
数据/文本统计分析：如科技文献引用关系分析和统计、专利文献引用分析和统计
图算法：并行化宽度优先搜索(最短路径问题，可克服Dijkstra串行算法的不足)，最小生成树，子树搜索、比对Web链接图分析算法PageRank，垃圾邮件连接分析
聚类(clustring)：文档聚类、图聚类、其它数据集聚类
相似性比较分析算法：字符序列、文档、图、数据集相似性比较分析
基于统计的文本处理：最大期望(EM)统计模型，隐马可夫模型(HMM)，……
机器学习：监督学习、无监督学习、分类算法（决策树、SVM…)
数据挖掘：
统计机器翻译
生物信息处理：DNA序列分析比对算法Blast：双序列比对、多序列比对生物网络功能模块(Motif)查找和比对
广告推送与推荐系统
…

大数据集上的简单算法能比小数据集上的复杂算法产生更好的结果！

MapReduce中可编程控制的阶段

Mapper / Reducer

Initialize: setup()
map() / reduce()
Close: cleanup()

Shuffle

Partitioner()
默认：HashPartitioner() (hadoop v0.21.0)

Sort

通过自定义的比较函数实现排序

MapReduce排序算法

Sort Algorithm in MapReduce
- map(k1, *) -> (k1, *) // Identity function
- shuffle and sort
  - (1) total-order partitioning
  - (2) local sorting
- reduce(k1, *) -> (k1, *) // Identity function
A customized total-order Partitioner
- recall that shuffle phase needs a Partitioner to partition the key space

Partitioner

(1) 如何避免在某些Reducer上聚集过多的数据而拖慢了整个程序
(2) 当有大量的key要分配到多个partition（也就是Reducer）时，如何高效地找到每个Key所属的partition
对Partitioner的要求
- 划分均匀
- 查找快速
TotalOrderPartitioner for TeraSort
- 一个提供全序划分的Partitioner
- 从Hadoop v0.19.0开始正式发布在库类中
为满足两个要求所采用的策略
- 通过采样获取数据的分布：预读一小部分数据采样(sample)，对采样数据排序后均分，假设有N个reducer，则取得N-1个分割点，以这些分割点划分区间
- 构建高效的划分模型：若Key 的数据类型是BinaryComparable的，即可以直接按字节比较大小（如Text），则以key构造TrieTree；否则以二分查找来确定key的所属区间
- Trie Tree, 一种高效的适于查找的数据结构，两级的trie可以最多对应大约256*256个reducer, 通常是足够的

MapReduce单词同现分析算法

单词同现矩阵
- 语料库的单词同现矩阵是一个二维 N×N矩阵
- N是语料库的词汇量（即，不同单词的数目）
- 矩阵元素M[i, j] 代表单词W[i] 与单词W [j]在一定范围内同现的次数（一个语句中，一个段落中，一篇文档中，或文本串中一个宽度为M个单词的窗口中，这些都依具体问题而定）
构建单词同现矩阵
- 同现矩阵的空间开销为 $O(n^2)$ ，因此难以直接放入内存中计算
- 简单地在单机上的实现，内存与磁盘之间的换页会使任务的执行十分缓慢
M.R. Algorithm (“pairs” approach) 伪代码:

class Mapper
	method Map(docid a, doc d)
		for all term w ∈ doc d do
			for all term u ∈ Neighbors(w) do
				//Emit count for each co-occurrence
				Emit(pair (w, u), count 1) 
class Reducer
    method Reduce(pair p; counts [c1, c2,…])
		s ← 0
		for all count c in counts [c1, c2,…] do
			s ← s + c //Sum co-occurrence counts
		Emit(pair p, count s)

算法的扩展
- 同现定义 Neighbors(w)为其他形式时该怎么实现？
  - 根据同现关系的不同，可能需要实现和定制不同的FileInputFormat和RecordReader
- 同现关系可扩展为从大量观察数据中进行任意离散关联事件的分析和数据挖掘
- 类似应用问题
  - 零售商通过分析大量的交易记录，识别出关联的商品购买行为（如：“啤酒和纸尿裤”的故事）
  - 从生物医学文献中自动挖掘基因交互作用关系

MapReduce文档倒排索引算法

Inverted Index(倒排索引)是目前几乎所有支持全文检索的搜索引擎都要依赖的一个数据结构。基于索引结构，给出一个词(term)，能取得含有这个term的文档列表(the list of documents)
Web Search中的问题主要分为三部分：
- crawling(gathering web content)
- indexing(construction of the inverted index)
- retrieval(ranking documents given a query)
crawling和indexing都是离线的，retrieval是在线、实时的

专利文献数据分析

HBase与Hive程序设计

HBase基本工作原理

HBase的设计目标和功能特点
- 针对 HDFS 缺少结构化半结构化数据存储访问能力的缺陷，提供一个分布式数据管理系统，解决大规模的结构化和半结构化数据存储访问问题
- 提供基于列存储模式的大数据表管理能力
- 可存储管理数十亿以上的数据记录，每个记录可包含百万以上的数据列
- 试图提供随机和实时的数据读写访问能力
- 具有高可扩展性、高可用性、容错处理能力、负载平衡能力、以及实时数据查询能力
HBase数据模型
- 逻辑数据模型
- 数据存储逻辑模型与 BigTable 类似但实现上有一些不同之处。
- 是一个分布式多维表，表中的数据通过：
  - 一个行关键字：row key
  - 一个列关键字：column key
  - 一个时间戳：time stamp
- 进行索引和查询定位的。
- 按照列存储的稀疏行列矩阵。物理存储格式上按逻辑模型中的行进行分割，并按照列族存储。
- 值为空的列不予存储，以节省存储空间
HBase的基本构架
- 由一个 MasterServer 和由一组子表数据区服务器 RegionServer 构成，分别存储逻辑大表中的部分数据
- 大表中的底层数据存于 HDFS 中
HBase的数据存储和管理
- 与 BigTable 类似，大表被分为很多个子表（ Region ），每个子表存储在一个子表服务器 RegionServer上
- 每个子表中的数据区 Region 由很多个数据存储块 Store 构成
- 而每个 Store 数据块又由存放在内存中的 memStore 和存放在文件中的 StoreFile 构成

HBase基本操作与编程方法示例

HBase shell 操作
创建表格与列举表格：create 'table', 'column', ...
插入数据：put 'table', 'column', ...
描述表信息：describe ''table
扫描数据：scan 'table'
限制列进行扫描：scan 'table', {COLUMN=>'cloumn:'}
HBase中的disable和enable

Hive基本工作原理

在Hadoop上用SQL进行数据分析
- Hive 包括一个高层语言的执行引擎，类似于 SQL 的执行引擎
- Hive 建立在 Hadoop 的其它组成部分之上，包括 Hive 依赖于HDFS 进行数据保存，依赖于 MapReduce 完成查询操作
Hive的组成模块
Hive的系统结构
Hive的数据模型
元数据存储：Metastore
数据的物理分布情况
Hive系统的配置

高级MapReduce编程技术

复合键值对的使用

用复合键让系统完成排序
1. 将value中需要排序的部分加入到key中形成复合键，这样将能利用MapRecue系统的排序功能完成排序。
2. 但需要实现一个新的Partitioner，保证原来同一key值的键值对最后分区到同一个Reduce节点上。
把小的键值对合并成大的键值对
1. 通常一个计算问题会产生大量的键值对，为了减少键值对传输和排序的开销，一些问题中的大量小的键值对可以被合并成一些大的键值对

用户自定义数据类型

Hadoop内置的数据类型
用户自定义数据类型
1. 需要实现Writable接口
2. 作为key或者需要比较大小时则需要实现WritableComparable接口

MapReduce 课程总结

http://blog.czccc.cc/p/c27cf766/

作者

Cheng

发布于

2019-12-18

更新于

2022-08-06

许可协议

MapReduce 课程总结

大数据技术简介

大数据的类型分类

大数据处理的主要技术问题

大数据研究的基本途径

？什么是大数据

？大数据特点: 5V

？三个层面的挑战

MapReduce 简介

为什么需要大规模数据并行处理

什么是MapReduce？

为什么MapReduce如此重要？

MapReduce在三个层面上的基本构思

如何对付大数据处理：分而治之

上升到抽象模型：Mapper与Reducer

上升到构架：统一构架，为程序员隐藏系统层细节

主要设计思想与特点

Google/Hadoop MapReduce基本构架

Google MapReduce的基本工作原理

失效处理

带宽优化

计算优化

用数据分区解决数据相关性问题

Hadoop MapReduce的基本工作原理

Hadoop MapReduce主要组件

文件输入格式InputFormat

输入数据分块InputSplits

数据记录读入RecordReader

Mapper

Combiner

Partitioner & Shuffle

Sort

Reducer

文件输出格式OutputFormat

RecordWriter

Hadoop 分布式文件系统HDFS

HDFS的基本特征

HDFS可靠性与出错恢复

HDFS文件系统操作命令

在MapReduce程序中使用HDFS

HDFS权限控制与安全特性

Hadoop HDFS的编程

编程示例

Hadoop系统安装运行与程序开发

MapReduce算法设计

MapReduce可解决哪些算法问题？

基本算法

复杂算法或应用

MapReduce中可编程控制的阶段

Mapper / Reducer

Shuffle

Sort

MapReduce排序算法

Partitioner

MapReduce单词同现分析算法

MapReduce文档倒排索引算法

专利文献数据分析

HBase与Hive程序设计

HBase基本工作原理

HBase基本操作与编程方法示例

Hive基本工作原理

高级MapReduce编程技术

复合键值对的使用

用户自定义数据类型

作者

发布于

更新于

许可协议

喜欢这篇文章？打赏一下作者吧

评论

目录