Thuật toán khoá hai pha (hay Giao thức khóa hai pha,tiếng Anh Two-Phase Locking Algorithm, Two-Phase Locking Protocol) là thuật toán hai giai đoạn thực hiện cơ chế kiểm soát tính đồng thời trong cơ sở dữ liệu quan hệ nhằm đảm bảo tính nguyên tử của giao dịch và tính toàn vẹn dữ liệu của cơ sở dữ liệu theo cách sử dụng khóa để tuần tự hóa các thao tác cập nhật dữ liệu. Giao dịch thu nhận các khóa cần thiết trong pha phát triển (hay mở rộng hoặc khóa) và giải phóng các khóa trong pha thu hẹp (hoặc mở khóa) cho tới khi giao dịch được cam kết.
Thực hiện thuật toán khoá hai pha nhằm phân chia quyền sở hữu tài nguyên (mục dữ liệu) cho các giao dịch đồng thời với kỳ vọng là không tạo ra bế tắc.
Tính nguyên tử của một giao dịch phát biểu rằng, trong xử lý giao dịch, hoặc tất cả các thao tác được hoàn thành (giao dịch thành công) hoặc không một thao tác nào được hoàn thành (giao dịch thất bại). Bộ quản lý khóa thực hiện thuật toán khoá hai pha nhằm đảm bảo tính nguyên tử của giao dịch trong tình huống các giao dịch được thực hiện đồng thời. Khi đó, giao dịch không chỉ chứa các thao tác thực thi cần thiết mà còn chứa các thao tác thu nhận khóa (khóa mục dữ liệu) và giải phóng khóa (mở khóa mục dữ liệu). Có hai kiểu khóa mục dữ liệu là khóa đọc đồng thời và khóa ghi độc quyền. Khóa đọc đồng thời ngăn bất kỳ thao tác ghi mục dữ liệu song cho phép các thao tác đọc mục dữ liệu, trong khi đó, khóa ghi độc quyền ngăn cả hai thao tác đọc và ghi mục dữ liệu. Các thao tác khóa mục dữ liệu và mở khóa mục dữ liệu cho phép hệ thống cơ sở dữ liệu kiểm soát được thứ tự các hoạt động đọc và ghi lên mục dữ liệu.
Hình 1 minh họa hoạt động của thuật toán khoá hai pha đối với một giao dịch. Như thể hiện ở Hình 1, theo dòng thời gian, diễn ra pha tăng trưởng, pha bị khóa và pha thu hẹp của giao dịch; lưu ý rằng, từ “hai pha” trong tên gọi thuật toán chỉ định rằng pha bị khóa và pha thu hẹp được ghép thành “pha thu hẹp”. Giao dịch này bao gồm các thao tác thực thi cần thiết (bắt đầu giao dịch, cập nhật dữ liệu và kết thúc giao dịch) và các thao tác nhận khóa (tại pha tăng trưởng) và các thao tác giải phóng khóa (tại pha thu hẹp). Pha tăng trưởng thường được Bộ quản lý khóa tiến hành theo một vòng lặp, ở mỗi vòng lặp, tất cả các khóa cần thiết cho giao dịch cần được thu nhận (Bộ quản lý khóa cấp); nếu thu nhận được mọi khóa thì kết thúc pha tăng trưởng, nếu chỉ một khóa không thu nhận được thì vòng lặp lại được bắt đầu với toàn bộ các khóa cần thiết. Pha bị khóa thực thi các thao tác cập nhật dữ liệu của giao dịch; lưu ý rằng việc thay đổi trạng thái (nếu có) của các mục dữ liệu chỉ được thi hành tại không gian bộ nhớ dành riêng của giao dịch và chỉ được cập nhật thực sự vào cơ sở dữ liệu ngay khi giao dịch được cam kết. Pha thu hẹp thực thi các thao tác giải phóng mọi khóa đã được thu nhận.
Bộ quản lý khóa thực hiện thuật toán khoá hai pha theo ba quy tắc dẫn dắt: (i) hai giao dịch không thể xung đột khóa, (ii) trong cùng một giao dịch, không một thao tác mở khóa nào được đi trước một thao tác khóa, (iii) không một dữ liệu nào bị giao dịch tác động cho đến khi mọi khóa đã được thu nhận (giao dịch ở điểm khóa).
Hình 2 minh họa một ví dụ hoạt động của thuật toán khoá hai pha lên các giao dịch đồng thời. Hai người sử dụng Bắc và Nam (gọi thay các giao dịch của họ) đều có được khóa đọc đồng thời (gọi tắt là khóa đọc) lên một cơ sở dữ liệu post theo câu lệnh PostgreSQL SELECT … FOR SHARE. Cả Bắc và Nam đều nhận được nội dung trường “title” của bản ghi này là “Transactions”.
Sau đó, Nam không thể thực hiện được câu lệnh UPDATE thay nội dung “ACID” vào trường “title” của bản ghi có id=1 của post vì câu lệnh UPDATE cần có khóa ghi độc quyền (gọi tắt là khóa ghi) nhưng do Bắc vẫn đang giữ khóa đọc lên post nên Bộ quản lý khóa chặn việc cấp khóa ghi cho Nam.
Chỉ sau khi giao dịch của Bắc kết thúc và giải phóng mọi khóa của Bắc thì Nam mới có thể tiếp tục câu lệnh UPDATE của mình. Câu lệnh UPDATE của Nam nâng cấp khóa từ khóa đọc thành khóa ghi lên chính post và việc nâng cấp đó ngăn các giao dịch khác có được khóa đọc hoặc khóa ghi lên post.
Bắc lại bắt đầu một giao dịch mới, đưa ra câu lệnh SELECT FOR SHARE với yêu cầu thu nhận lại khóa đọc lên post, nhưng câu lệnh này bị Bộ quản lý khóa chặn vì Nam đang sở hữu khóa ghi lên post.
Sau khi giao dịch của Nam được thực hiện, việc thay “Transactions”thành“ACID” hoàn thành, mọi khóa của Nam được giải phóng. Sau đó, truy vấn SELECT FOR SHARE của Bắc được tiếp tục nhận khóa đọc để thực hiện và nhận được giá trị “ACID” của trường “title” trong bản ghi có id=1.
K. P. Eswaran và cộng sự là những người đầu tiên mô tả khóa hai pha, đề xuất giải pháp chia sẻ khóa theo thứ tự và cho phép nhiều hơn một giao dịch giữ khóa đối với một mục dữ liệu miễn là các hành động được thực hiện theo cùng thứ tự với các khóa đã được thu nhận. Sau đó, chính sách cơ bản chia sẻ khóa theo khóa hai pha được mở rộng theo nhiều hướng. Trong chính sách cấp khóa vị tha (altruistic locking), một giao dịch có thể cho phép các giao dịch khác truy cập vào các mục dữ liệu đang bị khóa bởi nó nếu như giao dịch này không truy cập lại các mục dữ liệu này sau đó. Giao thức khóa hai pha theo chính sách khóa vị tha được sử dụng đối với các tình huống đang chạy đồng thời các giao dịch dài và ngắn. Ngoài ra còn có một số phiên bản khóa hai pha khác nữa.
Hệ thống xử lý giao dịch là phổ biến trong các tổ chức và giao dịch trong có độ dài ngắn là trong các hệ thống xử lý giao dịch như vậy. Mặt khác, các ứng dụng xử lý giao dịch trực tuyến (online transaction processing: OLTP) đòi hỏi các giải pháp xử lý giao dịch tin cậy và hiệu quả, vì vậy, thuật toán khoá hai pha đã trở thành chuẩn thực tế trong các hệ thống cơ sở dữ liệu dùng cho xử lý giao dịch trực tuyến.
Ở Việt Nam, thuật toán khoá hai pha có một số lượng người quan tâm hạn chế vì nó là một nội dung chuyên sâu gắn với một số chủ đề như điều khiển đồng thời, giải quyết tương tranh, hệ thống phân tán, v.v.
Chiến lược thu thập khóa ở pha tăng cường của giao dịch có thể là một vấn đề vì không có gì đảm bảo là giao dịch thu thập được các khóa đối với các mục dữ liệu cần thiết trong một thời gian hữu hạn. Vì vậy, giao thức khóa hai pha không được sử dụng trong các ứng dụng thời gian thực cứng.
Cơ chế chặn cấp khóa cho các giao dịch (chặn các giao dịch) có thế gây tác động nghiêm trọng tới thông lượng hệ thống.
Cần phân biệt thuật toán khoá hai pha (2PL) với thuật toán cam kết hai pha Two-phase commit (2PC). Thuật toán 2PC trong hệ thống phân tán là một giao thức đồng thuận nhằm mục tiêu cam kết hay hủy bỏ một giao dịch phân tán.
Tài liệu tham khảo[sửa]
- P. A. Bernstein and N. Goodman. Concurrency Control in Distributed Database Systems. Computing Surveys, 13 (2): 185-221, 1981.
- Wojciech Cellary, Erol Gelenbe, Tadeusz Morzy. Concurrency control in distributed database systems. Elsevier Science, 1989.
- Carlos M. Coronel. Database Systems: Design, Implementation, & Management. Cengage Learning, 2018.
- Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger. The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19 (11) 624-633, 1976.
- Georg Lausen. Two-Phase Locking. In (Ling Liu, M. Tamer Özsu. Encyclopedia of Database Systems (2nd edition). Springer, 2018), pp.4270-4275.
- Vlad Mihalcea. How does the 2PL (Two-Phase Locking) algorithm work. Last modified: Feb 7, 2020. https://vladmihalcea.com/2pl-two-phase-locking/
_trong_thu%E1%BA%ADt_to%C3%A1n_kho%C3%A1_hai_pha.png){kind=link}
