Luận án Nâng cao hiệu quả một số kỹ thuật đảm bảo tính nhất quán dữ liệu trong mạng P2P

 quan hệ 
 và 
 là biểu diễn chuyển đổi trạng thái trong 
tiến trình p, với 
 là chuyển trạng thái nội bộ, không nhận hay gửi thông điệp, 
chuyển trạng thái và gửi thông điệp, 
 chuyển trạng thái và nhận thông điệp. 
Định nghĩa 2.3 [25]. Một thuật toán phân tán trên là tập 
các thuật toán cục bộ của các 
Định nghĩa 2.4 [25]. Một sự dịch chuyển cấu hình theo phƣơng thức truyền 
thông tin không đồng bộ dựa trên một thuật toán phân tán, là một bộ 
 , trong đó: 
1. và } 
2. , với là hàm chuyển đổi trạng thái của tiến trình p; 
 là tập các cặp: 
Chúng thỏa mãn một trong ba điều kiện sau: 
a) 
 và 
b) Có 
 và 
c) Có 
 và 
3. và 
Một thực thi của một thuật toán phân tán là sự chuyển đổi cấu hình dựa trên 
S. Các cặp 
 đƣợc gọi là các sự kiện nội bộ của p, và 
đƣợc gọi là các sự kiện gửi và sự kiện nhận của p. 
Định nghĩa 2.5 [25]. Một sự dịch chuyển cấu hình theo phƣơng thức truyền 
thông tin đồng bộ dựa trên một thuật toán phân tán, là một bộ 
 , 
trong đó: 
38 
1. , 
2. , trong đó: 
a) là tập các cặp 
 thỏa ( 
b) là tập các cặp 
 ( 
 thỏa mãn có một thông điệp sao 
cho 
 và 
3. 
2.1.2. Biểu diễn các tham số của hệ thống dữ liệu chia sẻ 
Các tham số của hệ thống dữ liệu chia sẻ (trình bày trong chƣơng 1) có ảnh 
hƣởng quan trọng tới hƣớng tiếp cận nhằm tìm ra các giải pháp phù hợp cho mỗi hệ 
thống cụ thể và hiệu quả của các lƣợc đồ đảm bảo tính nhất quán dữ liệu. Vì vậy, 
trong mục này, luận án biểu diễn công thức toán học của các tham số đó để làm cơ 
sở cho việc nghiên cứu và thực hiện mô phỏng thực nghiệm đối với các giải pháp 
đƣợc đề xuất. 
2.1.2.1. Nút không thuần nhất 
Nút trong các hệ thống dữ liệu chia sẻ hoàn toàn tự trị và không thuần nhất 
đặt ra nhiều vấn đề khó khăn, phức tạp cho các lƣợc đồ đảm bảo tính nhất quán dữ 
liệu. Sự không thuần nhất của nút đƣợc biểu diễn bởi các hàm phân phối xác suất 
nhƣ trình bày dƣới đây. 
a) Khả năng của nút 
Đại lƣợng XP biểu thị cho khả năng của nút (tốc độ xử lý, bộ nhớ...) thỏa 
mãn là biến ngẫu nhiên trong phân phối Pareto [54]. Phân phối Pareto đƣợc đặc 
trƣng bởi hai giá trị cho trƣớc, gồm có tham số tỷ lệ là giá trị dƣơng nhỏ nhất 
của XP và tham số hình dạng (số dƣơng) đƣợc gọi là chỉ số đuôi. Khi đó, xác suất 
đại lƣợng XP lớn hơn một giá trị  nào đó đƣợc biểu diễn bởi hàm nhƣ sau: 
39 
 ̅ {
 (2.1) 
Hình 2.1 minh họa biểu đồ của phân phối Pareto. 
Hình 2.1. Biểu diễn phân phối Pareto 
b) Tốc độ nút vào/ra hệ thống, tốc độ nút thực hiện cập nhật 
Đặc trƣng nổi bật nhất của mạng P2P là kém ổn định do tốc độ nút vào/ra hệ 
thống cao và không xác định (nút chủ động hoặc bị lỗi); tốc độ nút thực hiện cập 
nhật trên các bản sao cục bộ. Đại lƣợng XP biểu thị cho mỗi sự kiện này thỏa mãn 
là biến ngẫu nhiên của phân phối Poisson [55], với tham số là số nguyên dƣơng 
thể hiện số lần xuất hiện trung bình của đại lƣợng XP trong một khoảng thời gian Γ 
cho trƣớc. Hàm xác suất biểu diễn cho đại lƣợng XP nhƣ sau: 
 (2.2) 
Trong đó: 
- e: Cơ số logarit tự nhiên. 
- : Số lần xuất hiện của sự kiện XP. 
Hình 2.2 minh họa biểu đồ của phân phối Poisson. 
50 
42 
20 
15 
5 
37.88 
69.70 
84.85 
96.21 100.00 
0
10
20
30
40
50
60
70
80
90
100
0
10
20
30
40
50
60
A B C D E
Số lần 
Tỷ lệ tích lũy % 
Khả năng của nút 
S
ố
 l
ầ
n
 x
u
ấ
t 
h
iệ
n
Phần trăm 
40 
Hình 2.2. Biểu diễn phân phối Poisson 
Tốc độ nút vào/ra hệ thống tƣơng ứng với tỷ lệ thời gian nút tham gia trong 
hệ thống và tốc độ nút thực hiện cập nhật tƣơng ứng với số lần nút thực hiện cập 
nhật trên độ dài thời gian tiến hành thực nghiệm. Do vậy, trong trình bày của luận 
án, sẽ sử dụng tỷ lệ này để chỉ tốc độ nút vào/ra hệ thống và đại lƣợng tổng số lần 
đã thực hiện cập nhật của tất cả các nút để chỉ tốc độ nút thực hiện cập nhật. 
2.1.2.2. Quy mô hệ thống dữ liệu chia sẻ 
Quy mô hệ thống dữ liệu chia sẻ đƣợc biểu thị bởi hai tham số, gồm có: số 
lƣợng nút tham gia và số lƣợng đối tƣợng dữ liệu chia sẻ trong hệ thống. Đặc biệt, 
do tốc độ nút vào/ra hệ thống không xác định nên các giá trị này sẽ liên tục biến đổi. 
Khi quy mô của hệ thống thay đổi, nhất là trong trƣờng hợp các tham số này gia 
tăng thì bài toán đảm bảo tính nhất quán càng trở nên khó khăn, phức tạp hơn. Số 
lƣợng nút tham gia và số lƣợng đối tƣợng dữ liệu chia sẻ trong hệ thống là đại 
lƣợng thỏa mãn phân phối Zipf [56], có công thức nhƣ sau: 
 ⁄
∑ ⁄ 
 (2.3) 
Trong đó: 
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
α 1 
α 4 
α 10 
Giá trị 𝜹 
P
(X
P
=
 𝛅
) 
41 
- : Số phần tử. 
- : Thứ hạng. 
- : Giá trị của số mũ đặc trƣng cho phân phối. 
Hình 2.3 minh họa biểu đồ của phân phối Zipf với 
 Hình 2.3. Biểu diễn phân phối Zipf 
2.2. LƢỢC ĐỒ CẬP NHẬT NỘI DUNG ĐẢM BẢO TÍNH NHẤT QUÁN DỮ 
LIỆU CHIA SẺ TRONG MẠNG P2P 
Khi nút muốn có dữ liệu chia sẻ, trƣớc tiên nó cần liên kết vào cấu trúc cây 
cập nhật. Mỗi lƣợc đồ sẽ có giải pháp xây dựng cây cập nhật khác nhau, trong đó có 
hai hƣớng tiếp cận nhƣ sau: 
Cây cập nhật tĩnh: Cấu trúc cập nhật của mỗi dữ liệu chia sẻ đƣợc xây dựng 
cố định trên mạng P2P, nhằm lan truyền nội dung cập nhật. 
Cây cập nhật động: Cấu trúc cập nhật của mỗi dữ liệu chia sẻ chỉ đƣợc xây 
dựng khi một nút nào đó thực hiện cập nhật, nhằm lan truyền nội dung cập nhật và 
cấu trúc cập nhật sẽ bị hủy bỏ khi cập nhật đã hoàn thành. 
0.00
0.10
0.20
0.30
0.40
0.50
0.60
0.70
0.80
0.90
1.00
0 1 2 3 4 5 6 7 8 9 10
s = 1
s = 2
s = 3
s = 4
Giá trị 𝜔 
P
(𝜔
,s
,1
0
) 
42 
Nút gốc
Mức 0
Mức 1
Mức 2
Mức L
Hình 2.4. Minh họa cây nhị phân cập nhật 
Lƣợc đồ tổng quan đƣợc thực hiện gồm có hai bƣớc nhƣ sau: 
Bước 1: Với mỗi dữ liệu chia sẻ X, lƣợc đồ sẽ xây dựng cấu trúc cây cập 
nhật d-ary phía trên mạng P2P, ký hiệu là . 
Cây bao gồm hữu hạn nút trong hệ thống hoặc chỉ gồm các nút sao. Trong 
đó, nút chính của khóa sẽ đƣợc chọn là nút gốc của cây và trên tập hợp các nút 
có một quan hệ phân cấp gọi là quan hệ "cha - con". Cây d-ary là cây mà mỗi nút có 
tối đa d nút con, d đƣợc gọi là bậc của nút. Giả sử có N nút tham gia, nhƣ vậy chiều 
cao của cây là . Hình 2.4 là minh họa cho cây nhị phân cập nhật. 
Bước 2: Các nút có thể thực hiện cập nhật trên bản sao cục bộ theo nhu cầu 
sử dụng, nhƣng đồng thời nút này cần gửi nội dung bản sao mới tới nút gốc để lan 
truyền cập nhật cho các nút phía dƣới. 
Trong phần sau đây, luận án trình bày và phân tích các giải pháp trong thực 
hiện đối với mỗi bƣớc cụ thể nêu trên. 
2.2.1. Giải pháp xây dựng và duy trì cấu trúc cập nhật 
2.2.1.1. Giải pháp xây dựng cây cập nhật 
Yi và các cộng sự đề xuất giải pháp xây dựng cây cập nhật theo thứ tự thời 
gian đến và cân bằng số lƣợng các nút trong mỗi cây con. Trong đó, nút chính của 
khóa sẽ là nút gốc của cây cập nhật. Mỗi nút sử dụng 2 biến cục bộ, gồm có 
43 
là tập các nút con của P và là số lƣợng các nút trong cây con của P. Giả sử 
nút P (có thể là nút đơn lẻ hoặc cây con) muốn liên kết vào cây cập nhật, nếu nó là 
nút mới, trƣớc tiên khởi tạo các biến cục bộ . Đồng thời 
nút P gửi thông điệp tới nút gốc để yêu cầu liên 
kết vào cây cập nhật. Nếu nút gốc chƣa có đủ nút con, nút P sẽ đƣợc liên kết làm 
nút con của nút gốc tại vị trí còn thiếu. Ngƣợc lại, nút gốc gửi thông điệp tới nút con 
Q có nhỏ nhất trong số nút con. Nút Q nhận đƣợc thông điệp và thực hiện 
tƣơng tự cho đến khi tìm đƣợc nút cha của nút . Mã giả của thuật toán trên đƣợc 
trình bày nhƣ dƣới đây. 
Đầu vào: Nút nhận thông điệp . 
Đầu ra: Nút cha của hoặc tiếp tục gửi . 
 Begin 
1 If K có ít hơn d nút con Then 
2 
3 + = 
4 Return K 
5 Else if 
6 Send request_join(P, , ) tới nút con Q 
7 // nút con Q có nhỏ nhất trong số nút con của K. 
8 End if 
 End 
Nakashima và các cộng sự đề xuất thuật toán xây dựng cây cập nhật theo xác 
suất nút mới có thông tin của nút gốc. Thuật toán thực hiện tƣơng tự thuật toán xây 
dựng cây cập nhật của Yi nhƣ trình bày ở trên. Tuy nhiên, thông điệp 
 của nút mới P có yêu cầu liên kết vào cây cập 
nhật là có thể không gửi tới nút gốc mà sẽ gửi tới nút mà nó biết, cụ thể nhƣ sau: 
Nút Y là nút đầu tiên nhận thông điệp yêu cầu đƣợc xác định nhƣ sau: 
- Nếu nút P biết đƣợc địa chỉ IP nút gốc của cây cậy nhật , thì nút gốc 
đƣợc chọn là nút y với xác suất bằng 1 
44 
- Ngƣợc lại, nút gốc sẽ là nút Y với xác suất p và nút gửi cập nhật cho P 
đƣợc chọn là nút Y với xác suất . 
So với giải pháp của Yi, giải pháp của Nakashima giúp giảm chi phí mà nút 
mới thực hiện gửi thông điệp yêu cầu liên kết vào cây cập nhật 
 , tuy nhiên nó không đạt đƣợc hiệu quả về cây 
cân bằng. Hơn nữa, trong cả hai phƣơng thức xây dựng cây cập nhật của Yi và 
Nakashima, có nhƣợc điểm là các nút liên kết với nhau (quan hệ cha –con) nhƣng 
có thể xa nhau về mặt logic, làm tăng chi phí truyền thông giữa các nút. Chẳng hạn 
trong mạng Pastry thì chi phí truyền thông giữa hai nút bất kỳ luôn là (bƣớc). 
Điều này dẫn đến tăng độ trễ cập nhật, số lƣợng băng thông và thông điệp để đảm 
bảo tính nhất quán dữ liệu. 
Chen và các cộng sự [57] đề xuất thuật toán xây dựng cây cập nhật sử dụng 
nút đại diện. Mỗi nút đƣợc định danh duy nhất trong vùng không gian định danh 
bit (chẳng hạn bằng cách băm địa chỉ IP của nút đó). Dựa vào định danh của mỗi 
nút, thuật toán phân chia liên tiếp tất cả các nút trong mạng P2P thành các phân 
vùng bằng nhau. Nút chính của khóa là nút gốc của cây cập nhật, các nút con là nút 
đại diện cho mỗi phân vùng. Thuật toán sử dụng vector lƣu thông tin về vị trí các 
nút sao trong cây con của nó và chỉ nút lá chứa bản sao. Hình 2.5 minh họa cây nhị 
phân cập nhật đƣợc xây dựng theo thuật toán trên. 
Không gian định 
danh 4 bít
Nút gốc
11011101
1001
1111
1101 1100
1001
Hình 2.5. Xây dựng cây cập nhật sử dụng nút đại diện 
45 
Trong giải pháp của Chen, các nút không chứa bản sao cũng tham gia cấu 
trúc cây cập nhật, dẫn đến quy mô của cây sẽ rất lớn, các nút có thể dễ trở nên quá 
tải do phải xử lý nhiều yêu cầu. 
Shen và các cộng sự [51] đề xuất thuật toán xây dựng cây cập nhật theo 
khoảng cách mạng. Giả sử trong không gian mạng Internet có m mốc. Mỗi nút tính 
toán khoảng cách của nó tới m mốc, biểu diễn dƣới dạng vector . 
Đƣờng cong Hilbert [58] thực hiện ánh xạ vector thành một số 
nguyên dƣơng, gọi là số Hilbert (ký hiệu ). Khi đó, các nút có chênh lệch càng 
nhỏ, sẽ càng gần nhau trong mạng Internet. Nút gốc của cây cập nhật là nút có ở 
chính giữa trong tập của các nút. Mỗi nút (không phải là nút lá) có d con với 
gần với của nó; theo chiều ngang, các nút cùng cấp có giá trị theo thứ tự tăng 
dần. Trong phƣơng thức xây dựng cây cập nhật của Shen, các nút gần nhau về địa lý 
sẽ liên kết gần nhau về mặt logic trong cấu trúc cây cập nhật. Tuy nhiên, giải pháp 
tốn nhiều chi phí để tính toán, xác định khoảng cách mạng của các nút. Do vậy đối 
với hệ thống có tốc độ nút vào/ra lớn sẽ không hiệu quả. 
2.2.1.2. Duy trì cấu trúc cây cập nhật 
Nút có tốc độ vào/ra hệ thống không xác định, nguyên nhân do nhu cầu tham 
gia hệ thống khác nhau của các nút và những yếu tố đặc trƣng của mạng P2P. Vì 
thế, các lƣợc đồ đảm bảo tính nhất quán dữ liệu cần có các giải pháp xử lý vấn đề 
này nhằm duy trì cấu trúc cập nhật. Khi tốc độ này càng lớn thì việc duy trì cấu trúc 
cây cập nhật càng khó khăn, phức tạp và đòi hỏi chi phí cao. 
Thông thƣờng, mỗi nút cần lƣu thông tin của nút cha và các nút tổ tiên của 
nó. Nút sử dụng thông điệp trao đổi thƣờng xuyên với nút cha để phát hiện sự rời bỏ 
cấu trúc của nút cha. Khi nút cha rời bỏ, mỗi nút con cần độc lập phát hiện ra điều 
này và tìm cách liên kết trở lại cấu trúc cây cập nhật dựa vào thông tin mà nó có. 
2.2.2. Mô hình lan truyền cập nhật 
Khi nút gốc nhận cập nhật mới, nó sẽ gửi cập nhật đó cho các nút con và các 
nút con thực hiện các thao tác lặp lại tƣơng tự, cho tới khi tất cả các nút nhận đƣợc 
46 
cập nhật. Mô hình tổng quát về lan truyền cập nhật trong cấu trúc cây đã đƣợc trình 
bày trong công bố [24] và để thực hiện tính toán có các giả thiết nhƣ sau: 
- Tốc độ yêu cầu cập nhật của các nút gửi tới nút gốc là ; 
- Mỗi nút (trừ nút lá) có bộ nhớ đệm kích thƣớc k để lƣu trữ các bản sao gửi 
tới nó. 
Lan truyền cập nhật đƣợc thực hiện đồng thời từ nút tới nút , 
 , trong đó là nút gốc và là nút lá. Độ trễ cập nhật từ một lớp tới lớp 
liền kề phía dƣới là thời gian lớn nhất lan truyền cập nhật của một cặp nút cha-con 
trong hai lớp đó. Ký hiệu là độ trễ cập nhật từ mức và mức . Nhƣ vậy, độ 
trễ cập nhật là một phân phối theo cấp số nhân theo mô hình hàng đợi (Hình 2.6). 
Hình 2.6. Mô hình lan truyền cập nhật trong cấu trúc cây 
Giả sử là độ trễ cập nhật lớn nhất, tức là . Nhƣ 
vậy, ta có mô hình hàng đợi đối với độ trễ cập nhật từ nút gốc tới nút lá, 
với bộ nhớ đệm có kích thƣớc , tốc độ cập nhật của các nút gửi đến nút gốc là 
 , thời gian phục vụ là (Hình 2.7). 
Hình 2.7. Mô hình tính toán rút gọn đối với độ trễ cập nhật 
2.2.3. Biểu diễn các tham số đánh giá hiệu quả 
Nhƣ đề cập trong chƣơng 1, trong bài toán nghiên cứu và của các hệ thống dữ 
liệu chia sẻ, có ba tham số có ý nghĩa quan trọng trong ứng dụng thực tiễn, bao gồm: 
mô hình nhất quán, tính sẵn sàng của dữ liệu chia sẻ và độ trễ cập nhật. Phần này, luận 
án trình bày biểu thức toán học biểu diễn cho ba tham số nêu trên, cụ thể nhƣ sau: 
a) Mô hình nhất quán dữ liệu – mức độ nhất quán 
Các lƣợc đồ sử dụng cấu trúc cây lan truyền cập nhật đảm bảo tính nhất quán 
47 
dữ liệu theo mô hình tuyến tính, kích thƣớc bộ nhớ đệm (giá trị của k) là độ lệch tối 
đa giữa các bản sao cho phép theo quy ƣớc, biểu thị mức độ nhất quán trong mô 
hình nhất quán tuyến tính (sau đây gọi là mức độ nhất quán). Tùy theo yêu cầu của 
ứng dụng mà các lƣợc đồ có thể xác định giá trị k phù hợp. 
b) Tính sẵn sàng của dữ liệu chia sẻ hay tỷ lệ cập nhật thành công 
Ta có tốc độ cập nhật gửi tới nút gốc là: 
 (2.4) 
Ký hiệu là xác suất có cập nhật trong hàng đợi. Theo lý thuyết hàng đợi 
hữu hạn M/M/1 ta có: 
 (2.5) 
Cập nhật bị từ chối khi bộ nhớ đệm của nút gốc đầy. Điều này xảy ra là do có 
một nút phía dƣới có bộ nhớ đệm đầy. Nhƣ vậy, các nút dọc theo liên kết từ nút 
gốc tới cũng có bộ nhớ đệm đầy. Giả sử ký hiệu chuỗi này là . Khi 
bộ nhớ đệm của nút đƣợc giải phóng (không còn đầy), thì cập nhật sẽ đƣợc gửi 
đồng thời nhƣ sau: . 
Ta có: 
 ∑ 
 (2.6) 
Suy ra: 
 (2.7) 
Tỷ lệ bản sao bị từ chối cập nhật khi gửi tới nút gốc là: 
 (2.8) 
48 
Do đó, tỷ lệ cập nhật thành công đƣợc biểu diễn bằng công thức sau: 
(2.9) 
c) Độ trễ cập nhật 
Số lƣợng cập nhật trong hàng đợi là [ ], biểu diễn bởi công thức: 
 [ ] ∑ 
 (2.10) 
Kết hợp với công thức trên, ta có: 
 [ ] 
 (2.11) 
Độ trễ cập nhật đƣợc biểu diễn bởi công thức sau: 
 [ ] 
 [ ]
 (2.12) 
Trong đó, là tốc độ cập nhật đến nút gốc không bị từ chối. 
49 
Nhận xét, đánh giá: 
Từ công thức biểu diễn toán học của các tham số đánh giá hiệu quả lƣợc đồ 
đảm bảo tính nhất quán dữ liệu trong mạng P2P nhƣ trên, chúng ta đƣa ra một số 
nhận xét, đánh giá quan trọng nhƣ trình bày dƣới đây. 
- Không thể đạt đƣợc tối ƣu đồng thời cho ba tham số nêu trên đối với các 
hệ thống dữ liệu chia sẻ, do chúng loại trừ lẫn nhau về mặt hiệu quả. Chẳng hạn, khi 
kích thƣớc bộ nhớ đệm càng nhỏ thì mức độ nhất quán càng cao, tuy nhiên tính sẵn 
sàng của dữ liệu càng nhỏ và ngƣợc lại. 
- Độ trễ cập nhật và tỷ lệ cập nhật thành công phụ thuộc vào các tham số của 
hệ thống dữ liệu chia sẻ và lƣợc đồ đảm bảo tính nhất quán, nhƣ sau: 
+ Các tham số của hệ thống dữ liệu chia sẻ gồm có: N (số lƣợng nút sao), 
khả năng của nút, tốc độ nút thực hiện cập nhật, tốc độ nút vào/ra hệ thống. 
+ Hiệu quả của lƣợc đồ đảm bảo tính nhất quán dữ liệu nhƣ: bậc của nút 
(d), kích thƣớc bộ nhớ đệm (k), và độ trễ cập nhật từ nút cha cho nút con ( ). 
Trong đó, hiệu quả về tỷ lệ cập nhật thành công sẽ tỷ lệ thuận với , tỷ lệ nghịch với 
 và ; độ trễ cập nhật tỷ lệ thuận với . Đặc biệt, giá trị phụ thuộc hiệu 
quả giải pháp xây dựng cấu trúc cập nhật, truyền thông giữa các nút và phƣơng thức 
lan truyền cập nhật; trong đó có những vấn đề khó khăn, phức tạp nhƣ nút quá tải, 
xảy ra tắc nghẽn, bế tắc và mất cân bằng tải. 
Hai lƣợc đồ đảm bảo tính nhất quán dữ liệu đƣợc đề xuất bởi Nakashima và 
Yi, sử dụng phƣơng thức lan truyền nội dung cập nhật, có hiệu quả cao đối với bài 
toán nghiên cứu nhƣng ở các mục tiêu khác nhau (hệ thống dữ liệu chia sẻ khác 
nhau). Nakashima xây dựng cấu trúc cây cập nhật tĩnh, trong đó mỗi nút không có 
bộ nhớ đệm, nên không xảy ra những trƣờng hợp tắc nghẽn, mất cân bằng tải...; giải 
pháp đạt đƣợc hiệu quả cao về độ trễ cập nhật nhƣng kém hiệu quả đối với tính sẵn 
sàng của dữ liệu cập nhật. Bên cạnh đó, giải pháp của Nakashima lan truyền cập 
nhật từ nút gốc tới nút lá và truyền thông giữa các nút còn kém hiệu quả do phƣơng 
thức xây dựng cấu trúc cây cập nhật, nên chƣa tối ƣu về độ trễ cập nhật, đặt biệt khi 
tốc độ nút vào/ra hệ thống lớn thì độ trễ cập nhật thƣờng tăng đột biến. Yi đề xuất 
50 
giải pháp BCoM, xây dựng cấu trúc cây cập nhật tĩnh, trong đó mỗi nút có bộ nhớ 
đệm (trừ nút lá) nhằm đạt đƣợc hiệu quả cân bằng giữa các tham số (mức độ đảm 
bảo tính nhất quán, độ trễ cập nhật, khả năng sẵn sàng của dữ liệu cập nhật). Tuy 
nhiên trong giải pháp của Yi, nút cha sẽ gửi các bản sao cập nhật cho các nút con 
khi bộ nhớ đệm của nút con còn trống, mà không phụ thuộc vào việc nút con có yêu 
cầu hay không, cho nên dễ dẫn đến tình trạng bộ nhớ đệm của các nút con đầy, 
đồng thời xảy ra tình trạng tắc nghẽn cập nhật. Đặc biệt, trong các ứng dụng mà tốc 
độ nút thực hiện cập nhật khác biệt nhau lớn. 
Trong các mục 3.1, 3.2 và 3.3 ở chƣơng 3, luận án trình bày các đề xuất khắc 
phục những hạn chế trên nhằm nâng cao hiệu quả các lƣợc đồ đảm bảo tính nhất 
quán dữ liệu. 
2.3. MÔ PHỎNG THỰC NGHIỆM 
Trong luận án, các giải pháp và thuật toán đề xuất đƣợc triển khai tại tầng 
ứng dụng xây dựng trên mạng Pastry có cấu trúc (Hình 2.8). 
Pastry Chord Tapestry
INET Simple SingleHost
 Liên kết vật lý
KBR TestApp DHT
DHT TestApp ...
Tầng dưới
Tầng mạng 
phủ P2P
Tầng ứng 
dụng
Hình 2.8. Kiến trúc ứng dụng xây dựng trên mạng P2P 
Pastry RowstronMạng đƣợc đề xuất bởi và các cộng sự vào năm 2001, là 
mạng nền khá nổi tiếng để phát triển các ứng dụng [59]. Một số nội dung giới thiệu 
Pastryvà thiết lập tham số của mạng liên quan tới minh họa, lập trình các thuật 
toán, giải pháp và thực nghiệm mô phỏng nhƣ sau: 
51 
[0, 2128 − 1] 
Hình 2.9. Sắp xếp các nút và khóa trong không gian định danh 128 bit 
Định danh mỗi nút 𝑀𝑖 và đối tƣợng dữ liệu chia sẻ 𝑋𝑗 lần lƣợt là 𝐼𝐷𝑀𝑖 𝐼𝐷𝑋𝑗 
trong cơ số 𝑏 (b là tham số cấu hình, thông thƣờng là 2 hoặc 4, trong luận án 𝑏 
4), hàm băm phân tán đối với địa chỉ IP của nút và tên dữ liệu 𝑋𝑗. Định danh của 
nút và khóa đƣợc sắp xếp, bố trí trên cùng một vùng không gian định danh 128 bit 
là [ 8 ] (𝐼𝐷𝑀𝑖 𝐼𝐷𝑋𝑗 [ 
 8 ] Hàm trừu tƣợng ) (Hình 2.9). 
xác định khoảng cách từ khóa đến khóa , để phân hoạch mỗi nút chịu trách 
nhiệm cho một vùng không gian khóa bằng nhau. Nhƣ minh họa trong hình 2.9, nút 
𝑀 chịu trách nhiệm cho các khóa 𝑘 (tƣơng ứng đối tƣợng dữ liệu 𝑋 khóa ) và 𝑘 
(tƣơng ứng đối tƣợng dữ liệu 𝑋 nút ); 𝑀 chịu trách nhiệm cho các khóa 𝑘 (tƣơng 
ứng đối tƣợng dữ liệu 𝑋 nút ); 𝑀 chịu trách nhiệm cho các khóa 4 𝑘4 (tƣơng ứng đối 
tƣợng dữ liệu 𝑋4 nút ); và 𝑀 chịu trách nhiệm cho các khóa 𝑖 𝑘𝑗 (tƣơng ứng đối tƣợng 
dữ liệu 𝑋𝑗). 
Mạng gồm các nút có khả năng khác nhau đƣợc sinh ngẫu nhiên bởi phân 
phối Pareto; nút có bảng định tuyến gồm 10 hàng, mỗi hàng có 15 ( 𝑏 thực ) 
thể; 32 (tƣơng ứng là 𝑏 nút lá (nút gần về logic), 32 ) (tƣơng ứng là 𝑏 nút ) 
láng giềng (nút gần về vật lý). Hình 2.10 là ví dụ minh họa bảng định tuyến của một 
nút, trong đó tham số cấu hình , kích thƣớc gồm có 8 hàng, mỗi hàng có 3 
thực thể, nút lá và 8 nút láng giềng. 8 
52 
10233033
10233001
10233021
10233000
102