LOGO
LẬP TRÌNH MẠNG
Cán bộ hướng dẫn : PGS.TS Lê Văn Sơn
Học viên thực hiện : Võ Minh Tiến
Lớp : Khoa học máy tính – K24
ÁP DỤNG THUẬT TOÁN MULLERY
ĐẢM BẢO GẮN BÓ DỮ LIỆU TRONG
CÁC CSDL PHÂN TÁN
01/31/15 1 www.blc.edu.vn
LOGO
Nội dung
Quản lý nhiều bản sao các ứng dụng
1
Giải thuật quản lý nhiều bản sao
2
Đánh giá số lượng, trạng thái, thông điệp bản sao
3
Kết luận
4
01/31/15 2
www.blc.edu.vn
LOGO
Quản lý nhiều bản sao

Cập nhật thông tin trong môi trường phân tán

Vấn đề nhân bản đối tượng thông tin:
•
Thời gian truy cập trung bình vào hệ thông tin
phân tán có thể được rút ngắn nhờ vào phương
pháp nhân nhiều bản sao của một đối tượng

đặc biệt b
ij
, i=1 n, j=1 m,
trong đó i chỉ server, j chỉ
bản sao, n là số lượng
server được mắc nối trong
mạng, m là số lượng các
bản sao cần phải cập nhật.
Mỗi server có thể quản lý
một mạng con. Ngoài ra,
các bản sao có thể được bố
trí trên các trạm thể hiện
bằng các t
k
, k=1 q, k là
trạm và q là số trạm được
mắc nối.
01/31/15 5
www.blc.edu.vn
LOGO
Quản lý nhiều bản sao
Nếu ta có n bản sao của đối tượng b nào đó, thì ràng
buộc toàn vẹn phải là:
Gọi M là cực đại của các cập nhật có thể diễn ra đồng
thời, thì M có thể tính theo công thức M = n × m.
Trên bản sao của 1 đối tượng
b
1
=b
2

Kỹ thuật đánh dấu bản điều khiển
Việc lựa chọn giải thuật cập nhật được tiến hành trên cơ sở truy
cập vào cấu trúc phân tầng.
Một hệ thống bao gồm
các chương trình, danh
sách tài nguyên cần
thiết để thực hiện các
lệnh và tổ hợp các tín
hiệu cho phép nhận biết
trạng thái của toàn bộ
các bản sao đang được
sử dụng trong hệ.
01/31/15 7
www.blc.edu.vn
LOGO
Giải thuật quản lý nhiều
bản sao
Nội dung cơ bản của
kỹ thuật này:
Trạng thái các bản sao
trên toàn bộ hệ thống
được thể hiện một
cách chính xác
Mỗi khi cập nhật cho
phép chỉ gửi những
chi tiết cần thay đổi là
đủ
Làm tươi thông tin trong
bản điều khiển thực
hiện tự động

tác tử nhận trong cơ chế
then cài đối với các phép
làm thay đổi thông tin trong
bản sao, ngược lại, thì thực
hiện theo kiểu tương tranh.
01/31/15 10
www.blc.edu.vn
LOGO
Giải thuật quản lý nhiều
bản sao
Các bước thể hiện công việc xử lý thông tin điều khiển
được tiến hành tuần tự như sau
01/31/15 11
www.blc.edu.vn
LOGO
Giải thuật quản lý nhiều
bản sao
Sơ đồ được nghiên cứu cho việc ghi có kiểm tra thông tin vào một
trường xác định của bản sao là cơ sở dữ liệu phân tán.
01/31/15 12
www.blc.edu.vn
LOGO
Đánh giá số lượng, trạng
thái, thông điệp bản sao

Có bao nhiêu trạng thái khác nhau cho mỗi bản sao
Thuật toán dựa trên các nguyên lý sau:
- Trước khi thực hiện cập nhật, một trạm nào đó cần phải
yêu cầu và thống nhất với các trạm khác.
- Khi đã có sự thống nhất, tiến hành cập nhật; việc cập


Số lượng bản sao và thông điệp
Nếu ta có n bản sao e
1
, e
2
, e
3
, , e
n
của
đối tượng e, một trong các ràng buộc
toàn vẹn là:
e
1
= e
2
= = e
n
Để tham chiếu đến e, cần phải thực hiện
giao dịch:
v_doc(e
i
): đọc e
i
theo kiểu chia sẻ
doc(e
i
): đọc e
i

Đánh giá số lượng, trạng
thái, thông điệp bản sao
Để thực hiện việc cập nhật vào các bản sao, ta cần phải
cài then chúng một cách hợp thức theo kiểu loại trừ
Để tránh bế tắc diễn ra, việc cài then các bản sao luôn
luôn phải được thực hiện trong cùng một trật tự.
Để cho i:=1 đến n thực hiện v_viet(e
i
)
<Thực hiện các cập nhật và chép lại chúng vào tất cả các bản>
Để cho i:=1 đến n thực hiện giai_phong(e
i
)
01/31/15 16
www.blc.edu.vn
LOGO
Đánh giá số lượng, trạng
thái, thông điệp bản sao
Để giải quyết bài toán ta cần phải tính đến các yếu tố sau:
a. Các trạm và các đối tượng có số lượng xác định trước (số
lượng cố định ở thời điểm khai thác).
b. Các tiến trình của các trạm và hệ thống viễn thông có thể
xảy ra sự cố kỹ thuật, những sự cố này có thể khắc phục được.
c. Có các chỉ dẫn cần thiết cho việc mở rộng sau này để có
thể xử lý các tình huống ngoài chế độ bình thường.
Vậy,
Gọi M: là số trạm trên một hệ phân tán
n: là số lượng các bản sao của một đối tượng
k: số đối tượng của một trạm
Số lượng bản sao của hệ thống = n.M.k

trong quản lý nhiều bản sao
• Bổ sung lý thuyết cập nhật nhiều bản sao
01/31/15 19
www.blc.edu.vn
LOGO
01/31/15 20 www.blc.edu.vn