Tài liệu Tìm hiểu nền tảng phát triển ứng dụng phân tán với hadoop và áp dụng cho search engine phân tán

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN HỆ THỐNG THÔNG TIN ĐẶNG VŨ ĐÌNH DUY – NGUYỄN TẤN DƯƠNG TÌM HIỂU NỀN TẢNG PHÁT TRIỂN ỨNG DỤNG PHÂN TÁN VỚI HADOOP VÀ ÁP DỤNG CHO SEARCH ENGINE PHÂN TÁN KHÓA LUẬN TỐT NGHIỆP CỬ NHÂN CNTT TPHCM, 2010 i TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN HỆ THỐNG THÔNG TIN ĐẶNG VŨ ĐÌNH DUY NGUYỄN TẤN DƯƠNG 0612068 0612072 TÌM HIỂU NỀN TẢNG PHÁT TRIỂN ỨNG DỤNG PHÂN TÁN VỚI HADOOP VÀ ÁP DỤNG CHO SEARCH ENGINE PHÂN TÁN KHÓA LUẬN TỐT NGHIỆP CỬ NHÂN CNTT GIÁO VIÊN HƯỚNG DẪN TS. HỒ BẢO QUỐC KHÓA 2006 - 2010 ii NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… TpHCM, ngày ….. tháng …… năm …… Giáo viên hướng dẫn [Ký tên và ghi rõ họ tên] iii NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… Khóa luận đáp ứng yêu cầu của Khóa luận cử nhân CNTT. TpHCM, ngày ….. tháng …… năm …… Giáo viên phản biện [Ký tên và ghi rõ họ tên] iv LỜI CẢM ƠN Chúng em xin chân thành cảm ơn Khoa Công Nghệ Thông Tin, trường Đại Học Khoa Học Tự Nhiên, Đại Học Quốc gia Tp. Hồ Chí Minh đã tạo điều kiện thuận lợi cho chúng em thực hiện tốt tài tốt nghiệp. Chúng em xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy Hồ Bảo Quốc. Thầy đã tận tâm hướng dẫn, định hướng và có những nhận xét đúng đắn, kịp thời cho nhóm chúng em trong suốt thời gian thực hiện luận văn này. Chúng em cũng xin cảm ơn sâu sắc thầy Lương Vỹ Minh. Thầy đã tận tình giúp đỡ chúng em trong quá trình triển khai hệ thống. Nhóm cũng xin cảm ơn các thầy cô trong khoa Công Nghê Thông Tin đã tận tình giảng dạy, trang bị cho chúng em những kiến thức nền tảng trong suốt quá trình học tập tại khoa. Bên cạnh đó, không thể không nhắc tới sự yêu thương và chăm sóc của gia đình, sự động viên của bạn bè đã giúp nhóm vượt qua những khó khăn khi thực hiện đề tài này. Mặc dù nhóm đã cố gắng hết sức trong quá trình thực hiện đề tài này nhưng chắc chắc sẽ không tránh khỏi những thiếu sót. Kính mong quý thầy cô và các bạn tận tình góp ý, chỉ bảo. Một lần nữa, nhóm xin cảm ơn và mong nhận được tình cảm chân thành từ tất cả mọi người. TP HCM, tháng 07 năm 2010 Nhóm thực hiện đề tài Nguyễn Tấn Dương – Đặng Vũ Đình Duy v Khoa Công Nghệ Thông Tin Bộ môn Hệ Thống Thông Tin ĐỀ CƯƠNG CHI TIẾT KHÓA LUẬN TỐT NGHIỆP TÊN ĐỀ TÀI: Tìm hiểu nền tảng phát triển ứng dụng phân tán với Hadoop và áp dụng cho các Search Engine phân tán. GIÁO VIÊN HƯỚNG DẪN: TS Hồ Bảo Quốc THỜI GIAN THỰC HIỆN: 01/02/2010 – 01/07/2010 SINH VIÊN THỰC HIỆN:  Nguyễn Tấn Dương 0612072  Đặng Vũ Đình Duy 0612068 LOẠI ĐỀ TÀI: Tìm hiểu công nghệ có ứng dụng minh họa. NỘI DUNG ĐỀ TÀI:  Tìm hiểu nền tảng xây dựng ứng dụng phân tán trên nền tảng Hadoop. o Hệ thống tập tin phân tán HDFS o Framework xây dựng ứng dụng phân tán theo mô hình MapReduce: vi MapReduce Engine.  Tìm hiểu cách phát triển ứng dụng phân tán trên nền tảng Hadoop.  Tìm hiểu ứng dụng Seacrh Engine phân tán Nutch và triển khai thực tế. KẾ HOẠCH THỰC HIỆN Thời gian Yêu cầu Phân công 01/02–10/02 Tìm hiểu tổng quan Hadoop. 0612072-0612068 11/02–20/02 Tìm hiểu mô hình MapReduce và GFS 0612072-0612068 theo công bố của Google. 21/02–18/03 Tìm hiểu hệ thống tập tin phân tán HDFS. 0612072-0612068 19/03– 5/04 0612072-0612068 Tìm hiểu MapReduce Engine 16/04–31/04 Tìm hiểu quá trình xây dựng ứng dụng 0612072-0612068 phân tán theo mô hình MapReduce với Hadoop. 01/05–25/05 Tìm hiểu ứng dụng Seacrh Engine phân 0612072-0612068 tán với Hadoop 26/05– 6/06 Triển khai Nutch lên hệ thống thực tế. 0612072-0612068 07/06– 8/06 Thực hiện các thực nghiệm trên hệ thống 0612072-0612068 và đánh giá. 19/06– 7/07 Hoàn chỉnh báo cáo. 0612072-0612068 vii Xác nhận của GVHD Ngày 05 tháng 07 năm 2010 SV Thực hiện  viii Mục lục Chương 1: Giới thiệu đề tài ........................................................................................ 1 1.1 Giới thiệu ............................................................................................................ 1 1.2 Ngữ cảnh và lý do thực hiện đề tài ...................................................................... 1 1.2.1 Sự bùng phát dữ liệu và bài toán truy tìm dữ liệu ......................................... 1 1.2.2 Search engine và các khó khăn ...................................................................... 3 1.2.3 Sự ra đời của mô hình MapReduce ................................................................ 5 1.2.4 Lý do thực hiện ............................................................................................. 7 1.3 Nội dung luận văn ............................................................................................... 7 Chương 2: Nền tảng tính toán phân tán với Hadoop ................................................... 9 2.1 Giới thiệu Framework Hadoop ............................................................................ 9 2.1.1 Hadoop là gì? ................................................................................................ 9 2.1.2 Lịch sử Hadoop ........................................................................................... 10 2.1.3 Các thành phần của Hadoop ........................................................................ 12 2.1.4 Ứng dụng của Hadoop trong một số công ty: ............................................... 13 2.1.5 Tổng quan của một Hadoop cluster: ............................................................ 14 2.2 Hadoop Distributed File System (HDFS) .......................................................... 17 2.2.1 Giới thiệu .................................................................................................... 17 2.2.2 Tổng quan thiết kế của HDFS ...................................................................... 19 ix 2.2.3 Các tính năng của NameNode ..................................................................... 29 2.2.4 Khả năng chịu lỗi và chẩn đoán lỗi của HDFS ............................................. 34 2.2.5 Các giao diện tương tác............................................................................... 36 2.2.6 Quản trị HDFS ............................................................................................ 37 2.3 MapReduce ....................................................................................................... 39 2.3.1 Giới thiệu mô hình tính toán MapReduce .................................................... 39 2.3.2 Hadoop MapReduce Engine ........................................................................ 42 Chương 3: Nutch - Ứng dụng Search Engine phân tán trên nền tảng Hadoop ........... 62 3.1 Ngữ cảnh ra đời và lịch sử phát triển của Nutch ................................................ 62 3.2 Giới thiệu Nutch ............................................................................................... 63 3.2.1 Nutch là gì? ................................................................................................. 63 3.2.2 Nền tảng phát triển ...................................................................................... 64 3.2.3 Các tính năng của Nutch. ............................................................................. 64 3.3 Kiến trúc ứng dụng Nutch ................................................................................. 66 3.3.1 Thuật giải Nutch .......................................................................................... 66 3.3.2 Cấu trúc dữ liệu của Nutch .......................................................................... 69 3.4 Kiến trúc Nutch................................................................................................. 73 3.4.1 Kiến trúc các thành phần ............................................................................. 73 3.4.2 Plugin-based ................................................................................................ 77 3.5 Nutch và việc áp dụng tính toán phân tán với mô hình MapReduce vào Nutch . 80 3.5.1 Nguyên nhân cần phải phân tán ................................................................... 80 3.5.2 Áp dụng tính toán phân tán cho các thành phần Crawler.............................. 80 x 3.5.3 Áp dụng tính toán phân tán cho Searcher ..................................................... 81 3.5.4 Mô hình ứng dụng Search Engine phân tán hoàn chỉnh ............................... 84 Chương 4: Thực nghiệm và các kết quả .................................................................... 86 4.1 Giới thiệu .......................................................................................................... 86 4.2 Thực nghiệm triển khai crawl và tạo chỉ mục. ................................................... 86 4.2.1 Mục đích ..................................................................................................... 86 4.2.2 Phần cứng.................................................................................................... 87 4.2.3 Phương pháp thực hiện ............................................................................... 87 4.2.4 Kết quả ........................................................................................................ 90 4.2.5 Đánh giá ...................................................................................................... 93 4.2.6 Kết luận....................................................................................................... 93 4.3 Thực nghiệm tìm kiếm trên tập chỉ mục ............................................................ 94 4.3.1 Mẫu dữ liệu: ................................................................................................ 94 4.3.2 Phần cứng.................................................................................................... 94 4.3.3 Phương pháp thực hiện ............................................................................... 94 4.3.4 Bảng kết quả thực hiện các truy vấn ............................................................ 95 4.3.5 Đánh giá: ..................................................................................................... 97 4.3.6 Kết luận....................................................................................................... 97 Chương 5: Tổng kết đề tài ........................................................................................ 98 5.1 Các kết quả đạt được ......................................................................................... 98 5.2 Hướng phát triển ............................................................................................... 98 Tài liệu tham khảo ...................................................................................................... 99 xi Danh sách các phụ lục .............................................................................................. 101 Phụ lục A: Hướng dẫn triển khai một Hadoop cluster. .............................................. 101 Phụ lục B: Bảng các tham số cấu hình Hadoop. ........................................................ 123 Phụ lục C: Các lệnh command line trên Hadoop. ...................................................... 131 Phụ lục D: Phát tiển ứng dụng theo mô hình MapReduce trên Framework Hadoop. . 144 Phụ lục E: Hướng dẫn triển khai hệ thống Search Engine phân tán với Nutch. ......... 154 Phụ lục F: Bảng các tham số cấu hình cho Nutch...................................................... 185 Phụ lục G: Cách lệnh command line điều khiển Nutch. ............................................ 188 xii Danh mục các bảng biểu Bảng 1: Các điều kiện thực nghiệm crawl .................................................................. 89 Bảng 2: Kết quả thống kê đánh giá thực nghiệm crawl ở chế độ standalone và Distributed................................................................................................................. 91 Bảng 3: Kết quả thống kê đánh giá thực nghiệm crawl ở chế độ standalone và Distributed – Trực quan hơn ...................................................................................... 92 Bảng 4: Bảng thực hiện kết quả truy vấn ................................................................... 96 xiii Danh sách các hình ảnh trong đề tài Hình 2-1 Cấu trúc các thành phần của Hadoop .......................................................... 12 Hình 2-2 Tổng quan một Hadoop cluster .................................................................... 15 Hình 2-3 Kiến trúc HDFS ........................................................................................... 21 Hình 2-4 Quá trình đọc file trên HDFS ....................................................................... 23 Hình 2-5 Quá trình tạo và ghi dữ liệu lên file trên HDFS ............................................ 25 Hình 2-6 Cấu trúc topology mạng ............................................................................... 31 Hình 2-7: Mô hình MapReduce của Google ............................................................... 40 Hình 2-8: Hàm map .................................................................................................... 42 Hình 2-9: Hàm reduce ................................................................................................ 42 Hình 2-10: Kiến trúc các thành phần .......................................................................... 44 Hình 2-11: Cơ chế hoạt động của Hadoop MapReduce ............................................... 46 Hình 2-12: Sự liên lạc đầu tiên giữa TaskTracker thực thi Maptask và JobTracker .... 48 Hình 2-13: Cơ chế hoạt động của Map task ................................................................ 49 Hình 2-14: TaskTracker hoàn thành Map task ............................................................ 50 Hình 2-15: Cơ chế hoạt động của Reduce task ........................................................... 51 Hình 2-16: TaskTracker hoàn thành Reduce task ........................................................ 53 Hình 2-17: Data locality ............................................................................................ 55 Hình 2-18: Phát triển ứng dụng MapReduce trên Hadoop ........................................... 57 Hình 3-1 Các bước chính trong thuật toán của Nutch .................................................. 66 Hình 3-2 Vòng lặp crawl ............................................................................................ 67 Hình 3-3 Các thành phần dữ liệu Nutch ...................................................................... 70 Hình 3-4 Tổng quan các thành phần của Nutch........................................................... 73 Hình 3-5 Kiến trúc các thành phần và quá trình thực hiện crawler .............................. 74 Hình 3-6 Các thành phần và quá trình thực hiện index và search ................................ 76 Hình 3-7: Plugin trong Nutch ..................................................................................... 78 Hình 3-8: Quá trình truy vấn chỉ mục bằng MapReduce ............................................. 82 xiv Hình 3-9 Search servers .............................................................................................. 84 Hình 3-10: Mô hình ứng dụng Search Engine phân tán hoàn chỉnh ............................ 85 Hình 4-1: Quy trình crawler........................................................................................ 87 Hình 4-2: Mô hình thực nghiệm phân tán crawler ....................................................... 90 xv Chương 1: Giới thiệu đề tài 1.1 Giới thiệu Tên đề tài luận văn: “Tìm hiều nền tảng phát triển ứng dụng phân tán với Hadoop và áp dụng cho Search Engine phân tán.” Sơ lược: Trong đề tài này, nhóm sẽ thực hiện tìm hiểu kỹ càng nền tảng phát triển các ứng dụng MapReduce trên framework Hadoop để phát triển các ứng dụng phân tán. Sau đó, nhóm sẽ tiến hành triển khai ứng dụng Nutch, là một ứng dụng Search Engine phân tán hoàn chỉnh, để đánh giá được tác dụng của việc ứng dụng MapReduce vào trong các ứng dụng thực tế. 1.2 Ngữ cảnh và lý do thực hiện đề tài 1.2.1 Sự bùng phát dữ liệu và bài toán truy tìm dữ liệu Trong thời đại chúng ta đang sống, ngành công nghệ máy tính phát triển một cách vũ bão. Số lượng người sử dụng máy tính và các tài nguyên trực tuyến để xử lý công việc, giải trí...ngày càng tăng nhanh. Theo ước tính đến nay, đã có 23% dân số Việt Nam sử dụng Internet (nguồn: http://www.thongtincongnghe.com/article/5932 ), số lượng người gia nhập cộng đồng mạng trên thế giới là 1,46 tỷ người (theo Mark Higginson, Giám đốc của hãng phân tích Nielsen Online). Hệ quả tất yếu sự gia tăng lượng người sử dụng là khối lượng dữ liệu số đang phình to ra với tốc độ chóng mặt. Thật không dễ để đo lường được tổng dung lượng dữ liệu số đã được lưu trữ trên thế giới. Tuy nhiên, IDC đã đưa ra ước lượng rằng tổng dung lượng dữ liệu số được lưu trữ năm 2006 khoảng 0.18 zettabytes, và con số đó năm 2011 sẽ là 1.8 zettabytes. Một zettabytes bằng 1012 bytes, bằng nghìn exabytes, bằng một triệu Petabytes và bằng 1 tỷ Terabytes. Có thể hình dung rằng nếu chia đều khối lượng dữ liệu được lưu trữ trong các thiết bị điện tử ra cho tất cả mọi người trên thế giới, thì mỗi người sẽ được một 1 lượng dữ liệu bằng một ổ cứng khoảng vài trăm Gigabytes. Lượng dữ quá lớn đó phần lớn đến từ việc sử dụng các dịch vụ trên mạng, chúng ta hãy khảo sát thử một số hệ thống sau đây.  Thị trường chứng khoán New York phát sinh ra khoảng 1 Terabyte dữ liệu về các giao dịch mỗi ngày.  Facebook đang host khoảng 10 tỷ tấm ảnh, tức khoảng một petabyte.  Trang web Ancestry.com, một trang web cung cấp dịch vụ lưu giữ gia phả (thông tin về gia đình, cây phả hệ), đang lưu trữ khoảng 2,5 petabyte dữ liệu.  Trang web Internet Archive, đang lưu trữ khoảng 2 petabytes dữ liệu, và gia tăng với tốc độ khoảng 20 terabyte/tháng. Khi khối lượng dữ liệu của một hệ thống gia tăng tới một mức độ nhất định (khoảng hàng ngàn Terabyte chẳng hạn), thì việc hệ thống sẽ phải đối mặt với thách thức làm sao để lưu trữ và phân tích dữ liệu. Chúng ta không thể lưu một khối dữ liệu rất lớn lên chỉ duy nhất một đĩa cứng vì hai lý do đơn giản. Thứ nhất, đó là sự giới hạn về khả năng lưu trữ của ổ cứng. Thứ hai, cho dù vượt qua được giới hạn về dung lượng, thì việc truy xuất một khối lượng dữ liệu đồ sộ như vậy một cách tuần tự (vì trên một đĩa đơn) sẽ rất mất thời gian vì giới hạn về tốc độ đọc đĩa. Do vậy, bắt buộc chúng ta phải lưu trữ dữ liệu lên trên nhiều đĩa cứng thay vì chỉ một. Điều này giúp cái thiện tốc độ truy xuất dữ liệu vì ta có thể tiến hành đọc/ghi một cách song song lên các đĩa. Việc lưu trữ dữ liệu phân tán lên nhiều đĩa cứng mang lại lợi thế về khả năng lưu trữ và tốc độ truy xuất dữ liệu. Tuy nhiên, việc duy trì một hệ thống phân tán với nhiều đĩa cứng đã dẫn đến một số vấn đề cần được giải quyết. Đầu tiên, là vấn đề hỏng hóc phần cứng. Do dữ liệu được lưu trên nhiều phần cứng khác nhau, nên khả năng một (hay nhiều) phần cứng xảy ra hỏng hóc cũng tăng lên đáng kể. Một cách giải quyết vấn 2 đề này mà ta có thể thấy ngay, đó là lưu trữ trùng lắp các mẫu dữ liệu lên nhiều đĩa cứng khác nhau. Vấn đề thứ hai là việc phân tích dữ liệu đôi khi cần truy đọc dữ liệu từ nhiều đĩa cứng khác nhau. Tức là dữ liệu được đọc từ một đĩa có thể cần được kết hợp với dữ liệu từ bất kỳ đĩa nào khác trên hệ thống. Các hệ thống phân tán thường cho phép kết hợp dữ liệu từ nhiều nguồn khác nhau, tuy nhiên làm được điều này một cách chính xác là không dễ chút nào. Sự bùng nổ về dữ liệu đã đặt ra cho chúng ta những thách thức, thách thức về việc làm thế nào lưu trữ và xử lý tất cả dữ liệu đó. Tuy nhiên, ở một mặt khác nó lại mang đến các cơ hội, cơ hội chiếm lĩnh một nguồn thông tin khổng lồ nếu chúng ta có đủ khả năng phân tích và xử lý nguồn dữ liệu đó, biến những dữ liệu thô thành những thông tin hữu ích với một mức chi phí hợp lý. 1.2.2 Search engine và các khó khăn Internet chứa hầu như tất cả những thông tin liên quan tới mọi lĩnh vực, mọi ngõ ngách trong cuộc sống. Nhưng nó rất rộng, rộng đến mức gần như không ai có thể kiểm soát được. Diện mạo của Internet lại thay đổi quá nhanh chóng và mạnh mẽ. Hạt nhân của Internet là Word Wide Web, với số lượng lên tới hàng chục tỉ trang, được lưu trữ trong hàng triệu máy chủ đặt khắp nơi trên toàn thế giới. Có thể ví Internet như một biển dữ liệu khổng lồ, với muôn vàn những viên ngọc quí nằm giữa các hạt sạn. Trong đời sống hàng ngày, nhu cầu tìm kiếm thông tin đóng vai trò vô cùng to lớn, và một trong những vấn đề bức thiết nhất của công nghệ hiện nay là làm sao "đãi cát tìm vàng", khai thác nguồn tài nguyên này một cách hợp lí, đem lại lợi ích tốt nhất cho con người. Tìm kiếm thông tin trên mạng Internet quả thật là một thách thức lớn lao. Có tới hàng chục tỉ trang Web tràn ngập trên mạng Internet, và vấn đề là làm sao đưa ra những gì ta muốn thu thập sao cho đồng thời thỏa mãn hai tiêu chí: Chính xác và 3 nhanh chóng. Hơn thế nữa, người dùng cũng không đủ kiên nhẫn để ngồi duyệt qua tất cả các trang web chứa thông tin cần tìm. Trên thực tế, người dùng hiếm khi vào quá mười trang web kết quả, và vì thế, một yêu cầu khó khăn nữa cần giải quyết, đó là: những gì phù hợp nhất phải được đặt lên hàng đầu. Đối với mỗi Search Engine (Google, Yahoo, MSN, v.v…), người dùng truy vấn tìm kiếm (hay nói đơn giản hơn là nhập vào một số từ khóa liên quan đến chủ đề cần tìm), và nhận được một danh sách các trang kết quả (thông thường là những trang web chứa các từ khóa cần tìm kiếm), được sắp xếp theo một tiêu chí nào đó. Qui trình làm việc của một Search Engine có thể được tóm gọn qua ba quá trình: crawling, indexing, và searching.  Crawling là quá trình Search Engine thu thập các trang web để lấy dữ liệu. quá trình này sẽ được thực hiện một cách tự động bởi một Web Crawler. Web Crawler sẽ sử dụng một số URL (uniform resource location) như là các URL hạt nhân để khởi động quá trình, Web Crawler sẽ lần theo các link (các tag anchor “”) để thu thập thêm nhiều trang web. Tất cả phần html của các trang web thu thập được sẽ được lưu trữ lại để sử dụng cho quá trình indexing.  Indexing: dữ liệu các trang web thu thập được sẽ được một chương trình tự động phân tách và tạo chỉ mục ngược (reverse index: chỉ mục với khoá là từ khoá và value là danh sách các tài liệu có mặt từ khoá). Kết quả của quá trình này là một khối chỉ mục ngược.  Searching: khi người dùng nhập một câu query (thông thường là một từ khoá), Search Engine sẽ thực hiện tìm kiếm trên khối chỉ mục để tìm ra những tài liệu phù hợp nhất (khớp nhất) với query. 4 Hiện nay, số lượng trang web có mặt trên Internet đã lên tới hàng tỷ trang. Điều này đã đặt ra cho các nhà phát triển Search Engine một số thử thách lớn:  Thứ nhất, là khối lượng dữ liệu phải lưu trữ là quá lớn. Giả sử mỗi trang web có kích thước trung bình 10 KB, thì với một tỷ trang web, ta cần 10 Terabyte (TB) để lưu trữ. Với toàn bộ khối lượng trang web trên Internet, khối lượng dữ liệu lưu trữ cần tới hàng petabyte (PB), vượt quá khả năng lưu trữ của một đĩa cứng thông thường. Hơn nữa, việc xử lý một khối dữ liệu lên đến hàng PB một cách tuần tự để thực hiện phân tách html và tạo chỉ mục ngược cũng sẽ mất rất nhiều thời gian.  Thứ hai, việc đáp ứng các yêu cầu search trên tập index quá lớn cũng là một vấn đề khó khăn. Một Search Engine thực thụ (như Yahoo! hay Google) mỗi giây phải đáp ứng hàng chục đến hàng trăm yêu cầu tìm kiếm. Và với vai trò là một người dùng, ít ai lại sử dụng một Search Engine phải mất vài giây để xử lý một yêu cầu Search. Vậy thử thách ở đây Search Engine phải thực hiện nhiều yêu cầu tìm kiếm cùng một lúc, trên một khối index lớn, với thời gian đáp ứng có thể chấp nhận được (thường là phải nhỏ hơn một giây). 1.2.3 Sự ra đời của mô hình MapReduce Năm 2004, Google công bố nền tảng MapReduce (thực ra có thể coi MapReduce là một mô hình lập trình, hay một thuật giải). MapReduce là giải pháp được các kỹ sư của Google tìm ra khi họ đang cố gắng mở rộng bộ máy tìm kiếm của mình. Có thể hiểu một cách đơn giản, MapReduce chia việc xử lý thành nhiều khối công việc nhỏ, phân tán khắp các nút tính toán (tiêu biểu là các server thông thường), rồi thu thập các kết quả. Sau khi ra đời, MapReduce nhanh chóng trở thành một đối tượng nghiên cứu và áp dụng của các doanh nghiệp cần xử lý khối lượng dữ liệu lớn với hai lý do sau: 5