Hệ quản trị cơ sở dữ liệu - Chương 6: Hệ thống phục hồi

ng các giải pháp gom cụm lại 
rất mất thời gian. 
• Phải thu nhặt rác. Mỗi khi giao dịch bàn giao, các trang chứa giá trị dữ liệu cũ đã bị sửa 
đổi bởi giao dịch sẽ trở thành không truy xuất được. Vì chúng không thuộc danh sách các 
trang tự do nhưng cũng không chứa dữ liệu hữu dụng. Ta gọi chúng là “rác”. Cần thiết 
phải định kỳ tìm kiếm và thêm các trang rác vào trong danh sách các trang tự do. Hành 
động này được gọi là “thu nhặt rác”. 
• Ngoài ra, kỹ thuật phân trang bóng sẽ gặp nhiều khó khăn hơn kỹ thuật dựa vào sổ ghi khi 
cần được tinh chỉnh để đáp ứng cho yêu cầu phục vụ song song cho nhiều giao dịch. Vì 
những lý do trên, kỹ thuật phân trang bóng không được sử dụng rộng rãi lắm. 
 PHỤC HỒI VỚI CÁC GIAO DỊCH CẠNH TRANH 
Cho dến bây giờ, ta chỉ xét các kỹ thuật phục hồi áp dụng cho các giao dịch được thực thi 
tuần tự. Bây giờ chúng ta sẽ tìm cách cải tiến kỹ thuật dựa vào sổ ghi nhằm đáp ứng yêu cầu phục 
vụ đồng thời cho nhiều giao dịch cạnh tranh. Ý tưởng thực hiện là: Không quan tâm đến số lượng 
các giao dịch cạnh tranh, hệ thống vẫn sử dụng một vùng đệm đĩa và một sổ ghi lộ trình. Các khối 
đệm được chia sẻ bởi tất cả các giao dịch. Chúng ta sẽ cho phép việc cập nhật tức thời cơ sở dữ 
liệu và cho phép một khối đệm có nhiều hạng mục dữ liệu được cập nhật bởi một hoặc nhiều giao 
dịch. 
TRAO ĐỔI VỚI ĐIỀU KHIỂN CẠNH TRANH 
Cơ chế phục hồi phụ thuộc rất nhiều vào cơ chế điều khiển cạnh tranh được sử dụng. Để 
cuộn lại một giao dịch thất bại ( failed transaction ), người ta phải huỷ bỏ ( undo) các cập nhật 
được thực hiện bởi giao dịch. Giả sử giao dịch T0 phải bị cuộn lại và một hạng mục dữ liệu Q đã 
bị T0 thay đổi giá trị và cần phải được đặt lại giá trị cũ. Bằng cách sử dụng kỹ thuật dựa vào sổ ghi 
lộ trình, ta trả lại giá trị cũ cho Q bằng cách sử dụng một log record. Giả thiết lại có giao dịch thứ 
hai T1 cũng vừa cập nhật Q xong, trước khi T0 bị cuộn lại. Như vậy, sự cập nhật được thực hiện 
bởi T1 sẽ bị mất đi nếu T0 bị cuộn lại. 
Biện pháp khắc phục là: nếu một giao dịch T đã cập nhật một hạng mục dữ liệu Q, thì 
không một giao dịch nào khác có quyền cập nhật lên hạng mục dữ liệu đó trong khi T chưa bàn 
giao hoặc chưa bị cuộn lại. Chúng ta có thể đảm bảo yêu cầu trên được thoả bằng cách sử dụng kỹ 
thuật ”chốt hai kỳ nghiêm ngặt” (strict two-phase locking). 
CUỘN LẠI GIAO DỊCH: 
Phương pháp để cuộn lại (rollback) một giao dịch Ti, sử dụng sổ ghi, trong môi trường 
cạnh tranh như sau: 
1. Dò ngược sổ ghi lộ trình để tìm ra các log record có dạng . 
129CHƯƠNG VI HỆ THỐNG PHỤC HỒI Trang 
H Ệ Q U Ả N T R Ị C Ơ S Ở D Ữ L I Ệ U 
2. Hạng mục dữ liệu Xj sẽ được trả lại giá trị cũ V1. 
3. Việc dò tìm kết thúc khi tìm thấy mẫu tin . 
Việc dò ngược sổ ghi lộ ¹eó một ý nghĩa rất quan trọng, do một giao dịch có thể đã cập 
nhật một hạng mục dữ liệu nhiều hơn một lần. Một ví dụ: Xét một cặp log records như sau: 
Cặp mẫu tin này thể hiện hai hành động cập nhật hạng mục dữ liệu A của giao dịch Ti. 
Nếu dò ngược sổ ghi lộ trình, A sẽ được trả về giá trị đúng là 10. Ngược lại, A sẽ nhận giá trị sai 
là 20. 
Nếu kỹ thuật strict two-phase locking được sử dụng để điều khiển cạnh tranh, thì việc trả 
về giá trị cũ cho một hạng mục dữ liệu sẽ không xoá đi những tác động của các giao dịch khác lên 
hạng mục dữ liệu này. 
CÁC ĐIỂM KIỂM SOÁT 
Ở phần V.4.3, người ta đã sử dụng điểm kiểm soát (checkpoint) để làm giảm số lượng các 
log record mà hệ thống phục hồi phải dò tìm trong sổ ghi trong giai đoạn phục hồi sau lỗi. Nhưng, 
do đã giả thiết là không có cạnh tranh nên giải pháp V.4.3 chỉ xét đến những giao dịch sau trong 
quá trình khôi phục lỗi: 
• Những giao dịch được khởi động sau điểm kiểm soát gần đây nhất. 
• Một giao dịch (nếu có) đang trong trạng thái hoạt động (active) tại thời điểm người ta đặt 
điểm kiểm soát gần đây nhất. 
Tình huống càng phức tạp khi các giao dịch được thực thi cạnh tranh. Có nghĩa là tại thời 
điểm đặt điểm kiểm soát, có thể có nhiều giao dịch đang ở trong trạng thái hoạt động. 
Trong một hệ thống xử lý các giao dịch cạnh tranh, ta yêu cầu rằng: một mẫu tin ghi dấu kiểm 
soát (checkpoint log record) phải có dạng như sau: 
Trong đó L là danh sách các giao dịch đang hoạt động tại thời điểm đặt điểm kiểm soát. 
Một lần nữa, ta qui ước rằng: khi hành động đặt điểm kiểm soát đang diễn ra, các giao 
dịch không được phép thực hiện bất kỳ thao tác cập nhật dữ liệu nào cả trên các khối đệm lẫn 
trên sổ ghi lộ trình. 
Tuy nhiên, qui ước trên lại gây phiền toái, bởi vì các giao dịch phải ngừng hoạt động khi 
đặt điểm kiểm soát. Một kỹ thuật nâng cao giải quyết điểm phiền toái này là “Điểm kiểm soát 
mờ” (fuzzy checkpoint). 
PHỤC HỒI KHỞI ĐỘNG LẠI ( Restart Recovery ) 
Khi hệ thống phục hồi sau lỗi, nó tạo ra hai danh sách: undo-list bao gồm các giao dịch 
cần phải huỷ bỏ và redo-list bao gồm danh sách các giao dịch cần được làm lại. 
Qui trình tạo lập hai danh sách redo-list, undo-list được thực hiện như sau: 
1. Đầu tiên, chúng sẽ rỗng. 
2. Dò ngược sổ ghi lộ trình, kiểm tra các mẫu tin cho đến khi tìm được mẫu tin 
 đầu tiên: 
a. Với mỗi mẫu tin được tìm thấy theo dạng , ta thêm Ti vào trong redo-
list. 
b. Với mỗi mẫu tin được tìm thấy theo dạng , nếu Ti không thuộc redo-list 
thì thêm Ti vào trong undo-list. 
c. Khi tất cả các log record đã được xem xét, ta kiểm tra danh sách L trong mẫu tin 
. Với mọi giao dịch Ti trong L, nếu Ti không thuộc redo-list thì 
thêm Ti vào undo-list. 
130CHƯƠNG VI HỆ THỐNG PHỤC HỒI Trang 
H Ệ Q U Ả N T R Ị C Ơ S Ở D Ữ L I Ệ U 
Khi hai danh sách redo-list, undo-list được thiết lập xong, tiến trình phục hồi được tiến 
hành như sau: 
1. Dò ngược lại sổ ghi và thực hiện thủ tục undo đối với mỗi log record thuộc về giao 
dịch Ti trong undo-list. Các log record của các giao dịch nằm trong danh sách redo-list 
sẽ bị bỏ qua trong giai đoạn này. Việc dò ngược sẽ ngưng khi mẫu tin được 
tìm thấy cho mọi giao dịch Ti thuộc danh sách undo-list. 
2. Định vị mẫu tin gần đây nhất trong log. 
3. Dò sổ ghi theo chiều xuôi bắt đầu từ mẫu tin gần đây nhất và thực 
hiện thủ tục redo đối với mỗi log record thuộc về giao dịch Ti nằm trong danh sách 
redo-list. Trong giai đoạn này, bỏ qua các log record của các giao dịch thuộc danh 
sách undo-list. 
Việc xử lý ngược ở bước 1 là rất quan trọng, nhằm đảm bảo kết quả trả về của cơ sở dữ 
liệu là đúng. 
Sau khi tất cả các giao dịch trong danh sách undo-list bị huỷ bỏ, tất cả các giao dịch trong 
danh sách redo-list sẽ được làm lại. Sau khi tiến trình phục hồi thành công, xử lý giao dịch được 
tiếp tục. 
Việc thực hiện huỷ bỏ các giao dịch trong undo-list trước khi làm lại các giao dịch trong 
redo-list có ý nghĩa rất quan trọng. Nếu làm ngược lại, vấn đề sau sẽ phát sinh: Giả sử hạng mục 
dữ liệu A có giá trị khởi đầu là 10. Giao dịch Ti đổi A thành 20 sau đó Ti bị huỷ bỏ. Sau đó, một 
giao dịch khác Tj cập nhật A thành 30. Đến đây thì hệ thống bị lỗi ngừng hoạt động. Hiện trạng 
của sổ ghi tại thời điểm hệ thống bị lỗi như sau: 
Nếu thực hiện redo trước, A sẽ được đặt giá trị 30. Sau đó thực hiện undo, A sẽ được đặt 
giá trị 10, mà giá trị này sai. Giá trị cuối cùng của A phải là 30. 
ĐIỂM KIỂM SOÁT MỜ (fuzzy checkpoint): 
Kỹ thuật fuzzy checkpoint cho phép các giao dịch được cập nhật dữ liệu trên các khối đệm 
khi checkpoint-record đã được viết xong nhưng trước thời điểm các khối đệm đã sửa đổi được ghi 
ra đĩa. 
Ý tưởng thực hiện fuzzy checkpoint như sau: Thay vì phải dò ngược sổ ghi để tìm mẫu tin 
checkpoint, ta sẽ lưu vị trí của mẫu tin checkpoint cuối cùng trong sổ ghi vào một chỗ cố định 
trong đĩa gọi là last_checkpoint. Tuy nhiên, thông tin này sẽ không được cập nhật khi một mẫu 
tin checkpoint được ghi ra đĩa. Thay vào đó, trước khi một mẫu tin checkpoint được ghi ra sổ ghi, 
ta tạo ra một danh sách các khối đệm bị sửa đổi. Thông tin last_checkpoint được cập nhật chỉ sau 
khi tất cả các khối đệm bị sửa đổi được ghi ra đĩa. 
last_checkpoint chỉ được dùng cho mục đích undo. 
131CHƯƠNG VI HỆ THỐNG PHỤC HỒI Trang 
H Ệ Q U Ả N T R Ị C Ơ S Ở D Ữ L I Ệ U 
BÀI TẬP CHƯƠNG VI 
VI.1. Trình bày các điểm khác nhau giữa 3 kiểu lưu trữ: lưu trữ không ổn định, lưu trữ ổn định 
và lưu trữ bền theo tiêu chuẩn đánh giá là chi phí cài đặt. 
VI.2. Thực tế, lưu trữ bền không thể thực hiện được. Giải thích tại sao? Hệ cơ sở dữ liệu giải 
quyết vấn đề này như thế nào? 
VI.3. So sánh các kỹ thuật cập nhật tức thời và cập nhật có trì hoãn trong sơ đồ phục hồi dựa 
vào sổ ghi lộ trình theo các tiêu chuẩn: tính dễ cài đặt và tổng chi phí thực hiện. 
VI.4. Giả sử rằng kỹ thuật cập nhật tức thời được sử dụng trong hệ thống. Bằng ví dụ, hãy chỉ ra 
rằng: tình trạng không nhất quán dữ liệu sẽ xảy ra nếu các log record không được ghi ra thiết 
bị lưu trữ bền trước khi giao dịch bàn giao (commit). 
VI.5. Giải thích mục đích của cơ chế điểm kiểm soát (checkpoint). Hành động đặt điểm kiểm 
soát nên được thực hiện theo chu kỳ bao lâu là hợp lý? 
VI.6. Khi hệ thống phục hồi sau lỗi, nó xây dựng 2 danh sách: undo-list và redo-list. Giải thích 
tại sao các log record của các giao dịch trong danh sách undo-list phải được xử lý theo thứ tự 
ngược, trong khi những log record trong danh sách redo-list lại được xử lý theo chiều xuôi? 
VI.7. So sánh sơ đồ phục hồi phân trang bóng và sơ đồ phục hồi bằng sử dụng sổ ghi lộ trình 
theo tiêu chuẩn: tính dễ cài đặt và tổng chi phí thực hiện. 
VI.8. Giả sử một cơ sở dữ liệu có 10 khối đĩa liên tiếp (khối 1, 2, 3, ..., 10). Hãy thể hiện trạng 
thái của buffer và thứ tự vật lý có thể có của các khối sau các thao tác cập nhật sau, giả sử: kỹ 
thuật phân trang bóng được sử dụng, buffer trong bộ nhớ chỉ đủ chứa 3 khối, chiến lược quản 
lý buffer là LRU (Least Recently Used) 
Đọc khối 3 
Đọc khối 7 
Đọc khối 5 
132CHƯƠNG VI HỆ THỐNG PHỤC HỒI Trang 
H Ệ Q U Ả N T R Ị C Ơ S Ở D Ữ L I Ệ U 
Đọc khối 3 
Đọc khối 1 
Sửa đổi khối 1 
Đọc khối 10 
Sửa khối 5 
133CHƯƠNG VI HỆ THỐNG PHỤC HỒI Trang