2011年12月22日

MapReduce 数据分布倾斜性

数据分布倾斜性指的是数据分布过度集中于数据空间的某端,造成“头重脚轻”或者“比萨斜塔”等不均匀的分布特点。数据分布倾斜性将造成运算效率上的“瓶颈”和数据分析结果的“以偏概全”。


效率上的“瓶颈”

假如在大型商场中,共有A,B1,B2..B9十家店铺,其中A店铺中有99W商品,B1,B2.B9这九家店铺分别有1W商品。我们要统计商场中商品总数,计算初,采用HASHMAP作为存储结构,其中Key:店铺 Value:商品。我们的计算过程是先统计每个店铺的商品总数,最后将结果累加。可以发现,由于A99W商品,按照1+1的累积方式(假如1+1耗时1秒),我们要加99W1才能得到A店铺的商品总数(总耗时99W秒),而B1,B2.B9只需分别累加1W1(分别耗时1W秒),而为了得到商场中的商品总数,我们必须等待所有店铺都分别累计结束才能处理总和,显而易见,此时运算瓶颈便集中在A店铺的商品累计上。

这类状况经常发生在分布式运算过程中,比如Hadoop Job计算,因为map/reduce 过程中是以Key-value形式来处理数据,假如某key下的数据量太大,会导致整个计算过程中move/shuffle/sort的耗时远远高于其他key,因此该Key变成为效率“瓶颈”。一般解决办法是,自定义partitioner,对所有的Value进行自定义分组,使得每组的量较平均,从而解决时间瓶颈问题。


数据分析结果的“以偏概全”

同样使用上述的“商场”案例,并且在此基础上我们假设A店铺,B9店铺是卖低端商品,而B1,B2..B8是卖高端商品,销量较小。如果我们要根据商品销售状况分析店铺在买家当中的受欢迎程度。由于A店铺本身商品量大,而且定位的销售价位是属于薄利多销,如果只从销售量的考虑,我们会以为A店铺在商场中是最受买家欢迎的,造成“片面”的分析结果。

其实,遇到这种情况,我们首先的分析卖家性质和买家性质,并且使用相对量来作为评估值,比如A店铺卖低端商品,日销售量1W商品,1W/99W<1%, B9店铺卖低端商品,日销售量5K商品,5K/1W=50%,所以在低端买家中,低端商品店铺B9应该是最受欢迎的。

posted @ 2011-12-22 10:17 Ric Dong 阅读(262) | 评论 (0)编辑 收藏

2011年12月21日

MapReduce 解析XML算法的一点构思

没想到Hadoop在解析XML时如此纠结,以至于新版api的mapreduce竟然放弃了XML格式的format以及reader,在老版(hadoop-0.19.*)的streaming模块提供了这样的api,由于我用的hadoop-0.20.2 3U1版本,因此需要把处理XML的几个类移植过来使用。
 
移植所带来的问题是各处依赖包,和各种api不兼容。没关系,我可以看一下源码,然后自己写一个。细看了一下reader的代码,发现mapreduce使用了BufferedInputStream的mark,reset来寻找XML的tag,这个tag就是我们在提交作业所设置的,比如<log>,</log>这样的标签。Java中stream流的mark和reset,允许指针回读,即在找到<log>时,mark一下指针,然后再找到</log>标签,最后通过reset方法,返回到mark的位置,把<log></log>内的数据读取出来。但在匹配的过程中,我发现mapred使用了BufferedInputStream 的 read(); 方法,该方法返回下一个可读的字节。那么整个处理过程就是读一个字节,比较一个字节,我没有在mapreduce中用这样的算法,但我测试过,向缓冲区(BufferedInputStream)中一个字节一个字节的读,性能严重不足,read(); 方法平均返回时间在331纳秒,处理一个170M的xml文档(tag比较多),竟然花了200+秒。(streaming模块还写了一个faster*方法,哎,慢死了)
 
周敏同学提供了pig中处理xml的reader,但pig那边的代码我还没细看,也不知道hadoop的jira中有没有新的feature来解决现有xml的问题。如果有的话,不防可以告诉我一下下。呵呵。 
 
现在有一个构思,即主要思想仍然围绕字节比较,因为字符串匹配效率更低,另外算法源于String.indexOf(“”),即找到<log>这个后,记住位置,然后再找</log>,这样算完全匹配,中间的内容用system.arraycopy来复制到新的字节数组,目前这算法我实现了一半,即找到<log>和</log>后,把这两个签标全部替换掉,170M文档,用时2.2秒(最快1.3秒)。
 
算法及问题:
首先提供一个BufferedInputStream,默认大小8k,在程序中建一个字节数组,大小为4k,即每次向BufferedInputStream读4k,这个效率是很不错的,然后去寻找<log>.toArray这样的字节数组,这一步速度是很惊人的。但这里有一个小的问题,即每次读4k的大小去处理,那很有可能<log></log>位于两次读取的一尾一头,那么我的想法是做一个半循环的字节数组,即如果在4k的字节数组中的最后找到<log>,那么就把前面未匹配的仍掉,然后把<log>标签移到字节数组最前端,然后另用这个字节数组再向BufferedInputStream中去读4k-5长度的内容(5是<log>的字节长度)。关于4k这个大小,首先要对XML数据进行sampling,即确定<log></log>当中的内容长度,然后再定这个缓冲buf的大小。

posted @ 2011-12-21 21:15 Ric Dong 阅读(260) | 评论 (0)编辑 收藏

仅列出标题  
<2022年6月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

导航

统计

留言簿

文章档案(2)

搜索

最新评论