Làm quen với mô hình MapReduce - Giới thiệu và Bài Tập (DS101). Môn Công nghệ | Đại học Trường Đại học Công nghệ thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh

lOMoAR cPSD| 58968691
1. Làm quen với mô hình MapReduce Chương 1: 1. Giới thiệu
là một mô hình nôi tiếng trong tính toán phân tán, MapReduce
thiệu trong bài báo MapReduce. Một chương trình viết được giới
ình MapReduce có kha năng chia nho một công việc (1 ến theo mô h
hành song song, sau đó kết hợp các kết qua lại đế job) đế ti t qua cuôi cùng. cho ra kế
ẽ dành đế giới thiệu vế7 MapReduce. Sau đó bài sẽ Bài này s
giới bài tập MapReduce được lây từ lớp distributed a thiệu vế7
MIT. Bài tập này sư dụng ngôn ngữ lập trình Go. system cu Chương 2:
2. Làm quen với mô hình MapReduce
Đế hiếu hơn ế7 MapReduce, chúng ta cùng xem chu trình đ v ế thực
hiện một job cua MapReduce.
Đọc dữ liệu đâ7u vào: Dữ liệu đâ7u vào có thế là một file
input hoặc một tập hợp nhiế7u file input. Nếu một file
input quá lớn ta có thế chia nho file ra làm nhiế7u file
khác nhau. Ý tương ơ đây là, môLi một file input sẽ được xư lý bơi một map task.
Xư lý dữ liệu đâ7u vào: Thực hiện Map, trộn/kết hợp các kết
qua tạo ra các file output trung gian.
Đọc dữ liệu từ các file trung gian
Xư lý dữ liệu từ các file trung gian: Thực hiện Reduce
Tập hợp kết qua output cua reduce đế cho ra kết qua cuôi
Sơ đô7 tông quan MapReduce
Mô hình MapReduce sẽ là bộ khung, người lập trình sẽ cung câp
cho bộ khung đó những thứ sau:
Một tập hợp các file input hoặc một file input lOMoAR cPSD| 58968691
Hàm MapFunc(key, value): hàm này xư lý một key và value tương
ứng rô7i cho xuât ra một tập hợp các cặp key, value trung gian
Hàm ReduceFunc(key, value[]): hàm này xư lý các value cua cùng
một key trung gian đế cho ra value cuôi cùng cua key đó.
Một sô nReduce là sô task reduce mà người dùng muôn.
Sau đây là ví dụ cụ thế vế7 thuật toán MapReduce được dùng trong bài
toán word count cơ ban, là bài toán đếm tông sô lâ7n xuât hiện cua
từng từ trong một tập hợp các file text.
Sơ đô7 MapReduce với bài toán word count
Trong sơ đô7 trến, ta gia dụ có 3 file input. MôLi một map task xư lý một file input.
MôLi map task đọc một file. Gia sư, ta có nội dung các file như
trến hình: file 1 có các từ “a”, “a”, “b”, “c”, tương tự với file 2 và file 3.
Task map 1 đọc file 1, với môLi một lâ7n một từ xuât hiện, thếm
giá trị 1 vào value cua cua từ đó. Như thế, map 1 sẽ có key “a”
với value là [1,1], “b” có value [1], “c” có value là [1].
Tương tự như vậy với các task map còn lại.
Sau đó, ta săp xếp các key đế sao cho môLi key đế7u được xư lý
bơi một task reduce duy nhât. Ở đây task reduce 0 xư lý key
“a”, “b” còn task reduce 1 xư lý key “c”, “d”. Có một cách đế
cài đặt là: reduceIndex=hash(key) %nReduce=ℎℎ()% lOMoAR cPSD| 58968691
MôLi task reduce xư lý nhiế7u key, với môLi key thì task này
dô7n các value lại đế ra 1 value duy nhât là sô lâ7n xuât hiện cua cua key đó.
Bước cuôi cùng là gộp tât ca các output ra thành một output cuôi.
Ta có thế thây, có tông cộng nMap∗nReduce∗ sô file trung gian. Chương 3:
3. Làm quen với mã nguô7n MapReduce Mã nguô7n c vế7
ua bài tập được lưu ơ đây. Bạn câ7n có một git đế máy cu
clone a mình, dùng lệnh sau:
git clone git://g.csail.mit.edu/6.824-golabs-2018 6.824
Phâ7n mã nguô7n này hôL trợ chạy MapReduce theo hai cách, một là
tuâ7n tự, hai là phân tán.
Cách thứ nhât, mô hình sẽ chạy các việc map và reduce lâ7n
lượt từng việc một. Ví dụ nếu có 3 task map và 2 task
reduce, mô hình sẽ chạy task map1, map2, map3, rô7i đến
reduce1, reduce2, xong cái trước rô7i mới đến cái sau.
Cách thứ hai là chạy phân tán. Với cách này, mô hình này sẽ
chạy các task map song song với nhau, môLi task một thread.
Khi tât ca các task map đã hoàn thành, nó sẽ băt đâ7u chạy
các task reduce, môLi task một thread, song song với nhau.
Khi tât ca các task reduce đã hoàn thành, nó sẽ gom output lại. Chương 4:
4. Map/Reduce input và output ến cua bài t Phâ7n đâ7u ti
ập chúng ta sẽ phai hoàn thiện mô
MapReduce. Ph hình â7n mô hình này còn thiếu hàm doMap() và
doReduce(). Đ hàm ế tránh hiếu nhâ7m, ơ đây ta có doMap() và
ma pFunc(); cũng như doReduce() và reduceFunc().
doMap() là hàm khung cua mô hình đế thực hiện một map task.
Hàm này sẽ đọc input, gọi hàm mapFunc(), lây output cua hàm lOMoAR cPSD| 58968691
mapFunc(), săp xếp/chia nho ra đế viết ra các file trung gian tương ứng.
doReduce(), là hàm khung cua mô hình đế thực thi
reduce task. Hàm này sẽ đọc input từ file trung
gian, gọi reduceFunc() và lây output cua
reduceFunc() viết ra các file output.
mapFunc() và reduceFunc() là hàm thực thi job, do
người dùng MapReduce cung câp, tuỳ vào làm job gì
mà viết hàm mapFunc() phù hợp.
Phâ7n này sẽ trình bày sơ lược thuật toán cua hai hàm
doMap() và hàm doReduce() bằng pseudo-code.
doMap(inputFile, nReduce, mapIndex, mapFunc()): content = read(inputFile)
mapFuncResult = mapFunc(inputFile, content) // return list, mỗi phần
tử của list là một cặp KeyValue
for KeyValue in mapFuncResult:
reduceIndex = hash(KeyValue.Key) % nReduce
intermediate_file_name = "map" + mapIndex + "reduce" +
reduceIndex // xây dựng tên file trung gian
write(intermediate_file_name, KeyValue)
doReduce(reduceIndex, nMap, reduceFunc()):
dict = {} // hash map key-> values for mapIndex in (0, nMap):
// đọc input từ nMap file trung gian
intermediate_file_name = "map" + mapIndex + "reduce" + reduceIndex lOMoAR cPSD| 58968691 content =
read(intermedia_file_name) for KeyValue in content:
dict[KeyValue].append(KeyValue.Value) reduce_file_out = "reduce" +
reduceIndex for KeyValue.Key, values in dict:
reduceFuncResult = reduceFunc(KeyValue.Key, values) // return
một value, là tổng hợp tất cả các value của một key
write(reduce_file_out, (Key reduceFuncResult))
Đế kiếm tra xem mô hình có triến khai đúng không, chạy test và
so sánh output với output sau:
$ env "GOPATH=$PWD/../../" go test -v -run
Sequential === RUN TestSequentialSingle
master: Starting Map/Reduce task test Merge:
read mrtmp.test-res-0 master: Map/Reduce task completed --- PASS:
TestSequentialSingle (1.34s) === RUN
TestSequentialMany master: Starting Map/Reduce task test Merge: read mrtmp.test-res-0 lOMoAR cPSD| 58968691
Merge: read mrtmp.test-res-1 Merge: read mrtmp.test-res-2 master:
Map/Reduce task completed --- PASS: TestSequentialMany (1.33s) PASS ok mapreduce 2.672s Chương 5:
5. Dùng MapReduce đế viết bài
toán word count - đếm từ
Bây giờ khi mô hình MapReduce đã hoàn tât, ta có thế viết các
chạy trến MapReduce. Phâ7n này sẽ trình bày bài toán đếm
ua hàm MapFunc() và hàm ReduceFunc(). Lưu ý là n này s job đế
ẽ làm MapReduce chạy Sequential - chạy tuâ7n từ và thuật toán c tự. phâ7
Bài toán này cho ta một tập hợp file input. Yếu câ7u là ta phai
ô lâ7n xuât hiện cua từng từ một trong tât ca các file đó. V
đếm ới mô hình MapReduce hoàn tât, mô hình s tông s mọi ẽ làm cho ta tât ca việc, bao g ô7m: Đọc input Gọi hàm MapFunc()
Chia nho output cua MapFunc() ra các file trung gian
Đọc input từ các file trung gian và phân phôi cho hàm ReduceFunc() Gọi hàm ReduceFunc()
Lây output cua hàm ReduceFunc() và dô7n lại thành output cuôi
Công việc cua ta trong phâ7n này là phai viết hàm MapFunc() và
hàm ReduceFunc() đế mô hình MapReduce có thế gọi. Hàm MapFunc()
lây input là một Key và một Value, trong đó Key ơ đây là tến
file input, Value là nội dung cua file. Thực ra với cách triến
khai mô hình MapReduce này, chúng ta không câ7n dùng đến Key mà lOMoAR cPSD| 58968691
chỉ quan tâm đến value, vì nội dung file đã được DoMap() đọc
rô7i. Ngoài ra, vì với mapFunc(), ta thếm 1 vào values với môLi
một lâ7n key xuât hiện nến chỉ câ7n tính độ dài cua values là
biết key đó xuât hiện bao nhiếu lâ7n. Sau đây là pseudo-code. mapFunc(Key, Value):
output = [] // list với mỗi phần tử là một cặp KeyValue
words = split(Value) // chia nội dung file ra thành từng từ for word in words: KeyValue = (word, 1) output.append(KeyValue) return output reduceFunc(Key, Value[]): return len(Value[])
Với hai hàm mapFunc() và reduceFunc() hoàn tât, mô hình
MapReduce này sẽ đọc được sô lâ7n xuât hiện cua từng từ trong
tât ca các file input. Đế kiếm tra xem kết qua, ta chạy lệnh sau
đế thực hiện word count và xem kết qua. File output sẽ tến là mrtmp.wcseq
$ cd "$GOPATH/src/main" $ time go run wc.go
master sequential pg-*.txt master: Starting Map/Reduce task wcseq Merge: read mrtmp.wcseq-res-0 lOMoAR cPSD| 58968691
Merge: read mrtmp.wcseq-res-1 Merge:
read mrtmp.wcseq-res-2 master:
Map/Reduce task completed 2.59user 1.08system 0:02.81elapsed
$ sort -n -k2 mrtmp.wcseq | tail -10
that: 7871 it: 7987 in: 8415 was:
8578 a: 13382 of: 13536 I: 14296 to: 16079 and: 23612 the: 29748 Chương 6: 6. Kết luận
Đây là một bài tập khá thú vị (và không hế7 dếL dàng) giúp chúng ta hiếu vế
7 mô hình MapReduce và cách triến khai MapReduce với
ngôn ngữ Go. Bài tập đòi hoi người làm phai tự đọc hiếu mã
nguô7n và tra cứu tài liệu đế viết chương trình với Go, nếu bạn chưa dùng Go bao giờ.
Mô hình này còn có thế chia nho việc và chạy việc song song, tận
dụng CPU đế giam thời gian thực thi. Bạn đọc có thế xem chi tiết
đế7 bài tập trong phâ7n tham khao. Chương 7: 7. Tham khao [1] “Lab 1: MapReduce”
http://nil.csail.mit.edu/6.824/2018//labs/lab-1.html