1. Lời mở đầu:
{jcomments on}
MapReduce được thiết kế bởi Google như 1 mô hình lập trình xử lý tập dữ liệu lớn song song, thuật toán được phân tán trên 1 cụm. Mặc dù, MapReduce ban đầu là công nghệ độc quyền của Google, nó đã trở thành thuật ngữ tổng quát hóa trong thời gian gần đây.
Hôm nay, TickLab xin phép được giới thiệu về mẫu hình lập trình MapReduce và những ứng dụng của nó.
2. Nội dung:
2.1 Tại sao dùng Map Reduce:
Vào năm 2020, tổng lượng dữ liệu được tạo ra trên toàn thế giới rơi vào khoảng 64 zettabytes (1 zettabyte = 1 000 000 000 000 gibabytes). Và dự kiến vào năm 2025, con số này có thể tăng lên đến 180 zettabytes.
Đề cập một chút đến kiến trúc của hệ thống database tập trung truyền thống nơi mà chỉ có một server đảm nhiệm vai trò lưu trữ và xử lý toàn bộ các dữ liệu. Cách tiếp cận này tỏ ra không hiệu quả khi gặp phải một lượng dữ liệu khổng lồ. Lý do nằm ở hiện tượng nghẽn cổ chai (bottleneck) mà ở đó tốc độ đọc ghi dữ liệu của bộ vi xử lý nhanh hơn rất nhiều so với tốc độ đọc ghi của bộ nhớ chính; và tốc độ đọc ghi của bộ nhớ chính lại nhanh hơn rất nhiều so với tốc độ đọc ghi của bộ nhớ thứ cấp - nơi chứa dữ liệu.
Hình 1: Cơ sở dữ liệu tập trung
Để giải quyết vấn đề trên, người ta đã đề xuất ra kiến trúc mới là phân chia dữ liệu ra thành nhiều phân vùng chứa ở nhiều servers. Điều này giúp băng thông được tăng lên và giảm áp lực tính toán lên bộ vi xử lý. Ngoài ra, với sự xuất hiện của Machine Learning và Deep Learning, nhu cầu tính toán trên tập dữ liệu ngày càng phức tạp và công phu. Việc phân tán dữ liệu và xử lý chúng song song đem lại hiệu suất cao hơn cũng như tiết kiệm chi phí hơn so với việc đầu tư những máy tính lớn (mainframe) hoặc siêu máy tính.
Hình 2: cơ sở dữ liệu phân tán
Việc phân tán dữ liệu có vẻ đã giải quyết được những vấn đề của kiến trúc tập trung truyền thống nhưng lại đưa ra những thách thức mới. Đó là phải phân tán như thế nào và song song hóa như thế nào để đạt được hiệu quả cao và cân bằng tải tốt (load-balancing). Vì vậy vào năm 2004, Google đã giới thiệu một mẫu hình lập trình trừu tượng phục vụ việc xử lý và sinh ra các tập dữ liệu lớn, Map Reduce. Thư viện Map Reduce chỉ là một thư viện trừu tượng, tức không có phần hiện thực (implementation) và cho phép các tổ chức tùy vào mục đích khác nhau mà triển khai các hiện thực khác nhau. Một trong những hiện thực rất nổi tiếng của Map Reduce là Hadoop mà chúng ta sẽ giới thiệu ở những phần sau. Map Reduce cho phép các lập trình viên thể hiện và biểu diễn các tính toán với các tập dữ liệu lớn phân tán một cách đơn giản mà không cần quan tâm chi tiết của các tác vụ:
Song song hóa (parallelization).
Chịu đựng lỗi (fault-tolerance).
Phân tán dữ liệu (data distribution).
Cân bằng tải (load-balancing).
2.2 Mẫu hình lập trình Map Reduce:
Như chính cái tên đã gợi ý, mẫu hình lập trình Map Reduce bao gồm 2 bước chính là Map và Reduce. Đơn vị tính toán cơ bản của Map Reduce là một cặp <key, value>. Ta có thể biểu diễn ý tưởng của mẫu hình này thông qua bảng sau:
|
Function |
Input |
Output |
|
Map |
(k1, v1) |
list (k2, v2) |
|
Reduce |
(k2, list(v2)) |
(k3, v3) |
Ban đầu, Mapper ở mỗi nút (node) trong hệ thống phân tán sẽ lần lượt lấy mỗi cặp (k1, v1) ở đầu vào và sinh ra một hoặc nhiều cặp (k2, v2) ở đầu ra, các cặp này được gọi là các cặp giá trị trung gian (intermediate values). Các giá trị trung gian có cùng khóa k2 sau khi được sinh ra sẽ được tập trung lại một nút làm đầu vào cho Reducer ở nút đó. Vì vậy đầu vào của hàm Reduce có dạng (k2, list(v2)). Và cuối cùng, Reducer sẽ sinh ra kết quả cuối cùng thông qua mỗi cặp đầu vào (k2, list(v2)) này.
Để minh họa một cách trực quan, ta cùng xem qua bài toán đếm số lượng từ xuất hiện trong tập hợp các tài liệu. Lúc này k1 chính là mỗi tệp tài liệu và v1 chính là văn bản trong tài liệu đó. k2 là một từ trong tài liệu và v2 là số lần xuất hiện của từ đó trong tài liệu k1. Và cuối cùng v3 là số lần xuất hiện của từ k3 trong tất cả các tài liệu.
Hình 3: Ví dụ Map Reduce cho bài toán đếm số từ xuất hiện trong tập hợp các tài liệu.
3. Kiến trúc và luồng hoạt động MapReduce:
3.1 Kiến trúc MapReduce:
Toàn bộ quá trình trải qua bốn giai đoạn thực thi là splitting, mapping, shuffling, và reducing. Giả sử ta có dữ liệu đầu vào cho MapReduce như sau:
Welcome to Hadoop Class
Hadoop is good
Hadoop is bad
Hình 4: Kiến trúc MapReduce
Dữ liệu đi qua các giai đoạn sau của MapReduce:
- Input Splits: Đầu vào cho một job trong MapReduce được phân tách thành các phần có kích thước cố định.
- Mapping: Đây là giai đoạn đầu tiên trong khi thực thi MapReduce. Trong giai đoạn này, dữ liệu trong mỗi lần tách được chuyển đến một hàm ánh xạ để tạo ra các giá trị đầu ra. Trong ví dụ này, công việc của giai đoạn ánh xạ là đếm số lần xuất hiện của mỗi từ từ các input splits và cho đầu ra là một danh sách ở dạng <từ, tần số xuất hiện>.
- Shuffling: Giai đoạn này sử dụng đầu ra của giai đoạn Mapping. Nhiệm vụ của nó là hợp nhất các record từ đầu ra của Mapping. Trong ví dụ này, các từ giống nhau được ghép lại với nhau cùng với số lần xuất hiện tương ứng của chúng.
- Reducing: Các giá trị đầu ra từ giai đoạn Shuffling được tổng hợp. Giai đoạn này kết hợp các giá trị từ Shuffling và trả về một giá trị đầu ra duy nhất. Tóm lại, giai đoạn này tổng hợp toàn bộ tập dữ liệu. Trong ví dụ này, giai đoạn này tổng hợp các giá trị từ Shuffling, tính tổng số lần xuất hiện của mỗi từ.
Vậy, MapReduce hoạt động như thế nào?
Hadoop chia job thành các task. Có 2 loại task đó là:
1. Map task (Splits và Mapping)
2. Reduce task (Shuffling và Reducing)
Quá trình thực thi hoàn chỉnh (thực hiện các task Map và Reduce) được kiểm soát bởi hai thực thể đó là:
1. Jobtracker: hoạt động như quá trình chủ (master) , chịu trách nhiệm hoàn thành việc thực thi các job
2. Nhiều Tasktracker: hoạt động như quá trình tớ (slave), mỗi tasktracker sẽ thực hiện job.
Hình 5: Kiến trúc MapReduce trong Hadoop và luồng thực thi của MapReduce job trong HDFS
Trong đó, một cụm dữ liệu(cluster) được chia ra thành nhiều nhóm dữ liệu nhỏ (data node). Đầu tiên, Client Program sẽ gửi MapReduce job cho jobtracker, jobtracker chịu trách nhiệm quản lý vòng đời của các job và định thời các tasktracker, jobtracker làm những nhiệm vụ sau:
- Khởi tạo các job, cung cấp trạng thái của job cho client và tasktracker, hoàn thành job
- Định thời các hàm map và reduce task trên một cluster.
Tasktracker: một job được jobtracker chia ra thành các task nhỏ, cụ thể là các map task và reduce task. Tasktracker chạy trên một cụm dữ liệu (cluster), có những tiến trình con, các tiến trình con này đăng ký job với jobtracker, và thực hiện các task được chỉ định. Các tiến trình con chạy tách biệt với nhau, trên các nhóm dữ liệu (node) riêng biệt. Nhiệm vụ của tasktracker:
- Tạo các tiến trình con để thực hiện các task, theo dõi tiến độ thực thi, gửi trạng thái của các tiến trình con cho jobtracker.
- Khi một task gặp lỗi thì có thể hủy tiến trình con theo chỉ định của jobtracker.
- Cung cấp một số service (shuffle data).
3.2 Luồng hoạt động các job của MapReduce:
Trong việc hoàn thành các MapReduce job, các thuộc tính chính đó là: lớp inputformat, lớp mapper, lớp reducer, và lớp outputformat.
- Lớp inputformat: lớp này đọc dữ liệu từ đĩa và chuyển đổi nó thành các cặp key-value cho hàm map.
- Lớp mapper: lớp này bao gồm hàm map sẽ xác định các cặp key-value từ input format và trả kết quả cho hàm reduce.
- Lớp reducer: lớp này nhận vào các cặp key-value từ lớp mapper và trả về chúng
- Lớp outputformat: lớp này nhận đầu vào là các cặp key-value từ reducer và ghi output vào đĩa.
Mô tả luồng hoạt động các job của MapReduce:
- Đầu tiên là gửi job (job submission), client gửi job đến jobtracker, gói job bao gồm các file thực thi, và các thành phần khác cần thiết để thực hiện job, các input cho job.
- Tiếp theo là khởi tạo job (job initialization), jobtracker chấp nhận job và đặt nó vào hàng đợi job queue. Dựa trên các đầu vào, nó tạo ra các map task cho mỗi đầu vào. Một số reduce task được tạo thành dựa trên việc cấu thành các job.
- Sau đó là gán task (task assignment), bộ định thời của jobtracker giao các task cho tasktracker từ một trong những job đang chạy. Trong Hadoop v1, tasktracker có một số vị trí cố định cho các map task và các reduce task. Bộ định thời sẽ nhận các thông tin về vị trí của các file đầu vào khi định thời các task trên cluster.
- Thứ tư là thực thi task (task execution), mỗi khi một task được định thời trên một vị trí, tasktracker quản lý việc thực hiện các task như sau: nó cung cấp tất cả các task cấu phần cho task process, sau đó khởi chạy máy ảo Java, giám sát tiến trình và phối hợp với jobtracker để thực hiện các hoạt động quản lý như dọn dẹp trên task exit, hay diệt các task thất bại trong quá trình thực thi.
- Cuối cùng là hoàn thành job (job completion), mỗi khi task cuối cùng trong job được hoàn thành, jobtracker sẽ chạy các task dọn dẹp job (được sử dụng để dọn dẹp các file trung gian trong cả HDFS và các hệ thống file cục bộ của tasktracker).
4. Ứng dụng thực tiễn:
Mô hình MapReduce được sử dụng trong nhiều dạng tính toán dữ liệu chuyên sâu nhờ vào khả năng tính toán song các khối dữ liệu lớn. Trong mục này, bài viết sẽ giới thiệu một số ứng dụng liên quan.
4.1 Xử lý truy vấn mẫu không gian địa lý (Geospatial Query Processing):
Với sự tiến bộ về công nghệ định vị, MapReduce giúp tìm kiếm đường đi ngắn nhất trên Google Map với vị trí cho trước.
Hình 6: MapReduce in Finding Shortest Path
Các hàm Map tìm tất cả đường đi từ điểm bắt đầu tới đích với giá trị khoảng cách tương ứng. Sau khi dữ liệu trung gian được sắp xếp theo khoá, hàm Reduce nhận đường có độ dài ngắn nhất .
4.2 Sắp xếp phân tán (Distributed Sort):
Sắp xếp phân tán được sử dụng để sắp xếp dữ liệu được phân chia trên nhiều miền khác nhau.
Trong việc triển khai MapReduce, dữ liệu input khởi tạo được đưa vào hàm Map để chuyển thành dữ liệu trung gian và lưu trên bộ nhớ đệm của đĩa cục bộ. Bước tiếp theo, dữ liệu trung gian được đưa vào các hàm Reduce phù hợp. Các hàm Reduce sẽ sắp xếp dữ liệu theo khóa được cung cấp và xuất output.
4.3 Phân cụm dữ liệu (Data Clustering):
Phân cụm dữ liệu là một lĩnh vực hấp dẫn đối với các nhà nghiên cứu trong lĩnh vực xử lý ảnh, khai thác dữ liệu và trích xuất thông tin. Phân cụm dữ liệu được sử dụng để giảm thiểu độ phức tạp tính toán trên một bộ dữ liệu lớn, bằng cách chia nhỏ bộ dữ liệu thành các tập dữ liệu con dựa trên các tiêu chí cụ thể.
Tác giả của bài báo [20] đã sử dụng thuật toán phân cụm song song K-means với MapReduce. Đặc trưng chính của thuật toán này là kết hợp một phần các giá trị trung gian của hàm Map với cùng một khoá.
4.4 Chỉ mục đảo ngược (Inverted Index):
Inverted Index là kĩ thuật thay vì index theo đơn vị row(document) giống như mysql thì chúng ta sẽ tiến hành index theo đơn vị term. Cụ thể hơn, Inverted Index là một cấu trúc dữ liệu, nhằm mục đích map giữa term, và các document chứa term đó. Inverted index được sử dụng trong truy xuất dữ liệu trong hệ thống CSDL lớn.
Ta xét một ví dụ sau: Có 3 document là A,B và C
- A = “This is the first document”
- B = “The second document”
- C = “First second”
Inverted index của 3 string A, B, C như sau:
- “this” -> { A }
- “is” -> { A }
- “the” -> { A, B }
- “first” -> { A, C }
- “document” -> { A, B }
- “second” -> { B, C }
Với mô hình MapReduce, hàm Map phân tích các document và đưa ra output gồm danh sách cặp các từ khoá và ID của document chứa từ khóa đó. Hàm Reduce nhận các từ khoá và tổng hợp danh sách ID của các document liên quan tới từ khóa đó.
5. Tổng kết:
|
Ưu điểm |
Khuyết điểm |
|
Đơn giản. Nó có thể xử lý nhanh chóng cho ra kết quả dễ dàng chỉ trong khoảng thời gian ngắn. |
Hiệu quả thấp về các phương diện
|
|
Linh hoạt |
Thao tác phức tạp |
|
Có khả năng mở rộng tốt (tăng giảm tốc độ có thể dựa vào thay đổi thiết kế Mapreduce và hoạt động tốt như nhau ở dữ liệu ít và nhiều) |
|
|
Độ chịu lỗi tốt |
Chỉ có Mappers tận dụng được Hadoop Distributed File System |
|
MapReduce có khả năng thực hiện trên nhiều nguồn ngôn ngữ lập trình khác nhau như: Java, C/ C++, Python, Perl, Ruby,… tương ứng với nó là những thư viện hỗ trợ |
MapReduce sử dụng dữ liệu được bản địa hóa, vì vậy việc chuẩn hóa dữ liệu không thể xảy ra vì điều này sẽ buộc chương trình phải tìm kiếm dữ liệu quan trọng ở nơi khác nhiều lần. Điều này cũng có nghĩa là tính toàn vẹn của dữ liệu không cao và dữ liệu dễ bị lỗi hơn. |
|
Hoạt động tốt trên dữ liệu không có cấu trúc hoặc bán cấu trúc vì nó được thiết kế để diễn giải dữ liệu tại thời điểm xử lý. |
Không có nhiều ý nghĩa trong dữ liệu có cấu trúc. |
6. THAM KHẢO:
[1] Al-Khasawneh M.A, Shamsuddin S.M, Hasan S. & Adamu A.B. (2018). MapReduce A Comprehensive Review, pp.2-3.
[2] David Taylor (2021). What is MapReduce in Hadoop? Architecture / Example, www.guru99.com/introduction-to-mapreduce.html
[3] R. Elmasri and S.B. Navathe (2017) Fundamentals of Database Systems, 7th Ed., Pearson Addison-Wesley
[4] Shafali Agarwal, Zeba Khanam (2015). MapReduce: A Survey Paper on Recent Expansion, pp.2-3.
[5] Seema Maitreya*,C.K. Jhab (2015) MapReduce: Simplified Data Analysis of Big Data.
[6] Tutorialspoint (October 18, 2021), MapReduce - Introduction (n.d.) https://www.tutorialspoint.com/map_reduce/map_reduce_introduction.html
[7] W. Zhao, H. Ma & Q. He (2009) Parallel K-means clustering based on mapreduce, cloudcom, LNCS 5931, pp 674-679 © springer-verlag Berlin Heidelberg