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

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à 25 khóa, khi node N dời khỏi mạng thì toàn bộ khóa của N sẽ được chuyển lên cho Successor. Khi node N tham gia vào mạng N sẽ lấy key từ Successor của nó mà key đó có giá trị nhỏ hơn N(theo không gian khóa). Ngoài ra không có sự thay đổi nào khác xảy ra trong sự sắp xếp giữa các node và khóa của chúng. Finger Table Để đảm bảo quá trình tìm kiếm diễn ra hiệu quả, Chord lưu trữ thông tin định tuyến giữa các node trong một bảng được gọi là Finger Table. Gọi m là số bit của độ dài khóa, ID của node, mỗi node cần lưu trữ thông tin tối đa m node khác trong bảng Finger Table của mình, giá trị tương ứng của mỗi node trong bảng Finger Table bao gồm: ID, IP, số hiệu cổng.... Gọi i là đối tượng thứ i trong bảng Finger Table của node N, i được thể hiện bằng: N.Finger[i]. Node đầu tiên trong bảng Finger Table của N chính là Successor của N, hay còn được gọi là Immediate Successor. Ký hiệu Định Nghĩa Finger[k] Node đầu tiên trên vòng Chord tiếp nối (n+ 2k-1)mode 2m, 1≤ k ≤ m .interval (finger[k].start, finger[k+1].start) .node First node>= n.finger[k].start Successor Node tiếp theo trên vòng tròn Chord; Finger[1].Node Predecessor Node ở trước trên vòng tròn Chord. Bảng 10: Bảng định nghĩa các trường trong Finger Table Trong đó giá trị của trường node tại dòng i của bảng được coi như là finger thứ i của node n. Thông tin lưu trong bảng cũng bao gồm cả IP và Port của các node tương ứng. Node đầu tiên trong bảng Finger Table của n chính là Successor của n, hay còn được gọi là Immediate Successor. Từ bảng Finger Table ở trên ta có thể thấy rằng: - Mỗi node chỉ cần lưu trữ thông tin của một số node nhất định trong bảng định tuyến của mình. - Node biết thông tin về các node gần nó nhiều hơn là các node ở xa. - Bằng cách định tuyến thông qua bảng Finger Table, một node n có thể xác định được vị trí của bất kỳ khóa nào trên mạng. Ánh xạ khóa vào một node trong Chord Chord ánh xạ các khóa vào các node, thường theo cặp (key, value). Một value có thể là 1 address, 1 văn bản, hoặc 1 mục dữ liệu. Chord có thể thực hiện chức năng này bằng cách lưu các cặp (key, value) ở các node mà key được ánh xạ. Một node sẽ chịu 26 trách nhiệm lưu giữ một khóa k nếu node đó là node có định danh id nhỏ nhất thỏa mãn điều kiện id >= k. Một node khi lưu giữ khóa k cũng sẽ được gọi là Successor (k) Hình 11: Lưu giữ key trong mạng Chord Tìm kiếm trong mạng Chord Trong vòng Chord, mỗi node chỉ cần liên hệ được với Successor hiện tại của nó. Quá trình tìm kiếm khóa diễn ra khá đơn giản. Tại node xác định, nơi truy vấn tìm kiếm bắt đầu, node đó sẽ chuyển truy vấn đó tới Successor của nó. Successor này sẽ xử lý, tìm kiếm từ khóa trong thư viện khóa của nó, nếu khóa đó tồn tại thì Successor sẽ trả lại kết quả cho node yêu cầu truy vấn. Ngược lại nó sẽ chuyển tiếp truy vấn tới Successor tiếp theo. Cứ như vậy, sau một số bước nhất định truy vấn sẽ có thể tìm được dữ liệu mong muốn. Thuật toán như đã nêu ở phần trên thực chất chỉ là quá trình chuyển tiếp truy vấn giữa các node và Successor của nó. Như vậy để có thể tìm được vị trí chính xác của khóa đôi khi sẽ phải mất rất nhiều bước. Nếu khóa truy vấn càng ở xa thì số truy vấn càng lớn, nếu thực hiện nhiều truy vấn một lúc sẽ gây ra quá tải trong mạng. Để giải quyết vấn đề trên, Chord đưa ra khái niệm Finger Table, mỗi node khi thực hiện quá trình tìm kiếm sẽ thực hiện so sánh giá trị của khóa với giá trị ID của các node. 27 Hình 12: Tìm kiếm khóa sử dụng bảng FingerTable Ví dụ: Tại hình trên, khi node số 8 khởi tạo tìm kiếm khóa 54, nó sẽ tìm trong bảng Finger Table và thấy giá trị của node số 42 gần với giá trị 54 nhất. Vì vậy truy vấn sẽ được chuyển trực tiếp tới node 42, node 42 sẽ so sánh trong finger table của mình và chuyển tiếp truy vấn tới node 51, node 51 sẽ chuyển truy vấn tới node 56 nơi chứa khóa 54. Tham gia và ổn định mạng Để đảm bảo quá trình tìm kiếm đạt hiệu quả trong khi các node tham gia và dời khởi mạng thì mỗi node trong Chord phải cập nhật được thông tin trong bảng định tuyến của mình, mỗi node sau một khoảng thời gian nhất định sẽ thực hiện quá trình ping tới successor của nó để biết là successor đó tồn tại hay đã dời khỏi mạng. Để có thể xác định được vị trí của các khóa trong mạng, Chord cần thỏa mãn 2 điểm sau: - Mỗi successor của 1 node phải được duy trì. - Với mỗi khóa k, node successor(k) có trách nhiệm quản lý k. Khi tham gia vào một mạng Chord, một node n cần chọn cho nó một định danh id và báo cho các node bên cạnh biết sự tham gia của nó. Các node Successor và Predecessor sẽ cần phải cập nhật thông tin về node mới tham gia vào mạng. Node n cũng khởi tạo bảng định tuyến Finger Table. Để mạng vẫn định tuyến đúng sau khi có sự tham gia của node n, các node cần thường xuyên chạy thuật toán ổn định mạng để 28 cập nhật thông tin về node bên cạnh (hay node láng giềng). Một số node có lưu thông tin về n trong bảng Finger Table thì cần cập nhật các entry liên quan trong Finger Table. Cuối cùng, node Successor của n sẽ chuyển một phần khóa k mà bây giờ n là Successor(k) cho n lưu giữ. Việc chuyển khóa sẽ do tầng trên của ứng dụng thực hiện. Khi một node chuẩn bị rời khỏi mạng, nó cần thông báo cho các node bên cạnh biết để ổn định lại mạng. Node đó cũng sẽ chuyển các khóa nó lưu giữ cho node Successor của nó. 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 Hệ thống thông báo sự kiện đòi hỏi phải cung cấp sự kiện yêu cầu một cách chính xác và kịp thời trong khi mạng ngang hàng có cấu trúc có các đặc điểm hoàn toàn có thể để đáp ứng được các yêu cầu này của hệ thống - Mạng ngang hàng có cấu trúc sử dụng bảng băm phân tán DHT đị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ể để chắc chắn rằng mọi node tham gia vào mạng đều có thể định tuyến truy vấn tới các node khác chứa dữ liệu mong muốn ngay cả khi dữ liệu đó không phổ biến, đồng thời xác định chặt chẽ mỗi node mạng sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ trong mạng. Với cấu trúc này, khi một máy cần tìm 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 cho dữ liệu đó và sau đó liên lạc trực tiếp đến nút mạng đó để lấy kết quả. - Trong mạng ngang hàng có cấu trúc, tài nguyên được phân bố một cách hợp lý để không có một máy tính nào lưu giữ quá nhiều dữ liệu dẫn đến quá tải thông tin định tuyến. Do mạng là có cấu trúc nên các thông điệp chuyển đi giữa các máy tính để duy trì mạng ngang hàng được giảm xuống mức tối thiểu. Băng thông của mạng được dành nhiều hơn cho việc chia sẻ tài nguyên. - Việc tìm kiếm thông tin trong mạng ngang hàng có cấu trúc cũng nhanh hơn trong mạng không cấu trúc. Nếu như mạng không có cấu trúc các máy tính gửi thông điệp quảng bá để tìm kiếm thông tin thì trong mạng có cấu trúc một máy tính chỉ cần gửi thông điệp tìm kiếm qua một số máy tính. Giao thức tìm kiếm chung trong mạng sẽ đảm bảo thông tin được tìm kiếm chính xác. Đây là một lợi thế rất quan trọng khi áp dụng mạng ngang hàng có cấu trúc để truyền tin 29 2.5. Kết luận Trong chương đã giới thiệu tổng quan về mạng ngang hàng, các ưu nhược điểm của mạng ngang hàng và phân loại mạng ngang hàng. Mang ngang hàng được chia thành hai loại là mạng ngang hàng không có cấu trúc và mạng ngang hàng có cấu trúc Mạng ngang hàng Gnutella là đại diện cho mạng ngang hàng không có cấu trúc và nhược điểm của mô hình mạng này là không đảm bảo chắc chắn tìm kiếm được dữ liệu có tồn tại trên mạng do sử dụng cơ chế tìm kiếm phát tràn thông điệp. Do mạng ngang hàng không có cấu trúc sử dụng cơ chế tìm kiếm phát tràn nên làm tốn băng thông mạng đồng thời giảm hiệu quả tìm kiếm. Mạng ngang hàng có cấu trúc đã khắc phục được những nhược điểm của mạng ngang hàng không có cấu trúc. Các nút trong mạng ngang hàng có cấu trúc được liên kết với nhau theo một quy luật, mỗi nút sẽ quản lý một phần dữ liệu chia sẻ trên mạng và các dữ liệu chia sẻ này sẽ có mối liên hệ với nút quản lý. Ở trong mô hình mạng ngang hàng có cấu trúc thì ta tìm hiểu chi tiết cách thức hoạt động của mạng ngang hàng Chord. Chương này còn đưa ra lý do luận văn sử dụng mạng ngang hàng có cấu trúc để xây dựng dịch vụ thông báo sự kiện Qua tìm hiểu về lịch sử phát triển của mạng ngang hàng, ưu nhược điểm của mạng ngang hàng thì ta thấy mạng ngang hàng là một công nghệ mạnh và sẽ phát triển trong tương lai. Việc triển khai các ứng dụng trên mạng ngang hàng sẽ có thể tận dụng được rất nhiều ưu điểm của mạng này như tận dưng được khả năng xử lý, lưu trữ, băng thông của mạng và hệ thống có khả năng mở rộng cao. Chương tiếp theo luận văn sẽ trình bày mục đích, yêu cầu và hoạt động của hệ thống, trình bày cấu trúc và chi tiết giải pháp 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 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 3.1. Mục đích và yêu cầu của hệ thống Cho phép người sử dụng đăng ký yêu cầu sự kiện, hệ thống sẽ lưu yêu cầu này trên một note của mạng. Khi có một thông tin sự kiện được cung cấp, hệ thống sẽ tìm kiếm các yêu cầu cho thông tin sự kiện này trên mạng chord và gửi đến node mạng có yêu cầu. Ví dụ như một người dùng muốn cung cấp sự kiện bóng đá thì hệ thống sẽ tự động tìm tất cả các thông tin đã được cung cấp về Bóng đá như: Giải đấu, trận đấu, tỉ số của trận đấu,…và gửi thông báo đến người dùng yêu cầu. Yêu cầu của dịch vụ thông báo sự kiện được chia thành hai loại là yêu cầu của người dùng và yêu cầu của hệ thống: - Yêu cầu của người dùng:  Hệ thống gửi thông báo sự kiện đúng, chính xác, thức thời  Thời gian gửi yêu cầu và thông báo nhanh  Sử dụng dễ dàng.  Có thể cung cấp được dịch vụ và yêu cầu dịch vụ  Một số yêu cầu phụ như hệ thống có giao diện đẹp, hoạt động ổn định, tốn ít khả năng xử lý và lưu trữ của thiết bị. - Yêu cầu của hệ thống:  Cung cấp sự kiện đúng, chính xác, thức thời.  Có thể quản lý, lưu trữ và tìm kiếm thông tin trên quy mô lớn.  Có thể cung cấp dịch vụ cho số lượng lớn người dùng tại một thời điểm.  Hệ thống có thể dễ dàng mở rộng như nâng cấp hệ thống, tăng số lượng các máy phục vụ.  Có thể kháng lỗi tốt và đảm bảo tìm kiếm được thông tin dù mạng bị lỗi. 31 3.2. Giải pháp thực hiện Mạng hàng hàng có cấu trúc có ưu điểm là 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 để có thể tìm kiếm sự kiện chính xác phù hợp với yêu cầu của người dùng. Có khả năng truyền thông báo hiệu quả, thời gian tìm kiếm dữ liệu nhanh hơn, thông tin tìm kiếm chính xác và độ tin cậy cao. Một cách tiếp cận mới trong kỹ thuật thông báo sự kiện là dùng bảng băm phân tán (DHT) để xây dựng cấu trúc lớp phủ trên đỉnh của mạng P2P, lớp phủ này cung cấp phương pháp hiệu quả để định tuyến các truy vấn đến các node tương ứng, xác định dựa trên hàm băm. Mục tiêu là các node lưu trữ một yêu cầu và nhận được một sự kiện thỏa mãn hoặc là giống nhau, hoặc là gần giống nhau. Dịch vụ thông báo sự kiện có thể thực hiện một xử lý chọn lọc để xác định những thông báo nào được đưa ra mà node yêu cầu sự kiện quan tâm, định tuyến và cung cấp thông báo đến node đó. Quá trình lựa chọn cũng được sử dụng bằng dịch vụ thông báo sự kiện để tối ưu hóa việc truyền thông bên trong mạng. Lưu trữ dữ liệu phân tán, một node đồng thời đóng vai trò là node nhận yêu cầu sự kiện và cũng là node cung cấp sự kiện nên có thể truy vấn thông tin, cập nhật thông tin nhanh. Hình 13: Mô hình luồng sự kiện 32 Dịch vụ thông báo sự kiện gồm các thành phần: Mạng lưu trữ thông tin: Mạng này đóng vai trò nền tảng hoạt động của toàn bộ hệ thống, các thông tin trong hệ thống sẽ được lưu trữ và tìm kiếm tại đây. Vì vậy, nó phải cung cấp được đầy đủ các giao thức cho hai đối tượng cung cấp dịch vụ và yêu cầu dịch vụ Sử dụng mạng ngang hàng có cấu trúc Chord: Vòng tròn Chord lưu không gian định danh ID của các node, mỗi node sẽ lưu giữ giá trị của một khoảng khóa nào đấy, mỗi khóa K được định nghĩa gồm một cặp địa chỉ IP và cổng (IP,Port) của node tương ứng, có nghĩa là mỗi cặp (khóa K, sự kiện Ev) sẽ gửi thông tin sự kiện Ev cho địa chỉ node yêu cầu sự kiện (IP, port). Yêu cầu sự kiện: Yêu cầu sự kiện có thể lựa chọn một thuộc tính chung của sự kiện, tất cả các sự kiện được cung cấp mà có thuộc tính này sẽ đều được trả lại cho người yêu cầu. Người dùng có thể chọn sự kiện có sẵn trong list ở trường Tên sự kiện, nhấn nút Yêu cầu sự kiện, sự kiện được băm thành khóa, khóa này được lưu ở một node trên mạng Chord. - Giao thức yêu cầu sự kiện được định nghĩa có cấu trúc: (Loại sự kiện-Yêu cầu sự kiện, Khóa, Nội dung sự kiện,…) - Hệ thống sẽ tạo ra khóa ứng với 1 cặp thuộc tính - giá trị của sự kiện yêu cầu rồi gửi yêu cầu sự kiện đó đến node phụ trách khóa. Node phụ trách khóa sẽ lưu lại các thông tin: o Yêu cầu sự kiện o Khóa o Địa chỉ node yêu cầu sự kiện Cung cấp sự kiện: Có chức năng quảng bá thông tin về sự kiện và đưa ra các thông báo theo cách thức trước đó được quảng bá. Người dùng chọn sự kiện có sẵn trong danh sách của trường Tên sự kiện cung cấp, nhấn nút Cung cấp, sự kiện được băm thành khóa, khóa này được lưu ở một node trên mạng Chord. 33 - Giao thức cung cấp sự kiện được định nghĩa có cấu trúc: (Loại sự kiện-Cung cấp sự kiện, Khóa, Nội dung sự kiện,…) - Hệ thống sẽ tạo ra các khóa ứng với các cặp thuộc tính - giá trị của sự kiện yêu cầu rồi gửi thông tin sự kiện đến các node phụ trách khóa, node phụ trách khóa thực hiện: o Kiểm tra cơ sở dữ liệu và lấy danh sách các node gửi yêu cầu phù hợp với thông tin sự kiện. o Kiểm tra yêu cầu sự kiện với thông tin sự kiện. - Gửi thông tin sự kiện đến node yêu cầu sự kiện Sự kiện [2]Một sự kiện trong hệ thống thông báo sự kiện được quy định như một tập hợp các cặp giá trị thuộc tính d {( attr {(attr1, v1), (attr2, v2), ..., (attrd, vd)}, trong đó d là số thuộc tính {attr1,attr2, ..., attrd} kết hợp với sự kiện. Ví dụ, thông báo sự kiện Bóng đá, mỗi node sẽ lưu thông tin về Giải đấu, Trận đấu, Kết quả trận đấu…do đó d sẽ là đại diện cho các dữ liệu thuộc tính là attr1= 'Giải đấu', attr2= 'Trận đấu', attr3= 'Kết quả trận đấu'. Trong biểu thức tổng quát, các khó khăn trong truy vấn có thể được xác định tại một thuộc tính phân biệt dạng thông thường - phân biệt của một hoặc nhiều mệnh đề điều kiện, mỗi mệnh đề là một kết hợp của các thuộc tính cơ bản. Mỗi thuộc tính cơ bản ký hiệu là (attri ? pi), là một điều kiện trên một số các thuộc tính attri với ? là toán tử lọc. Khi được sử dụng trong các tài liệu của kỹ thuật thông báo sự kiện, một toán tử lọc có thể là một toán tử so sánh (=,) hoặc một toán tử chuỗi như “trước của”, “sau của” và “chuỗi con của” nếu thuộc tính có kiểu chuỗi. Một sự kiện x thỏa mãn một truy vấn q, biểu hiện bằng x ∈ q , khi và chỉ khi x đủ các thuộc tính xác định trong ít nhất một mệnh đề điều kiện của q. 34 Hình 14: Chi tiết một số sự kiện - Tên sự kiện có thể bao gồm các sự kiện như: Bóng đá, ca nhạc, phim, …. - Khi chọn một Tên sự kiện, hệ thống sẽ hiển thị thông tin chi tiết về Sự kiện và người dùng cần chọn thêm thông tin chi tiết về sự kiện đó Lưu trữ và tìm kiếm dữ liệu: Dịch vụ thông báo sự kiện tìm kiếm thông tin bằng phương pháp tìm kiếm giá trị thuộc tính. Theo phương pháp này, mỗi nội dung thông tin sẽ được định danh bởi một tên nội dung là tập các cặp thuộc tính-giá trị mô tả nội dung thông tin. Việc sử dụng các cặp thuộc tính/giá trị đảm bảo cho khả năng biểu diễn nội dung thông tin được chính xác và dễ dàng thông qua khả năng biểu diễn ngữ nghĩa của các thuộc tính-giá trị trong tên nội dung. Ví dụ như tên miền của nội dung thông tin về sự kiện Bóng đá có thể được biểu diễn như sau: 35 (Tên sự kiện = “Bóng đá”, Giải đấu=”Bóng đá Anh”, Trận đấu=”Chelsea- Blackburn”, Kết quả giữa trận = “1-0”) trong đó các thuộc tính “Tên sự kiện”, “Giải đấu”, “Trận đấu”, “Kết quả giữa trận” đã được định nghĩa trước. Việc tìm kiếm truy vấn thông tin cũng sẽ dựa trên các cặp thuộc tính-giá trị trong đó, câu truy vấn sẽ chứa một tập các cặp thuộc tính-giá trị cần truy vấn. Kết quả tìm kiếm trả về sẽ là các nội dung thông tin với tên nội dung có chứa các cặp thuộc tính-giá trị cần truy vấn. Nội dung thông tin sẽ bao gồm các thông tin chi tiết liên quan đến sự kiện. Các node lưu trữ tên và nội dung sự kiện sẽ tạo thành một mạng ngang hàng có cấu trúc Chord. Các thông báo phân bổ thông tin và truy vấn thông tin gửi giữa các node được định tuyến theo địa chỉ là các khóa và dựa trên bảng định tuyến lưu tại mỗi node. Việc phân bổ nội dung sự kiện sẽ được thực hiện dựa trên việc ánh xạ tên nội dung vào khóa phân bổ và nội dung sự kiện sẽ được gửi đến node phụ trách khóa phân bổ. Giải pháp ánh xạ khóa là tạo khóa phân bổ chính từ mỗi cặp thuộc tính-giá trị trong tên nội dung. Do có những cặp thuộc tính-giá trị phổ biến nên để tránh tình trạng quá tải cho các node phụ trách các khóa phổ biến, các node này sẽ chỉ lưu một phần nội dung thông tin gán với khóa phổ biến, phần còn lại sẽ được lưu tại các node khác dựa trên các khóa thứ cấp. Các khóa thứ cấp là giá trị băm của hơn hai cặp thuộc tính- giá trị có trong tên nội dung được phân bổ. Node phụ trách khóa phổ biến sẽ lưu lại ánh xạ giữa các khóa phân bổ chính và khóa thứ cấp để đảm bảo các thông báo truy vấn thông tin sẽ được gửi đến tất cả các node có khả năng chứa thông tin cần tìm. Với cách lưu trữ trên có thể thấy giải pháp này có các ưu điểm như:  Với các cặp thuộc tính-giá trị không phổ biến, do số lượng nội dung thông tin gán vào mỗi cặp thuộc tính-giá trị đó không lớn nên chúng sẽ được lưu tại một node và việc truy vấn đến các cặp thuộc tính-giá trị không phổ biến sẽ chỉ cần thực hiện trên một node với mỗi truy vấn. Điều này đảm bảo cho tính hiệu quả trong việc tìm kiếm.  Với các cặp thuộc tính-giá trị phổ biến, do số lượng nội dung thông tin gán vào mỗi cặp thuộc tính-giá trị đó là lớn nên chúng sẽ được lưu tại nhiều node. Số lượng nội dung thông tin càng lớn thì số node lưu giữ thông tin càng lớn. Điều này đảm bảo cho tính cân bằng tải của hệ thống. Với câu truy vấn chứa nhiều cặp thuộc tính-giá trị phổ biến, việc truy vấn sẽ được thực hiện trên node phụ trách khóa phân bổ chính và các node phụ trách các khóa thứ cấp. 36  Việc sử dụng giao thức DHT trong việc phân bổ và tìm kiếm thông tin đảm bảo khả năng mở rộng (scalability) của hệ thống, tính hiệu quả (efficiency) trong định tuyến gói tin và khả năng chịu lỗi (fault tolerent) cho hệ thống được đề xuất. 3.3. Cấu trúc hệ thống ` Cung cấp sự kiện ` Yêu cầu sự kiện Quảng bá sự kiện Cung cấp sự kiện Đăng ký sự kiện Thông báo sự kiện `Peer ` Peer ` Peer ` Peer` Peer `Peer Hình 15: Cấu trúc của hệ thống thông báo sự kiện Hệ thống bao gồm ba thành phần chính: - Cung cấp sự kiện: Cho phép cung cấp sự kiện cho người dùng - Yêu cầu sự kiện: Cho phép đăng ký sự kiện yêu cầu, khi có sự kiện thỏa mãn yêu cầu thông báo về sự kiện sẽ được gửi đến thành phần này - Mạng ngang hàng có cấu trúc: o Dựa trên mô hình mạng Chord. o Mạng này đóng vai trò nền tảng hoạt động của toàn bộ hệ thống, các thông tin trong hệ thống sẽ được lưu trữ và tìm kiếm tại đây. o Cung cấp được các giao thức cho hai thành phần Cung cấp sự kiện và yêu cầu sự kiện [1]Các node cung cấp sự kiện sẽ quảng bá (advertise) thông tin về sự kiện và đưa ra (publish) các thông báo theo cách thức trước đó được quảng bá. Như vậy, một quảng bá biểu thị mục đích của node để đưa ra một loại thông báo đặc biệt. Chúng cũng được sử dụng để đăng ký các sự kiện yêu cầu. 37 Dịch vụ thông báo sự kiện có thể thực hiện một xử lý chọn lọc để xác định những thông báo nào được đưa ra mà node yêu cầu sự kiện quan tâm, định tuyến và cung cấp thông báo đến node đó. Quá trình lựa chọn cũng được sử dụng bằng dịch vụ thông báo sự kiện để tối ưu hóa việc truyền thông bên trong mạng. 3.4. Hoạt động của hệ thống Hệ thống bao gồm ba thành phần chính: giao diện người cung cấp sự kiện, giao diện người yêu cầu sự kiện và mạng ngang hàng có cấu trúc. Mạng ngang hàng có cấu trúc được sử dụng trong hệ thống này dựa trên mô hình mạng Chord. Mạng này đóng vai trò nền tảng hoạt động của toàn bộ hệ thống, các thông tin trong hệ thống sẽ được lưu trữ và tìm kiếm tại đây. Vì vậy, nó phải cung cấp được đầy đủ các giao thức cho hai thành phần giao diện còn lại. Nhiệm vụ của hai thành phần giao diện chỉ là thu thập thông tin của người sử dụng, mã hóa theo chuẩn của hệ thống, sau đó sử dụng các giao thức tìm kiếm và lưu trữ sẵn có trong mạng Chord để hoạt động. Tại giao diện cung cấp sự kiện, người cung cấp có thể lựa chọn các thuộc tính của sự kiện cần cung cấp, sau đó nhập thông tin về sự kiện này và gửi lên mạng. Mỗi thuộc tính trong sự kiện sẽ được hệ thống băm thành một khóa riêng và lưu trữ tại những nút khác nhau trên mạng. Việc lưu trữ này sẽ giúp quá trình tìm kiếm sự kiện dễ dàng hơn. Người yêu cầu sự kiện có thể lựa chọn một thuộc tính chung của sự kiện, tất cả các sự kiện được cung cấp mà có thuộc tính này sẽ đều được trả lại cho người yêu cầu. 38 C ác k hó a sẽ đ ư ợ c l ư u và o 1 bả ng Hình 16: Hoạt động của hệ thống thông báo sự kiện Như hình trên, sự kiện được cung cấp gồm 3 cặp thuộc tính giá trị (Type = Bóng đá), (Giải đấu = Seria A) và (Trận đấu = ACMilan-InterMilan). Mỗi cặp thuộc tính giá trị này sẽ được băm thành một khóa khác nhau. Mỗi khóa kèm với tên và thông tin sự kiện sẽ được lưu trữ tại những nút khác nhau trên mạng (tùy vào bảng DTH trong mạng Chord). Như vậy, những thuộc tính ở mức cao trên cây thuộc tính có thể có rất nhiều những sự kiện được cung cấp kèm với nó. Khi người yêu cầu cần một sự kiện nào đó. Họ sẽ lựa chọn theo những thuộc tính mà mình cần. Ví dụ ở hình trên, người yêu cầu sự kiện lựa chọn 2 cặp thuộc tính giá trị là (Type = Bóng đá) và (Giải đấu = Seria A). Trong 2 cặp thuộc tính giá trị này, chỉ có cặp thuộc tính (Giải đấu = Seria A) là được băm thành khóa. Do đây là thuộc tính nằm bên dưới trong cây thuộc tính, vì vậy tất cả những sự kiện có thuộc tính (Giải đấu = Seria A) đều sẽ có thuộc tính (Type = Bóng đá), nên chỉ cần băm thuộc tính này là đủ. Để đáp ứng được các yêu cầu sự kiện một cách đầy đủ nhất. Hệ thống sẽ tiến hành lưu trữ lại cả thông tin sự kiện và yêu cầu sự kiện trên các nút trong mạng Chord. Hai loại thông báo này được lưu trữ theo những chuẩn cố định để dễ dàng hơn trong việc tìm kiếm. 39 - Thông tin sự kiện được lưu trữ theo cấu trúc: (Khóa, các thuộc tính của sự kiện, chi tiết thông tin sự kiện). - Yêu cầu sự kiện được lưu trữ theo cấu trúc: (Khóa, thuộc tính của sự kiện, địa chỉ IP, cổng). Trong đó địa chỉ IP và cổng là của nút yêu cầu sự kiện, khi có thông tin sự kiện thỏa mãn, thông tin này sẽ được gửi về nút tương ứng dựa trên các thông số này. Quá trình cung cấp sự kiện và tìm kiếm sự kiện đều diễn ra theo cả hai chiều, bao gồm cả việc lưu trữ và tìm kiếm. Khi người sử dụng yêu cầu một sự kiện nào đó, yêu cầu này sẽ được lưu trữ lại, và mạng Chord cũng tiến hành tìm kiếm các sự kiện đã có thỏa mãn yêu cầu để trả lại cho người sử dụng. Ngược lại, khi có một sự kiện được cung cấp, ngoài việc lưu trữ lại các sự kiện này, hệ thống cũng sẽ tìm kiếm các yêu cầu đã được lưu trữ sẵn. Nếu tìm thấy yêu cầu thỏa mãn, sự kiện sẽ được gửi ngay đến người sử dụng dựa trên các thông số lưu trữ trên hệ thống. Phương pháp này sẽ làm giảm tải truyền trên mạng, giúp hệ thống hoạt động ổn định hơn. 3.5. Kết luận Chương này trình bày về mục đích, yêu cầu, phương pháp xây dựng và cấu trúc của dịch vụ thông báo sự kiện dựa trên mạng ngang hàng có cấu trúc đã đề xuất. Qua chương này ta thấy dịch vụ thông báo sự kiện dựa trên mạng ngang hàng có thể đáp ứng được các yêu cầu: thời gian phản hồi của dịch vụ nhanh và hệ thống có thể dễ dàng mở rộng. Trong chương tiếp theo chúng ta sẽ thử nghiệm và đánh giá về hiệu quả của hệ thống. 40 CHƯƠNG 4. THỰC THI VÀ ĐÁNH GIÁ CHƯƠNG TRÌNH 4.1. Triển khai hệ thống Hình 17: Mô hình thử nghiệm - Thực hiện triển khai hệ thống trên 6 node có cấu hình mạng:  Peer 1: Địa chỉ IP là 169.254.80.1  Peer 2: Địa chỉ IP là 169.254.80.2  Peer 3: Địa chỉ IP là 169.254.80.3  Peer 4: Địa chỉ IP là 169.254.80.4  Peer 5: Địa chỉ IP là 169.254.80.5  Peer 6: Địa chỉ IP là 169.254.80.6 41 - Tiến hành cung cấp sự kiện lên mạng Hình 18: Giao diện chức năng cung cấp sự kiện - Thực hiện yêu cầu sự kiện Hình 19: Giao diện chức năng yêu cầu sự kiện 42 - Hệ thống hiển thị thông báo đến node đã yêu cầu sự kiện Hình 20: Giao diện thông báo sự kiện - Thử nghiệm tăng số yêu cầu sự kiện đến hệ thống  Tiến hành thử nghiệm với số yêu cầu đến hệ thống lần lượt là: 1 yêu cầu, 2 yêu cầu, 4 yêu cầu, 6 yêu cầu - Chương trình sẽ lưu lại thời gian tại các thời điểm sau: Trường hợp 1: Thực hiện yêu cầu sự kiện cho các sự kiện đã được cung cấp trên mạng - Thời điểm t1.1: thời điểm node đầu tiên bắt đầu gửi yêu cầu sự kiện. - Thời điểm t1.2: một máy trong Chord nhận được yêu cầu sự kiện và đồng thời máy tính này sẽ gửi truy vấn tìm kiếm ngay lúc này. - Thời điểm t1.3: Thời điểm máy tính trong mạng Chord nhận được sự kiện yêu cầu và gửi ngay kết quả cho node yêu cầu sự kiện. - Thời điểm t1.4: Thời điểm node yêu cầu sự kiện nhận được thông báo - Từ các mốc thời gian trên có thể tính được: - Thời gian gửi yêu cầu sự kiện=t1.2-t1.1 - Thời gian tìm kiếm sự kiện trên mạng Chord=t1.3-t1.2 - Thời gian gửi thông báo đến node yêu cầu sự kiện=t1.4-t1.3 Trường hợp 2: Cung cấp sự kiện cho yêu cầu có sẵn trên mạng 43 - Thời điểm t2.1: thời điểm 1 node bắt đầu cung cấp sự kiện lên hệ thống. - Thời điểm t2.2: thời điểm các node phụ trách khóa nhận được sự kiện cung cấp - Thời điểm t2.3 : Thời điểm tìm được yêu cầu tương ứng với sự kiện - Thời điểm t2.4 : Thời điểm node gửi yêu cầu sự kiện nhận được thông báo - Từ các mốc thời gian trên có thể tính được: - Thời gian cung cấp sự kiện = t2.2-t2.1 - Thời gian tìm kiếm sự kiện trên mạng Chord = t2.3-t2.2 - Thời gian gửi thông báo đến node yêu cầu sự kiện = t2.4-t2.3 4.1. Kết quả thử nghiệm Thực hiện 4 thử nghiệm độc lập, với số yêu cầu sự kiện (số node) lần lượt là: - Thử nghiệm thứ 1: 1 yêu cầu - Thử nghiệm thứ 2: 2 yêu cầu - Thử nghiệm thứ 3: 4 yêu cầu - Thử nghiệm thứ 4: 6 yêu cầu. Thời gian tại mỗi thời điểm sẽ thay đổi tương ứng như mô tả trong bảng dưới đây: Trường hợp 1: Thực hiện yêu cầu sự kiện cho các sự kiện đã được cung cấp trên mạng Thời gian(s) Số sự kiện 1 yêu cầu 2 yêu cầu 4 yêu cầu 6 yêu cầu Thời gian gửi yêu cầu sự kiện trung bình 0.13 0.16 0.20 0.25 Thời gian tìm kiếm sự kiện trên mạng Chord trung bình 0.23 0.26 0.30 0.33 Thời gian gửi thông báo đến 0.16 0.19 0.24 0.28 44 node yêu cầu sự kiện trung bình Bảng 21: Kết quả thử nghiệm yêu cầu sự kiện cho các sự kiện đã được cung cấp - Biểu đồ minh họa Hình 22: Đồ thị kết quả thử nghiệm yêu cầu sự kiện cho các sự kiện đã được cung cấp Trường hợp 2: Cung cấp sự kiện cho yêu cầu có sẵn trên mạng Thời gian (s) Số sự kiện cung cấp 1 sự kiện 2 sự kiện 4 sự kiện 6 sự kiện Thời gian cung cấp sự kiện trung bình 0.15 0.17 0.21 0.26 Thời gian tìm kiếm sự kiện trên mạng Chord trung bình 0.25 0.29 0.31 0.35 Thời gian gửi thông báo đến node yêu cầu sự kiện trung bình 0.18 0.19 0.25 0.29 Bảng 23: 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 - Biểu đồ minh hoạ Hình 24: Đồ 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 4.2. Nhận xét và đánh giá hệ thống Qua bảng số liệu ta thấy khi số lượng các yêu cầu càng tăng thì thời gian thực hiện của hệ thống cũng tăng theo, tức là khi số lượng yêu cầu tăng thì hệ thống sẽ bị chậm. Tuy nhiên hệ thống hoàn toàn có thể triển khai được vì khi tăng thêm 2 yêu cầu thì thời gian thực hiện của hệ thống cũng chỉ tăng lên gần 0.05s 46 CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 5.1. Kết luận Ngày nay, cùng với sự phát triển của Internet, các ứng dụng trên nó cũng đã được sử dụng rộng rãi trong mọi lĩnh vực, ở khắp mọi nơi trên thế giới. Sự mở rộng của Internet kéo theo sự cải tiến không ngừng của các mô hình mạng và P2P có cấu trúc đang là lựa chọn hàng đầu của các nhà cung cấp dịch vụ trong lĩnh vực mạng và truyền thông với nhiều nghiên cứu, nhiều giải pháp cải tiến được đưa ra. Luận văn cũng không nằm ngoài xu hướng chung đó. Từ yêu cầu của người dùng là cung cấp sự kiện chính xác, thức thời và yêu cầu của hệ thống cung cấp sự kiện phải có khả năng quản lý, lưu trữ dữ liệu phân tán, tìm kiếm thông tin nhanh trên quy mô lớn và hệ thống dễ dàng mở rộng. Khoá luậ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 trong đó sự kiện tìm kiếm dựa trên yêu cầu của người dùng. Từ tính chất và ưu điểm của mạng ngang hàng có cấu trúc thì việc lựa chọn triển khai dịch vụ yêu cầu sự kiện trên mạng ngang hàng có cấu trúc là phù hợp vì bản chất của mạng ngang hàng là quản lý, lưu trữ thông tin phân tán và ưu điểm của mạng ngang hàng có cấu trúc là có khả năng tìm kiếm nhanh, tìm kiếm dữ liệu trên quy mô lớn và hệ thống có tính mở rộng cao. Mạng ngang hàng còn có ưu điểm là có thể tận dụng được khả năng lưu trữ, xử lý và băng thông của các máy tham gia vào mạng. Luận văn đã xây dựng hệ thống cho phép tìm kiếm thông tin trên mạng ngang hàng có cấu trúc Chord. Kết quả thử nghiệm cho thấy dịch vụ thông báo sự kiện dựa trên mạng ngang hàng có cấu trúc đã xây dựng có thể đáp ứng được các yêu cầu của hệ thống dịch vụ dựa vào vị trí là có khả năng lưu trữ, xử lý thông tin phân tán, tìm kiếm thông tin nhanh và hệ thống có tính mở rộng cao. Sự kiện cung cấp theo yêu cầu từ phía người dùng. 5.2. Hướng phát triển Tuy đã có nhiều cố gắng nhưng luận văn vẫn còn gặp phải nhiều vấn đề chưa giải quyết, chính vì vậy trong thời gian sắp tới luận văn sẽ tiếp tục phát triển và hoàn thiện giải pháp hệ thống Tiếp tục thử nghiệm theo giải pháp mở rộng, đánh giá kỹ lưỡng hệ thống đã xây dựng và triển khai triển khai hệ thống trong điều kiện thực tế để tiến hành điều chỉnh các tồn tại còn mắc phải. 47 TÀI LIỆU THAM KHẢO Tiếng Anh 1. Antonio Carzaniga, David S. Rosenblum, Alexander L. Wolf. Citations “Design and Evaluation of a Wide-Area Event Notification Service”, 2001 2. Duc A. Tran and C. Pham. “Enabling Content-Based Publish/Subscribe Services in Cooperative P2P Networks. Journal on Computer Networks (COMNET), Elsevier, 54(11): 1739-1749, August 2010 3. Ion Stoicay, Robert Morrisz, David Liben-Nowellz, David R. Kargerz, M. Frans Kaashoekz, Frank Dabekz, Hari Balakrishnanz, “Chord: A Scalable Peer- to-peer Lookup Service for Internet Applications”, In Proceedings of the 2001 ACM SIGCOMM Conference, pages 149–160, 2001. 4. Ralf Steinmetz, Klaus wehrle (Edt): “Peer-to-Peer Systems and Applications” Tubingen Darmasta, 2005 5. berlin.de/diss/servlets/MCRFileNodeServlet/FUDISS_derivate_000000001083/ 03_hinze_chapter03.pdf?hosts=