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 0612068
NGUYỄN TẤN DƯƠNG 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
iii


[Ký tên và ghi rõ họ tên]
iv
NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………

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
vi

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.


16/04–31/04

Tìm hiểu quá trình xây dựng ứng dụng
phân tán theo mô hình MapReduce với
Hadoop.
0612072-0612068

01/05–25/05 Tìm hiểu ứng dụng Seacrh Engine phân
tán với Hadoop
0612072-0612068

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
và đánh giá.
0612072-0612068

19/06– 7/07 Hoàn chỉnh báo cáo. 0612072-0612068

viii
Xác nhận của GVHD Ngày 05 tháng 07 năm 2010

SV Thực hiện




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

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 xiii

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


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
xv

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

1

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

(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ể

độ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ả.

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

Chương 4: Báo cáo kết quả thực nghiệm. Trong chương này nhóm sẽ trình bày các
thực nghiệm và kết quả thực nghiệm. Thêm vào đó là các đánh giá và kết luận về kết
quả này.

dụng phân tán có cường độ dữ liệu lớn một cách miễn phí. Nó cho phép các ứng dụng
có thể làm việc với hàng ngàn node khác nhau và hàng petabyte dữ liệu. Hadoop lấy
được phát triển dựa trên ý tưởng từ các công bố của Google về mô hình MapReduce và
hệ thống file phân tán Google File System (GFS).”
Vậy ta có thể kết luận như sau:
1) Hadoop là một framework cho phép phát triển các ứng dụng phân tán.

1
Phần cứng thông thường: dịch từ thuật ngữ commodity hardware, tức các loại phần cứng thông thường, rẻ
tiền. Các phần cứng này thường có khả năng hỏng hóc cao. Thuật ngữ này dùng để phân biệt với các loại phần
cứng chuyên dụng đắt tiền, khả năng xảy ra lỗi thấp như các supermicrocomputer chẳng hạn.
10

2) Hadoop viết bằng Java. Tuy nhiên, nhờ cơ chế streaming, Hadoop cho phép
phát triển các ứng dụng phân tán bằng cả java lẫn một số ngôn ngữ lập trình khác như
C++, Python, Pearl.
3) Hadoop cung cấp một phương tiện lưu trữ dữ liệu phân tán trên nhiều node, hỗ
trợ tối ưu hoá lưu lượng mạng, đó là HDFS. HDSF che giấu tất cả các thành phần phân
tán, các nhà phát triển ứng dụng phân tán sẽ chỉ nhìn thấy HDFS như một hệ thống file
cục bộ bình thường.
4) Hadoop giúp các nhà phát triển ứng dụng phân tán tập trung tối đa vào phần
logic của ứng dụng, bỏ qua được một số phần chi tiết kỹ thuật phân tán bên dưới (phần
này do Hadoop tự động quản lý).
5) Hadoop là Linux-based. Tức Hadoop chỉ chạy trên môi trường Linux
2
.
2.1.2 Lịch sử Hadoop
Hadoop được tạo ra bởi Dough Cutting, người sáng tạo ra Apache Lucene – bộ thư
viện tạo chỉ mục tìm kiếm trên text được sử dụng rộng rãi. Hadoop bắt nguồn từ Nutch,
một ứng dụng search engine nguồn mở.