Quartz 🪬

Commit Protocols

12 min read

Các commit protocol thường được sử dụng trong các Database System phân tán (thường là trong các hệ thống sử dụng kiến trúc microservices) nhằm thực hiện một atomic operation (transaction) nào đó.

The Problem

Cho một hệ CSDL có các cấu trúc dữ liệu phức tạp nằm ở 3 site A, B và C.

  • Các thao tác cập nhật cấu trúc dữ liệu sẽ nằm trong một transaction.
  • A khởi tạo transaction và các site còn lại thực hiện transaction.

Có thể xem A là ứng dụng đang cần ghi dữ liệu lên 2 database phân tán là B và C.

Minh họa transaction:

Begin
{
	Read some stuff, get some locks
	Do some updates at B, C
}
Commit

Giả sử B và C đã hoàn thành được một số bước trong transaction nhưng có một lỗi xảy ra ở site B khiến cho nó bị restart. Câu hỏi đặt ra là làm sao để C undo những bước đã thực hiện?

Câu trả lời là chúng ta đưa ra một quy định để các site xem những việc đang làm là nhất thời và có thể discard khi có một site nào đó bị crash.

Two-phase Commit Protocol (2PC)

Xét một hệ thống phân tán bao gồm 1 site chịu trách nhiệm khởi tạo transaction (coordinator) và các site thực hiện transaction (các participant). Giao thức sẽ gồm hai phase như sau:

The Algorithm

Vote-Request Phase

  1. Coordinator gửi một vote-request message đến tất cả các participant để hỏi xem chúng có thể commit được hay không và chờ phản hồi.
  2. Các participant thực hiện transaction đến khi nào cần commit. Khi đó chúng sẽ ghi một entry vào undo log và một entry vào redo log.
  3. Mỗi participant phản hồi lại một agreement message (vote “Yes”) nếu các bước trong transaction được thực hiện thành công hoặc một abort message (vote “No”) nếu có xảy ra một lỗi nào đó khiến cho nó không thể commit. Các tài nguyên của participant sẽ bị khóa nếu nó vote “Yes”.

Commit (or completion) Phase

Thành công:

Nếu coordinator nhận được đủ số lượng vote “Yes” từ tất cả các participant trong vote-request phase:

  1. Coordinator gửi một commit message đến tất cả các participant và tạo ra một record ở trong commit log (record này sẽ hỗ trợ trong quá trình khôi phục).
  2. Mỗi participant hoàn thành transaction, giải phóng tất cả các lock và tài nguyên bị khóa trong khi thực hiện transaction.
  3. Mỗi participant gửi lại một ACK cho coordinator.
  4. Coordinator hoàn thành transaction khi nhận đủ ACK từ tất cả các participant.

Thất bại:

Nếu có bất kỳ participant nào vote “No” trong vote-request phase:

  1. Coordinator gửi một abort message đến tất cả các participant.
  2. Mỗi participant undo transaction sử dụng undo log, giải phóng tất cả các lock và tài nguyên bị khóa trong khi thực hiện transaction.
  3. Mỗi participant gửi lại một ACK cho coordinator.
  4. Coordinator undo transaction khi nhận đủ ACK từ tất cả các participant.

Sơ đồ minh họa:

Coordinator                                          Participant
							PREPARE-COMMIT
                 -------------------------------->
                             VOTE YES/NO             prepare/abort
                 <-------------------------------
commit/abort               COMMIT/ROLLBACK
                 -------------------------------->
                             ACKNOWLEDGEMENT         commit/abort
                 <--------------------------------
end

Summary

Giao thức Two-phase Commit (2PC) trong hệ thống phân tán bao gồm hai phase: vote-request phase và commit phase.

  1. Trong phase đầu, coordinator yêu cầu tất cả các participant bình chọn cho việc commit.
  2. Trong phase sau:
    • Nếu nhận đủ số phiếu “Yes”: gửi lệnh commit.
    • Nếu có bất kỳ phiếu “No” nào: gửi lệnh abort để hủy bỏ transaction.

State Machine Diagram

State machine diagram của coordinator và các participant (hay cohort):

Ký hiệu các trạng thái:

  • q: nhàn rỗi hoặc đang truy vấn.
  • w: chờ (sẵn sàng để commit)
  • c: commit
  • a: abort

Ta có khẳng định sau:

  • Coordinator ở state q thì các participant có thể ở state q, w và a.
  • Coordinator ở state w thì các participant có thể ở state q, w và a.
  • Coordinator ở state a/c thì các participant có thể ở state w và a/c.
  • Participant ở state a/c thì các participant khác có thể ở state w và a/c.
  • Một participant không bao giờ ở state c nếu có một participant khác ở state q. Lý do là vì để commit thì participant cần phải nhận được commit message từ coordinator. Tuy nhiên, nếu tồn tại một site đang ở state q thì có nghĩa là coordinator chưa nhận đủ vote message từ các participant nên nó sẽ không thể gửi commit message cho các participant.

Managing Scenarios with Timeouts

Các trạng thái của coordinator và participant đều có thể xảy ra blocking. Do đó, chúng ta cần sử dụng cơ chế timeout để xử lý transaction.

Trường hợp 1: participant chờ để nhận vote-request message từ coordinator khi ở trạng thái q. Nếu sau một khoảng timeout nhất định mà vẫn chưa nhận được thì nó sẽ abort transaction và gửi abort message (vote “No”) đến coordinator.

Trường hợp 2: coordinator có thể ở trạng thái w để chờ nhận các vote message từ các participant. Nếu sau một khoảng timeout nhất định mà nó vẫn chưa nhận đủ các vote message thì nó sẽ abort transaction và gửi abort message cho các participant.

Trường hợp 3: một participant ở trạng thái w đang chờ để nhận được commit hay abort message từ coordinator nhưng coordinator lại bị crash. Sau một khoảng timeout nhất định, participant này sẽ không thể tự động commit hay abort vì nó không biết được coordinator gửi commit hay abort message.

  • Giải pháp đơn giản nhất là giữ cho participant bị block đến khi nào coordinator recover lại và gửi commit/abort message.
  • Một giải pháp khác là cho phép participant liên lạc với các participant khác để quyết định trạng thái của nó. Ví dụ, participant P có thể liên lạc với participant Q:
    • Nếu Q ở trạng thái c thì đồng nghĩa với việc coordinator đã gửi commit message cho các participant. Khi đó, P có thể commit transaction. Điều này khả thi nếu coordinator đã gửi commit message cho Q trước khi nó bị crash và do bị crash nên nó chưa kịp gửi commit message cho P.
    • Tương tự, nếu Q ở trạng thái a thì P cũng có thể abort transaction.

Question

Với trường hợp 3, xét 4 site A, B, C và D. A và B đang ở trạng thái w, C đang ở trạng thái c và D đang ở trạng thái a.

Sẽ thế nào nếu A liên lạc với C và commit, trong khi đó B liên lạc với D và abort? Hệ thống lúc đó sẽ không nhất quán? Nếu vậy thì làm cách nào để đồng bộ?

Handling Crashses

Ta xét hai trường hợp sau:

  • Trường hợp 4: Một vài participant crash ở bước nào đó của transaction.
  • Trường hợp 5: Coordinator crash ở bước nào đó của transaction.

Đối với trường hợp 4:

  • Nếu participant crash trước khi vote (phase 1), coordinator abort transaction (sau timeout).
  • Nếu participant crash sau khi vote (phase 2). Sau khi khôi phục, nó sẽ kiểm tra log của coordinator để biết được rằng cần phải commit hay abort transaction.

Đối với trường hợp 5:

  • Nếu coordinator crash trong lúc chờ nhận vote từ các participant:
    • Sau khi khôi phục thì gửi abort message cho tất cả các participant.
    • Các participant mà đã đồng ý commit (vote “Yes”) thì sẽ undo transaction sử dụng undo log và abort.
    • Các participant còn lại chỉ cần abort.
    • Lưu ý: tất cả các participant đều sẽ bị block cho đến khi coordinator khôi phục.
  • Nếu coordinator crash tại thời điểm sau khi nhận đủ vote “Yes” từ tất cả các participant và trước khi hoàn thành transaction:
    • Khi khôi phục, gửi commit message cho tất cả các participant.

Disadvantages

Sau khi participant gửi agreement message đến coordinator, nó sẽ block đến khi nhận được commit hoặc abort message. Nếu tất cả các participant đều ở trạng thái chờ nhận commit/abort message và coordinator xảy ra lỗi vĩnh viễn thì các participant sẽ không bao giờ hoàn thành được transaction do chúng không thể tự quyết định trạng thái của mình. Điều này khiến cho protocol bị block và đây chính là nhược điểm lớn nhất của 2PC.

Three-phase Commit Protocol (3PC)

Concurrency Set and Sender Set

Concurrency set C(si) là một tập các trạng thái sj của các site khác mà có thể xảy ra khi một site đang ở trạng thái si. Ký hiệu:

C(si) = { sj | sj may be concurrent with si }

Sender set S(s) là tập các sender đã gửi message đến khi site có trạng thái là s. Ký hiệu:

S(s) = { i | in state s we may receive a message from site i }

General Idea

Thêm một phase so với 2PC, bao gồm ba phase như sau:

  1. Hỏi các participant xem có thể commit được hay không (gửi vote-request message). Các participant vote “Yes”/“No” (gửi agreement hoặc abort message).
  2. Coordinator thực hiện abort transaction (gửi abort message) hoặc chuẩn bị commit (gửi prepare-commit message). Các participant trả lời “OK” (gửi ready-commit message).
  3. Thực hiện commit transaction.

Có thể thấy, abort xảy ra ở phase 2 và commit xảy ra ở phase 3.

State Machine Diagram

State machine diagram của coordinator và các participant:

Ta có thêm một trạng thái là:

  • p: coordinator chờ để nhận ready-commit message và participant chờ để nhận commit message.

Có thể thấy, một participant không thể ở trong trạng thái p nếu tồn tại một participant khác đang ở trạng thái q hoặc a.

Failure Cases

Tương tự với 2PC, ta cũng có hai trường hợp đầu:

  1. Trường hợp 6: nếu participant ở state q và quá timeout thì nó sẽ abort transaction và xem như coordinator đã bị crash.
  2. Trường hợp 7: nếu coordinator ở state w và quá timeout thì nó sẽ abort transaction và xem như có một (hoặc tất cả) participant đã bị crash.

Có thêm một số trường hợp sau:

Trường hợp 8: giả sử coordinator bị block ở state p. Sau khi hết timeout, nó sẽ kết luận rằng có một participant nào đó đã bị crash. Tuy nhiên, do participant đó đã gửi lại agreement message (ở phase 2) nên coordinator vẫn sẽ gửi commit message cho các participant đang hoạt động. Đối với participant bị crash, nó sẽ cần phải commit transaction khi khôi phục.

Trường hợp 9: giả sử participant P bị block ở trạng thái w hoặc p. Sau khi hết timeout, nó có thể kết luận rằng coordinator đã bị crash và cần phải quyết định trạng thái tiếp theo là gì. Tương tự như 2PC, participant sẽ liên lạc với một participant Q khác để chuyển trạng thái của mình.

Ngoài việc chuyển trực tiếp sang c hoặc a khi trạng thái của Q là c hoặc a, có hai trường hợp khác có thể xảy ra:

  1. Trường hợp 9.1: nếu tất cả các participant mà P liên lạc đều ở trạng thái p thì transaction có thể được commit. Trong trường hợp có một participant Q nào đó cũng bị crash và khôi phục lại sau đó. Trạng thái của Q chỉ có thể là w, p hoặc c.
    • Trường hợp 9.1a: nếu là w thì Q sẽ tiếp tục đi hỏi các participant khác.
    • Trường hợp 9.1b: nếu là p hoặc c thì P có thể commit transaction.
  2. Trường hợp 9.2: nếu tất cả các participant mà P liên lạc đều ở trạng thái w thì transaction có thể bị abort. Trong trường hợp có một participant Q nào đó cũng bị crash và khôi phục lại sau đó:
    • Trường hợp 9.2a: nếu trạng thái của Q là q thì abort transaction là đúng đắn. Lý do là vì sau timeout, Q sẽ chuyển sang a và khi P liên lạc đến Q thì trạng thái của nó cũng sẽ chuyển sang a.
    • Trường hợp 9.2b: nếu trạng thái của Q là p thì việc abort transaction (thay vì commit như trường hợp 9.1) sẽ không gây ảnh hưởng tiêu cực đến giao thức 🤔.

Advantages Over 2PC

Xét trường hợp 3, khi đa số các site đang ở trạng thái w và có một site S bị crash rồi sau đó khôi phục lại trạng thái c/a. Đối với 2PC, các site đang hoạt động và ở trạng thái w sẽ không thể đưa ra quyết định cuối cùng khi site S đang bị crash. Các site đó cần phải chờ site S khôi phục lại (blocking) và quyết định trạng thái tiếp theo của chúng từ trạng thái của site S.

Tuy nhiên, đối với 3PC, nếu có bất kỳ site nào đang hoạt động ở trạng thái w thì site S bị crash chỉ có thể khôi phục lại trạng thái q, a hoặc p chứ không thể là c. Bằng cách này, các site đang hoạt động luôn có thể đưa ra quyết định cuối cùng cho trạng thái của chúng (luôn là abort) mà không cần chờ site S khôi phục. Xét trường hợp có đa số các site ở trạng thái w và site S khôi phục lại các trạng thái sau:

  • q: abort transaction (trường hợp 9.2a).
  • a: abort transaction (site S abort, các site khác khi liên lạc đến cũng sẽ chuyển sang abort - trường hợp 3).
  • p: abort transaction (trường hợp 9.2b).

Resources

Backlinks