Các Giao thức Kiểm soát Đồng thời

Các giao thức kiểm soát đồng thời là các phương pháp — khóa, sắp xếp theo dấu thời gian, xác thực lạc quan và đa phiên bản — nhằm lên lịch các giao dịch đồng thời sao cho kết quả tương đương với một thực thi tuần tự.

Definition

Giao thức kiểm soát đồng thời là một tập hợp các quy tắc điều chỉnh cách các giao dịch đồng thời truy cập dữ liệu sao cho mọi lịch trình được phép đều có thể tuần tự hóa (hoặc thỏa mãn một mức độ cô lập yếu hơn được chọn), từ đó duy trì sự cô lập mà không buộc các giao dịch phải chạy từng cái một.

Scope

Chủ đề này bao gồm các giao thức đảm bảo tính tuần tự trong môi trường đồng thời: khóa hai pha và biến thể nghiêm ngặt của nó, với phát hiện và ngăn chặn tắc nghẽn; các giao thức sắp xếp theo dấu thời gian; kiểm soát đồng thời lạc quan với các pha đọc-xác thực-ghi; và kiểm soát đồng thời đa phiên bản, bao gồm cô lập ảnh chụp nhanh. Nó đề cập đến cách mỗi giao thức đảm bảo các lịch trình chính xác và sự đánh đổi giữa việc chặn, hủy bỏ và thông lượng. Nó không bao gồm định nghĩa về tính tuần tự và các cơ chế phục hồi bổ sung cho kiểm soát đồng thời.

Core questions

• Khóa hai pha đảm bảo các lịch trình có thể tuần tự hóa như thế nào?
• Tắc nghẽn được phát hiện, ngăn chặn hoặc giải quyết như thế nào?
• Các giao thức sắp xếp theo dấu thời gian và lạc quan khác với khóa như thế nào?
• Kiểm soát đồng thời đa phiên bản cho phép người đọc tránh chặn người ghi như thế nào?
• Những đánh đổi về thông lượng giữa các phương pháp bi quan và lạc quan là gì?

Key concepts

• khóa hai pha
• 2PL nghiêm ngặt và chặt chẽ
• khóa chia sẻ và độc quyền
• phát hiện và ngăn chặn tắc nghẽn
• sắp xếp theo dấu thời gian
• kiểm soát đồng thời lạc quan
• kiểm soát đồng thời đa phiên bản
• cô lập ảnh chụp nhanh

Key theories

Khóa hai pha

Nếu mọi giao dịch đều có được tất cả các khóa của nó trước khi giải phóng bất kỳ khóa nào (một pha tăng trưởng tiếp theo là một pha thu hẹp), tất cả các lịch trình kết quả đều có thể tuần tự hóa xung đột; khóa hai pha nghiêm ngặt bổ sung giữ các khóa ghi cho đến khi cam kết để đảm bảo khả năng phục hồi.

Kiểm soát đồng thời lạc quan

Các giao dịch thực thi mà không cần khóa và được xác thực tại thời điểm cam kết đối với các giao dịch đồng thời; các giao dịch xung đột bị hủy bỏ và thử lại, hoạt động tốt khi tranh chấp thấp.

Kiểm soát đồng thời đa phiên bản

Bằng cách giữ nhiều phiên bản của mỗi mục dữ liệu, hệ thống cho phép đọc truy cập một ảnh chụp nhanh nhất quán mà không chặn các thao tác ghi; cô lập ảnh chụp nhanh là một lược đồ đa phiên bản được sử dụng rộng rãi, mặc dù nó có thể cho phép một số bất thường không thể tuần tự hóa.

Clinical relevance

Các giao thức kiểm soát đồng thời xác định cách một cơ sở dữ liệu hoạt động dưới tải: khóa là mạnh mẽ nhưng có thể gây ra tắc nghẽn và tranh chấp, các phương pháp lạc quan và đa phiên bản cho phép đồng thời đọc cao, và việc lựa chọn giao thức trực tiếp định hình thông lượng và độ trễ của các hệ thống giao dịch có lưu lượng truy cập cao.

History

Khóa hai pha và khóa vị từ đã được Eswaran và các đồng nghiệp tại System R chính thức hóa vào năm 1976; Kung và Robinson đã giới thiệu kiểm soát đồng thời lạc quan vào năm 1981; và chuyên khảo năm 1987 của Bernstein, Hadzilacos và Goodman đã thống nhất lý thuyết. Các phương pháp đa phiên bản và cô lập ảnh chụp nhanh sau đó trở nên phổ biến trong các hệ thống cơ sở dữ liệu được sử dụng rộng rãi nhờ hành vi thân thiện với việc đọc của chúng.

Debates

Cô lập ảnh chụp nhanh so với tính tuần tự

Cô lập ảnh chụp nhanh mang lại tính đồng thời cao bằng cách cho phép người đọc xem một ảnh chụp nhanh nhất quán, nhưng nó cho phép các bất thường như độ lệch ghi mà tính tuần tự đầy đủ cấm; các nhà thực hành tranh luận khi nào đảm bảo yếu hơn của nó là chấp nhận được và khi nào các biến thể có thể tuần tự hóa là cần thiết.

Key figures

• Jim Gray
• Philip Bernstein
• H. T. Kung

Seminal works

• eswaran1976
• kung1981
• bernstein1987

Frequently asked questions

Điều gì gây ra tắc nghẽn và nó được xử lý như thế nào?

Tắc nghẽn xảy ra khi hai hoặc nhiều giao dịch mỗi giao dịch giữ một khóa mà giao dịch kia cần, do đó không giao dịch nào có thể tiếp tục. Các hệ thống xử lý nó bằng cách phát hiện — xây dựng biểu đồ chờ đợi, tìm một chu trình và hủy bỏ một giao dịch nạn nhân — hoặc bằng các lược đồ ngăn chặn sắp xếp việc thu thập khóa hoặc sử dụng dấu thời gian để quyết định giao dịch nào chờ đợi so với hủy bỏ.

Khi nào kiểm soát đồng thời lạc quan là một lựa chọn tốt?

Các phương pháp lạc quan phát huy tác dụng khi xung đột hiếm khi xảy ra, bởi vì các giao dịch chạy mà không có chi phí khóa và chỉ thỉnh thoảng thất bại trong việc xác thực và thử lại. Trong điều kiện tranh chấp cao, chúng lãng phí công việc vào việc hủy bỏ và thử lại, vì vậy khóa bi quan hoặc các phương pháp đa phiên bản thường được ưu tiên cho các khối lượng công việc nặng về ghi, dễ xảy ra xung đột.