Phác họa bài post:
ⓐ BigFiles,
Clusters.
ⓑ Ý tưởng
MapReduce.
ⓒ
Implementation (cài đặt thực thi).
ⓓ Dataflow
(dòng chảy dữ liệu).
ⓔ Performance
(Hiệu suất).
ⓕ Experience
(trải nghiệm MapReduce tại Google).
ⓖ Hadoop,
Spark
~
Để giúp anh/chị
quyết định có đọc tiếp hay không, tôi xin phép cung cấp các thông tin liên quan
đến bài post này như sau:
·
Chủ
đề: Mô hình lập trình,
điện toán phân tán, hệ điều hành.
·
Tính
thời sự: Năm 2004 (có đề
cập vài thông tin gần đây: 2020, 2021).
·
Thời
gian đọc: 7 phút, lồng
vào thời gian uống cà phê (uống cà phê xong là đọc xong).
-
Xin phép anh/chị
hôm nay chúng ta nhàn đàm về mô hình lập trình phân tán không đồng bộ MapReduce.
Đối với anh/chị lâu năm trong nghề thì mô hình này đã trở thành “kinh điển”,
không có gì mới để đàm luận. Riêng cá nhân tôi, khi đọc lại bài
báo (đăng năm 2004) của
Jeffrey Dean và Sanjay Ghemawat,
tôi vẫn cảm nhận được tính đột phá của ý tưởng. Hơn nữa, ý tưởng này lại được
trình bày đơn giản, dễ hiểu đến mức bất ngờ thú vị. Vì vậy, dành thời gian khoảng
5-7 phút để vừa nhâm nhi cà phê vừa “ôn lại” ý tưởng làm nền cho Big Data
cất cánh thì có lẽ cũng “đáng lắm”. 😊
⦀
ⓐ BigFiles, Clusters.
Trước khi bàn đến
MapReduce, mời anh/chị tham khảo lại
ý tưởng BigFiles do Larry
Page và Sergey
Brin, hai đồng sáng lập
viên công ty Google, đề xuất. BigFiles
còn có một tên khác là GFS, viết tắt của cụm từ Google File System. Ý tưởng
rất đơn giản. Nếu mỗi một máy tính có một hệ thống file thì một cụm máy tính (cluster)
cũng có một hệ thống file của nó. Đấy chính là hệ thống tổng hợp của toàn bộ
các file trên các máy tính đơn lẻ của cụm gộp lại. Mỗi một file là tổ hợp của
nhiều đoạn (Chunk) 64MB hợp thành. Mỗi một Chunk có một ID riêng, ID là một dãy 64 bit. Một file có thể gồm
nhiều đoạn nằm rải rác ở nhiều máy trong cụm. GFS có cấu trúc phân cấp và có cơ
chế nhân bản (replicate) nhằm đảm bảo mức độ an toàn của nội dung lưu. Mức
replicate mặc định bằng 3 (có thể cấu hình thay bằng một mức khác). Tức
là nội dung trên đĩa luôn luôn có 3 bản sao nằm ở 3 vị trí khác nhau. Xác suất
để nội dung ở 3 vị trí này cùng đồng thời bị hỏng là cực nhỏ.
Cụm máy tính của
Google có 2 loại máy là Master server (gọi là nút Master) và Chunk
server (gọi là nút lưu). Nút Master không lưu file, chỉ làm nhiệm vụ quản
lý: bảng ánh xạ (mapping) các ID đến các nút lưu.
Một tiến trình
(process) muốn truy cập file, trước hết cần nút Master cấp phép. Sau khi được cấp phép, tiến trình đó được phép
liên lạc với nút lưu trong một khoảng thời gian nhất định. Việc thay đổi nội
dung của một Chunk nào đó được thực hiện giống như một giao dịch trong
các phép toán của cơ sở dữ liệu: giao dịch nguyên tử (atomic transaction)
ACID (Atomicity, Consistency, Isolation, Durability). Nghĩa là dữ liệu của
GFS luôn luôn được đảm bảo tính toàn vẹn (integrity).
Do có replication
(cơ chế nhân bản tự động) nên GFS có mức độ an toàn dữ liệu rất cao, mặc dù các
máy Chunk server (nút lưu) có thể chỉ
là các loại máy thông thường, giá rẻ.
⦀
ⓑ Ý tưởng MapReduce.
Để hiểu bối cảnh
ra đời của MapReduce, chúng ta quay trở lại thời gian các năm xung quanh
năm 2000 (1998-2002), lúc mà Google chỉ mới là công ty Startup trong lĩnh vực
tìm kiếm trên mạng Internet (Web Search). Mỗi một ngày, sau khi đi lục
tìm trên Internet các trang web (web crawling), kho dữ liệu của Google lớn
lên từng giờ mà kết quả tìm kiếm phải đảm bảo thời gian chỉ trên dưới 0.5 giây
cho mỗi yêu cầu của lệnh tìm kiếm. Không một máy tính đơn lẻ nào đủ mạnh để thực
hiện việc này, vì dữ liệu tích tụ càng ngày càng nhiều. Cần phải có một cơ chế
tính toán song song hoặc xử lý phân tán nào đó trên nhiều máy (cụm máy) để giải
bài toán nan giải này. Đó là bối cảnh ra đời của MapReduce: phân tán xử
lý cùng một công việc nhưng được chia ra cho nhiều máy. Cũng cần nói thêm là ở Google,
họ đã xử lý phân tán trước MapReduce rồi nhưng các phần mềm đó “tự chịu
trách nhiệm” xử lý phân tán, chưa sử dụng chung một khung mô hình.
-
Lấy một ví dụ, giả
thiết cụm máy tính của Google có 1,000 máy, hệ thống file được tổ chức theo mô
hình GFS (xem ở mục trước). Giả thiết rằng hệ thống có hàng triệu tài liệu nằm
rải rác trên 1,000 máy này. Một bài toán đơn giản như tính số lần xuất hiện của
các từ (word) trong hàng triệu tài liệu đó đòi hỏi phần mềm phải quét hết
tất cả các file trên hệ thống. Cách mà MapReduce tiếp cận là chia công
việc này cho tất cả 1,000 máy “cùng thực hiện”. Mỗi máy chủ yếu chỉ “quét” các
file lưu trên đĩa cứng của máy đó hoặc các máy “bên cạnh”. Bằng cách này, các
máy tiết kiệm thời gian truyền tin từ máy này sang máy khác và vì các máy song
hành nên thời gian xử lý = max (thời gian xử lý của từng máy trong 1,000 máy).
Chúng ta dễ dàng nhận ra rằng thời gian xử lý này ngắn hơn nhiều so với tổng thời
gian xử lý của 1,000 máy.
⚠ Bất đẳng
thức: max (x1, x2, …, xn) ≤ x1 + x2
+ … + xn, trong đó xi > 0.
-
➡ Mô
hình MapReduce chia việc xử lý tính toán thành 2 hàm: Map và Reduce.
·
Map (k1, v1) ⟶ list (k2,
v2)
·
Reduce (k2, list(v2)) ⟶ list (v2)
-
Quy ước ký hiệu:
k: key (khóa); v: value (giá trị); các từ viết tắt k1, v1, k2, v2: là ký hiệu loại
dữ liệu (type).
-
Mã lệnh của hai
hàm Map và Reduce do người dùng viết. Điều đó có nghĩa là người
dùng chỉ định công việc cho Map và cho Reduce thực thi.
Chú ý là đầu ra
của Map, list (k2, v2), được sắp xếp theo khóa k2;
sau đó trở thành đầu vào của Reduce: (k2,
list(v2)).
⚠ Chúng
ta chú ý thêm đặc điểm của hàm Reduce. Hàm Reduce thông thường chỉ
làm phép toán tổng hợp. Thế nào là một phép toán tổng hợp? Là một phép
toán trên toàn bộ các bản ghi. Ví dụ: đếm số bản ghi, tổng của N con số,
đếm số lần xuất hiện của một từ nào đó trong N bản ghi, …
-
❓ Thế
vai trò của hệ thống là gì? Vai trò của hệ thống là phân chia công việc của Map
cho M Worker và công việc của Reduce cho R Worker. Worker
là chương trình chạy trên một máy tính. Như vậy, vai trò của hệ thống là chia
việc cho nhiều Worker cùng thực hiện. Công việc phân chia này được hệ thống
“ẩn” đi, người lập trình khỏi phải bận tâm.
-
Ngoài ra, hệ thống trộn đầu ra của hàm Map thành đầu vào cho hàm Reduce
(xem đầu vào và đầu ra của các hàm Map và Reduce).
Ngôn ngữ lập
trình của MapReduce là C++. Việc điều hành phân chia công việc, trộn, sắp
xếp dữ liệu trung chuyển được thực hiện thông qua một thư viện (library).
⚠ Khi
lập trình cho các hàm Map và Reduce, các hàm này nằm trong một lớp
(Class) nào đó do người dùng định nghĩa nhưng lớp này phải thừa kế các lớp
của thư viện MapReduce. Ví dụ: hàm Map nằm trong lớp thừa kế lớp Mapper,
hàm Reduce nằm trong lớp thừa kế lớp Reducer. Anh/chị nào là dân
kỹ thuật lập trình thì nên tham khảo Phụ lục A của bài
báo (cuối bài).
⦀
ⓒ Implementation (cài đặt thực thi).
Bối cảnh để cài
đặt MapReduce là hệ thống máy của
Google vào khoảng năm 2000: cụm máy tính gồm hàng ngàn máy PC (giá rẻ: 4GB RAM,
đĩa cứng 160GB IDE), các máy được nối với nhau bằng các bộ switch Ethernet
tốc độ 100/1000 Gigabit/s. Vì là các máy PC thông thường nên hệ thống cần tính
đến trường hợp máy bị “treo” hoặc đĩa cứng “trục trặc”. File của cụm máy được tổ
chức theo hệ thống GFS (xem mục ⓐ). Các máy
chạy hệ điều hành Linux.
-
Để tránh bị hiểu
nhầm, xin phép anh/chị chúng ta thống nhất dùng từ tiếng Anh. Các tiến trình/chương
trình đang chạy trên các máy trong mạng được gọi là “Worker”. Các công
việc mà Map hay Reduce thực hiện được gọi là “Task” (tác vụ).
-
➡ Nhìn
một cách tổng quan: đầu vào của Map được chia thành M mảnh, việc
xử lý các mảnh này được các Worker thực hiện song song. Tương tự như vậy,
công việc của Reduce cũng được chia thành R vùng, được các Worker
cùng thực hiện song song.
1.
MapReduce đầu tiên chia đầu vào của hàm Map thành M mảnh và đồng thời cho khởi động các Worker trên các máy trạm. (Trong HĐH Linux, lệnh này là fork).
2.
Trong
số này có một Worker đặc biệt, có tên
là Master, điều hành các Worker còn lại. Lúc này, Map có M Task, Reduce có R Task.
3.
Một
Worker tương ứng với Map xử lý đầu vào từ 1 phân mảnh trong tổng
số M phân mảnh. (Thực chất: Worker này gọi hàm đã được người dùng định
nghĩa.) Đầu ra của Map được lưu tạm
thời trong RAM.
4.
Một
cách định kỳ, căn cứ vào giá trị của khóa k2, Worker (của Map) sẽ xác định được vùng tương ứng trong số R vùng và ghi dữ liệu lên đĩa cứng của máy trạm. (Thuật toán “xác định
vùng” thường được dùng là hàm băm modulo R:
hash(k2) Mod R.) Sau đó Worker này báo
cho Master biết vị trí tương ứng của
đĩa cứng. Tiếp theo, Master báo cho Worker của Reduce biết vị trí này.
5.
Khi
một Worker của Reduce biết được vị trí trên, Worker
này sẽ sử dụng hàm RPC (Remote Procedure Call: máy này gọi một hàm trên
máy kia) để đọc dữ liệu về máy của mình. Sau khi đọc xong, Worker của Reduce phải sắp
xếp dữ liệu (Sort) theo khóa k2, nhằm sắp
xếp tất cả các giá trị cùng một khóa theo cùng một danh mục.
6.
Tiếp
theo, Worker của Reduce lập một vòng lặp: lần lượt đọc tất các các khóa k2 và danh mục giá trị tương ứng, gọi hàm Reduce do người dùng định nghĩa. Đầu ra
của hàm Reduce này sẽ được nối thành
một file, tương ứng với một vùng của Reduce.
7.
Sau
khi toàn bộ các Worker của Map và Reduce hoàn thành công việc, Master
sẽ trả lại điều khiển cho chương trình người dùng.
Cuối
cùng, người dùng được cái gì? Đó là R
file (tương ứng với R vùng của Reduce)! Việc sử dụng R file đó như thế nào là việc của người
dùng.
-
Tóm
tắt: {Map} ⟶ [M
x R file trung gian] ⟶
{Trộn} ⟶ {Reduce}
⟶ [R
file kết quả]
-
➡ Thế
Master điều khiển hệ thống như thế
nào?
Master có bảng ghi tình trạng của tất cả các Task, có tất cả 3 trạng thái:
- Idle (chưa bắt đầu),
- In-progress (đang thực thi),
- Completed (đã hoàn thành).
Master đồng thời chịu trách nhiệm trung chuyển
dữ liệu đầu ra của Map thành dữ liệu
đầu vào của Reduce (k2, v2). Để thực thi việc
này, mỗi khi một Task của Map hoàn thành (Completed), Master ghi lại vị trí và chiều dài của R file đã thực hiện. Sau đó Master sẽ báo cho các Worker của Reduce biết để Worker đó
đọc thông tin (bằng RPC - Remote Procedure Call – xem ở trên).
-
➡ Làm
thế nào để Master biết một Worker nào đó “chết”?
Đơn
giản là sử dụng lệnh Ping. Nếu sau một khoảng thời gian mà không thấy Worker phản hồi thì coi như Worker đó “chết”. Lúc đó, các Task tương ứng với Worker này sẽ được ghi là Idle (chưa bắt đầu) và Master sẽ chuyển Task này cho một Worker
khác thực hiện lại từ đầu.
-
➡ Nếu
Master “chết” thì sao?
Cách
của Google rất đơn giản: báo là quy trình MapReduce
đã bị “hỏng” (failed). Người dùng có quyết định gọi lại MapReduce hay không là quyền của người
dùng. Tất nhiên, người ta cấu hình cụm máy tính sao cho xác suất Master hỏng là cực thấp.
Các
tác giả trong bài báo có đề cập là họ có thể thay thế bằng phương pháp checkpoint,
nhưng vào thời điểm đó, họ chọn giải pháp đơn giản và hiệu quả như trên.
<Mở
ngoặc>
❓ Thế
phương pháp checkpoint là gì?
Trước
mỗi lần Master thay đổi bảng trạng
thái, Master ghi giá trị trước đó của
bảng trạng thái ra một bản ghi dự phòng. Trong trường hợp Master “chết” thì người ta có thể khởi động lại từ bảng trạng thái
ngay trước đó bằng một Master dự
phòng thứ cấp (Backup).
Master thứ cấp chạy song song với Master sơ cấp và định kỳ “ping”
Master sơ cấp để kiểm tra xem Master
sơ cấp có bị “chết” hay không. Khi phát hiện thấy Master sơ cấp “chết”, Master
thứ cấp sẽ điều khiển thay thế và điểm khởi đầu cho Master thứ cấp chính
là bảng trạng thái gần nhất mà Master sơ cấp đã ghi ra bản ghi dự phòng ở
trên.
</Đóng
ngoặc>
-
➡ Làm
thế nào để đảm bảo tính toàn vẹn khi có Worker
bị “chết”?
Chúng
ta phân biệt trường hợp Worker thực
hiện một Task của Map và Task của Reduce.
·
Trường
hợp Map: Worker ghi ra R file trên
đĩa cứng cục bộ (local disk) ngay trên máy của Worker. Lưu ý rằng file trên đĩa cứng cục bộ khác file hệ thống GFS.
Hệ thống GFS cấp phép truy cập tổng thể. Bất cứ một máy nào trong cụm đều có thể
truy cập GFS. Ngược lại, trong hệ thống cục bộ (local) máy này không thể
truy cập đĩa cứng cục bộ của máy khác. Nếu Worker
của Map bị “chết” giữa chừng thì một
số hoặc toàn bộ R file trên máy này
không ai truy cập được. Vì vậy, Worker
của Map phải “sống” cho đến hết chu kỳ
của MapReduce. Nếu không (“chết” giữa
chừng), hệ thống bắt buộc phải chuyển Task
này cho một Worker khác làm lại từ đầu.
Như vậy, đầu ra của Map là dạng giao
dịch nguyên tử (atomic commit): hoặc là thành công, dữ liệu có tính toàn
vẹn hoặc phải ghi là “hỏng”.
·
Trường
hợp Reduce: Worker có đầu ra chỉ là một file. Khi Task của Reduce hoàn
thành thì Worker đặt lại tên file: từ
tên cục bộ thành tên tổng thể (GFS). Khi nhiều máy cùng thực hiện một Task thì riêng việc đặt lại tên file này
cũng cần đảm bảo tính nguyên tử (atomic commit).
-
➡ Làm
thế nào để tối ưu hóa thời gian xử lý MapReduce?
Có
3 yếu tố liên quan đến tốc độ xử lý của MapReduce:
thời gian truy cập đĩa cứng, tốc độ mạng, cách phân mảnh M, R và số các máy tính
có trong cụm máy.
·
Tối
ưu hóa Worker và tối ưu hóa truy cập
đĩa cứng. Nếu hệ thống
có cách phân chia các Worker sao cho Worker đó khi truy cập đĩa cứng thì chủ
yếu là truy cập đĩa cứng trên máy cục bộ chứ không truy cập đĩa cứng trên máy
khác. MapReduce tìm cách chia Task của Map cho các Worker sao
cho “mảnh” đầu vào của Map tương ứng
với khối 64MB trên đĩa cứng cục bộ (local disk) của chính máy đó.
·
Tối
ưu hóa việc phân mảnh M, R và số Worker.
Quan hệ giữa M, R và số các Worker nên
như thế nào cho tối ưu? Chúng ta biết rằng các tiến trình (process) có
nhiều truy cập I/O thì mỗi một Worker
cần xử lý đa nhiệm với số Task khá lớn
mới đạt tối ưu. Lý do: khi truy cập I/O thì phép ngắt (Interrupt) trả điều
khiển lại ngay cho tiến trình; tiến trình lúc đó có thời gian để xử lý một Task khác. Nếu số Task quá nhỏ
thì khoảng thời gian “rỗi” dạng này nhiều, vì vậy, không tối ưu.
Mặt khác, việc chọn hàm để ra được con số R
liên quan trực tiếp đến cân bằng tải (load-balancing) của Reduce. Nếu chọn không tối ưu thì dẫn đến
tình trạng một số Task của Reduce làm việc rất nặng trong lúc số
khác lại “nhàn rỗi” không có nhiều việc để làm. Hàm mặc định của họ là hàm băm
modulo R: hash(k2) Mod R.
⚠ Con số tối ưu là con số nào? Con số bài báo đưa ra là: M=200,000; R=5,000; số Worker=2,000.
Nghĩa là, trung bình một Worker có thể
đảm nhận 100 Task của Map và 2.5 Task của Reduce.
-
➡ Thêm
các Task dự phòng thứ cấp (Backup
Tasks).
Theo
bài báo, hệ thống MapReduce hay gặp
phải hiện tượng Worker bị “lạc” (Straggler).
Nghĩa là có Worker mất rất nhiều thời
gian một cách bất thường để thực thi một Task
nào đó vào cuối chu trình. Có một số lý do cho hiện tượng này:
·
Đĩa
cứng sắp bị hỏng. Worker vẫn đọc/ghi
được nhưng thay vì tốc độ 30 MB/s bây giờ chỉ truy cập được với tốc độ 1 MB/s.
·
Xảy
ra tranh chấp giữa các Task được chỉ
định trên cùng một máy: tranh chấp truy cập đĩa cứng, tranh chấp truyền tin qua
mạng, …
Để
giải quyết vấn đề này, vào khoảng thời gian cuối chu trình MapReduce, họ thêm cho mỗi Task
đang thực thi (In-progress) một Task
dự phòng thứ cấp (Backup). Nghĩa là vào thời điểm đó, có 2 Worker cùng thực hiện một Task. Khi một trong 2 Worker (sơ cấp hoặc thứ cấp) thông báo Task này đã thực thi xong (Completed)
thì coi như Task này đã hoàn tất.
Các
tác giả cho biết, bằng kỹ thuật này, họ đã làm cho hệ thống MapReduce giảm thời gian thực thi một
cách đáng kể. (Trong một thử nghiệm, khi họ tắt chức năng Backup, tổng thời gian xử lý của MapReduce đã tăng lên tới 44%.)
⦀
ⓓ Dataflow (dòng chảy dữ liệu).
Để giúp anh/chị
bớt nhức đầu với các chi tiết cài đặt hệ thống như được diễn giải ở phần trước,
một cách tổng quan, tôi sắp xếp lại dòng chảy dữ liệu của mô hình MapReduce như trong liệt kê sau đây.
·
Input
reader (bộ đọc đầu vào):
Thời điểm này hệ thống MapReduce chia
đầu vào thành từng mảnh (‘split’), có độ dài thông thường là 64MB, chỉ định
mảnh cho các hàm Map tương ứng. Bộ đọc
tạo các cặp (k1, v1).
·
Map
function (hàm Map): Hàm này do người dùng định nghĩa
dưới dạng:
Map (k1, v1)
⟶ list (k2,
v2)
·
Partition
function (hàm chia
vùng): Căn cứ vào số vùng R (mặc định
từ hệ thống hoặc do người dùng chỉ định), MapReduce
dùng một hàm để chia vùng căn cứ theo giá trị của khóa k2.
(Thuật toán “xác định vùng” hay được dùng là hàm băm modulo R: hash(k2)
Mod R. Trong kiến trúc của MapReduce, người dùng có thể định nghĩa “hàm
chia vùng”.) Hệ thống MapReduce tổ hợp
(sắp xếp theo khóa k2) đầu ra của Map và chia thành R vùng làm đầu vào cho Reduce.
Vì vậy, hàm chia vùng cần đảm bảo tính cân bằng tải của hệ thống. Nghĩa là R vùng cần được chia tương đối đều,
tránh hiện tượng vùng có rất nhiều dữ liệu, vùng khác lại rất ít.
·
Compare
function (hàm so sánh):
Đây là hàm dùng cho việc sắp xếp dữ liệu khi trộn M mảnh của Map thành R vùng của Reduce.
·
Reduce
function (hàm Reduce): Hàm này do người dùng định
nghĩa dưới dạng:
Reduce (k2, list(v2))
⟶
list (v2)
·
Output
writer (ghi đầu ra):
Đây là thời điểm hệ thống MapReduce
ghi đầu ra lên GFS.
-
Một cách cô đọng
hơn nữa, chúng ta hình dung dòng chảy của MapReduce
là:
Map ⟶
Trộn dữ liệu (sắp xếp) ⟶
Reduce.
Tất cả các công
việc trên được xử lý song song, với tính toàn vẹn của dữ liệu, hệ thống xử lý
có dự phòng, không ngắt.
⦀
ⓔ Performance (Hiệu suất).
➡ Hiệu
suất rõ nhất của mô hình MapReduce là
lập trình. Rất dễ dàng. Người lập trình chỉ việc định nghĩa hàm Map và hàm Reduce.
➡ Việc
mở rộng hệ thống thì thế nào? Cũng rất dễ! Cứ mua bổ sung thêm máy, kết nối vào
cụm (cluster), khai báo các tham số của thư viện MapReduce. Thế là xong.
-
❓ Làm
thế nào để đo được mức độ hiệu suất của hệ thống? Liệu các máy có chạy song
song không? Có máy nào hoạt động quá tải trong lúc các máy khác lại “nhàn rỗi”
không? Có cách nào “ép” hệ thống hoạt động ở mức tối đa để phát hiện ra các “bug”
mà bình thường hệ thống không thể hiện? Đo hiệu suất hệ thống là vấn đề rất thú
vị, đúng không anh/chị!?
-
➡ Để
hỗ trợ người dùng đọc được thông tin trạng thái (status information), Master chạy một http server (một
trang web) kết xuất các loại thông tin như: số Task đã hoàn tất (Completed), số Task đang thực thi (In-progress), lượng đầu vào (Input),
lượng trung chuyển (từ Map sang Reduce), lượng đầu ra (Output), Worker nào bị “chết”, Task nào do Worker bị “chết” thực hiện, …
Bằng
cách quan sát bảng trạng thái này, người dùng có thể dự đoán lúc nào thì chương
trình kết thúc, liệu có cần tăng/giảm nguồn lực để chạy chương trình một cách tối
ưu, …
<Mở
ngoặc>
Đối
với anh/chị đã từng trải nghiệm lập trình hệ thống (đặc biệt trên hệ vi xử lý 8
bit), khi anh/chị thử nghiệm “chạy mù” chương trình, lúc đó mới thấm thía giá
trị bảng quan sát trạng thái như thế nào!
</Đóng
ngoặc>
-
➡ Các
tác giả bài báo cho biết, họ đã làm một thử nghiệm MapReduce với dung lượng 1010 bản ghi 100 byte (~ 1
terabyte) để tìm kiếm chuỗi ký tự (dùng lệnh grep) và sắp xếp (sort)
toàn bộ các bản ghi (trong bản ghi 100 byte: 10 byte đầu tiên được sử dụng làm
khóa). Người ta sử dụng cụm 1,800 máy PC, mỗi máy chạy Inel Xeon 2GHz, RAM: 4GB,
đĩa cứng: 160GB IDE, đường truyền mạng: Ethernet 1 gigabit/s.
·
Chương
trình Grep: Người ta cấu
hình M=15,000 và R=1. Khi tìm kiếm chuỗi ký tự, chủ yếu là Map thực thi còn Reduce
chỉ việc chép lại kết quả. Toàn bộ chương trình chạy mất 150 giây, trong đó Map mất khoảng 80 giây (anh/chị nào quan
tâm thì xem đồ thị trong bài báo). Thời điểm mà hệ thống huy động nguồn lực cao
nhất là 1,764 Worker ở trạng thái thực
thi (trên tổng số 1,800 Worker). Quan sát trạng thái hệ thống, người ta
thấy MapReduce mất khoảng 1 phút (60
giây) để khởi động: đây là quãng thời gian Master
“giao việc” cho các Worker, mở file (file
của Map) và “tối ưu hóa” giữa Worker và đĩa cứng cục bộ (Worker trên máy nào thì truy cập đĩa cứng
trên máy đó).
·
Chương
trình Sort: cấu hình M=15,000; R=4,000. Người ta quan sát thấy Map
mất khoảng 200 giây để đọc dữ liệu. Sau thời điểm Map khởi động khoảng 20 giây thì phần “trộn” (gửi dữ liệu từ Map sang Reduce) bắt đầu. Có sự giao thoa giữa Map và công đoạn “trộn”: một số Task
của Map đọc dữ liệu trong khi một số
khác đã chuyển sang gửi dữ liệu. Tổng thời gian “trộn” là khoảng 600 giây.
Tương tự, cũng có giao thoa giữa công đoạn “trộn” và Reduce. Reduce của Sort
ghi kết quả lên 2 bản sao giống hệt nhau. Đây cũng là lý do vì sao thời gian Reduce của Sort dài hơn thời gian
Reduce của Grep. Tổng thời
gian cho chương trình Sort là 891 giây. So sánh, điểm chuẩn TeraSort (TeraSort
Benchmark) để sắp xếp 1 terabyte vào thời điểm đó là 1,057 giây. (Anh/chị
có thể tham khảo thêm sortbenchmark.org.)
⦀
ⓕ Experience (trải nghiệm MapReduce tại Google).
“Trải nghiệm”
là cụm từ dùng trong bài báo. Trên thực tế, đây là các ứng dụng của mô hình MapReduce vào các công việc trong nội bộ
Google:
·
Ứng
dụng trong Machine Learning (Google khởi động Machine Learning từ
năm 2001)
·
Ứng
dụng trong Google News và Froogle. (Google News: tổng hợp
tin tức từ các báo. Froogle: tìm kiếm các sản phẩm được bán trực tuyến
và so sánh giá các mặt hàng.)
·
Trích
xuất dữ liệu của các truy vấn trực tuyến (online queries)
·
Trích
xuất thuộc tính của các trang Web
·
…
·
Lập
chỉ số toàn bộ nội dung World Wide Web
-
Xin có thêm một
vài bình luận về lập chỉ số toàn bộ nội dung World Wide Web. Google là
công ty cung cấp dịch vụ tìm kiếm World Wide Web nên việc tìm kiếm phải
đảm bảo đủ nhanh để thu hút người dùng. Để tăng tốc độ tìm kiếm, một trong các
thủ thuật cơ bản là phải định kỳ lập chỉ số (indexing) của kho dữ liệu
khổng lồ này. Chương trình Sort (sắp xếp) được sử dụng cho công việc này.
Bao lâu thì họ
lập chỉ số một lần? Một cách chính thức thì Google không cung cấp thông tin này.
Trong bài báo, các tác giả nói là họ chạy chỉ số vào cuối tuần – như vậy có thể
suy ra tần suất lập chỉ số vào thời điểm đó là khoảng 1 tuần / lần. Càng về sau
thì tần suất lập chỉ số càng dày đặc, từ vài ngày đến vài giờ một lần. Khi
Google chuyển từ cấu trúc file GFS sang Colossus thì việc lập chỉ số định kỳ
không còn cần thiết nữa vì trong cấu trúc Colossus, khi họ cập nhật thông tin từ
các trang Web, cấu trúc này tự động lập chỉ số (tham khảo).
-
ⓖ Hadoop, Spark
Được truyền cảm
hứng từ MapReduce, tháng 1/2006, Doug
Cutting và Mike Cafarella khởi động dự án mã nguồn mở Hadoop.
Trang chủ của dự án ở đây. Tôi tin là trên diễn đàn này, rất nhiều anh/chị “thạo”
Hadoop, thậm chí là đã triển khai Hadoop tại cơ quan/doanh nghiệp của mình.
Một cách cô đọng,
chúng ta có thể so sánh Hadoop với MapReduce
như sau:
·
Ngôn
ngữ lập trình: Hadoop sử dụng Java, còn MapReduce
sử dụng C++
·
Hệ
thống file: Hadoop sử dụng HDFS (Hadoop Distributed File System), còn MapReduce sử dụng GFS (Google File
System)
·
Mô
hình lập trình: sử dụng cùng tên là MapReduce!
😊
Xem kỹ, thì
HDFS cũng rất giống GFS!
Có lẽ sự khác
biệt lớn nhất giữa MapReduce và
Hadoop là: Hadoop là open source nên nếu thiên hạ muốn sử dụng thì chỉ cần
đọc tài liệu rồi tải phiên bản mới nhất về mà dùng. Có rất nhiều tên tuổi lớn sử
dụng Hadoop, xin liệt kê một số: Yahoo, Facebook, Adobe, Alibaba, AOL, eBay, LinkedIn,
Powerset/Microsoft, Spotify, Twitter.
-
Năm 2014, dự án
Spark ra đời. Spark rất giống Hadoop, nhưng có một cải tiến rất
đáng kể: đó là thay vì truy cập đĩa (như Hadoop và MapReduce), Spark truy cập RAM, nếu có thể. Ý tưởng là sử dụng
kỹ thuật bộ nhớ chia sẻ: nhiều tiến trình (process) cùng
truy cập một khối bộ nhớ RAM, giống như các tiến trình đó cùng truy cập đĩa cứng
vậy. Ngoài ra, Spark còn thêm một số tính năng khác. Với quy mô dữ liệu nhỏ,
Spark chạy nhanh hơn Hadoop khoảng 100 lần, còn với quy mô dữ liệu lớn, Spark
chạy nhanh hơn Hadoop khoảng 3 lần.
⦀
➕ Đọc thêm.
Khi Google (và
các Tech Giants khác) có hàng trăm Datacenters khổng lồ nằm rải rác nhiều
nơi trên thế giới, hẳn anh/chị đoán là Google phải sử dụng một hệ thống file
tân tiến hơn GFS? Đúng thế, thưa anh/chị, hệ thống file đó có tên là Colossus.
Tuy nhiên, có rất ít tài liệu nói về Colossus. Chỉ mới gần đây, vào ngày
19/04/2021 có một bài báo giới thiệu một cách sơ lược về
Colossus. Thế mới hay, để cạnh tranh, không phải lúc nào cũng mở hết “ruột gan”
ra được. 😊
Và để điều hành
các chương trình chạy trên hàng triệu máy tại các Datacenters thì phải
có một cách điều hành khác chứ? Đúng thế, hệ điều hành đó có tên là Borg. Tôi
tìm thấy 2 bài post nói về Borg. Bài thứ nhất, đăng vào tháng 4/2015: Large-scale cluster management at Google
with Borg. Bài thứ hai,
mới đăng gần đây, vào tháng 7/2020: Borg: the Next Generation. Nếu anh/chị là dân lập trình hệ điều
hành thì tôi đoán là anh/chị đã đọc các bài này rồi. Còn nếu anh/chị chưa đọc
thì tôi nghĩ anh/chị cũng nên lướt qua để cảm nhận các ý tưởng về cách vận hành
các cụm máy tính khổng lồ vào thời điểm hiện nay. Đương nhiên là phải thêm một
vài tách cà phê nữa … 😊
(\_/)
(
•_•)
/
>☕
Không có nhận xét nào:
Đăng nhận xét