Luận văn Xây dựng dịch vụ thông báo sự kiện dựa trên mạng ngang hàng có cấu trúc

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Đặng Thị Nội

XÂY DỰNG DỊCH VỤ THÔNG BÁO SỰ KIỆN DỰA

TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC

Ngành: Công nghệ thông tin

Chuyên ngành: Truyền dữ liệu và mạng máy tính

Mã số: 60.48.15

LUẬN VĂN THẠC SĨ

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS.NGUYỄN HOÀI SƠN

HÀ NỘI - 2011

LỜI CAM ĐOAN

Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá

nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung luận văn, những

điều được trình bày hoặc là của cá nhân tôi, hoặc do tôi tổng hợp được từ các nguồn tài

liệu khác nhau. Tất cả các tài liệu được tham khảo điều có xuất xứ rõ ràng, được trích

dẫn hợp pháp và được liệt kê đầy đủ trong mục tài liệu tham khảo của luận văn.

Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định

cho lời cam đoan của mình.

Hà Nội, ngày 15 tháng 06 năm 2011

Đặng Thị Nội

LỜI CẢM ƠN

Tôi xin bày tỏ lời cảm ơn chân thành tới các thầy cô giáo trong khoa Công nghệ

thông tin - Đại học Công nghệ - ĐHQG Hà Nội, đặc biệt là các thầy cô giáo trong bộ

môn Truyền dữ liệu và mạng máy tính, đã tạo điều kiện thuận lợi và giúp đỡ tôi trong

thời gian tôi học tập.

Tôi xin bày tỏ lòng biết ơn chân thành, lời cảm ơn sâu sắc đối với thầy giáo TS.

Nguyễn Hoài Sơn đã tận tình hướng dẫn, định hướng cho tôi giải quyết các vấn đề

trong luận văn.

Tôi cũng xin bày tỏ lời cảm ơn đối với cha mẹ, gia đình, các đồng nghiệp và

các bạn học viên lớp Cao học K14T2 đã động viên, giúp đỡ, góp ý cho tôi rất nhiều

trong quá trình hoàn thành luận văn.

Luận văn được tài trợ một phần từ đề tài nghiên cứu cơ bản mã số 102.01.25.09

Quỹ phát triển khoa học và công nghệ quốc gia (NAFOSTED).

Hà Nội, ngày 15 tháng 06 năm 2011

Đặng Thị Nội

MỤC LỤC

LỜI MỞ ĐẦU

CHƯƠNG 1. MÔ HÌNH DỊCH VỤ THÔNG BÁO SỰ KIỆN

1

3

1.1. Tổng quan về dịch vụ thông báo sự kiện................................................................... 3

1.2. Ứng dụng của dịch vụ thông báo sự kiện.................................................................. 4

1.3. Hoạt động của dịch vụ thông báo sự kiện.................................................................. 6

1.4. Hạn chế của các dịch vụ hiện tại............................................................................... 9

1.5. Kết luận.................................................................................................................. 10

CHƯƠNG 2. SỬ DỤNG MẠNG NGANG HÀNG CÓ CẤU TRÚC TRONG DỊCH VỤ

THÔNG BÁO SỰ KIỆN

11

2.1. Khái niệm mạng ngang hàng .................................................................................. 11

2.2. Ưu, nhược điểm của mạng ngang hàng................................................................... 13

2.3. Phân loại mạng ngang hàng.................................................................................... 14

2.3.1.

2.3.2.1.

2.3.2.2.

2.3.2.3.

2.3.2.

2.3.2.1.

2.3.2.2.

Mạng ngang hàng phi cấu trúc....................................................................... 14

Mạng ngang hàng tập trung.................................................................. 14

Mạng ngang hàng thuần túy ................................................................. 16

Mạng ngang hàng lai ghép.................................................................... 17

Mạng ngang hàng có cấu trúc........................................................................ 19

Mạng ngang hàng có cấu trúc dựa trên DHT (Distributed Hash Table) . 21

Mạng ngang hàng có cấu trúc Chord .................................................... 23

2.4. Tại sao sử dụng mạng ngang hàng có cấu trúc trong hệ thống thông báo sự kiện .... 28

2.5. Kết luận.................................................................................................................. 29

CHƯƠNG 3. XÂY DỰNG DỊCH VỤ THÔNG BÁO SỰ KIỆN DỰA TRÊN MẠNG

NGANG HÀNG CÓ CẤU TRÚC

30

3.1. Mục đích và yêu cầu của hệ thống.......................................................................... 30

3.2. Giải pháp thực hiện ................................................................................................ 31

3.3. Cấu trúc hệ thống ................................................................................................... 36

3.4. Hoạt động của hệ thống.......................................................................................... 37

3.5. Kết luận.................................................................................................................. 39

CHƯƠNG 4. THỰC THI VÀ ĐÁNH GIÁ CHƯƠNG TRÌNH

40

4.1. Triển khai hệ thống ................................................................................................ 40

4.1. Kết quả thử nghiệm................................................................................................ 43

4.2. Nhận xét và đánh giá hệ thống................................................................................ 45

CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

46

5.1. Kết luận.................................................................................................................. 46

5.2. Hướng phát triển .................................................................................................... 46

TÀI LIỆU THAM KHẢO

47

DANH MỤC BẢNG BIỂU

Bảng 1: Bảng định nghĩa các trường trong Finger Table....................................................... 25

Bảng 2: Kết quả thử nghiệm yêu cầu sự kiện cho các sự kiện đã được cung cấp.................. 44

Bảng 3: Kết quả thử nghiệm cung cấp sự kiện cho yêu cầu có sẵn trên mạng ...................... 44

DANH MỤC HÌNH ẢNH

Hình 1: Cách thức hoạt động của hệ thống thông báo sự kiện................................................. 7

Hình 2: Trình tự thông báo sự kiện......................................................................................... 8

Hình 3: Mô hình Client/Server ............................................................................................. 11

Hình 4: Mô hình mạng ngang hàng P2P............................................................................... 12

Hình 5: Các loại hình mạng ngang hàng............................................................................... 14

Hình 6: Mạng ngang hàng tập trung thế hệ thứ nhất (Napster).............................................. 15

Hình 7: Mạng ngang hàng thuần túy (Gnutella 4.0, FreeNet)................................................ 16

Hình 8: Mạng ngang hàng lai ghép....................................................................................... 18

Hình 9: Mạng ngang hàng có cấu trúc.................................................................................. 20

Hình 10: Lưu giữ key trong mạng Chord.............................................................................. 26

Hình 11: Tìm kiếm khóa sử dụng bảng FingerTable............................................................. 27

Hình 12: Mô hình luồng sự kiện........................................................................................... 31

Hình 13: Chi tiết một số sự kiện........................................................................................... 34

Hình 14: Cấu trúc của hệ thống thông báo sự kiện................................................................ 36

Hình 15: Hoạt động của hệ thống thông báo sự kiện............................................................. 38

Hình 16: Mô hình thử nghiệm.............................................................................................. 40

Hình 17: Giao diện chức năng cung cấp sự kiện................................................................... 41

Hình 18: Giao diện chức năng yêu cầu sự kiện..................................................................... 41

Hình 19: Giao diện thông báo sự kiện .................................................................................. 42

Hình 20: Đồ thị kết quả thử nghiệm yêu cầu sự kiện cho các sự kiện đã được cung cấp........ 44

Hình 21: Đồ thị kết quả thử nghiệm cung cấp sự kiện cho yêu cầu có sẵn trên mạng ............ 45

1

LỜI MỞ ĐẦU

Với sự phát triển của công nghệ thông tin ngày nay, lượng thông tin cung cấp vô

cùng phong phú và đa dạng. Điều này cũng gây ra một số khó khăn khi người dùng

không thể tìm được chính xác điều mà họ quan tâm. Do đó chúng tôi phát triển dịch vụ

để có thể tìm được dữ liệu một cách chính xác và đầy đủ nhất có thể.

Tuy hiện nay có nhiều dịch vụ thông báo sự kiện nhưng khi muốn tìm kiếm

thông tin người dùng phải thực hiện câu truy vấn để hệ thống đưa ra kết quả phản hồi.

Để đáp ứng được nhu cầu của người sử dụng là tìm kiếm thông tin chính xác và phù

hợp với yêu cầu nên luận văn đã xây dựng một hệ thống giúp người dùng chỉ phải

đăng ký sự kiện, khi sự kiện phát sinh hệ thống sẽ thông báo một cách kịp thời đến

người đã đăng ký mà không phải thực hiện truy vấn.

Do các máy chủ cung cấp dịch vụ hiện nay hoạt động rời rạc không có sự liên kết

với nhau gây quá tải tại máy chủ khi có nhiều người cùng truy cập một thời điểm.

Chính vì vậy nảy sinh nhu cầu liên kết các nhà cung cấp dịch vụ lại với nhau thành

một mạng dịch vụ. Để liên kết các nhà cung cấp dịch vụ lại với nhau thì cần phải giải

quyết các vấn đề về quản lý, lưu trữ, xử lý thông tin phân tán và tìm kiếm thông tin

trên quy mô lớn. Do bản chất có thể quản lý, lưu trữ và tìm kiếm dữ liệu trên quy mô

lớn và dễ dàng mở rộng nên mạng hàng hàng có cấu trúc là giải pháp tốt để liên kết

các nhà cung cấp dịch vụ với nhau.

Vì vậy, luận văn đã xây dựng một hệ thống thông báo sự kiện dựa trên mạng

ngang hàng có cấu trúc lưu trữ và xứ lý thông tin phân tán (bản chất của mạng ngang

hàng), tìm kiếm thông tin nhanh, có thể tìm kiếm dữ liệu trên quy mô lớn và hệ thống

có thể dễ dàng mở rộng.

Để đánh giá hiệu quả của hệ thống đã xây dựng, chúng tôi đã thử nghiệm và đánh

giá thông qua môi trường mạng có giới hạn băng thông và độ trễ giống với môi trường

mạng Internet hiện nay. Kết quả thử nghiệm cho thấy hệ thống xây dựng đã đáp ứng

được các yêu cầu của dịch vụ thông báo sự kiện là cung cấp dịch vụ thời gian thực và

có thể dễ dàng mở rộng hệ thống.

Khoá luận được chia làm 5 chương:

- Chương 1: Chương này sẽ giới thiệu về dịch vụ thông báo sự kiện đang được sử

dụng và các yêu cầu của dịch vụ thông báo sự kiện sẽ xây dựng.

2

- Chương 2: Trong chương này sẽ giới thiệu tổng quan về mạng ngang hàng, ưu

nhược điểm của mạng ngang hàng và lý do sử dụng mạng ngang hàng có cấu trúc để

xây dựng hệ thống.

- Chương 3: Chương này sẽ trình bày về ý tưởng, yêu cầu và cách thức xây dựng

dịch vụ thông báo sự kiện dựa trên mạng ngang hàng có cấu trúc.

- Chương 4: Trình bày về mô hình thực nghiệm để đánh giá hiệu quả của dịch vụ

thông báo sự kiện đã xây dựng, đưa ra các nhận xét đánh giá kết quả thử nghiệm.

- Chương 5: Kết luận và hướng phát triển tiếp theo của luận văn.

3

CHƯƠNG 1. MÔ HÌNH DỊCH VỤ THÔNG BÁO SỰ KIỆN

Ngày nay, với sự tiến bộ của khoa học kỹ thuật, đặc biệt là sự phát triển nhanh

chóng của công nghệ phần cứng đã có thể tạo ra các thiết có khả năng lưu trữ và xử lý

lớn với giá thành nhỏ khiến cho số lượng người dùng sử dụng các thiết bị này tăng

nhanh chóng. Chính vì số lượng các thiết bị này tăng nhanh dẫn đến nhu cầu của người

dùng muốn sử dụng các dịch vụ gia tăng trên các thiết bị này lớn. Dịch vụ thông báo

sự kiện là một dịch vụ gia tăng đang phát triển ngày nay. Các ứng dụng của dịch vụ

này rất đa dạng, cung cấp cho thông tin nhanh và chính xác.

1.1. Tổng quan về dịch vụ thông báo sự kiện

Dịch vụ thông báo sự kiện là một hạ tầng ứng dụng độc lập, hỗ trợ cho việc xây

dựng các hệ thống dựa trên nền sự kiện. Các node cung cấp dịch vụ đến cơ sở hạ tầng

và node yêu cầu sự kiện đăng ký với cơ sở hạ tầng để nhận các thông báo liên quan.

Dịch vụ thông báo sự kiện cho phép yêu cầu sự kiện đồng thời cung cấp các sự kiện

được yêu cầu thông qua mạng internet hoặc kết nối không dây. Dịch vụ này có thể

cung cấp sự kiện một cách tự động khi có sự kiện phát sinh.

Một dịch vụ thông báo sự kiện là dịch vụ kết nối vô danh giữa các bên lẫn nhau.

Dịch vụ thu nhận, lọc và cung cấp thông tin về các sự kiện.

Một hệ thông báo sự kiện thực hiện dịch vụ thông báo sự kiện cụ thể. Chúng ta

đề cập đến dịch vụ thông báo sự kiện như là khái niệm nói chung và hệ thống thông

báo sự kiện khi chú trọng vào việc thực hiện các dịch vụ được thiết kế. Nhiều công bố

không cho một định nghĩa rõ ràng mà chỉ là một mô tả khái niệm về dịch vụ thông báo

sự kiện, gọi đó là “Dịch vụ thông báo”, “dịch vụ Cung cấp/Yêu cầu”, hay “hệ thống

đẩy”.

[2] Dịch vụ này khác với các dịch vụ khác ở chỗ truy vấn của các dịch vụ trước

đây được gửi lên và lưu trữ trước mà kết quả có thể chưa tồn tại nhưng người đăng ký

truy vấn hy vọng sẽ nhận được thông báo khi kết quả trở thành có sẵn. Các dịch vụ

hiện tại thích hợp cho các ứng dụng tìm kiếm mà nơi truy vấn đang chờ thông tin, đối

lập với các ứng dụng truyền thống nơi các truy vấn cần phải tồn tại trước.

Dịch vụ được sử dụng trong mạng ngang hàng P2P là một đề tài rất được chú ý

trong những năm gần đây vì P2P có thể được áp dụng cho các mạng phân tán như là

cách hiệu quả để chia sẻ tài nguyên, giảm thiểu chi phí máy chủ và phát huy hợp tác

giữa các node. Thông thường một node cung cấp không biết ai đang quan tâm đến dữ

4

liệu của nó và ngược lại một node đăng ký cũng không biết ở đâu trong mạng dữ liệu

của nó quan tâm là có sẵn. Vì vậy một vấn đề khó khăn là thiết kế cơ chế cho người

đăng ký và nhà cung cấp để tìm thấy nhau một cách nhanh chóng và hiệu quả. Đơn

giản là quảng bá các truy vấn đến tất cả các node trong mạng hoặc để sử dụng một

trung tâm chỉ mục của tất cả các truy vấn được đăng ký và thông tin được công bố.

Do đó, một loạt các cơ chế Cung cấp/ Đăng ký đã được đề xuất, dựa trên thông

báo và dựa vào cấu trúc. Phương pháp tiếp cận đầu tiên được thiết kế cho tất cả các

mạng phi cấu trúc, trong đó các nút Đăng ký và các node Cung cấp tìm thấy nhau,

trao đổi thông tin bằng cách sử dụng các liên kết ngang hàng hiện có, thông thường

dựa trên một số hình thức ngẫu nhiên. Một cách tiếp cận khác là tổ chức các nút vào

một cấu trúc phủ và phát triển phương pháp Cung cấp/ Đăng ký trên đỉnh của nó. Ví

dụ mạng phủ là dựa vào bảng phân tán DTH. Lợi thế của cách tiếp cận dựa vào thông

báo là áp dụng cho mạng phi cấu trúc, trong khi phương pháp tiếp cận dựa trên cấu

trúc được ưa chuộng cho hiệu quả tốt hơn.

1.2. Ứng dụng của dịch vụ thông báo sự kiện

- Phát hiện và cảnh báo xâm nhập trong mạng không dây: Ứng dụng quan sát tất

cả những hoạt động hệ thống, như các file log và những lưu lượng mạng thu thập

được, theo dõi những cuộc gọi hệ thống, lịch sử kiểm tra và những thông điệp báo lỗi

trên hệ thống… phát hiện người xâm nhập và gửi cảnh báo đến quản trị mạng

- Hợp nhất hệ thống, thiết bị và các ứng dụng từ nhiều nhà cung cấp: truyền

thông thông báo sự kiện đến các node yêu cầu các sự kiện quan trọng như: sự gián

đoạn sản xuất, các mối đe dọa an ninh, và thiên tai, … Khi sự kiện xảy ra, cảnh báo

được gửi đến nhóm được xác định trước hoặc các cá nhân, những người có thể phản

ứng nhanh chóng với trạng thái và phản hồi. Tin nhắn được hỗ trợ trên hầu như bất kỳ

loại điện thoại hoặc thiết bị nhắn tin, và thông qua email.

- Gửi tin nhắn tức thời: Khi có bạn bè lên mạng, người sử dụng sẽ được gửi tin

nhắn đến thông báo và có thể gửi tin nhắn, gửi mail, SMS, … cho nhau

- Cung cấp tin tức: Người dùng có nhu cầu thông tin về một lĩnh vực nào đấy, hệ

thống sẽ dựa vào yêu cầu của người dùng và gửi thông tin chính xác cho người dùng

khi sự kiện về thông tin xẩy ra

-[5] Hệ thống cá nhân hóa: Thuật ngữ cá nhân không bị giới hạn thông báo sự

kiện, nó bao gồm thể hiện quan tâm của khách hàng trong hồ sơ cá nhân. Hồ sơ được

5

khách hàng định nghĩa rõ ràng hoặc hoàn toàn bởi các dữ liệu khai thác hoặc phân tích

các hoạt động của khách hàng. Hệ thống cá nhân hóa hoạt động trên mức độ ứng dụng.

- Dịch vụ cảnh báo: Thuật ngữ hệ thống thông báo hoặc dịch vụ thông báo được

dùng chung khi nói về dịch vụ thông báo sự kiện, nó chú trọng đến ứng dụng của dịch

vụ. Thuật ngữ “dịch vụ cảnh báo” hiện nay được sử dụng rộng rãi trong phạm vi của

các thư viện kỹ thuật số; thuật ngữ “cảnh báo” cũng thường được đề cập đến dịch vụ

đăng ký nhận tin qua email. Các ứng dụng ban đầu cho các dịch vụ cảnh báo được hệ

thống nâng báo động trong trường hợp nguy hiểm, xâm nhập, hoặc trục trặc động cơ.

- Dịch vụ Cung cấp/ Đăng ký: Các mô hình Cung cấp/ Đăng ký là một mô hình

tương tác bao gồm cả nhà cung cấp thông tin (nhà cung cấp, nhà cung ứng) cung cấp

dữ liệu vào hệ thống và các khách hàng (người đăng ký, người tiêu dùng) đăng ký các

vấn đề quan tâm trong hệ thống. Vai trò của hệ thống Cung cấp/Đăng ký là cùng lúc

gửi thông tin chính xác cho đúng khách hàng yêu cầu. Hệ thống Cung cấp/ Đăng ký

được hệ thống thông báo sự kiện hỗ trợ nhà cung cấp chủ động gửi dữ liệu vào hệ

thống. Thông thường các sự kiện và tin nhắn thông báo sự kiện không phân biệt.

- Hệ thống đẩy: Thuật ngữ hệ thống đẩy đề cập đến hệ thống dựa trên Internet,

mang đến nội dung cho khách hàng của nó thông qua các kênh dựa trên đối tượng.

Việc triển khai hệ thống đẩy thường là hệ thống trung gian hỗ trợ hệ thống mức ứng

dụng.

- Hệ thống dựa trên phổ biến: Trong bối cảnh hệ thống thông tin dựa trên phổ

biến, một hệ thống thông báo sự kiện là một nhà môi giới thông tin, mua lại thông tin

từ các nguồn dữ liệu, làm tăng thêm giá trị và phân phối thông tin cho khách hàng

(bằng mạng thông tin của khách hàng). Thuật ngữ này tập trung vào việc phân phối

các tài liệu không phải là quan sát và lọc các sự kiện.

- Hệ thống lọc thông tin: Hệ thống như là một hệ thống thông báo sự kiện có các

giao dịch đặc biệt là các tài liệu mới hoặc thay đổi. Các dịch vụ này còn được gọi là hệ

thống lọc tài liệu.

- Hệ thống định tuyến dựa trên nội dung: Thuật ngữ này dùng để chỉ các hệ thống

truy hồi thông tin trong đó các truy vấn được định tuyến đến các máy chủ có sẵn dựa

trên sự phù hợp mong đợi của máy chủ để truy vấn.

- Hệ thống giám sát (sự kiện): Thuật ngữ này dùng để chỉ các hệ thống giám sát

nguồn sự kiện nào đó, lọc các sự kiện và gửi thông báo. Nhìn chung, các nguồn sự

kiện là những nguồn quan sát bị động như các cảm biến và đầu đo. Các ứng dụng tự

6

quan sát, giám sát chương trình máy tính để giao tiếp trong hệ thống phân phối và ứng

dụng web.

- Cơ sở hạ tầng dựa trên sự kiện: Cơ sở hạ tầng dựa trên sự kiện hỗ trợ trao đổi

tin nhắn không đồng bộ giữa các đối tượng trong một môi trường phân phối. Xác định

khả năng tương tác độc lập, hệ thống không đồng nhất và xây dựng một giao tiếp

chương trình đến chương trình ở cấp độ hệ thống

- Dịch vụ nhận thức: Thuật ngữ nhận thức mô tả điều chỉnh tự động các thông tin

hiện tại của nhà cung cấp và khách hàng. Khách hàng nhận thức tất cả các thay đổi của

nhà cung cấp, hoặc là đối tượng mới, hoặc là xóa các đối tượng, hoặc là sửa đổi các

đối tượng.

- Dịch vụ xử lý sự kiện: Thuật ngữ dịch vụ xử lý sự kiện mô tả một dịch vụ được

quy định trong Java

1.3. Hoạt động của dịch vụ thông báo sự kiện

Hệ thống hoạt động dựa trên khả năng lưu trữ của mạng ngang có cấu trúc

Chord.

Khi người dùng yêu cầu một sự kiện nào đó, hệ thống sẽ tạo ra khóa tương ứng

với một cặp (thuộc tính - giá trị) của sự kiện yêu cầu và gửi yêu cầu sự kiện đến một

node gọi là node phụ trách khóa. Node phụ trách khóa sẽ lưu lại sự kiện yêu cầu, khóa

và địa chỉ của node đã yêu cầu sự kiện. Khi có sự kiện tương ứng với yêu cầu, node

phụ trách khóa sẽ gửi thông tin sự kiện cho node đó theo đúng địa chỉ của node yêu

cầu sự kiện mà nó đã lưu.

Sự kiện khi được cung cấp, hệ thống sẽ tạo ra các cặp (thuộc tính - giá trị) của sự

kiện yêu cầu và gửi thông tin sự kiện yêu cầu đến các node phụ trách khóa . Node phụ

trách khóa sẽ kiểm tra cơ sở dữ liệu, lấy ra danh sách các node gửi yêu cầu phù hợp

với thông tin sự kiện được cung cấp và gửi thông tin sự kiện đến node yêu cầu sự kiện.

Việc lưu thông tin sự kiện tại 1 node nào đó trên mạng đảm bảo cho việc lưu trữ

không bị quá tải và khi có vấn đề xảy ra với 1 node trong mạng thì khả năng cung cấp

dịch vụ không bị gián đoạn.

7

Hình 1: Cách thức hoạt động của hệ thống thông báo sự kiện

[5] Hình 1 mô tả các thành phần trong hệ thống và mối liên quan giữa chúng.

Trong mô hình này các khái niệm về sự kiện, mô tả sự kiện đã được đơn giản hóa

Đối tượng quan tâm là các đối tượng thông tin của node cung cấp, tùy chọn trong

kho đối tượng. Thay đổi của các đối tượng này (tạo mới, cập nhật, xóa) do bộ phát

hành thực hiện.

Nhiệm vụ của bộ quan sát là phát hiện những thay đổi của đối tượng đơn lẻ hoặc

trong kho đối tượng. Nếu bộ phát hành không thông báo cho bộ quan sát về các thay

đổi thì bộ quan sát sẽ làm nhiệm vụ phát hiện những thay đổi này (thực hiện theo một

lịch trình). Mọi thay đổi là sự kiện thì các sự kiện được bộ quan thông báo đến bộ lọc.

Bộ lọc lưu mô tả dịch vụ của node yêu cầu dịch vụ và so sánh các sự kiện với phần

truy vấn của các mô tả. Nếu mô tả dịch vụ với sự kiện phù hợp, bộ lọc này sẽ tạo ra

một thông báo sự kiện và cung cấp nó cho node yêu cầu dịch vụ này. Đối với các sự

kiện phức hợp được tìm thấy, các sự kiện sẽ được lưu trữ trong Kho lưu trữ.

Bộ thông báo lần lượt kiểm tra thời hạn của các yêu cầu. Nếu yêu cầu phải được

cung cấp ngay lập tức, thông báo sự kiện được chuyển đổi theo đúng định dạng cụ thể

của node yêu cầu và cung cấp sự kiện. Nếu không, thông báo sẽ được đưa vào bộ đệm

cho đến khi thông báo hết hạn. Bộ thông báo sẽ theo dõi hạn của các sự kiện.

Trong mô tả của Bộ yêu cầu sự kiện cần phân biệt hai phần: Cấu trúc truy vấn

(sử dụng bởi các bộ lọc) quy định rõ các sự kiện mà node yêu cầu quan tâm; trong cấu

trúc tham số, các thông số bổ sung được xác định, chẳng hạn như: thời hạn, giao thức

thông báo, và định dạng thông báo. Những thông số này có thể được sử dụng bởi Bộ

quan sát và Bộ thông báo dạng này.

8

Các thành phần của dịch vụ thông báo sự kiện có thể được (và thường được) triển

khai và nhân rộng cho khả năng nâng cấp và độ tin cậy. Bộ khởi động và đối tượng

thường trú tại Kho lưu trữ đối tượng nằm của node cung cấp.

Một dịch vụ thông báo sự kiện bao gồm các kiểu nhà cung cấp có thể thực hiện

một Bộ quan sát như là một màng bọc cho mỗi nhà cung cấp. Ngoài ra, người quan sát

có thể được chuyển đến trang web của nhà cung cấp (nếu được phép) và thực hiện

nhiệm vụ của mình như một đại lý của dịch vụ thông báo sự kiện đó.

Quan niệm trung tâm của một dịch vụ thông báo sự kiện là sự kiện. Ngược lại

với các trạng thái, các sự kiện là không có thời hạn. Sự kiện có thể được thay đổi trạng

thái trong cơ sở dữ liệu, tín hiệu trong các hệ thống tin nhắn, hoặc các sự kiện trong

thế giới thực như xuất cảnh và lượt khách của các phương tiện. Cách chính thức,

chuyển trạng thái được gây ra bởi hành động chẳng hạn như chèn, xóa, hoặc thay đổi

của một đối tượng thông tin.

Hình 2: Trình tự thông báo sự kiện

Hình 2 mô tả một trình tự thông báo sự kiện theo luông thời gian. Một sự kiện

trình tự thông báo đầy đủ cho thấy luồng dữ liệu từ khi xảy ra sự kiện cho đến khi một

thông báo được gửi đến node yêu cầu sự kiện. Hoạt động sự kiện có thể xảy ra bất cứ

lúc nào.

9

1.4. Hạn chế của các dịch vụ hiện tại

[5]Hệ thống thông báo sự kiện tương tự như các phần mền hệ thống khác, thường

là các thực thể. Dưới đây là một số nhược điểm của hệ thống hiện tại:

- Thiếu độc lập trong thi hành: Các dịch vụ phản ánh việc thực hiện cụ thể, không

bao gồm hoạt động sự kiện quan sát và cũng không bao gồm một khái niệm sự

kiện chung chung. Rất ít các dịch vụ thông báo sự kiện độc lập. Các dịch vụ

thường tập trung vào việc lưu trữ đối tượng, thông báo sự kiện không được đảm

bảo, quá trình thông báo sự kiện được mô tả đơn giản, thành phần hệ thống cụ

thể không được xác định trước.

- Thuật ngữ không thống nhất: Có nhiều tên cho loại dịch vụ (cảnh báo, dịch vụ,

dịch vụ thông báo, dịch vụ thông tin,…), có nhiều khái niệm khác nhau về dịch

vụ thông báo sự kiện, các dịch vụ thông báo sự kiện khác nhau sử dụng từ ngữ

giống nhau để mô tả.

- Mô hình sự kiện không đầy đủ: Hầu hết các dịch vụ dựa trên sự kiện, một sự kiện

được xác định bởi đặc trưng vật lý của nó như tin nhắn. Cách tiếp cận này là

không đủ vì bỏ qua các sự kiện không quan sát được, các vấn đề quan sát sự

kiện và thời điểm chèn dữ liệu.

- Dựa trên mô hình mạng Client/Server: Theo mô hình này thì một máy khách

(client) sẽ kết nối với một máy chủ thông qua một giao thức như WWW, FTP,

Telnet, email ... Nói chung, mô hình client/Server có nhiều ưu điểm, một trong

số đó là việc mọi xử lý đều nằm trên Server do đó sẽ tránh cho clients những

tính toán nặng nề, và do đó các máy Client không cần có cấu hình mạnh. Tuy

nhiên, với chế độ hoạt động theo kiểu: Client đóng vai trò thụ động, chỉ yêu cầu

dịch vụ từ Server chứ không thể cung cấp dịch vụ cho các client khác, thì chính

ưu điểm trên lại trở thành nhược điểm của mô hình này. Với tốc độ phát triển

Internet như hiện nay, số lượng client tăng nhanh liên tục gây ra sự quá tải và

tắc nghẽn tại các Server. Khi số lượng clients tăng đến một mức độ nào đó mà

nhu cầu về tải và băng thông tăng lên tới mức máy chủ không còn đủ khả năng

để đáp ứng được dịch vụ cho các máy khách thì Server bị sập và mạng sẽ bị sập

theo. Việc tăng số lượng Server để tăng khả năng chịu tải cho các Server là cần

thiết. Tuy nhiên, chi phí cho 1 Server thường là rất lớn.

10

1.5. Kết luận

Chương này đã giới thiệu tổng quan về dịch vụ thông báo sự kiện dựa trên mạng

ngang hàng có cấu trúc, hoạt động của dịch vụ thông báo sự kiện cũng như các yêu cầu

hệ thống của dịch vụ này.

Trong luận văn này, chúng tôi đề xuất việc xây dựng một hệ thống thông báo sự

kiện dựa trên mạng ngang hàng có cấu trúc. Hệ thống này lưu trữ và xứ lý thông tin

phân tán (bản chất của mạng ngang hàng), tìm kiếm thông tin nhanh, có thể tìm kiếm

dữ liệu trên quy mô lớn và hệ thống có thể dễ dàng mở rộng. Trong chương tiếp theo,

luận văn sẽ trình bày tổng quan về mạng ngang hàng: khái niệm mạng ngang hàng, ưu

nhược điểm của mạng ngang hàng, phân loại mạng ngang hàng và lý do sử dụng mạng

ngang hàng có cấu trúc trong hệ thống thông báo sự kiện.

11

CHƯƠNG 2. SỬ DỤNG MẠNG NGANG HÀNG CÓ CẤU TRÚC TRONG

DỊCH VỤ THÔNG BÁO SỰ KIỆN

Mạng ngang hàng ngày càng trở nên phổ biến, đặc biệt là trong các ứng dụng

chia sẻ tệp tin ngang hàng. Các mạng ngang hàng đã xuất hiện từ những năm 1980 và

phát triển mạnh mẽ như APANET, Usenet, FidoNet. Hiện nay, với sự tham gia của các

công ty thương mại và phi thương mại như Napster, Gnutella mạng ngang hàng ngày

càng lớn mạnh và được được nhiều người sử dụng. Nhất là hiện nay khi lượng thông

tin truyền tải trên mạng vô cùng lớn, nhu cầu tìm kiếm và chia sẻ thông tin cũng tăng

lên. Mạng ngang hàng được xây dựng giữa các máy tính độc lập có khả năng chia sẻ

dữ liệu và tận dụng tài nguyên để chia sẻ cho các máy tính khác.

2.1. Khái niệm mạng ngang hàng

Như chúng ta đã biết, ngày nay hầu như mọi dịch vụ Internet đều dựa trên mô

hình client/Server. Theo mô hình này thì một máy khách (client) sẽ kết nối với một

máy chủ thông qua một giao thức nhất định như WWW, FTP, Telnet, email ... Nói

chung, mô hình client/Server có nhiều ưu điểm, một trong số đó là việc mọi xử lý đều

nằm trên Server do đó sẽ tránh cho clients những tính toán nặng nề, và do đó các máy

Client không cần có cấu hình mạnh.

Hình 3: Mô hình Client/Server

Tuy nhiên, với chế độ hoạt động theo kiểu: Client đóng vai trò thụ động, chỉ yêu

cầu dịch vụ từ Server chứ không thể cung cấp dịch vụ cho các client khác, thì chính ưu

điểm trên lại trở thành nhược điểm của mô hình này. Với tốc độ phát triển Internet như

hiện nay, số lượng client tăng nhanh liên tục gây ra sự quá tải và tắc nghẽn tại các

Server. Khi số lượng clients tăng đến một mức độ nào đó mà nhu cầu về tải và băng

12

thông tăng lên tới mức máy chủ không còn đủ khả năng để đáp ứng được dịch vụ cho

các máy khách thì Server bị sập và mạng sẽ bị sập theo.

Việc tăng số lượng Server để tăng khả năng chịu tải cho các Server là cần thiết.

Tuy nhiên, chi phí cho 1 Server thường là rất lớn. Bởi vậy, ý tưởng về một kiến trúc

mạng mà ở đó, không cần thêm chi phí cho việc lắp đặt thêm Server, ta vẫn đảm bảo

mạng hoạt động tốt bằng cách tận dụng những tài nguyên mạng có sẵn từ chính các

máy tham gia mạng, đã dẫn đến sự ra đời của mạng ngang hàng (peer to peer - P2P) .

Mạng ngang hàng là một cấu trúc được tạo nên bởi các máy tính liên kết với

nhau, vai trò của mỗi máy tính là như nhau, mỗi máy tính là một phần và duy trì sự tồn

tại của mạng. Các máy tính trong mạng thường xuyên liên lạc với các máy tính khác

để ổn định mạng và chia sẻ dữ liệu với nhau. Mạng ngang hàng có nhiều ứng dụng và

ứng dụng phổ biến nhất là chia sẻ tệp tin, tất cả các dạng tệp tin chia sẻ như âm thanh,

hình ảnh, dữ liệu...

Hình 4: Mô hình mạng ngang hàng P2P

Một mạng ngang hàng đúng nghĩa không có khái niệm Client và Server hay nói

cách khác tất cả các máy tham gia đều bình đẳng và được gọi là Peer. Peer là một nút

mạng vừa đóng vai trò là Server với các máy khác trong mạng vừa đóng vai trò là

Client khi được các máy khác phục vụ mình. Tất các máy đều có thể yêu cầu dịch vụ,

cũng như đáp ứng yêu cầu dịch vụ của các máy khác. Mọi máy tính đều có thể lưu trữ

và chia sẻ tài nguyên, cũng như kết nối trực tiếp với nhau.

13

2.2. Ưu, nhược điểm của mạng ngang hàng

Mô hình mạng ngang hàng rất phù hợp với tính phi tập trung của Internet, bởi

bản chất của tài nguyên là phân tán, các thông tin lưu trữ không chỉ trên các máy chủ

mà ở cả các máy khách.

Xét về khía cạnh sức mạnh xử lý, mạng mạng ngang hàng có khả năng xử lý cao

hơn cả những máy chủ lớn nhất hiện nay do đó sử dụng mạng ngang hàng có thể cải

thiện đáng kể hiệu quả của các phương pháp phân tích, xử lý dữ liệu và giải các bài

toán phức tạp (đây đều là những vấn đề vượt ra ngoài tầm xử lý của những máy chủ

tập trung khi số lượng truy vấn, tính toán tăng lên đến hàng trăm triệu mỗi ngày). Sở dĩ

như vậy là vì mạng ngang hàng đã tận dụng khả năng xử lý, khả năng lưu trữ còn thừa

của các máy tính tham gia mạng với những thuật toán phân tán hợp lý. Công nghệ này

đã chia việc xử lý lớn ra thành những việc xử lý nhỏ có thể phân tán giữa các máy tính

trong một mạng. Mỗi máy tính sẽ xử lý một phần dữ liệu và trả về kết quả xử lý cho

máy tính trung tâm, máy tính trung tâm sẽ ghép nối các kết quả này lại với nhau. Bằng

cách đó, ta có thể giải quyết được những bài toán phức tạp mà không cần phải nâng

cấp khả năng xử lý của hệ thống hiện tại.

Bên cạnh đó, việc phân tán trách nhiệm cung cấp dịch vụ đến tất cả các nút trên

mạng sẽ giúp loại bỏ vấn đề ngừng trệ dịch vụ do nơi cung cấp duy nhất gặp sự cố.

Mạng ngang hàng cũng tận dụng được băng thông trên toàn bộ mạng vì việc tăng

số giao tiếp giữa các thiết bị mạng qua các đường truyền khác nhau sẽ làm giảm khả

năng tắc nghẽn mạng. Ngoài ra, khi càng nhiều máy tính tham gia vào mạng ngang

hàng thì tổng sức mạnh xử lý, khả năng lưu trữ và băng thông lại tăng theo điều đó cho

thấy khả năng mở rộng của mạng mạng ngang hàng.

Tuy nhiên, mạng ngang hàng cũng có nhiều nhược điểm. Với mô hình mạng

ngang hàng thuần túy, tức là mô hình mà ở đó mọi máy đều có vai trò như nhau và

không tuân theo bất cứ một quy luật định tuyến hay kết nối nào thì mạng mạng ngang

hàng cũng bộc lộ khá nhiều nhược điểm:

- Chính vì yêu cầu dịch vụ được đáp ứng một cách tùy biến nên máy yêu cầu dịch

vụ có thể nhận được nhiều kết quả khác nhau khi nó kết nối đến các máy khác

nhau cung cấp cùng một dịch vụ.

- Các yêu cầu gửi đi có thể không nhận được kết quả trả về vì không có gì đảm

bảo sẽ tồn tại một máy nào đó có khả năng đáp ứng yêu cầu đó.

14

- Các tài nguyên có thể biến mất do nút cung cấp tài nguyên có thể ngắt kết nối

bất cứ lúc nào.

2.3. Phân loại mạng ngang hàng

Hình 5: Các loại hình mạng ngang hàng

Theo [4], mạng ngang hàng được phân thành 2 loại: mạng có cấu trúc và mạng

không có cấu trúc.

2.3.1. Mạng ngang hàng phi cấu trúc

2.3.2.1. Mạng ngang hàng tập trung

Mạng này có đặc điểm là vẫn còn dựa trên một máy chủ tìm kiếm trung tâm, cấu

trúc Overlay của mạng được mô tả như một mạng hình sao

15

Hình 6: Mạng ngang hàng tập trung thế hệ thứ nhất (Napster)

- Nguyên tắc hoạt động:

 Mỗi client lưu trữ files định chia sẻ với các node khác trong mạng.

 Một bảng lưu trữ thông tin kết nối của người dùng đăng kí (IP address,

connection bandwidth ….).

 Một bảng liệt kê danh sách các files mà mỗi người dùng định chia sẻ (tên

file, dung lượng, thời gian tạo file …….)

 Mọi máy tính tham gia mạng được kết nối với máy chủ tìm kiếm trung tâm,

các yêu cầu tìm kiếm được gửi tới máy chủ trung tâm phân tích, nếu yêu cầu

được giải quyết máy chủ sẽ gửi trả lại địa chỉ IP của máy chứa tài nguyên

trong mạng và quá trình truyền file được thực hiện theo đúng cơ chế của

mạng ngang hàng, giữa các host với nhau mà không cần quan máy chủ trung

tâm.

- Ưu điểm:

 Dễ xây dựng.

 Tìm kiếm file nhanh và hiệu quả.

- Nhược điểm:

 Vấn đề luật pháp, bản quyền.

 Dễ bị tấn công.

 Cần quản trị (central server).

Napster là mạng ngang hàng đặc trưng cho hệ thống mạng ngang hàng tập trung,

với Napster, việc tìm kiếm file bị thất bại khi bảng tìm kiếm trên máy chủ vì lý do nào

đó không thực hiện được. Chỉ có các file truy vấn và việc lưu trữ được phân tán, vì vậy

16

máy chủ đóng vai trò là một nút cổ chai. Khả năng tính toán và lưu trữ của máy chủ

tìm kiếm phải tương xứng với số nút mạng trong hệ thống, do đó khả năng mở rộng

mạng bị hạn chế rất nhiều.

2.3.2.2. Mạng ngang hàng thuần túy

Mạng ngang hàng thuần túy là một dạng khác của thế hệ thứ nhất trong hệ thống

các mạng ngang hàng. Trong mạng ngang hàng thuần tuý thì vai trò của các máy trong

mạng là ngang nhau, không còn máy chủ tìm kiếm tập trung như trong mạng Napster,

nó khắc phục được vấn đề nút cổ chai trong mô hình tập trung. Tuy nhiên vấn đề tìm

kiếm trong mạng ngang hàng thuần túy lại sử dụng cơ chế phát tràn, yêu cầu tìm kiếm

được gửi cho tất cả các node mạng là láng giềng với nó, điều này làm tăng đáng kể lưu

lượng trong mạng. Các phần mềm tiêu biểu cho mạng ngang hàng dạng này là

Gnutella 4.0, FreeNet.

Hình 7: Mạng ngang hàng thuần túy (Gnutella 4.0, FreeNet)

- Hoạt động của Gnutella

 Khi người dùng tại 1 node muốn tìm kiếm tài nguyên, node sẽ gửi yêu cầu

đến mỗi node mà nó đang kết nối đến. Các node này khi nhận được yêu cầu

lại tiếp tục chuyển yêu cầu tới các node mà node này biết. Việc chuyển tiếp

cứ tiếp tục đến khi gói tin đạt đến số hop được đĩnh nghĩa trước bởi node

tìm kiếm ban đầu. Nếu câu truy vấn tìm được kết quả, node có kết quả sẽ

cung cấp kết quả trực tiếp đến node tìm kiếm thông qua giao thức UDP. Vì

vậy, mỗi câu truy vấn bao giờ cũng gồm thông tin về địa chỉ IP và cổng của

node khác.

 Khi 1 node ngắt kết nối, nó sẽ lưu lại danh sách các node nó đã kết nối và

các tài nguyên chia sẻ để dùng cho lần kết nối tiếp theo.

17

 Để giải quyết vấn đề thắt nút cổ chai (bottlenecks), Gnutella đã được cài đặt

thành hệ thống nhiều tầng. Thay vì tất cả các node đều có vai trò như nhau,

giờ đây, các node gia nhập vào mạng chỉ được giữ ở cạnh mạng giống như

các node lá và không chịu trách nhiệm định tuyến. Các node ultrapeers mới

có khả năng định tuyến thông điệp tìm kiếm và lưu thông điệp đó. Điều này

cho phép việc tìm kiếm trong 1 không gian mạng rộng hơn và cũng làm tăng

hiệu quả hoạt động của mạng. Do không phụ thuộc vào 1 Server duy nhất

nên Gnutella cũng khó bị đánh sập hơn so với Napster.

 Ưu điểm:

o Dễ xây dựng.

o File download query

o Đảm bảo tính phân tán hoàn toàn cho các node tham gia mạng, các

node tham gia và rời khỏi mạng một cách tùy ý mà không ảnh

hưởng đến cấu trúc của mạng.

 Nhược điểm:

o Tốn băng thông.

o Phức tạp trong tìm kiếm.

o Các node có khả năng khác nhau (CPU power, bandwidth, storage)

đều có thể phải chịu tải (load) như nhau.

2.3.2.3. Mạng ngang hàng lai ghép

Để khắc phục nhược điểm của mạng ngang hàng thuần túy, một mô hình mang

ngang hàng mới được phát triển với tên gọi là mạng ngang hàng lai. Đây được gọi là

mạng ngang hàng thế hệ 2. Trong mô hình này, mỗi máy đều được nối với tất cả các

máy khác trong mạng, cách nối này mang đặc điểm của mô hình mạng ngang hàng

thuần túy. Tuy nhiên, vẫn có một máy đóng vai trò máy chủ trung tâm, máy chủ này

có nhiệm vụ quản lý các thông tin chỉ mục.

18

Hình 8: Mạng ngang hàng lai ghép

- Trong mô hình mạng ngang hàng lai tồn tại một trật tự phân cấp bằng việc định

nghĩa các Super Peers.

- Các SupperPeer tạo thành một mạng không cấu trúc, có sự khác nhau giữa

SupperPeers và ClientPeers trong mạng, mỗi SupperPeer có nhiều kết nối đến

các ClientPeers.

- Mỗi SupperPeer chứa một danh sách các file được cung cấp bởi các ClientPeer

và địa chỉ IP của chúng vì vậy nó có thể trả lời ngay lập tức các yêu cầu truy

vấn từ các ClientPeer gửi tới.

 Ưu điểm:

o Hạn chế việc Flooding các query, làm giảm lưu lượng trong mạng,

nhưng vẫn tránh được hiện tượng nút cổ chai (do có nhiều

SuperPeers).

o Khắc phục được nhược điểm về sự khác nhau về CPU power,

bandwidth … ở mạng ngang hàng thuần túy, các SuperPeer sẽ chịu

tải chính, các node khác chịu tải nhẹ.

 Những nhược điểm của việc quản lý điều khiển tập trung vẫn tồn tại trong

mô hình mạng này. Nếu máy chủ trung tâm gặp lỗi thì các máy Peer không

thể truy cập đến thông tin chỉ mục ở trên máy chủ trung tâm nên không thể

tìm kiếm thông tin được. Đại diện cho mô hình mạng ngang hàng lai ghép là

mạng ngang hàng Napster.

19

2.3.2. Mạng ngang hàng có cấu trúc

Mô hình mạng P2P mà trong đó, các node được tổ chức lại theo 1 cấu trúc nhất

định và việc định tuyến thông báo sẽ dựa trên cấu trúc đó, được gọi là mô hình mạng

ngang hàng có cấu trúc.

Mạng P2P thuần túy hoạt động không hiệu quả do các node tham gia mạng

không tuân theo 1 quy luật nào, các kết nối xảy ra ngẫu nhiên, thông báo được gửi kiểu

phát tràn, …Mạng ngang hàng có cấu trúc dựa trên DHT khắc phục nhược điểm của

mạng không cấu trúc bằng cách sử dụng hệ thống bảng băm phân tán. Hệ thống này

định nghĩa liên kết giữa các nút mạng trong mạng phủ theo một thuật toán cụ thể, đồng

thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với phần dữ liệu nào

được chia sẻ trong mạng. Với cấu trúc này, khi một máy cần tìm một dữ liệu, nó chỉ

cần áp dụng một giao thức chung để xác định nút mạng nào chịu trách nhiệm về dữ

liệu đó và liên lạc trực tiếp đến nút mạng đó để lấy kết quả.

Mạng P2P có cấu trúc sử dụng một giao thức đảm bảo tính toàn cục để chắc chắn

rằng mọi peer tham gia mạng đều có thể định tuyến truy vấn tới các peer khác chứa dữ

liệu mong muốn, ngay cả khi dữ liệu đó không phổ biến. Sự đảm bảo này yêu cầu một

mạng phủ (overlay) được liên kết theo một cấu trúc nhất định. Hầu hết những mạng

P2P có cấu trúc hiện này đều thuộc kiểu DHT, với kiểu này một kỹ thuật băm phù hợp

được sử dụng để gán quyền quản lý dữ liệu cho những peer tham gia cụ thể, cũng như

bảng băm truyền thống, mỗi khóa sẽ được gán cho những ô cụ thể. Một số mạng

based-DHT phổ biến có thể kể là: Chord, Pastry, CAN,….

Bảng băm là một cặp (khóa, giá trị). Mỗi một node khi tham gia vào mạng có thể

dễ dàng tìm thấy giá trị mong muốn dựa vào khóa của giá trị đó. Việc hình thành khóa

và gắn các khóa đó với giá trị tương ứng được thực hiện trực tiếp tại các node trong

mạng, chính vì vậy khả năng sập mạng được giảm tối thiểu khi các node tham gia hoặc

dời bỏ mạng. Chính lý do này khiến khả năng mở rộng của mạng DHT là cực lớn, quá

trình kiểm soát việc tham gia, dời bỏ mạng của các node trở lên dễ dàng hơn.

20

Hình 9: Mạng ngang hàng có cấu trúc

Dựa trên cấu trúc bảng băm phân tán đã có nhiều nghiên cứu và đề xuất ra các

mô hình mạng ngang hàng có cấu trúc, điển hình là cấu trúc dạng vòng (như trong

hình vẽ mô tả): Chord, Pastry…, và cấu trúc không gian đa chiều: CAN, Viceroy.

Với cấu trúc vững mạnh, DHT được sử dụng như một giao thức nền để xây dựng

nhiều ứng dụng phức tạp như: Hệ thống các file phân tán, hệ thống chia sẻ file ngang

hàng, hệ thống nội dung phân tán, tin nhắn tức thời, Multicast… Các mạng DHT nổi

tiếng thường được nhắc đến là: Bittorrent, eDonkey, …

Các nghiên cứu về DHT được bắt nguồn cùng với sự phát triển của các hệ thống

P2P như Napster, Gnutella, và Freenet, những hệ thống này sử dụng lợi thế của các tài

nguyên phân tán trên mạng Internet để cung cấp một ứng dụng chia sẻ thông tin hữu

dụng. Cụ thể, chúng đã sử dụng lợi thế tăng băng thông và sức chứa của ổ cứng còn

nhàn rỗi của các Peer để cung cấp dịch vụ chia sẻ file và các hệ thống này khác nhau

chủ yếu ở cách thức thực hiện việc tìm kiếm dữ liệu mà các peer quản lý.

DHT sử dụng cơ chế định tuyến dựa trên khóa trên 1 kiến trúc mạng chặt chẽ

hơn để có thể đạt được cả tính phân tán về tài nguyên của Gnutella và Freenet, tính

hiệu quả về truy vấn của Napster. Có một hạn chế là DHT chỉ hỗ trợ tìm kiếm chính

xác, không hỗ trợ tìm kiếm theo từ khóa, hay tìm kiếm theo khoảng,… tuy nhiên các

chức năng này có thể triển khai mở rộng trên nền DHT.

21

2.3.2.1. Mạng ngang hàng có cấu trúc dựa trên DHT (Distributed Hash Table)

Bảng băm phân tán (Distributed hash tables) là một giải thuật cung cấp dịch vụ

tìm kiếm tương tự cấu trúc dữ liệu bảng băm (Hash table): Một cặp {khóa, giá trị}

được lưu trữ vào trong bảng băm phân tán, và bất kỳ node tham gia nào cũng có thể

đưa ra một khóa và dễ dàng truy vấn lấy giá trị tương ứng. Việc hình thành khóa và

gắn các khóa đó với giá trị tương ứng được thực hiện trực tiếp tại các node trong

mạng, nên khi thay đổi số node tham gia không ảnh hưởng đáng kể đến hoạt động của

hệ thống. Điều này cho phép bảng băm phân tán có khả năng mở rộng ra một số lượng

rất lớn các node tham gia mà vẫn quản lý được sự ra vào liên tục của các node, cũng

như sự gián đoạn của một số node.

Mỗi bảng băm phân tán đều cần có một không gian địa chỉ. Mỗi khóa sẽ lấy một

giá trị từ không gian này. Kích thước không gian địa chỉ thường gặp nhất là 2160 (mỗi

khóa là một số nhị phân 160 bit).

Các node và dữ liệu sẽ được ánh xạ vào cùng một không gian địa chỉ sử dụng

hàm băm SHA-1. Với mỗi node, hàm băm sẽ băm địa chỉ IP của node đó để thu được

một khóa 160 bit, gọi là định danh node (node identifier hay nodeID). Định danh node

được sử dụng để xác định vị trí của node trong bảng băm. Như vậy mỗi node sẽ có một

địa chỉ duy nhất, và do không gian khóa là rất lớn nên cũng có thể xem là mỗi địa chỉ

tương ứng với một node duy nhất. Đối với dữ liệu, mỗi file dữ liệu cũng được gắn với

một định danh. Định danh của dữ liệu được băm từ tên file dữ liệu hoặc băm từ nội

dung của file, là giá trị duy nhất trong không gian địa chỉ.

Mỗi node sẽ quản lý một khoảng giá trị nhất định trong không gian địa chỉ. Dữ

liệu được lưu ở node và được quản lý thông qua định danh. Khi một node muốn tìm

kiếm một dữ liệu trong bảng băm phân tán, nó sẽ gửi truy vấn lần lượt qua các node

khác. Nội dung truy vấn chính là định danh của dữ liệu. Khi một node lưu trữ dữ liệu

có định danh trên nhận được truy vấn thì nó sẽ trả về dữ liệu yêu cầu.

Như vậy, việc tìm kiếm dữ liệu trong bảng băm phân tán sẽ luôn thực hiện được.

Tuy nhiên vấn đề đặt ra là khi số lượng node tham gia lớn thì việc tìm kiếm sẽ diễn ra

như thế nào để đảm bảo tính hiệu quả về mặt thời gian và tính ổn định khi liên tục có

các node gia nhập và rời khỏi bảng băm.

22

Các tính chất của mạng DHT

DHT nhấn mạnh vào các thuộc tính sau:

- Phân tán (Decentralization): các node tham gia cấu thành hệ thống không có

thành phần trung tâm làm điều phối mạng.

- Khả năng mở rộng: hệ thống vẫn có thể hoạt động hiệu quả với hàng nghìn hoặc

hàng triệu node.

- Khả năng chịu lỗi: hệ thống vẫn có thể làm việc ổn định ngay cả khi có các sự

kiện node tham gia, rời bỏ mạng hay lỗi diễn ra.

Kỹ thuật khóa được sử dụng để đạt được mục đích là mỗi node chỉ cần liên kết

với một số ít các node khác trong hệ thống, thường là O(logn) với n là số node tham

gia. Vì vậy sự thay đổi trong các thành viên chỉ ảnh hưởng đến một phần nhỏ của hệ

thống.

Cuối cùng, DHT phải giải quyết những vấn đề cơ bản của các hệ thống phân tán

đó là cân bằng tải, tính toàn vẹn dữ liệu, hiệu năng (cụ thể là đảm bảo các hoạt động

như định tuyến, lưu trữ, truy vấn phải được thực thi nhanh chóng).

Mạng Overlay

Mỗi node duy trì một tập các liên kết với các node khác (hàng xóm của nó hoặc

có thể gọi là bảng định tuyến). Các liên kết này sẽ tạo ra một mạng overlay. Một node

kết nạp các node khác vào làm hàng xóm của nó dựa trên một cấu trúc nào đó, gọi là

network topology.

Tất cả DHT topology đều có chung một thuộc tính quan trọng là: với một khóa k

bất kỳ, node có chứa khóa k hoặc có liên kết tới node khác gần hơn với khóa k theo

khoảng cách trong không gian khóa được định nghĩa ở trên, thì đều có thể định tuyến

được thông điệp tới node quản lý khóa k sử dụng thuật toán tham lam: ở mỗi bước,

chuyển thông điệp tới hàng xóm mà ID của nó gần nhất với khóa k. Khi không có

hàng xóm nào như thế, thì chúng ta đã đến đúng node là node quản lý khóa k. Kiểu

định tuyến này đôi khi được gọi là định tuyến dựa trên khóa (key based routing).

Ngoài tính chính xác trong định tuyến, có hai yếu tố quan trọng trong một

topology là số lượng hops tối đa trên đường đi thấp để các yêu cầu kết thúc nhanh; và

số lượng hàng xóm tối đa thấp để việc duy trì không quá khó khăn. Lựa chọn thứ ba là

lựa chọn phổ biến. Nhiều DHT sử dụng tính linh hoạt trong cách chọn hàng xóm để

23

chọn ra những hàng xóm gần nhau về mặt độ trễ giữa các node của mạng vật lý ở phía

dưới.

2.3.2.2. Mạng ngang hàng có cấu trúc Chord

Theo một đánh giá tổng hợp về các thuật toán định tuyến dựa trên DHT trong các

kiến trúc mạng khác nhau như hình tròn (ring, với giao thức Chord), hình cây (tree),

hình hộp (hypercube, với giao thức CAN), …xét về sự linh hoạt trong việc định tuyến,

khả năng phục hồi trạng thái cũng như khả năng chịu lỗi, kiến trúc ring đều được đánh

giá cáo. Vì vậy, kiến trúc Chord thường hay được sử dụng như là mạng phủ để thực

hiện các cài đặt trên P2P có cấu trúc.

Giới thiệu giao thức Chord

Có thể nói Chord là đại diện tiêu biểu nhất của hệ thống mạng ngang hàng có cấu

trúc DHT. Không những vậy Chord còn là nền tảng cho những nghiên cứu phát triển

ứng dụng sau này. Một số nghiên cứu đã chỉ ra rằng: Chord không chỉ là một mạng

DHT đơn thuần mà còn mang nhiều ưu điểm khác mà một số mạng DHT không có.

Nói tới Chord ta có thể nhắc tới những đặc điểm sau đây:

- Cân bằng tải (Load Balance ): Quá trình hình thành và phân bổ khóa của Chord

dựa trên thuật toán Consistent Hashing. Chính những đặc điểm của thuật toán

này đã tạo cho Chord một khả năng cân bằng tải một cách tự nhiên ngay khi

mạng được khởi tạo.

- Sự phân quyền: Trong giao thức Chord, không node nào quan trọng hơn node

nào, quyền hạn này được thực hiện rất hiệu quả trong giao thức Chord.

- Khả năng mở rộng: Quá trình hình thành mạng, tìm kiếm dữ liệu trong Chord

phụ thuộc nhiều vào sự biến thiên của hàm số logarit. Chính điều này tạo cho

Chord khả năng mở rộng với số lượng rất lớn các node, cải thiện hiệu suất tìm

kiếm một các tối đa.

- Tính sẵn sàng: Mỗi node trong Chord tự động điều chỉnh bảng thông tin định

tuyến (Finger Table) của chính nó khi có một node tham gia hoặc dời mạng.

Nói cách khác trong mạng Chord quá trình duy trì sự tồn tại của mạng diễn ra

hoàn toàn tự động, chính điều này đã giảm thiểu khả năng đổ vỡ xuống mức tối

thiểu khi quá trình tham gia và dời bỏ mạng của các node diễn ra.

24

Mô hình mạng Chord

Chord [3] được mô tả dưới dạng một vòng tròn và không gian định danh phân bố

đều trên vòng tròn tăng dần theo chiều kim đồng hồ. Nếu gọi N là số bit định danh của

không gian khóa thì mạng Chord có thế chứa tối đa 2N node. Mỗi node trên Chord có

một định danh id và có khả năng duy trì liên kết 2 chiều với các node đứng liền trước

và liền sau nó theo chiều kim đồng hồ, tạo thành 1 mạch kiên kết vòng. Node liền

trước được gọi là Successor(id), và node liền sau được gọi là Predecessor(id). Thêm

vào đó, mỗi node sẽ lưu một bảng định tuyến gọi là Finger Table, cho phép node đó

định tuyến tới các node ở xa. Mỗi dòng trong bảng Finger Table sẽ lưu thông tin về 1

node ở xa, gọi là 1 entry. Không gian định danh có bao nhiêu bit thì Finger Table có

bấy nhiêu entry.

Để hình thành được một mạng Chord hoàn chỉnh không thể không nói tới 2 yếu

tố được coi như cốt lõi của mạng Chord: Consistent Hashing và Finger Table.

Consitent Hasing đóng vai trò quan trong trong việc hình thành ID của các node, khóa

dữ liệu và phân phối khóa vào các node tương ứng. Trong khi đó Finger Table đóng

vai trò chuyển tiếp giữa các node trong mạng, phục vụ cho quá trình tìm kiếm được

diễn ra một cách nhanh chóng và hiệu quả.

Consistent Hashing

Consistent Hasing là thuật toán cơ bản mà Chord sử dụng, Consistent Hashing sử

dụng m bit làm độ lớn cho việc cung cấp ID và khóa của các node. ID của node được

cung cấp bằng nhiều cách khác nhau( băm địa chỉ IP của node, chọn một cách tự động

từ không gian ID có sẵn…). Việc tạo khóa cũng tương tự. Khóa được tạo ra bằng cách

băm tên của dữ liệu, tính tần suất xuất hiện của từ trong văn bản…. Độ dài của khóa m

phải đủ lớn để đảm bảo khả năng trùng giữa 2 nodes hoặc khóa là thấp.

Consistent Hashing phân phát khóa vào node như sau: Các ID được xắp xếp trên

một vòng tròn module 2m. Khóa K được gắn vào node đầu tiên mà ID của nó bằng

hoặc lớn hơn giá trị của K. Node đó được gọi là Successor của khóa K - Successor(k).

Nếu tưởng tượng các ID hình thành lên một vòng tròn có giá trị từ 0 tới 2m - 1thì

Successor(k) là node đầu tiên quay theo chiều kim đồng hồ tính từ K. Ta gọi vòng tròn

ID của các node là vòng Chord.

Consistent Hashing được xây dựng với mục đích giảm thiểu tác động tới cấu trúc

mạng khi các node tham gia hoặc dời bỏ mạng. Để duy trì sự sắp xếp giữa các node và