Tiểu luận môn Hệ tin học phân tán
• Phép chuyển giá trị từ tài khoản này sang tài khoản khác được
xem như một tác động.
• Đọc và ghi một bản ghi là các tác động, nếu hệ quản lý các
tập tin đảm bảo tính không chia cắt được chúng.
I.3 Một số tính chất của giao dịch
Một giao dịch phải đảm bảo các đặc tính sau :
• Tính nguyên tử (Atomic) : đặc tính nguyên tử của giao dịch có ý nghĩa
rằng 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 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): mặc dù nhiều giao dịch có thể thực hiện đồng
thời, nhưng 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ố.
Ví dụ : Giao dịch chuyển khoản
Chuyển P đồng từ tài khoản A sang tài khoản B :
đọc(A) ;
nếu A>=P thì
A := A – P ;
viết(A) ;
đọc(B) ;
B := B + P ;
viết(B) ;
nếu không
<Thông báo số dư tài khoản A không đủ>
Kết thúc nếu
Giải thích các tính chất của giao dịch trên :
Tính nguyên tử: Nếu giao dịch lỗi sau bước 4 và trước bước 7, hệ thống
buộc phải huỷ bỏ toàn bộ các tác động trước đó để đảm bảo tính gắn bó dữ
liệu. Nếu không thì tổng của A và B bị thay đổi.
Tính gắn bó: Tổng của A và B không bị thay đổi bởi sự thực hiện của giao
dịch.
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
3/26
Tiểu luận môn Hệ tin học phân tán
Tính cách ly: giữa các bước 4 và 7, không được có giao dịch khác cập nhật
vào CSDL, hoặc hệ thống sẽ rơi vào trạng thái không gắn bó.
Tính bền vững: Khi giao dịch được hoàn thành, các cập nhật vào CSDL
phải được bảo toàn ngay cả khi hệ thống bị sự cố.
Cho một tập hợp giao dịch M={T
1
,T
2
…,T
n
} lần lượt được thực hiện bởi
các tiến trình độc lập p
1
,p
2
…,p
n
. việc thực hiện tuần tự có nghĩa là thực hiện tất
cả các giao dịch của M theo kiểu nối đuôi nhau và tuân thủ một trật tự nào đó.
Sự gắn bó của hệ được bảo toàn.
Nếu vì lý do hiệu quả, nhiều giao dịch được thực hiện song song thì sự gắn
bó không còn đảm bảo được nữa. Một yêu cầu khác nữa rất quan trọng là trong
quá trình thực hiện hệ phải đảm bảo cho các tác động không bị ngắt quãng.
Trong thực tế giao dịch là một chuổi các tác động như : đọc, ghi dữ liệu,
thực hiện các phép tính số học đơn giãn trong vùng làm việc riêng, hoặc là các
tác động như cài then, mở then…
I.4 Trật tự hoá các tác động
Trở lại với 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. Bằng các tác động không chia sẽ này,
toàn bộ việc thực hiện của tập hợp các giao dịch M bởi một tập hợp các tiến
trình tương tranh là 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) chẳng hạn. Trong trật tự tuân
thủ trật tự nội tại của từng giao dịch, dãy này bao gồm tất cả các tác động cấu
tạo nên các giao dịch M; mỗi một tác động chỉ xuất hiện một và chỉ một lần.
Một dãy như vậy gọi là trật tự hoá của tập hợp các giao dịch M.
Trong số các trật tự hoá của một tập hợp các giao dịch, điều rất quan trọng
là phải tách ra cho được những cái phục vụ trạng thái gắn bó dữ liệu và chúng
được gọi là trật tự hoá gắn bó.
Như vậy đặc tính quan trọng của trật tự hoá tương ứng với việc thực hiện
tuần tự của tập hợp các giao dịch hay còn gọi là trật tự hoá tuần tự. Nếu ta nắm
được các đặc trưng của các trật tự hoá tương đương với một trật tự hoá tuần tự
có nghĩa là cùng tác dụng như trật tự hoá tuần tự, thì ta đã có được điều kiện
đủ của sự gắn bó.
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.
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
4/26
Tiểu luận môn Hệ tin học phân tán
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.
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.
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 của T2 thay đổi
e.
• Một tác động của T1 thay đổi e và một tác động của 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 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 đượ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 hiệu ứng thì điều kiện đủ là chúng phải cùng
quan hệ phụ thuộc.
Do vậy, điều kiện đủ cho sự gắn bó của một trật tự hoá có thể phát biểu
như sau : Một trật tự hoá là gắn bó, nếu nó có cùng quan hệ phụ thuộc với một
trật tự tuần tự.
Đồ thị phụ thuộc: Để phân tích quan hệ phụ thuộc giữa các giao dịch
trong một trật tự hoá, ta xây dựng đồ thị phụ thuộc mà các nút của nó được
gán nhãn bởi tên của giao dịch và các cung là tên các đối tượng mà giao dịch
cập nhật trong quá trình thực hiện.
Để cho một trật tự hoá tuần tự, đồ thị này không có vòng lặp ( thực tế, nếu
(T1, x, T2) thì T1 trước T2 trong trật tự tuần tự)
Để 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ó cùng quan hệ phụ thuộc.
Do vậy, điều kiện đủ cho sự gắn bó của một trật tự hoá có thể phát biểu
như sau: Một trật tự hoá là gắn bó, nếu nó có cùng quan hệ phụ thuộc với trật
tự tuần tự.
Ví dụ: Xét 3 trật tự hoá có thể là S
1
, S
2
, S
3
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
5/26
Giao dịch loại T
Giao dịch loại U
A := A – P
A := A * (1 + t)
B := B * (1 + t)
B := B + P
Trật tự hoá S
1
Giao dịch loại T
Giao dịch loại U
A := A – P
A := A * (1 + t)
B := B + P
B := B * (1 + t)
Trật tự hoá S
2
Giao dịch loại T
Giao dịch loại U
A := A – P
B := B + P
A := A * (1 + t)
B := B * (1 + t)
Trật tự hoá tuần tự S
3
Tiểu luận môn Hệ tin học phân tán
Đồ thị ứng với các trật tự hoá S
1
, S
2
, S
3
:
I.5 Giao dịch phân tá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
6/26
B
T
U
A
(S
1
)
T U
A
(S
2
)
T U
A
(S
3
)
B B
Tiểu luận môn Hệ tin học phân tán
Trong một giao dịch phân tán sẽ bao gồm một tập hợp các giao dịch con
T
1
, T
2,
.,T
k
được thực thi trên các trạm S
1
, S
2,
., S
k
.
Mỗi giao dịch con quản lý dữ liệu cục bộ. Các vấn đề cụ thể liên quan đến
việc quản lý các giao dịch phân tán khác biệt với các giao dịch tập trung xuất
phát từ hai nội dung:
Dữ liệu có thể được sao chép trên nhiều trạm khác nhau. Việc quản lý then
cài của bản sao dữ liệu là một vấn đề riêng.
Bất kể dữ liệu có được sao chép hay không chúng cũng cần phải sử dụng
giao thức uỷ nhiệm phân tá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
7/26
Tiểu luận môn Hệ tin học phân tán
CHƯƠNG II ĐẢM BẢO ĐẶC TÍNH TOÀN VẸN
DỮ LIỆU TRONG HỆ PHÂN TÁN
II.1 KỸ THUẬT GIAO DỊCH 2 PHA
II.1.1 Cơ chế then cài
Một giao dịch nào đó đang thực hiện phép then cài trên một đối tượng
muốn giành quyền sử dụng đối tượng này theo một vài kiểu truy cập nhất
định. Cơ chế then cài gán hay không gán quyền truy cập này căn cứ vào quy
tắc tiền định như loại trừ tương hỗ, luật đọc hiệu chỉnh thông tin, .
Nếu quyền được thừa nhận thì đối tượng bị cài then bởi giao dịch. Nếu
không, tiến trình thực hiện giao dịch bị khoá và đối tượng không bị cài then.
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 giao dịch T
1
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 T
2
sẽ đưa giao dịch T
2
rơi vào trạng
thái chờ cho cho đến khi T
1
mở then.
Nếu giao dịch T
1
thực hiện then cài chia sẽ R thì giao dịch T
2
cũng có thể
gán một then cài chia sẽ, nhưng T
2
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.
II.1.2 Loại trừ tương hỗ (Loại trừ lẫn nhau)
Một trong những giải pháp đơn giản để đạt được trật tự hoá gắn bó thể hiện
ở chổ bắt buộc phải sử dụng trật tự hoá tuần tự. Để làm việc đó, toàn bộ giao
dịch được đặt trong cặp hàm nguyên thuỷ mo_giaodich() và dong_giaodich().
Đây là sự đảm bảo cho việc loại trừ tương hỗ giữa các giao dịch.
Nếu ta biết trước các đối tượng được xử lý bởi một giao dịch nào đó, thì ta
có thể cài then công việc truy cập đến các đối tượng. Điều đó chỉ cho phép
thực hiện song song đối với các giao dịch truy cập vào các đối tượng rời rạc.
II.1.3 Then cài lựa chọn các đối tượng
Các quy tắc truy cập đối tượng được chú ý. Đó là tính hợp thức của việc
truy cập. Nội dung quy tắc này như sau :
Một giao dịch thay đổi giá trị của một đối tượng phải loại trừ tất cả các
giao dịch khác muốn truy cập, ngược lại thì việc truy cập được tiến hành theo
kiểu tương tranh.
Để đảm bảo điều đó luôn luôn được thực hiện, người ta cho phép tiến
hành cài then một đối tượng trước khi việc sử dụng nó có hiệu lực.
Một giao dịch có thể thực hiện ba hàm nguyên thuỷ trên đối tượng e :
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
8/26
Tiểu luận môn Hệ tin học phân tán
STT Tên hàm Thuyết minh
1 v_doc(e) Sử dụng khi muốn có được quyền đọc e theo kiểu
chia sẽ.
2 v_viet(e) Sử dụng khi muốn có được quyền đọc và viết vào
e theo kiểu loại trừ.
3 giai_phong(e) Giải phóng đối tượng e. Giả sử trước đó đối tượng
đã bị cài then bởi cùng giao dịch này.
Một giao dịch được gọi là phát triển nếu :
• Một phép toán chỉ được thực hiện trên một đối tượng sau khi đối
tượng đó đã bị cài then bởi giao dịch theo kiểu tương tích với phép toán
đó.
• Không có giao dịch nào cài then được trên đối tượng mà trước đó
đối tượng đã bị cài then cũng bởi chính giao dịch đó, ngoại trừ theo
kiểu loại trừ trong trong trường hợp trước đó đã sử dụng kiểu chia sẽ.
• Sau khi kết thúc một giao dịch, không có đối tượng nào bị cài then.
Các then cài được sử dụng để hạn chế một lớp các trật tự hoá có khả năng
được thực hiện.
Một trật tự hoá được gọi là hợp thức nếu :
• Đối tượng bị một giao dịch cài then theo kiểu chia sẽ không bị bất
kỳ 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.
II.1.4 Giao dịch hai pha
Đây là kỹ thuật nhằm đảm bảo đặc tính toàn vẹn dữ liệu trong hệ thống
thông tin. Nội dung của kỹ thuật này là kiểm tra hai điều kiện của một giao
dịch hình thành hợp thức:
• 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
• 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.
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
9/26
Tiểu luận môn Hệ tin học phân tán
Điều kiện này thể hiện ở chỗ là dãy các phép toán trên các then cài
được phân tích thành hai pha nối tiếp nhau. Một pha mà trong đó các
đối tượng bị cài then, còn pha kia chúng được mở then. Đặc tính này
định nghĩa các giao dịch theo hai pha.
Ý nghĩa của giao dịch hai pha :
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ó.
Giao dịch hai pha giới hạn số lượng đồng thời có thể xãy ra trong một tật
tự hoá.
II.1.5 Hệ quả của tính không chắc chắn
Bây giờ ta hãy tưởng tượng rằng các đối tượng được phân tán trên nhiều
trạm khác nhau và được nối với nhau thông qua hệ thống viễn thông và rằng
các tiến trình diễn ra trên các trạm khác nhau. Hệ thống viễn thông cho phép
các tiến trình trên các trạm khác nhau có thể trao đổi các thông điệp với nhau.
Ta cũng giã định rằng các tiến trình và các phương tiện truyền thông tin là các
đối tượng có thể rơi vào tình trạng sự cố.
Các đối tượng thay đổi hay tham chiếu trong quá trình thực hiện cùng một
giao dịch có thể nằm trên các trạm khác nhau.
Một hệ quản lý tập hợp thông tin phân tán bao gồm :
STT Cơ chế
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
10/26
Pha mở then
Pha cài then
Then cài bởi T
i
Tiểu luận môn Hệ tin học phân tán
1
Cơ chế cho phép sắp xếp một cách tổng quát các tác động của cùng
một giao dịch, ngay cả khi các tác động này diễn ra trên các trạm khác
nhau
2
Cơ chế điều khiển các tranh chấp truy cập cục bộ vào các đối tượng và
đảm bảo tôn trọng tính toàn vẹn của các đối tượng cục bộ này.
3
Cơ chế có khả năng xử lý các bế tắc và thiếu thốn vô hạn, hậu quả của
việc huỷ bỏ các giao dịch
4 Cơ chế phục hồi các giao dịch đã bị huỷ bỏ hay xử lý các sự cố.
II.1.6 Xử lý các sự cố
Ta giả sử rằng các bộ xử lý và bộ nhớ cấu tạo nên cấu tạo nên các trạm là
nguyên nhân chính của sự cố ngắt quãng quá trình thực hiện các tiến trình. Các
hệ thống viễn thông cũng có thể là nơi diễn ra các sự cố làm mất hẳn hay
chồng chéo các thông điệp.
Ta xét sự gắn bó thông tin không chỉ trong các điều kiện thuận lợi như đã
nêu trước đây, mà còn tính đến các yếu tố mới và cũng xét đến các công cụ
cho phép đảm bảo cho sự gắn bó này.
Nếu một tiến trình p 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ó.
Một cơ chế cho phép duy trì sự gắn bó trong môi trường phân tán có sự cố
phải là :
STT Phải thực hiện
1 Giao dịch T bắt buộc phải được thực hiện một cách trọn vẹn
2 Nếu có sự cố diễn ra thì bắt buộc nó phải quay về điểm xuất phát
Muốn thực hiện những điều vừa nêu trong bảng trên, người ta đòi hỏi giao
dịch phải có các đặc tính toàn vẹn như sau :
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
11/26
Tiểu luận môn Hệ tin học phân tán
STT Đặc tính
1
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ó
2
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ó
3
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ó
Các đặc tính trên có thể mô tả bằng hình vẽ sau đây :
Trong tình huống này, ta có hai giải pháp có thể là :
STT Giải pháp tổng quát
1 Phục hồi trạng thái của hệ như trước khi diễn ra giao dịch T
2 Cố gắng tiếp tục thực hiện giao dịch T cho đến kết thúc
Không phải lúc nào ta cũng có thể áp dụng được giải pháp 1 vì một số tác
động không thể qua trở lại được. Như thế, ta phải xác định cho được điểm
không qua trở lại của từng giao dịch. Căn cứ vào điểm này, nếu vượt qua nó,
không có hành động quay trở lại nào được thực hiện và trạng thái trước đó của
giao dịch sẽ được thực hiện bởi phép lặp lại (rollback).
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
12/26
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ó
Không có nhận xét nào:
Đăng nhận xét