H PHÂN TÁNỆ V n đ nhi u b n sao trong đi u ki n truy c p l nấ ề ề ả ề ệ ậ ớ
GIỚI THIỆU
Quản lý nhiều bản sao của cùng một đối tượng thông tin hiện nay đang
được các nhà chuyên môn tin học quan tâm nghiên cứu ngay trong giai đoạn
phân tích, thiết kế và xây dựng hệ.
Quản lý nhiều bản sao là giải pháp kỹ thuật bao gồm tập hợp các thông tin
được nhân bản từ một đối tượng thông tin và các chương trình quản lý chúng
trong môi trường phân tán.
Các giải thuật này là cơ sở chủ yếu cho các giải pháp đảm bảo sự gắn bó
tất yếu nhờ dấu, nhờ bộ tuần tự tuần hoàn và đảm bảo sự gắn bó mạnh cho các hệ
thống đồng nhất.
Nội dung quản lý nhiều bản sao là các giải pháp cho phép tự động hóa các
công việc:
• Kiểm tra tính hợp thức của truy cập thông tin
• Khôi phục thông tin
• Cập nhật thông tin
• An toàn cho các bản sao
• Sử dụng cho các bộ nhớ, đĩa
• Chuyển các bản loại bỏ vào vùng có thể khôi phục
. . .
Tiểu luận này sẽ tập trung giới thiệu hệ thống nhiều bản sao và các thao
tác đọc ghi.
Trang 1
H PHÂN TÁNỆ V n đ nhi u b n sao trong đi u ki n truy c p l nấ ề ề ả ề ệ ậ ớ
CHƯƠNG I
VẤN ĐỀ NHIỀU BẢN SAO
TRONG ĐIỀU KIỆN TRUY CẬP LỚN
I. VẤN ĐỀ NHÂN BẢN CÁC ĐỐI TƯỢNG DỮ LIỆU
Khi nghiên cứu về hệ phân tán chúng ta thấy rằng thời gian truy cập trung
bình vào thông tin trong hệ phân tán có thể được rút ngắn, trong một số trường
hợp, nhờ vào phương pháp nhân nhiều bản và được gọi là nhân nhiều bản sao của

Một đối tượng được đưa vào trên một trạm xác định và được quản lý bởi
một Server cục bộ trên trạm này.
Khi một tiến trình ở xa muốn sử dụng đối tượng, nó phải bắt đầu bằng yêu
cầu Server cho một bản sao thông qua hệ thống viễn thông. Sau khi sử dụng
xong, tiến trình phải gửi lại cho Server một phiên bản đã được sửa đổi của đối
tượng.
* Các trường hợp thể hiện trong hình I.1 và hình I.2 xét theo chức năng là
giống nhau. Đó là trường hợp một bản duy nhất của đối tượng là một đặc quyền
Trang 3
L
B
cb
B
cb
L
Bộ xử lý
Bộ nhớ cục bộ
(e)
Máy client
B
ch
Bộ nhớ chung
(e)
L
HỆ THỐNG VIỄN THÔNG
Máy Server
H PHÂN TÁNỆ V n đ nhi u b n sao trong đi u ki n truy c p l nấ ề ề ả ề ệ ậ ớ
Trường hợp 2: Thể hiện tính cân đối giữa các người sử dụng tài nguyên
thông tin của mạng
Hình I.3. Hệ thống đối xứng

e
e
e
e
e
e
e
… …
L
L
L
L
L
L
H PHÂN TÁNỆ V n đ nhi u b n sao trong đi u ki n truy c p l nấ ề ề ả ề ệ ậ ớ
- Tồn bộ giao dịch thay đổi bản sao của đối tượng cần phải chép lại càng
sớm càng tốt thay đổi đó trên tất cả các bản sao khác.
- Việc cập nhật tức thì của tất cả các bản sao là khơng cần thiết.
Căn cứ theo u cầu thứ nhất, trong khi thực hiện giao dịch, khơng có bất
kỳ sao chép nào khác được thực hiện. Sau khi thực hiện xong, tất cả các bảo sao
hồn tồn giống nhau.
Đối với u cầu thứ hai, việc cập nhật tức thời là khơng quan trọng, nhưng
ta lại đặt ra rằng tất cả các bản sao của đối tượng bị thay đổi trở thành giống nhau
sau một khoảng thời gian xác định.
Trong tất cả các trường hợp, một giao dịch tham chiếu trạng thái một đối
tượng, thực hiện xuất phát từ một trạm trên bản cục bộ, cần phải cung cấp:
- Hoặc là một giá trị cập nhật của tất cả các thay đổi diễn ra trước tham
chiếu
- Hoặc là một giá trị đã cũ, nhưng lại là giá trị được cập nhật ở thời điểm
trước đó.

b
11
b
11
S
1
S
1
b
21
b
21
b
22
b
22
…
b
2m
b
2m
S
2
S
2
b
n1
b
n1
b

e12 = e22 = = en2

e1m = e2m = = enm
Giả sử với trường hợp có n bản sao b
1
, b
2
, …, b
n
của đối tượng e, để tham
chiếu đến e, cần phải thực hiện giao dịch:
Để 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ừ.
* Nhược điểm căn bản của giải pháp này là rất yếu về song song giữa các
phép toán cập nhật. Ta có thể áp dụng các ràng buộc toàn vẹn yếu hơn.
II.2. THUẬT TOÁN ĐẢM BẢO SỰ GẮN BÓ YẾU NHỜ DẤU:
Trang 6
Để cho i:=1 đến n thực hiện việc v_viet(e
i
)
<Thực hiện các cập nhật và chép chúng vào tất cả các bản>
Để cho i:=1 đến n thực hiện giai_phong(e
i
)
H PHÂN TÁNỆ V n đ nhi u b n sao trong đi u ki n truy c p l nấ ề ề ả ề ệ ậ ớ
II.2.1. NGUYÊN LÝ:
Tập hợp các yêu cầu cập nhật được sắp xếp theo cùng một kiểu trên tất cả
các trạm nhờ cơ chế dấu. Theo đó mỗi một yêu cầu được phát đi cho tập hợp các
trạm. Trên mỗi trạm, tồn tại một tiến trình Server đảm nhận nhiệm vụ tiếp nhận
các yêu cầu theo trật tự của dấu. Điều đó cho phép có được một sự gắn bó yếu

1 Việc đột nhiên biến mất đi một trạm nào đó phải được các trạm
khác nhận biết tự động.
2 Việc phát một thông điệp là một phép toán không chia cắt được
Trang 7
H PHÂN TÁNỆ V n đ nhi u b n sao trong đi u ki n truy c p l nấ ề ề ả ề ệ ậ ớ
nữa. Đó là một thông điệp hoặc là tất cả đều phải nhận được hoặc
là không trạm nào nhận được cả.
Vì vậy, việc tuân thủ hai điều kiện trên đặt ra cho chúng ta tình hình là
nếu điều kiện đầu tiên có thể được khống chế, thì điều kiện thứ hai rất khó đảm
bảo.
II.3. SƠ LƯỢT THUẬT TOÁN ĐẢM BẢO SỰ GẮN BÓ YẾU NHỜ BỘ
TUẦN TỰ TUẦN HOÀN.
II.3.1. NGUYÊN LÝ:
Trước khi phát một yêu cầu, một trạm nào đó cần phải kết hợp với nó một
số thứ tự được cấp từ bộ tuần tự tuần hoàn. Các yêu cầu được tiếp nhận tại mỗi
trạm theo cùng một trật tự thống nhất. Điều đó giúp ta có được một sự gắn bó
yếu. Cần quan tâm rằng cơ chế phân phối các số dựa trên nền tảng tổ chức các
trạm theo kiểu vòng tròn ảo.
II.3.2. TRIỂN KHAI HỆ ỔN ĐỊNH:
Bộ tuần hoàn tự cung cấp cho mỗi một yêu cầu số sắp tới còn chưa dùng,
giả sử đó là T. Khi đến phiên của trạm nhận bộ tuần tự, nó yêu cầu một số lượng
n số đúng bằng số lượng các yêu cầu cập nhật đang chờ trên trạm này. Các số
này là:
T, T + l , … , T + n - 1
Nó tiếp tục chuyển bộ tuần tự cho trạm kề liền sau nó và số sắp tới chưa
dùng đến là T+n.
Khi một trạm đã có số, nó phát yêu cầu cập nhật cùng với số này. Trên
mỗi trạm, các cập nhật được thực hiện bằng cách tiếp nhận các yêu cầu cùng các
số liên tiếp nhau. Để xác định yêu cầu sắp đến cần phải xử lý, mỗi trạm một duy
trì một biến chứa số V được phối hợp với yêu cầu xử lý cuối cùng. Các yêu cầu

II.4.1. NGUYÊN LÝ:
Tập hợp bao gồm các trạm được tổ chức theo kiểu vòng tròn ảo. Các cập
nhật được thực hiện theo hai thì:
1. Thống nhất giữa các trạm
2. Thực hiện cập nhật
 Do vây, thuật toán này đảm bảo một sự gắn bó mạnh. Nếu có nhiều yêu
cầu cập nhật diễn ra đồng thời thì ta phải có quy tắc để có thể quyết định yêu cầu
nào được tiếp nhận và thỏa mãn. Nhằm phục vụ cho ý tưởng đó, ta thường hay sử
dụng dấu phối hợp cho mỗi cập nhật và ta xử lý yêu cầu có thời gian dấu lâu
nhất.
II.4.2. KHAI TRIỂN HỆ ỔN ĐỊNH:
Trạng thái có thể của mỗi trạm là:
STT Trạng thái Giải thích
1 Nghỉ ngơi
Trạm không thực hiện cập nhật nào cả.
2 Hoạt động
Trạm đã nhận một yêu cầu cập nhật cục bộ
mà yêu cầu này đã được truyền cho các trạm
khác để kiểm tra.
3 Thụ động
Trạm đã đồng ý cho một cập nhật và chờ trật
tự tương ứng.
Trang 9
H PHÂN TÁNỆ V n đ nhi u b n sao trong đi u ki n truy c p l nấ ề ề ả ề ệ ậ ớ
4 Cập nhật
Trạm đang trong tình trạng chuyển của cập
nhật, trong khi đó tất cả các yêu cầu khác
truyền đến đều được lưu trữ. Chúng sẽ được
xử lý khi quay về một trong các trạng thái
khác.

mạng con độc lập; mỗi mạng tiếp tục hoạt động như là hệ cục bộ. Dẫu rằng các
bản sao tạo nên mạng con vẫn duy trì trạng thái gắn bó, sự hợp nhất lại chúng lại
Trang 10
H PHN TN V n nhi u b n sao trong i u ki n truy c p l n
l vn khỏ nan gii. Ta ch cú th trỏnh c hin tng ny bng cỏch s
lng cỏc trm nh hn hay bng a s tuyt i ca h khi s.
CHNG II:
THUT TON X Lí CC THAO TC C
CC THAO TC C GHI
I. GII THUT QUN Lí NHIU BN SAO - THUT TON X Lí
CC THAO TC C, CC THAO TC C - GHI.
Vic x lý trng thỏi iu khin do trm nhn tin hnh trờn c s tham
chiu thụng tin trong bn iu khin v theo yờu cu th hin trong hỡnh II.1.
Hỡnh II.1. Trỡnh t thc hin cp nht bn iu khin
Sau khi hon thnh trn vn cụng vic, trm nhn tin hnh phỏt thụng
ip n ton b cỏc trm ca h thng cp nht vo bn iu khin, ng thi
t ng cp nht vo bn cc b ca mỡnh.
Trang 11
Thực hiện việc cập nhật thông tin
trên bản điều khiển B
caithen(B)
Khóa bản điều khiển B
Mở khóa bản điều khiển
giaiphong(B)
Capnhat(B)
Bắt đầu
X Lí THễNG
IP
X Lí THễNG
IP


S

S

S

H PHÂN TÁNỆ V n đ nhi u b n sao trong đi u ki n truy c p l nấ ề ề ả ề ệ ậ ớ
Hình II.2. Sơ đồ tổng quát xử lý nhiều bản sao
Khi cập nhật, giải thuật GT
l
, l=1 P được thực hiện bởi trạm 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.
Việc phát hiện và xử lý lỗi trong quá trình xử lý được tiến hành ngay sau
khi trạm nhận được yêu cầu cập nhật. Nếu mọi cố gắng sửa lỗi không thể thực
hiện có kết quả, thì thông điệp sẽ được phát đi để yêu cầu trạm gửi phát lại thông
tin. Trong trường hợp công việc cập nhật kết thúc tốt đẹp, một thông điệp khẳng
định cũng được phát đi bởi trạm nhận. Sau khi phát đi thông điệp, trạm gửi
chuyển sang trạng thái chờ thông điệp mới, còn trạm nhận thông điệp chỉ chuyển
sang trạng thái chờ khi đã nhận đủ các thông điệp khẳng định.
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ư trong hình sau đây:
Trang 12
1
1
TIẾP CẬN YÊU CẦU CẬP NHẬT ĐẾN TỪ SERVER HAY WORKSTATION.
KIỂM TRA, XỬ LÝ LỖI VÀ CHUẨN BỊ CÁC THAM SỐ KỸ THUẬT
TIẾP CẬN YÊU CẦU CẬP NHẬT ĐẾN TỪ SERVER HAY WORKSTATION.
KIỂM TRA, XỬ LÝ LỖI VÀ CHUẨN BỊ CÁC THAM SỐ KỸ THUẬT

TỒN TẠI
BẢN SAO
TRUY CẬP THÔNG
TIN VỀ CẤU TRÚC
TRUY CẬP THÔNG
TIN VỀ CẤU TRÚC
XÁC ĐỊNH ĐỘ DÀI
CỦA INFORMATION
XÁC ĐỊNH ĐỘ DÀI
CỦA INFORMATION
HỢP THỨC
PHÁT THÔNG ĐIỆP
CHO TRẠM GỬI
PHÁT THÔNG ĐIỆP
CHO TRẠM GỬI
Đ
S
Đ
TRẠNG THÁI
VẬT LÝ [O/I]
S
PHÉP ĐẶC
BIỆT
TRẠNG THÁI CHỜ
TRẠNG THÁI CHỜ
S Đ
Đ
S
OK2
S

KẾT THÚC
H PHÂN TÁNỆ V n đ nhi u b n sao trong đi u ki n truy c p l nấ ề ề ả ề ệ ậ ớ
Hình II.4. Sơ đồ xử lý cập nhật nhiều bản sao
II. KẾT LUẬN:
Vấn đề cập nhật các bản sao thông tin của cùng một đối tượng dùng chung
trong môi trường phân tán đã được nghiên cứu khá rộng rãi và đã được ứng dụng
vào thực tế xây dựng các ứng dụng lớn như thương mại điện tử, chính phủ điện
tử Tuy vậy, trong khuôn khổ tiểu luận này chỉ nêu lên những vấn đề mang tính
nguyên lý. Thuật toán xử lý các thao tác đọc, các thao tác đọc-ghi trên không chỉ
chỉ đảm bảo hệ thống hoạt động với tốc độ bình quân chấp nhận được, ổn định,
tin cậy mà quan trọng hơn cả là phải đảm bảo tính gắn bó của dữ liệu trong các
bản sao.
Mô hình hệ thống quản lý nhiều bản sao giống nhau trên môi trường phân
tán và các giải thuật được nghiên cứu trên đã đáp ứng các yêu cầu của một hệ
thống phức tạp với lượng thông tin lớn cần phải xử lý. Nó được ứng dụng như là
các nguyên lý cơ bản cho các hệ thống tệp tin phân tán, các cơ sở dữ liệu phân
tán hiện nay.
Trang 14
H PHÂN TÁNỆ V n đ nhi u b n sao trong đi u ki n truy c p l nấ ề ề ả ề ệ ậ ớ
TÀI LIỆU THAM KHẢO
[1] Hệ phân tán – TS. Lê Văn Sơn, Nhà xuất bản Đại học quốc gia TP.
Hồ Chí Minh.
[2] Tạp chí khoa học và công nghệ ĐHĐN số 1 năm 2003.
[3] Nguyên lý các hệ cơ sở dữ liệu – Sách dịch Jeffery Ullman – Nhà
xuất bản thống kê.
[4] Distributed Systems (
Concepts and Design) –
George
Coulouris, Jean Dollimore & Tim Kindberg.
Trang 15