Tài liệu Báo cáo thu hoạch môn học cơ sở dữ liệu nâng cao nghiên cứu xử lý đồng hành trong cơ sở dữ liệu phân tán và ứng dụng xây dựng chương trình demo máy rút tiền tự động đa ngân hàng.

Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 1/49 ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG KHÓA 2 ---- oOo ---- BÁO CÁO THU HOẠCH MÔN HỌC CƠ SỞ DỮ LIỆU NÂNG CAO ĐỀ TÀI: NGHIÊN CỨU XỬ LÝ ĐỒNG HÀNH TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ ỨNG DỤNG XÂY DỰNG CHƯƠNG TRÌNH DEMO MÁY RÚT TIỀN TỰ ĐỘNG ĐA NGÂN HÀNG. Giảng viên phụ trách: TS Đỗ Phúc. Nhóm sinh viên thực hiện: Nguyễn Nam Hải – CH0403005 Phan Nhựt Long – CH0403009 Phan Thanh Nam – CH0403011 Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 2/49 LỜI CẢM ƠN Nhóm sinh viên thực hiện xin gửi lời cảm ơn chân thành đến Thầy Đỗ Phúc, Thầy đã tận tình hướng dẫn chúng em trong suốt thời gian môn học cũng như trả lời trực tuyến. Do thời gian và trình độ còn nhiều hạn chế cũng như số lượng lớn các thuật ngữ, khái niệm cần trình bày, chắc chắn khóa luận còn có chỗ sai sót. Nhóm chúng em rất mong nhận được ý kiến góp ý và động viên của các Thầy/Cô cũng như tất cả các Anh/Chị và các bạn để khóa luận được hoàn thiện hơn nữa. Xin chân thành cảm ơn! ‰ Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 3/49 1. Cơ sở dữ liệu phân tán (CSDLPT) a.Khái niệm CSDLPT CSDLPT là tập hợp các CSDL được liên kết logic và làm việc một cách trong suốt đối với người sử dụng. Khái niệm “trong suốt đối với người sử dụng” hàm nghĩa người sử dụng có thể truy cập tất cả các CSDL như là chúng thuộc về một CSDL duy nhất. Trong định nghĩa trên có hai điểm quan trọng là: ; Phân tán: dữ liệu có sự độc lập vị trí, người sử dụng không biết nơi lưu trữ CSDL và có thể di chuyển dữ liệu từ vị trí vật lý này đến vị trí vật lý khác mà không ảnh hưởng đến người dùng khác. ; Tương quan logic: dữ liệu có một số thuộc tính ràng buộc chúng với nhau, điều này có thể giúp ta phân biệt được CSDLPT với một tập hợp các CSDL cục bộ hoặc các tập tin CSDL lưu giữ tại các vị trí khác nhau trên một mạng máy tính. Ngày nay, tầm quan trọng của CSDLPT là không thể phủ nhận và các lý do chính yếu để giải thích tại sao lại cần sử dụng và phát triển CSDLPT là: ; Nguyên nhân về tổ chức và kinh tế: Các tổ chức, đặc biệt là các tổ chức kinh tế lớn thường có khuynh hướng mở rộng địa bàn hoạt động (mở các chi nhánh mới) nhưng vẫn phải đảm bảo tính thông suốt và nhất quán của hệ thống CSDL. ; Sự liên kết các CSDL đang tồn tại: CSDLPT là giải pháp tự nhiên khi có các CSDL đang tồn tại và sự cần thiết xây dựng một ứng dụng toàn cục. Trong trường hợp này CSDLPT được làm từ dưới lên (bottom-up) từ các CSDL đã tồn tại từ trước. Tiến trình này có thể đòi hởi phải cấu trúc lại một cách cục bộ ở một mức độ nhất định. Nhưng dù sao những sửa đổi này vẫn nhỏ hơn nhiều so với việc tạo lập một CSDL tập trung hoàn toàn mới. ; CSDLPT cho phép mỗi vị trí lưu giữ CSDL riêng nhằm hỗ trợ truy cập hiệu quả và tức thì các dữ liệu được dùng thường xuyên. Các dữ liệu này vẫn có thể được dùng ở những nơi khác nhưng có tần suất sử dụng ít hơn. ; Nếu có sự cố hư hỏng máy tính cục bộ hoặc đường liên lạc bị sụp đổ thì phần còn lại của mạng vẫn tiếp tục làm việc được. ; Làm giảm tổng chi phí tìm kiếm. ; Tính tin cậy và sẵn sàng cao. b. Thuận lợi của CSDLPT: ; Khả năng phục hồi nhanh chóng (Resilience): việc truy cập dữ liệu không phụ thuộc vào một máy tính hay một đường kết nối trên mạng. Nếu có bất kỳ một lỗi nào xảy ra thì sẽ có một vài CSDL được truy cập trên các nút cục bộ khác, hơn nữa, nếu có lỗi xảy ra trên đường kết nối thì có thể đường nối dữ liệu khác được chọn thay thế. ; Giảm dòng dữ liệu trên đường truyền đồng thời tăng khả năng trả lời. ; “Trong suốt vị trí” cho phép dữ liệu vật lý di chuyển mà không cần thay đổi ứng dụng hay thông báo cho người sử dụng. ; Cách thức mở rộng dễ dàng: dễ dàng phát triển, mở rộng và điều này là nhờ vào: Ö Nhiều bộ xử lý có thể được thêm vào mạng; Ö Nhiều CSDL có thể được thêm vào trên một nút mạng; Ö Cập nhật phần mềm độc lập với cấu trúc vật lý. c. Bất lợi của CSDLPT: Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 4/49 ; Phí tổn gây ra bởi các tác vụ điều khiển và phối hợp có thể làm giảm đáng kể hiệu năng. ; Một khi dữ liệu được sao lưu ở nhiều vị trí khác nhau sẽ dẫn đén việc gia tăng các tài nguyên cần sử dụng nhằm đảm bảo cập nhật đồng thời và nhất quán; việc sao lưu cần thêm không gian lưu trữ. ; Vấn đề bảo đảm an toàn phức tạp hơn. ; Khó khăn trong việc thay đổi: hiện nay chưa có một công cụ hoặc phương pháp nào tối ưu để trợ giúp người sử dụng có thể chuyển đổi dữ liệu từ tập trung sang phân tán và ngược lại. d. các thành phần của CSDLPT: Ví trí DDBMS DC LDBMS GSC GSC Computer Network DB LDBMS = CSDL cục bộ DC = Truyền dữ liệu Communications GSC = Global Systems Catalog DDBMS = Hệ QTCSDLPT DDBMS DC Ví trí Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 5/49 2. Giao tác (Transaction) a. Khái niệm giao tác Giao tác là một chuỗi lệnh thực hiện trên các đối tượng dữ liệu (các dòng tuples, cột- fields) trong một hệ cơ sở dữ liệu (CSDL). Các lệnh của giao tác bao gồm: • Các lệnh thực hiện: - Read(): Đọc dữ liệu từ CSDL và trả về giá trị phần tử được lưu trong CSDL. - Write(): Lưu giá trị của phần tử vào CSDL. • Các lệnh giao tác: - Start(): Bắt đầu thực hiện một giao tác - Commit(): Kết thúc thành công một giao tác. - Abort(): Hủy bỏ một giao tác. Hình thức hóa khái niệm giao tác như sau: Gọi Oij(x) là lệnh Oj của giao tác Ti truy xuất trên cùng mục dữ liệu x, trong đó: Oj∈{Read,Write} và lệnh Oj là nguyên tử (không phân chia được). Đặt OSi=UjOij Ni∈{Commit,Abort} Khi đó, Ti={Σi, T2 thì L1 < L2 với L1, L2 là điểm khoá của T1, T2 Chứng minh: Bằng các ví dụ, việc chứng minh định lý này sẽ được dễ dàng hơn. Ví dụ: Trên mục dữ liệu x có các thao tác (ký hiệu là OP) đụng độ. T1 OP1 trên x với tại thời điểm t1 T2 OP2 trên x với tại thời điểm t2 t1 < t1 ► Vì vậy: t1 sẽ giữa khoá trên x tại t1, tương tự với t2. Ta đã biết, hai khoá (mà có ít nhất một khoá là khoá X) không thể đồng thời tồn tại tại cùng một thời điểm . ► Vì vậy T2 chỉ có thể khoá x sau khi T1 đã giải phóng khoá, bởi vậy, với t’ và t’’ bất kỳ thoả t1 < t’ < t’’ ≤ t2: ● T1 giải phóng khoá trên x tại t’ ● T2 khoá x tại t’’ ► Theo định nghĩa của L1 và L2 ta có: ● L1 < t’ < t’’ ≤ L2 và vì vậy ta có Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO ● L1 < L2 Trang 12/49 ⇐ điều phải chứng minh! ► Giả sử có một lịch biểu tuân theo 2PL có chứa chu trình sau: T1 -> T2, T2 -> T3, T3 ->T1 thì theo hệ quả trên: ● L1 < L2 ● L2 < L3 ● L3 < L1 Như vậy có sự mâu thuẫn: L1 < L1 Vì vậy sẽ không có chu trình và lịch biểu là tuần tự. ii. Nội dung thuật toán: (1) Với mỗi giao tác Ti trong lịch biểu H: Tạo một đỉnh có tên là Ti trong đồ thị có hướng; (2) Với mỗi trường hợp giao tác Tj trong H thực hiện một lệnh read(x) để đọc giá trị x mà nó đã được ghi bởi lệnh write(x) của giao tác Ti thì: Tạo một cung từ Ti -> Tj trong đồ thị SG; (3) Với mỗi trường hợp giao tác Tj trong H thực hiện một lệnh write(x) để ghi trị x mà nó đã được đọc bởi lệnh read(x) của giao tác Ti thì: Tạo một cung từ Ti -> Tj trong đồ thị SG; (4) Với mỗi trường hợp giao tác Tj trong H thực hiện một lệnh write(x) để ghi trị x mà nó đã được đưọc ghi bởi lệnh write(x) của giao tác Ti trước đó thì: Tạo một cung từ Ti -> Tj trong đồ thị SG; (5) Lịch biểu H là khả tuần tự nếu và chỉ nếu đồ thị SG không có chu trình; Ví dụ: S1:W2(x)W1(x)R3(x)R1(x)R1(x)W2(y)R3(y)R3(z)R2(x) Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO S1 bất khả tuần tự vì đồ thị có chu trình Trang 13/49 S4: R2(z)W2(x)W2(y)W1(x)R1(x)R3(x)R3(z)R3(y) S4 là lịch biểu khả tuần tự vì đồ thị không có chu trình d. Khả năng tự phục hồi: Chúng ta đã xét đến các lịch biểu có thể chấp nhận được trên quan điểm nhất quán của cơ sở dữ liệu với ngầm định rằng không có các lỗi giao dịch xảy ra. Bây giờ chúng ta sẽ chỉ ra tác động của các lỗi giao dịch khi thực hiện đồng thời. Nếu một giao dịch Ti bị lỗi vì một lý do nào đó, ta cần phải tháo bỏ tác động của giao dịch này để đảm bảo tính nguyên tố của giao dịch. Trong một hệ thống cho phép thực hiện đồng thời, nếu Ti bị hủy bỏ thì phải đảm bảo rằng giao dịch Tj nào đó phụ thuộc vào Ti cũng phải được hủy bỏ. Để đạt được sự đảm bảo này, chúng ta cần đặt ra các hạn chế trên kiểu của các lịch được cho phép trong hệ thống này. Các lịch có khả năng tự phục hồi: Xét một lịch biểu sau: T8 T9 Read(A); Write(A); Read(A); Read(B); Trong đó: T8 và T9 là các giao dịch có các lệnh thực hiện được mô tả tương ứng ở trên. Bởi ta đang xét đến việc đảm bảo tính nguyên tố của giao dịch trong quá trình chuyển giao giữa các giao dịch, nên ở đây ta sẽ xét trường hợp hệ thống cho phép T9 chuyển giao ngay sau khi thực hiện lệnh Read(A). Do vậy T9 chuyển giao trước T8. Bây giờ giả sử rằng T8 bị lỗi trước khi nó Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 14/49 chuyển giao. Do T9 đã đọc giá trị của khoản mục dữ liệu A được ghi bởi T8, chúng ta phải hủy bỏ T9 để đảm bảo tính nguyên tố của giao dịch. Tuy nhiên T9 đã được chuyển giao và không thể hủy bỏ. Do vậy, chúng ta có một tình huống ở đó lịch không thể phục hồi một các đúng đắn sau lỗi của T8. Lịch biểu mà ta vừa thấy ở trên với việc chuyển giao tức thời sau lệnh Read(A) là một ví dụ của một lịch không thể phục hồi mà sẽ không được phép. Hầu hết các hệ cơ sở dữ liệu yêu cầu rằng tất cả các lịch phải có khả năng phục hồi. Một lịch có khả năng phục hồi là một lịch ở đó với mỗi cặp giao dịch Ti và Tj, trong đó: Tj đọc một khoản mục dữ liệu được ghi trước đó bởi Ti thì thao tác chuyển giao của Ti phải xuất hiện trước thao tác chuyển giao của Tj. e. Các lịch không lan truyền: Khi có một lịch có khả năng phục hồi, để phục hồi một cách đúng đắn từ lỗi của một giao dịch Ti, chúng ta phải quay lui một số giao dịch. Các tình huống như vậy xảy ra nếu các giao dịch đã đọc dữ liệu được ghi bởi Ti. Ta hãy xét một lịch được thể hiện như sau: T10 T11 T12 Read(A); Read(B); Write(A); Read(A); Write(A); Read(A); Giao dịch T11 đọc một giá trị của A được ghi bởi giao dịch T10. Giao dịch T12 đọc một giá trị của A được ghi bởi giao dịch T11. Giả sử rằng tại thời điểm này giao dịch T10 bị lỗi, do vậy T10 phải quay lui. Do T11 phụ thuộc vào T10 nên T11 cũng phải quay lui. Do T12 phụ thuộc vào T11 nên T12 cũng phải quay lui. Hiện tượng này, trong đó một giao dịch bị lỗi dẫn đến một dãy các giao dịch phải quay lui, được gọi là quay lui lan truyền. Quay lui lan truyền là không mong muốn, do nó dẫn đến việc tháo bỏ một số đáng kể công việc. Có thể mong muốn hạn chế các lịch mà đối với chúng các lan truyền quan lui không thể xảy ra. Các lịch như thế được gọi là các lịch không lan truyền. Một lịch không lan truyền là một lịch trong đó với mỗi cặp các giao dịch Ti và Tj – mà Tj đọc một khoản mục dữ liệu được ghi trước đó bởi Ti, thì thao tác chuyển giao của Ti phải xuất hiện trước thao tác đọc của Tj. Từ đây ta dễ dàng thấy rằng: một lịch không lan truyền cũng là một lịch có khả năng phục hồi. Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 15/49 f. Cài đặt tính độc lập: Từ những trình bày ở trên, ta đã thấy những tính chất một lịch biểu phải có để đảm bảo tính nhất quán của cơ sở dữ liệu và cho phép các lỗi giao dịch được điều khiển trong một phương pháp an toàn. Đặc biệt, các lịch biểu tuần tự, khả tuần tự và không lan truyền thỏa mãn các yêu cầu này. Các sơ đồ điều khiển đồng hành khác nhau có thể được sử dụng để đảm bảo rằng: thậm chí khi nhiều giao dịch được thực hiện đồng thời, chỉ các lịch chấp nhận được sinh ra, không kể đến việc chia sẻ tài nguyên giữa các giao dịch như thế nào. Một ví dụ thô sơ về điều khiển đồng hành: một giao dịch yêu cầu một khóa trên toàn bộ cơ sở dữ liệu trước khi nó thực hiện và giải phóng khóa sau khi nó đã chuyển giao. Trong khi một giao dịch giữ một khóa, không một giao dịch nào được phép yêu cầu khóa, do vậy tất cả các giao dịch khác thực hiện đồng thời với giao dịch này phải đợi cho đến khi nào khóa được giải phóng. Do chính sách khóa như vậy, nên chỉ có một giao dịch được thực hiện tại một thời điểm. Vì vậy, chỉ có các lịch tuần tự được sinh ra. Chúng là các lịch tuần tự tầm thường và dễ dàng thấy rằng chúng là các lịch biểu không lan truyền. Một sơ đồ điều khiển đồng hành như sơ đồ trên dẫn đến hiệu năng kém do nó buộc các giao dịch phải đợi các giao dịch trước đó hoàn thành trước khi nó được khởi động. Nói cách khác, nó cung cấp một mức thấp của khả năng xử lý đồng thời. Mục đích của các sơ đồ điều khiển đồng hành là cung cấp một mức hiệu năng cao của khả năng xử lý đồng thời, trong khi vẫn đảm bảo rằng tất cả các lịch biểu có thể được sinh ra là tuần tự, khả tuần tự và không lan truyền. Trong phần tiếp theo dưới đây chúng ta sẽ xét đến các giao thức điều khiển đồng hành. 4. Khoá chốt: a. Các khái niệm - Khoá chốt là một cơ chế thường dùng để giải quyết những vấn đề liên quan đến việc đồng bộ hoá dữ liệu truy cập dùng chung. Mỗi phần tử dữ liệu đều có một khoá chốt kết hợp với chúng. - Bộ xếp lịch đảm bảo rằng chỉ duy nhất giao tác có thể giữ khoá chốt trong một thời điểm, và chỉ có một giao tác có thể truy xuất dữ liệu đó tại cùng một thời điểm. - Khoá chốt được bộ xếp lịch (schedule manager) dùng để đảm bảo tính khả tuần tự. - Trước khi một giao tác có thể truy cập dữ liệu dùng chung, bộ xếp lịch lịch sẽ khảo sát trạng thái khoá chốt của những dữ liệu này. + Nếu không có giao tác nào khác đang giữ chúng thì bộ xếp lịch sẽ phát lệnh thông báo khoá dữ liệu này lại và sau đó các giao tác thực hiện các lệnh của mình trên dữ liệu đó. + Nếu dữ liệu đang bị khoá bởi giao tác T2, thì giao tác này phải chờ cho đến khi nào T2 giải phóng khoá đó. Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 16/49 - Có 2 loại khoá chốt: khoá đọc (read lock, rl) và khoá ghi (write lock, wl). + rli(x): khoá đọc trên phần tử dữ liệu x của giao tác Ti + wlj(x): khoá ghi trên phần tử dữ liệu x của giao tác Tj - Hai khoá pli(x) và qlj(y) đụng độ nếu x=y, i≠j, có nghĩa rằng chúng khoá trên cùng một phần tử dữ liệu, chúng được phát sinh từ hai giao tác khác nhau và một trong hai thao tác là ghi. b. Những quy tắc quản lý và sử dùng khoá ™ Qui tắc 1: - Khi nhận được một thao tác pi[x] từ bộ quản lý giao tác (Transaction Manager, TM), bộ xếp lịch kiểm tra nếu pli[x] đụng độ với một vài qlj[x] được đặt trước đó. + Nếu đúng, nó sẽ trì hoãn pi[x] và buộc Ti chờ cho đến khi nó có thể đặt được khoá cần thiết. + Nếu không đụng độ, bộ xếp lịch (scheduler) sẽ đặt pli[x] và gởi pi[x] đến bộ quản lý dữ liệu (Data Manager, DM). - Quy tắc này nhằm hạn chế hai giao tác truy xuất đồng thời một phần tử dữ liệu trong tình trạng đụng độ. ™ Qui tắc 2: - Mỗi khi bộ xếp lịch đặt khoá cho Ti, pli[x], nó không thể giải phóng khoá đó cho đến khi DM trả lời đã xử lý thao tác tương ứng của khoá, pi[x]. ™ Qui tắc 3: - Mỗi khi bộ xếp lịch đã giải phóng một khoá cho một giao tác, nó không thể lấy tiếp bất kỳ khoá nào cho giao tác đó. - Quy tắc (3) được gọi là quy tắc hai giai đoạn, là nguồn gốc của khoá chốt hai giai đoạn. c. Khoá chốt hai pha (Two phase locking, 2PL): - 2PL là một trong những 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 lệnh của các giao tác. - Nhiệm vụ của bộ xếp lịch 2 giai đoạn (Two phase locking, 2PL) là quản lý khoá chốt và điều khiển giao tác khi nào lấy và khi nào giải phóng khoá. - 2PL nhằm đồng bộ hoá việc đọc và ghi. Trước khi đọc mục dữ liệu x, phải khóa x (khóa do đọc). Trước khi ghi lên x, giao tác phải khóa mục x ( khóa do ghi). - Quá trình cấp phát và thu hồi khóa được thể hiện ở biểu đồ khoá 2PL sau: Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Giai đoạn thu hồi Giai đoạn tăng trưởng Trang 17/49 Hình trên cho thấy bộ quản lý khoá giải phóng khoá ngay sau khi hoàn tất việc truy xuất. Điều này cho phép các giao dịch đang đợi khoá tiếp tục tiến hành và nhận khoá, do vậy, làm tăng hoạt động đồng thời. Gọi Oper(T,x) là lệnh truy xuất mục dữ liệu x trong giao tác T. - Dựa vào kỹ thuật khóa chốt hai giai đoạn, có thể chia giao tác thành hai giai đoạn, dựa trên 3 nguyên tắc trên: + Giai đoạn tăng trưởng (growing phase), trong giai đoạn này nó nhận các khoá và truy xuất các mục dữ liệu. Khi bộ lập lịch nhận được lệnh Oper(T,x), nó kiểm tra lệnh này có tranh chấp với những lệnh truy xuất trên x khác, đã được bộ lập lịch cấp khóa. ƒ Nếu nó tranh chấp, lệnh Oper(T,x) bị bị trì hoãn. ƒ Nếu không tranh chấp, bộ lập lịch sẽ cấp 1 khóa cho x và gửi lệnh này đến bộ quản lý dữ liệu. Bộ lập lịch sẽ không giải phóng khóa cho đến khi bộ quản lý dữ liệu đã thực hiện xong lệnh Oper(T,x). + Giai đoạn thu hồi (shrinking phase) là giai đoạn giải phóng những khoá của nó. Khi bộ lập lịch bắt đầu giải phóng bất kỳ khóa nào của giao tác T thì nó sẽ không cấp bất kỳ khóa nào cho T, cho dù các mục dữ diệu của T đòi hỏi khóa. Nếu T cứ đòi hỏi khóa khi tiến trình giải phóng khóa xảy ra thì chương trình phát sinh lỗi và giao tác sẽ gọi lệnh Abort. - Điểm khoá (lock point) là thời điểm giao dịch đã nhận được tất cả các khoá nhưng chưa bắt đầu giải phóng khoá nào. Vì thế điểm khoá xác định cuối giai đoạn tăng trưởng và đầu giai đoạn thu hồi của một giao tác. - [Eswaran et al., 1976] đã có định lý khẳng định rằng mọi lịch biểu tạo bởi một thuật toán điều khiển đồng thời tuân theo quy tắc 2PL đều khả tuần tự. d. Khoá chốt hai pha chặt chẽ (Strict two phase locking) - Một kỹ thuật khác được gọi là khóa chốt hai pha chặt chẽ. Kỹ thuật này cũng gồm 2 giai đoạn: Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 18/49 + Giai đoạn tăng trưởng: giống với giai đoạn đầu của kỹ thuật khóa 2 pha. + Giai đoạn thu hồi khóa: ƒ Tất cả các khóa được giải phóng cùng một lúc sau khi giao tác T kết thúc hoặc bị hủy bỏ. ƒ Không có thao tác đọc/ghi nào được thực hiện một khi khóa được giải phóng bởi giao tác. ƒ Nếu giao tác bị hủy bỏ thì việc phục hồi lại những thay đổi dữ liệu được thực hiện trước khi khóa được giải phóng. - Biểu đồ khóa 2 pha chặt chẽ. Tất cả các khóa được giải phóng cùng lúc e. Vấn đề bế tắc (deadlock) - Vấn đề bế tắc luôn xảy ra trong các kỹ thuật dùng cơ chế khóa chốt. - Giả sử có 2 giao tác T1 và T2 thực hiện các lệnh đọc ghi trên mục dữ liệu x và y như sau: T1: lock (x); lock(y); read (x); write (y); T2: lock (y); lock(x); read (y); write (x); T1 chiếm giữ khóa x và cố gắng khóa y, T2 chiếm giữ khóa y và cố gắng khóa x. Hiện tượng bế tắc sẽ xảy ra. - Để khắc phục tình trạng này: + Thiết lập thời gian timeout, nếu thời gian thực hiện giao tác vượt quá thời gian timeout thì hủy bỏ giao tác hoặc thực hiện thuật toán kiểm tra bế tắc. + Sắp xếp các mục dữ liệu và truy xuất chúng theo một thứ tự nhất định. + Giảm bớt việc đồng hành các giao tác. Nguyễn Nam Hải CH0403005 – Phan Nhựt Long CH0403009 – Phan Thanh Nam CH0403011 Khóa luận môn học CƠ SỞ DỮ LIỆU NÂNG CAO Trang 19/49 5. Thời nhãn: a. Khái niệm thời nhãn: ¾ Mỗi giao dịch được gán một danh biểu (mốc thời gian) duy nhất vào lúc bắt đầu. ¾ Cơ chế quản lý đồng hành theo thời nhãn không sử dụng bất kỳ khóa chốt nào. ¾ Có thể xảy ra đụng độ giống deadlock, ví dụ: giao dịch yêu cầu đọc một đối tượng đã bị cập nhật bởi một giao dịch trước đó, … ¾ Nếu phát sinh đụng độ, thì khởi động lại giao dịch. ¾ Việc khởi động lại một giao dịch chịu ít chi phí hơn so với việc thực hiện rollback. Gọi fmax là thời nhãn của giao tác cuối cùng đọc bộ R. Gọi umax là thời nhãn của giao tác cuối cùng cập nhật bộ R. Gọi T là thời nhãn của giao tác T. Cập nhật R. Nếu t là trễ hơn thời nhãn cho đọc (fmax) và trễ hơn thời nhãn cho cập nhật R (umax) thì chấp nhận T, ngược lại: khởi động lại T. Như vậy: các giao dịch bị loại khỏi thao tác cập nhật các bộ cho đến khi nó có thời nhãn trễ hơn bộ cần cập nhật. Do vậy nó không gây hại cho các giao dịch khác. Với mỗi giao dịch Ti trong hệ thống, chúng ta kết hợp với nó một nhãn thời gian cố định duy nhất được ký hiệu TS(Ti). Nhãn thời gian này được gán bởi hệ cơ sở dữ liệu trước khi giao dịch Ti được khởi động thực hiện. Nếu một giao dịch Ti đã được gán nhãn TS(Ti), một giao dịch mới Tj đi vào hệ thống thì TS(Ti) - Xem thêm -