RESTful Transactions

I was reading recently in RESTful Web Services (Leonard Richardson & Sam Ruby, O’Reilly, 2007) about how to implement transactional behavior in a RESTful web service. Most web services today do this with an overloaded POST operation, but the authors assert that this isn’t necessary.

Their example (in Chapter Eight) uses the classic bank account transaction scenario, where a customer wants to transfer 50 dollars from checking to savings. I’ll recap here for your benefit. Both accounts start with 200 dollars. So after a successful transaction, the checking account should contain 150 dollars and the savings account should contain 250 dollars. Let’s consider what happens when two clients operate on the same resources:

Client A -> Read account: 200 dollars
Client A -> Withdraw 50 dollars: 200 - 50 = 150 dollars
Client A -> Write account: 150 dollars

Client B -> Read account: 150 dollars
Client B -> Withdraw 50 dollars: 150 - 50 = 100 dollars
Client B -> Write account: 100 dollars

This is all well and good until you consider that the steps in these operations might not be atomic. Transactions protect against the following situation, wherein the separate steps of these two Clients’ operations are interleaved:

Client A -> Read account: 200 dollars
Client B -> Read account: 200 dollars
Client A -> Withdraw 50 dollars: 200 - 50 = 150 dollars
Client B -> Withdraw 50 dollars: 200 - 50 = 150 dollars
Client A -> Write account: 150 dollars
Client B -> Write account: 150 dollars

After both operations, the account should contain 100 dollars, but because no account locking was in effect during the two updates, the second withdrawal is lost. Thus 100 dollars was physically removed from the account, but the account balance reflects only a 50 dollar withdrawal. Transaction semantics would cause the following series of steps to occur:

Client A -> Begin transaction
Client A -> Read account: 200 dollars
Client B -> Begin Transaction (block)
Client A -> Withdraw 50 dollars: 200 - 50 = 150 dollars
Client A -> Write account: 150 dollars
Client A -> Commit transaction
Client B -> (unblock) Read account: 150 dollars
Client B -> Withdraw 50 dollars: 150 - 50 = 100 dollars
Client B -> Write account: 100 dollars
Client B -> Commit transaction

Web Transactions

The authors’ approach to RESTful web service transactions involves using POST against a “transaction factory” URL. In this case /transactions/account-transfer represents the transaction factory. The checking account is represented by /accounts/checking/11 and the savings account by /accounts/savings/55.

Now, if you recall from my October 2008 post, PUT or POST: The REST of the Story, POST is designed to be used to create new resources whose URL is not known in advance, whereas PUT is designed to update or create a resource at a specific URL. Thus, POSTing against a transaction factory should create a new transaction and return its URL in the Location response header.

A user might make the following series of web requests:

GET /transaction/account-transfer/11a5/accounts/checking/11 HTTP/1.1
Host: example.com
...
200 Ok

balance=200
---
GET /transaction/account-transfer/11a5/accounts/savings/55 HTTP/1.1
Host: example.com
...
200 Ok

balance=200

The fact that the client reads the account balances before beginning is implied by the text, rather than stated explicitly. At some later time (hopefully not much later) the transaction is started:

POST /transaction/account-transfer HTTP/1.1
Host: example.com
...
201 Created
Location: /transaction/account-transfer/11a5
---
PUT /transaction/account-transfer/11a5/accounts/checking/11 HTTP/1.1
Host: example.com

balance=150
...
200 Ok
---
PUT /transaction/account-transfer/11a5/accounts/savings/55 HTTP/1.1
Host: example.com

balance=250
...
200 Ok
---
PUT /transaction/account-transfer/11a5 HTTP/1.1
Host: example.com

committed=true
...
200 Ok

At first glance, this appears to be a nice design, until you begin to consider the way such a system might be implemented on the back end. The authors elaborate on one approach. They state that documents PUT to resources within the transaction might be serialized during building of the transaction. When the transaction is committed the entire set of serialized operations could then be executed by the server within a server-side database transaction. The result of committing the transaction is then returned to the client as the result of the client’s commit on the web transaction.

However, this can’t work properly, as the server would have to have the client’s view of the original account balances in order to ensure that no changes had slipped in after the client had read the accounts, but before the transaction was committed (or even begun!). As it stands, changes could be made by a third-party to the accounts before the new balances are written and there’s no way for the server to ensure that these other modifications are not overwritten by outdated state provided by the transaction log. It is, after all, the entire purpose of a transaction to protect a database against this very scenario.

Fixing the Problem

One way to make this work is to include account balance read (GET) operations within the transaction, like this:

POST /transaction/account-transfer HTTP/1.1
Host: example.com
...
201 Created
Location: /transaction/account-transfer/11a5
---
GET /transaction/account-transfer/11a5/accounts/checking/11 HTTP/1.1
Host: example.com
...
200 Ok

balance=200
---
PUT /transaction/account-transfer/11a5/accounts/checking/11 HTTP/1.1
Host: example.com

balance=150
...
200 Ok
---
GET /transaction/account-transfer/11a5/accounts/savings/55 HTTP/1.1
Host: example.com
...
200 Ok

balance=200
---
PUT /transaction/account-transfer/11a5/accounts/savings/55 HTTP/1.1
Host: example.com

balance=250
...
200 Ok
---
PUT /transaction/account-transfer/11a5 HTTP/1.1
Host: example.com

committed=true
...
200 Ok

The GET operations would, of course, return real data in real time. But the fact that the accounts were read within the transaction would give the server a reference point for later comparison during the execution of the back-end database transaction. If the values of either account balance are modified before the back-end transaction is begun, then the server would have to abort the transaction and the client would have to begin a new transaction.

This mechanism is similar in operation to lock-free data structure semantics. Lock-free data structures are found in low-level systems programming on symmetric multi-processing (SMP) hardware. A lock-free data structure allows multiple threads to make updates without the aid of concurrency locks such as mutexes and spinlocks. Essentially, the mechanism guarantees that an attempt to read, update and write a data value will either succeed or fail in a transactional manner. The implementation of such a system usually revolves around the concept of a machine-level test and set operation. The would-be modifier, reads the data element, updates the read copy, and then performs a conditional write, wherein the condition is that the value is the same as the originally read value. If the value is different, the operation is aborted and retried. Even under circumstances of high contention the update will likely eventually occur.

How this system applies to our web service transaction is simple: If the values of either account are modified outside of the web transaction before the back-end database transaction is begun (at the time the commit=true document is PUT), then the server must abort the transaction (by returning “500 Internal server error” or something). The client must then retry the entire transaction again. This pattern must continue until the client is lucky enough to make all of the modifications within the transaction that need to be made before anyone else touches any of the affected resources. This may sound nasty, but as we’ll see in a moment, the alternatives have less desirable effects.

Inline Transaction Processing

Another approach is to actually have the server begin a database transaction at the point where the transaction resource is created with the initial POST operation above. Again, the client must read the resources within the transaction. Now the server can guarantee atomicity — and data integrity.

As with the previous approach, this approach works whether the database uses global- or resource-level locking. All web transaction operations happen in real time within a database transaction, so reads return real data and writes happen during the write requests, but of course the writes aren’t visible to other readers until the transaction is committed.

A common problem with this approach is that the database transaction is now exposed as a “wire request”, which means that a transaction can be left outstanding by a client that dies in the middle of the operation. Such transactions have to be aborted when the server notices the client is gone. Since HTTP is a stateless, connectionless protocol, it’s difficult for a server to tell when a client has died. At the very least, database transactions begun by web clients should be timed out. Unfortunately, while timing out a database transaction, no one else can write to the locked resources, which can be a real problem if the database uses global locking. Additional writers are blocked until the transaction is either committed or aborted. Locking a highly contended resource over a series of network requests can significantly impact scalability, as the time frame for a given lock has just gone through the ceiling.

It’s clear that creating proper RESTful transaction semantics is a tricky problem.

About these ads

23 comments on “RESTful Transactions

  1. Alezz says:

    Awesome! Thanks

  2. jsled says:

    “If you find yourself in need of a distributed transaction
    protocol, then how can you possibly say that your architecture
    is based on REST? I simply cannot see how you can get from one
    situation (of using RESTful application state on the client and
    hypermedia to determine all state transitions) to the next
    situation of needing distributed agreement of transaction semantics
    wherein the client has to tell the server how to manage its own
    resources.” — Roy Fielding, rest-discuss, 2009-06-09

    How about

    that the server is exclusively responsible for handling in a transactional manner. Or not. The client simply doesn’t know such things.

    You can try to come up with a way to shoehorn multiple HTTP requests into a transactional scope, but such a thing is not REST.

  3. jsled says:

    [Gah, stupid comment system ate my example. That should read…]

    How about:

    [form type="account-transfer" method="POST" action="account-transfer"]
    [select name="creditAccount"]
    [option value="/accounts/assets/bank"/]
    [options…]
    [/select]
    [select name="debitAccount"]
    […options…]
    [/select]
    [input type="currency" name="amount"/]
    [/form]

    • Mike H says:

      Yes, I agree. This example seems to be best implemented in one of two ways.

      1. An “account-change” resource, which takes the account and the amount to increment/decrement.

      or

      2. An “account-transfer” resource, which takes the source and destination accounts and the amount to transfer.

      • John Calcote says:

        @mike h: You must be very careful that you follow proper web semantics – that is, that you honor the properties of each of the verbs – PUT and POST. First, your account-change resource is a transaction resource in my post. Second, you can’t use any sort of increment/decrement operator safely. Remember that the web is connectionless, which means that you can’t guarantee that a server will get your request. The only way to know the server has received it is to get a response code – 200, 201, etc. But if the server’s response is lost, you have no way of knowing whether or not the requested action was taken by the server. If you make the request again – just to be sure, then you may end up subtracting 50 twice.

    • John Calcote says:

      @jsled: Well, there’s nothing really wrong with this method – it’s just not as RESTful as it could be – this is a classic example of overloaded POST. You’ve defined a new verb, so you’ve effectively extended the Web verb set. The first paragraph of this post indicates that it will be about *not* overloading POST.

      • jsled says:

        It’s as RESTful as your example. Even more so, as it’s actually using hypermedia. :)

        There’s no overloading of POST. The hypermedia describes the semantics of the “account-transfer” resource; the user-agent is simply creating a new resource, which is the POST operation. It’s the same in all 3 cases.

        BTW, there’s no reason that an /account-transfer/11a5/ resource can’t provide a “consistent-read” view of its subordinate accounts. In fact, the key window to close is the one between creating the transaction resource and GETting the balances to know what to PUT, which you only add as a parenthetical. As for another client changing the values while this transaction is going on … well, isn’t that the whole point? The server doesn’t have to honor the final “committed” PUT if it can’t do so.

        I wish, in (especially) the RWS book and your example there was hypermedia described. The client seems to know an awful lot about how the /account-transfer/11a5/{subordinate-account-resources} uris are constructed. How does the client know to POST /transaction/account-transfer/ in the first place? How does it know what the URLs are? How does it know it should PUT commited=true at the end? “Hypermedia as the engine of application state” is perhaps even a more important part of REST than the uniform interface.

        Ultimately, I guess, my point was: why do 6 operations when 1 will do? If the server is directing the client anyways, why not direct it to do something easy for the server to implement? I’d not want to create the server side that had to maintain those consistent-read views, waiting for some future PUT that might never come, when a single, simple POST would suffice.

        • John Calcote says:

          @jsled: Sorry it took so long for me to get back to you. I wanted to think about what you said before jumping in with a reply. I like your approach, and I think now I finally understand Roy’s comments regarding transactions (and quoted by you). It seems that the RWS example tries to do something that simply shouldn’t be done by providing a general purpose transaction model. Instead, it appears from your’s and Roy’s comments that the proper (and most RESTful) approach should be to keep it much closer to the application domain. That is, don’t try to be too general, but rather, just provide a resource that encapsulates the entire set of semantics required by the “transfer money from one account to the other” transaction. In doing this, you also make the service much more connected and linked, because the documents sent have much more inherent knowledge of the operation encapsulated by this transaction than a more general transaction would.

          Thank you very much for your input jsled – you may also wish to read and comment on the entry on this page by Alexandros. The link he provides takes you to his thesis work at university in the UK. I’m sure he would appreciate your insights on Roy’s take on general transaction handing over a RESTful interface. He’s trying to design a general-purpose transaction system that’s RESTful, and I think he’s missing a key element regarding server-managed application state. I think he’s done very well on hypermedia and connectedness issues.

          Again – thank you for your input. You’ve helped me (and other readers, hopefully) understand better, and that’s why I do this. :)

  4. [...] Calcote in RESTful Transactions: It’s clear that creating proper RESTful transaction semantics is a tricky [...]

  5. Alexandros says:

    Hi John, I and some collaborators starting from the examples of the O’Reilly book have tried to materialise a complete transaction model, as a thought experinent to see if REST and ACID can co-exist. I think we have addressed some of your concerns and I would love to hear your opinion on it.

    You can find it here: http://bit.ly/resttrans

  6. chris says:

    hi,

    actually, why is the client doing any calculations?
    client should read the account balance.
    then make a POST to the transaction.
    the new account balance could be part of the response,
    or the client has to GET the account balance again.

  7. John Calcote says:

    @chris: My example was simplified. For instance, chances are very good that any document representing an account is going to contain significantly more than just the current balance, unless the service provides a URL that accesses just the balance, such as /accounts/savings/55/balance. Recall also that a transaction is a self-contained unit that has nothing to do with the original accounts…until it’s committed. So are you saying that the commit request on the transaction would return new balances for both accounts? This is a good optimization, and one that I might recommend. However, I would also add that it’s not really RESTful. A RESTful implementation might return a document, but that document would only contain links to the accounts modified within the transaction, and since you already know those links, it wouldn’t really be that helpful.

  8. Thanks, great clear explanation !

  9. [...] RESTful Transactions I was reading recently in RESTful Web Services (Leonard Richardson & Sam Ruby, O’Reilly, 2007) about how to [...] [...]

  10. At JBoss we implemented your final approach which works quite well for clients that want classic ACID transactions. The problem you cite (that of holding locks for extended periods of time) is common to all implementations that guarantee ACID behavior.

    Consequently we proposed an alternative implementation (called Compensating RESTful transactions) in which all actions are required to be compensatable. It is then up to the system designer to decide which model or which mixture of the two approaches suits his particular constraints. There is a write up of both approaches on the web (type jboss restful transactions into your search bar).

    The Retro stuff looks interesting too, although it wasn’t clear how the recovery works.

  11. [...] RESTful design patterns have been around for a while. Here’s how you might deal with RESTful transactions. [...]

  12. jay says:

    Good thoughts, but I found is distracting that examples differed from the problem as stated in text, i.e. the results should have been two accounts one at 250 and one at 150, not one account with two $50 deductions.

    Just something to consider when trying to develop examples.

  13. Adib Saikali says:

    You can also version the accounts like this.

    GET /accounts/chequing/11/latest
    REDIRECT: /account/chequing/11/12
    GET /account/chequing/11/12

    balance=500

    /account/chequing/11/12 is a url of the form /account/chequing/11/{versionNo}

    REQUEST: GET /account/savings/14/latest
    REDIRECT /account/saving/14/77
    GET /account/saving/14/77

    balance=5000

    POST /transactions/

    /account/savings/14/77
    /account/chequing/11/12
    400

    201 CREATED
    Location: /transactions/888

    GET /transactions/888

    /account/savings/14/77
    /account/chequing/11/12
    400

    4600
    900

    You can now do GET/

    Some Scenarios:

    1) If there POST is posted more than once then the version
    mismatch will be detected and the server can redirect
    the client to another URI such as /transaction/versionMismatch which has an error message saying
    the versions did not match

    2) If the any of the accounts changed since I got the
    acctual representation of the latest version version
    mistmatch occurs and the tx fails

    I have not thought of all the edge cases and if this could work, but this is very similar to how hibernate
    does optimistic locking, I think it can probably be
    made to work.

  14. Adib Saikali says:

    Opps my XML tags around the request and response for a tx post got eaten up by the blog engine, ah I guess you need to view source to see them.

  15. Adib Saikali says:

    trying again with square brackets so the blog does not eat
    up the XML tags, replace all [] with angle brackets
    below.

    You can also version the accounts like this.

    GET /accounts/chequing/11/latest
    REDIRECT: /account/chequing/11/12
    GET /account/chequing/11/12

    balance=500

    /account/chequing/11/12 is a url of the form /account/chequing/11/[versionNo]

    REQUEST: GET /account/savings/14/latest
    REDIRECT /account/saving/14/77
    GET /account/saving/14/77

    balance=5000

    POST /transactions/

    [from]/account/savings/14/77[/from]
    [to]/account/chequing/11/12[/to]
    [amount]400[/amount]
    [/transfer]

    201 CREATED
    Location: /transactions/888

    You can now do

    GET /transactions/888
    [transaction]
    [transfer]
    [from]/account/savings/14/77[/from]
    [to]/account/chequing/11/12[/to]
    [amount]400[/amount]
    [/transfer]
    [result]
    [from id="/account/savings/14/78"]4600[/from]
    [to id="/account/savings/11/13"]9000[/from]
    [/result]
    [/transaction]

    Some Scenarios:

    1) If there POST is posted more than once then the version
    mismatch will be detected and the server can redirect
    the client to another URI such as /transaction/versionMismatch which has an error message saying
    the versions did not match

    2) If the any of the accounts changed since I got the
    acctual representation of the latest version version
    mistmatch occurs and the tx fails

    I have not thought of all the edge cases and if this could work, but this is very similar to how hibernate
    does optimistic locking, I think it can probably be
    made to work.

  16. Hi,

    We are working on a REST API for the server-side of a graphical modeling platform. Our resources – models, diagrams and elements – are hierarchical by nature and our server keeps track of revisions of these models.

    The platform allows users to work on the same models simultaneous. Concurrency is realized using a git-inspired strategy; when a user starts working, he starts working on a new revision that is not yet shared with others. The unshared update a user is working on, does reside on the server, so the user can close his session and continue later wihout having to share his changes.

    As a user’s work evolves, the system claims the resources he touches, making sure he can effectuate his changes at a later point in time. This pessimistic approach appears to fit our customers the best. Of course claims have a time-out to avoid dead-lock and/or starvation.

    To expose the functions that we support in a RESTful way, we came up with a two-phase-commit-pattern we like to refer to as the ‘framing the future’-pattern: A user can frame a resource by posting a frame to it, create or update child resources by posting these to the frame instead of the resource and have these changes take affect somewhere in the future:

    We use Frames, Catches and Patches as a means to let clients transfer preliminary state as if it were final state, with the guarantee that this state can be finalized later. The terminolgy should be understood as follows: A Frame represents a snapshot view on your resource, a Catch refreshes your snapshot and a Patch effectuates your changes to it. Frames present resources as if your are the only one changing them, without actually putting your changes to effect. So you don’t bother others with your changes and others don’t bother you with theirs… Yet. Because you can choose to catch up with patches others made by posting a Catch. And if you would choose to post a Patch, others may in turn post a Catch to catch up with your changes.

    From within a Frame you see exactly the same resources as from outside a Frame, at least for the time you don’t do any (preliminary) updates from within that Frame and as long as nobody else effectuates any updates. When you do update resources from within your Frame, these resources only reflect your changes within that Frame; from outside your Frame these resources will show as before. One could say a Frame provides you with a view on your resources as if your changes have actually taken place and as if changes someone else made after you created your Frame have not been effectuated yet.

    Only when you post a Catch to your Frame, it will reflect changes that were finalized from outside your Frame and only when you post a Patch to your Frame, your changes will in turn be effectuated. After posting a Patch, all resources will reflect your changes, both from within your Frame and from outside your Frame; only other Frames won’t show your changes as long as these don’t get refreshed. From this point on you can keep on using your Frame to make new changes. These changes will be treated like before you posted your first Patch; you will need to post another Patch to finalize these new changes.

    A Frame provides certainty when it comes to finalizing your changes, but only to a certain extend. A Frame comes with a time-out; when the Frame expires it won’t accept any postings anymore, which means you will loose your changes after your last Patch. After each Patch, a Frame’s expiration date will be reset. As long as a Frame does not expire, it will use a pessimistic claiming strategy to ensure you can finalize your changes later. As a consequence, updates you make from within a Frame, may bounce as resources may already be claimed by other users from within their Frames.

    All can be illustrated using the following scenario with two users that add an element to the same diagram of a model in parallel:

    // before posting a frame User 1 sees a single element in diagram 1 of model 1
    // after posting a new element within his frame, the diagram shows elements 1 and 2
    User 1 GET @ /models/1/diagrams/1/elements -> [element 1]
    User 1 POST frame @ /models/1/frames -> frame 1
    User 1 POST element @ /models/1/frames/1/diagrams/1/elements -> element 2
    User 1 GET @ /models/1/frames/1/diagrams/1/elements -> [element 1, element 2]

    // as the updates of User 1 are preliminary, User 2 also sees only one element
    // after posting a new element within his frame, the diagram shows elements 1 and 3
    User 2 GET @ /models/1/diagrams/1/elements -> [element 1]
    User 2 POST frame @ /models/1/frames -> frame 2
    User 2 POST element @ /models/1/frames/2/diagrams/1/elements -> element 3
    User 2 GET @ /models/1/frames/2/diagrams/1/elements -> [element 1, element 3]
    User 2 POST patch @ /models/1/frames/2/patches -> patch 1
    User 2 DELETE @ /models/1/frames/2

    // even though User 2 posted a patch, User 1 still only sees elements 1 and 2
    // however, after posting a catch, frame 1 does reflect the changes of User 2
    User 1 GET @ /models/1/frames/1/diagrams/1/elements -> [element 1, element 2]
    User 1 POST catch @ /models/1/frames/1/catches -> catch 1
    User 1 GET @ /models/1/frames/1/diagrams/1/elements -> [element 1, element 2, element 3]
    User 1 POST patch @ /models/1/frames/1/patches -> patch 1
    User 1 DELETE @ /models/1/frames/1

    // now that both users shared their updates by posting a patch to their frame
    // the actual resource reflects all the updates and show the same to all users
    User 1 GET @ /models/1/diagrams/1/elements -> [element 1, element 2, element 3]
    User 2 GET @ /models/1/diagrams/1/elements -> [element 1, element 2, element 3]

    I’m curious what other’s think about this approach, so please share your thoughts on this pattern.

    Regards,
    Diederik van Leeuwen

  17. Toby Ovod-Everett says:

    Something to consider. IMHO, in any banking application worth it’s salt (and I do hope they are salting their passwords), account balances are simply persistent caches to improve performance!

    That’s a very important point, and I think it bears repeating. There has to be an audit trail – there has to be a list of every action that occurred to the account. And thus the balance (how much is in the account) should be calculable by simply summing the results of the records of those actions. It’s just that doing that query repeatedly creates performance issues, and so we cache the result.

    As such, balance transfers are nouns, not verbs! One doesn’t “transfer money”. One “creates a record of a balance transfer”.

    In fact, all state-change verbs can be recast as “create a record of this state-change” – whether or not the application chooses to persist that record is up to the application.

Comments are closed.