Re: MapReduce (Re: [情報] 利用智慧型手機建構雲端

看板Cloud作者yauhh (喲)時間14年前 (2010/08/30 20:51)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串6/6 (看更多)

※ 引述《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