作者yauhh (喲)
看板Cloud
標題Re: MapReduce (Re: [情報] 利用智慧型手機建構雲端
時間Mon Aug 30 20:51:00 2010
※ 引述《yauhh (喲)》之銘言：
: 我想MapReduce是個model,不一定有個完整的底層平台.
: 既然是programming model,有可能從一開始寫程式就可以順著這個心法做.
: 從檔案文件處理出發,首先要從檔案系統取得檔案清單. 這是map:
: TakeFiles(folder, nil):
當時我談MapReduce framework,同時在另一方面想,各種程式的寫法如何表達成
map-reduce的組合,也是個問題. 由於目前還沒把自己的framework做好,
現在有個想法只能用嘴上提一提.
在此要談的是map-reduce版本的sort. 我用Erlang語言來說明.
一般Quick sort是最令人滿意的排序了. Qsort遞迴定義為以下程式:
qsort([]) ->
[];
qsort([X|Xs]) ->
qsort([ Y || Y <- Xs, Y < X ]) ++ [X] ++ qsort([ Z || Z <- Xs, Z >= X]).
是在資料結構上,有個分解->遞迴->結合的處理過程.
在多運算單元的場合,分散式排序dsort是兩個map. 第一個map是
distribute(List, List):
for all Number in List,
emit(Number, to-be-Nth(number, List)).
拿到一列可容許長度的資料,對每個資料項目number取它應該在排序後的第幾個位置.
to-be-Nth函數找法很簡單,在預定排序是由小到大的前提之後,只要求List中有多少個
小於number的數字,將個數加一即為結果.
第二個map是
write(Skip, List<Number, Nth>):
for all Number, Nth in List<Number, Nth>
write Number at position #Nth
no_emit()
這map稍微改一下map的規格,使map可能送出一對資料,或者可能不送出資料.
這個map, write函數,是拿到一些可容許數量的數對,分別代表資料與排序位置,
它就把資料寫到指定的位置. 在此是引用檔案系統可以隨機寫入的假設.
Dsort程式,對應為以上第一個map ( distribute(List,List) ), 具體如下:
dsort(Xs) ->
L = length(Xs),
[ spawn(?MODULE, sort_node, [self(), Nth, Xs])
|| Nth <- lists:seq(1, length(Xs)) ],
wait([], L).
主要程式先對每個資料項目,做map到 sort_node 函數的動作. Erlang語言是內建
分散式系統訊息傳遞定義的語言,同樣一個spawn內建函數除了可以分生出程序之外,
也可以用以對其他計算點(別台電腦)指定要分生出程序. 以上dsort函數先分出很多
程序,分出程序同時給了所需的資料參數,接著就等待每個程序傳訊息回來.
等待L個訊息回來的wait函數定義如下:
wait(State, 0) ->
State;
wait(State, N) ->
receive
{Kth, Y} -> State1 = [{Kth,Y}|State]
end,
wait(State1, N-1).
然後sort_node定義為上述的第二個map ( write(Skip,List<Number,Nth>) ),
每一個sort_node的instance只送回一項數對.
kth_sort(Nth, Xs) ->
length([ Y || Y <- Xs, Y < lists:nth(Nth, Xs) ]) + 1.
sort_node(FromID, Nth, Xs) ->
FromID ! { lists:nth(Xs), kth_sort(Nth, Xs) }.
測試環境 Erlang R13B02, CPU Via 700 (大概吧,HP mini-note 2133/Xubuntu 10.4)
使用timer內建模組的 tc/3 函數做執行時間測試:
> timer:tc(sort, qsort, [lists:seq(1,200)]).
{31428, ... } 31428微秒
> timer:tc(sort, dsort, [lists:seq(1,200)]).
{12691, ... } 12691微秒
> timer:tc(sort, qsort, [lists:seq(1,200)]).
{25120, ... } 25120微秒
> timer:tc(sort, dsort, [lists:seq(1,200)]).
{7582, ... } 7582微秒
另外在四核心平台測的結果可能大不相同,不過,將dsort/1最後的wait([], L)刪除,
執行時間也是大幅刪減到比qsort/1遠遠較小. 而sort_node/3是在許多個分出來的
程序中同時進行,這種平行本身就節省了大量的計算時間.
這表示,我可以將程式寫成:第一個map送訊息叫第二個map分別處理每個單元,
而第二個map不必將結果帶回給第一個map. 而是由第二個map按照資料的新位置寫到
檔案系統中. 如此以完成分散式排序.
這種排序方法其實跟Quick sort比較,沒有很強的意義. 應該可以跟同是外部排序的
Merge sort好好比比看.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.115.187