数据分布倾斜性指的是数据分布过度集中于数据空间的某端，造成“头重脚轻”或者“比萨斜塔”等不均匀的分布特点。数据分布倾斜性将造成运算效率上的“瓶颈”和数据分析结果的“以偏概全”。
效率上的“瓶颈”
假如在大型商场中，共有A,B1,B2…..B9十家店铺，其中A店铺中有99W商品，B1,B2….B9这九家店铺分别有1W商品。我们要统计商场中商品总数，计算初，采用HASHMAP作为存储结构，其中Key：店铺 Value：商品。我们的计算过程是先统计每个店铺的商品总数，最后将结果累加。可以发现，由于A有99W商品，按照1+1的累积方式（假如1+1耗时1秒），我们要加99W个1才能得到A店铺的商品总数（总耗时99W秒），而B1,B2….B9只需分别累加1W个1（分别耗时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应该是最受欢迎的。
没想到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的大小。