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

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