數據分布傾斜性指的是數據分布過度集中于數據空間的某端，造成“頭重腳輕”或者“比薩斜塔”等不均勻的分布特點。數據分布傾斜性將造成運算效率上的“瓶頸”和數據分析結果的“以偏概全”。
效率上的“瓶頸”
假如在大型商場中，共有A,B1,B2…..B9十家店鋪，其中A店鋪中有99W商品，B1,B2….B9這九家店鋪分別有1W商品。我們要統計商場中商品總數，計算初，采用HASHMAP作為存儲結構，其中Key：店鋪 Value：商品。我們的計算過程是先統計每個店鋪的商品總數，最后將結果累加?？梢园l現，由于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的大小。