0.4 Điều khiển cạnh tranh  (Page 10/13)

Trong các hệ CSDL đa phiên bản, mỗi hoạt động Write(Q) tạo ra một bản mới của Q. Khi một hoạt động Read(Q) được phát ra, hệ thống chọn lựa một trong các phiên bản của Q để đọc. Sơ đồ điều khiển cạnh tranh phải đảm bảo rằng việc chọn lựa này được tiến hành sao cho tính khả tuần tự được đảm bảo. Do lý do hiệu năng, một giao dịch phải có khả năng xác định dễ dàng và mau chóng phiên bản dhạng mục dữ liệu sẽ đọc.

Thứ tự tem thời gian đa phiên bản

Kỹ thuật chung được dùng trong các sơ đồ đa phiên bản là tem thời gian. Ta kết hợp với một giao dịch một tem thời gian tĩnh duy nhất, ký hiệu TS(Ti). Tem thời gian này được gán trước khi khi giao dịch bắt đầu sự thực hiện. Mỗi hạng mục dữ liệu Q kết hợp với một dãy<Q1, Q2, ... , Qm>mỗi phiên bản Qk chứa ba trường dữ liệu:

• Content là giá trị của phiên bản Qi
• W-timestamp(Qk) là tem thời gian của giao dịch đã tạo ra phiên bản Qk
• R-timestamp(Qk) là tem thời gian lớn nhất của giao dịch đã đọc thành công phiên bản Qk

Một giao dịch, gọi là Ti , tạo ra phiên bản Qk của hạng mục dữ liệu Q bằng cách phát ra một hoạt động Write(Q). Trường Content của phiên bản chứa giá trị được viết bởi Ti . W-timestamp và R-timestamp được khởi động là TS(Ti). Giá trị R-timestamp được cập nhật mỗi khi một giao dịch Tj đọc nội dung của Qk và R-timestamp(Qk)<TS(Tj).

Sơ đồ tem thời gian đa phiên bản dưới đây sẽ đảm bảo tính khả tuần tự. Sơ đồ hoạt động như sau: giả sử Tj phát ra một hoạt động Read(Q) hoặc Write(Q). Qk ký hiệu phiên bản của Q, tem thời gian viết của nó là tem thời gian viết lớn nhất nhỏ hơn hoặc bằng TS(Tj).

1. Nếu giao dịch Tj phát ra một Read(Q), khi đó giá trị trả lại là nội dung của phiên bản Qk
2. Nếu Tj phát ra một Write(Q) và nếu TS(Tj)<R-timestamp(Qk) khi đó giao dịch Tj bị cuộn lại. Nếu không, nếu TS(Tj) = W-timestamp(Qk) nội dung của Qk bị viết đè, khác đi một phiên bản mới của Q được tạo.

Các phiên bản không còn được dùng đến nữa bị xoá đi dựa trên quy tắc sau: Giả sử có hai phiên bản Qi và Qj của một hạng mục dữ liệu và cả hai phiên bản này cùng có W-timestamp nhỏ hơn tem thời gian của giao dịch già nhất trong hệ thống, khi đó phiên bản già hơn trong hai phiên bản Qi và Qj sẽ không còn được dùng nữa và bị xoá đi.

Sơ đồ thứ tự tem thời gian đa phiên bản có tính chất hay đó là một yêu cầu Read không bao giờ thất bại và không phải chờ đợi. Trong một hệ thống mà hoạt động Read xảy ra nhiều hơn Write cái lợi này là đáng kể. Tuy nhiên có vài điều bất lợi của sơ đồ này là: thứ nhất đọc một hạng mục dữ liệu cũng đòi hỏi cập nhật trường R-timestamp, thứ hai là xung đột giữa các giao dịch được giải quyết bằng cuộn lại.

Chốt hai kỳ đa phiên bản

Giao thức chốt hai kỳ đa phiên bản cố gắng tổ hợp những ưu điểm của điều khiển cạnh tranh với các ưu điểm của chốt hai kỳ. Giao thức này phân biệt các giao dịch chỉ đọc và các giao dịch cập nhật.

Các giao dịch cập nhật thực hiện chốt hai kỳ nghiêm khắc (các chốt được giữ đến tận khi kết thúc giao dịch). Mỗi hạng mục dữ liệu có một tem thời gian. Tem thời gian trong trường hợp này không là tem thời gian dựa trên đồng hồ thực mà là một bộ đếm, sẽ được gọi là TS-counter.