BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNGĐẠI
ĐẠI HỌC
HỌC BÁCH
BÁCH KHOA
TRƢỜNG
KHOAHÀ
HÀNỘI
NỘI
VIỆN CÔNG
NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
---------------------*-----------------------------------------*---------------------

NGUYỄN THỊ HUYỀN

XỬ LÝ ĐỒ THỊ LỚN TRÊN MÔI TRƢỜNG PHÂN TÁN
SỬ DỤNG MAPREDUCE
ĐỀ TÀI TIỂU LUẬN
AN TOÀN CÁC HỆ THỐNG THÔNG TIN
TÊN ĐỀ TÀI
LUẬN VĂN THẠC SĨ KỸ THUẬT
TẤN CÔNG SQL INJECTION
CÔNG NGHỆ THÔNG TIN
Nhóm thực hiện: 1. Chu Bá Thành
2. Nguyễn VăQuyế

Lớp: Cao học 2011A
NGƢỜI HƢỚNG DẪN KHOA HỌC:
Giảng
viên hƣớng
dẫn:

TS PHẠM
ĐĂNG
HẢI
PGS.TS Nguyễn Liniang

HÀ NỘI - 2016


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce

LỜI CẢM ƠN
Để hoàn thành luận văn tốt nghiệp “Xử lý đồ thị lớn trên môi trường phân tán sử
dụng MapReduce”, lời đầu tiên em xin gửi lời cảm ơn sâu sắc nhất tới TS Phạm
Đăng Hải, ngƣời đã hƣớng dẫn và chỉ bảo em tận tình trong suốt thời gian làm khóa
luận.
Em xin chân thành cảm ơn PGS.TS Huỳnh Quyết Thắng, PGS.TS Nguyễn Đức
Nghĩa, TS Cao Tuấn Dũng đã cung cấp cho em các kiến thức nền tảng về xử lý dữ
liệu trên môi trƣờng phân tán, lý thuyết đồ thị để em thực hiện đề tài này.
Cuối cùng, em xin gửi lời cảm ơn sâu sắc tới các thầy cô, đồng nghiệp và ngƣời
thân trong gia đình đã động viên, khích lệ em trong quá trình thực hiện luận văn.

Học viên
Nguyễn Thị Huyền


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce

LỜI CAM ĐOAN
Với mục đích học tập, nghiên cứu để nâng cao trình độ chuyên môn nên tôi đã
làm luận văn này một cách nghiêm túc và hoàn toàn trung thực.

Trong luận văn, tôi có sử dụng tài liệu tham khảo của một số tác giả, tôi đã nêu
trong phần tài liệu tham khảo ở cuối luận văn.
Tôi xin cam đoan và chịu trách nhiệm về nội dung, sự trung thực trong luận văn
tốt nghiệp Thạc sĩ của mình.
Hà Nội, tháng 04 năm 2016
Học viên

Nguyễn Thị Huyền


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce

MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT ................................................. 1
DANH MỤC CÁC BẢNG.......................................................................................... 2
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ..................................................................... 3
MỞ ĐẦU ..................................................................................................................... 4
1. Lý do chọn đề tài ................................................................................................ 4
2. Mục đích nghiên cứu .......................................................................................... 5
3. Đối tƣợng nghiên cứu ......................................................................................... 6
4. Phạm vi nghiên cứu ............................................................................................ 6
5. Phƣơng pháp nghiên cứu .................................................................................... 6
6. Những luận điểm cơ bản và đóng góp mới của đề tài ........................................ 7
CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ĐỒ THỊ LỚN....................................... 8
1.1. Giới thiệu về đồ thị và đồ thị lớn........................................................................ 8
1.1.1. Định nghĩa đồ thị và đồ thị lớn (Big Graph) .............................................. 9
1.1.2. Đồ thị có trọng số và đƣờng đi ................................................................. 10
1.2. Nghiên cứu về các ứng dụng của bài toán xử lý đồ thị lớn .............................. 11
1.3. Những thách thức trong xử lý đồ thị lớn. ......................................................... 12
1.3.1. Phân tích đồ thị lớn .................................................................................. 12

1.3.2. Thiết kế thuật toán .................................................................................... 13
1.3.3. Nén đồ thị ................................................................................................. 13
1.3.4. Trực quan hóa đồ thị ................................................................................ 14
1.4. Một số kỹ thuật và công cụ xử lý đồ thị lớn ..................................................... 14
CHƢƠNG 2: MÔ HÌNH LẬP TRÌNH MAPREDUCE ....................................... 16
2.1. Tổng quan về Hadoop/MapReduce .................................................................. 16
2.1.1. Hadoop ..................................................................................................... 16
a) Hadoop là gì? ........................................................................................... 16
b)

Kiến trúc của Hadoop............................................................................... 17

2.1.2. MapReduce............................................................................................... 20
2.2. Mô hình kiến trúc của MapReduce .................................................................. 21
2.3. Hàm Map .......................................................................................................... 23
2.4. Hàm Reduce ..................................................................................................... 23
2.5. Vòng đời của MapReduce Job ......................................................................... 23
CHƢƠNG 3: PHÂN TÍCH ĐỒ THỊ LỚN VỚI MAPREDUCE ......................... 28
3.1. Tổng quan về vấn đề phân tích đồ thị .............................................................. 28
3.2. Khai phá đồ thị (Graph Mining) ....................................................................... 28


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce

3.2.1. Các nghiên cứu liên quan đến khai phá đồ thị ......................................... 29
3.2.2. Các thách thức và hƣớng tiếp cận đƣợc đề xuất cho Graph Mining ........ 31
3.3. So khớp đồ thị (Graph Matching) .................................................................... 32
3.3.1. Các nghiên cứu liên quan đến Graph Matching ....................................... 33
3.3.2. Các thách thức và hƣớng tiếp cận đƣợc đề xuất cho Graph Matching .... 35
3.4. Truy vấn đồ thị (Graph Querying) ................................................................... 36

3.4.1. Các nghiên cứu liên quan đến Graph Querying ....................................... 36
3.4.2. Các thách thức và hƣớng tiếp cận đƣợc đề xuất cho Graph Querying .... 37
CHƢƠNG 4: ỨNG DỤNG MAPREDUCE GIẢI QUYẾT BÀI TOÁN TÌM
ĐƢỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ PHÂN TÁN ....................................... 40
4.1. Bài toán tìm đƣờng đi ngắn nhất và thuật toán Dijkstra .................................. 40
4.1.1. Bài toán tìm đƣờng ngắn nhất .................................................................. 40
4.1.2. Thuật toán Dijkstra ................................................................................... 42
4.2. Đồ thị phân tán ................................................................................................. 43
4.3. Đề xuất thuật toán tìm đƣờng đi ngắn nhất trên đồ thị phân tán ...................... 45
4.3.1. Ƣớc lƣợng từng phần ............................................................................... 45
4.3.2. Đề xuất thuật toán .................................................................................... 45
4.3.3. Một vài quan sát và suy luận .................................................................... 47
4.4. Cài đặt bài toán sử dụng MapReduce ............................................................... 53
4.5. Thực nghiệm và đánh giá kết quả..................................................................... 54
4.5.1. Thiết lập môi trƣờng thực nghiệm ........................................................... 54
4.5.2. Kết quả thực nghiệm ................................................................................ 55
KẾT LUẬN ............................................................................................................... 57
1. Kết quả đạt đƣợc của đề tài .............................................................................. 57
2. Hạn chế của đề tài............................................................................................. 58
3. Hƣớng phát triển của đề tài .............................................................................. 58
TÀI LIỆU THAM KHẢO ......................................................................................... 59
PHỤ LỤC .................................................................................................................. 63


DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT
Từ viết tắt

Từ đầy đủ

Giải thích

Một dạng giao thức kết nối của
máy tính. Nó nằm trong chuẩn

MPI

defacto cho kết nối giữa các nút

Message Passing Interface

chạy một chƣơng trình song song
trên bộ nhớ chia sẻ đƣợc phân
phối

SSH

HDFS

Giao thức kết nối mạng có tính

Secure Shell

bảo mật cao

Hadoop Distributed File System

Hệ thống tệp tin phân tán của
Hadoop

MR


Map Reduce

Mô hình lập trình Map Reduce

AI

Artificial Intelligence

Trí tuệ nhân tạo

MDL

Minimum Description Length

DBMS

Database Management System

Nguyên tắc chiều dài mô tả tối
thiểu
Hệ quản trị cơ sở dữ liệu
Ngôn ngữ truy vấn mang tính cấu

SQL

Structured Query Language

TCP

Transmission Control Protocol


Là một giao thức kết nối mạng

Bulk Synchronous

Là một mô hình thiết kế cho các

Parallelization

thuật toán song song

BSP

trúc.

Là một phƣơng thức chung nhất
RDF

Resource Description

cho các mô tả khái niệm hoặc mô

Framework

hình hóa của thông tin đƣợc diễn
dịch trong các tài nguyên web.

1



Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce

DANH MỤC CÁC BẢNG
Bảng 4.1: Dữ liệu trên các đồ thị con và đồ thị liên kết............................................ 45
Bảng 4.2: Minh họa input và output node của đồ thị phân tán ................................. 48
Bảng 4.3: Kết quả thực hiện câu truy vấn Q trên F1. ............................................... 51
Bảng 4.4: Kết quả thực hiện câu truy vấn Q trên F2 ................................................ 52
Bảng 4.5: Kết quả thực hiện câu truy vấn Q trên F3 ................................................ 52

2


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1: Phân loại đồ thị ....................................................................................10
Hình 1.2: Đồ thị có trọng số ................................................................................11
Hình 1.3: Nén đồ thị ............................................................................................13
Hình 2.1: Kiến trúc của một cụm Hadoop ...........................................................18
Hình 2.2: Mô hình kiến trúc của HDFS ..............................................................19
Hình 2.3: Mô hình MapReduce ...........................................................................21
Hình 2.4: Tiến trình xử lý các cặp key-value MapReduce ..................................22
Hình 4.1: Minh họa đồ thị phân tán .....................................................................44
Hình 4.2: Ví dụ đồ thị phân tán có trọng số ........................................................46
Hình 4.3: Đồ thị phụ thuộc Gd đƣợc tạo ra từ kết quả của các Pi ........................52
Hình 4.4: Mô hình MapReduce trong trả lời câu truy vấn trên đồ thị phân tán ..53
Hình 4.5: Thời gian thực thi câu truy vấn với số lƣợng đồ thị con khác nhau ....56

3



Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce

MỞ ĐẦU
1. Lý do chọn đề tài
Cơ sở khoa học: Khái niệm về đồ thị lớn xuất hiện ở khắp mọi nơi từ các mạng
xã hội và các mạng điện thoại di động đến các mạng sinh học và World Wide Web.
Khai thác đồ thị lớn dẫn đến nhiều ứng dụng thú vị bao gồm cả an ninh mạng, phát
hiện gian lận, tìm kiếm Web, hệ gợi ý, và nhiều hơn nữa.
Việc xử lý và phân tích dữ liệu đồ thị lớn dựa trên những nghiên cứu trong
nhiều lĩnh vực bao gồm khoa học máy tính, thống kê, toán học, kỹ thuật dữ liệu,
nhận dạng mẫu, trực quan hóa, trí tuệ nhân tạo, học máy, và tính toán hiệu năng
cao. Vấn đề này cũng đã và đang đƣợc rất nhiều các nhà nghiên cứu khoa học trên
thế giới quan tâm.
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 một lƣợng lớn dữ liệu trên các máy phân tán hoạt động 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ó 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.
MapReduce làm đơn giản hoá các giải thuật tính toán phân tán. Với
MapReduce, ta 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ý.
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 dung
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 v.v… Facebook có thể xử lý đƣợc khối lƣợng

4


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
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.
Cơ sở thực tiễn: Trên thế giới hiện nay dữ liệu đồ thị đang đƣợc tạo ra với tốc
độ chƣa từng có. Hiện tại nó đƣợc đo bằng terabytes và có xu hƣớng đến petabytes,
với hơn tỷ các nút và các cạnh. Ví dụ, Facebook tải 60 terabyte dữ liệu mới mỗi
ngày đƣợc coi là một đồ thị lớn với hơn 1,5 tỷ đỉnh tƣơng ứng với số lƣợng ngƣời
dùng tính đến năm 2015; Yahoo đã có một đồ thị 1,4 tỷ nút Web tại 2002;
Microsoft đã có 1,15 tỷ cặp truy vấn URL vào năm 2009 và Google xử lý 20
petabyte mỗi ngày.
Tại Việt Nam cũng đang ngày càng gia tăng tốc độ phát triển và hội nhập với
các xu hƣớng công nghệ thế giới. Với hơn 30 triệu ngƣời dùng Internet và hơn 15
triệu ngƣời dùng Mobile Internet vào năm 2012, điều này làm cho Việt Nam đang
đứng trƣớc một cơ hội vô cùng lớn về khai thác dữ liệu đồ thị lớn. Sẽ có những
doanh nghiệp Việt Nam khai thác thành công dữ liệu lớn với doanh số hàng trăm
triệu USD trong vòng 5 năm tới. Đặc biệt, giai đoạn 2014-2016, xu hƣớng Mobile
và lƣợng ngƣời dùng Internet 3G sẽ tiếp tục tăng mạnh. Các dịch vụ kết nối OTT
(Over-the-top) và truyền thông xã hội đóng góp hơn 80% phƣơng thức giao tiếp
online, video online và nội dung số mobile. Điều này góp phần đẩy mạnh xu hƣớng
truyền thông số đa phƣơng tiện, đa màn hình (PC, smartphone, tablet, smart TV) sẽ
bùng nổ với độ phủ hơn 50% dân số Việt Nam. Việt Nam là một kho “vàng” dữ liệu
vô cùng lớn cho việc ứng dụng Big Data, Big Graph. Vì vậy việc nghiên cứu để xử
lý dữ liệu đồ thị lớn sao cho hiệu quả là hết sức thiết thực.
Vì những lý do trên mà tôi chọn đề tài “Xử lý đồ thị lớn trên môi trường phân
tán sử dụng MapReduce” làm đề tài luận văn của mình.
2. Mục đích nghiên cứu
 Nghiên cứu đƣợc một số vấn đề trong xử lý đồ thị lớn (Big Graph)

-

Vấn đề liên quan đến truy vấn dữ liệu trên đồ thị lớn.

5


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
-

Vấn đề về công nghệ, công cụ xử lý Big Graph.

 Nghiên cứu về Hadoop/MapReduce
-

Tổng quan về Hadoop/MapReduce

-

Cách thức giải quyết bài toán với MapReduce

 Giải quyết bài toán tìm đƣờng đi ngắn nhất trên đồ thị phân tán sử
dụng Mapreduce.
-

Đề xuất thuật toán tìm đƣờng đi ngắn nhất trên đồ thị phân tán.

-

Cài đặt bài toán sử dụng MapReduce


-

Thực nghiệm và đánh giá kết quả.

3. Đối tƣợng nghiên cứu
 Nghiên cứu tìm hiểu lý thuyết về đồ thị, đồ thị lớn,
 Nghiên cứu tổng quan về Hadoop/MapReduce trong xử lý dữ liệu phân
tán
 Nghiên cứu vấn đề về công nghệ, công cụ xử lý Big Graph. Áp dụng giải
quyết bài toán tìm đƣờng đi ngắn nhất trên đồ thị phân tán.
4. Phạm vi nghiên cứu
 Tổng quan về lý thuyết đồ thị, đồ thị lớn
 Mô hình lập trình MapReduce
 Phân tích đồ thị lớn với MapReduce
 Ứng dụng MapReduce giải quyết bài toán tìm đƣờng đi ngắn nhất trên đồ
thị phân tán.
5. Phƣơng pháp nghiên cứu
 Nghiên cứu tài liệu khoa học về xử lý đồ thị lớn.

6


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
 Nghiên cứu lý thuyết về đồ thị, đồ thị lớn.
 Nghiên cứu về các ứng dụng của việc khai thác và xử lý đồ thị lớn.
 Nghiên cứu về xử lý đồ thị phân tán với MapReduce ứng dụng giải quyết
bài toán tìm đƣờng đi ngắn nhất trên đồ thị phân tán.
6. Những luận điểm cơ bản và đóng góp mới của đề tài
Đề tài đã trình bày đƣợc một cách tiếp cận mới để giải quyết bài toán tìm đƣờng

đi ngắn nhất từ một đỉnh đến một đỉnh khác trên đồ thị phân tán. Đề tài đã đề xuất
một thuật toán dựa trên kỹ thuật ƣớc lƣợng từng phần và khai thác nền tảng hỗ trợ
xử lý dữ liệu song song phân tán MapReduce.

7


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
CHƢƠNG 1:
1.1.

TỔNG QUAN VỀ XỬ LÝ ĐỒ THỊ LỚN

Giới thiệu về đồ thị và đồ thị lớn

Đồ thị dễ dàng tìm thấy ở khắp mọi nơi trong cuộc sống hàng ngày của chúng ta
nhƣ:
-

Hệ thống mạng internet (Co-expression Network)

-

Mạng xã hội (Social network)

-

Quy trình của một chƣơng trình (Program flow)

-


Các hợp chất hóa học ( Chemical compound)

-

Cấu trúc của Protein (Protein structure)

Một dữ liệu lớn ngày nay trên các hệ thống mạng đều có thể biểu diễn dƣới dạng
các đồ thị & mối quan hệ của chúng theo:
-

Liên kết, kết nối vật lý

-

Kết nối giữa các mạng trong lớp mạng

-

Mối quan hệ trong mạng xã hội

-

Siêu lien kết giữa các trang web

-

Các tƣơng tác phức tạp giữa các thực thể…

Những đồ thị trên chứa đựng những thong tin giá trị cho việc ứng dụng vào hệ

thống mạng nhƣ
-

Những phát hiện từ cộng đồng, những điểm chung

-

Phân lớp

-

Những hệ thống đƣợc đƣa ra theo ƣu tiên nào đó

-

Tìm kiếm trên mạng

-

P2P (điểm tới điểm) tìm kiếm & lấy dữ liệu

-

Tin cậy & uy tín…

Nhìn chung, đồ thị có tính bao quát hơn từng đối tƣợng, tuần tự, cây, mạng nói
chung. Đồ thị giải quyết đƣợc nhiều vấn đề có độ tính toán phức tạp cao.

8



Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
1.1.1. Định nghĩa đồ thị và đồ thị lớn (Big Graph)
Định nghĩa 1.1. Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối
các đỉnh đó đƣợc mô tả hình thức: G = (V, E), trong đó V gọi là tập các đỉnh
(vertices) và E gọi là tập các cạnh (edges). Có thể coi E là tập các cặp (u, v) với u
và v là hai đỉnh của V.
Có nhiều loại đồ thị khác nhau biểu diễn cho những đối tƣợng khác nhau và
trong các ứng dụng khác nhau. Ngƣời ta phân loại đồ thị dựa trên đặc điểm của các
cạnh nối [1].
Cho đồ thị G = (V, E). Các định nghĩa một cách hình thức nhƣ sau:
Định nghĩa 1.2. Đồ thị G đƣợc gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V
có nhiều nhất là 1 cạnh trong E nối từ u tới v.
Định nghĩa 1.3. Đồ thị G đƣợc gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có
thể có nhiều hơn 1 cạnh trong E nối từ u tới v.
Định nghĩa 1.4. Đồ thị G đƣợc gọi là đồ thị vô hướng nếu các cạnh trong E là
không định hƣớng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v,
u. Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự. (u, v)

(v, u).

Định nghĩa 1.5. Đồ thị G đƣợc gọi là đồ thị có hướng nếu các cạnh trong E là
có định hƣớng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhƣng chƣa chắc đã có cạnh
nối từ đỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính thứ tự:
(u, v) ≠ (v, u). Trong đồ thị có hƣớng, các cạnh đƣợc gọi là các cung. Đồ thị vô
hƣớng cũng có thể coi là đồ thị có hƣớng nếu nhƣ ta coi cạnh nối hai đỉnh u, v bất
kỳ tƣơng đƣơng với hai cung (u, v) và (v, u).

9



Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce

Hình 1.1: Phân loại đồ thị
Mặc dù chƣa có một khái niệm chính xác về đồ thị lớn (Big Graph) nhƣng
chúng ta có thể khái quát rằng thuật ngữ “đồ thị lớn” chỉ các đồ thị mà dữ liệu của
nó gồm tập các đỉnh và cạnh (có thể gồm cả nhãn của đỉnh hay cạnh) với số lƣợng
lớn lên đến hàng triệu đơn vị (ví dụ mạng xã hội Facebook đƣợc xem nhƣ một đồ
thị lớn với hơn 1.5 tỷ đỉnh tƣơng ứng với số lƣợng ngƣời dùng tính đến 12/2015).
Sự phức tạp trong cấu trúc của đồ thị lớn khiến cho các thuật toán đồ thị truyền
thống không xử lý đƣợc hoặc xử lý với một hiệu năng thấp. Từ đó, đồ thị lớn đặt ra
các thách thức cho việc lƣu trữ, phân tích, trực quan hóa và truy vấn. Bởi vậy, gần
đây nhiều nhà nghiên cứu đã tập trung vào các giải pháp, thuật toán để giải quyết
vấn đề của đồ thị lớn, một trong các nền tảng phải kể đến là MapReduce (chi tiết về
MapReduce đƣợc trình bày ở Chƣơng 2)
1.1.2. Đồ thị có trọng số và đƣờng đi
Định nghĩa 1.6. Đồ thị có trọng số là đồ thị mà mỗi cạnh của nó đƣợc gán cho
tƣơng ứng với một số (nguyên hoặc thực). Số gán cho mỗi cạnh của đồ thị đƣợc gọi
là trọng số của cạnh. Hình 2 sau đây minh họa cho một đồ thị có trọng số.

10


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce

Hình 1.2: Đồ thị có trọng số
Định nghĩa 1.7. Cho đồ thị G = (V, E). Đƣờng đi p từ một đỉnh u đến một đỉnh
v là một dãy n đỉnh:

x0, x1, x2, …, xn-1


Trong đó: u = x0, v = xn-1, (xi, xi+1)

E,

Định nghĩa 1.8. Cho đồ thị có trọng số G=(V, E). Độ dài của đƣờng đi p từ một
đỉnh u đến một đỉnh v là tổng của (n-1) trọng số tạo ra từ dãy n đỉnh: x0, x1, x2, …,
xn-1, ký hiệu là:
∑
Trong đó: u = x0, v = xn-1,
1.2.

(xi, xi+1)

E,

,

xi→xi+1

Nghiên cứu về các ứng dụng của bài toán xử lý đồ thị lớn

Đồ thị lớn đƣợc sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác
nhau. Chẳng hạn, chúng ta có thể phân biệt các hợp chất hoá học hữu cơ khác nhau
với cùng một công thức phân tử nhƣng khác nhau về cấu trúc phân tử nhờ đồ thị.
Chúng ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tin
đƣợc với nhau hay không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có trọng số

11



Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
trên các cạnh có thể sử dụng để giải quyết các bài toán nhƣ tìm đƣờng đi ngắn nhất
giữa hai thành phố trong cùng một mạng giao thông.
Đặc biệt, việc khai thác thông tin từ các đồ thị lớn nhƣ các mạng xã hội đã và
đang đem lại nhiều lợi ích trong thực tế. Một mạng xã hội đƣợc coi là một đồ thị
lớn, ở đó mỗi ngƣời dùng đóng vai trò là một đỉnh của đồ thị, và một cạnh đƣợc tạo
bởi hai ngƣời dùng kết bạn với nhau. Nhờ việc phân tích, xử lý đồ thị (ví dụ thao tác
duyệt đồ thị, tìm đƣờng đi) các nhà phát triển có thể tạo ra các kênh quảng cáo mà
thông tin đƣợc lan truyền từ ngƣời dùng này đến ngƣời dùng khác, cũng nhƣ việc
chia sẻ thông tin giữa các ngƣời dùng trong mạng xã hội đƣợc thực hiện một cách
nhanh chóng.
Một ứng dụng mang lại nhiều lợi ích của đồ thị lớn đó là việc khai thác mạng
lƣới các website trên Internet. Ở đó, mỗi website đóng vai trò là một đỉnh của đồ
thị, liên kết đến một website khác tạo ra một cạnh của đồ thị. Với sự bùng nổ của
Internet hiện nay, đây là một đồ thị rất lớn với nhiều thách thức cho việc khai thác,
xử lý và tìm ra các thông tin ý nghĩa. Nhờ việc xử lý đồ thị lớn này, các công cụ tìm
kiếm (Web Search Engine) có thể đƣa ra các kết quả một cách nhanh trong đáp ứng
yêu cầu ngƣời dùng. Hay việc xếp thứ hạng website trên các công cụ tìm kiếm đã
đem lại lợi ích kinh tế cho các nhà phát triển công cụ tìm kiếm (ví dụ Google, Bing,
v.v…), cũng nhƣ các công ty kinh doanh dựa vào quảng cáo sản phẩm trên Internet.
1.3.

Những thách thức trong xử lý đồ thị lớn.

Trong tƣơng lai, khi kích thƣớc của đồ thị ngày càng tăng cùng với các nhu cầu
ứng dụng khác nhau của nó thì sẽ mở ra càng nhiều cơ hội thú vị mới cho việc
nghiên cứu trong khai thác đồ thị lớn. Dƣới đây xin đƣợc liệt kê 4 trong số những
hƣớng nghiên cứu quan trọng của đồ thị lớn.
1.3.1. Phân tích đồ thị lớn

Vấn đề ở đây là làm thế nào để thiết kế các công cụ/mô hình cho phân tích đồ thị
lớn để cung cấp hạ tầng tính toán nhanh và có khả năng mở rộng. Một thách thức

12


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
cho hƣớng nghiên cứu này là cân bằng tốc độ và khả năng mở rộng. MapReduce là
mô hình xử lý dữ liệu lớn dựa trên các đĩa (disk), và do đó nó đƣợc mở rộng và
mạnh mẽ. Nhƣng nó không đƣợc tối ƣu về tốc độ truy cập. Mặt khác, hệ thống dựa
trên bộ nhớ trong nhƣ MPI xử lý nhanh, nhƣng lại không có khả năng mở rộng. Một
nền tảng phân tích dữ liệu lớn lý tƣởng khai thác tốt nhất cả hai đĩa và bộ nhớ sẽ
cung cấp các tính toán nhanh và có khả năng mở rộng [2].
1.3.2. Thiết kế thuật toán
Trên thực tế có rất nhiều thuật toán cho xử lý đồ thị, tuy nhiên vấn đề đặt ra là
làm thế nào để chuyển đổi các thuật toán từ tuần tự sang xử lý song song phân tán.
Một thách thức khác với việc thiết kế thuật toán đó là làm sao để chuyển các thuật
toán đồ thị chính xác nhƣng chƣa hiệu quả trên đồ thị lớn thành các thuật toán gần
đúng mà hiệu quả. Bởi vì với các đồ thị lớn, các thuật toán có độ phức tạp lớn hơn
độ phức tạp tuyến tính thì sẽ chi phí rất nhiều thời gian xử lý và khó khả thi, cho
nên thay bằng một thuật toán gần đúng có thể sẽ chạy nhanh hơn và phù hợp hơn
với xử lý đồ thị lớn.
1.3.3. Nén đồ thị

Hình 1.3: Nén đồ thị
Một cách hiệu quả để đối mặt với thực tế kích thƣớc ngày càng lớn của các đồ
thị, nén đồ thị là một kỹ thuật đáng đƣợc nghiên cứu. Nén đồ thị không chỉ tiết kiệm

13



Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
không gian lƣu trữ mà còn giúp cải thiện tốc độ xử lý bởi truy cập trên đĩa là chậm
hơn so với truy cập từ bộ nhớ. Một thách thức trong nén đồ thị là thiết kế tốt các
thuật toán phân mảnh hay phân cụm đồ thị, bởi vì khi có ít kết nối giữa các cụm thì
sẽ cải thiện đƣợc khả năng nén. Vấn đề ở đây là các đồ thị trên thực tế thƣờng rất
khó cho phân mảnh [3].
1.3.4. Trực quan hóa đồ thị
Một đồ thị lớn sẽ có rất nhiều đỉnh với nhiều mối tƣơng tác giữa chúng với nhau.
Bởi vậy việc trực quan hóa đồ thị sẽ giúp chúng ta hiểu tốt hơn cấu trúc và các mối
tƣơng tác trong đồ thị, ví dụ nhƣ GEPHI [4] là một công cụ khá hữu hiệu trong trực
quan đồ thị. Vấn đề ở đây là làm thế nào để tổng quát hóa nên các đặc tính của một
đồ thị rất lớn để ngƣời dùng có thể dễ hiểu chỉ trên một màn hình có độ phân giải
giới hạn.
1.4.

Một số kỹ thuật và công cụ xử lý đồ thị lớn

Một số mô hình lập trình thông thƣờng nhƣ truyền thông điệp (message-passing)
và xử lý đồng bộ (bulk-synchronous processing) đã đƣợc áp dụng vào phân tích đồ
thị lớn. Trong đó kỹ thuật truyền thông điệp đã thu hút rất nhiều nhà nghiên cứu
tham ra và tạo ra nhiều công cụ hữu ích cho phân tích đồ thị lớn [29, 30]. Những
công cụ tạo ra bởi kỹ thuật này có thể triển khai trên môi trƣờng phân tán, song
chúng đối mặt với vấn đề nhƣ việc vận chuyển dữ liệu qua mạng hay việc truy cập
bộ nhớ chính đối với các đồ thị lớn. Một nền tảng mới đƣợc đề cập đến trong những
năm gần đây cho việc phân tích đồ thị lớn đó là MapReduce [5]. Nền tảng
MapReduce thƣờng gồm các máy chủ phân tán và nó chạy nhiều tác vụ khác nhau
song song. Có nhiều thành phần quản lý việc giao tiếp giữa các nodes khác nhau
của dữ liệu và cung cấp tính sẵn sàng cao và mức độ chịu lỗi. Chƣơng trình đƣợc
viết theo chức năng MapReduce tự động đƣợc phân tán và thực thi song song trên

các máy chủ. Nền tảng MapReduce quan tâm cả chi tiết của phân vùng dữ liệu và
thực thi quá trình xử lý trên máy chủ phân tán lúc chạy. Trong khi xử lý nếu có lỗi,
nền tảng này cung cấp tính sẵn sàng cao và các node khác thực hiện thay thế nhiệm
14


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
vụ của node bị lỗi. Ở các chƣơng tiếp theo, tác giả sẽ trình bày bản chất của nền
tảng MapReduce, cách nghiên cứu sử dụng MapReduce trong phân tích đồ thị lớn
cũng nhƣ ứng dụng của nó.

15


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
CHƢƠNG 2:
2.1.

MÔ HÌNH LẬP TRÌNH MAPREDUCE

Tổng quan về Hadoop/MapReduce

2.1.1. Hadoop
a) Hadoop là gì?
Apache Hadoop định nghĩa:
“Apache Hadoop là một framework dùng để chạy những ứng dụng trên một
cluster lớn đƣợc xây dựng trên những phần cứng thông thƣờng1. Hadoop hiện thực
mô hình Map/Reduce, đây là mô hình mà ứng dụng sẽ đƣợc chia nhỏ ra thành nhiều
phân đoạn khác nhau, và các phần này sẽ đƣợc chạy song song trên nhiều node khác
nhau. Thêm vào đó, Hadoop cung cấp một hệ thống file phân tán (HDFS) cho phép

lƣu trữ dữ liệu lên trên nhiều node. Cả Map/Reduce và HDFS đều đƣợc thiết kế sao
cho framework sẽ tự động quản lý đƣợc các lỗi, các hƣ hỏng về phần cứng của các
node.”
Wikipedia định nghĩa:
“Hadoop là một framework nguồn mở viết bằng Java cho phép phát triển các
ứng 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.

16


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
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 Linux2.
b) Kiến trúc của Hadoop
Hadoop bao gồm các thành phần sau:
 Hadoop Common: chứa các thƣ viện và các tiện ích cần thiết cho các
mô-đun khác của Hadoop
 Hadoop Distributed File System (HDFS): Hệ thống file phân tán, lƣu
trữ dữ liệu trên các máy, cung cấp băng thông tổng hợp rất cao trên các
cluster.
 Hadoop YARN: một nền tảng quản lý tài nguyên chịu trách nhiệm về
quản lý tài nguyên tính toán trong các cụm và sử dụng chúng để lập lịch
trình cho các ứng dụng của ngƣời dùng.
 Hadoop MapReduce: một mô hình lập trình để xử lý dữ liệu quy mô
lớn.
Một cụm Hadoop nhỏ bao gồm một master và nhiều nút slaver. Một nút
master gồm có: JobTracker, TaskTracker, NameNode và DataNode. Một nút slaver,
2

Thực tế ta có thể làm cho Hadoop chạy trên Windows. Muốn Hadoop chạy đƣợc trên Windows, ta
phải cài đặt thêm chƣơng trình giả lập môi trƣờng Linux trên Windows.

17


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
gồm một DataNode và một TaskTracker. Hadoop đòi hỏi Java Runtime
Environment (JRE) 1.6 hoặc cao hơn. Cách thức chuẩn để khởi động và tắt các kịch
bản yêu cầu Secure Shell (SSH) đƣợc thiết lập giữa các nút trong cụm.


Hình 2.1: Kiến trúc của một cụm Hadoop
Trong một cụm Hadoop lớn hơn, HDFS đƣợc quản lý thông qua một máy chủ
chuyên dụng NameNode để lƣu trữ các chỉ số hệ thống tập tin, và một NameNode
thứ cấp có thể tạo ra những bản sao cấu trúc bộ nhớ của namenode, do đó ngăn
ngừa tập tin hệ thống sai hỏng và giảm mất mát dữ liệu. Tƣơng tự nhƣ vậy, một
máy chủ JobTracker có thể quản lý việc lập kế hoạch.

18


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce
 Hệ thống tệp tin phân tán HDFS
HDFS (Hadoop Distributed File System) là một hệ thống tệp tin phân tán phân
phối, khả năng mở rộng, và di động tập tin hệ thống đƣợc viết bằng Java dành cho
Hadoop. Mỗi nút trong Hadoop thƣờng có một NameNode; một cụm DataNodes
hình thành cụm HDFS.

Hình 2.2: Mô hình kiến trúc của HDFS
 Các trình nền của Hadoop
 NameNode
NameNode là trình nền quan trọng nhất của Hadoop. Nó nắm giữ cây thƣ mục
của tất cả các tệp tin trong hệ thống HDFS và theo dõi các tệp dữ liệu trên Cluster.
Các ứng dụng client sẽ hỏi NameNode khi chúng muốn xác định vị trí của tệp tin
trên hệ thống hoặc khi chúng muốn thêm/sao chép/di chuyển/xóa một tệp.

19


Xử lý đồ thị lớn trên môi trƣờng phân tán sử dụng MapReduce

NameNode sẽ phản hồi lại các yêu cầu bằng cách liệt kê ra các máy chủ DataNode,
nơi nắm giữa dữ liệu cần thiết.
Khi một NameNode không hoạt động thì toàn bộ tệp tin của hệ thống sẽ bị
« offline ». Khi đó, một tùy chọn là SecondNameNode sẽ đƣợc sử dụng trên một
máy riêng biệt. Nó chỉ tạo ra các điểm đánh dấu của không gian tên bằng cách kết
hợp các chỉnh sửa tập tin vào tập tin fsimage và không cung cấp bất kỳ một cơ chế
dự phòng nào.
 DataNode
Một DataNode dùng để lƣu trữ dữ liệu trong hệ thống tệp tin HDFS. Trong hệ
thống file phân tán sẽ có nhiều DataNode. Khi bắt đầu khởi động, DataNode kết nối
đến NameNode và chờ cho đến khi nhận đƣợc các thông tin dịch vụ. Nó sẽ phản hồi
lại các yêu cầu của NameNode về các thao tác trên tệp tin hệ thống.
Các ứng dụng phía Client có thể thao tác với DataNode khi mà NameNode
cung cấp vị trí của dữ liệu.
2.1.2. MapReduce
MapReduce là một mô hình lập trình liên quan đến việc xử lý và sinh ra tập dữ
liệu lớn một cách song song, phân tán trên một cụm máy tính [5]. Một chƣơng trình
MapReduce gồm một thủ tục Map() thực hiện việc lọc, sắp xếp dữ liệu (ví dụ nhƣ
thao tác lọc và sắp xếp các học viên theo tên và đƣa vào danh sách, mỗi danh sách
tƣơng ứng với 1 tên) và một thủ tục Reduce() thực hiện thao tác để đƣa ra kết quả
theo yêu cầu (ví dụ nhƣ việc đếm số sinh viên trong mỗi danh sách, tần suất xuất
hiện của mỗi tên). Một “hệ thống MapReduce” đƣợc dựng bằng việc ghép nối giữa
các máy chủ phân tán, thực hiện các công việc một cách song song, thực hiện việc
quản lý tất cả các thông tin và truyền dữ liệu giữa các phần khác nhau của hệ thống,
cung cấp khả năng dự phòng và chịu lỗi.
Các thƣ viện của MapReduce đƣợc viết bởi nhiều ngôn ngữ với các mức độ tối
ƣu hóa khác nhau. Một mô hình cài đặt mã nguồn mở phổ biến là Apache Hadoop.

20