DBMS phân tán - Kiểm soát sao chép

Chương này xem xét kiểm soát sao chép, được yêu cầu để duy trì dữ liệu nhất quán trong tất cả các trang web. Chúng tôi sẽ nghiên cứu các kỹ thuật điều khiển sao chép và các thuật toán cần thiết để điều khiển sao chép.

Như đã thảo luận trước đó, replicationlà một kỹ thuật được sử dụng trong cơ sở dữ liệu phân tán để lưu trữ nhiều bản sao của một bảng dữ liệu tại các trang web khác nhau. Vấn đề với việc có nhiều bản sao trong nhiều trang web là chi phí duy trì tính nhất quán của dữ liệu, đặc biệt là trong các hoạt động cập nhật.

Để duy trì dữ liệu nhất quán lẫn nhau trong tất cả các trang web, các kỹ thuật kiểm soát sao chép cần được áp dụng. Có hai cách tiếp cận để kiểm soát sao chép, đó là -

Kiểm soát sao chép đồng bộ
Kiểm soát sao chép không đồng bộ

Kiểm soát sao chép đồng bộ

Trong cách tiếp cận sao chép đồng bộ, cơ sở dữ liệu được đồng bộ hóa để tất cả các bản sao luôn có cùng giá trị. Một giao dịch yêu cầu một mục dữ liệu sẽ có quyền truy cập vào cùng một giá trị trong tất cả các trang web. Để đảm bảo tính đồng nhất này, giao dịch cập nhật một mục dữ liệu được mở rộng để nó thực hiện cập nhật trong tất cả các bản sao của mục dữ liệu. Nói chung, giao thức cam kết hai pha được sử dụng cho mục đích này.

Ví dụ, chúng ta hãy xem xét một bảng dữ liệu PROJECT (PId, PName, PLocation). Chúng tôi cần chạy một giao dịch T1 cập nhật PLocation thành 'Mumbai', nếu PLocation là 'Bombay'. Nếu không có bản sao nào ở đó, các hoạt động trong giao dịch T1 sẽ là:

Begin T1: 
   Update PROJECT Set PLocation = 'Mumbai' 
   Where PLocation = 'Bombay'; 
End T1;

Nếu bảng dữ liệu có hai bản sao ở vị trí A và vị trí B, thì T1 cần tạo ra hai con T1A và T1B tương ứng với hai vị trí đó. Giao dịch mở rộng T1 sẽ là -

Begin T1: 
   Begin T1A : 
      Update PROJECT Set PLocation = 'Mumbai' 
      Where PLocation = 'Bombay'; 
   End T1A;  
	
   Begin T2A : 
      Update PROJECT Set PLocation = 'Mumbai'
      Where PLocation = 'Bombay'; 
   End T2A; 
	
End T1;

Kiểm soát sao chép không đồng bộ

Trong cách tiếp cận sao chép không đồng bộ, các bản sao không phải lúc nào cũng duy trì cùng một giá trị. Một hoặc nhiều bản sao có thể lưu trữ giá trị lỗi thời và một giao dịch có thể thấy các giá trị khác nhau. Quá trình đưa tất cả các bản sao về giá trị hiện tại được gọi làsynchronization.

Một phương pháp đồng bộ hóa phổ biến là phương pháp lưu trữ và chuyển tiếp. Trong phương pháp này, một trang được chỉ định là trang chính và các trang khác là trang phụ. Trang web chính luôn chứa các giá trị được cập nhật. Tất cả các giao dịch đầu tiên vào trang web chính. Các giao dịch này sau đó được xếp hàng đợi để nộp đơn ở các trang phụ. Các trang web thứ cấp chỉ được cập nhật bằng phương pháp triển khai khi giao dịch được lên lịch thực hiện trên đó.

Thuật toán kiểm soát sao chép

Một số thuật toán điều khiển sao chép là -

Thuật toán điều khiển sao chép master-slave.
Thuật toán biểu quyết phân tán.
Thuật toán đồng thuận đa số.
Thuật toán mã thông báo lưu hành.

Thuật toán kiểm soát nhân bản Master-Slave

Có một trang web chính và trang web nô lệ 'N'. Một thuật toán chính chạy tại trang web chính để phát hiện xung đột. Một bản sao của thuật toán nô lệ chạy ở mỗi trang web phụ. Thuật toán tổng thể thực hiện theo hai giai đoạn sau:

Transaction acceptance/rejection phase- Khi một giao dịch đi vào màn hình giao dịch của một trang web nô lệ, trang web phụ sẽ gửi một yêu cầu đến trang web chính. Trang chủ kiểm tra xung đột. Nếu không có bất kỳ xung đột nào, chủ sẽ gửi một thông báo “ACK +” đến trang web phụ, sau đó bắt đầu giai đoạn ứng dụng giao dịch. Nếu không, master sẽ gửi một thông báo “ACK-” đến slave, sau đó sẽ từ chối giao dịch.
Transaction application phase- Khi bước vào giai đoạn này, trang web nô lệ nơi giao dịch đã nhập sẽ phát một yêu cầu tới tất cả các nô lệ để thực hiện giao dịch. Khi nhận được các yêu cầu, các nô lệ ngang hàng thực hiện giao dịch và gửi một “ACK” đến các nô lệ yêu cầu khi hoàn thành. Sau khi nô lệ yêu cầu đã nhận được thông báo “ACK” từ tất cả các đồng nghiệp của nó, nó sẽ gửi thông báo “XONG” đến trang web chính. Master hiểu rằng giao dịch đã được hoàn thành và xóa nó khỏi hàng đợi đang chờ xử lý.

Thuật toán bỏ phiếu phân tán

Điều này bao gồm 'N' các trang web ngang hàng, tất cả đều phải “OK” một giao dịch trước khi nó bắt đầu thực hiện. Sau đây là hai giai đoạn của thuật toán này:

Distributed transaction acceptance phase- Khi một giao dịch đi vào trình quản lý giao dịch của một trang, nó sẽ gửi một yêu cầu giao dịch đến tất cả các trang khác. Khi nhận được yêu cầu, một trang web ngang hàng giải quyết xung đột bằng cách sử dụng các quy tắc bỏ phiếu dựa trên mức độ ưu tiên. Nếu tất cả các trang web ngang hàng “OK” với giao dịch, trang web yêu cầu bắt đầu giai đoạn đăng ký. Nếu bất kỳ trang web ngang hàng nào không “OK” một giao dịch, trang web yêu cầu sẽ từ chối giao dịch.
Distributed transaction application phase- Khi bước vào giai đoạn này, trang web nơi giao dịch đã được nhập sẽ phát một yêu cầu đến tất cả các nô lệ để thực hiện giao dịch. Khi nhận được các yêu cầu, các nô lệ ngang hàng thực hiện giao dịch và gửi một thông báo “ACK” đến nô lệ yêu cầu khi hoàn thành. Sau khi nô lệ yêu cầu đã nhận được thông báo “ACK” từ tất cả các đồng nghiệp của nó, nó cho người quản lý giao dịch biết rằng giao dịch đã được hoàn thành.

Thuật toán đồng thuận đa số

Đây là một biến thể từ thuật toán bỏ phiếu phân tán, trong đó một giao dịch được phép thực hiện khi đa số các đồng nghiệp "OK" một giao dịch. Điều này được chia thành ba giai đoạn -

Voting phase- Khi một giao dịch đi vào trình quản lý giao dịch của một trang, nó sẽ gửi một yêu cầu giao dịch đến tất cả các trang khác. Khi nhận được yêu cầu, một trang web ngang hàng sẽ kiểm tra các xung đột bằng cách sử dụng các quy tắc bỏ phiếu và giữ các giao dịch xung đột, nếu có, trong hàng chờ xử lý. Sau đó, nó sẽ gửi một thông báo “OK” hoặc “NOT OK”.
Transaction acceptance/rejection phase- Nếu trang web yêu cầu nhận được phần lớn “OK” trong giao dịch, nó chấp nhận giao dịch và phát “CHẤP NHẬN” cho tất cả các trang. Nếu không, nó sẽ phát “TỪ CHỐI” đến tất cả các trang web và từ chối giao dịch.
Transaction application phase- Khi một trang web ngang hàng nhận được thông báo “TỪ CHỐI”, nó sẽ xóa giao dịch này khỏi danh sách đang chờ xử lý và xem xét lại tất cả các giao dịch bị hoãn lại. Khi một trang web ngang hàng nhận được thông báo “CHẤP NHẬN”, nó sẽ áp dụng giao dịch và từ chối tất cả các giao dịch bị hoãn lại trong hàng đợi đang chờ xử lý mâu thuẫn với giao dịch này. Nó gửi một “ACK” đến nô lệ yêu cầu khi hoàn thành.

Thuật toán lưu hành mã thông báo

Theo cách tiếp cận này, các giao dịch trong hệ thống được tuần tự hóa bằng cách sử dụng mã thông báo lưu hành và được thực thi tương ứng với mọi bản sao của cơ sở dữ liệu. Do đó, tất cả các giao dịch được chấp nhận, tức là không có giao dịch nào bị từ chối. Điều này có hai giai đoạn -

Transaction serialization phase- Trong giai đoạn này, tất cả các giao dịch được lên lịch chạy theo thứ tự tuần tự hóa. Mỗi giao dịch trong mỗi trang web được gán một vé duy nhất từ một chuỗi tuần tự, cho biết thứ tự giao dịch. Khi một giao dịch đã được chỉ định một vé, nó sẽ được truyền đến tất cả các trang web.
Transaction application phase- Khi một trang web nhận được một giao dịch cùng với phiếu của nó, nó sẽ đặt giao dịch đó để thực hiện theo phiếu của nó. Sau khi giao dịch kết thúc, trang web này sẽ phát đi một thông báo thích hợp. Một giao dịch kết thúc khi nó đã hoàn thành việc thực hiện ở tất cả các trang web.