ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
VẤN ĐỀ XỬ LÝ GIAO DỊCH
TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN
Môn học : CSDL Nâng cao
Giảng viên : PGS.TS. Nguyễn Hà Nam
Học viên : Lê Ngọc Phú
Nguyễn Huy Hoàng
Hà Nội, 2012
MỤC LỤC
LỜI MỞ ĐẦU 3
MỘT SỐ KHÁI NIÊM VỀ CSDL PHÂN TÁN 3
KỸ THUẬT PHÂN TÁN CSDL 4
XỬ LÝ GIAO DỊCH TRONG CSDL PHÂN TÁN 7
GIAO THỨC 2PC (TWO PHASE COMMIT) 9
ĐIỀU KHIỂN TƯƠNG TRANH TRONG CSDL PHÂN TÁN 10
Vấn đề xử lý giao dịch trong CSDL phân tán 2
Lời mở đầu.
Như chúng ta đã biết CSDL phân tán là CSDL được phân mảnh và lưu trữ trên những vị
trí khác nhau trong hệ thống. Ở mỗi trạm đó có nhiều ứng dụng đòi hỏi phải thực hiện nhiều
chương trình cùng một lúc hoặc thực hiện nhiều tiến trình của cùng một chương trình. Một số
trường hợp hai hoặc nhiếu tiến trình đọc và thay đổi giá trị cùng một đối tượng không được
phép thực hiện cùng một lúc vì chúng đưa ra kết quả không xác thực với thực tế. Ngược lại
khi chúng ta không thay đổi dữ liệu thì khi đó cũng không quan tâm đến thứ tự đọc ghi dữ
liệu vì vậy hệ điều hành có thể yêu cầu đọc đồng thời.Khi chỉ có yêu cầu đọc dữ liệu thì ta
muốn càng nhiều thao tác đọc dữ liệu càng tốt vì tiết kiệm thời gian. Mỗi thực hiện như trên
được gọi là một giao dịch khác nhau. Việc quản lý giao dịch là phải đảm bảo rằng cho dù bất
kì điều gì xảy ra trong giao dịch thì cơ sở dữ liệu không bị ảnh hưởng.
Giao dịch phân tán là giao dịch bao gồm một bó thao tác giữa hai hoặc nhiều máy. Thông
thường, trong một giao dịch phân tán, chúng ta cần quan tâm đến tài nguyên cho giao dịch,
quản lý việc giao dịch, yêu cầu giao dịch. Trong đó việc kiểm soát hoạt động đồng thời được

- Sao chép: Trong CSDL quan hệ phân tán, một phân mảnh có thể được sao chép, nhân
rộng và lưu trữ tại 1 số vùng khác nhau.
1.1 Quá trình phân mảnh.
Mục đích của việc phân mảnh dữ liệu trong CSDL phân tán là nhằm hạn chế việc truy
xuất thừa, khi nhân bản dữ liệu làm tốn không gian bộ nhớ. Việc phân mảnh dữ liệu giúp cho
quá trình giao dịch được thực hiện đồng thời . Một truy vấn tổng thể được chia thành nhiều
truy vấn con, các truy vấn con này có thể thực hiện đồng thời với nhau giúp việc xử lý nhanh
Vấn đề xử lý giao dịch trong CSDL phân tán 4
hơn . Tuy nhiên cũng gặp một số rắc rồi khi truy xuất dữ liệu như cùng truy xuất vào một
phần tử dữ liệu.
Dữ liệu có thể được lưu trữ trên nhiều máy tính khác nhau qua sự phân mảnh. Một CSDL
được chia thành một số phần gọi là các phân mảnh, mỗi phân mảnh này đặt tại 1 số vùng
khác nhau.
Nguyên tắc của quá trình phân mảnh:
- Điều kiện đầy đủ: Một mối quan hệ R được chia thành các phân mảnh R1, R2 Rn, mỗi
mục dữ liệu trên R phải tồn tại ở ít nhất một phân mảnh Ri. Nguyên tắc này nhằm bảo
đảm dữ liệu không mất mát trong quá trình phân mảnh.
- Điều kiện kiến thiết: Nó phải có khả năng kiến thiết lại mỗi một quan hệ toàn cục từ các
phân mảnh của nó.
- Điều kiện phân tách được: Nếu quan hệ R được phân mảnh ngang thành R1,R2…Rn và
mục dữ liệu Tj nằm trong mảnh Rj thì nó sẽ không nằm trong 1 mảnh Rk(k#j). Đối với
phân mảnh dọc thì các thuộc tính trong khoá chính phải nằm trong mỗi phân mảnh.
1.1.1 Phân mảnh ngang.
Trong phân mảnh ngang, các mỗi quan hệ được chia theo chiều ngang. Phân mảnh ngang
trên R là tách R thành n bộ R1,R2 Rn sao cho quan hệ R có thể được khôi phục lại từ phép
hợp R = R1 U R2 U U Rn.
Ví dụ :
Ta có bảng KhachHang(MaKH, Hoten,Diachi, SoDT, Ngaysinh) ta phân mảnh bảng này
thành 3 phân mảnh ngang như sau :
KH1 = Diachi=’HaNoi’(KhachHang)

o Nếu bản sao của CSDL được lưu trữ tại mọi nơi của hệ thống ta có trường hợp
sao lặp đầy đủ.
o Hiện nay có nhiều kỹ thuật mới cho phép tạo bản sao không đầy đủ phù hợp với
yêu cầu dữ liệu ở mỗi trạm và một bản đầy đủ được quản lý ở server.
o Sau một khoảng thời gian nhất định các bản sao được làm đồng bộ với bản
chính bằng một ứng dụng nào đó.
Vấn đề xử lý giao dịch trong CSDL phân tán 6
- Phương thức lai:
o CSDL được phân thành nhiều phần: quan trọng và không quan trọng.
o Phần ít quan trọng được lưu trữ ở một nơi và phần quan trọng được lưu ở một
nơi khác.
Xử lý giao dịch trong CSDL phân tán.
1.3 Thế nào là giao dịch .
Giao dịch là tập hợp các thao tác tạo thành một đơn vị làm việc logic trong hệ cơ sở dữ
liệu, như thao tác đọc và ghi dữ liệu.
1.4 Tính chất của giao dịch
Dù giao dịch được thực hiện trong CSDL tập trung hay phân tán thì nó đều phải thỏa mãn
4 tính chất sau :
- Tính nguyên tử (Atomicity): Toàn bộ thao tác của giao dịch được thực hiện hoặc không
thực hiện gì hết.
- Tính nhất quán (Consistency): Giao dịch phải đảm báo tính nhất quán của cơ sở dữ liệu.
- Tính cô lập (Isolation): Nhiều giao dịch được thực hiện đồng thời, các giao dịch này
không biết được các giao dịch khác đang thực hiện, kết quả trung gian của mỗi giao dịch
cũng được dấu trước các giao dịch khác.
- Tính bền lâu (Duarability): Sau khi giao dịch được hoàn thành quá trình thay đổi trong
cơ sở dữ liệu vẫn còn ngay cả khi hệ thống xảy ra sự cố.
1.5 Ví dụ về giao dịch.
T1
Read(X);
X=X – 2 ;

nào tham gia trong hành động COMMIT. Khi đó nếu TM bị lỗi ở pha 2 (trong giao thức 2
Vấn đề xử lý giao dịch trong CSDL phân tán 8
pha), DMs sẽ không phát lệnh ghi, đồng thời có thể nhận ra vấn đề và thông báo cho các DM
khác liên quan đến quá trình COMMIT
Chi tiết xử lý giao dịch:
Hình 3- Chi tiết xử lý giao dịch.
Trong DDBMS quá trình xử lý giao dịch thực hiện như sau:
- Thao tác đọc: Bộ quản lý dữ liệu (DM) thực hiện việc duyệt CSDL cục bộ(CSDL tại các
server) để trả về theo yêu.
- Thao tác ghi: Bộ quản lý dữ liệu (DM) sửa đổi CSDL cục bộ và trả về sự chấp thuận cho
bộ lập lịch S, bộ lập lịch S trả về bộ quản lý giao dịch (TM), bộ (TM) trả về cho giao dịch.
Giao thức 2PC (Two Phase Commit)
Gồm hai giai đoạn như sau :
 Giai đoạn 1: Ở một vị trí nào đó, máy chủ này sẽ gửi một thông báo C-PREPARE tới
tất cả các máy chủ khác, để thực hiện giao dịch ngay bây giờ. Sau khi các máy chủ nhận
được thông báo này nó gửi lại thông báo C-READY nếu đã sẵn sàng cho việc thực hiện
giao dịch. Một số máy chủ có thể gửi lại thông báo C-REFUSE nếu không thực hiện
được giao dịch bởi một lý do nào đó.
 Giai đoạn 2: Nếu máy chủ gửi thông báo C-PREPARE mà nhận được thông báo C-
READY từ tất cả các máy chủ khi đó nó sẽ gửi một thông báo C-COMMIT tới tất cả các
máy chủ đó. Mỗi máy chủ đồng ý khi nhận được thông báo này. Nếu máy chủ gửi thông
báo C-PREPARE mà nhận được một thông báo C-REFUSE từ bất kỳ máy chủ nào thì nó
lại gửi thông báo C-ROLLBACK tới tất cả các máy chủ khác. Khi đó giao dịch thực hiện
không kết thúc.
Vấn đề xử lý giao dịch trong CSDL phân tán 9
Điều khiển tương tranh trong CSDL phân tán.
Một số vấn đề phát sinh liên quan tới việc điều khiển tương tranh và khôi phục các vấn
đề trong CSDL phân tán. Có một số vấn đề chính như sau:
- Lỗi site: Có một số tình huống phát sinh khi một hoặc nhiều site bị lỗi trong CSDL quan
hệ phân tán. Trong trường hợp đó, tính nhất quán và toàn vẹn của CSDL cần được khôi

1.8 Thế nào là đụng độ .
Là khi các thao tác đọc, ghi cùng truy xuất đến một mục dữ liệu ở cùng một thời gian
nhất định được gọi là đụng độ. Các thao tác này xuất phát từ các giao dịch khác nhau
1.9 Các phương pháp giái quyết vấn đề đụng độ .
1.9.1 Thuật toán khóa chốt hai giai đoạn (Two Phase Locking - 2PL)
- Là kỹ thuật hiệu quả trong việc khắc phục một số đụng độ cũng như thời gian chết trong
quá trình thực hiện các giao dịch.
- Trong kỹ thuật này thì bộ lập lịch quản lý khóa chốt và điều khiển giao dịch khi nào lấy
và khi nào giải phóng khóa.
- Giải quyết tốt việc đồng bộ hóa trong việc đọc, ghi. Trước khi đọc dữ liệu x thì phải khóa
mục x lại(readlock(x)),trước khi ghi lên x thì phải khóa x lại (writelock(x)).
- Định nghĩa khoá xung đột dựa trên kiểu đồng bộ được thực hiện:
o Với kiểu “RW”: 2 khoá xung đột khi cả 2 cùng khoá trên một mục dữ liệu và
một khoá là đọc và 1 khoá là ghi.
o Với kiểu “WW”: 2 khoá xung đột khi cả 2 cùng khoá trên một mục dữ liệu và 2
khoá đều là khoá ghi.
Kỹ thuật này gồm hai giai đoạn:
- Giai đoạn tăng trưởng(Growing phase): cho phép nhận các khóa và truy xuất dữ liệu
- Giai đoạn thu hồi(Shirnking phase): cho phép giải phóng các khóa đã khóa mục dữ liệu
trong giao dịch.
Vấn đề xử lý giao dịch trong CSDL phân tán 11
Hình 4 – Sơ đồ khóa 2PL.
Hình này cho thấy rằng: Sau khi hoàn thành việc truy xuất dữ liệu thì các khóa được giải
phóng. Điều này cho phép các giao dịch đang đợi khóa tiếp tục tiến hành và nhận khóa. Vì
thế làm tăng tính đồng thời trong việc xử lý dữ liệu.
Điểm khóa (Lock point): Là thời điểm mà giao dịch đã nhận được tất cả các khóa nhưng
chưa bắt đầu giải phóng khóa nào. Chính là điểm cuối của giai đoạn tăng trưởng và đầu giai
đoạn thu hồi khóa.
Nhận xét sơ đồ 2PL:
Với sơ đồ này thì phải biết được tất cả các yêu cầu khóa của mỗi giao dịch và thời điểm

Nếu nó là đa số, TM sẽ coi như tất cả các khoá được thiết lập. Ngược lại, nó sẽ chờ DM gửi
thông diệp “lock blocked”. Đặt bế tắc sang một bên, cuối cùng nó sẽ nhận được đủ “lockset”
để tiếp tục xử lý. Vì tại một thời điểm chỉ có một giao dịch T có thể giữ phần lớn ổ khoá trên
X, chỉ có một giao dịch ghi lên X có thể ở pha 2 của nó tại bất cứ thời điểm nào. Do đó tất cả
các bản sao của X có cùng trình tự ghi. Điểm khoá của T xuất hiện khi nó thu được số lượng
khoá ghi đủ lớn trên mỗi mục dữ liệu. Khi cập nhật nhiều mục dữ liệu, một giao dịch phải thu
được một lượng lớn các khoá trên các mục dữ liệu trước khi phát lệnh dm-write. Theo
nguyên tắc, phương thức chọn 2PL có thể được điều chỉnh trong đồng bộ “RW”. Trước khi
đọc bất cứ bản sao X nào đó, giao dịch T phải yêu cầu khoá đọc trên các bản sao X; Khi một
số khoá đủ lớn được thiết lập, giao dịch T có thể đọc trên bất cứ bản sao nào. Kỹ thuật này
đòi hỏi cao: Đúng ra chỉ yêu cầu một bản sao X được khoá, bản sao cho việc đọc thì không,
nhưng kỹ thuật này yêu cầu khoá trên tất cả các bản sao. Vì lý do này nó không phù hợp cho
đồng bộ “RW”.
1.9.1.4 Kỹ thuật 2PL tập trung.
Thay vì phân tán lịch 2PL, một lịch tập trung được đặt tại 1 site, khi truy xuất bất cứ site
nào khác, ổ khoá phù hợp được lấy từ lịch 2PL trung tâm. Ví dụ, khi thực hiện dm-read(x)
khi x không đặt ở site trung tâm, đầu tiên TM yêu cầu read-lock trên x tại site trung tâm. Chờ
tới khi site trung tâm hiểu được và thực hiện khoá, nó sẽ gửi yêu cầu dm-read(x) tới DM của
lưu giữ x.
Vấn đề xử lý giao dịch trong CSDL phân tán 13
Như hình vẽ dưới, giả sử giao dịch thực hiện đồng thời, thực hiện READ sẽ thực hiện
trước END. Các thực hiện sẽ được mô tả như sau:
DM A: RL [X1]; DM B: RL [Y2]; DM C: RL [Z3]
Tại thời điểm này thì: T1 khoá đọc trên X1, T2 khoá đọc Y2, T3 khoá đọc Z3.
Trước khi xử lý toàn bộ giao dịch yêu cầu khoá ghi: T1 yêu cầu khoá ghi trên Y1,Y2; T2
yêu cầu khoá ghi trên Z2, Z3; T3 yêu cầu trên X1.
Nhưng T1 không thể khoá ghi trên Y2 cho tới khi T2 giải phóng khoá đọc; 2khoong thể
có khoá ghi trên Z3 cho tới khi T3 giải phóng khoá đọc; T3 không thể có khoá ghi trên X1
cho tới khi T1 giải phóng quyền đọc. Đây chính là Deadlock.
1.9.2 Thuật toán nhãn thời gian.

1 Read(A) Tr =20
2 Read(A) Tr =30
3 Write(B) Tw=20
4 Write(A) Tw=30
5 Read(B)
T1 bị hủy
bỏ
Giải thích :
 Bước 1: T2(có nhãn thời gian là t=20) thực hiện đọc A có tw=0. Vì t>tw và t>tr nên
tr(A)=20.
 Bước 2: T3(có nhãn thời gian t=30) thực hiện đọc A có tw=0. Vì t>tw và t>tr(30>20) nên
tr(A)=30.
 Bước 3: T2(có nhãn thời gian t=20) thực hiện ghi B có tr=0 và tw=0 mà t>tr và t>tw nên
tw(B)=20
 Bước 4: T3(có nhãn thời gian t=30) thực hiện ghi A có tr(A)=30 và tw(A)=0. Vì
t>tw(30>0) nên tw(A)=30
 Bước 5: T1(có nhãn thời gian t=10) thực hiện đọc B có tw(B)=20 vì t<tw(B) nên giao
dịch T1 bị hủy bỏ
1.9.2.4 Đánh giá thuật toán
- Ưu điểm: Lịch tạo ra là khả tuần tự và tránh được deadlock
Vấn đề xử lý giao dịch trong CSDL phân tán 15
- Nhược điểm: Ta có thể khởi động lại giao dịch để đánh nhãn thời gian mới cho giao dịch
đó.
Vấn đề xử lý giao dịch trong CSDL phân tán 16