DBMS phân tán - Xử lý bế tắc

Chương này giới thiệu tổng quan về các cơ chế xử lý deadlock trong hệ cơ sở dữ liệu. Chúng tôi sẽ nghiên cứu các cơ chế xử lý bế tắc trong cả hệ thống cơ sở dữ liệu tập trung và phân tán.

Deadlocks là gì?

Deadlock là trạng thái của một hệ thống cơ sở dữ liệu có từ hai giao dịch trở lên, khi mỗi giao dịch đang chờ một mục dữ liệu đang bị khóa bởi một giao dịch khác. Bế tắc có thể được biểu thị bằng một chu kỳ trong biểu đồ chờ đợi. Đây là một đồ thị có hướng, trong đó các đỉnh biểu thị các giao dịch và các cạnh biểu thị chờ các mục dữ liệu.

Ví dụ, trong biểu đồ chờ đợi sau, giao dịch T1 đang đợi mục dữ liệu X bị khóa bởi T3. T3 đang chờ Y bị T2 khóa và T2 đang chờ Z bị T1 khóa. Do đó, một chu kỳ chờ được hình thành và không có giao dịch nào có thể tiến hành thực hiện.

Xử lý bế tắc trong các hệ thống tập trung

Có ba cách tiếp cận cổ điển để xử lý bế tắc, đó là -

Phòng ngừa bế tắc.
Tránh bế tắc.
Phát hiện và loại bỏ bế tắc.

Tất cả ba cách tiếp cận có thể được kết hợp trong cả hệ thống cơ sở dữ liệu tập trung và phân tán.

Ngăn chặn bế tắc

Phương pháp phòng ngừa bế tắc không cho phép bất kỳ giao dịch nào có được các khóa sẽ dẫn đến bế tắc. Quy ước là khi có nhiều giao dịch yêu cầu khóa cùng một mục dữ liệu, thì chỉ một trong số chúng được cấp khóa.

Một trong những phương pháp ngăn chặn bế tắc phổ biến nhất là mua trước tất cả các ổ khóa. Trong phương pháp này, một giao dịch có được tất cả các khóa trước khi bắt đầu thực hiện và giữ lại các khóa trong toàn bộ thời gian giao dịch. Nếu một giao dịch khác cần bất kỳ khóa nào đã có được, nó phải đợi cho đến khi tất cả các khóa mà nó cần có sẵn. Sử dụng cách tiếp cận này, hệ thống không bị bế tắc vì không có giao dịch đang chờ nào bị khóa.

Tránh bế tắc

Phương pháp tránh bế tắc xử lý các bế tắc trước khi chúng xảy ra. Nó phân tích các giao dịch và các khóa để xác định xem liệu việc chờ đợi có dẫn đến bế tắc hay không.

Phương pháp có thể được phát biểu ngắn gọn như sau. Các giao dịch bắt đầu thực hiện và yêu cầu các mục dữ liệu mà chúng cần khóa. Người quản lý khóa kiểm tra xem khóa có sẵn không. Nếu nó có sẵn, người quản lý khóa sẽ phân bổ mục dữ liệu và giao dịch mua lại khóa. Tuy nhiên, nếu mục bị khóa bởi một số giao dịch khác ở chế độ không tương thích, trình quản lý khóa sẽ chạy một thuật toán để kiểm tra xem việc giữ giao dịch ở trạng thái chờ có gây ra bế tắc hay không. Theo đó, thuật toán quyết định liệu giao dịch có thể chờ hay một trong các giao dịch nên bị hủy bỏ.

Có hai thuật toán cho mục đích này, đó là wait-die và wound-wait. Giả sử rằng có hai giao dịch, T1 và T2, trong đó T1 cố gắng khóa một mục dữ liệu đã bị khóa bởi T2. Các thuật toán như sau:

Wait-Die- Nếu T1 lớn hơn T2 thì T1 được phép chờ. Ngược lại, nếu T1 nhỏ hơn T2, T1 bị hủy bỏ và sau đó được khởi động lại.
Wound-Wait- Nếu T1 cũ hơn T2, T2 bị hủy bỏ và sau đó được khởi động lại. Ngược lại, nếu T1 nhỏ hơn T2 thì T1 được phép chờ.

Phát hiện và loại bỏ bế tắc

Phương pháp phát hiện và loại bỏ deadlock chạy một thuật toán phát hiện deadlock theo định kỳ và loại bỏ deadlock trong trường hợp có. Nó không kiểm tra bế tắc khi giao dịch đặt yêu cầu khóa. Khi một giao dịch yêu cầu khóa, người quản lý khóa sẽ kiểm tra xem nó có khả dụng hay không. Nếu nó có sẵn, giao dịch được phép khóa mục dữ liệu; nếu không thì giao dịch được phép chờ.

Vì không có biện pháp phòng ngừa trong khi cấp yêu cầu khóa, một số giao dịch có thể bị bế tắc. Để phát hiện các bế tắc, trình quản lý khóa định kỳ kiểm tra xem biểu đồ chờ có chu kỳ hay không. Nếu hệ thống bị khóa, trình quản lý khóa sẽ chọn một giao dịch nạn nhân từ mỗi chu kỳ. Nạn nhân bị phá thai và cuộn lại; và sau đó khởi động lại sau đó. Một số phương pháp được sử dụng để lựa chọn nạn nhân là:

Chọn giao dịch trẻ nhất.
Chọn giao dịch có ít mục dữ liệu nhất.
Chọn giao dịch đã thực hiện ít cập nhật nhất.
Chọn giao dịch có chi phí khởi động lại ít nhất.
Chọn giao dịch phổ biến cho hai hoặc nhiều chu kỳ.

Cách tiếp cận này chủ yếu phù hợp với các hệ thống có giao dịch thấp và cần phản hồi nhanh với các yêu cầu khóa.

Xử lý bế tắc trong các hệ thống phân tán

Xử lý giao dịch trong hệ thống cơ sở dữ liệu phân tán cũng được phân tán, tức là cùng một giao dịch có thể được xử lý tại nhiều hơn một trang web. Hai mối quan tâm chính về xử lý bế tắc trong hệ thống cơ sở dữ liệu phân tán không có trong hệ thống tập trung làtransaction location và transaction control. Một khi những mối quan tâm này được giải quyết, các bế tắc được xử lý thông qua bất kỳ biện pháp ngăn chặn bế tắc nào, tránh bế tắc hoặc phát hiện và loại bỏ bế tắc.

Địa điểm giao dịch

Các giao dịch trong hệ thống cơ sở dữ liệu phân tán được xử lý trên nhiều trang và sử dụng các mục dữ liệu trong nhiều trang. Số lượng xử lý dữ liệu không được phân phối đồng nhất giữa các trang web này. Khoảng thời gian xử lý cũng khác nhau. Do đó, cùng một giao dịch có thể đang hoạt động ở một số trang web và không hoạt động ở những trang khác. Khi hai giao dịch xung đột được đặt trong một trang web, có thể xảy ra trường hợp một trong số chúng ở trạng thái không hoạt động. Điều kiện này không phát sinh trong một hệ thống tập trung. Mối quan tâm này được gọi là vấn đề địa điểm giao dịch.

Mối quan tâm này có thể được giải quyết bằng mô hình Daisy Chain. Trong mô hình này, một giao dịch mang một số chi tiết nhất định khi nó di chuyển từ trang này sang trang khác. Một số chi tiết là danh sách các bảng được yêu cầu, danh sách các trang web được yêu cầu, danh sách các bảng và các trang web đã truy cập, danh sách các bảng và các trang web chưa được truy cập và danh sách các ổ khóa có được với các loại. Sau khi giao dịch kết thúc bằng cam kết hoặc hủy bỏ, thông tin sẽ được gửi đến tất cả các trang web liên quan.

Kiểm soát giao dịch

Kiểm soát giao dịch liên quan đến việc chỉ định và kiểm soát các trang web cần thiết để xử lý một giao dịch trong hệ thống cơ sở dữ liệu phân tán. Có nhiều lựa chọn liên quan đến việc lựa chọn nơi xử lý giao dịch và cách chỉ định trung tâm kiểm soát, như -

Một máy chủ có thể được chọn làm trung tâm điều khiển.
Trung tâm điều khiển có thể đi từ máy chủ này sang máy chủ khác.
Một số máy chủ có thể chia sẻ trách nhiệm kiểm soát.

Ngăn chặn bế tắc phân tán

Cũng giống như trong ngăn chặn bế tắc tập trung, trong cách tiếp cận ngăn chặn bế tắc phân tán, một giao dịch phải có được tất cả các khóa trước khi bắt đầu thực hiện. Điều này ngăn chặn bế tắc.

Trang web nơi giao dịch đi vào được chỉ định là trang web kiểm soát. Trang web kiểm soát sẽ gửi thông báo đến các trang web có các mục dữ liệu để khóa các mục. Sau đó, nó chờ xác nhận. Khi tất cả các trang web đã xác nhận rằng họ đã khóa các mục dữ liệu, giao dịch sẽ bắt đầu. Nếu bất kỳ trang web hoặc liên kết giao tiếp nào bị lỗi, giao dịch phải đợi cho đến khi chúng được sửa chữa.

Mặc dù cách thực hiện đơn giản, nhưng phương pháp này có một số nhược điểm -

Việc mua trước các ổ khóa đòi hỏi một thời gian dài vì sự chậm trễ liên lạc. Điều này làm tăng thời gian cần thiết cho giao dịch.
Trong trường hợp trang web hoặc liên kết bị lỗi, giao dịch phải đợi một thời gian dài để các trang web phục hồi. Trong khi đó, ở các trang đang chạy, các vật phẩm bị khóa. Điều này có thể ngăn không cho các giao dịch khác thực hiện.
Nếu trang web kiểm soát không thành công, nó không thể giao tiếp với các trang web khác. Các trang web này tiếp tục giữ các mục dữ liệu bị khóa ở trạng thái khóa của chúng, do đó dẫn đến việc bị chặn.

Tránh bế tắc phân tán

Cũng như trong hệ thống tập trung, tính năng tránh deadlock phân tán xử lý deadlock trước khi xảy ra. Ngoài ra, trong các hệ thống phân tán, các vấn đề về vị trí giao dịch và kiểm soát giao dịch cần được giải quyết. Do tính chất phân tán của giao dịch, các xung đột sau có thể xảy ra:

Xung đột giữa hai giao dịch trong cùng một trang web.
Xung đột giữa hai giao dịch trong các trang web khác nhau.

Trong trường hợp xung đột, một trong các giao dịch có thể bị hủy bỏ hoặc được phép chờ theo thuật toán chờ đợi phân tán hoặc chờ đợi phân tán.

Giả sử rằng có hai giao dịch, T1 và T2. T1 đến địa điểm P và cố gắng khóa một mục dữ liệu đã bị T2 khóa tại địa điểm đó. Do đó, có một xung đột tại Trang P. Các thuật toán như sau:

Distributed Wound-Die
- Nếu T1 lớn hơn T2 thì T1 được phép chờ. T1 có thể tiếp tục thực hiện sau khi Trang P nhận được thông báo rằng T2 đã cam kết hoặc hủy bỏ thành công ở tất cả các trang.
- Nếu T1 nhỏ hơn T2 thì T1 bị hủy. Kiểm soát đồng thời tại Địa điểm P sẽ gửi một thông báo đến tất cả các địa điểm mà T1 đã truy cập để hủy bỏ T1. Trang web kiểm soát thông báo cho người dùng khi T1 đã được hủy bỏ thành công trong tất cả các trang web.
Distributed Wait-Wait
- Nếu T1 lớn hơn T2 thì T2 cần được hủy bỏ. Nếu T2 đang hoạt động tại Trang P, Trang P sẽ hủy bỏ và quay trở lại T2, sau đó phát thông báo này đến các trang có liên quan khác. Nếu T2 đã rời khỏi Địa điểm P nhưng đang hoạt động tại Địa điểm Q, thì Địa điểm P sẽ phát sóng mà T2 đã bị hủy bỏ; Site L sau đó hủy bỏ và quay trở lại T2 và gửi thông báo này đến tất cả các site.
- Nếu T1 nhỏ hơn T1 thì T1 được phép chờ. T1 có thể tiếp tục thực thi sau khi Trang P nhận được thông báo rằng T2 đã hoàn tất quá trình xử lý.

Phát hiện bế tắc phân tán

Cũng giống như phương pháp phát hiện deadlock tập trung, các deadlock được phép xảy ra và được gỡ bỏ nếu được phát hiện. Hệ thống không thực hiện bất kỳ kiểm tra nào khi một giao dịch đưa ra yêu cầu khóa. Để triển khai, đồ thị chờ toàn cục sẽ được tạo. Sự tồn tại của một chu kỳ trong biểu đồ chờ toàn cục cho thấy những bế tắc. Tuy nhiên, rất khó để phát hiện ra các bế tắc vì giao dịch chờ tài nguyên trên toàn mạng.

Ngoài ra, các thuật toán phát hiện bế tắc có thể sử dụng bộ định thời. Mỗi giao dịch được liên kết với một bộ đếm thời gian được đặt thành một khoảng thời gian mà một giao dịch dự kiến sẽ kết thúc. Nếu một giao dịch không kết thúc trong khoảng thời gian này, bộ đếm thời gian sẽ tắt, cho biết có thể xảy ra bế tắc.

Một công cụ khác được sử dụng để xử lý bế tắc là một bộ phát hiện bế tắc. Trong một hệ thống tập trung, có một bộ phát hiện bế tắc. Trong một hệ thống phân tán, có thể có nhiều hơn một bộ phát hiện khóa chết. Một bộ phát hiện bế tắc có thể tìm ra các điểm bế tắc cho các trang web dưới sự kiểm soát của nó. Có ba lựa chọn thay thế để phát hiện bế tắc trong một hệ thống phân tán, cụ thể là.

Centralized Deadlock Detector - Một vị trí được chỉ định là bộ phát hiện bế tắc trung tâm.
Hierarchical Deadlock Detector - Một số bộ phát hiện khóa chết được sắp xếp theo thứ bậc.
Distributed Deadlock Detector - Tất cả các trang web tham gia phát hiện các bế tắc và loại bỏ chúng.