Giải pháp hiệu quả đảm bảo nhất quán dữ liệu chia sẻ phân tán trên nền tảng P2P có cấu trúc

Nội dung text: Giải pháp hiệu quả đảm bảo nhất quán dữ liệu chia sẻ phân tán trên nền tảng P2P có cấu trúc

1. Các cơng trình nghiên cứu phát triển CNTT và Truyền thơng Tập V-1, Số 17 (37), tháng 6/2017 Giải pháp hiệu quả đảm bảo nhất quán dữ liệu chia sẻ phân tán trên nền tảng P2P cĩ cấu trúc An Effective Solution for The Consistency of Data Sharing and Distribution on Structured P2P Substrate Nguyễn Hồng Minh, Nguyễn Xuân Huy Abstract: There are certain difficulties in cho các ứng dụng xây dựng phía trên kiến trúc phân ensuring the consistency of data sharing and tán cĩ khả năng tự tổ chức, khả năng chịu lỗi và đảm distribution on structured P2P substrate because of bảo yêu cầu sẵn sàng cao của dữ liệu chia sẻ. the requirements of simultaneous processing Nghiên cứu trước đây tập trung đối với yêu cầu interacted by many users and peer's input/output or chia sẻ dữ liệu phân tán tĩnh, chủ yếu chỉ cĩ các thao updated speed. This paper presents a high effective tác đọc, ít cập nhật và node cĩ độ ổn định cao. Ngày solution which is proposed for structured P2P nay, yêu cầu dữ liệu chia sẻ cĩ thể được cập nhật substrate, uses the updated dissemination tree and thường xuyên hay thậm chí làm việc tương tác, đồng proposes a method using buffer and index vectors in thời bởi nhiều người dùng như P2P WiKi [7], Social order to "condition" between the requests and Networking [8], P2P collaborative workspace [9],v.v processes of updating. The experimental results Hơn nữa, giải pháp cần giải quyết những khĩ khăn do conducted on Oversim are aimed at comparing the đặc trưng của mạng P2P. efficiency of new proposed solution with that of Trong bài này, điểm chứa bản sao của dữ liệu chia Nakashima. The experimental results indicate that the sẻ được gọi là node. Khi cập nhật node, sự thay đổi new proposed is highly effective in ensuring the phải được lan truyền theo phương thức hiệu quả tới consistency (over 90%) and satisfies the requirements các node khác trong hệ thống. Đây chính là lược đồ of latency of update propagation. Especially, in case đảm bảo nhất quán và cũng là khĩ khăn, thách thức the peer’s input/output or updated speed is high, the chủ yếu trong các ứng dụng chia sẻ dữ liệu phân tán new proposed also achieve greater efficiency. [10]. Chẳng hạn, cách thức đơn giản là một node chịu Keyword: P2P structured; data consistency; trách nhiệm với khĩa (được gọi là node chính) lưu trữ replica; replica node; updated dissemination tree. thơng tin của tất cả các node chứa bản sao (gọi là node sao). Khi thực hiện cập nhật mới, node chính gửi I. GIỚI THIỆU thơng báo trực tiếp tới tất cả các node sao. Tuy nhiên, Các ứng dụng chia sẻ dữ liệu phân tán xây dựng với cách thức này thì node chính dễ trở nên quá tải, trên nền mạng phủ P2P như Gnutella [1], KazaA [2], nhất là khi số lượng node tăng nhanh, tốc độ cập nhật Freenet [3] ngày càng được quan tâm nghiên cứu và vào/ra của node cao. trong những năm gần đây. P2P gồm các điểm (peer) Các hướng nghiên cứu được chia thành 2 lớp giải liên kết logic tạo thành mạng phủ trên nền của mạng pháp như sau: vật lý, chẳng hạn như Pastry [4], Tapestry [5], CAN Một là, lớp giải pháp cho P2P khơng cĩ cấu trúc để [6], v.v Trong đĩ, điểm khơng thuần nhất về khả cập nhật cho các node sao, node sử dụng phương thức năng xử lý, tốc độ vào/ra, độ trễ truyền thơng điệp và lan truyền kém tin cậy như: ngẫu nhiên, lan rộng và băng thơng sử dụng. Hơn nữa, P2P cung cấp nền tảng - 22 -
2. Các cơng trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 làm ngập. Hướng nghiên cứu này cĩ ưu điểm thực chỉ ra rằng giải pháp mới cĩ hiệu quả cao đối với hiện đơn giản, đáp ứng yêu cầu sẵn sàng cao của dữ yêu cầu đảm bảo nhất quán (trên 90% bản sao liệu chia sẻ. Tuy nhiên, nhược điểm là chi phí truyền được cập nhật), trong khi đáp ứng được yêu cầu thơng kém hiệu quả (do sự dư thừa, trùng lặp), độ trễ về độ trễ lan truyền cập nhật. Đặc biệt, trong lớn và khả năng xẩy ra tương tranh do cập nhật dữ liệu trường hợp node cĩ tốc độ vào/ra hoặc cập nhật lớn, giải pháp mới cũng cho hiệu quả cao hơn. đồng thời. Hơn nữa, giải pháp chỉ đảm bảo nhất quán xác suất, ngẫu nhiên và nhất quán yếu. Phần cịn lại của bài báo được trình bày như sau: Phần II giới thiệu tổng quan các nghiên cứu đã đề Hai là, lớp giải pháp cho P2P cĩ cấu trúc: xây xuất; phần III mơ tả giải pháp; phần IV tiến hành thực dựng phía trên nền mạng phủ P2P cây bổ trợ lan nghiệm và so sánh kết quả; phần V trình bày kết luận truyền cập nhật (cây cập nhật). Bất kỳ node sao nào của bài báo. cũng cĩ thể cập nhật trên bản sao đang sử dụng. Tuy nhiên sự thay đổi này phải được gửi về node gốc. II. MỘT SỐ NGHIÊN CỨU LIÊN QUAN Node này chịu trách nhiệm gửi cập nhật tới các node Datta [13] sử dụng cho P2P khơng cĩ cấu trúc và sao cĩ yêu cầu nên khắc phục tình trạng dư thừa thơng kém ổn định bằng phương thức lan rộng khi cập nhật. điệp, khả năng xẩy ra tương tranh Các giải pháp xây Trong đĩ, mỗi node cĩ thơng tin của một tập các node dựng, xử lý những vấn đề về cấu trúc, thực hiện lan khác. Node đẩy (Push) bản sao cập nhật tới các node truyền cập nhật cĩ thể khác nhau và đạt được những khác mà nĩ cĩ thơng tin. Khi liên kết vào cấu trúc, kết quả như: khắc phục các nhược điểm nêu trên của node thực hiện kéo (Pull) bản sao gần nhất để sử dụng. lớp giải pháp cho P2P khơng cĩ cấu trúc, đảm bảo độ Giải pháp chỉ đảm bảo nhất quán xác suất, nhất quán tin cậy cao và yêu cầu đảm bảo nhất quán theo thiết kế yếu và tốn chi phí thơng điệp do sự trùng lặp. Wang đề ra. Tuy nhiên, cịn tồn tại những hạn chế trong xây [14] phát triển hơn khi tổ chức các node sao thành dựng cây và phương thức cập nhật, dẫn đến tình trạng chuỗi liên kết logic. Mỗi node cĩ thơng tin (định danh chưa hiệu quả về yêu cầu độ trễ, sử dụng thơng điệp, ID và địa chỉ IP) của node kề nĩ về mỗi hướng. Như mức độ nhất quán Đặc biệt cây cập nhật cĩ thể xẩy vậy, node cĩ thơng tin của node kề, gọi là các node ra tắc nghẽn làm giảm độ tin cậy, ổn định và phát sinh thăm dị. Khi cập nhật, node đẩy bản sao mới tới các nhiều chi phí. node thăm dị hiện đang online. Node thăm dị xa nhất Để vượt qua những khĩ khăn trên, chúng tơi đề của mỗi hướng nhận được bản sao lại tiếp tục gửi theo xuất giải pháp đảm bảo nhất quán dữ liệu chia sẻ theo hướng đĩ cho tới khi tất cả các node nhận được. Giải mơ hình tuyến tính [10]. Trong đĩ sử dụng cây cập pháp đã giảm được chi phí truyền thơng (70%) so với nhật d-ary, gồm các node sao của mỗi đối tượng dữ sử dụng phương thức lan rộng. liệu chia sẻ. Node sử dụng vùng đệm (buffer) lưu các Li [15] đề xuất xây dựng cây cập nhật động gồm bản sao và vectors chỉ số để quản lý cập nhật hiệu quả. các node cĩ khả năng cao (tốc độ xử lý, độ ổn định, Kết quả nghiên cứu đã cĩ những đĩng gĩp mới: băng thơng ). Các node cao chịu trách nhiệm cho tập Đề xuất giải pháp hiệu quả xử lý tốc độ vào/ra tối đa α node thấp. Node thấp cập nhật sẽ gửi tới node hoặc cập nhật của node; phân cấp hợp lý chịu cao chịu trách nhiệm để lan truyền trong cây. Node trách nhiệm cập nhật, “điều hịa” giữa yêu cầu cập cao này là node gốc của cây cập nhật, các node cao nhật và thực hiện cập nhật. Hơn nữa, chúng tơi khác được liên kết động dựa vào khoảng cách của cũng đề xuất phương pháp chống tắc nghẽn linh mạng. Shen [16] đề xuất sử dụng SWARM thực hiện hoạt, hiệu quả. nhĩm các node gần nhau và cùng chủ đề như “music”, Chúng tơi sử dụng ứng dụng Oversim [11] để thực “image”, “Book” (mỗi chủ đề cĩ thể gồm nhiều tập nghiệm giải pháp mới và giải pháp do Nakashima tin chia sẻ) thành một nhĩm và tạo một bản sao cho đề xuất [12] trên nền mạng phủ Pastry. Kết quả mỗi nhĩm. Node cĩ khả năng cao nhất sẽ được chọn là - 23 -
3. Các cơng trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 node chịu trách nhiệm (swarm server), các node khác III. GIẢI PHÁP được gọi là node phụ thuộc (client). Khi client cập III.1. Khái quát nhật, nĩ gửi đến swarm server để lan truyền trong cây Chúng tơi sử dụng mạng Pastry để làm ví dụ minh cập nhật động được tạo từ các swarm server. Trong đĩ họa cho giải pháp được đề xuất. Pastry sử dụng hàm swarm server gửi cập nhật là node gốc, các swarm băm phân tán để định danh ID duy nhất cho node và server khác được liên kết dựa vào khoảng cách. Các dữ liệu chia sẻ trong cùng khơng gian định danh 128 giải pháp sử dụng cây cập nhật động trên cĩ ưu điểm bit (tập hợp [0, -1]). ID của node i (ký hiệu ) khơng tốn chi phí duy trì cấu trúc cây, tuy nhiên cũng băm từ địa chỉ IP và ID của dữ liệu băm từ tên tập tin. cĩ khĩ khăn để xác định khoảng cách và khả năng của Các node liên kết logic tạo thành mạng phủ Pastry node trong thực tế. Vì vậy trường hợp tốc độ cập nhật (Hình 1), cĩ thể thực hiện trao đổi thơng điệp lẫn nhau của node khơng cao, giải pháp này tỏ ra cĩ hiệu quả về nhờ bảng định tuyến. Mỗi node được phân hoạch để chi phí, độ trễ và số lượng thơng điệp. Ngược lại thì chịu trách nhiệm cho một vùng khơng gian khĩa gọi là giải pháp sẽ kém hiệu quả do tốn chi phí xây dựng cây node chính của khĩa. cập nhật. Chen [17] đề xuất giải pháp SCOPE phân chia liên tiếp tất cả các node trong mạng phủ P2P cĩ cấu trúc dựa vào khơng gian định danh thành các phân vùng bằng nhau. Node chịu trách nhiệm đối với khĩa trong khơng gian định danh ban đầu là node gốc. Mỗi phân vùng cĩ node đại diện lưu thơng tin vị trí các node. Chỉ node lá mới thực sự chứa các bản sao. Yêu cầu/hủy cập nhật gửi từ node lá tới node gốc thơng qua các node đại diện. Node gốc gửi cập nhật trực tiếp Điểm(Điểm khơng cĩ bản sao) tới node lá sau khi xác định được yêu câu thơng qua Node (Điểm cĩ bản sao) các node đại diện. Giải pháp này giảm được chi phí Hình 1. Phân tán dữ liệu chia sẻ trong mạngPastry truyền thơng, tránh tương tranh cập nhật. Tuy nhiên, do node khơng chứa bản sao cũng tham gia vào cây III.2. Xây dựng cấu trúc cây cập nhật cập nhật, nên số lượng node của cây sẽ rất lớn và node Mỗi đối tượng dữ liệu chia sẻ f, giải pháp đề xuất phải tham gia vào nhiều cây khác nhau. Điều này dễ xây dựng cây cập nhật tĩnh d-ary (mỗi node cĩ tối đa d dẫn đến quá tải, tăng chi phí xây dựng, duy trì cấu node con) gồm các node chứa bản sao của f. Trong đĩ, trúc; tăng độ trễ lan truyền cập nhật. Nakashima [12] node chính là node gốc của cây cập nhật (ký hiệu R). đề xuất sử dụng cây cập nhật chỉ gồm các node sao. Mỗi node cĩ các biến cục bộ Child, Count lần lượt là Các node liên kết vào cấu trúc theo thứ tự thời gian tập các node con và số lượng node ở phía dưới, tính cả đến. Node gốc chỉ nhận được bản cập nhật mới khi tất chính nĩ. cả các node sao đã nhận được bản sao trước đĩ. Do Khi một node P cĩ yêu cầu dữ liệu chia sẻ f, nĩ gửi vậy, mặc dù cĩ hiệu quả hơn so với SCOPE về số yêu cầu được liên kết vào cây cập nhật (request_join) lượng thơng điệp trao đổi, độ trễ, tuy nhiên giải pháp tới R theo định tuyến của mạng phủ. R nhận được yêu của Nakashima cịn hạn chế về mức độ đảm bảo nhất cầu sẽ thi hành thuật tốn AGLINK (trình bày dưới quán (tốc độ loại bỏ cập nhật thường xấp xỉ 95%) hay đây) để liên kết P vào cây cập nhật. Tiếp theo P sẽ yêu độ trễ lan truyền cập nhật khi node cĩ tốc độ vào/ra cầu bản sao từ node cha của nĩ. hoặc cập nhật tăng cao. - 24 -
4. Các cơng trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 được liên kết làm node con phải của node 0. Khi node 0 3 gửi yêu cầu tới node 0, node 0 hiện đã cĩ đủ 2 node con, cho nên nĩ sẽ gửi yêu cầu xuống cho node 1 để yêu cầu thực hiện tương tự, kết quả node 3 được liên 1 2 kết làm node con trái của node 1. III.3. Các thao tác cơ bản 3 4 5 Node lá chỉ cĩ bản sao đang sử dụng. Để điều hịa yêu cầu và thực hiện cập nhật cĩ hiệu quả cao (giảm Hình 2 Minh họa xây dựng cây cập nhật 2-Ary tắc nghẽn, độ trễ và tăng mức độ nhất quán) mỗi node Thuật tốn ALGLINK khi node yêu cầu chia sẻ dữ trong của cây cập nhật sử dụng các biến cục bộ: liệu f: Vectors bit chỉ số: ghi yêu cầu cập nhật từ ALGLINKd-Ary Construction(R,P) node con và chính nĩ nhằm mục đích cĩ thơng tin vị Input: P gửi request_jointới R trí node yêu cầu cập nhật. Trong đĩ, bit đầu tiên ghi Output: Node cha của P yêu cầu của chính node đĩ, bit tiếp theo lần lượt cho Begin các node con từ trái qua phải. Bit chỉ ra node Pgửi request_join tới R tương ứng cĩ/khơng yêu cầu cập nhật. // P khởi tạo các biến cục bộ Buffer kích thước : buffer cĩ bản ghi := {} //tập rỗng và mỗi bản ghi cĩ phần tử. Phần tử đầu tiên : = 1 chứa bản sao. Độ lớn của là độ lệch tối đa giữa các If R cĩ ít hơn d Node conThen bản sao đang sử dụng. Buffer nhận các bản sao từ = node cha hoặc xĩa đi những bản sao cũ khi đã cập + = nhật cho tất cả các node con và cho chính nĩ. Thành ReturnR phần bit gồm hoặc để trống tiếp theo chỉ ra If else phiên bản đĩ đã/chưa cập nhật cho node tương ứng R gửi thơng điệp yêu cầu tới node con Q hoặc khơng cĩ node con tại vị trí đĩ. Như vậy, tất cả cĩ nhỏ nhất trong số node con các bản ghi đều chứa bit , tức là bản sao đĩ chưa cập của R và lặp lại cho đến khi tìm được nhật cho tất cả các node mà nĩ chịu trách nhiệm. node K thỏa mãn (cĩ ít hơn d node con và cĩ nhỏ nhất) Yêu cầu cập nhật: node lá gửi yêu cầu cập nhật = mới lên node cha khi cĩ yêu cầu. Node trong chỉ + = gửi yêu cầu cập nhật lên node cha khi buffer của ReturnK nĩ khơng cĩ bản sao yêu cầu. Node cha nhận yêu End cầu ghi bit 1 vào vectors, tương ứng vị trí của node yêu cầu. Hình 2 minh họa phương thức xây dựng cây cập Trong Hình 3, vectors cĩ 3 bit của node Y chỉ ra: nhật 2-Ary (mỗi node cĩ tối đa 2 node con) cho dữ yêu cầu cập nhật từ node Z và chính node Y (tương liệu chia sẻ f. Ban đầu node 0 được chọn là node gốc. ứng với bit 1 trong vectors), node K khơng yêu cầu Node 1 gửi yêu cầu liên kết vào cây tới node 0 nhờ cập nhật (tương ứng với bit 0). định tuyến mạng phủ. Node 0 kiểm tra chưa cĩ node Cập nhật: node cập nhật trên bản sao cục bộ và con, nên node 1 được liên kết làm node con trái của gửi trực tiếp tới node gốc theo định tuyến trên node 0. Tiếp theo, node 2 gửi yêu cầu tới node 0. mạng phủ Pastry. Node gốc lưu các bản sao vào Node 0 kiểm tra chỉ cĩ node con trái. Vì vậy, node 2 buffer theo thứ tự thời gian đến , , . - 25 -
5. Các cơng trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 . Node Y cập nhật bản sao cho node Z. Hơn R nữa node Y đồng thời xĩa bản ghi chứa . Chẳng hạn node K cĩ yêu cầu cập nhật, node Y kiểm tra X trong buffer thấy rằng là bản sao mới nhất và đã cập nhật tới node K. Vì vậy, node Y gửi yêu cầu cập 1 1 0 Y nhật lên node cha của nĩ là node X. III.4. Duy trì cấu trúc cây Z K Mỗi node sử dụng ancestor lưu thơng tin của node cha tính từ node cha trực tiếp cho tới node gốc. Ancestor được cập nhật đồng thời khi thực hiện cập M nhật bản sao. Node sử dụng thơng điệp trao đổi Hình 3. Minh họa các thao tác cơ bản thường xuyên với node cha để phát hiện sự rời bỏ cấu trúc của node cha. Khi node cha rời bỏ, mỗi node con Bảng 1. Buffer của node Y trước và sau cập nhật độc lập phát hiện ra và tìm cách liên kết trở lại cấu trúc cây dựa vào thơng tin ancestor và thực hiện theo trình tự từ dưới lên và cĩ thể tới node gốc. Trường hợp node gốc rời bỏ, mạng phải chịu trách nhiệm tìm node mới để thay thế. Giả sử xác suất node rời bỏ cấu trúc cây là η theo phân phối Poisson. Vậy xác suất để node con tìm được liên kết trở lại là 1- . Trường hợp node liên kết trở lại là node đại diện cho một cây con sẽ làm tăng chiều cao lớn hơn 1, nên Lan truyền cập nhật: node gốc chịu trách nhiệm khơng thể xây dựng cây cập nhật bằng thuật tốn cây gửi các bản sao xuống phía dưới theo yêu cầu và cân bằng truyền thống. Hơn nữa, các ứng dụng cĩ tốc các node trong cũng thực hiện tương tự. Các node độ vào/ra của node lớn thì việc tối ưu chiều cao của kiểm tra vectors để biết yêu cầu cập nhật. Nếu yêu cây rất khĩ khăn, phức tạp và khơng cần thiết. Trong cầu bản sao cĩ trong buffer, node sẽ gửi chính xác giải pháp mới được đề xuất, mỗi node duy trì, cập nhật dựa vào thơng tin trong vectors. Khi đĩ node đồng dễ dàng các biến cục bộ Child, Count nhằm tính tốn thời ghi bit 1 vào vị trí tương ứng với node nhận sao cho cây cân bằng về số lượng node, giảm chiều cập nhật, trong bản ghi của bản sao. Nếu phiên cao của cây cập nhật khi node liên kết vào hệ thống bản yêu cầu chưa cĩ trong buffer và buffer cịn (node đơn hoặc một cây con). Phương pháp này thực trống, node sẽ gửi yêu cầu lên node cha. Mỗi node hiện đơn giản tuy nhiên vẫn đảm bảo hiệu quả cao so chỉ chịu trách nhiệm cập nhật cho node con. với giải pháp tối ưu hĩa chiều cao của cây cập nhật. Phương thức này đã “điều hịa” được giữa yêu cầu III.5. Giải quyết tắc nghẽn và thực hiện cập nhật. Do vậy node khơng trở nên Ngay cả khi buffer đầy nhưng chỉ cĩ các yêu cầu quá tải cũng như xẩy ra tương tranh hoặc tắc cập nhật các bản sao mà node đang cĩ thì cũng khơng nghẽn khi các node cập nhật. xẩy ra tắc nghẽn, node vẫn đảm bảo phục vụ. Vì vậy, Ví dụ trong Hình 3 và Bảng 1a, b, node Y kiểm tra giải pháp đề xuất chỉ xẩy ra tắc nghẽn khi buffer của vectors biết node Z và chính node Y cĩ yêu cầu cập một node đầy và nhận được thêm yêu cầu cập nhật nhật. Node Y cập nhật bản sao cho chính nĩ đồng bản sao mới khơng cĩ trong buffer. Điều này là do tốc thời ghi bit 1 vào vị trí tương ứng trong bản ghi chứa độ cập nhật khơng cân bằng giữa các node trong cây - 26 -
6. Các cơng trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 con. Cụ thể hơn, cĩ hai trường hợp dẫn đến buffer đầy Thứ hai, khi một node con yêu cầu cập nhật nhanh. như ví dụ trong Bảng 2 sẽ được trình bày sau đây. Để Ví dụ trong Bảng 2b, node K cĩ tốc độ cập nhật nhanh phịng ngừa tắc nghẽn, giải pháp đề xuất xử lý ngay hơn nhiều so với node Y và Z. Node Y chọn node K khi buffer đầy mà khơng đợi đến khi cĩ yêu cầu bản để thay thế nĩ. Node Y sẽ được liên kết vào cây con sao mới khơng cĩ trong buffer bằng cách hỗn đổi liên của K tại vị trí phù hợp với tốc độ yêu cầu cập nhật kết của các node sao cho phù hợp nhằm giải phĩng của nĩ (Hình 5). Giải phĩng và truyền thơng tin trong buffer đầy. Nhờ vậy, chúng ta cĩ thể phịng ngừa được buffer thực hiện tương tự trường hợp 1. hiện tượng tắc nghẽn. Bảng 2. Buffer của node Y đầy Bảng 3. Giải phĩng buffer của node Y X X Y Y Z Z K K M M Hình 4. Minh họa trường hợp 1 chống tắc nghẽn Hình 5. Minh họa trường hợp 2 chống tắc nghẽn IV. ĐÁNH GIÁ THỰC NGHIỆM Thứ nhất, khi tốc độ cập nhật của node Y nhanh Thực nghiệm sử dụng Oversim mơ phỏng giải hơn nhiều (Bảng 2a) so với 2 node con Z, K dẫn tới pháp mới và giải pháp do Nakashima đề xuất trên nền buffer đầy. node Y biết được node Z là node con cĩ mạng phủ Pastry. Chúng tơi lựa chọn so sánh với tốc độ yêu cầu cập nhật chậm nhất. Do vậy node Y tìm Nakashima vì đây là nghiên cứu tiêu biểu, hiệu quả kiếm trong cây con của nĩ node M cĩ tốc độ yêu cầu đối với các mạng phủ P2P cĩ cấu trúc. Kết quả thực cập nhật tương đồng với node K để hốn đổi liên kết nghiệm đánh giá ảnh hưởng của các tham số đặc trưng với node Z (Hình 4). Node M và node Z đồng thời bởi P2P như: gia tăng số lượng node sao, tốc độ cập hốn đổi chỉ số tương ứng trong buffer của nhau. Lưu nhật và vào/ra của node, đối với hiệu quả của mỗi giải ý rằng node M cĩ tốc độ cập nhật nhanh hơn node Z, pháp dựa trên 2 tiêu chí đánh giá quan trọng đối với hệ do vậy các bản sao đã được cập nhật. thống chia sẻ dữ liệu phân tán: Do vậy, buffer lúc này của node Y cĩ thể xĩa đi các bản sao đã cập nhật cho các Node Y, K, M (Bảng 3 a, Độ trễ lan truyền cập nhật: thời gian trung bình b). nhận bản sao của tất cả các node. - 27 -
7. Các cơng trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 Mức độ đảm bảo nhất quán: tỷ lệ các bản sao Chính vì vậy, kết quả chỉ ra trong Hình 7, giải pháp được cập nhật cho tất cả các node trên tổng số cập của Nakashima cĩ kết quả ổn định và tốt hơn. nhật gửi tới node gốc. Chúng tơi giả sử trong thời gian thực nghiệm, trung Tham số cấu hình cho mạng phủ Pastry gồm: bình mỗi node thực hiện tối đa 200 cập nhật. Kết quả Mạng cĩ node. Mỗi node cĩ bảng định tuyến gồm trong Hình 8 chỉ ra: Khi tốc độ cập nhật dưới 160 thì 40 hàng, mỗi hàng cĩ 15 thực thể, 32 node lá. Sự hai giải pháp cho kết quả khá tương đồng. Tuy nhiên, khơng thuần nhất của các node được sinh bởi phân khi tốc độ lớn hơn thì giải pháp đề xuất cĩ độ trễ tốt phối Pareto [18] với thiết lập a = 1 và b = (a và b hơn. Đặc biệt, giải pháp của Nakashima cĩ độ trễ tăng là tham số cận dưới và cận trên của hàm phân phối đều so với tốc độ cập nhật, trong khi giải pháp đề xuất Pareto) để cĩ node cĩ khả năng khác nhau. giữ được độ trễ ổn định. Lý do bởi vì, trong giải pháp Tham số của ứng dụng và mơ phỏng: Độ dài mỗi của Nakashima, tốc độ cập nhật tỷ lệ thuận với số mơ phỏng 1000 đơn vị thời gian. Mỗi file dữ liệu cĩ lượng node sao cần cập nhật bởi node gốc. Từ đĩ dẫn số lựợng bản sao từ 1 đến 5000 theo phân phối Zipf đến độ trễ luơn tăng. Tuy nhiên trong giải pháp được [19]. Tốc độ cập nhật, tốc độ vào/ra của các node sao đề xuất thì ít chịu ảnh hưởng bởi tốc độ cập nhật do theo phân phối Poisson. Bậc của node d = 16. Buffer node con nhận các bản sao từ node cha. cĩ độ lớn b = 20. Kết quả chỉ ra trong các biểu đồ là kết quả trung bình của 10 lần thử. IV.1. Độ trễ lan truyền cập nhật Tốc độ vào/ra của node được tính bằng tỷ lệ thời gian node tham gia chia sẻ dữ liệu trên độ dài thời gian tiến hành thực nghiệm. Trong giải pháp của Nakashima, khi tốc độ vào/ra của node nhỏ thì hầu như bản sao sẽ được gửi thành cơng từ node gốc tới tất Hình 6. Ảnh hưởng của tốc độ vào/ra cả các node sao. Ngược lại, giải pháp sẽ cần thêm nhiều chi phí do thời gian dừng hệ thống để xử lý yêu cầu vào/ra của node. Với giải pháp đề xuất, node con chủ yếu nhận các bản sao sẵn cĩ từ node cha. Vì vậy hệ thống luơn duy trì được sự ổn định cao độ trễ lan truyền cập nhật và chỉ khi node cha rời bỏ mới cĩ sự tác động đáng kể trong cây con. Kết quả trong Hình 6 chỉ ra, giải pháp đề xuất cĩ độ trễ ổn định, khơng tăng nhanh khi tốc độ vào/ra của node tăng. Hơn nữa, giải Hình 7. Ảnh hưởng của gia tăng số lượng node pháp mới cĩ hiệu quả tốt hơn giải pháp do Nakashima đề xuất khi node cĩ tốc độ vào/ra lớn hơn 0.425. Khi số lượng node chia sẻ dữ liệu tăng thì chiều cao cây cập nhật tăng nên độ trễ trung bình tăng theo trong cả hai giải pháp. Tuy nhiên, do độ trễ lan truyền qua mỗi bước nhỏ, nên trong giải pháp của Nakashima, khi số lượng node tăng thì độ trễ vẫn ổn định và nhỏ. Trong khi đối với giải pháp mới phải tốn thêm độ trễ vì cập nhật chỉ được gửi khi cĩ yêu cầu. Hình 8. Ảnh hưởng của tốc độ cập nhật - 28 -
8. Các cơng trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 IV.2. Mức độ đảm bảo nhất quán Khi tốc độ vào/ra, số lượng, tốc độ cập nhật của node tăng thì độ trễ lan truyền cập nhật cũng tăng theo dẫn đến mức độ đảm bảo nhất quán trong cả hai giải pháp đều giảm. Kết quả trong Hình 9, Hình 10, Hình 11 chỉ ra, ngay cả khi node cĩ tốc độ vào/ra lớn (0.5), số lượng node tăng (1000) hay tốc độ cập nhật cao thì giải pháp đề xuất vẫn cĩ kết quả cao (trên 90%) do Hình 11. Ảnh hưởng của tốc độ cập nhật bản sao vẫn cĩ thể được gửi tới node gốc để thực hiện cập nhật cho đến khi buffer của node gốc đầy (tối đa b V. KẾT LUẬN bản sao). Nếu tăng/giảm độ lớn của b sẽ làm Bài báo trình bày một giải pháp mới hiệu quả đảm tăng/giảm mức độ đảm bảo nhất quán. Điều này đồng bảo nhất quán dữ liệu xây dựng trên nền mạng phủ nghĩa với tăng/giảm độ lệch giữa các bản sao trong mơ P2P cĩ cấu trúc. Trong đĩ dữ liệu chia sẻ phân tán, cĩ hình nhất quán tuyến tính dẫn đến khơng thỏa mãn thể được cập nhật thường xuyên, tương tác bởi nhiều yêu cầu của ứng dụng. Vì vậy, phải căn cứ yêu cầu người dùng. Kết quả thực nghiệm chỉ ra rằng, giải của ứng dụng để sử dụng giá trị b phù hợp. Ngược lại, pháp mới cĩ hiệu quả tốt hơn giải pháp do Nakashima giải pháp của Nakashima cĩ tỷ lệ loại bỏ cập nhật rất đề xuất về mức độ đảm bảo nhất quán với trên 90% xấu trong tất cả các trường hợp. Nguyên nhân do việc cập nhật được thực hiện, trong khi độ trễ lan truyền chỉ sử dụng một bản sao tại cùng một thời điểm, nên cập nhật đảm bảo tương đối ổn định khơng tăng nhiều. bản sao mới sẽ bị loại bỏ khi bản sao trước đĩ chưa Đặc biệt, trường hợp node cĩ tốc độ cao vào/ra hoặc được gửi tới tất cả các node sao (do độ trễ lan truyền). yêu cầu cập nhật, giải pháp mới cho hiệu quả cao hơn. Đặc biệt khi tốc độ cập nhật cao, hiệu quả của hai giải pháp đối với mức độ đảm bảo nhất quán càng rõ rệt. TÀI LIỆU THAM KHẢO [1] Gnutella Org Gnutella, [2] Nathaniel S, and Aaron Krekelberg, Good, Usability and privacy: a study of Kazaa P2P file-sharing, Proceedings of the SIGCHI conference on Human factors in computing systems,ACM,pp. 137- 144, 2003. [3] Ian, et al Clarke, Freenet: A distributed anonymous information storage and retrieval system, Designing Privacy Enhancing Technologies, Springer Hình 9. Ảnh hưởng của tốc độ vào/ra Berlin Heidelberg, pp. 46-66, 2001. [4] A. Rowstron and P. Druschel, Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems,IFIP/ACM International Conference on Distributed Systems Platforms and Open Distributed Processing, Springer Berlin Heidelberg, pp. 329-350, 2001. [5] B. Y . Zhao, J. D. Kubiatowicz, and A. D. Joseph, Tapestry: An infrastructure for fault-resilient wide-area location and routing, Technical Report Hình 10. Ảnh hưởng của gia tăng số lượng node UCB//CSD-01-1141, Vol. 214, U. C. Berkeley, April 2001. - 29 -
9. Các cơng trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 [6] S. Ratnasamy, P . Francis, M. Handley, R. Computers, pp. 2953-2967, 2015. Karp, and S. Shenker, A Scalable Content- [17] Xin, et al Chen, SCOPE: Scalable consistency Addressable Network, Proc. of ACM SIGCOMM, Vol. maintenance in structured P2P systems, in 24th 31, No. 4, pp. 161-172, Aug. 2001 Annual Joint Conference of the IEEE Computer and [7] G. Pierre, and M. V. Steen G. Urdaneta, A Communications Societies, vol. 3, pp. 1502-1513, decentralized wiki engine for collaborative wikipedia 2005. hosting, WEBIST,pp. 156-163, 2007. [18] Josef. Steindl, The Pareto Distribution, Palgrave [8] D. Schioberg, L. H. Vu, and A. Datta S. Macmillan UK, Economic Papers, pp. 321-327, 1990. Buchegger, Peerson: P2p social networking early [19] Lada A., and Bernardo A. Huberman. experiences and insights, Proceedings of the Second Adamic, Zipf’s law and the Internet, Glottometrics, ACM EuroSys Workshop on Social Network Systems, pp. 143-150, 2002. ACM, pp. 46-52, 2009. [9] Jun, et al Wang, Distributed collaborative filtering Nhận bài ngày: 23/11/2016 for peer-to-peer file sharing systems, Proceedings of the 2006 ACM symposium on Applied computing, ACM, pp. 1026-1030, 2006. SƠ LƢỢC VỀ TÁC GIẢ [10] David, and Jưrn Kuhlenkamp. Bermbach, Consistency in distributed storage systems, Networked NGUYỄN HỒNG MINH Systems, Springer Berlin Heidelberg, pp. 175-189, Sinh năm 1982. 2013. Tốt nghiệp Cử nhân khoa học [11] ngmar, Bernhard Heep, Stephan I and máy tính, Học viện An ninh Krause. Baumgart, OverSim: A flexible overlay Nhân dân năm 2005; Nhận bằng network simulation framework, IEEE Global Internet Symposium,IEEE, pp. 79-84, 2007. Thạc sỹ Hệ thống phân tán và mạng, Đại học Besancon Pháp, [12] Takayoshi, and Satoshi Fujita. Nakashima, Tree-Based Consistency Maintenance năm 2010. Scheme for Peer-to-Peer File Sharing Systems, Lĩnh vực nghiên cứu: Hệ thống phân tán. Computing and Networking (CANDAR), 2013 First Email: hongminhnguyen1982@gmail.com International Symposium on, IEEE, pp. 187-193, 2013. [13] M. H., AND ABERER, K A. DATTA, "Updates in highly unreliable, replicated peer-to-peer NGUYỄN XUÂN HUY systems",Distributed Computing Systems, 2003. Sinh năm 1944 tại Nam Định. Proceedings. 23rd International Conference,IEEE, pp. Tốt nghiệp Cử nhân Tốn, Đại 76-85, 2003. học Sư Phạm Leningrad, Liên [14] Zhijun, et al WANG, An efficient update propagation algorithm for P2P systems, Computer Xơ năm 1973. Nhận bằng Tiến Communications, pp 1106-1115, 2007(30.5). sĩ CNTT năm 1981, Tiến sĩ [15] Zhenyu LI, Gaogang XIE, and Zhongcheng khoa học CNTT năm 1990 tại LI, Efficient and scalable consistency maintenance for Trung tâm Tính tốn, Viện Hàn heterogeneous peer-to-peer systems, IEEE lâm Khoa học Liên Xơ. Transactions on Parallel and Distributed Systems, pp Lĩnh vực nghiên cứu: Cơng nghệ phần mềm, Cơ sở dữ 1695-1708, 2008(19.12). liệu lớn, phân tán. [16] Haiying, Guoxin Liu, and Harrison Chandler Shen, Swarm intelligence based file Email: nxhuy564@gmail.com replication and consistency maintenance in structured P2P file sharing systems, IEEE Transactions on - 30 -