mapreduce的一些算法设计，优化等（1）

本系列是根据书籍《Data-Intensive Text Processing with MapReduce.pdf》和工作中的一些mapreduce使用做的笔记：

本篇针对《Data-Intensive Text Processing with MapReduce》第三章：

 

1. local aggregation（局部合并）

 

IN-MAPPER COMBINING，也就是说，在map端进行合并。在hadoop的mapreduce过程中，map端在将中间数据传递到reduce端之前，

会先将数据写到本地磁盘。要知道，相对其他操作来说，读写磁盘和网络的延迟会带来较大的性能损耗。因此，尽可能减少

传递到reduce端的数据是能提高性能的。

 

以word count统计为例，增加local aggregation的伪码如下：

 

class Mapper
	method Initialize
		H <- new AssociativeArray
	method Map(docid a; doc d)
		for all term t in doc d do
			H{t} <- H{t} + 1
	method Close
	for all term t in H do
		Emit(term t; count H{t})

 

 

如果是一个完整的mapper的实现，继承自Mapper类，在setup方法中，初始化数据结构，在最后cleanup中输出结果

 

缺点：（1）. 这破坏了函数式编程的特性

      （2）. 算法不能假定输入数据的顺序，例如，用户的日志顺序，正常情况下，都是按照时间顺序打印的，但是在分布式系统上，

你不能假定你获得的输入顺序也是这样的（这个是个通用的原理，例如在写hive的udf或者udaf统计相关数据时，若要记录状态时，

也要记住这一点）；

      （3）. in-mapper combining需要内存足够大，能够容纳一个map任务的所有数据；其实一旦遇到内存问题后，也存在通用的解决

方案，可以使用block或者计数器的方式，block的意思是，使用内存进行统计，超过一个block的大小先将数据flush；计数器的意思

是，放入内存的对象可以设置一个阈值，超过这个值，则执行flush动作。不管是block还是计数器的方式，都要要预估一下。

 

 

2.对（pairs）与带（stripes）

 

以nlp中的词语共现作为例子，例如w12表示词语w1和词语w2共同出现测次数。共现矩阵的空间是O(n^2)，其中n是单词的数量，从给定的文档

中统计结果

 

（1）使用pairs算法，伪码：

 

class Mapper
	method Map(docid a; doc d)
		for all term w in doc d do
			for all term u in Neighbors(w) do
				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 // 共现次数累加
		Emit(pair p; count s)

 

 

（2）使用stripes算法

 

class Mapper
	method Map(docid a; doc d)
		for all term w in doc d do
			H <- new AssociativeArray
			for all term u in Neighbors(w) do
				H{u} <-  H{u} + 1 // 计算本文档中共现词的次数
			Emit(Term w; Stripe H)
class Reducer
	method Reduce(term w; stripes [H1;H2;H3; : : :])
		Hf <- new AssociativeArray
		for all stripe H in stripes [H1;H2;H3; : : :] do
			Sum(Hf;H) // 累积每个文档里同一个词对应的共现
		Emit(term w; stripe Hf)

 

 

两个算法对区别在于，使用的key，value不同。简单来说，pair是一个词与另一个词共现就输出一个key-value，但是stripe输出的key-value的key是本词，而value是所有与他共现的词

一些结论：

（1）pair的输出产生更多的中间数据，排序时间也多；

（2）stripe方式的value则是序列化和反序列化需要耗时相对较多，同时value值很大的时候，可能出现oom现象，的那是pair算法则不会有这个问题

（3）两者都可以使用local aggregation的方式优化

 

（4）根据实际测试，stripe算法的性能较好