Distributed transactions and scalability issues in large-scale distributed systems

Distributed transactions is the main evil of scalability

It is very hard to scale distributed transactions to an extremely high level, moreover they reduce throughput. Unlike a transaction on a local database, a distributed transaction involves altering data on multiple nodes. It can be a database + JMS broker or just a set of different databases. As an example let’s recall a classical 2-phase commit (2PC later) – a type of atomic commitment protocol in a back-end service with high volume of transactions. This protocol provides ACID-like properties for global transaction processing. I won’t go into details how it works under the hood, I’ll just tell you that C (Consistency) from ACID is the main evil of  scalability in distributed systems. It puts a great burden due to its complex coordination algorithm.  Overall throughput can drop up to a few times. Locks in all of the data sources are being held during 2PC. The longer duration locks create the risk of higher contention. The 2PC coordinator also represents a Single Point of Failure, which is unacceptable for critical systems.  For systems that have reasonably high volume of messages, or sensitive SLAs, it’s worth giving up strong consistency for throughput.

But how can I live without distributed transactions to achieve higher scalability?

Algorithms such as 2PC use “Exactly Once” technique whereas we will use “At least Once” technique. The difference is that a developer should take care of that in his application code to cope with it. Most queueing technologies provide acknowledgements that a message has been accepted (handling is a separate deal). Databases use local transactions. We can deal with downstream failures without coordination. Read on!

Idempotence and fault tolerance

From math, idempotence is as simple as that:

idempotence

That is, the result stays the same, no matter how many times a function gets called on the same argument. In distributed world Idempotence implies that an operation can be invoked repeatedly without changing the result. Why do I need one? Because we should somehow resolve processing duplicate requests in case of a system failure. Let’s make it clear by considering an example. A client-appliction sends a financial transaction to a server (there might be a cluster of them load-balanced or just one) and waits for acknowledgment. For some reason, at this particular time:

  • A server goes down or
  • Client goes down or
  • Network failure happens

In all of these 3 cases, a client-app didn’t get an acknowledgment message (reply) from the server about a transaction status. Of course, the client then should retry this transaction. The server must ensure that this financial transaction is accomplished “At least Once”. Here comes to the rescue idempotence. The server must remember a state – that a transaction with this Id has already been processed including saved acknowledgement message in order to check that it exists and reply with its acknowledgement message in case it does. We don’t have expensive distributed transactions anymore – “At least Once” is a more relaxed and scalable approach. That is, instead of locking resources everywhere, we can assume that messages will arrive at least once.

Optimistic locking

Even though this technique is quite old, one goes well with idempotence. If two people are trying to affect change to the same entity at the same time we don’t lock database records, rather we use a concept of versioning and optionally uniqueness. The idea is to save a version of each entity record in the database but to make sure before saving it wasn’t changed. A simple example is a self-service kiosk where people check-in before boarding at the airport. They can select a vacant seat from the seat map.

seatmap

Each seat has a version = 1. When multiple people make their choice in parallel before proceeding the system simply checks if a seat-version hasn’t changed. If it has a user is notified that the seat already been taken while she was thinking. This is a very simple example where version either can be 1 or 2. A more difficult situation could be in order-management systems where an order might have many versions but that doesn’t change the point how optimistic locking works.  The idea again yields great trade-off in terms of speed because we don’t use locking-mechanism.

Local atomic transactions and unique constraints

Local atomic transactions are usually restricted to a single store. Local transactions are primarily needed to apply a set of operations atomically to a single resource (e.g. relational database) as well as ensure correct ordering of operations within a transaction. In some cases, we can do away with transactions, particularly if we don’t care about the order of operations within a transaction. In that case we can process operations asynchronously leading to a better throughput again. Sometimes, a model requiring the order can be redesigned for  asynchronicity of operations.

Putting it all together

In order to achieve greater throughput a system should correspond to the following principles:

  1. You can retry the operation if there is a failure down the stream based on idempotence.
  2. Don’t use transactions and use optimistic locking if possible – it’s much cheaper.
  3. Local transactions based on a single phase commit for each resource are more scalable than distributed ones increasing overall application availability.
  4. Messages may be reordered.

Wrapping up

Such great systems as Google’s Bigtable or Spanner don’t support traditional ACID transactions because they have a heavy overhead on a highly distributed data storage model. I was lucky to use all above techniques in my applications too involving mission-critical financial transactions and must say that a few years ago not so many people knew about the techniques but now I can hear about them more and more often. Oh yeah, I almost forgot! I urge you to read this great article written by Pat Helland that has even more use-cases. I bumped at it during my research to know more. And remember, you can live without distributed transactions if you implement idempotence and downstream failures correctly.

References

1. Your Coffee Shop Doesn’t Use Two-Phase Commit by Gregor Hohpe.

2. Idempotence Is Not a Medical Condition by Pat Helland.

3. 2PC or not 2PC, Wherefore Art Thou XA? by Dan Pritchett.

4. Life beyond Distributed Transactions: an Apostate’s Opinion by Pat Helland.

Advertisements

One thought on “Distributed transactions and scalability issues in large-scale distributed systems

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s