Luận văn Thạc sĩ Khoa học máy tính: Thuật toán đánh chỉ mục ngược với MapReduce và ứng dung trong việc ̣ đánh giá ý kiến của học sinh Hòa Bình trên mạng xã hội

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:77

Thêm vào BST

Báo xấu

16
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn tập trung nghiên cứu vào mô hình MapReduce, cấu trúc và cách thức hoạt động. Từ đó kết hợp với thuật toán đánh chỉ mục và chỉ mục ngược để thực hiện việc tìm kiếm và thống kê kết quả. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Thuật toán đánh chỉ mục ngược với MapReduce và ứng dung trong việc ̣ đánh giá ý kiến của học sinh Hòa Bình trên mạng xã hội

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Lê Đinh Hợp Thuâ ̣t toán đánh chỉ mục ngược với MapReduce và ứng du ̣ng trong việc đánh giá ý kiến của học sinh Hòa Bình trên mạng xã hội Chuyên ngành: Khoa học máy tính Mã số : 60 48 01 01 Người hướng dẫn khoa học: PGS TS Đỗ Trung Tuấn Thái Nguyên, 12 - 2016 i
Lời cam đoan Tôi xin cam đoan: Những kết quả nghiên cứu được trình bày trong luận văn là hoàn toàn trung thực, của tôi, không vi phạm bất cứ điều gì trong luật sở hữu trí tuệ và pháp luật Việt Nam. Nếu sai, tôi hoàn toàn chịu trách nhiệm trước pháp luật. TÁC GIẢ LUẬN VĂN Lê Đinh Hợp ii
Lời cám ơn Tôi xin chân thành cảm ơn Trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên đã tạo điều kiện thuận lợi cho tôi hoàn thành khóa học này. Tôi xin chân thành cảm ơn các Thầy Cô giáo – Các nhà khoa học đã trực tiếp giảng dạy truyền đạt những kiến thức chuyên ngành Khoa học máy tính cho tôi trong những tháng năm học tập tại trường. Đặc biệt tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới PGS TS Đỗ Trung Tuấn đã tận tình hướng dẫn, dìu dắt và chỉ bảo cho tôi những kiến thức về chuyên môn thiết thực và những chỉ dẫn khoa học quý báu để tôi hoàn thành bản luận văn này. Luận văn này còn nhiều thiếu sót, rất mong được các thầy cô giáo trong hội đồng chấm luận văn xem xét, góp ý kiến để luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn! Thái Nguyên, tháng 12 năm 2016 iii
Mục lục Lời cam đoan .........................................................................................................i Lời cám ơn .......................................................................................................... iii Mục lục ................................................................................................................iv Danh sách các từ viết tắt ......................................................................................vi Danh mục các hình vẽ, bảng biểu...................................................................... vii Chương mở đầu ....................................................................................................9 Đặt vấn đề .....................................................................................................9 Đối tượng và phạm vi nghiên cứu .............................................................. 11 Hướng thực hiện đề tài ...............................................................................11 Những nội dung nghiên cứu chính ............................................................. 11 CHƯƠNG 1 MÔ HÌNH MapReduce .................................................................12 1.1. Tổng quan về MapReduce ...........................................................................12 1.1.1. Sự quan trọng của MapReduce .........................................................12 1.1.2. Các ý tưởng của MapReduce ........................................................... 13 1.1.3. Cấu trúc dữ liệu trong MapReduce ..................................................15 1.1.4. Mapper và Reducer ..........................................................................15 1.1.5. Partitioner và Combiner ...................................................................17 1.2. Bộ khung thực thi ........................................................................................19 1.2.1. Lập lịch ............................................................................................. 19 1.2.2. Di chuyển dữ liệu và mã lệnh ........................................................... 19 1.2.3. Đồng bộ hóa .....................................................................................20 1.2.4. Xử lý lỗi ............................................................................................ 20 1.3. Hệ thống file phân tán..................................................................................20 1.3.1. Kiến trúc của HDFS .........................................................................21 1.3.2. Nhiệm vụ của NameNode ................................................................ 21 1.3.3. Nhiệm vụ của DataNode ..................................................................22 1.3.4. Nhiệm vụ của Secondary NameNode ..............................................23 CHƯƠNG 2THUẬT TOÁN XỬ LÝ DỮ LIỆU VĂN BẢN VỚI MapReduce 25 2.1. Thiết kế thuật toán MapReduce cơ bản .......................................................25 iv
2.1.1. Gộp lớn cục bộ .................................................................................26 2.1.2. Bộ hai và bộ ba .................................................................................30 2.1.3. Tính toán tần số tương đối ..................................................................33 2.1.4. Sắp xếp thứ cấp ................................................................................36 2.2 Thuật toán tính chỉ mục ngược để tìm kiếm dữ liệu văn bản .......................36 2.2.1. Dò tìm Web ......................................................................................37 2.2.2 Thuật toán chỉ mục ngược .................................................................39 2.2.3. Cài đặt theo cơ bản ...........................................................................41 2.2.4. Cài đặt thuật toán cải tiến .................................................................43 2.2.5. Nén chỉ mục ......................................................................................45 2.3. Về tìm kiếm .................................................................................................52 CHƯƠNG 3 THỬ NGHIỆM THUẬT TOÁN ĐÁNH GIÁ Ý KIẾN TRÊN MẠNG XÃ HỘI ............................................................................................................56 3.1 Mã nguồn mở Solr ........................................................................................56 3.1.1. Giới thiệu .......................................................................................... 56 3.1.2. Các tính năng chính của Solr: .......................................................... 56 3.2 Mã nguồn mở Nutch .....................................................................................56 3.2.1. Các lý do để tự xây dựng một Search Engine ..................................56 3.2.2. Các tính năng chính của Nutch ........................................................57 3.3. API biểu đồ Facebook .................................................................................58 3.4. Solr trên Hadoop và tìm kiếm thử nghiệm ..................................................60 3.4.1. Sơ đồ .................................................................................................60 3.4.1. Cài đặt cụm máy Hadoop .................................................................62 3.4.2. Cài đặt Nutch tích hợp với Solr ........................................................67 3.4.3. Thu thập dữ liệu ...............................................................................69 3.5. Thực hiện tìm kiếm thử nghiệm trên tập chỉ mục đã thu thập được. ..........72 Kết luận ..............................................................................................................75 v
Danh sách các từ viết tắt CNTT Công nghệ Thông tin HDFS Hadoop Distributed File System URL Uniform Resource Locator HTML HyperText Markup Language LISP LISt Processing ML Markup Language HPC High-Performance Computing NAS Network-Attach Storage SAN Storage Area Network GFS Google File System SPOF Single Point Of Failure SNN Secondary NameNode APW Associated Press Wordstream REST Representational State Transfer PRAM Parallel Random Access Machine BSP Bulk Synchronous Parallel vi
Danh mục các hình vẽ, bảng biểu Hình 1.1. Mô hình chia để trị .............................................................................14 Hình 1.2. Hàm Map và Fold trong Functional Programming ............................ 15 Hình 1.3. Hai pha Map và Reduce của một MapReduce job ............................. 16 Hình 1.4. Mô hình MapReduce đầy đủ các thành phần .....................................19 Hình 1.5. Kiến trúc của HDFS ...........................................................................21 Hình 1.6. Vai trò của NameNode và DataNode trong HDFS ............................ 23 Hình 1.7. Kiến trúc HDFS đầy đủ ......................................................................23 Hình 2.1. Bảo toàn trạng thái trong Hadoop ......................................................26 Hình 2.2. Tiến trình hoạt động của chương trình WordCount ........................... 27 Hình 2.3. Thời gian chạy của thuật toán "pairs" và "stripes" ............................. 32 Hình 2.4. Ví dụ minh họa cặp giá trị ..................................................................35 Hình 2.5. Minh họa đơn giản của một chỉ mục ngược. ......................................40 Hình 2.6: Minh họa đơn giản cơ sở thuật toán lập chỉ mục ngược trong MapReduce với ba mapper và hai reducer ....................................................................43 Hình 2.7. Mười số nguyên dương đầu tiên trong nguyên phân, γ, và mã Golomb (b = 5, 10) ......................................................................................................................49 Hình 2.8. Ma trận Term-document .....................................................................53 Hình 3.1. Sơ đồ hoạt động của Nutch khi sử dụng như một Crawler ................57 Hình 3.2. Sơ đồ đầy đủ của Nutch khi sử dụng như một Search Engine ...........58 Hình 3.3. Facebook ............................................................................................ 58 Hình 3.4. Trao đổi qua API ................................................................................59 Hình 3.5: Mô hình tổng quan của hệ thống khảo sát..........................................60 Hình 3.6: Sơ đồ giai đoạn đánh chỉ mục ............................................................ 61 Hình 3.7: đánh chỉ mục với MapRedece trên Solr .............................................61 Hình 3.8: Giao diện làm việc của Solr ............................................................... 68 Hình 3.9: Giao diện làm việc của Facebook Graph API ....................................69 Hình 3.10: Access Token của một trình Facebook Graph API .......................... 70 vii
Hình 3.11: Thu thập dữ liệu từ trang mạng của trường THPT Hoàng Văn Thụ 70 Hình 3.12:Giao diên theo dõi quá trình làm việc của MapReduce ....................71 Bảng 3.2: Kết quả thu thập dữ liệu ở 2 chế độ ...................................................72 Hình 3.13: Giao diện trang web tìm kiếm trên Solr ...........................................73 Bảng 3.3: Một số kết quả truy vấn theo chủ đề ..................................................73 viii
Chương mở đầu Đặt vấn đề Trong thời đại hiện nay, công nghệ thông tin được ứng dụng tại mọi lĩnh vực trong cuộc sống, với một hệ thống máy tính người ta có thể làm được rất nhiều công việc, tiết kiệm được thời gian, công sức và tiền bạc. Với sự phát triển vượt bậc của Internet hiện nay, lượng thông tin ngày càng nhiều, sự tăng trưởng có thể nói là được tính bằng cấp số nhân, theo một nghiên cứu thì cứ khoảng 5 năm thì lượng tri thức của nhân loại sẽ tăng gấp đôi, với lượng thông tin đồ sộ trên mạng hiện nay thì việc tìm kiếm và khai thác thông tin là một công việc hết sức quan trọng, mang lại nhiều lợi ích về khoa học và kinh tế. Cùng với sự ra đời của Internet, sự xuất hiện và phát triển không ngừng của lĩnh vực thương mại điện tử, các lĩnh vực nghiên cứu xã hội khiến cho việc xúc tiến các hoạt động kinh doanh hoặc nghiên cứu, quảng bá sản phẩm dịch vụ diễn ra trên khắp các kênh thông tin xã hội, đặc biêt là trên Internet. Như chúng ta đã biết ngày nay mọi thông tin đều được đưa lên các trang mạng xã hội dưới dạng các Posts và rất nhiều người dùng để lại các nhận xét (comments) về các thông tin được đưa lên, ta thấy đó chính là một kho thông tin vô cùng hưu ích, nếu ta có thể tìm kiếm và phân loại dữ liệu ấy, chúng ta có thể thu được các kết quả khảo sát cần thiết phục vụ cho các hoạt động nghiên cứu hoặc các hoạt động sản xuất kinh doanh. Kết quả khảo sát ấy có thể là những tỉ lệ như "thích" (like) hay là không có ý kiến gì đối với một vấn đề được đưa ra. Việc tìm kiếm và xử lý và tổng hợp các thông tin hưu ích đó cần phải có một mô hình đáp ứng được nhu cầu về việc có thể làm việc trên một lượng dữ liệu lớn và tốc độ cao. Mô hình MapReduce là một mô hình lập trình giúp các ứng dụng có thể xử lý nhanh hơn một lượng dữ liệu lớn dữ liệu trện các máy phần tán song song, độc lập với nhau từ đó giúp rút ngắn thời gian xử lý toàn bộ dữ liệu. MapReduce có thể chạy trên các phần cứng thông thường (commodity hardware), không đòi hỏi các server chạy MapReduce phải là các máy tính có cấu hình đặc biết mạnh mẽ. Do vậy chi phí triển khai Mapreduce sẽ rẻ hơn. MapReduce làm đơn giản hóa các giải thuật tính toán phân tán. Với MapReduce, bạn chỉ cần cung cấp hai hàm Map và Reduce cùng với một số thành phần xử lý dữ liệu đầu vào. Do vậy, các nhà phát triển ứng dụng phần tán có thể tập trung nhiều hơn cho phần logic của úng dụng, bỏ qua các chi tiết phức 9
tạp của việc phân tán xử lý. Sự ra đời của MapReduce đã mở ra cho các doanh nghiện và các trung tâm nhiên cứu cơ hội xử lý các nguồn dữ liệu đồ sộ với chi phí thấp và thời gian nhanh hơn. Hiện nay, đã có nhiều công ty lớn triển khai sử dụng mô hình MapReduce trong việc kinh doanh và khảo sát. Công ty Amazon sử dụng MapReduce để xử lý các file log trong quá trình mua hàng của khách hàng để dự đoán được xu hướng mua hàng... Facebook có thể xử lý được khối lượng hơn 10 tỷ hình ảnh mà hộ đang lưu trữ để thu thập các thông tin về hình ảnh, và thu thập 15 terabyte dữ liệu mỗi ngày vào một kho dữ liệu quy mô Petabyte để thực hiện việc khảo sát và đánh giá xu hướng người dùng. Việc nghiên cứu về xu hướng, đánh giá khảo sát một vấn đề trên quy mô lớn luôn là 1 vấn đề gặp nhiều khó khăn. Trước đây các nhà khảo sát, đánh giá ý kiến trên các đối tượng nghiên cứu thường sử dụng phương pháp thủ công rất tốn kém và mất rất nhiều thời gian để tổng hợp tin tức, chẳng hạn như muốn khảo sát ý kiến của học sinh đối với một số thay đổi trong chương trình học, người ta không thể lựa chọn hỏi ý kiến của tất cả các học sinh mà chỉ có thể lựa chọn một số địa điểm đặc trưng để thực hiện khảo sát, và đôi khi, kết quả của những khảo sát này không mang được tính khách quan vì tâm lý e ngại của các em học sinh. Và những cuộc khảo sát này, đôi khi phải thực hiện trong vòng một vài năm mới có thể có kết quả tổng hợp. Như vậy là mất rất nhiều công sức, của cải và thời gian. Với việc thực trạng hiện nay hầu hết rất cả các em trong lứa tuổi học sinh, sinh viên đều biết sử dụng và thích tham gia các mạng xã hội trên Internet ( đặc biết là Facebook) thì việc tìm kiếm một từ khóa có tần suất xuất hiện cao sẽ phản ánh được những xu hướng, những ý kiến của người dùng hơn là việc khảo sát thủ công rất nhiều và việc nhận về những kết quả khảo sát ý kiến. Tổng hợp các thông tin trên máy tính với sự hỗ trợ của mô hình MapReduce sẽ giúp chúng ta có thể thực hiện quá trình đánh giá, khảo sát ý kiến hết sức nhanh chóng và mang lại hiệu quả, cũng như tiết kiệm được rất nhiều thời gian và tiền bạc. Với những nhu cầu cấp thiết trên, học viên thực hiện nghiên cứu kỹ thuật chỉ mục ngược (Inverted Indexing) đó là phương pháp thực hiện quét một lần trên văn bản sau đó lập danh sách các thuật ngữ (từ, cụm từ) trong file đó và bao gồm cả những thông tin đi kèm với mỗi thuật ngữ (term) ( vị trí, tần suất, độ quan trọng...). Các thông tin này sẽ được tổ chức theo một cấu trúc dữ liệu riêng và được gọi là chỉ mục. Với phương pháp đánh chỉ mục ngược kết hợp với mô hình MapReduce sẽ giải quyết được những hạn chế trước đây trong phương pháp thông kê, đánh giá ý kiến trên một quy mô lớn, và đó là lý do học viên lựa chọn 10
đề tài "Thuật toán đánh chỉ mục ngược với MapReduce và ứng dụng trong việc đánh giá ý kiến của học sinh Hòa Bình trên mạng xã hội". Đối tượng và phạm vi nghiên cứu Luận văn tập trung nghiên cứu vào mô hình MapReduce, cấu trúc và cách thức hoạt động. Từ đó kết hợp với thuật toán đánh chỉ mục và chỉ mục ngược để thực hiện việc tìm kiếm và thống kê kết quả. Hướng thực hiện đề tài  Nghiên cứu về mô hình MapReduce  Nghiên cứu về thuật toán đánh chỉ mục và chỉ mục ngược  Thực hiện thử nghiệm và cài đặt Những nội dung nghiên cứu chính Luận văn được trình bày trong 3 chương. Các nội dung cơ bản của luận văn được trình bày theo cấu trúc như sau: 1. Chương 1: Tổng quan về MapReduce; Giới thiệu khái niệm về MapReduce, một số các thành phần, mô hình lập trình của MapReduce và hệ thống phân phối tập tin của nó; Trình bày nhu cầu về đánh giá ý kiến trên mạng xã hội và khả năng áp dụng. 2. Chương 2: Thuật toán xử lý dữ liệu văn bản với MapReduce; Trình bày về thiết kế thuật toán MapReduce cơ bản và thuật toán chỉ mục ngược để tìm kiếm văn bản; 3. Chương 3: Thử nghiệm ứng dụng MapReduce và thuật toán đánh chỉ mục ngược để đánh giá ý kiến trên mạng xã hội; Trình bày mô hình hoạt động của ứng dụng đánh giá ý kiến trên mạng xã hội. Các kết quả thử nghiệm của hệ thống tìm kiếm và đánh giá ý kiến trên dữ liệu văn bản có sử dụng MapReduce và thuật toán tính chỉ mục ngược. 11
CHƯƠNG 1 MÔ HÌNH MapReduce 1.1. Tổng quan về MapReduce 1.1.1. Sự quan trọng của MapReduce Về tính thiết thực, MapReduce cung cấp một công cụ rất hiệu quả để giải quyết các bài toán dữ liệu lớn. Ngoài ra, MapReduce còn quan trọng trong cách nó đã thay đổi việc sắp xếp tính toán trên quy mô lớn. Nói một cách công bằng thì MapReduce không phải là mô hình tính toán song song đầu tiên được đưa ra. Mô hình phổ biến nhất trong lý thuyết khoa học máy tính có từ mấy thập kỷ trước là PRAM1 (Parallel Random Access Machine). Trong mô hình này, một lượng lớn các vi xử lý chia sẻ một bộ nhớ lớn không giới hạn, hoạt động đồng thời trên một lượng dữ liệu chia sẻ để tạo ra kết quả. Các mô hình khác như LogP2 và BSP3 (Bulk Synchronous Parallel), tuy nhiên không có mô hình nào có được sự thành công như MapReduce. MapReduce là mức trừu tượng thành công nhất trên các tài nguyên tính toán mở rộng cho đến nay. Tuy nhiên, mức trừu tượng giải quyết sự phức tạp bằng cách che dấu sự chi tiết và đưa ra các hành vi được thiết kế tốt cho ngƣời sử dụng ứng với mức trừu tượng đó. Chính vì thế, mức trừu tượng không thể hoàn hảo, nó làm cho một số công việc dễ hơn, nhưng cũng làm một số công việc khác khó hơn hoặc có khi là không thể thực hiện được. Vấn đề này làm cho việc ứng dụng MapReduce trong một số bài toán cũng có mặt hạn chế. Điều đó có nghĩa MapReduce không phải là mô hình cuối cùng trong lớp mô hình lập trình mới cho phép xử lý tính toán trên quy mô lớn một cách hiệu quả. 1 http://en.wikipedia.org/wiki/Parallel_Random_Access_Machine 2 http://en.wikipedia.org/wiki/LogP_machine 3 http://en.wikipedia.org/wiki/Bulk_Synchronous_Parallel 12
1.1.2. Các ý tưởng của MapReduce Giải quyết các bài toán dữ liệu lớn đòi hỏi cách tiếp cận riêng biệt mà nhiều khi đối lập với mô hình tính toán truyền thống. Dưới đây là các ý tƣởng chính của MapReduce: Scale “out” not “up” (mở rộng chứ không nâng cấp): Để tăng sức mạnh xử lý thay vì nâng cấp bộ vi xử lý cũng như khả năng lưu trữ của máy tính (mua các server có khả năng xử lý cao – high-end server) giải pháp đưa ra là tăng số lượng các server thông dụng (low-end server). Giải pháp này kinh tế hơn nhiều so vì nó chỉ bổ sung một số máy tính và tận dụng được các server sẵn có trong khi giải pháp nâng cấp có thể dẫn đến việc mua sắm mới lại toàn bộ các server. Hơn nữa giá thành của một server chuyên dụng đắt hơn nhiều so với một cụm máy tính thông thường với khả năng xử lý tương đương. Assume failures are common (chấp nhận việc xảy ra lỗi là thường xuyên): Với sự gia tăng về số lượng của các server trong một cluster, lỗi xảy ra là điều bình thường. Do đó các dịch vụ phân tán trên nhiều server phải tính toán đến các lỗi về phần cứng cũng như phần mềm thường xuyên xảy ra. Mô hình lập trình MapReduce có khả năng xử lý các lỗi thông qua một số cơ chế như tự động khởi động lại các task trên cluster node khác nhau. Move processing to the data (đưa xử lý đến dữ liệu): Trong các ứng dụng tính toán hiệu năng cao truyền thống (High – Prefomance Computing - HPC). Thông thường, một siêu máy tính có các nút xử lý (processing node) và các nút lưu trữ (storage node) được kết nối với nhau qua một kết nối tốc độ cao. Nhiều công việc nặng nề về dữ liệu không phải là những đòi hỏi xử lý cao. Do đó việc tách rời việc lưu trữ dữ liệu và tính toán tạo ra sự thắt cổ chai trong mạng. Do đó sẽ hiệu quả hơn nếu chuyển sự thực thi xử lý đến dữ liệu thay vì chuyển dữ liệu đến nơi xử lý chúng. MapReduce sử dụng một kiến trúc trong đó các bộ xử lý và đĩa lưu trữ được đặt cùng với nhau. Trong sự thiết lập như vậy, chúng ta có thể tận dụng lợi thế của dữ liệu cục bộ bằng cách chạy đoạn mã trên bộ xử lý một cách trực tiếp trên khối dữ liệu cần xử lý. Hệ thống tập tin phân tán có nhiệm vụ quản lý dữ liệu mà MapReduce xử lý. Process data sequentially and avoid random access (xử lý dữ liệu tuần tự và tránh truy cập ngẫu nhiên): Trong trường hợp xử lý một lượng lớn dữ liệu, dung lượng bộ nhớ thường không đủ cho toàn bộ dữ liệu xử lý. Do đó dữ liệu phải được lưu trữ trên đĩa. Thời gian cho việc truy cập ngẫu nhiên thường hạn chế bởi sự di chuyển của đầu đọc cũng như tốc độ đĩa do đó làm chậm công việc xử lý. Để tránh hạn chế này, MapReduce được thiết kế để xử lý các 13
khối dữ liệu của một tập dữ liệu lớn. Hide system-level details from the application developer (che giấu mức chi tiết hệ thống đối với nhà phát triển): Để dễ dàng cho các lập trình viên khi viết ứng dụng xử lý phân tán, MapReduce che giấu sự thực thi phức tạp bên dưới. Thay vào đó, MapReduce cung cấp một mô hình lập trình trừu tượng với các interface đơn giản được định nghĩa sẵn. Phương pháp thường được sử dụng để giải quyết các bài toán dữ liệu lớn hiện nay là chia để trị. Ý tưởng là phân mảnh một bài toán lớn thành các bài toán con nhỏ. Các bài toán nhỏ độc lập với nhau để có thể được giải quyết song song bởi các workers khác nhau – workers có thể là các tiến trình trong bộ vi xử lý hoặc các bộ vi xử lý trong trong bộ vi xử lý đa nhân, các bộ xử lý trên một máy, các máy trên một cụm máy tính. Các kết quả trung gian từ các worker cụ thể sẽ được gộp lại để tạo thành kết quả cuối cùng. Hình 1.1. Mô hình chia để trị MapReduce có nguồn gốc từ lập trình hàm (Functional Programming). Ví dụ điển hình như các ngôn ngữ lập trình Lisp và ML. Tính năng chính của lập trình hàm là khái niệm về các hàm bậc cao (higher-order functions), hoặc các hàm chấp nhận tham số của nó là một hàm. Hai hàm bậc cao thường được xây dựng sẵn là Map và Fold. Như hình dưới, cho một danh sách, Map lấy tham số là một hàm f (có 1 tham số) và áp dụng cho toàn bộ phần tử trong danh sách. Cho một danh sách, Fold lấy tham số là một hàm g (có 2 tham số) và một giá trị khởi tạo: g đầu tiên được áp dụng cho giá trị khởi tạo và phần tử đầu tiên trong danh sách, kết quả 14
được lưu trong biến trung gian, tiếp tục dùng biến trung gian này để phần tử thứ 2 trong danh sách để làm tham số cho hàm g, công việc tiếp lặp đi lặp lại đến khi hết toàn bộ danh sách. Fold trả về kết quả cuối cùng là giá trị cuối cùng của biến trung gian. Hình 1.2. Hàm Map và Fold trong Functional Programming Hàm Map trong MapReduce tương ứng với hàm Map, hàm Reduce tương ứng với hàm Fold trong lập trình hàm. 1.1.3. Cấu trúc dữ liệu trong MapReduce Các cặp key-value là cấu trúc dữ liệu cơ bản trong MapReduce. Key và value có thể nhận các giá trị có kiểu cơ bản như số nguyên, số thực, chuỗi hay có thể nhận các kiểu giá trị có cấu trúc do người dùng định nghĩa. Một phần quan trọng của giải thuật MapReduce là việc xác định cấu trúc key-value trên các tập dữ liệu cần xử lý. Ví dụ, đối với một tập các trang web, các key có thể là các URL và các value có thể là nội dung của các trang HTML, đối với một đồ thị, key có thể là node id và value có thể là danh sách kề của node đó. Trong một số thuật toán key được sử dụng để phân biệt các bộ dữ liệu (giống như khái niệm khóa trong cơ sở dữ liệu), trong khi ở một số thuật toán, các input key không quan trọng và thường được bỏ qua. 1.1.4. Mapper và Reducer Trong MapReduce, lập trình viên định nghĩa một lớp Mapper và một lớp Reducer với hai hàm cơ bản sau:  map (k1, v1) → [ (k2, v2)]  reduce (k2, [v2]) → [ (k3, v3)] Ký hiệu […] để chỉ một danh sách các giá trị. Đầu vào của một công việc MapReduce (MapReduce job) là dữ liệu được lưu trữ trên hệ thống file phân tán (Distributed File System). Hàm map và reduce lần lượt được cài đặt trong hai lớp 15
Mapper và Reducer. Mapper được áp dụng cho mọi cặp key-value để tạo ra các cặp key-value trung gian. Reducer được áp dụng cho tất cả các giá trị (value) ứng với cùng một key trung gian để tạo các cặp key-value ở đầu ra. Giữa 2 pha map và reduce là một phép xử lý nhóm phân tán các cặp key-value trung gian dựa trên các key. Dữ liệu trung gian được gởi đến mỗi reducer theo thứ tự được sắp xếp bởi các key. Tuy nhiên không có một quan hệ thứ thự nào được thiết lập cho các key giữa các reducer với nhau. Các cặp key-value ở đầu ra của các reducer được ghi vào hệ thống file phân tán (các cặp key-value trung gian được bỏ qua). Đầu ra cuối cùng là r file trên hệ thống file phân tán, trong đó r là số các reducer. Trong phần lớn các trường hợp, việc tổng hợp các đầu ra của các reducer là không cần thiết bởi vì r files thường lại là đầu vào cho một MapReduce job khác. Hình 5 mô tả 2 giai đoạn của một MapReduce job. Hình 1.3. Hai pha Map và Reduce của một MapReduce job Ví dụ minh họa MapReduce: Ứng dụng đếm từ (Word count) trong một tập văn bản.  Input: Tập văn bản  Outut: Danh sách các từ cùng số lần xuất hiện của chúng trong tập văn bản. class Mapper method Map (docId a, doc d) 16
for all term t ϵ doc d do Emit (term t, count 1) class Reducer method Reduce (term t, counts[c1, c2,…]) sum ← 0 for all count c ϵ counts[c1, c2,…] do sum ← sum + c Emit (term t, count sum) Hàm Map duyệt qua từng từ trong tập văn bản ứng với mỗi từ sẽ tạo ra một cặp key-value với key chính là từ vừa gặp và value = 1. Hàm Reduce nhận đầu vào là một từ (term) và và danh sách tần số ci bắt gặp của term đó (các giá trị thực là các số 1), Reduce chỉ đơn giản cộng tất cả các giá trị ci trong danh sách counts. 1.1.5. Partitioner và Combiner Phần trên chúng ta đã làm đơn giản cái nhìn về MapReduce, ngoài hai thành phần Mapper và Reducer, thường thì lập trình viên phải chỉ thêm 2 thành phần phụ nữa: 1.1.5.1. Thành phần Partitioner Nó có nhiệm vụ chia không gian khóa (key) trung gian sau bƣớc Map và gán các cặp key-value trung gian tới các Reduce. Hay nói một cách khác, partitioner chỉ định tác vụ (task) mà cặp key-value trung gian phải được chuyển đến đó. Trong mỗi Reducer, các khóa được xử lý theo thứ tự đã được sắp xếp. Partitioner đơn giản nhất bao gồm việc tính toán giá trị băm của key và sau đó thực hiện phép chia lấy phần dƣ của giá trị này với số lượng reducer. Do đó các partitioner có thể gán một key và danh sách value của nó tới một reducer có số hiệu là giá trị băm vừa tính được. Thông thường hàm băm phải được tính toán sao cho số lượng key gửi đến mỗi reducer xấp xỉ bằng nhau. Tuy nhiên partitioner không chú ý đến giá trị value trong cặp key-value, do đó có thể xảy ra tình trạng phân bố dữ liệu không đồng đều trên các reducer. 1.1.5.2. Thành phần Combiner Thành phần này trong MapReduce đóng vai trò như một thành phần tối ưu giúp giảm tải việc chuyển dữ liệu giữa từ các Mapper đến các Reducer. Có thể 17
xem combiner như là một reducer nhỏ (mini-reducer) đặt tại đầu ra của mapper, trước pha trộn và sắp xếp (shuffle and sort phase) gởi các cặp key-value tới các reducer. Mỗi combiner hoạt động cô lập và do đó nó không truy xuất đến các cặp key-value của các mapper khác. Đầu vào của combiner là các cặp key-value từ đầu ra của mapper và nó xử lý tất cả các cặp key-value có key giống nhau để chuyển thành cặp key-value (cùng định dạng như ở đầu vào của combiner có key không thay đổi nhưng value đã bị biến đổi) ở đầu ra. Tuy nhiên, Reducer và Combiner không thể hoán đổi vai trò cho nhau. 18
Hình 1.4. Mô hình MapReduce đầy đủ các thành phần 1.2. Bộ khung thực thi Một trong những ý tưởng quan trọng nhất trong MapReduce là tách biệt việc xử lý phân tán cái gì (what) ra khỏi việc xử lý phân tán như thế nào (how). Một chương trình MapReduce (Mapreduce Job), bao gồm đoạn mã cho Mapper, Reducer và có thể thêm Partioner và Combiner được đóng gói lại với nhau với các tham số cấu hình (ví dụ vị trí các tập tin đầu vào và nơi lưu trữ đầu ra). Nhà phát triển đưa chương trình lên cho node quản lý tác vụ trong cluster (trong Hadoop gọi là JobTracker) và execution framework xử lý tất cả những thứ khác: xử lý trong suốt các vấn đề của việc thực thi mã lệnh phân tán. Các chức năng chính của Execution framework bao gồm: 1.2.1. Lập lịch Mỗi chương trình MapReduce được chia nhỏ thành các đơn vị nhỏ gọi là tasks. Ví dụ, một map task có thể chịu trách nhiệm xử lý một khối các cặp key-value nào đó (trong Hadoop gọi là input split), tương tự, một reduce task có thể xử lý một phần của không gian khóa. 1.2.2. Di chuyển dữ liệu và mã lệnh Ý tưởng của MapReduce là di chuyển mã lệnh, không phải di chuyển dữ liệu. 19
Tuy nhiên, trong một số trường hợp – để cho việc tính toán có thể thực hiện chúng ta phải đưa dữ liệu đến mã lệnh. Trong MapReduce, việc này phụ thuộc phần lớn vào hệ thống file phân tán. Để có được việc cục bộ dữ liệu, scheduler phải khởi động task tại node có chứa khối dữ liệu cần thiết cho task đó. Nếu không thể được (do đang chạy quá nhiều task), một task mới sẽ được khởi tạo ở node khác và dữ liệu được truyền qua mạng đến node đó để xử lý. 1.2.3. Đồng bộ hóa Việc đồng bộ hóa chỉ đến các cách thức để các tiến trình đang xử lý đồng thời có thể hợp lại (“join up”), ví dụ chia sẻ kết quả trung gian hoặc trao đổi thông tin trạng thái. Trong MapReduce, việc đồng bộ hóa xảy ra giữa pha map và reduce. Các cặp key-value trung gian phải được gộp theo khóa, điều này đạt được bằng một phép toán sắp xếp phân tán lớn trên tất cả các node đã chạy map tasks và tất cả các node sẽ chạy reduce tasks. Dữ liệu trung gian được copy qua mạng, vì thế tiến trình này thường được gọi là “shuffle and sort”. Một chương trình MapReduce với m mapper và r reducer có thể có tới m x r phép toán copy vì mỗi mapper có thể có đầu ra đến tất cả các reducer. 1.2.4. Xử lý lỗi MapReduce framework phải hoàn thành tất cả các tasks trong môi trường xảy ra lỗi thường xuyên. Vì MapReduce được thiết kế dành cho các cụm máy giá rẻ (low-end) nên việc thực thi có thể sẽ dễ xảy ra lỗi, đặc biệt trong các cụm lớn, lỗi đĩa cứng và RAM sẽ xảy ra thường xuyên. MapReduce frame work phải xử lý được các việc này. 1.3. Hệ thống file phân tán Chúng ta đã tập trung nhiều vào việc xử lý dữ liệu lớn. Nhưng một điều không kém phần quan trọng đó là: nếu không có dữ liệu thì chúng ta không có gì để xử lý cả. Trong tính toán hiệu năng cao (HPC – High-Performance Computing) và các kiến trúc cụm truyền thống, việc lưu trữ được xem là một thành phần tách biệt với việc tính toán. Có nhiều cách cài đặt khác nhau, trong đó có Network-Attach Storage (NAS) và Storage Area Network (SAN) là được sử dụng thường xuyên. Tuy nhiên với cách cài đặt nào đi nữa thì chu trình xử lý vẫn không thay đổi: các node tính toán lấy đầu vào từ nơi lưu trữ, nạp dữ liệu vào bộ nhớ, xử lý dữ liệu và ghi kết quả ngược trở lại. Khi kích thước dữ liệu càng tăng lên thì khả năng xử lý cũng phải tăng lên. Nhưng khi khả năng xử lý tăng thì sự liên kết giữa node lưu trữ và node xử lý lại trở thành một trở ngại. Lúc này để có hiệu năng cao thì cần phải có đường truyền mạng tốc độ cao (vd: 10 gigabit Ethernet, InfiniBand). Đây không phải là giải pháp hiệu quả về kinh tế. Một cách khác đó là bỏ qua sự tách biệt giữa lưu trữ và tính toán. Đây chính là ý tưởng của hệ thống file phân tán bên dưới MapReduce. Google File System (GFS) là cài đặt hệ thống file phân tán riêng của Google và Hadoop Distributed File System (HDFS) 20