Giao dịch
Giao dịch là một chuỗi các thao tác trên dữ liệu có điểm bắt đầu và kết thúc.
Một giao dịch là việc thực hiện tuần tự các thao tác đọc và ghi. Việc kết thúc giao dịch có thể là lưu các thay đổi (cam kết) hoặc hủy các thay đổi (khôi phục). Liên quan đến cơ sở dữ liệu, một giao dịch bao gồm một số yêu cầu được coi là một yêu cầu duy nhất.
Giao dịch phải đáp ứng các thuộc tính ACID
Tính nguyên tử. Giao dịch được hoàn thành hoàn toàn hoặc không hoàn thành.
Tính nhất quán. Khi hoàn thành một giao dịch, không được vi phạm các hạn chế áp đặt đối với dữ liệu (ví dụ: các ràng buộc trong cơ sở dữ liệu). Tính nhất quán ngụ ý rằng hệ thống sẽ được chuyển từ trạng thái đúng này sang trạng thái đúng khác.
Sự cách ly. Các giao dịch chạy song song không được ảnh hưởng lẫn nhau, ví dụ như thay đổi dữ liệu được sử dụng bởi giao dịch khác. Kết quả của việc thực hiện các giao dịch song song phải giống như khi các giao dịch được thực hiện tuần tự.
Sự bền vững. Một khi đã cam kết, những thay đổi sẽ không bị mất.
Nhật ký giao dịch
Nhật ký lưu trữ các thay đổi được thực hiện bởi các giao dịch, đảm bảo tính nguyên tử và ổn định của dữ liệu trong trường hợp hệ thống bị lỗi
Nhật ký chứa các giá trị mà dữ liệu có trước và sau khi được giao dịch thay đổi. Chiến lược ghi nhật ký viết trước yêu cầu thêm mục nhập nhật ký về các giá trị trước đó trước khi bắt đầu và về các giá trị cuối cùng sau khi giao dịch hoàn tất. Trong trường hợp hệ thống dừng đột ngột, cơ sở dữ liệu sẽ đọc nhật ký theo thứ tự ngược lại và hủy các thay đổi do giao dịch thực hiện. Gặp phải một giao dịch bị gián đoạn, cơ sở dữ liệu sẽ thực thi nó và thực hiện các thay đổi về nó trong nhật ký. Ở trạng thái tại thời điểm xảy ra lỗi, cơ sở dữ liệu sẽ đọc nhật ký theo thứ tự chuyển tiếp và trả về các thay đổi được thực hiện bởi các giao dịch. Bằng cách này, tính ổn định của các giao dịch đã được thực hiện và tính nguyên tử của giao dịch bị gián đoạn được bảo toàn.
Chỉ thực hiện lại các giao dịch thất bại là không đủ để phục hồi.
Ví dụ. Người dùng có 500 USD trong tài khoản của mình và người dùng quyết định rút số tiền đó từ máy ATM. Hai giao dịch đang được tiến hành. Cái đầu tiên đọc giá trị số dư và nếu có đủ tiền trong số dư, nó sẽ phát hành tiền cho người dùng. Thứ hai trừ số tiền cần thiết từ số dư. Giả sử hệ thống gặp sự cố và thao tác đầu tiên không thành công, nhưng thao tác thứ hai thì thất bại. Trong trường hợp này, chúng tôi không thể phát hành lại tiền cho người dùng nếu không đưa hệ thống về trạng thái ban đầu với số dư dương.
Mức độ cách nhiệt
Đã đọc cam kết
Vấn đề Dirty Read là một giao dịch có thể đọc kết quả trung gian của một giao dịch khác.
Ví dụ. Giá trị số dư ban đầu là $0. T1 thêm $50 vào số dư của bạn. T2 đọc giá trị số dư ($50). T1 loại bỏ các thay đổi và thoát. T2 tiếp tục thực hiện với dữ liệu số dư không chính xác.
Giải pháp là đọc dữ liệu cố định (Read Commited), cấm đọc dữ liệu do giao dịch thay đổi. Nếu giao dịch A đã thay đổi một bộ dữ liệu nhất định thì giao dịch B khi truy cập vào dữ liệu này buộc phải đợi giao dịch A hoàn tất.
Đọc lặp lại
Vấn đề cập nhật bị mất. T1 lưu các thay đổi bên trên các thay đổi của T2.
Ví dụ. Giá trị số dư ban đầu là $0 và hai giao dịch đồng thời bổ sung số dư. T1 và T2 đọc số dư là $0. Sau đó T2 cộng $200 vào $0 và lưu kết quả. T1 cộng $100 vào $0 và lưu kết quả. Kết quả cuối cùng là 100 USD thay vì 300 USD.
Vấn đề đọc không thể lặp lại. Đọc cùng một dữ liệu liên tục trả về các giá trị khác nhau.
Ví dụ. T1 đọc giá trị số dư là $0. T2 sau đó thêm $50 vào số dư và kết thúc. T1 đọc lại dữ liệu và phát hiện sự khác biệt với kết quả trước đó.
Đọc lặp lại đảm bảo rằng lần đọc thứ hai sẽ trả về kết quả tương tự. Dữ liệu được đọc bởi một giao dịch không thể thay đổi ở những giao dịch khác cho đến khi giao dịch được hoàn thành. Nếu giao dịch A đã đọc một tập dữ liệu nhất định thì giao dịch B khi truy cập dữ liệu này buộc phải đợi giao dịch A hoàn tất.
Đọc theo thứ tự (Có thể tuần tự hóa)
Vấn đề đọc Phantom. Hai truy vấn chọn dữ liệu dựa trên một điều kiện nhất định sẽ trả về các giá trị khác nhau.
Ví dụ. T1 yêu cầu số lượng tất cả người dùng có số dư lớn hơn $0 nhưng nhỏ hơn $100. T2 khấu trừ 1 USD từ người dùng có số dư 101 USD. T1 đưa ra lại yêu cầu.
Đọc theo thứ tự (Có thể tuần tự hóa). Các giao dịch được thực hiện hoàn toàn tuần tự. Nghiêm cấm cập nhật hoặc thêm hồ sơ nằm trong các điều khoản của yêu cầu. Nếu giao dịch A đã yêu cầu dữ liệu từ toàn bộ bảng thì toàn bộ bảng sẽ bị đóng băng đối với các giao dịch khác cho đến khi giao dịch A hoàn tất.
Người lập kế hoạch
Đặt thứ tự các hoạt động sẽ được thực hiện trong các giao dịch song song.
Cung cấp một mức độ cô lập nhất định. Nếu kết quả của các phép toán không phụ thuộc vào thứ tự của chúng thì các phép toán đó có tính giao hoán (Có thể cho phép). Các phép toán đọc và các phép toán trên dữ liệu khác nhau có tính chất giao hoán. Các thao tác đọc-ghi và ghi-ghi không có tính chất giao hoán. Nhiệm vụ của bộ lập lịch là xen kẽ các hoạt động được thực hiện bởi các giao dịch song song sao cho kết quả thực hiện tương đương với việc thực hiện tuần tự các giao dịch.
Cơ chế kiểm soát công việc song song (Concurrency Control)
Lạc quan dựa trên việc phát hiện và giải quyết xung đột, bi quan dựa trên việc ngăn chặn xung đột phát sinh.
Theo cách tiếp cận lạc quan, nhiều người dùng có thể tùy ý sử dụng các bản sao dữ liệu. Người đầu tiên hoàn tất chỉnh sửa sẽ lưu các thay đổi, trong khi những người khác phải hợp nhất các thay đổi. Một thuật toán lạc quan cho phép xảy ra xung đột nhưng hệ thống phải phục hồi sau xung đột.
Với cách tiếp cận bi quan, người dùng đầu tiên nắm bắt được dữ liệu sẽ ngăn cản người khác nhận dữ liệu. Nếu xung đột hiếm khi xảy ra thì nên chọn chiến lược lạc quan vì nó mang lại mức độ đồng thời cao hơn.
Khóa
Nếu một giao dịch có dữ liệu bị khóa thì các giao dịch khác phải đợi cho đến khi dữ liệu được mở khóa mới truy cập vào dữ liệu.
Một khối có thể được phủ lên cơ sở dữ liệu, bảng, hàng hoặc thuộc tính. Khóa chia sẻ có thể được áp dụng trên cùng một dữ liệu bằng một số giao dịch, cho phép tất cả các giao dịch (bao gồm cả giao dịch đã áp đặt nó) đọc, cấm sửa đổi và thu thập độc quyền. Khóa độc quyền chỉ có thể được áp đặt bởi một giao dịch, cho phép mọi hành động của giao dịch áp đặt, cấm mọi hành động của người khác.
Bế tắc là tình trạng các giao dịch kết thúc ở trạng thái chờ xử lý kéo dài vô thời hạn.
Ví dụ. Giao dịch đầu tiên chờ dữ liệu được thu thập bởi giao dịch thứ hai được giải phóng, trong khi giao dịch thứ hai chờ dữ liệu được thu thập bởi giao dịch thứ nhất được giải phóng.
Một giải pháp lạc quan cho vấn đề bế tắc cho phép bế tắc xảy ra, nhưng sau đó khôi phục hệ thống bằng cách khôi phục một trong các giao dịch liên quan đến bế tắc.
Sự bế tắc được tìm kiếm ở những khoảng thời gian nhất định. Một trong những phương pháp phát hiện là theo thời gian, tức là coi như bế tắc đã xảy ra nếu giao dịch mất quá nhiều thời gian để hoàn thành. Khi phát hiện bế tắc, một trong các giao dịch sẽ được khôi phục, cho phép các giao dịch khác liên quan đến bế tắc hoàn tất. Việc lựa chọn nạn nhân có thể dựa trên giá trị của giao dịch hoặc thâm niên của họ (sơ đồ Wait-Die và Wound-wait).
Mỗi giao dịch T một dấu thời gian được chỉ định TS chứa thời gian bắt đầu của giao dịch.
Đợi-Chết.
Nếu TS(Ti) < TS(Tj)sau đó Ti chờ đợi, nếu không Ti quay lại và bắt đầu lại với cùng dấu thời gian.
Nếu một giao dịch trẻ đã có được một tài nguyên và một giao dịch cũ hơn yêu cầu cùng một tài nguyên thì giao dịch cũ hơn được phép chờ. Nếu giao dịch cũ hơn đã có được tài nguyên thì giao dịch trẻ hơn yêu cầu tài nguyên đó sẽ được khôi phục.
Vết thương-đợi đã.
Nếu TS(Ti) < TS(Tj)sau đó Tj quay lại và bắt đầu lại với cùng dấu thời gian, nếu không Ti chờ.
Nếu giao dịch trẻ hơn đã có được tài nguyên và giao dịch cũ hơn yêu cầu cùng một tài nguyên thì giao dịch trẻ hơn sẽ được khôi phục. Nếu giao dịch cũ hơn đã có được tài nguyên thì giao dịch trẻ hơn yêu cầu tài nguyên đó sẽ được phép chờ. Việc lựa chọn nạn nhân dựa trên mức độ ưu tiên sẽ ngăn chặn tình trạng bế tắc nhưng khôi phục các giao dịch không bị bế tắc. Vấn đề là các giao dịch có thể bị roll back nhiều lần vì... một giao dịch cũ hơn có thể giữ tài nguyên trong một thời gian dài.
Một giải pháp bi quan cho vấn đề bế tắc không cho phép giao dịch bắt đầu thực hiện nếu có nguy cơ xảy ra bế tắc.
Để phát hiện bế tắc, một biểu đồ được xây dựng (biểu đồ chờ, biểu đồ chờ), các đỉnh của chúng là các giao dịch và các cạnh được định hướng từ các giao dịch đang chờ giải phóng dữ liệu đến giao dịch đã thu thập dữ liệu này. Bế tắc được coi là đã xảy ra nếu đồ thị có vòng lặp. Xây dựng biểu đồ chờ, đặc biệt là trong cơ sở dữ liệu phân tán, là một thủ tục tốn kém.
Khóa hai pha - ngăn ngừa bế tắc bằng cách thu giữ tất cả tài nguyên được sử dụng bởi giao dịch khi bắt đầu giao dịch và giải phóng chúng khi kết thúc
Tất cả các thao tác chặn phải diễn ra trước thao tác mở khóa đầu tiên. Nó có hai giai đoạn - Giai đoạn phát triển, trong đó các chuôi tích tụ và Giai đoạn thu nhỏ, trong đó các chuôi được giải phóng. Nếu không thể chiếm được một trong các tài nguyên, giao dịch sẽ bắt đầu lại. Có thể một giao dịch sẽ không thể có được các tài nguyên cần thiết, ví dụ: nếu một số giao dịch cạnh tranh để giành cùng một tài nguyên.
Cam kết hai giai đoạn đảm bảo rằng cam kết được thực thi trên tất cả các bản sao cơ sở dữ liệu
Mỗi cơ sở dữ liệu nhập thông tin về dữ liệu sẽ được thay đổi vào nhật ký và phản hồi với điều phối viên OK (Giai đoạn bỏ phiếu). Sau khi mọi người đều trả lời OK, điều phối viên sẽ gửi tín hiệu bắt buộc mọi người phải cam kết. Sau khi cam kết, các máy chủ phản hồi OK; nếu ít nhất một máy chủ không phản hồi OK thì điều phối viên sẽ gửi tín hiệu hủy các thay đổi đến tất cả các máy chủ (Giai đoạn hoàn thành).
Phương pháp dấu thời gian
Giao dịch cũ hơn được khôi phục khi cố gắng truy cập dữ liệu liên quan đến giao dịch trẻ hơn
Mỗi giao dịch được gán một dấu thời gian TS tương ứng với thời điểm bắt đầu thực hiện. Nếu như Ti lớn hơn Tjsau đó TS(Ti) < TS(Tj).
Khi một giao dịch được khôi phục, nó sẽ được gán một dấu thời gian mới. Mỗi đối tượng dữ liệu Q tham gia vào giao dịch được đánh dấu bằng hai nhãn. W-TS(Q) — dấu thời gian của giao dịch trẻ nhất đã hoàn thành thành công bản ghi Q. R-TS(Q) — dấu thời gian của giao dịch trẻ nhất đã thực hiện bản ghi đọc trên Q.
Khi giao dịch T yêu cầu đọc dữ liệu Q Có hai lựa chọn.
Nếu TS(T) < W-TS(Q), nghĩa là dữ liệu đã được cập nhật bởi một giao dịch trẻ hơn, sau đó giao dịch đó T cuộn lại.
Nếu TS(T) >= W-TS(Q), sau đó việc đọc được thực hiện và R-TS(Q) đang trở thành MAX(R-TS(Q), TS(T)).
Khi giao dịch T yêu cầu thay đổi dữ liệu Q Có hai lựa chọn.
Nếu TS(T) < R-TS(Q), nghĩa là dữ liệu đã được đọc bởi một giao dịch trẻ hơn và nếu thay đổi được thực hiện thì xung đột sẽ phát sinh. Giao dịch T cuộn lại.
Nếu TS(T) < W-TS(Q), nghĩa là giao dịch cố gắng ghi đè lên một giá trị mới hơn, giao dịch T sẽ được khôi phục. Trong các trường hợp khác, sự thay đổi được thực hiện và W-TS(Q) trở nên bình đẳng TS(T).
Không cần xây dựng đồ thị chờ đắt tiền. Các giao dịch cũ hơn phụ thuộc vào các giao dịch mới hơn, do đó không có chu kỳ nào trong biểu đồ chờ. Không có tình trạng bế tắc vì giao dịch không phải chờ đợi mà được khôi phục ngay lập tức. Có thể thực hiện khôi phục theo tầng. Nếu như Ti lăn đi và Tj Tôi đọc dữ liệu mà tôi đã thay đổi Tisau đó Tj cũng nên quay lại. Nếu cùng một lúc Tj đã được thực hiện thì sẽ vi phạm nguyên tắc ổn định.
Một trong những giải pháp cho việc rollback theo tầng. Một giao dịch hoàn thành tất cả các thao tác ghi ở cuối và các giao dịch khác phải đợi thao tác đó hoàn tất. Giao dịch chờ được cam kết trước khi được đọc.
Quy tắc viết Thomas - một biến thể của phương pháp dấu thời gian trong đó dữ liệu được cập nhật bởi một giao dịch trẻ hơn bị cấm bị ghi đè bởi một giao dịch cũ hơn
giao dịch T yêu cầu thay đổi dữ liệu Q. Nếu TS(T) < W-TS(Q), nghĩa là giao dịch cố gắng ghi đè lên một giá trị mới hơn, giao dịch T không được khôi phục như trong phương thức dấu thời gian.
Nguồn: www.habr.com