1
1
TI U LU NỂ Ậ
TI U LU NỂ Ậ


H TIN H C PHÂN TÁNỆ Ọ
H TIN H C PHÂN TÁNỆ Ọ
N i dung Lý ộ thuy tế
HOÀN THI N K THU T M B O C TÍNH TOÀN Ệ Ỹ Ậ ĐẢ Ả ĐẶ
V N TRONG H TIN H C PHÂN TÁNẸ Ệ Ọ
N i dung bài t pộ ậ
CH NG MINH NGUYÊN T C GIAO D CH HAI PHAỨ Ắ Ị
CBHD: PGS TS. Lê Văn Sơn
HVTH: Nguyễn Vũ
2
CÁC N I DUNG CHÍNHỘ
CÁC N I DUNG CHÍNHỘ
Chương 1 MỘT SỐ KHÁI NIỆM CHUNG

Khái niệm toàn vẹn dữ liệu

Khái niệm giao dịch

Một số tính chất của giao dịch

Trật tự hoá các tác động
Chương 2 ĐẶC TÍNH TOÀN VẸN TRONG HỆ TIN HỌC PHÂN TÁN
KỸ THUẬT GIAO DỊCH 2 PHA

Kỹ thuật then cài


Giao dịch hai pha

Quản lý gắn bó các giao dịch

Sử dụng giao dịch hai pha
KỸ THUẬT THỨ TỰ DẤU

Nội dung kỹ thuật thứ tự dấu

Giải thuật thứ tự dấu

Trật tự hoá thứ tự dấu
BÀI TẬP
Chương 3 PHÁT TRIỂN PHƯƠNG PHÁP ĐẢM BẢO GẮN BÓ DỮ LIỆU
TRONG ĐIỀU KIỆN CÓ SỰ CỐ CỦA CÁC HỆ THỐNG THÔNG TIN ĐĂNG KÝ
TRÊN MẠNG INTERNET/INTRANET
3
Ch ng 1ươ
Ch ng 1ươ
CÁC KHÁI NI M CHUNGỆ
CÁC KHÁI NI M CHUNGỆ

Khái niệm toàn vẹn dữ liệu

Khái niệm giao dịch

Một số tính chất của giao dịch

Trật tự hoá các tác động

4
KHÁI NI M TOÀN V N D LI UỆ Ẹ Ữ Ệ
KHÁI NI M TOÀN V N D LI UỆ Ẹ Ữ Ệ

Đặc tính toàn vẹn dữ liệu trong hệ tin học phân tán thể hiện
tính bền vững, tính đúng đắn, tính nhất quán của thông tin.

Toàn vẹn dữ liệu tuân theo các luật của một tổ chức, hệ
thống. Các luật này được gọi là các ràng buộc toàn vẹn.

Trạng thái của hệ thoả mãn các ràng buộc toàn vẹn gọi là
trạng thái gắn bó.

Mục tiêu cuả đặc tính toàn vẹn dữ liệu là duy trì hệ thống
luôn trong trạng thái gắn bó
5
KHÁI NI M GIAO D CHỆ Ị
KHÁI NI M GIAO D CHỆ Ị

Là chương trình duy nhất thực hiện từ một trạng thái gắn
bó và đưa hệ đến một trạng thái gắn bó khác.

Mỗi giao dịch được cấu tạo từ một dãy các tác động
6
M T S TÍNH CH T C A GIAO D CHỘ Ố Ấ Ủ Ị
M T S TÍNH CH T C A GIAO D CHỘ Ố Ấ Ủ Ị

Tính nguyên tử(Atomic) : một giao dịch hoặc là được
thực hiện trọn vẹn hoặc là không thực hiện gì cả.


Đặc tính gắn bó(Consistent): giao dịch chuyển hệ thống
phân tán từ trạng thái gắn bó này sang trạng thái gắn bó
khác.

Đặc tính cách ly (Isolation): các giao không biết được sự
thực hiện của các giao dịch đồng thời khác. Kết quả của
giao dịch này không ảnh hưởng đến giao dịch khác.

Tính bền vững (Durability) : Sau một giao dịch kết thúc
thành công, các thay đổi mà nó tạo ra được bảo toàn ngay
cả khi hệ thống bị sự cố
7
TR T T HOÁ TÁC NGẬ Ự ĐỘ
TR T T HOÁ TÁC NGẬ Ự ĐỘ
Xét tập hợp các giao dịch M = {T1, T2,…, Tn}, mỗi một giao dịch được
cấu tạo từ một dãy các tác động

Việc thực hiện toàn bộ giao dịch M tương đương với việc thực
hiện một dãy S các tác động thuộc các giao dịch này, như S = (a1,
a2,…, an)

Trong số các trật tự hoá của một tập hợp các giao dịch phải tách ra
cho được những cái phục vụ trạng thái gắn bó dữ liệu, gọi là trật
tự hoá gắn bó
Trật tự hoá S được gọi là hợp thức nếu thoả mãn các điều sau:

Một đối tượng được cài then chia sẽ thì sẽ không có then cài loại
trừ nào được thực hiện cho đến khi mở then.

Một đối tượng được cài then loại trừ thì sẽ không có then cài nào

được thực hiện cho đến khi mở then .
8
Chương 2. ĐẶC TÍNH TOÀN VẸN DỮ LIỆU
Chương 2. ĐẶC TÍNH TOÀN VẸN DỮ LIỆU
KỸ THUẬT GIAO DỊCH 2 PHA
KỸ THUẬT GIAO DỊCH 2 PHA

Kỹ thuật then cài

Giao dịch hai pha

Xử lý các sự cố

Quản lý gắn bó các giao dịch
9
K thu t then càiỹ ậ
K thu t then càiỹ ậ
Cơ chế then cài cho phép một giao dịch có thể giải phóng đối tượng
mà nó cài then. Có hai loại then cài chính là then cài loại trừ W và
then cài chia sẽ R:

Nếu một giao dịch A thực hiện cài then loại trừ W lên một đối
tượng thì một yêu cầu cài then chia sẽ R từ một giao dịch B
khác sẽ đưa giao dịch B rơi vào trạng thái chờ cho cho đến khi
A mở then.

Nếu giao dịch A thực hiện then cài chia sẽ R thì giao dịch B
cũng có thể gán một then cài chia sẽ , nhưng B sẽ rơi vào trạng
thái chờ nếu nó yêu cầu một then cài loại trừ W
10

Giao d ch hai phaị
Giao d ch hai phaị
Xét một giao dịch hình thành hợp thức bằng cách
kiểm tra hai điều kiện:
Điều kiện 1

Toàn bộ đối tượng bị cài then vẫn ở trong tình trạng
cài then cho đến cuối giao dịch.
Điều kiện 2

Không có then cài nào có thể diễn ra tiếp theo một
then cài khác trong cùng một giao dịch.
 Giao dịch 2 pha
11
Giao d ch hai phaị
Giao d ch hai phaị
Then cài
b i Tiở
Th i gianờ
Pha cài then Pha m thenở

N u m t tr t t hoá h p th c S tho mãn i u ki n ế ộ ậ ự ợ ứ ả đề ệ
giao d ch hai pha thì tr t t hoá ó là g n bóị ậ ự đ ắ
12
X LÝ S C Ử Ự Ố
X LÝ S C Ử Ự Ố
Nếu một tiến trình bị sự cố trong lúc thực hiện một giao dịch thì
trạng thái của hệ xuất phát từ việc thực hiện từng phần đó chắc chắn
sẽ không còn gắn bó.


Giao dịch T bắt buộc phải được thực hiện một cách trọn vẹn

Nếu có sự cố diễn ra thì bắt buộc nó phải quay về điểm xuất phát
Đòi hỏi giao dịch có các đặc tính toàn vẹn như sau

Nếu một tiến trình bị sự cố trước khi kết thúc T nhưng lại sau các thay đổi
cần thiết của T, trạng thái của hệ là gắn bó

Nếu một tiến trình bị sự cố trước khi diễn ra các thay đổi của T, trạng thái
của hệ là gắn bó

Nếu một tiến trình bị sự cố giữa các thay đổi của T, trạng thái của hệ là
không gắn bó
13
X LÝ S CỬ Ự Ố
X LÝ S CỬ Ự Ố
Gắn bó
1
2
3
Trước khi cập nhật (thay đổi)
Sau khi cập nhật (thay đổi)
Không gắn bó
14
Ch ng 2 C TÍNH TOÀN V N D LI U (tt)ươ ĐẶ Ẹ Ữ Ệ
Ch ng 2 C TÍNH TOÀN V N D LI U (tt)ươ ĐẶ Ẹ Ữ Ệ
K THU T TH T D UỸ Ậ Ứ Ự Ấ
K THU T TH T D UỸ Ậ Ứ Ự Ấ

N i dung k thu t th t d uộ ỹ ậ ứ ự ấ


Gi i thu t th t d uả ậ ứ ự ấ

Tr t t hoá th t d uậ ự ứ ự ấ
15
K thu t óng d uỹ ậ đ ấ
K thu t óng d uỹ ậ đ ấ

Mỗi giao dịch được gán một số id duy nhất dựa trên thời
gian mà giao dịch được đưa vào hệ thống.

T1 T2, nếu T1 có dấu nhỏ hơn dấu của T2 ký hiệu
ts(T1)<ts(T2)

Mọi tác động đọc ghi đều được đọc ghi theo thứ tự dấu
của nó.

Số id này có thể là giá trị một bộ đếm hoặc là của đồng
hồ hệ thống
16
Gi i thu t th t d uả ậ ứ ự ấ
Gi i thu t th t d uả ậ ứ ự ấ
Khi giao dịch T đọc đối tượng e :
if tg(T) > tg_doc(e)
then (1) thực hiện tác động đọc
(2) tg(T) = max {tg_doc(e),tg(T)}
else huỷ
Khi giao dịch T ghi đối tượng e:
if tg(T) >= tg_doc(e) and tg(T) >= tg_viet(e)
then (1) thực hiện tác động đọc

(2) tg(T) = max {tg_viet(e),tg(T)}
else huỷ
17
Trật tự hóa thứ tự dấu
Trật tự hóa thứ tự dấu
Nếu S là một trật tự hoá có được bằng cách thực hiện theo một trật tự
thứ tự dấu thời gian, S là trật tự hoá gắn bó.
Chứng minh:
Giả sử rằng giao dịch Ti trước giao dịch Tj trong đồ thị phụ thuộc P(S), ký hiệu Ti

Tj.

⇒

∃
các tác động phụ thuộc pi[e], qj[e] trong trật tự hoá S,

khi đó pi[e] < qj[e] (quan hệ xảy ra trước, tác động pi[e] xảy ra trước
qj[e])

Theo quy tắc thứ tự dấu ta có ts(Ti) < ts(Tj)
Giả sử rằng P(S) là đồ thị lặp, ta có:

T1
→
T2
→
Tn
→
T1


Theo quy tắc thứ tự dấu : ts(T1)<ts(T2) <ts(T3)…<ts(Tn)<ts(T1)

Điều này mâu thuẫn
Vậy P(S) là đồ thị phụ thuộc không lặp, do đó ta có S là trật tự hoá gắn bó
18
Bài t pậ
Bài t pậ
Cho một tập hợp các giao dịch M = {T1,T2,…,Tn}.
Phầ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 giao dịch hai pha. Hãy chỉ
ra rằng toàn bộ trật tự hoá hợp thức S của M là gắn bó.
Phần 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. Hãy chỉ ra
rằng toàn bộ trật tự hoá hợp thức S của M là gắn bó
19
Bài tập – Phần 1
Bài tập – Phần 1
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
Ta chứng minh bổ đề: 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)
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ó:

l(T1) < l(T2) < … < l(Tn) < l(T1)
Điều này là vô lý nên P(S) phải là đồ thị không lặp  S là trật tự
hoá gắn bó
20
Bài t p – Ph n 2ậ ầ
Bài t p – Ph n 2ậ ầ
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
Ta chứng minh bổ đề: 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)
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  S là trật tự hoá
gắn bó
21