文档章节

MapReduce Design Patterns

woodo
 woodo
发布于 2014/11/11 23:52
字数 1642
阅读 58
收藏 0
点赞 0
评论 0

1 (总计)Summarization Patterns

1.1(数字统计)Numerical Summarizations

 这个算是Built-in的,因为这就是MapReduce的模式. 相当于SQL语句里边Count/Max,WordCount也是这个的实现。

1.2(反向索引)Inverted Index Summarizations

 这个看着名字很玄,其实感觉算不上模式,只能算是一种应用,并没有涉及到MapReduce的设计。其核心实质是对listof(V3)的索引处理,这是V3是一个引用Id。这个模式期望的结果是:
 url-〉list of id

1.3(计数器统计)Counting with Counters

 计数器很好很快,简单易用。不过代价是占用tasktracker,最重要使jobtracker的内存。所以在1.0时代建议tens,至少<100个。不过2.0时代,jobtracker变得per job,我看应该可以多用,不过它比较适合Counting这种算总数的算法。
 context.getCounter(STATE_COUNTER_GROUP, UNKNOWN_COUNTER).increment(1);

2 (过滤)Filtering Patterns

2.1(简单过滤)Filtering

这个也算是Built-in的,因为这就是MapReduce中Mapper如果没有Write,那么就算过滤掉

了. 相当于SQL语句里边Where。

map(key, record):
    if we want to keep record then
    emit key,value

2.2(Bloom过滤)Bloom Filtering

以前我一直不知道为什么叫BloomFilter,看了wiki后,才知道,贴过来大家瞧瞧:
A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate.
其原理可以参见这篇文章:

http://blog.csdn.net/jiaomeng/article/details/1495500
要是让我一句话说,就是根据集合内容,选取多种Hash做一个bitmap,那么如果一个词的 hash落在map中,那么它有可能是,也有可能不是。但是如果它的hash不在,则它一定没有落在里边。此过滤有点意思,在HBase中得到广泛应用。接下来得实际试验一下。

Note: 需要弄程序玩玩

2.3(Top N)Top Ten


 这是一个典型的计算Top的操作,类似SQL里边的top或limit,一般都是带有某条件的top

操作。
 算法实现:我喜欢伪代码,一目了然:

class mapper:
    setup():
        initialize top ten sorted list
     
    map(key, record):
        insert record into top ten sorted list
        if length of array is greater-than 10 then
        truncate list to a length of 10

    cleanup():
        for record in top sorted ten list:
        emit null,record

class reducer:
    setup():
        initialize top ten sorted list

    reduce(key, records):
        sort records
        truncate records to top 10
        for record in records:
            emit record

2.4(排重)Distinct


 这个模式也简单,就是利用MapReduce的Reduce阶段,看struct,一目了然:

map(key, record):
    emit record,null

reduce(key, records):
    emit key

3 (数据组织)Data Organization Patterns


3.1(结构化到层级化)Structured to Hierarchical

这个在算法上是join操作,在应用层面可以起到Denormalization的效果.其程序的关键之处是用到了MultipleInputs,可以引入多个Mapper,这样便于把多种Structured的或者任何格式的内容,聚合在reducer端,以前进行聚合为Hierarchical的格式.
 MultipleInputs.addInputPath(job, new Path(args[0]),
TextInputFormat.class, PostMapper.class);
MultipleInputs.addInputPath(job, new Path(args[1]),
TextInputFormat.class, CommentMapper.class);
 在Map输出的时候,这里有一个小技巧,就是把输出内容按照分类,添加了前缀prefix,这样在Reduce阶段,就可以知道数据来源,以更好的进行笛卡尔乘积或者甄别操作. 从技术上讲这样节省了自己写Writable的必要,理论上,可以定义格式,来携带更多信息. 当然了,如果有特殊排序和组合需求,还是要写特殊的Writable了.
 outkey.set(post.getAttribute("ParentId"));
 outvalue.set("A" + value.toString());

3.2(分区法)Partitioning


 这个又来了,这个是built-in,写自己的partitioner,进行定向Reducer.

3.3(装箱法)Binning


 这个有点意思,类似于分区法,不过它是MapSide Only的,效率较高,不过产生的结果可能需

要进一步merge.
 The SPLIT operation in Pig implements this pattern.
 具体实现上还是使用了MultipleOutputs.addNamedOutput().

// Configure the MultipleOutputs by adding an output called "bins"
// With the proper output format and mapper key/value pairs

MultipleOutputs.addNamedOutput(job, "bins", TextOutputFormat.class,Text.class, NullWritable.class);

// Enable the counters for the job
// If there are a significant number of different named outputs, this
// should be disabled

MultipleOutputs.setCountersEnabled(job, true);

// Map-only job
job.setNumReduceTasks(0);

3.4(全排序)Total Order Sorting

这个在Hadoop部分已经详细描述过了,略。

3.5(洗牌)Shuffling

这个的精髓在于随机key的创建。
outkey.set(rndm.nextInt());
context.write(outkey, outvalue);


4 (连接)Join Patterns


4.1(Reduce连接)Reduce Side Join


 这个比较简单,Structured to Hierarchical中已经讲过了。

4.2(Mapside连接)Replicated Join


 Mapside连接效率较高,但是需要把较小的数据集进行设置到distributeCache,然后把

另一份数据进入map,在map中完成连接。


4.3(组合连接)Composite Join


 这种模式也是MapSide的join,而且可以进行两个大数据集的join,然而,它有一个限制就是两个数据集必须是相同组织形式的,那么何谓相同组织形式呢?
• An inner or full outer join is desired.
• All the data sets are sufficiently large.
• All data sets can be read with the foreign key as the input key to the mapper.
All data sets have the same number of partitions.
• Each partition is sorted by foreign key, and all the foreign keys reside in the associated partition of each data set. That is, partition X of data sets A and B contain
the same foreign keys and these foreign keys are present only in partition X. For a visualization of this partitioning and sorting key, refer to Figure 5-3.
• The data sets do not change often (if they have to be prepared).

// The composite input format join expression will set how the records
// are going to be read in, and in what input format.
conf.set("mapred.join.expr", CompositeInputFormat.compose(joinType,
KeyValueTextInputFormat.class, userPath, commentPath));


4.4(笛卡尔)Cartesian Product


 这个需要重写InputFormat,以便两部分数据可以在record级别联合起来。sample略。


5 (元模式)MetaPatterns


5.1(链式Job)Job Chaining


 多种方式,可以写在driver里边,也可以用bash脚本调用。hadoop也提供了JobControl

可以跟踪失败的job等好的功能。


5.2(折叠Job)Chain Folding


 ChainMapper and ChainReducer Approach,M+R*M


5.3(合并Job)Job Merging


 合并job,就是把同数据的两个job的mapper和reducer代码级别的合并,这样可以省去

I/O和解析的时间。

6 (输入输出)Input and Output Patterns


6.1 Customizing Input and Output in Hadoop

  • InputFormat
      getSplits
      createRecordReader

  • InputSplit
      getLength()
      getLocations()

  • RecordReader
      initialize
      getCurrentKey and getCurrentValue
      nextKeyValue
      getProgress
      close

  • OutputFormat
      checkOutputSpecs
      getRecordWriter
      getOutputCommiter

  • RecordWriter
      write
      close
     


 6.2 (产生Random数据)Generating Data


 关键点:构建虚假的InputSplit,这个不像FileInputSplit基于block,只能去骗hadoop了。


 6.3 External Source Output
 6.4 External Source Input
 6.5 Partition Pruning 剪除杂生


 上面三个模式,可以用一个例子来,这个例子很有意思,就是读取Redis数据,运行MapReduce,输出到Redis,我想这个是大多数应用可以借鉴的。

Note: 需要弄程序玩玩.


 
(趋势)Trends in the Nature of Data


 Images, Audio, and Video
 Streaming Data

© 著作权归作者所有

共有 人打赏支持
woodo
粉丝 5
博文 57
码字总数 32118
作品 0
朝阳
高级程序员
MapReduce 计数器简介

1、计数器简介 在许多情况下,一个用户需要了解待分析的数据,尽管这并非所要执行的分析任务 的核心内容。以统计数据集中无效记录数目的任务为例,如果发现无效记录的比例 相当高,那么就需要...

大数据之路
2014/06/09
0
3
2014-11-12--Hadoop的基础学习(三)--Hadoop中MapReduce框架入门

1.MapReduce的简单概念 百度百科:MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行运算。概念"Map(映射)"和"Reduce(归约)",和他们的主要思想,都是从函数式编程语言里借来的...

查封炉台
2014/11/16
0
8
如何分布式运行mapreduce程序

如何分布式运行mapreduce程序 一、 首先要知道此前提 若在windows的Eclipse工程中直接启动mapreduc程序,需要先把hadoop集群的配置目录下的xml都拷贝到src目录下,让程序自动读取集群的地址后...

Zero零_度
2015/09/06
0
0
Spark和MapReduce的区别

性能: Spark在内存中处理数据,而MapReduce是通过map和reduce操作在磁盘中处理数据。所以从这方面讲Spark的性能是超过MapReduce的。但是当数据量比较大,无法全部读入内存时,MapReduce就比...

无精疯
04/26
0
0
Hadoop源代码分析(包hadoop.mapred中的MapReduce接口)

前面已经完成了对org.apache.hadoop.mapreduce的分析,这个包提供了Hadoop MapReduce部分的应用API,用于用户实现自己的MapReduce应用。但这些接口是给未来的MapReduce应用的,目前MapReduce...

超人学院
2015/05/25
0
0
hadoop 学习笔记:mapreduce框架详解

这个觉得写得特别的详细,有一些细节可能要去看书,会理解的更好点,,,   Mapreduce初析   Mapreduce是一个计算框架,既然是做计算的框架,那么表现形式就是有个输入(input),mapre...

LIPING234
2013/10/25
0
0
Hadoop中的MapReduce(5)

在MapReduce中,它也是主从结构,主节点:JobTracker,从节点:TaskTracker。主节点只有一个从节点有很多个,主节点在主机上,从节点分布到其他机器上。 JobTracker: 作用: 1、负责接收用户...

肖鋭
2014/02/23
0
0
Hadoop、MapReduce、YARN和Spark的区别与联系

(1) Hadoop 1.0 第一代Hadoop,由分布式存储系统HDFS和分布式计算框架MapReduce组成,其中,HDFS由一个NameNode和多个DataNode组成,MapReduce由一个JobTracker和多个TaskTracker组成,对应...

cuiyaonan2000
05/08
0
0
Hadoop2.X的安装与配置(二)本地模式

在上一篇文章中,我们介绍了Hadoop2.X安装与配置前的准备阶段。 在本地模式配置前,首先完成准备阶段。 点击如下链接,进入准备阶段的配置 https://blog.csdn.net/weixin38187469/article/d...

weixin_38187469
04/16
0
0
Hadoop的辉煌还能延续多久?

Hadoop技术已经无处不在。不管是好是坏,Hadoop已经成为大数据的代名词。短短几年间,Hadoop从一种边缘技术成为事实上的标准。看来,不仅现在Hadoop是企业大数据的标准,而且在未来,它的地位...

一枚Sir
2014/08/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

回想过往,分析当下,着眼未来

好久没有真正的在纸质笔记本上写过东西了,感觉都快不会写字了,笔画都不知道怎么写了。接下来就说说咱们的正事。 2018年7月22日,我做了一个决定,那就是去参加安全培训(可能是我职业生涯中...

yeahlife
40分钟前
1
0
关于工作中的人际交往

关于工作中的人际交往 Intro 写了篇发泄情绪的博客,但不会发布出来。 大概就是,要么忍,要么滚。 以及一些不那么符合社会主义核心价值观,不满于大资本家与小资本家剥削的废话。

uniqptr
45分钟前
0
0
springMVC的流程

1.用户发送请求至前端控制器DispatcherServlet 2.DispatcherServlet收到请求调用HandlerMapping处理器映射器。 3.处理器映射器根据请求url找到具体的处理器,生成处理器对象及处理器拦截器(...

JavaSon712
今天
0
0
大数据教程(3.2):Linux系统软件安装之自动化脚本

博主前面文章有介绍过软件的安装,可以帮助IT人员顺利的完成功能软件安装;但是,对于我们运维人员或者需要管理软件安装的项目经理来说,有些应用一次行需要搭建很多台相同的软件环境(如tom...

em_aaron
今天
0
1
Spring Boot 2.0.3 JDBC整合Oracle 12

整合步骤 1. Oracle驱动引入 Oracle驱动一般不能通过maven仓库直接下载得到,需自行下载并导入到项目的lib目录下,建议通过如下pom依赖引入下载的Oracle驱动 <!-- Oracle 驱动 -->...

OSC_fly
今天
0
0
java 8 并行流 - 1

下面创建一个并行流,与顺序流 //顺序流Stream.iterate(0L, i -> i + 1) .limit(Integer.MAX_VALUE) .reduce(0L, Long::sum);//并行流Stream.iterate(0L, i -> i......

Canaan_
今天
0
0
数据结构与算法5

二分法采用向下取整的方法 使用有序数组的好处是查找的速度比无序数组快的多,不好的方面是因为要将所有靠后的数据移开,所以速度较慢,有序数组和无序数组的删除操作都很慢。 有序数组在查找...

沉迷于编程的小菜菜
昨天
1
1
SpringBoot | 第十一章:Redis的集成和简单使用

前言 上几节讲了利用Mybatis-Plus这个第三方的ORM框架进行数据库访问,在实际工作中,在存储一些非结构化或者缓存一些临时数据及热点数据时,一般上都会用上mongodb和redis进行这方面的需求。...

oKong
昨天
5
0
对基于深度神经网络的Auto Encoder用于异常检测的一些思考

一、前言 现实中,大部分数据都是无标签的,人和动物多数情况下都是通过无监督学习获取概念,故而无监督学习拥有广阔的业务场景。举几个场景:网络流量是正常流量还是攻击流量、视频中的人的...

冷血狂魔
昨天
0
0
并发设计之A系统调用B系统

A-->B A在发送请求之前,用乐观锁,减少对B的重复调用,这样一定程度上是幂等性。 比如A系统支付功能,要调用B系统进行支付操作,但是前端对"支付"按钮不进行控制,即用户会不断多次点击支付...

汉斯-冯-拉特
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部