Báo cáo tiểu luận môn Hệ phân tán – Kỹ thuật bảo đảm tính toàn vẹn dữ liệu
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
KHOA CÔNG NGHỆ THÔNG TIN

TIỂU LUẬN MÔN HỌC
HỆ TIN HỌC PHÂN TÁN
GVHD : PGS. TS. Lê Văn Sơn
HVTH : Đinh Duy Khánh
LỚP : Cao học khóa 11 (2012 - 2014)
Lời nói đầu
Nhóm 1: Vũ Thị Thanh Huyền – Nguyễn Cửu Thị Ánh Mai Trang 1
Đà Nẵng, tháng 7/2014
Báo cáo tiểu luận môn Hệ phân tán – Kỹ thuật bảo đảm tính toàn vẹn dữ liệu
Ngày nay, các thông tin quan trọng được lưu trữ trên mạng càng nhiều và thường
xuyên được truy nhập từ các máy tính khác trong mạng. Chính những điều này đã và
đang mang lại những lợi ích to lớn cho việc chia sẻ tài nguyên, kết nối trong các tổ chức
doanh nghiệp. Tuy nhiên, do đặc điểm nhiều người sử dụng và phân tán về mặt địa lý nên
việc bảo vệ tài nguyên đó tránh khỏi mất mát, xâm phạm (vô tình hay cố ý) trong môi
trường mạng phức tạp hơn nhiều so với một máy tính đơn lẻ, một người sử dụng. Chính vì
thế công tác bảo đảm đặc tính toàn vẹn dữ liệu và công tác an toàn bảo mật cho các hệ
thống phân tán thường là phức tạp và ngày càng trở nên quan trọng.
Vì vậy, việc nghiên cứu và phát triển các phương pháp đảm bảo gắn bó dữ liệu trong
môi trường phân tán đến nay đã có một số thành công đáng kể. Trong bài báo cáo của
nhóm chúng tôi, chúng tôi xin trình bày đề tài “Hoàn thiện kỹ thuật đảm bảo đặc tính
toàn vẹn dữ liệu trong hệ tin học phân tán”.
Phần 1 – Trình bày nội dung lý thuyết về “Hoàn thiện kỹ thuật đảm bảo đặc
tính toàn vẹn dữ liệu trong hệ tin học phân tán”.
Nhóm 1: Vũ Thị Thanh Huyền – Nguyễn Cửu Thị Ánh Mai Trang 2
Báo cáo tiểu luận môn Hệ phân tán – Kỹ thuật bảo đảm tính toàn vẹn dữ liệu
1. Đặt vấn đề.
Vấn đề gắn bó dữ liệu trong các hệ thống phân tán nói chung và các hệ thống thông tin

đồng nghĩa với việc nghiên cứu đưa ra các giải pháp kỹ thuật duy trì trạng thái gắn bó của
hệ tức là nghiên cứu các kỹ thuật duy trì hệ thống luôn thoả mãn các ràng buộc toàn vẹn.
Hay nói cách khác, duy trì hệ thống luôn hoạt động trong điều kiện chuyển từ trạng thái
gắn bó này sang trạng thái gắn bó khác.
Nhóm 1: Vũ Thị Thanh Huyền – Nguyễn Cửu Thị Ánh Mai Trang 3
Báo cáo tiểu luận môn Hệ phân tán – Kỹ thuật bảo đảm tính toàn vẹn dữ liệu
3. Sự gắn bó thông tin
Ta có một tập thông tin nào đó có thể truy cập bởi một tập hợp các tiến trình. Số lượng
đối tượng thông tin có thể truy cập và số lượng tiến trình có nhu cầu thông tin là cố định.
Hệ này phát triển rời rạc theo thời gian, giữa các điểm xác định, ta có thể nhận biết được
các trạng thái thực của chúng, nghĩa là các giá trị của đối tượng và ngữ cảnh thực hiện của
các tiến trình. Hệ như vậy hoạt động với độ ổn định tuyệt vời.
Các điều kiện giả định trên so với hệ thực tế có những điểm khác nhau căn bản sau đây :
STT So sánh
1
Các đối tượng và các tiến trình có thể tạo lập và hủy bỏ có tính chất động
trong suốt quá trình tồn tại của hệ
2
Các đối tượng và các tiến trình có thể được phân tán trên các trạm khác nhau
liên hệ với nhau qua hệ thống viễn thông. Do vậy, ta không thể xác định
trạng thái thời điểm của hệ vì lý do độ trễ đường truyền giữa các trạm và tính
không tương thích giữa các điểm quan sát trong các trạm đó.
3
Hệ thống viễn thông và các tiến trình là các đối tượng có thể xảy ra sự cố kỹ
thuật.
4. Tác động và giao dịch
Trong hệ phân tán, thông thường người ta hay sử dụng khái niệm giao dịch như là thực
thể sử dụng.
Giao dịch là phép toán hợp thành một lôgic hoàn chỉnh mà việc triển khai nó có thể dẫn
đến thực hiện một tiến trình duy nhất hay nhiều tiến trình được định vị trên các trạm khác

= (a
11
, a
12
, a
13
, a
14
) và T
2
= (a
21
, a
22
, a
23
, a
24
). Một trật tự hóa M = {T1, T2}
được thể hiện theo một trong nhiều cách sau:
S1 = a
11
, a
21
, a
12
, a
22
, a
23

Cho Stt là một trật tự hoá tuần tự của tập hợp các giao dịch M và S là một trật tự hoá bất
kỳ của M. Hiệu ứng của S giống với hiệu ứng của Stt, nếu hai điều kiện sau đây được
triển khai :
Điều kiện 1
Để cho mỗi đối tượng e, các cập nhật biểu hiện trong cùng một trật tự trong S và Stt.
Điều kiện 2
Hãy xem xét hai cập nhật kế tiếp nhau của một đối tượng e trong số các trật tự hoá, và
các cập nhật tương ứng của e trong trật tự hoá khác. Giữa hai cập nhật này, ta tham
khảo cùng các đối tượng trong hai trật tự hoá này trong cùng trật tự hay không.
Nhóm 1: Vũ Thị Thanh Huyền – Nguyễn Cửu Thị Ánh Mai Trang 5
Báo cáo tiểu luận môn Hệ phân tán – Kỹ thuật bảo đảm tính toàn vẹn dữ liệu
Các điều kiện nêu trên đây là các điều kiện đủ cho việc đánh giá tương đương. Ta chỉ có
thể hoán vị, không thay đổi hiệu ứng của một trật tự hoá, hoặc là các thao tác đọc đối
tượng có tính chất liên tiếp hoặc là các thao tác gán các đối tượng khác nhau một cách
liên tục.
Trật tự hoá S được gọi là hợp thức nếu thoả mãn các điều sau:
Đối tượng được một giao dịch cài then theo kiểu chia sẻ không bị bất cứ then cài nào theo
kiểu loại trừ của các giao dịch khác.
Một đối tượng bị cài then theo kiểu loại trừ thì không bị bất kỳ then cài mới nào nữa.
Do vậy, mọi cố gắng cài then không phù hợp với các điều kiện tương hỗ nêu trên đều phải
chờ (bị làm chậm lại) cho đến khi mở then.
Để cho trật tự hoá S, ta định nghĩa một quan hệ phụ thuộc giữa các giao dịch :
Cho T1 và T2 là hai giao dịch của M, e là đối tượng của hệ. Ta nói rằng T2 phụ thuộc T1
qua trung gian của e, ký hiệu bằng (T1,e,T2), với các điều kiện sau đây được kiểm tra:
- Một tác động của T1 tham chiếu e và một tác động sau T2 thay đổi e.
- Một tác động của T1 thay đổi e và một tác động sau T2 tham chiếu e.
- Một tác động của T1 thay đổi e và một tác động sau T2 thay đổi e mà e không
được thay đổi bởi một giao dịch khác giữa hai tác động T1 và T2. Thuật ngữ “ trước”
được hiểu theo nghĩa “ cái tiếp theo nó trong trật tự hoá S ”.
Để cho hai trật tự hoá có cùng một hiệu ứng thì điều kiện đủ là chúng phải cùng quan hệ

hình quan hệ hoặc các liên kết theo kiểu 1 – n, (n > 1) giữa các đối tượng trong mô hình
mạng
2. Ràng buộc hành vi (Behavioral Constraint) nhằm điều hòa các hoạt động của
các ứng dụng.
Trong quá trình nghiên cứu bài toán, các tác giả vận dụng phương pháp tổng quát đảm
bảo gắn bó dữ liệu và các ràng buộc toàn vẹn thông tin phục vụ công tác phân tích, thiết
kế hệ quản trị cơ sở dữ liệu cho hệ thống cơ sở dữ liệu đăng ký với thông tin gắn bó trong
điều kiện phân tán.
Để có thể khôi phục lại dữ liệu và trạng thái gắn bó thông tin của toàn hệ thống khi có
sự cố diễn ra, một trong những vấn đề quan trọng hàng đầu là cần phải xác định được
loại, bản chất và vị trí diễn ra sự cố mà từ đó nhận biết một cách tự động và chuyển đến
phương án giải quyết nào cho phù hợp. Bản chất (mã) sự cố và thủ tục giải quyết sự cố có
liên quan đến gắn bó được lưu trữ tại trung tâm hoặc phân tán trên các trạm của hệ đăng
ký phân tán. Trong trường hợp các thủ tục được phân tán, thì bản thân các thủ tục đó cũng
đòi hỏi phải có giải pháp đảm bảo gắn bó giống như dữ liệu bình thường.
Về tổng quan, các sự cố được chia làm hai loại chính là sự cố xảy ra do các trạm trên
hệ thống phân tán và sự cố do hệ thống viễn thông gây ra. Song để tiện lập trình giải
pháp, người ta cụ thể hoá ra thành bốn mức với các nguyên nhân tương ứng thể hiện
trong bảng 1.
Bảng các loại sự cố và nguyên nhân gây ra sự cố
TT Loại sự cố Tiếng Anh Nguyên nhân
1 Sự cố
giao dịch
Transaction
Failure
Do một lỗi nào đó trong bản thân giao dịch
gây nên. Ví dụ như dữ liệu nhập không
đúng hoặc do phát hiện ra một khóa gài
tiềm tàng hoặc hiện hữu
Sự cố

Do lỗi trong các thông điệp, các thông điệp
vô trật tự, thông điệp bị thất lạc hoặc không
phân phối thông điệp và sự cố khác liên
quan đến đường truyền.
Phương pháp tổng quát cho việc khắc phục bốn loại sự cố này được trình bày trong
bảng 2.
Bảng phương pháp tổng quát khắc phục sự cố
TT Loại sự cố Cách khắc phục
1 Sự cố giao dịch
[CKP
1
] + [CKP
2
] Hủy bỏ giao dịch, sau đó đặt lại cơ sở dữ
liệu về trạng thái của nó trước khi khởi động giao dịch này
2 Sự cố vị trí [CKP
2
] Thiết kế nghi thức ủy thác nguyên tử không bị
phong tỏa
3
Sự cố phương
tiện
[CKP
0
] Được xem như những vấn đề cục bộ của một vị trí,
vì vậy không xem xét trong trường hợp các hệ thống phân
tán
4
Sự cố đường
truyền

3. TPC-Server-App1, TPC-Server-App2, , TPC-Server-AppN là các RMI Server cài
đặt thuật toán 2PC tuyến tính (Linear Two Phase Commit - TPC)
4. TPCMonitorServer là một trình giám sát cho phép hiển thị quá trình dịch chuyển
của danh sách di chuyển [6] trong quá trình xử lý của các TPC-Server-Appi, i = 1,N
5. ConnectionPool là chương trình điều khiển các liên kết cơ sở dữ liệu dùng chung
6. Database1, Database2, , DatabaseN là các cơ sở dữ liệu quan hệ phân tán trên
mạng.
Mô tả hoạt động :
Các C
1
, C
2
, , C
n
là các Client truy cập vào Web Server bằng trình duyệt Web. Các yêu
cầu này đòi hỏi việc xử lý phải truy vấn đến các cơ sở dữ liệu phân tán. Do đó việc xử
lý thành công hay không phụ thuộc vào kết quả của tất cả các truy vấn này. Điều đó có
nghĩa là, xử lý sẽ thành công nếu tất cả các truy vấn đều thành công, ngược lại, xử lý sẽ
không thành công nếu có bất kỳ một truy vấn nào bị lỗi hoặc không thực hiện được.
Khi nhận được một yêu cầu từ các C
i
, i=1,n, các Servlet sẽ dựa vào yêu cầu này để
thành lập nên một danh sách các Database Server sẽ truy vấn và các câu lệnh SQL
tương ứng được thực hiện tại mỗi Server. Việc thành lập danh sách các câu lệnh SQL
truy vấn tại mỗi Database Server được dựa theo thứ tự ưu tiên SELECT, DELETE,
UPDATE, INSERT. Sau khi thành lập danh sách di chuyển, Servlet chuyển danh sách
di chuyển này cho TPC-Server-App đầu tiên trong danh sách di chuyển thông qua
phương thức gọi từ xa RMI.
Nhóm 1: Vũ Thị Thanh Huyền – Nguyễn Cửu Thị Ánh Mai Trang 9
Báo cáo tiểu luận môn Hệ phân tán – Kỹ thuật bảo đảm tính toàn vẹn dữ liệu

Đề bài: Cho một tập hợp các giao dịch M = {T
1
, T
2
, , T
n
}.
1. Giả sử rằng các giao dịch của M là hình thành tốt và thoả mãn các điều kiện (1)
của VI.3.1.3 (trang 261). Hãy chỉ ra rằng toàn bộ trật tự hóa hợp thức S của M là gắn bó.
2. Ta giả sử rằng các giao dịch của M là hình thành tốt và kiểm tra điều kiện (2)
của giao dịch hai pha trong VI.3.1.3. Hãy chỉ ra rằng toàn bộ trật tự hóa hợp thức S của M
là gắn bó.
1. Cơ sở lý thuyết:
Trạng thái của hệ thỏa mãn 1 tập các ràng buộc toàn vẹn gọi là trạng thái gắn bó
Tiến trình là 1 dãy thực hiện các giao dịch.
Giao dịch là chương trình duy nhất được thực hiện từ 1 trạng thái gắn bó dẫn hệ đến 1
trạng thái gắn bó khác
Một giao dịch được cấu tạo từ một dãy các tác động :
S(a
1
, a
2
, …, a
n
): 1 dãy các tác động thuộc giao dịch thuộc tập hợp các giao dịch
M{T
1
, T
2
,…… , T

theo kiểu tương tranh.
Một giao dịch có thể thực hiện 3 hàm nguyên thủy trên đối tượng e: v_doc(e);
v_viet(e); giai_phong(e)
2. Áp dụng giải bài tập
Cho 1 tập hợp các giao dịch M={T
1
, T
2
,…., T
n
}.
Câu 1. Giả sử rằng các giao dịch của M là hình thành tốt và thỏa mãn các điều kiện:
“Toàn bộ các đối tượng bị cài then vẫn ở trong tình trạng cài then cho đến cuối giao
dịch”. Hãy chỉ ra rằng toàn bộ trật tự hóa hợp thức S của M là gắn bó.
Giả sử ta có 1 trật tự hóa toàn phần trên M băng quan hệ “<”. Điều đó có nghĩa là T
i
< T
j
,
nếu tác động cuối cùng của T
i
trong S trước tác động cuối cùng của T
j
. Giả sử các tác
động T1 tác động lên n đối tượng A1, A2,…, An. Điều kiện trên có nghĩa là khí các tác
động của giao dịch T1 tác động lên hết các đối tượng A1, A2,…, An, thì sau đó T2 mới
được tác động lên các đối tượng này, tương tự như vậy cho đến Tn.
Một giao dịch T
i
đang thực hiện phép then cài trên một đối tượng e chính là dành

,……,T
n
}. Mỗi lần cần
tiến hành giao dịch trên đối tượng, thì đối tượng đó được giao dịch cài then. Tất cả các
giao dịch trên đối tượng này đều được thực hiện tuần tự (theo giả sử lúc ban đầu). Với hệ
phân tán, các tác động của các giao dịch trong tập hợp M có thể sử dụng song song nhưng
phải thỏa mãn điều kiện là: tác động cuối cùng của T
i
trong S trước tác động cuối cùng
của T
j
. Ngoài ra theo giả thuyết các giao dịch trong tập hợp M thỏa mãn điều kiện:”Toàn
bộ các đối tượng bị cài then vẫn ở trong tình trạng cài then cho đến cuối giao dịch”. Mà
mỗi đối tuợng chỉ được 1 giao dịch cài then và chỉ khi nào hoàn thành giao dịch đó thì đối
tượng mới được giải phóng then cài. Kết hợp cảc 2 điều kiện nêu trên thì tập hợp các tác
động S này có quan hệ phụ thuộc với S
seq.
. Vì vậy toàn bộ trật tự hóa của M là gắn bó.
Ta gọi tác động cuối cùng của giao dịch là l:
- Tác động cuối cùng của giao dịch Ti là l(Ti)
- Tác động cuối cùng của giao dịch Tj là l(Tj)
- Quan hệ “<” là trật tự hoá toàn phần trên M
Yêu cầu: Nếu Ti < Tj (quan hệ giao dịch Ti trước giao dịch Tj) trong trật tự hoá S thì l(Ti)
< l(Tj).
Chứng minh :
Ti < Tj trong trật tự hoá S nghĩa là: S = … pi(e) … qj(e) … ; p và q là các tác động của Ti
và Tj phụ thuộc qua đối tượng e.
S là trật tự hoá hợp thức và các giao dịch là hoàn thành tốt nên:
S = … pi(e) … li(e) … qj(e)…,lj(e)*)
Từ (*) kết hợp với điều kiện “Toàn bộ các đối tượng bị cài then vẫn ở trong tình trạng

seq
bởi
vì trong S gồm các tác động cập nhật sắp xếp tăng dần, các cập nhật này cũng tương
ứng với các then cài, tác động trước sẽ được mở then nhưng tác động kế tiếp chỉ được
mở then khi tác động trước đã đóng then theo điều kiện :”Không có then cài nào có
thể diễn ra tiếp theo 1 then cài khác trong cùng 1 giao dịch ”
Ta gọi tác động mở then đầu tiên là fu
- Tác động mở then đầu tiên của giao dịch Ti là fu(Ti)
- Tác động mở then đầu tiên của giao dịch Tj là fu(Tj)
Quan hệ “<” là trật tự hoá toàn phần trên M
Yêu cầu: Nếu Ti < Tj (quan hệ giao dịch Ti trước giao dịch Tj) trong trật tự hoá S thì
fu(Ti) < fu(Tj).
Chứng minh :
Ti < Tj trong trật tự hoá S nghĩa là: S = … pi(e) … qj(e) … ; p và q là các tác động của Ti
và Tj phụ thuộc qua đối tượng e.
S là trật tự hoá hợp thức và các giao dịch là hoàn thành tốt nên:
S = … pi(e) … ui(e) …uj(e) … qj(e)…; (*)
Từ (*) kết hợp với điều kiện (2) ta có: fu(Ti) < fu(Tj)
Gọi P(S) là đồ thị phụ thuộc của trật tự hoá S, ta giả sử rằng P(S) là đồ thị lặp, lúc đó ta
có:
T1 < T2 < … < Tn < T1
Theo bổ đề nêu trên ta có:
fu(T1) < fu(T2) < … < fu(Tn) < fu(T1)
Điều này là vô lý nên P(S) phải là đồ thi không lặp, điều này suy ra S là trật tự hoá gắn
bó. (Điều phải chứng minh)
Thông qua 2 điều kiện 1 và 2 trong VI.2.3, ta xác định được S và S
seq
tương đương.
Hay nói cách khá toàn bộ trật tự hóa hợp thức của một tập hợp các giao dịch hình
Nhóm 1: Vũ Thị Thanh Huyền – Nguyễn Cửu Thị Ánh Mai Trang 14

1.Đặt vấn đề 3
2.Khái niệm toàn vẹn dữ liệu 3
3.Sự gắn bó thông tin 4
4.Tác động và giao dịch 4
5.Tác động của sự cố đối với việc toàn vẹn dữ liệu 6
6.Phát triển giải pháp kỹ thuật đảm bảo gắn bó dữ liệu 8
Phần 2 – Bài tập 11
1.Cơ sở lý thuyết: 11
2.Áp dụng giải bài tập 12
Kết luận 16
Mục lục 18
Nhóm 1: Vũ Thị Thanh Huyền – Nguyễn Cửu Thị Ánh Mai Trang 18