1

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
o0o NGUYỄN VIẾT THÀNH

MỘT SỐ THUẬT TOÁN ĐIỀU KHIỂN TƯƠNG TRANH
TRONG GIAO DỊCH ĐỒNG THỜI

Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60.48.15 TÓM TẮT LUẬN VĂN THẠC SỸ
Người hướng dẫn khoa học:
TS. PHẠM VIỆT HÀ 2

LỜI MỞ ĐẦU
Cơ sở dữ liệu là một lĩnh vực lớn và là chuyên ngành được sự quan tâm nhiều nhất
trong Công nghệ thông tin. Từ khi có mô hình cơ sở dữ liệu đầu tiên vào những năm 60
thì đến nay đã trải qua nhiều hệ cơ sở dữ liệu và có nhiều ứng dụng trong khoa học và
thương mại. Đặc biệt là trong thế kỷ 21, sự phát triển của internet bùng nổ một cách mạnh
mẽ thì cơ sở dữ liệu phân tán cũng trở thành một lĩnh vực quan trọng và phát triển nhanh
chóng. Bên cạnh đó, với sự phát triển của internet thì việc lưu trữ và xử lý dữ liệu tại
nhiều vị trí khác nhau của các công ty, các tổ chức đặc biệt là các công ty và tổ chức
thương mại cần được đáp ứng đầy đủ và các dữ liệu này cần phải được đảm bảo sự nhất

và đưa ra kết quả ứng dụng.
4

CHƯƠNG 1: TỔNG QUAN VỀ QUẢN LÝ GIAO TÁC VÀ ĐIỀU
KHIỂN TƯƠNG TRANH
1.1 Giao tác và xung đột dữ liệu
1.1.1 Giao tác (Transaction):
Giao tác được xem như một dãy các thao tác đọc và ghi trên cơ sở dữ liệu cùng với
các bước tính toán cần thiết. Với ý nghĩa đó, một giao tác có thể được nghĩ như là một
chương trình nhúng các câu truy vấn truy cập CSDL. Định nghĩa khác của giao tác là một
sự thực thi đơn giản một chương trình. Một câu truy vấn đơn giản cũng được xem là một
chương trình mà thực hiện như một giao tác.
1.1.1.1 Đặc điểm của giao tác
Chúng ta nhận thấy rằng các giao tác đều đọc và ghi một số dữ liệu. Điều này được
dùng làm cơ sở nhận biết một giao tác. Các mục dữ liệu được giao tác đọc cấu tạo nên tập
đọc RS (read set) của nó. Tương tự, các mục dữ liệu được một giao tác ghi được gọi là tập
ghi WS(write set). Lưu ý rằng tập đọc và tập ghi của một giao tác không nhất thiết phải
tách biệt. Cuối cùng hợp của tập đọc và tập ghi của một giao tác tạo ra tập cơ sở BS (base
set), nghĩa là BS = RS ∩ WS.
1.1.1.2 Các tính chất của giao tác
 Tính nguyên tử
Tính nguyên tử là một giao tác được xử lý như một đơn vị thao tác. Chính vì thế
mà các hành động của giao tác, hoặc tất cả đều hoàn tất hoặc không một hành động
nào hoàn tất.
 Tính nhất quán
Tính nhất quán (consistency) của một giao tác chỉ đơn giản là tính đúng đắn của
nó. Nói cách khác, một giao tác là một chương trình đúng đắn, ánh xạ cơ sở dữ liệu từ
trạng thái nhất quán này sang một trạng thái nhất quán khác.
5


một dữ liệu 2 lần. Nhưng lần đọc thứ 2 thì kết quả được truy xuất ra bị thay đổi so với
kết quả truy xuất ban đầu do đã bị cập nhật bới một chương trình khác trong lúc chạy.
c) Đọc ảo (Phantom read)
Đọc ảo cũng gần giống với đọc không lặp nhưng đọc ảo xuất hiện khi một chương
trình đọc một tập các dữ liệu 2 lần. Trong đó số phần tử truy xuất được trong lần thứ
nhất khác với số phần tử đọc trong lần thứ 2 vì sau khi chạy lần thứ nhất và trước khi
chạy lần thứ 2 thì có một chương trình khác đã thực hiện thêm mới hoặc xóa một sô
bản ghi trong tập dữ liệu được truy xuất.
1.2 Quản lý giao tác và giải quyết xung đột bằng điều khiển tương tranh
Như phần 1.1 và 1.2 chúng ta tìm hiểu xung quanh khái niệm giao tác và các trường
hợp có thể xảy ra xung đột/tương tranh giữa chúng. Phần 1.3 sẽ trình bày một cách trừu
tượng về thực hiện một vài giao tác xen kẽ, được gọi là lịch trình và một vài vấn đề có
thể phát sinh ra do việc thực thi xen lẫn gây ra. Từ vấn đề phát sinh do việc thực thi xen
kẽ, chúng ta sẽ tìm hiểu tổng quan về điều khiển tương tranh nhằm giải quyết xung đột.
Cuối cùng chúng ta sẽ tìm hiểu tổng quan về cách một hệ cơ sở dữ liệu khôi phục sự cố và
những bước phải làm trong suốt quá trình hỗ trợ khôi phục sự cố.
1.3 Kết luận chương
Trong chương 1 của luận văn, chúng ta đã tìm hiểu một cách tổng quan về các khái
niệm và nguyên nhân gây ra tương tranh. Qua đó chỉ ra các trường hợp gây ra dị thường
xung đột dữ liệu như: đọc bẩn, đọc không thể lặp, đọc ảo. Từ các dị thương xung đột này,
chúng ta tìm hiểu tổng quan về phương pháp mà DBMS thực hiện điều khiển tương tranh.
7

CHƯƠNG 2: MỘT SỐ THUẬT TOÁN ĐIỀU KHIỂN TƯƠNG
TRANH
2.1 Lý thuyết khả tuần tự
Từ các định nghĩa về lịch và lịch đầy đủ. Phần này chúng ta đưa ra các ví dụ để làm rõ
tính khả tuần tự của lịch. Và các vấn đề liên quan đến việc lập lịch.
2.2 Các thuật toán điều khiển tương tranh
2.2.1 Phân loại các cơ chế điều khiển tương tranh

Bi quan Lạc quan
8

2.2.2 Các thuật toán điều khiển tương tranh dựa trên khoá
Ý tưởng chính của việc điều khiển tương tranh bằng khóa là bảo đảm dữ liệu dùng
chung cho các thao tác tương tranh chỉ được truy xuất mỗi lần một giao tác. Điều này
được thực hiện bằng cách liên kết một khóa chốt (lock) với mỗi đơn vị khóa. Khóa này
được giao tác đặt ra trước khi nó truy xuất và được điều chỉnh lại vào lúc nó hết sử dụng.
Hiển nhiên là một đơn vị khóa không thể truy xuất được nếu đã bị khóa bởi một giao tác
khác. Vì vậy yêu cầu khóa của một giao tác chỉ được trao nếu khóa đi kèm hiện không bị
một giao tác khác giữ.
Phần này nêu ra và phân tích các thuật toán cơ bản liên quan đến khoá. Qua các thuật
toán đã phân tích, chúng ta có thể đưa ra các biểu đồ thuật toán như sau:
Hình 2. 2: Biểu đồ khoá 2 pha (2PL) Hình 2. 3: Biểu đồ khoá 2 pha nghiêm ngặt


Giải phóng khoá
9

2.2.2.1 Thuật toán khoá 2 pha tập trung (Centralized 2PL) Hình 2. 4: Cấu trúc giao tiếp của khoá 2 pha trung tâm
2.2.2.2 Thuật toán khoá 2 pha phân tán (D2PL)
Hình 2. 5: Cấu trúc liên lạc của khoá 2 pha phân tán

Bộ xử lý dữ liệu tại
các site tham gia
TM điều phối TM site trung tâm
Yêu cầu khoá
(1)

p l
ị
ch tham gia

Các DM tham gia

Thao tác
(2)
Kết thúc thao tác
(3)
Giải phóng khoá
(4)
10

2.2.3 Thuật toán điều khiển tương tranh dựa trên timestamp
Không giống như các thuật toán dựa trên khoá, các thuật toán điều khiển tương tranh
dựa trên timestamp không cố gắng duy trì khả năng khả tuần tự bằng việc loại trừ lẫn
nhau. Thay vì như vậy, chúng lựa chọn theo một độ ưu tiên một thứ tự khả tuần tự và thực
thi các giao tác thích hợp. Để thiết lập thứ tự này, bộ quản lý giao tác gán cho mỗi giao
tác T
i
một timestamp duy nhất ts(T
i
) tại mỗi lần nó khởi chạy.
2.2.3.1 Thuật toán thứ tự timestamp cơ bản
Thuật toán TO cơ bản thực hiện minh bạch quy tắc TO. Bộ quản lý giao tác cộng tác
gán timestamp cho mỗi giao tác, xác định các site nào lưu trữ mục dữ liệu nào và gửi một
vài thao tác đến các site nào.
2.2.3.2 Thuật toán thứ tự timestamp bảo lưu
Thuật toán TO cơ bản không bao giờ gây ra các thao tác chờ mà thay vào đó là tái

giao tác T
ij
đến site j mà cần được lưu để xác thực T
ij
. Hiển nhiên, điều này tăng chi phí
lưu trữ.
2.4Quản lý Deadlock
Như được chỉ ra trước đó, bất kỳ thuật toán điều khiển tương tranh dựa trên khoá nào
có thể gây ra deadlock khi có sự loại trừ lẫn nhau trong việc truy cập tài nguyên dùng
chung (dữ liệu) và các giao tác phải đợi trên các tài nguyên bị khoá. Hơn nữa, như chúng
ta đã tìm hiểu, một vài thuật toán dựa trên thứ tự timestamp cũng yêu cầu các giao tác đợi
cũng có thể gây ra deadlock. Do đó, các hệ quản trị CSDL phân tán yêu cầu các thủ tục để
điều khiển chúng.
Có 3 phương thức để điều khiển deadlock là: ngăn ngừa deadlock, phòng tránh
deadlock, phát hiện và giải quyết deadlock.
Xác nhận Đọc Tính toán

Ghi

Đọc Tính toán

Xác nhận Ghi

12

2.4.1 Ngăn ngừa deadlock
Các phương pháp ngăn ngừa deadlock đảm bảo rằng các deadlock không thể xuất hiện
tại nơi đầu tiên. Do đó, bộ quản lý giao tác kiểm tra một giao tác tại lúc nó bắt đầu khởi
tạo và không cho phép nó thực thi nếu nó có thể gây ra deadlock. Để thực hiện việc kiểm
tra này, nó yêu cầu tất cả các mục dữ liệu mà giao tác có thể được truy cập được khai báo

deadlock cho các site thành phần. Do đó, giống như phát hiện deadlock kế thừa, có các bộ
phát hiện deadlock cục bộ tại mỗi site mà thông tin các đồ thị đợi cục bộ của chúng đến
site khác (trong thực tế, chỉ có các vòng deadlock vô tận là được gửi).
1.5 Kết luận chương
Chương 2 của luận án này trình bày chi tiết một số thuật toán điều khiển tương tranh
được cài đặt trong các DBMS và trên các site thương mại hiện nay. Từ nội dung của
chương 2 này, luận án đã chỉ rõ nguyên nhân gây ra deadlock và phương pháp hạn chế và
giả quyết các deadlock có thể xảy ra. Và từ chi tiết các thuật toán đã trình bày trong
chương này, làm cơ sở để thực hiện đánh giá và cài đặt trong chương 3.

DD
0x

DD
11

DD
12

DD
21

DD
22

DD
23

DD
24

1. Có 2 cơ chế cơ bản để tránh thực thi không tuần tự (thực hiện tương tranh):
WAITING và RESTARTING.
2. Thứ tự thực thi của 2 giao tác được xác định khác nhau.
3. Cơ chế xử lý khi xảy ra deadlock.
Bộ lập lịch

Bộ quản trị
dữ liệu
Bộ quản trị
dữ liệu
Bộ quản trị
dữ liệu
Bộ lập lịch

Bộ lập lịch

Site 1
Site 2
Site n
Dữ liệu
Dữ liệu
Dữ liệu
Giao tác
Bộ quản trị
giao tác
Giao tác
Giao tác
Giao tác
Giao tác
Giao tác

gian chờ.
o Thuật toán dựa trên timestamp bảo lưu: cũng tương tự như thuật toán dựa
trên timestamp cơ bản nhưng thuật toán bảo lưu sẽ tạo ra các độ trễ trong
việc truy cập vào dữ liệu, giảm được tình trạng tái khởi động lại nhiều lần,
tăng hiệu năng xử lý. Nhưng vì có độ trễ giữa các giao tác nên có thể gây ra
16

hiện tượng deadlock khi các giao tác khác truy cập cùng đến một mục dữ
liệu mà thời gian timeout của mỗi giao tác là rất lớn.
o Thuật toán dựa trên timestamp đa phiên bản: cũng giống như các thuật toán
dựa trên timestamp trên nhưng thuật toán này giảm được việc tái khởi động
và tránh được việc tạo độ trễ trong việc truy xuất dữ liệu, tăng được hiệu
năng xử lý và độ tin cậy cao hơn. Tuy nhiên, việc tạo ra đa phiên bản dẫn
đến chi phí lưu trữ dữ liệu sẽ cao hơn rất nhiều lần, ngoài ra khi thực hiện
lọc kết hợp dữ liệu, việc xử lý dữ liệu trở nên phức tạp. Điều này yêu cầu
các hệ quản trị cơ sở dữ liệu thực hiện xử lý dữ liệu tại các phiên bản một
các trong suốt và quản lý dữ liệu một cách nhất quán dữa các phiên bản.
3.2 Lựa chọn ứng dụng thuật toán điều khiển tương tranh và cài đặt thuật
toán trong giao dịch thương mại điện tử
3.2.1 Lựa chọn ứng dụng thuật toán điều khiển tương tranh trong giao dịch
thương mại điện tử
Qua quá trình tìm hiểu và khảo sát, tôi lựa chọn thuật toán điều khiển tương tranh dựa
trên timestamp để cài đặt cho ứng dụng thương mại trực tuyến.Việc lựa chọn thuật toán
này đảm bảo cho người sử dụng không bị mất mát thông tin nhưng vẫn đảm bảo chất
lượng sử dụng.
3.2.2 Cài đặt ứng dụng thuật toán điều khiển tương tranh trong giao dịch
thương mại điện tử
Trong phần này chúng ta cài đặt thuật toán điều khiển tương tranh trong môi trường
giao dịch thương mại điện tử phân tán. Chương trình được viết trên nền Microsoft dotNet
và chạy ổn định trên hầu hết các môi trường windows hỗ trợ NetFramework version 2 trở

Database
Web
Browser

Web
Server

18 Hình 3. 3: Các method được cài đặt trong Web Service
- Phần 2, Website thương mại phục vụ cho người sử dụng giao dịch trực tuyến qua
các Browser hỗ trợ môi trường web.
19 Hình 3. 4: Giao diện Website thương mại
- Phần 3, ứng dụng được chạy trên Windows trên môi trường của người sử dụng.

Hình 3. 5: Giao diện ứng dụng giao dịch thương mại trên môi trường người sử dụng
20

3.3 Kết luận chương
Chương này đã đưa ra những nhận xét và đánh giá các thuật toán điều khiển tương
tranh đã trình bày ở chương 2. Qua những đánh giá đã nêu ra, chương này đã lựa chọn
thuật toán trong việc cài đặt ứng dụng điều khiển tương tranh trong giao dịch thương mại
điện tử.
Chương này cũng trình bày ứng dụng thương mại điện tử mà đã được cài đặt thuật
toán điều khiển tương tranh do tác giả thiết kế và viết ứng dụng.
21


23

TÀI LIỆU THAM KHẢO
[1] Chu Kỳ Quang (2003), ”Điều khiển tương tranh trong hệ thống tin học Dịch vụ tiết
kiệm bưu điện”, Tạp chí Bưu Chính Viễn Thông.
[2] Papadimitriou, Christos H. (1986), The theory of database concurrency control,
Computer Science Press.
[3] Jeffrey D. Ullman (1988), Principles of Database and Knowledge: Base Systems,
Computer Science Press.
[4] Eswaran, K. P., Gray, J. N., Lorie, R. A., and Traiger, I. L. (1976), “The notions of
consistency and predicate locks in a database system”, Communications of the ACM,
19(11).
[5] Mohan, C., Lindsay, B., and Obermarck, R. (1986), “Transaction management in the
R* distributed database management system”, ACM Transactions on Database Systems,
11(4), pp.378-396.
[6] The Tandem Database Group, (1987, revised 1988), “NonStop SQL, A Distributed,
High-Performance, High-Availability Implementation of SQL”, Tandem Systems Review.
[7] A. Borr (1988), “High-Performance SQL through low-level System Intergration”,
Tandem Systems Review, 4(2), pp.63-72.
[8] H.T. Kung and John T. Robinson (1981), “On Optimistic Methods of Concurrency
Control”, ACM Transactions on Database Systems, 6(2), pp.213-226.
[9] Abadi, D., Carney, D., Cetintemel, U., Cherniack, M., Convey, C., Lee, S.,
Stonebraker,M., Tatbul, N., and Zdonik, S (2003) “A new model and architecturefor data
stream management”, The International Journal on Very Large Data Bases, 12(2), pp.
120-139.
[10] Lecture (2008),“Distributed Concurrency Control”, Tsinghua Universary.
[11] Dean Leftingwell (2011), “Agile Software Requirements: Lean Requirements
Practices for Teams, Programs, and the Enterprise”, Agile Software Development Series.
[12] Özsu, M. Tamer, Valduriez, Patrick (2011), “Principles of distributed database