Wednesday, June 14, 2017

Sagas and how they differ from two-phase commit

With all the talk about microservices and distributed transactions in the community these days and in particular the use of the term Saga - it seems like a good time for a refresher on Sagas and how they differ from a 2PC transaction. As we know, transaction management is needed in a microservices architecture and Sagas can provide a good fit to addressing that need. There are several ways[9] to handle and implement Saga in such environment but the explanation of that topic is not the goal of this post.

This post instead introduces the concept of Saga transactions and compares it to ACID two-phase commit transactions. The two approaches having the same goal - coordinate resources while operations over them form one logical unit of work but taking quite different approaches to ensure that goal is met.

ACID

First, let’s refresh on the concept of an ACID transaction. ACID is defined as - atomicity, consistency, isolation and durability. These properties are provided by a system to guarantee that operations over multiple resources can be considered as a single logical operation (unit of work).
Let’s take it briefly one by one.
  • Atomicity signifies all or nothing. If one operation from the set fails then all others have to fail too. Looking from a different angle we can call the property abortability[1].
  • Consistency states that system is consistent before transaction starts and after it finishes. The definition of consistency varies from resource to resource. In database systems, we can consider it as not breaking any constraints defined by the primary key, foreign key, uniqueness etc. But being consistent in broader term is understood having the application in the consistent state. That is not maintained by the transactional system itself but by the application programmer. Of course, the transaction helps to defend it.
  • Isolation refers to the behaviour of concurrent operations. The ACID definition defines it as transactions being serializable - the system behaves like all transactions being processed in a single thread one by one. Such implementation is not required and it widely differs[2]. Besides such behaviour (even pretended) brings performance implications. It’s usual that isolation property is relaxed to comply with one of the isolation levels with the lower guarantee than serializability[3].
  • Durability means that if the transaction commits all data are persisted and even the system crashes it will be accessible after the restart.

Considering that definition of ACID transactions, now let’s consider about Saga and two-phase commit.

Two-phase commit (2PC)

A well-known algorithm to achieve ACID transaction outcomes is the two-phase commit protocol. 2PC (part of a family of consensus protocols) serves to coordinate the commit of a distributed transaction, i.e one that updates multiple resources. Those of you already familiar with Narayana will be well acquainted with a popular manifestation of this philosophy: JTA
As its name suggests, the protocol works in two phases. The first phase is named ‘prepare’ and the coordinator queries participants if they are ready to finish with the commit. The second phase is named ‘commit’ and coordinator commands participants to commit and made changes visible to the outer world. Coordinator commands to commit only if all participants voted for it. If some of the participant votes ‘abort’ then the whole transaction and all participants are rolled back. It means any change made to the participant during the transaction is aborted.

For a better understanding of the process see details at our wiki at https://developer.jboss.org/wiki/TwoPhaseCommit2PC.

Saga

The Saga[4] pattern, on the other hand, works with units of work that can be undone. There is no commitment protocol included.
The original paper discusses updates to single node database where such work is processed but the notion can be further applied to distributed transactions too.
A Saga consists of a sequence of operations, each could work with a resource. Changes made by the operation on the particular resource are visible to the outer world immediately. We can see it as a just group of operations (a.k.a local transactions) which are executed one by one group by the Saga.
A Saga guarantees that either all operations succeed or all the work is undone by compensating actions. The compensating actions are not generically provided by a coordinator framework, instead, they have undone actions defined in business logic by the application programmer.
The Saga paper talks about three ways of handling a failure:
  • Backward recovery - when a running operation fails then compensating action are executed for any previously finished operation. The compensation actions are executed in reverse order than the operations were run in.
  • Forward recovery - when the running operation is aborted but in the following step, it’s replayed to finish with success. The benefit is that forward progress is ensured and work is not wasted even when the failure occurs - the particular operation is aborted, replayed and Saga continues from that operation forward.
    You don’t need to specify any compensation logic but you can be trapped in an infinite retry loop. This recovery is defined as the pure forward recovery in the paper[4].
  • Forward/backward recovery - for sake of completeness the paper[4] defines the way of combining the forward and backward recovery. The application logic or the saga manager defines save-points. A savepoint declares a place in the Saga processing where operations can be safely retried from. When the running operation fails then compensation action is executed for previously finished operations up to the defined save-point. From there, operations are replied with a try for finishing the Saga successfully.
    We say that the forward recovery defines save-points after each of the successfully finished operation.
The undo actions for compensation and replay actions of forward recovery are expected to be idempotent for being possible to retry it multiple times. If there isn’t any special handling in underlying transport, such as retaining results, it is up to the application developer to code the handler an idempotent way. The saga manager then needs to be able to cope with the situation when Saga participant responses that the operation was already done.
The approach of forward recovery could be very handy [8] (the talk references this approach at time 28:20) but we focus more on compensations (backward recovery).

For better outlining the process let’s take an example. Let’s say we have a message queue where we want to send a message to and a database where we want to insert a record . If we want to group those operations we know each of them is represented by a local transaction. For purpose of this text we define a resource-located transaction as the counterpart of the local transaction which is transaction managed by the resource itself (i.e. database transaction or message broker transaction). Saga groups together business operations and defines compensating undo action for each of them. When business logic sends the message the local transaction is committed and immediately available in the queue. When data is inserted into the database table, the local transaction is committed and the value could be read. When both business operations succeed the Saga finishes.

Let’s try to elaborate a little bit
  1. First saga manager starts Saga
  2. The business logic sends a message to the JMS queue. This business operation is attached to Saga which brings obligation from to define a compensation handler (a chunk of code which is executed in case of Saga needs to be aborted).
    Sending of the message is wrapped into a short local transaction which ends when JMS message is acknowledged by the receiver.
  3. The business logic inserts a row into the database table - again, the operation is attached to Saga, the SQL insert command is covered by short local transaction and a compensation handler has to be defined to undo the insertion in case of abortion of the Saga
  4. If everything goes fine this is the end of the Saga and business logic can continue with another saga.
     

Let’s say a failure occurs during insertion a record to the database and we apply backward recovery.

  • As database insertion fails the ACID resource-located transaction reached an error state and has to be rolled-back by the resource. The error is returned to the Saga.
  • The saga manager is responsible for data integrity being preserved which is ensured by aborting the whole Saga which means executing compensating actions for previously completed business operations. The compensation action for database insertion is not needed as the local transaction has been already rolled-back. But compensation action of sent JMS message is waiting to be executed.
  • The compensating action is inevitably bound to the business context, thus we have to define at least a simple one.
    Let’s assume that sending of the JMS message meant placing an order in a warehouse system. Now the compensating action is expected to undo it. Probably the easiest way to model such cancellation is by sending a different message with cancel command to the JMS broker queue. We expect there is a system listening to messages which process the real order cancellation later on.

Sagas and ACID

We consider two-phase commit to being compliant with ACID. It provides atomicity - the all actions are committed or rolled-back, consistency - system is inconsistent state before transaction begins and after it ends, isolation - isolation provided by resource-located transactions (ie. locking in database) prevents the inconsistent isolation, we can say that except for heuristic, the data is as if serialized access was maintained. And of course, durability is ensured with transaction logs.

On the other hand, we consider Sagas to relax the isolation property. The outcome of each operation, each single resource-located transaction, is visible it ends. From other ACID properties the atomicity is preserved - the whole Saga either ends successfully or all the work is compensated, durability is preserved - all data is persisted at the end of the Saga, consistency - consistency mostly depends on the application programmer but at the end of the Saga the system state should be consistent. In fact, this is the same matter as for the 2PC.

In the case of two-phase commit the length of the resource-located transaction spans almost over the whole global transaction lifetime. Impact on the concurrency depends on implementation of the underlying system but as an example, in relational databases we can expect locks which restricts concurrent work over the same data (locks are acquired for records being work with, and depending on isolation level the lock could be acquired even for the whole table where record resides, despite this is simplified as many databases uses optimistic concurrency where locks are taken at prepare time).
On the other hand, a Saga commits the resource-located transactions immediately after each step in a business process ends. The time when locks are acquired is just that short. Business logic inserts data to the database table, immediately commits the resource-located transactions and locks are released. From this point of view, the Saga more readily facilitates concurrent processing.

Blending Sagas and ACID

One advantage of the two-phase commit approach is ease of use for the application programmer. It’s on the transaction manager to manage all the transaction troubleshooting. The programmer cares only for his business logic - sending a message to the queue, inserting data to the database. On the other hand, Sagas do require that a compensating action being created and such action has to be defined for any Saga in particular.

Saga is a good fit for long-lived transactions (LLT)[7] which are represented by the well-known example of booking a flight, a hotel and a taxi to the hotel in one transaction. We expect communication with third party systems over WebService or REST call. All such communication is “time-consuming” and using two-phase commit locking resources for the whole time of the transaction existence is not a good solution. Here the Saga is nice as it provides a more fine-grained approach to work with the transaction participants.

Some people have the impression that 2PC and Saga stand once against other. That’s truly not so. Each of them plays well its role and helps to solve particular use cases. Furthermore, 2PC transactions and Sagas can be deployed in such a manner as to benefit from both of their advantages.

The Saga (long running action) could define the top level work unit. ACID transactions are the good fit for being steps (operations) of such unit of work.


Where does Narayana fit in

As you might know, Narayana - the premier open source transaction manager - provides implementations of both of these transaction models, suitable for a wide variety of deployment environments.

Many of you are likely familiar most with our JTA 2PC implementation as used in JBoss EAP and the open source WildFly application server. That implementation is based on X/Open specification[12]. For more information, you can refer to the Narayana documentation[10].
In terms of compensations; if you want to stick to standards, you can already use Narayana to achieve saga based transaction using the Narayana WS-BA implementation. However, Narayana also provides a modern compensating transactions framework based on CDI. For more information please refer to a great article from Paul about the compensating framework[5] or visit our Narayana quickstarts[6].


References
[1] https://www.youtube.com/watch?v=5ZjhNTM8XU8 (Transactions: myths, surprises and opportunities, Martin Kleppmann)
[2] https://wiki.postgresql.org/wiki/SSI (Serializable Snapshot Isolation (SSI) in PostgreSQL)
[3] https://en.wikipedia.org/wiki/Isolation_(database_systems) (Wikipedia, Isolation - database systems)
[5] https://developer.jboss.org/wiki/CompensatingTransactionsWhenACIDIsTooMuch (Narayana: Compensating Transactions: When ACID is too much)
[6] https://github.com/jbosstm/quickstart/tree/master/compensating-transactions (Narayana quickstart to compensating transactions)
[8] https://www.youtube.com/watch?v=xDuwrtwYHu8 (GOTO 2015, Applying the Saga Pattern, Caitie McCaffrey)
[10] http://narayana.io/documentation/index.html (Narayana documentation)
[11] https://www.progress.com/tutorials/jdbc/understanding-jta (Understanding JTA - The Java Transaction API)
[12] http://pubs.opengroup.org/onlinepubs/009680699/toc.pdf (The XA Specification - The Open Group Publications Catalog)

1 comment:

mapa said...
This comment has been removed by a blog administrator.