DBMS phân tán - Kiểm soát đồng thời
Các kỹ thuật kiểm soát đồng thời đảm bảo rằng nhiều giao dịch được thực hiện đồng thời trong khi vẫn duy trì các thuộc tính ACID của các giao dịch và khả năng tuần tự hóa trong lịch trình.
Trong chương này, chúng ta sẽ nghiên cứu các cách tiếp cận khác nhau để điều khiển đồng thời.
Khóa giao thức điều khiển đồng thời dựa trên khóa
Các giao thức điều khiển đồng thời dựa trên khóa sử dụng khái niệm khóa các mục dữ liệu. Alocklà một biến được liên kết với một mục dữ liệu xác định xem có thể thực hiện các thao tác đọc / ghi trên mục dữ liệu đó hay không. Nói chung, một ma trận tương thích khóa được sử dụng để cho biết liệu một mục dữ liệu có thể bị khóa bởi hai giao dịch cùng một lúc hay không.
Hệ thống điều khiển đồng thời dựa trên khóa có thể sử dụng giao thức khóa một pha hoặc hai pha.
Giao thức khóa một pha
Trong phương pháp này, mỗi giao dịch sẽ khóa một vật phẩm trước khi sử dụng và mở khóa ngay sau khi sử dụng xong. Phương pháp khóa này cung cấp sự đồng thời tối đa nhưng không phải lúc nào cũng thực thi khả năng tuần tự hóa.
Giao thức khóa hai pha
Trong phương pháp này, tất cả các thao tác khóa trước thao tác mở khóa hoặc mở khóa đầu tiên. Giao dịch bao gồm hai giai đoạn. Trong giai đoạn đầu, một giao dịch chỉ có được tất cả các khóa mà nó cần và không phát hành bất kỳ khóa nào. Điều này được gọi là mở rộng hoặcgrowing phase. Trong giai đoạn thứ hai, giao dịch giải phóng khóa và không thể yêu cầu bất kỳ khóa mới nào. Đây được gọi làshrinking phase.
Mọi giao dịch tuân theo giao thức khóa hai pha được đảm bảo có thể tuần tự hóa. Tuy nhiên, cách tiếp cận này cung cấp tính song song thấp giữa hai giao dịch xung đột.
Các thuật toán kiểm soát đồng thời dấu thời gian
Các thuật toán kiểm soát đồng thời dựa trên dấu thời gian sử dụng dấu thời gian của giao dịch để điều phối quyền truy cập đồng thời vào một mục dữ liệu nhằm đảm bảo khả năng tuần tự hóa. Dấu thời gian là một số nhận dạng duy nhất do DBMS cấp cho một giao dịch đại diện cho thời gian bắt đầu của giao dịch.
Các thuật toán này đảm bảo rằng các giao dịch cam kết theo thứ tự được quy định bởi dấu thời gian của chúng. Giao dịch cũ hơn nên cam kết trước giao dịch trẻ hơn, vì giao dịch cũ hơn vào hệ thống trước giao dịch trẻ hơn.
Các kỹ thuật kiểm soát đồng thời dựa trên dấu thời gian tạo ra các lịch trình có thể tuần tự hóa sao cho lịch trình nối tiếp tương đương được sắp xếp theo thứ tự tuổi của các giao dịch tham gia.
Một số thuật toán điều khiển đồng thời dựa trên dấu thời gian là:
- Thuật toán sắp xếp dấu thời gian cơ bản.
- Thuật toán sắp xếp dấu thời gian bảo thủ.
- Thuật toán đa vũ trụ dựa trên thứ tự dấu thời gian.
Thứ tự dựa trên dấu thời gian tuân theo ba quy tắc để thực thi khả năng tuần tự hóa -
Access Rule- Khi hai giao dịch cố gắng truy cập đồng thời vào cùng một mục dữ liệu, đối với các hoạt động xung đột, giao dịch cũ hơn sẽ được ưu tiên. Điều này khiến giao dịch trẻ hơn phải đợi giao dịch cũ hơn để cam kết trước.
Late Transaction Rule- Nếu một giao dịch trẻ hơn đã ghi một mục dữ liệu, thì một giao dịch cũ hơn không được phép đọc hoặc ghi mục dữ liệu đó. Quy tắc này ngăn giao dịch cũ hơn cam kết sau khi giao dịch trẻ hơn đã được cam kết.
Younger Transaction Rule - Một giao dịch trẻ hơn có thể đọc hoặc ghi một mục dữ liệu đã được ghi bởi một giao dịch cũ hơn.
Thuật toán điều khiển đồng thời lạc quan
Trong các hệ thống có tỷ lệ xung đột thấp, nhiệm vụ xác thực mọi giao dịch về khả năng tuần tự hóa có thể làm giảm hiệu suất. Trong những trường hợp này, việc kiểm tra khả năng tuần tự hóa bị hoãn lại ngay trước khi cam kết. Vì tỷ lệ xung đột thấp nên xác suất hủy bỏ các giao dịch không thể tuần tự hóa cũng thấp. Cách tiếp cận này được gọi là kỹ thuật điều khiển đồng thời lạc quan.
Theo cách tiếp cận này, vòng đời của giao dịch được chia thành ba giai đoạn sau:
Execution Phase - Một giao dịch tìm nạp các mục dữ liệu vào bộ nhớ và thực hiện các hoạt động trên chúng.
Validation Phase - Một giao dịch thực hiện kiểm tra để đảm bảo rằng việc cam kết các thay đổi của nó đối với cơ sở dữ liệu sẽ vượt qua kiểm tra khả năng tuần tự hóa.
Commit Phase - Một giao dịch ghi lại mục dữ liệu đã sửa đổi trong bộ nhớ vào đĩa.
Thuật toán này sử dụng ba quy tắc để thực thi khả năng tuần tự hóa trong giai đoạn xác thực -
Rule 1- Cho hai giao dịch T i và T j , nếu T i đang đọc mục dữ liệu mà T j đang ghi, thì pha thực hiện của T i không được trùng lặp với pha cam kết của T j . T j chỉ có thể cam kết sau khi T i thực hiện xong.
Rule 2- Cho hai giao dịch T i và T j , nếu T i đang ghi mục dữ liệu mà T j đang đọc, thì pha cam kết của T i ’s không được trùng lặp với pha thực hiện của T j ’. T j chỉ có thể bắt đầu thực hiện sau khi T i đã cam kết.
Rule 3- Cho hai giao dịch T i và T j , nếu T i đang ghi mục dữ liệu mà T j cũng đang ghi, thì pha cam kết của T i ’s không được trùng lặp với pha cam kết của T j . T j chỉ có thể bắt đầu cam kết sau khi T tôi đã cam kết.
Kiểm soát đồng thời trong các hệ thống phân tán
Trong phần này, chúng ta sẽ xem các kỹ thuật trên được thực hiện như thế nào trong hệ thống cơ sở dữ liệu phân tán.
Thuật toán khóa hai pha phân tán
Nguyên tắc cơ bản của khóa hai pha phân tán cũng giống như giao thức khóa hai pha cơ bản. Tuy nhiên, trong một hệ thống phân tán có các trang web được chỉ định làm trình quản lý khóa. Trình quản lý khóa kiểm soát các yêu cầu mua khóa từ các trình giám sát giao dịch. Để thực thi sự phối hợp giữa những người quản lý khóa trong các trang web khác nhau, ít nhất một trang web được cấp quyền xem tất cả các giao dịch và phát hiện xung đột khóa.
Tùy thuộc vào số lượng trang web có thể phát hiện xung đột khóa, các phương pháp khóa hai pha phân tán có thể có ba loại:
Centralized two-phase locking- Trong cách tiếp cận này, một trang web được chỉ định làm trình quản lý khóa trung tâm. Tất cả các trang web trong môi trường đều biết vị trí của trình quản lý khóa trung tâm và nhận được khóa từ đó trong các giao dịch.
Primary copy two-phase locking- Theo cách tiếp cận này, một số địa điểm được chỉ định làm trung tâm điều khiển khóa. Mỗi trang web này có trách nhiệm quản lý một tập hợp các khóa xác định. Tất cả các trang web đều biết trung tâm kiểm soát khóa nào chịu trách nhiệm quản lý khóa của bảng dữ liệu / mục phân mảnh nào.
Distributed two-phase locking- Trong cách tiếp cận này, có một số trình quản lý khóa, trong đó mỗi trình quản lý khóa sẽ kiểm soát các khóa của các mục dữ liệu được lưu trữ tại trang cục bộ của nó. Vị trí của trình quản lý khóa dựa trên việc phân phối và nhân rộng dữ liệu.
Kiểm soát đồng thời dấu thời gian phân tán
Trong một hệ thống tập trung, dấu thời gian của bất kỳ giao dịch nào được xác định bằng cách đọc đồng hồ vật lý. Tuy nhiên, trong hệ thống phân tán, số đọc đồng hồ logic / vật lý cục bộ của bất kỳ trang web nào không thể được sử dụng làm dấu thời gian toàn cầu, vì chúng không phải là duy nhất trên toàn cầu. Vì vậy, dấu thời gian bao gồm sự kết hợp của ID trang web và việc đọc đồng hồ của trang web đó.
Để triển khai các thuật toán sắp xếp dấu thời gian, mỗi trang web có một bộ lập lịch để duy trì một hàng đợi riêng cho mỗi người quản lý giao dịch. Trong quá trình giao dịch, người quản lý giao dịch gửi yêu cầu khóa đến bộ lập lịch của trang web. Bộ lập lịch đưa yêu cầu vào hàng đợi tương ứng theo thứ tự dấu thời gian tăng dần. Yêu cầu được xử lý từ phía trước hàng đợi theo thứ tự dấu thời gian của chúng, tức là yêu cầu cũ nhất trước.
Đồ thị xung đột
Một phương pháp khác là tạo đồ thị xung đột. Đối với các lớp giao dịch này được xác định. Một lớp giao dịch chứa hai tập dữ liệu được gọi là tập đọc và tập ghi. Một giao dịch thuộc về một lớp cụ thể nếu tập đọc của giao dịch là một tập con của tập đọc 'của lớp và tập ghi của giao dịch là tập con của tập ghi' của lớp. Trong giai đoạn đọc, mỗi giao dịch đưa ra yêu cầu đọc cho các mục dữ liệu trong tập đọc của nó. Trong giai đoạn ghi, mỗi giao dịch đưa ra các yêu cầu ghi của nó.
Biểu đồ xung đột được tạo cho các lớp mà các giao dịch đang hoạt động thuộc về. Điều này chứa một tập hợp các cạnh dọc, ngang và chéo. Một cạnh dọc kết nối hai nút trong một lớp và biểu thị xung đột trong lớp. Một cạnh ngang kết nối hai nút trên hai lớp và biểu thị xung đột ghi-ghi giữa các lớp khác nhau. Một cạnh chéo kết nối hai nút trên hai lớp và biểu thị xung đột ghi-đọc hoặc đọc-ghi giữa hai lớp.
Các đồ thị xung đột được phân tích để xác định liệu hai giao dịch trong cùng một lớp hoặc trên hai lớp khác nhau có thể chạy song song hay không.
Thuật toán điều khiển đồng thời lạc quan phân tán
Thuật toán điều khiển đồng thời lạc quan phân tán mở rộng thuật toán điều khiển đồng thời lạc quan. Đối với phần mở rộng này, hai quy tắc được áp dụng:
Rule 1- Theo quy tắc này, một giao dịch phải được xác thực cục bộ tại tất cả các trang web khi nó thực thi. Nếu một giao dịch được phát hiện là không hợp lệ tại bất kỳ trang web nào, nó sẽ bị hủy bỏ. Xác thực cục bộ đảm bảo rằng giao dịch duy trì khả năng tuần tự hóa tại các trang web nơi nó đã được thực hiện. Sau khi một giao dịch vượt qua kiểm tra xác thực cục bộ, nó sẽ được xác thực trên toàn cầu.
Rule 2- Theo quy tắc này, sau khi một giao dịch vượt qua kiểm tra xác thực cục bộ, nó sẽ được xác thực toàn cầu. Xác thực toàn cầu đảm bảo rằng nếu hai giao dịch xung đột chạy cùng nhau tại nhiều hơn một trang web, chúng sẽ cam kết theo cùng một thứ tự tương đối tại tất cả các trang mà chúng chạy cùng nhau. Điều này có thể yêu cầu một giao dịch phải đợi giao dịch xung đột khác, sau khi xác thực trước khi cam kết. Yêu cầu này làm cho thuật toán kém lạc quan hơn vì một giao dịch có thể không thể cam kết ngay sau khi nó được xác thực tại một trang web.