MỤC LỤC
CHƢƠNG I. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN ......................................................... 2
1.1.CƠ SỞ DỮ LIỆU PHÂN TÁN ................................................................................................... 2
1.1.1. Khái niệm ............................................................................................................................. 2
1.1.2. Lợi điểm của Hệ cơ sở dữ liệu phân tán .............................................................................. 2
1.2.QUẢN TRỊ CƠ SỞ DỮ LIỆU PHÂN TÁN ............................................................................... 3
CHƢƠNG II. QUẢN TRỊ TƢƠNG TRANH ....................................................................................... 6
2.1. MÔ HÌNH XỬ LÍ GIAO TÁC ................................................................................................... 7
2.1.1. Các định nghĩa..................................................................................................................... 7
2.1.2. Mô hình xử lý giao tác tập trung. ........................................................................................ 9
2.1.3. Mô hình xử lý giao tác phân tán. ....................................................................................... 10
2.2. PHÂN TÍCH BÀI TOÁN ĐIỀU KHIỂN TƢƠNG TRANH ................................................... 11
2.2.1. Tính khả tuần tự ................................................................................................................. 13
2.2.2. Mô hình điều khiển tương tranh. ....................................................................................... 15
2.2.3. Thời gian và nhãn thời gian trong CSDL phân tán ........................................................... 16
2.3. CÁC KỸ THUẬT ĐIỂU KHIỂN TƢƠNG TRANH ............................................................... 17
2.3.1. Các kỹ thuật đồng bộ hóa dựa trên khóa hai pha .............................................................. 17
2.3.2. Quá trình thực hiện 2PL cơ bản ........................................................................................ 18
2.3.3. Kỹ thuật 2PL sao chép chính ............................................................................................. 18
2.3.4. Kỹ thuật 2PL biểu quyết .................................................................................................... 19
2.3.5. Kỹ thuật 2PL tập trung. ..................................................................................................... 19
2.3.6. Phát hiện và ngăn chặn tắc nghẽn ..................................................................................... 20
2.4. CÁC KỸ THUẬT ĐỒNG BỘ HÓA DỰA TRÊN TRẬT TỰ NHÃN THỜI GIAN ............... 24
2.4.1. Sự thực hiện T/O cơ bản .................................................................................................... 24
2.4.2. Luật ghi Thomas ................................................................................................................ 26
2.4.3. Đa phiên bản T/O .............................................................................................................. 26
2.4.2. Luật ghi Thomas ................................................................................................................ 29
2.4.3. Đa phiên bản T/O .............................................................................................................. 29
2.4.4. Duy trì T/O ........................................................................................................................ 31
2.4.5. Quản lý nhãn thời gian ..................................................................................................... 31
2.5. DC-ROLL ................................................................................................................................. 32

dữ liệu ở những vị trí khác nhau để lấy thông tin tổng hợp.
1.1.2. Lợi điểm của Hệ cơ sở dữ liệu phân tán
Có nhiều nguyên nhân để phát triển cơ sở dữ liệu phân tán nhƣng trung lại chỉ
gồm những điểm sau đây:
Lợi điểm về tổ chức và tính kinh tế:tổ chức phân tán nhiều chi nhánh và dùng
cơ sở dữ liệu phân tán phù hợp với các tổ chức kiểu này. Với vai trò là động lực thúc
đẩy kinh tế thƣơng mại phát triển rộng hơn, thì việc phát triển các trung tâm máy tính
phân tán ở nhiều vị trí trở thành nhu cầu cần thiết.
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53

Page 2


Cơ sở dữ liệu phân tán – Điều khiển tương tranh

Tận dụng những cơ sở dữ liệu sẵn có: Hình thành cơ sở dữ liệu phân tán từ các
cơ sở dữ liệu tập trung có sẵn ở các vị trí địa phƣơng.
Thuận lợi cho nhu cầu phát triển: Xu hƣớng dùng cơ sở dữ liệu phân tán sẽ
cung cấp khả năng phát triển thuận lợi hơn và giảm đƣợc xung đột về chức năng giữa
các đơn vị đã tồn tại và giảm đƣợc xung đột giữa các chƣơng trình ứng dụng khi truy
cập đến cơ sở dữ liệu. Với hƣớng tập trung hoá, nhu cầu phát triển trong tƣơng lai sẽ
gặp khó khăn.
Giảm chi phí truyền thông: Trong cơ sở dữ liệu phân tán chƣơng trình ứng
dụng đặt ở địa phƣơng có thể giảm bớt đƣợc chi phí truyền thông khi thực hiện bằng
cách khai thác cơ sở dữ liệu tại chỗ.
Tăng số công việc thực hiện:Hệ cơ sở dữ liệu phân tán có thể tăng số lƣợng
công việc thực hiện qua áp dụng nguyên lý xử lý song song với hệ thống xử lý đa
nhiệm. Tuy nhiên cơ sở dữ liệu phân tán cũng có tiện lợi trong việc phân tán dữ liệu
nhƣ tạo ra các chƣơng trình ứng dụng phụ thuộc vào tiêu chuẩn mở rộng vị trí làm
cho các nơi xử lý có thể hỗ trợ lẫn nhau. Do đó tránh đƣợc hiện tƣợng tắc nghẽn cổ

khiển giữa các hệ quản trị cơ sở dữ liệu tập trung cài đặt ở những điểm khác nhau
trên mạng máy tính. Những phần mềm cần thiết cho việc xây dựng cơ sở dữ liệu
phân tán là:
Phần quản lý cơ sở dữ liệu ( Database Management -DB ).
Phần truyền thông dữ liệu (Data Communication - DC).
Từ điển dữ liệu đƣợc mở rộng để thể hiện thông tin về phân tán dữ liệu
trong mạng máy tính (Data Dictionary - DD).
Phần cơ sở dữ liệu phân tán (Distributed Database DDB).
Mô hình các thành phần của hệ quản trị cơ sở dữ liệu phát triển theo kiểu
thƣơng mại (Truy cập từ xa trực tiếp).

Những dịch vụ hệ quản trị cơ sở dữ liệu cung cấp:
- Cách thức truy cập dữ liệu từ xa: bằng chƣơng trình ứng dụng.
- Lựa chọn một cấp độ trong suốt phân tán thích hợp:cho phép mở rộng hệ
thống theo nhiều cách khác nhau theo từng hoàn cảnh (phải cân nhắc giữa cấp độ
trong suốt phân tán và phân chia công việc thực hiện để công việc quản trị hệ thống
đơn giản hơn).
- Quản trị và điều khiển cơ sở dữ liệu bao gồm công cụ quản lý cơ sở dữ liệu,
tập hợp thông tin về các thao tác trên cơ sở dữ liệu và cung cấp thông tin tổng thể về
file dữ liệu đặt ở các nơi trong hệ thống.
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53

Page 4


Cơ sở dữ liệu phân tán – Điều khiển tương tranh

- Điều khiển tƣơng tranh và điều khiển hồi phục dữ liệu của giao tác phân tán.
Cách thức truy cập cơ sở dữ liệu từ xa qua chƣơng trình ứng dụng theo hai cách
cơ bản: Truy cập từ xa trực tiếp và gián tiếp.

liệu phân tán vì:
(1) Tại một thời điểm có thể có nhiều ngƣời sử dụng cùng truy xuất dữ liệu lƣu
trong các trạm khác nhau của một hệ phân tán;
(2) Một cơ chế điều khiển tƣơng tranh tại một máy tính không thể ngay lập tức
biết đƣợc sự tƣơng tác tại các máy tính khác.
Điều khiển tƣơng tranh đã đƣợc nghiên cứu trong nhiều năm qua, đối với các
hệ quản trị cơ sở dữ liệu tập trung thì bài toán này đã đƣợc giải quyết rất tốt. Một lý
thuyết toán học đã đƣợc phát triển để phân tích vấn đề điều khiển tƣơng tranh và trên
cơ sở đó đã đƣa ra một phƣơng pháp chuẩn để giải quyết điều này, đó là phƣơng
pháp “khóa hai pha” (two- phase locking). Những nghiên cứu gần đây về điều khiển
tƣơng tranh trong cơ sở dữ liệu tập trung chỉ còn tập trung vào việc cải tiến khóa hai
pha với mong muốn hệ thống đạt đƣợc điều tối ƣu nhất trong vấn đề này.
Đối với điều khiển tƣơng tranh trong môi trƣờng phân tán thì phức tạp hơn
nhiều. Hơn 20 thuật toán điều khiển tƣơng tranh đã đƣợc đƣa ra và chỉ một vài thuật
toán trong số đó đang đƣợc sử dụng. Những thuật toán này thƣờng phức tạp, khó
hiểu, khó chứng minh tính đúng đắn (thực tế là có nhiều thuật toán không chính
xác). Vì chúng đƣợc mô tả bằng nhiều thuật ngữ khác nhau và tạo nên những giả
định khác nhau về môi trƣờng hệ quản trị cơ sở dữ liệu phân tán cơ bản, nên rất
khó để so sánh các thuật toán với nhau, thậm chí là trên lĩnh vực định lƣợng. Thực tế
thì mỗi tác giả đều cho rằng phƣơng pháp của họ là tốt nhất, nhƣng có rất ít bằng
chứng thuyết phục ý kiến đó.
Trong chƣơng này chúng ta sẽ làm quen với một số thuật ngữ chuẩn để mô tả các
thuật toán điều khiển tƣơng tranh trong môi trƣờng các hệ quản trị cơ sở dữ liệu
phân tán và một mô hình chuẩn cho môi trƣờng này. Bài toán điều khiển tƣơng
tranh đƣợc tách làm hai bài toán con là đồng bộ hóa đọc-ghi và ghi- ghi. Mọi thuật
toán điều khiển tƣơng tranh phải bao gồm hai thuật toán con để giải quyết hai bài
toán con này. Bƣớc đầu tiên nhằm mục đích hiểu một thuật toán điều khiển tƣơng
tranh tách biệt với thuật toán con trong mỗi bài toán con. Thực ra, các thuật toán con
đều đƣợc các thuật toán điều khiển tƣơng tranh trong hệ quản trị cơ sở dữ liệu phân
tán dùng với hai ký thuật chính: khóa hai pha và thứ tự nhãn thời gian.

giao tác này là các truy vấn trực tuyến biểu diễn bằng ngôn ngữ truy vấn độc lập
hoặc các chƣơng trình ứng dụng đƣợc viết bởi một ngôn ngữ lập trình đa năng.
Tập đọc logic (logical Readset) và tập ghi logic (logical writeset) của một giao tác
là một tập các mục dữ liệu logic mà các giao tác đọc, ghi sử dụng. Tƣơng tự,
tập đọc lƣu trữ (stored readset), tập ghi lƣu trữ (stored writeset) là tập các mục dữ
liệu lƣu trữ mà giao tác đọc, ghi sử dụng.
Độ chính xác của các thuật toán điều khiển tƣơng tranh đƣợc định nghĩa
liên quan tới việc ngƣời sử dụng muốn biết rõ sự thực thi của các giao tác. Có hai
tiêu chuẩn liên quan đến vấn đề này:
(1) Ngƣời dùng mong muốn rằng mỗi giao tác đƣợc báo cho hệ thống biết là
nó sẽ đƣợc thực hiện;
(2) Ngƣời dùng mong rằng việc tính toán đƣợc thực hiện bởi mỗi giao tác là
nhƣ nhau cho dù nó thực thi một mình trong một hệ thống chuyên dụng hay song
song với các giáo tác khác trong một hệ thống đa chƣơng trình. Đây chính là vấn đề
cơ bản trong điều khiển tƣơng tranh.
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53

Page 7


Cơ sở dữ liệu phân tán – Điều khiển tương tranh

Một DDBMS gồm bốn thành phần (hình 2.1): các giao tác, TM, DM và dữ
liệu. Các giao tác kết nối với các TM, TM kết nối với DM và DM quản lý dữ liệu
(các TM không kết nối với các TM khác, các DM cũng không kết nối với nhau).
Chức năng của TM là quản lý các giao tác. Mỗi giao tác đƣợc thực thi trong
DDBMS dƣới sự giám sát của một TM, nghĩa là giao tác chuyển mọi thao tác cơ sở
dữ liệu của nó tới TM. Mọi tính toán phân tán cần thiết để thực thi một giao tác
đều đƣợc quản lý bới TM.


đọc(X) tới cơ sở dữ liệu để lấy bản sao của X từ cơ sở dữ liệu, sau đó gán giá trị
vừa lấy cho T và đƣa nó vào không gian làm việc của T.
WRITE(X, new value): TM kiểm tra lại không gian làm việc riêng của bản
sao X. Nếu tồn tại, giá trị X đƣợc cập nhật cho giá trị mới. Ngƣợc lại, một bản sao
của X với giá trị mới đƣợc tạo ra trong không gian làm việc. Giá trị mới của X
không đƣợc lƣu trong cơ sở dữ liệu tại thời điểm này.
END: TM phát ra lệnh dm-write(X) cho mỗi mục dữ liệu logic X đƣợc
cập nhật bởi T. Mỗi lệnh dm-write(X) yêu cầu module quản lý dữ liệu cập nhật giá
trị của X trong cơ sở dữ liệu đã đƣợc lƣu bằng giá trị của X trong không gian làm
việc của T. Khi tất cả các lệnh dm-write đã đƣợc thực hiện, giao tác T sẽ kết thúc
quá trình xử lý và không gian làm việc riêng của nó đƣợc xóa đi.
Hệ quản trị cơ sở dữ liệu có thể khởi tạo lại T trƣớc mỗi quá trình xử lý lệnh
dm-write. Tác dụng của việc khởi tạo lại T là xóa không gian làm việc riêng của nó
và thực hiện lại giao tác T từ đầu. Rất nhiều thuật toán điều khiển tƣơng tranh sử
dụng thao tác khởi động lại nhƣ một cách để làm đúng các hoạt động của giao
tác. Tuy nhiên, khi một lệnh dm-write đơn đƣợc xử lý, T có thể không đƣợc khởi
động lại. Mỗi lệnh dm-write cài đặt một cách cố định việc cập nhật vào cơ sở dữ
liệu và chúng ta không đƣợc phép tác động đến từng phần của các giao tác.
Một hệ quản trị cơ sở dữ liệu phân tán có thể tránh những kết quả từng phần
nhƣ thế bằng cách sử dụng một thuộc tính nguyên tố, thuộc tính này yêu cầu các
thuộc tính khác của lệnh dm-write của giao tác có đƣợc thực thi hay không. Thao tác
chuẩn của thuộc tính nguyên tố này là một thủ tục gọi là cam kết hai pha. Giả sử T
đang cập nhật hai mục dữ liệu X và Y. Khi T phát lệnh END thì giai đoạn đầu tiên
của cam kết hai pha sẽ bắt đầu, trong khi đó DM đƣa ra yêu cầu ghi đối với X và Y.
Những lệnh này yêu cầu DM sao chép dữ liệu X và Y từ không gian làm vệc riêng
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53

Page 9



địa điểm. Chẳng hạn, trong SDD-1 không gian làm việc cá nhân của giao tác T
đƣợc phân bố tại mọi địa điểm mà T truy xuất dữ liệu.
Giả sử T đang cập nhật các mục dữ liệu x, y, z đƣợc lƣu trữ tƣơng ứng tại
DMx, DMy, DMz và giả sử TM của T bị thất bại sau khi phát ra lệnh dmwrite(x) nhƣng trƣớc khi phát ra lênh dm-write đối với y và z. Lúc này, chắc
chắn cơ sở dữ liệu không còn chính xác. Đối với hệ quản trị cơ sở dữ liệu tập trung
hiện tƣợng dị thƣờng này không có gì nguy hại vì không có một giao tác nào có
thể truy xuất vào cơ sở dữ liệu cho đến khi TM khôi phục lại. Tuy nhiên, trong các
hệ quản trị cơ sở dữ liệu phân tán, các TM khác vẫn có thể thực hiện lệnh và truy
xuất vào cơ sở dữ liệu không chính xác.
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53

Page 10


Cơ sở dữ liệu phân tán – Điều khiển tương tranh

Để tránh hiện tƣợng này, các lệnh tiền ghi dữ liệu phải đƣợc thay đổi một ít.
Thêm vào đó, các mục dữ liệu đặc tả phải đƣợc sao chép vào một vùng nhớ an toàn,
đồng thời các lệnh tiền ghi dữ liệu cũng phải chỉ rõ những DM nào có liên quan đến
sự dịch chuyển. Sau đó, nếu TM còn bị thất bại trong suốt giai đoạn thứ hai của quá
trình dịch chuyển hai giai đoạn, các DM của các lệnh dm-write không đƣợc
phát ra có thể nhận ra trạng thái và kết quả của các DM có liên quan đến việc dịch
chuyển. Nếu bất kỳ một DM nào nhận một lệnh dm-write, các DM còn lại sẽ hành
động nhƣ thể chúng cũng nhận đƣợc lệnh.
Nhƣ trong các hệ quản trị cơ sở dữ liệu tập trung, một giao tác T truy xuất hệ
thống bằng cách phát ra lệnh BEGIN, READ, WRITE và END. Trong hệ quản
trị cơ sở dữ liệu phân tán, những quá trình đó diễn ra nhƣ sau:
BEGIN: TM tạo một không gian làm việc riêng cho T. Chúng ta không biết
đƣợc vị trí và tổ chức của không gian làm việc
này.


ví dụ về các máy rút tiền tự động ATM (automated teller machine). Tƣơng ứng
với các yêu cầu của khách hàng, ATM lấy dữ liệu từ một cơ sở dữ liệu, tính toán và
lƣu kết quả trở lại vào cơ sở dữ liệu.
Dị thường 1: Mất cập nhật
Giả sử tại một thời điểm có hai khách hàng đang cố gắng gửi tiền vào
cùng một tài khoản. Trong trƣờng hợp không có điều khiển tƣơng tranh, hai hành
động này có thể gặp rắc rối (hình 5.2). Hai máy ATM xử lý thao tác của hai
khách hàng có thể đọc số dƣ tài khoản tại cùng một thời điểm, tính số dƣ mới
một cách song song rồi lƣu số dƣ mới vào lại cơ sở dữ liệu. mạng hoạt động không
chính xác: mặc dù cả hai khách hàng đều đã gửi tiền, cơ sở dữ liệu chỉ phản hồi
một hành động, hành động gửi tiền của khách hàng còn lại bị mất bởi hệ thống.

Hình 2.2: Dị thường mất cập nhật

Dị thường 2: Các kết quả trả về không thống thất.
Giả sử có hai khách hàng thực hiện các giao tác sau:
Khách hàng1: Chuyển 1,000,000 $ từ tài khoản tiết kiệm của Acme
Corporation sang tài khoản kiểm tra của nó.
Khách hàng 2: In tổng số dƣ trong tài khoản tiết kiệm và kiểm tra của Acme
Corporation.
Trong trƣờng hợp không có điều khiển tƣơng tranh, hai giao tác này sẽ có rắc
rối (hình 5.3). Giao tác đầu tiên có thể đọc số dƣ tài khoản tiết kiệm, trừ
1,000,000$ và lƣu kết quả trả về vào cơ sở dữ liệu. Rồi giao tác thứ hai đọc số dƣ tài
khoản tiết kiệm và tài khoản kiểm tra, in tổng số. Sau đó, giao tác thứ nhất hoàn
thành việc chuyển tiền bằng cách đọc số dƣ tài khoản kiểm tra, cộng thêm
1,000,000$ và lƣu kết quả cuối cùng vào cơ sở dữ liệu. Không giống nhƣ trƣờng hợp
dị thƣờng 1, các giá trị lƣu trong cơ sở dữ liệu bởi thao tác này là chính xác. Tuy
nhiên, thực thi không đúng vì số dƣ đƣợc in ra bởi khách hàng 2 là
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53



Cơ sở dữ liệu phân tán – Điều khiển tương tranh

chuẩn của các giao tác bằng một tập các log, mỗi log biểu thị trật tự mà tại đó dmread và dm-write xảy ra trên một DM (hình 5.4). Một thực thi là một chuỗi nếu tồn
tại một trật tự tuyệt đối các giao tác mà nếu T trƣớc Tj trong thứ tự tuyệt đối đó thì
mọi thao tác của Ti xảy ra trƣớc mọi thao tác của Tj trong mọi log mà cả hai xuất
hiện (hình 2.4). Bằng trực giác, điều này cho thấy các giao tác thực thi một cách tuần
tự có cùng thứ tại tại mọi DM.

Một thực thi có thể của T1, T2, T3 đƣợc biểu diễn bởi các log sau (ri[x] là
thao tác dm-read(x) phát ra bởi Ti , wi[x] là một dm-write(x) do Ti phát ra)
Log của DM A: r1[x1]w1[y1]r2[y1]w3[x3]
Log của DM B: w1[y2]w2[z2]
Log của DM C: w2[z3]r3[z3]
Hình 2.4: Một mô hình thực thi mẫu chuẩn bằng các log

Hai thao tác xung đột nhau nếu chúng thực thi trên cùng một mục dữ liệu và
đều thực hiện lệnh dm-write. Trong trƣờng hợp các thao tác là xung đột nhau thì thứ
tự mà các thao tác thực hiện có ý nghĩa quan trọng. Để minh họa cho khái niệm xung
đột, chúng ta xét một mục dữ liệu x và các giao tác T, Tj. Nếu T phát ra lệnh dmwrite(x) và Tj phát lệnh dm-write(x), giá trị đọc bởi giao tác T sẽ phụ thuộc vào
lệnh dm-read xảy ra trƣớc hay sau lệnh dm-write. Tƣơng tự, nếu cả hai giao tác
đều phát lệnh dm-write(x), giá trị cuối cùng của x phụ thuộc vào lệnh dm-write nào
xảy ra cuối cùng. Những tình huống xung đột nhƣ vậy xảy ra tƣơng ứng đƣợc gọi là
xung đột đọc-ghi(rw) và xung đột ghi-ghi(ww).
Thực thi đƣợc mô hình hóa trong hình 2.4 theo từng chuỗi. Mỗi log là một
chuỗi, nghĩa là không có sự chen ngang của các thao tác từ các giao tác khác. Tại
DM A, T1 rồi đến T2 đến T3; tại DM C: T2 trƣớc T3. Do đó, T1, T2, T3 là một
thứ tự toàn phần thoả mãn định nghĩa của chuỗi.
Các thực thi sau không tạo thành chuỗi.

Trong mệnh đề 2.1, xung đột rw và ww đƣợc xem nhƣ nhau theo khái niệm
xung đột thông thƣờng. Tuy nhiên, chúng ta có thể phân tích khái niệm tính khả tuần
tự bằng cách phân biệt hai loại xung đột này. Cho E là một thực thi đƣợc tạo mẫu
bởi một tập các log. Ta định nghĩa các quan hệ nhị phân trên các giao tác
trong E, kí hiệu Æ với các chỉ số dƣới khác nhau. Với mỗi cặp giao tác Ti và
Tj:
(1) Ti -> rwTj nếu trong một số log của E, Ti đọc một số mục dữ liệu vào Tj
rồi mới ghi.
(2) Ti -> wrTj nếu trong một số log của E, Ti ghi một số mục dữ liệu rồi Tj
mới đọc.
(3) Ti -> wwTj nếu trong một số log của E, Ti ghi một số mục dữ liệu rồi Tj
mới ghi.
(4) Ti -> rwrTj nếu Ti -> rwTj hoặc Ti -> wrTj
(5) Ti -> Tj nếu Ti -> rwrTj hoặc Ti -> wwTj
Ta thấy, -> (kèm theo chỉ số dƣới) có nghĩa là “phải đƣợc thực hiện trƣớc
trong mọi chuỗi khả tuần tự”.
Mọi xung đột giữa các thao tác trong E đƣợc biểu diễn bằng một mốiquan hệ
->. Do đó, ta có thể phát biểu lại mệnh đề 5.1 dƣới dạng -> . Theo mệnh đề 2.1, E
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53

Page 15


Cơ sở dữ liệu phân tán – Điều khiển tương tranh

là khả tuần tự nếu tồn tại một thứ tự tuyệt đối của các giao tác mà phù hợp với -> .
Điều kiện sau cùng này đƣợc đảm bảo nếu và chỉ nếu -> không là quan hệ vòng
tròn (một quan hệ -> không là quan hệ vòng tròn nếu không tồn tại một chuỗi T1>T2, T2->T3,…,Tn-1 ->Tn mà T1 =Tn) . Chia -> thành các phần ->rwr và ->
ww và phát biểu lại mệnh đề 2.1 nhƣ sau:
Mệnh đề 2.2

định và không liên quan.
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53

Page 16


Cơ sở dữ liệu phân tán – Điều khiển tương tranh

Site 1

Site 2
Message

M1

Message M2

Local
Time

Local
time

Hình 2.6: Mối quan hệ "xuất hiện trước" tại hai điểm trong hệ thống

2.3. CÁC KỸ THUẬT ĐIỂU KHIỂN TƯƠNG TRANH
2.3.1. Các kỹ thuật đồng bộ hóa dựa trên khóa hai pha
Khóa hai pha (2PL-Two-Phases Locking) đƣợc sử dụng để đồng bộ hóa việc
đọc và ghi bằng cách phát hiện và ngăn chặn một cách dứt khoát các xung đột giữa
các thao tác hiện hành. Trƣớc khi đọc mục dữ liệu x, một giao tác phải sở hữu một

Khi một giao tác sở hữu mọi khóa mà nó từng sở hữu, gọi là thời điểm khóa của
giao tác. Cho E là một thực thi sử dụng 2PL để đồng bộ hóa rw (ww).
Quan hệ ->rw (->ww) sinh ra bởi E đƣợc đồng nhất với quan hệ sinh ra bởi
một chuỗi thực thi E’ mà trong đó mọi giao tác đều thực hiện thời điểm khóa của nó.
Do đó, các điểm khóa của E xác định thứ tự tuần tự của E.
2.3.2. Quá trình thực hiện 2PL cơ bản
Quá trình thực hiện của 2PL thực chất là một quá trình lập lịch 2 PL, một
mô đun phần mềm sẽ nhận các khóa yêu cầu và khóa giải phóng đồng thời xử lý
chúng theo chỉ định của 2PL.
Cách thực hiện 2PL cơ bản trong một cơ sở dữ liệu phân tán là phân bố lịch
trình theo cơ sở dữ liệu, thay lịch trình đối với mục dữ liệu x tại DM mà x đƣợc lƣu
lại. Trong sự thực hiện này, các khóa đọc sẽ đƣợc các lệnh dm-read và dm- write yêu
cầu, cũng có thể đƣợc các lệnh tiền ghi dữ liệu yêu cầu. Nếu khóa đƣợc yêu cầu
không đƣợc cấp, thao tác đƣợc đƣa vào hàng đợi, dẫn tới tình trạng nghẽn
(deadlock). Các khóa ghi đƣợc giải phóng hoàn toàn bởi lệnh dm-write. Tuy nhiên,
để giải phóng các khóa đọc, một thao tác giải phóng khóa đặc biệt đƣợc yêu cầu.
Những quá trình giải phóng khóa này đƣợc thực hiện song song với lệnh dmwrite, khi tín hiệu dm-write bắt đầu pha co lại. Khi một khóa đƣợc giải phóng, các
thao tác trong hàng đợi của mục dữ liệu đƣợc xử lý theo thứ tự vào trƣớc ra trƣớc
(FIFO).
Chú ý rằng quá trình thực hiện này tự động xử lý dữ liệu thừa một cách
chính xác. Giả sử mục dữ liệu logic X có các bản copy x1, …,xm. Nếu 2PL cơ bản
đƣợc dùng trong đồng bộ rw, một giao tác có thể đọc bất cứ một bản copy nào và
chỉ cần thu đƣợc một khóa đọc trên bản copy của X mà nó đọc thực sự. Tuy nhiên,
nếu một giao tác đƣợc cập nhật thì nó phải cập nhật mọi bản copy của X và do đó
phải thu khóa ghi của tất cả các bản copy (dù 2PL cơ bản dùng có đƣợc cho đồng bộ
rw hay ww hay không).
2.3.3. Kỹ thuật 2PL sao chép chính
2PL sao chép chính (Primary Copy 2PL) là một kỹ thuật 2PL hƣớng sự chú
ý vào dữ liệu dƣ thừa. Một bản sao của mỗi mục dữ liệu logic xác định một bản sao
chính; trƣớc khi truy xuất bất cứ bản sao nào của mục dữ liệu logic, khóa thích hợp

DM mà trƣớc đó đã đóng khóa.
Khi chỉ có một giao tác chiếm đa số khóa trên X tại một thời điểm nào đó thì
chỉ có một giao tác ghi lên X có thể chuyển sang giai đoạn thứ hai của quá trình
chuyển dữ liệu. Mọi bản sao của X do đó sẽ cùng thứ tự đƣợc ghi dữ liệu lên.
Điểm khóa của một giao tác diễn ra khi đa số khóa của nó là khóa ghi lên mỗi
mục dữ liệu trong tập ghi của nó. Khi cập nhật nhiều mục dữ liệu, một giao tác phải
có đƣợc đa số khóa trên mỗi mục dữ liệu trƣớc khi phát ra bất kỳ lệnh dm-write nào.
Theo nguyên tắc, 2PL biểu quyết thích hợp với đồng hóa rw. Trƣớc khi đọc
bất kỳ bản sao nào của X, một giao tác yêu cầu các khóa đọc trên mọi bản sao của
X đó, khi đa số khóa đƣợc thiết lập, giao tác đó có thể đọc dữ liệu.
2.3.5. Kỹ thuật 2PL tập trung.
Thay vì phân phối lịch trình 2PL ta có thể tập trung nó tại một trạm đơn.
Trƣớc khi truy xuất dữ liệu tại bất kỳ trạm nào, các khóa thích hợp phải đƣợc thu lại
từ lịch trình 2PL trung tâm. Do đó, chẳng hạn khi thực hiện lệnh dm-write(x) mà x
không đƣợc lƣu tại trạm trung tâm, TM trƣớc hết phải yêu cầu một khóa đọc trên
x từ trạm trung tâm, đợi trạm này trả lời là khóa đã đƣợc thiết lập rồi gửi dm-read(x)
tới DM đang kiểm soát x. Giống nhƣ bản sao chính 2PL, phƣơng pháp tiếp cận
này hƣớng đến yêu cầu nhiều kết nối hơn phƣơng pháp 2PL cơ bản, khi các lệnh
dm-read prewrite hoàn toàn không yêu cầu khóa.
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53

Page 19


Cơ sở dữ liệu phân tán – Điều khiển tương tranh

2.3.6. Phát hiện và ngăn chặn tắc nghẽn
Các cách thực hiện của phƣơng pháp 2PL đã nói ở trên bắt buộc các giao tác
phải đợi các khóa không có hiệu lực. Nếu quá trình chờ đợi này không đƣợc điều
khiển sẽ dẫn đến tắc nghẽn (hình 2.7).

Cơ sở dữ liệu phân tán – Điều khiển tương tranh

T2 yêu cầu khóa ghi trên z2 và z3
T3 yêu cầu khóa ghi trên x1
 Nhƣng
T1 không thể nhận khóa ghi trên y2 cho đến khi T2 giải phóng khóa đọc T2
không thể nhận khóa ghi trên z3 cho đến khi T3 giải phóng khóa đọc T3 không thể
nhận khóa ghi trên x1 cho đến khi T2 giải phóng khóa đọc
Đây là 1 trƣờng hợp tắc nghẽn.

Hình 2.8. Đồ thị chờ của hình 2.7

2.3.6.1. Ngăn chặn tắc nghẽn
Vấn đề ngăn chặn tắc nghẽn cần phải đƣợc chú ý kỹ khi một giao tác bị khởi
động lại vì hệ thống có nguy cơ xảy ra tắc nghẽn. Để thực hiện việc ngăn chặn tắc
nghẽn, lịch trình 2PL đƣợc điều chỉnh nhƣ sau: Khi có một khóa đƣợc yêu cầu bị từ
chối, lịch trình kiểm tra giao tác phát ra yêu cầu (gọi là Ti) và giao tác đang sở hữu
khóa (Tj). Nếu Ti và Tj qua đƣợc cuộc kiểm tra thì Ti đƣợc phép đợi Tj diễn ra,
ngƣợc lại, một trong hai giao tác sẽ bị hủy bỏ. Nếu Ti khởi động lại, thuật toán ngăn
chặn tắc nghẽn gọi là không ƣu tiên theo thứ tự (nonpreemptive), nếu Tj khởi động
lại thì thuật toán gọi là ƣu tiên theo thứ tự (preemptive). Bài kiểm tra đƣa vào lịch
trình phải đảm bảo rằng nếu Ti đợi Tj thì tắc nghẽn không thể cho ra kết quả. Một
cách tiếp cận đơn giản là không bao giờ để cho Ti đợi Tj. Điều này không có ý nghĩa
đối với việc ngăn chặn tắc nghẽn nhƣng lại có hiệu lực trong nhiều trƣờng hợp khởi
động lại.
Một cách tiếp cận hay hơn là đánh dấu các thuộc tính của các giao tác và kiểm
tra quyền ƣu tiên để quyết định xem Ti có đợi Tj không. Ví dụ để Ti đợi Tj nếu Ti có
độ ƣu tiên thấp hơn Tj (nếu cả hai có cùng độ ƣu tiên, Ti không thể đợi Tj hoặc
ngƣợc lại). Việc kiểm tra này ngăn chặn đƣợc tắc nghẽn vì với mỗi cung (Ti,Tj)
trong đồ thị chờ, Ti có độ ƣu tiến thấp hơn Tj. Vì chu trình là đƣờng đi từ một đỉnh

động lại. Khi dùng kỹ thuật ngăn chặn tắc nghẽn trong chuyển giao dữ liệu hai pha,
phải chú ý rằng một giao tác không đƣợc phép hủy khi pha thứ hai dx bắt đầu. Nếu
một kỹ thuật có sử dụng chế độ ƣu tiên muốn hủy Tj, nó sẽ kiểm tra TM của Tj và
hủy lệnh hủy Tj nếu Tj đã bắt đầu chuyển sang giai đoạn thứ hai. Kết quả thu đƣợc
là không có tắc nghẽn nếu Tj đang ở pha thứ hai, nó không thể đợi bất kỳ một giao
tác nào cả.
Sắp xếp trƣớc các tài nguyên (Preordering of resources) là một kỹ thuật tránh
tắc nghẽn mà hoàn toàn tránh đƣợc việc khởi động lại. Kỹ thuật này yêu cầu phải
khai báo trƣớc các khóa ( mỗi giao tác phải thu nhận mọi khóa trƣớc khi bắt đầu).
Các mục dữ liệu đƣợc đánh số và mỗi giao tác yêu cầu từng khóa một theo thứ tự
đƣợc đánh số. Độ ƣu tiên của các giao tác là giá trị cao nhất của khóa đƣợc đánh số
của của nó. Vì một giao tác chỉ có thể đợi các giao tác có độ ƣu tiên cao hơn nên
không xả ra tắc nghẽn. Ngoài yêu cầu khai báo trƣớc, bất tiện chính của kỹ thuật
này là nó đòi hỏi các khóa phải có thứ tự, điều này làm tăng thời gian trả lời.
Xét thực thi trong hình 2.7 và 2.8
Các khóa đƣợc yêu cầu tại các DM theo thứ tự sau:
DM A
DM B
DM C
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53

Page 22


Cơ sở dữ liệu phân tán – Điều khiển tương tranh

khóa đọc x1 choT1

khóa đọc x1 cho T1


thị chờ tổng thể.
Chúng ta hãy bàn về một số kỹ thuật xây dựng đồ thị chờ tổng thể để phát hiện
tắc nghẽn: tập trung và phân cấp.
Trong kỹ thuật tập trung, theo định kỳ, mỗi lịch trình gửi đồ thị chờ cục bộ
của nó tới bộ phận phát hiện tắc nghẽn. Bộ phận này kết hợp các đồ thị cục bộ thành
một hệ thống đồ thị chờ bằng cách hợp các đồ thị cục bộ lại.
Trong kỹ thuật phân cấp, các trạm dữ liệu đƣợc tổ chức thành cây phân cấp
với bộ phận phát hiện tắc nghẽn tại mỗi nút của cây. Các khối tắc nghẽn địa phƣơng
tại các trạm đơn đƣợc phát hiện tại trạm; các khối tắc nghẽn liên quan đến hai hay
nhiều trạm của cùng một miền đƣợc phát hiện bởi bộ phận phát hiện tắc nghẽn miền.
Mặc dù hai kỹ thuật đƣợc đề cập ở đây khác nhau ở mức chi tiết, nhƣng cả hai
đều liên quan đến chu kỳ chuyển dữ liệu tới bộ phận phát hiện tắc nghẽn của một
hay nhiều trạm. Chu kỳ tự nhiên của quá trình sinh ra hai vấn đề. Thứ nhất, một khối
tắc nghẽn có thể tồn tại trong vài phút mà không bị phát hiện vì thời gian trả lời
Đồng Văn Toàn – Lớp HTTT & TT - KS CLC K53

Page 23


Cơ sở dữ liệu phân tán – Điều khiển tương tranh

không đƣợc đảm bảo. Để giải quyết điều này, các bộ phận phát hiện tắc nghẽn
phải hoạt động thƣờng xuyên hơn, tăng chi phí phát hiện tắc nghẽn. Thứ hai, một
giao tác T có thể khởi động lại vì nhiều lí do khác hơn là vấn đề tƣơng tranh (chẳng
hạn trạm bị hỏng). Cho đến khi việc khởi động lại của T đƣợc truyền đến bộ phận
phát hiện tắc nghẽn, bộ phận này có thể tìm thấy chu trình trong đồ thị chờ có chứa
T. Một chu trình nhƣ thế gọi là khối tắc nghẽn ảo (phantom deadlock). Khi phát hiện
ra một khối tắc nghẽn ảo, bộ phận phát hiện tắc nghẽn không cần khởi động lại giao
tác khác hơn T. Sự đề phòng đặc biệt cần thiết để tránh việc khởi động lại không cần
thiết trong 2PL biểu quyết.

Page 24


Cơ sở dữ liệu phân tán – Điều khiển tương tranh

chƣơng trình với cơ sở dữ liệu.
Khi một giao tác bị bỏ qua, nó đƣợc gán một nhãn thời gian mới lớn hơn nhãn
cũ bởi TM của nó và khởi động lại. Kỹ thuật khởi động lại đƣợc đề cập kỹ hơn dƣới
đây.
Cơ chế uỷ thác hai pha là sự kết hợp nhãn thời gian các prewrite và việc chấp
nhận hay loại bỏ các priwrite thay cho các dm –write. Đầu tiên chƣơng trình chấp
nhận prewrite, nó phải đảm bảo chấp nhận dm-write tƣơng ứng không có vấn đề
gì khi dm-write đến. Với rw (hoặc ww) đồng bộ, một S chấp nhận prewrite(x) với
nhãn thời gian TS nó không phải đƣa ra bất kỳ dm-read(x) nào (hoặc dm-write(x))
với nhãn thời gian lớn hơn TS cho đến khi dm-write(x) đƣợc đƣa ra. Hiệu quả cũng
tƣơng tự thiết lập khóa ghi trên x cho khoảng thời gian tồn tại việc uỷ thác hai pha.
Để thực hiện qui tắc trên, S đệm các dm-read, các dm-write và các prewrite.
Min-R-ts(x)=Min các nhãn thời gian đệm cho dm-read(x), Min-W-ts(x) = Min
các nhãn thời gian các bất đệm cho dm-write(x), Min-P-ts(x) = Min các nhãn thời
gian đệm cho dm-prewrite(x).
Sự đồng bộ Rw đƣợc thực hiện nhƣ sau:
1. R là một dm-read(x). Nếu ts(R)Min-P-ts(x), R đƣợc làm bộ đệm. Ngƣợc lại R là output.
2. P là một prewrite(x). ts(P)Min-RMột dm-write(x). vW không bao giờ bị loại bỏ. Nếu ts(W)>min-P -ts(x) thì W là vật
đệm ngƣợc lai W là output.
4.Khi W là output, prewrite tƣơng ứng làm bộ đệm. Đây là nguyên nhân minP-ts(x) tăng, bộ đệm dm-writes đƣợc retested để nhìn thấy nếu bất kỳ một dm-write
nào đó là output. Nhƣ hình 2.11
Khi dm-write(x) đến, thực hiện nhƣ sau: