[tech]淺談 partition sort (1

[tech]淺談 partition sort (1

partition sort 就是一種Map Reduce的精神，
其實，在 Google 發表Map Reduce的paper 以前，
我想實際上有遇到"Big Data"的公司，都有這樣類似的解法。
只是後來Hadoop把這件事情吵熱了，
甚至紛紛使用了Hadoop，

不過我對Google內部使用的Map Reduce的framework還是，很好奇。

基本上有external sort兩種解法，

• merge sort


• partition sort

partition sort有幾點要注意的，
你建立的partition table決定你的效率好壞，
也就是說，要是你把大部分的要處理的資料分到同一台機器去，或者是造成某幾台機器要計算的量其實是很少的。
那就沒有辦法達到 balance 的效果。
所以，我們預期的應該是，當partition出去之後，每個部份做完處理的時間應該是一樣的，這樣才不用等待，並且充份利用每個partiion的計算力。

要建立partition table有幾個方式，

• sampling

1. 取all record


2. 取前面幾筆record


3. random取幾筆record

透過抽樣，如果要sort的量夠大，我們就能假設，這樣的結果有一定的正確性。
經由控制reducer的num數，與每一個地方可以用的mem大小，能夠提高效率。

整個而言，要建立的partition table，有一個重要的特點：

同樣key的record會被分類到同一個partition去，
每一個partition彼此都有order順序的。