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 các Search Engine phân tán.

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
x
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
xi
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
xii
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

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

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
2
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
3
đề 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à
4
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 “<a>”) để 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.
5
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:
6
 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ó khả năng
tính toán, lưu trữ và truy xuất mạnh mẽ. Do vậy, chi phí triển khai MapReduce sẽ rẻ
hơn.
 Thứ hai, MapReduce làm đơn giản hoá 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 tạp của việc phân tán
xử lý.
Trước MapReduce, các doanh nghiệp muốn xử lý hàng petabyte (triệu gigabyte)
dữ liệu để tìm mối quan hệ liên quan đến nghiệp vụ phải rất cân nhắc khi đầu tư cho
việc đầy mạo hiểm này vì chi phí và thời gian cần thiết là trở ngại. Sự ra đời của
MapReduce đã mở ra cho các doanh nghiệp 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. Với việc áp dụng MapReduce, Amazon có thể xử
lý được các file log phát sinh trong quá trình bán hàng trên mạng, phục vụ cho việc dự
đoán xu hướng mua hàng của khách hàng, các sản phẩm đang được mua nhiều
Facebook có thể xử lý được khối lượng hơn 10 tỷ hình ảnh mà họ đang lưu trữ để rút
trích các thông tin về kích thước hình ảnh, phát hiện các hình ảnh xấu.
Cho đến nay, ngoài Google, đã có rất nhiều giải pháp cài đặt bằng nhiều ngôn ngữ
khác nhau MapReduce như Qizmt (C#), Skynet (Ruby) và Greenplum (Python, Perl,
SQL). Vào cuối đầu năm 2005, Dough Cutting đã áp dụng thành công MapReduce vào
ứng dụng Search Engine nguồn mở của mình. Sau đó, nhận ra được các tiềm năng to
lớn của MapReduce, Cutting đã tách MapReduce ra thành một dự án riêng biệt với tên
gọi Apache Hadoop. Cho đến nay, Hadoop đã trở thành giải pháp nguồn mở hàng đầu
hỗ trợ mô hình MapReduce. Hadoop viết bằng Java, tuy nhiên hỗ trợ phát triển
MapReduce trên nhiều ngôn ngữ khác ngoài Java như C++, Pearl, Python.
7
Sự bùng nổ dữ liệu không gì ngăn được là một thực tế. Khi có các giải pháp sử
dụng MapReduce, chúng ta sẽ có thể nhìn thấy ý nghĩa của petabyte. Năm 2009
MapReduce đã được bầu chọn vào vị trí số một trên danh sách Top 10 công nghệ có
ảnh hướng nhất cùng với các công nghệ (nguồn: http://www.thongtincongnghe.com/article/14015 ).
1.2.4 Lý do thực hiện
Qua các vấn đề đã nêu ra ở trên, ta thấy được những ích lợi sẽ có nếu chúng ta
nắm vững được cách thức phát triển mô hình MapReduce cho bài toán xử lý dữ liệu
lớn. Vì vậy nhóm đã quyết định thực hiện đề tài này với mong muốn tạo ra một cơ sở
lý thuyết và các hướng dẫn kỹ thuật để về vấn đề phát triển ứng dụng phân tán theo mô
hình MapReduce trên một framework nguồn mở: Hadoop. Bên cạnh đó, để minh họa
tốt hơn cho đề tài, nhóm đã chọn Nutch, một ứng dụng Search Engine phân tán sử
dụng HDFS và MapReduce của Hadoop, để triển khai thực tế.
1.3 Nội dung luận văn
Luận văn gồm có 5 chương chính:
Chương 1: Giới thiệu. Giới thiệu đề tài thực hiện.
Chương 2: Giới thiệu nền tảng tính toán phân tán với Hadoop. Trong chương này,
nhóm sẽ giới thiệu sơ lược về dự án Hadoop của Apache Software Foundation. Sau đó
là nhóm sẽ đi sâu vào hai phần trọng tâm là HDFS và MapReduce Engine. Giới thiệu
kiến trúc, sức mạnh, và cách phát triển các ứng dụng phân tán trên Hadoop.
Chương 3: Nutch - Ứng dụng Search Engine phân tán trên nền tảng Hadoop.
Trong chương này nhóm sẽ giới thiệu Nutch, một ứng dụng Search Engine phân tán
được phát triển trên nền tảng Hadoop