LeVanLoi'log, ⌚ 2021-12-01
***

☕ Nhàn đàm ICT: MapReduce ⦀

Tác giả: Lê Văn Lợi

Bài đã đăng trên diễn đàn ICT_VN (ict_vn@googlegroups.com).
Ngày đăng: 01-12-2021.
-
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 (x₁, x₂, …, x_n) ≤ x₁ + x₂ + … + x_n, trong đó x_i > 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.

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).
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.
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.
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.
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.
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.
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.

❓ 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.

➡ 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, …

Đố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!

➡ 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 10¹⁰ 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 … 😊

(_/)
( •_•)
/ >☕

🏷 Distributed computing | Điện toán phân tán
🏷 Google
🏷 Jeff Dean
🏷 Operating system | Hệ điều hành
🏷 Programming model | Mô hình lập trình
🏷 Sanjay Ghemawat

Bài trước ☚

☛ Bài sau