19.4 Commit Protocols

Topic: 19.4 Commit Protocols

• Goal: Ensure atomicity in distributed transactions. Either all sites involved commit or all sites abort.
• Challenge: Site or communication failures can lead to inconsistencies.

Subtopic: 19.4.1 Two-Phase Commit (2PC)

• Concept: A widely used protocol with a coordinator and participants (sites involved in the transaction).
• Phases:
  1. Prepare Phase:
     • Coordinator sends prepare T message to all participants.
     • Participants vote ready T (if able to commit) or abort T (if unable to commit).
     • Participants force-write the prepare/abort/ready log records before sending the vote.
  2. Commit/Abort Phase:
     • If all participants vote ready T, the coordinator decides commit T and sends it to all.
     • If any participant votes abort T or times out, the coordinator decides abort T and sends it to all.
     • Participants force-write commit/abort log records.
     • Participants acknowledge the commit/abort message.
     • Coordinator writes complete T record after receiving all acknowledgements.
• Handling Failures:
  • Participant Failure:
    • If a participant fails before sending ready T, it’s treated as if it voted abort T.
    • If a participant fails after voting ready T, it must consult the coordinator upon recovery to determine the outcome (commit or abort) of the transaction. It will query other sites if coordinator is not available.
    • If a participant’s log has no information on T, it means it failed before receiving prepare T. Hence, it can abort T unilaterally.
  • Coordinator Failure:
    • If the coordinator fails before sending prepare T, the transaction is effectively aborted.
    • If the coordinator fails during the commit phase, participants might be blocked, waiting for the coordinator to recover. They can query each other about the status.
      • If any site has a commit T record, then commit T
      • If any site has an abort T record, then abort T
      • If any site has no ready T record, then abort T
      • If all sites have ready T but no further information, they have to wait for the coordinator’s recovery. This is the blocking problem.
• Recovery: Upon recovery, a site inspects its log to find transactions that were in progress during the failure and takes appropriate actions (redo/undo) based on the 2PC protocol.
• Concurrency Control:
  • Locks acquired by a transaction must be held until it either commits or aborts.
  • To avoid blocking during recovery, lock information can also be added to the log. After a site recovers, it reacquires the locks of all in-doubt transactions before proceeding.

Subtopic: 19.4.2 Three-Phase Commit (3PC)

• Goal: Reduce blocking in 2PC (under certain assumptions).
• Assumptions: No network partitions, limited site failures (at most k).
• Key Idea: Introduce a pre-commit phase between prepare and commit.

Phases:

1. Prepare: Same as 2PC. Coordinator asks for votes (prepare T), participants vote ready T or abort T.
2. Pre-commit: If all vote ready T, the coordinator sends precommit T (after force-writing precommit T). Participants acknowledge (after force-writing precommit T).
3. Commit/Abort: If coordinator gets all precommit T acknowledgements, it sends commit T. Timeout leads to abort T at the coordinator. If a participant times out in the ready T state, it contacts others. If any site has abort T or no information, it aborts. If all are in ready T, they elect a new coordinator that runs a termination protocol.

Termination Protocol:

• If any site has commit T, the new coordinator decides commit T.
• If any site has abort T, the new coordinator decides abort T.
• If no site has commit T or abort T, but at least one site has precommit T, the new coordinator issues commit T.
• If no site has abort T or precommit T (all are in ready T if they voted), the new coordinator issues abort T.

Advantages:

• Reduces blocking: If any operational site committed, no operational site can abort, and vice-versa.

Disadvantages:

• More complex, higher overhead than 2PC.
• Doesn’t eliminate blocking with network partitions or more than k failures.
• Not widely used in practice.

Subtopic: 19.4.3 Alternative Models of Transaction Processing

Motivation:

• Limitations of 2PC: The Two-Phase Commit (2PC) protocol, while ensuring atomicity in distributed transactions, suffers from the blocking problem. If the coordinator fails, participants might be left in a state where they cannot unilaterally decide whether to commit or abort the transaction, potentially holding resources for an extended period.
• Strict ACID Properties Not Always Necessary: For some applications, especially in large-scale distributed systems and Web applications, strict ACID (Atomicity, Consistency, Isolation, Durability) properties might be too expensive or restrictive. Availability and performance might be prioritized over strong consistency.
• Need for Different Models: These limitations motivate the need for alternative models of transaction processing that can provide better availability and scalability, even if it means relaxing some of the traditional ACID guarantees.

Key Concepts:

• Moving Away from Distributed Transactions: Instead of a single, atomic transaction spanning multiple sites, these models break down the work into smaller, independent units of work at each site.
• Asynchronous Communication: Sites often communicate asynchronously, meaning they don’t need to be simultaneously involved in a transaction’s execution.
• Relaxed Consistency: These models often relax the strict consistency guarantees of ACID transactions in favor of eventual consistency or other weaker forms of consistency.
• Application-Level Handling of Failures: The application logic plays a more significant role in handling failures and ensuring data consistency, as opposed to relying solely on the database system’s transaction manager.

Two Main Alternative Models:

1. Persistent Messaging:

   • Concept: Sites communicate by sending messages that are guaranteed to be delivered reliably.
   • Mechanism:
     • A transaction at one site, instead of directly updating data at another site, creates a message containing the requested operation (e.g., “transfer $100 from account X to account Y”).
     • The message is stored persistently (e.g., in a database table messages_to_send).
     • A separate message delivery process monitors the table, retrieves messages, and sends them to the destination site.
     • The message is deleted from the table only after an acknowledgement is received, ensuring that it is delivered exactly once if the sending transaction commits. If the transaction aborts, the message is not sent.
     • The receiving site, upon receiving a message, processes it (e.g., performs the requested update). It also records the received messages (e.g., in a received_messages table) to detect and discard duplicates.
     • The message is acknowledged back to the sender. The sender keeps resending the message periodically until acknowledged.
   • Guarantees:
     • Exactly-once delivery: If the sender transaction commits, the message is guaranteed to be delivered exactly once to the destination, even in the presence of failures.
     • No delivery on abort: If the sender transaction aborts, the message is not delivered.
   • Advantages:
     • Avoids blocking: Sites can operate independently without waiting for the coordinator or other sites.
     • Improved availability: The system can continue to make progress even if some sites are unavailable.
   • Disadvantages:
     • Weaker consistency: Data might be temporarily inconsistent across sites.
     • Application-level complexity: The application needs to handle message delivery failures and implement logic to ensure consistency (e.g., using compensating actions). For instance, if a message requests a fund transfer to a closed account, the application needs to define how to handle this error and potentially reverse the debit at the sender.
     • Received messages are usually never deleted, but to prevent the received_messages table from growing indefinitely, messages can be given timestamps and the older messages can be discarded.

2. Workflows:

   • Concept: A higher-level model for managing complex, long-running processes that involve multiple steps, potentially across different systems or organizations, and often with human interaction.
   • Characteristics:
     • Decomposition into steps: Workflows are broken down into a sequence of steps or activities.
     • Long-running: Workflows can span extended periods (hours, days, or even longer).
     • Heterogeneous environments: Steps might involve different systems, databases, or even manual tasks.
     • Asynchronous execution: Steps are often executed asynchronously.
     • State management: The workflow management system tracks the state of each workflow instance (which steps have been completed, which are pending, etc.).
   • Example:
     • Loan application process: A workflow might involve steps like:
       1. Customer submits application (online form).
       2. System performs automated credit check.
       3. If credit check fails, reject application.
       4. If credit check passes, assign loan officer.
       5. Loan officer reviews application and supporting documents.
       6. Loan officer approves or rejects the loan.
       7. If approved, generate loan documents and disburse funds.
   • Relationship to Databases:
     • Workflows often interact with databases to store and retrieve data needed for each step.
     • The workflow management system itself might use a database to store the state and history of workflow instances.
   • Benefits:
     • Automation of complex processes: Workflows can automate complex business processes, reducing manual effort and errors.
     • Improved coordination: They provide a framework for coordinating activities across different systems and organizations.
     • Flexibility and adaptability: Workflows can be adapted to changing business needs.
     • Visibility and monitoring: Workflow management systems provide tools for monitoring the progress of workflows and identifying bottlenecks.

Key Differences from Traditional Transactions:

Feature	Traditional Transactions (ACID)	Persistent Messaging	Workflows
Scope	Typically short, atomic units of work	Asynchronous communication between independent transactions	Long-running, multi-step processes
Atomicity	All or nothing	At the level of individual messages (exactly-once delivery)	Atomicity of individual steps, but not necessarily the entire workflow
Consistency	Strong consistency guarantees	Weaker, eventual consistency	Depends on the workflow definition and how steps are implemented
Isolation	Concurrent transactions are isolated	Limited isolation between message senders and receivers	Isolation between steps might be enforced, but not always strictly
Durability	Committed changes are permanent	Messages are persisted until delivered	Workflow state is typically persisted
Blocking	2PC can lead to blocking	Avoids blocking	Generally avoids blocking within the workflow execution
Complexity	Can be complex to implement in a distributed setting	Requires application-level handling of consistency	Requires a workflow management system and careful design
Communication	Synchronous	Asynchronous	Asynchronous