RETRO: A (hopefully) RESTful Transaction Model

Comment on and Discuss RETRO here

This document discusses RETRO, work in progress by myself (Alexandros Marinos), my collaborators Amir Razavi, Sotiris Moschoyiannis, and our supervisor, Prof. Paul Krause, at the Department of Computing, University of Surrey in the United Kingdom. I can be contacted at a.marinos@surrey.ac.uk 

Introduction

Within the EU-FP6 OPAALS project [6] and Digital Ecosystems [7, 13] research in general, there is a need for a transaction model to help disparate service providers in a distributed system coordinate and compose into unforeseen, higher value services, forming an evolving digital ecosystem for business and community activities. In this, we have found REST an ideal complement, as the following quote indicates:

“A lot of people think of systems as static things. Dead things. REST is not going to appeal to those people. All of its constraints are designed to keep systems living longer than we are willing
or able to anticipate.” – Roy Fielding [5]

We therefore have started research efforts in the direction of enabling RESTful transactions to take place over the web. However the topic of transactions in combination with REST is a difficult one to breach. This is in part because of the association of distributed transactions with the WS-* set of specifications, as well as the lack of a clear justification for the need of such capabilities. In our research so far, we have found that the RESTful approach significantly simplifies the transaction model compared to an RPC-based approach, simultaneously making it more powerful. The next section attempts to explain the need for transactions in a distributed system such as the web.

Why do we need RESTful Transactions?

A common conception among the REST community is that if transactional needs arise, a resource should have been defined, the updating or creation of which will cause the desired modifications to the resources the transaction would have needed to modify. So in the case of transferring funds from one bank account to another, a solution would be for a new transferRequests collection to be created by the designers of the system that transferRequest resource representations are POSTed to. Each transferRequest representation would link to the source and destination account URIs, and also contain the amount to be transferred. This paradigm in its strict interpretation, however suitable for a range of problems, cannot cover all needs for transactional interactions in a distributed system.

In the common case of the shopping cart, a buyer adds items to a virtual shopping cart. The purchase of the group of items is then processed on checkout. In RESTful terms, the shopping cart and the items in it are expected to be identified as resources by a URI. The processing and purchase of the items in the shopping cart is then transactional as the semantics of ‘purchase these 4 items’ imply atomicity, being distinct and stricter than the non-atomic ‘buy as many of these items as possible’. In the case where these items are all necessary for a common purpose (e.g. a DIY project or cooking based on a recipe), best-effort is not enough as missing one item is enough to render the purchase useless to the buyer. Taking the shopping cart metaphor a step further, in a physical store, an item added to a physical shopping cart is not available for anyone else to purchase in the interval between placing the item in the shopping cart and checking out at the cashiers. These semantics may not be practical for every online store, but in situations of high-value, limited availability, highly specific items (such as seats in a flight) and trusted buyers (such as travel agents), they may make sense or even be necessary. This implies a need for a locking mechanism to ‘mark’ the items as being considered for purchase by a buyer, and therefore not available to other buyers, at least for the moment. As we elaborate the shopping cart model, we see it gradually becoming an ad-hoc transaction model with the need for atomic semantics and a locking mechanism. Regardless of the duplication of effort, if this model is not well designed, it will fail to implement the semantics correctly and therefore end up having adverse effects contrary to user expectations in some cases.

Additionally, in situations where the items needing to be purchased are not all available from a single vendor, but there is still need for atomicity, such as a travelling arrangement containing a return flight, a hotel booking, and a car rental for the duration of the stay and perhaps a sightseeing tour booking, there is need for a standardized transaction model that can coordinate a purchase across multiple vendors without the need for an opaque intermediary, such as Expedia in our example. While the above examples focus around purchasing and actual monetary transactions, the computer science concept of transactions has far wider applications in distributed systems such as in many collaboration scenarios.

As is common with disruptive technologies, REST over HTTP is evolving to compete with WS-* in increasingly advanced usage scenarios such as Google’s GData and the upcoming Sun Cloud API [1, 2]. The RETRO model aims to be part of the next wave of REST evolution by helping define a RESTful transaction model that is designed to operate over HTTP. To date, usage of REST has remained at the level of serial sequences of operations, each succeeding or failing atomically. While its advantages have made it the dominant web services paradigm on the web, the WS-* stack provides the only standard for transactions [3, 4].

Transaction Basics

The general term ‘Transaction’ has been introduced by Gray [8] and is defined by the four properties contained in the ACID acronym: Atomicity, Consistency, Isolation, and Durability. These properties guarantee that a system is maintained in a consistent state, even as transactions are executed within it concurrently. This includes the situations where one or more transactions fail to commit.

The fundamental property of transactions is that if one or more operations of the transaction fail, it should automatically undo all previous actions and return to the original consistent state. This property is called atomicity. A transaction that is started when a system is in a consistent state may make the state temporarily inconsistent, but it must terminate by producing a new consistent state. This temporary inconsistency may not affect other concurrent transactions, so as to maintain the illusion that each transaction runs in isolation. It follows that concurrent execution should not cause application programs to malfunction, which is the first law of concurrency control [12]. Finally, transactions should be durable, meaning that once a transaction is complete, its results should be persisted permanently.

When dealing with a sequence of transactions (one transaction executed at a time), each transaction starts with the consistent state that its predecessor ended with. If all the transactions are short, the data are centralized in a main memory, and all data are accessed through a single thread, then there is no need for concurrency. The transactions can simply be run in sequence. Real-world interactive systems however, often require execution of several transactions concurrently. Use cases such as distributed environments or dynamic allocation of resources to external developers illustrate this need.

A RESTful Transaction Model

The main motivation behind RETRO is to design a transactional model that can guarantee transactions with the ACID properties, while remaining within the constraints of REST over HTTP. To accomplish this, the model operates over resources and also every significant entity in the transaction model is made into a resource itself that is to be manipulated through the uniform interface of HTTP. To satisfy statelessness, a user locks resources serially, at which point copies of the resources are created within the transactional scope. The client can then manipulate those copies through the uniform interface as they would if they were interacting with an isolated service. Any resources that would be created as a side-effect of these manipulations can also be created within the transactional scope and reachable through hypertext links from the manipulated resources. The requests of the client are stored as resources themselves and become the history of the transaction. Once the transaction is committed, the new state of the locked resource copies is applied to the original resources atomically.

Creating a Transaction

Transaction Collection (Tc): To create a new transaction its representation must be POSTed to the transaction collection. The server should then return a ‘201 Created’ response, along with the URI for to the new transaction resource. By applying the GET operation to transaction collection resource itself, a transaction owner will receive in a collection format links to the transactions they own as a response, after successfully authenticating.

Table 1 - Available Operations for Tc

Our model uses a number of collections. The media type of these collections is not specified here, although the ATOM Publishing Protocol is being examined as a suitable collection handling format. However, any collection representation, as long as it covers the hypermedia requirements of this model, can be used.

Transaction (T): The transaction resource should be represented by a dedicated media type (e.g. application/x.retro-transaction+xml). It should specify the elements in Table 2 as well as the operations that can be applied to them.

Table 2 - Elements of T

These 3 elements identify the resources vital to the execution of a transaction. Any operation on a transaction resource should be applied only after authenticating that the client is the owner of the transaction. The owner can GET the transaction resource to locate the resources relevant to it, PUT to it to update its state or DELETE it to abort the transaction and delete all its subordinate resources. The transaction OwnerURI element should link to a URI that the server understands as an identity and can execute an authentication protocol on. Conceivably, this could be simply a URI on the server itself or even an OpenID [9] handle on a remote server. Finally, the owner of the transaction can commit it by using POST on the CommitTransactionURI. This pattern is akin to a button being pressed on a machine, inspired by a similar pattern used in Sun Cloud API [2, 10, 11]. If the request reaches the server successfully and the server is able to commit the transaction, it will respond with ‘202 Accepted’.

The same functionality could have been implemented by adding a TransactionExecutionRequests collection that an individual TransactionExecutionRequest resource can be POSTed to and lead to the execution of a linked transaction. The addition of an extra collection and all the associated resources however was deemed overkill as monitoring the state of the transaction can be done directly through the TransactionStatus element in the transaction resource and making individual requests into separate resources did not yield any real benefits. This design decision can be reversed however, is sufficient reason is found to do so.

Transaction Lock Collection (T-Lc) : The transaction lock collection contains links to the locks that belong to a specific transaction. New locks can be created by POSTing a new lock representation to this collection.

Table 4 - Available Operations for T-Lc

Placing a Resource in the Transaction Context

Lockable resources (R) are the resources on which the transactions operate on. To satisfy the hypermedia constraint, every lockable resource should indicate it is lockable and link to the transaction collection. Also, ideally, any resource that can be served by an HTTP server should be potentially lockable, conditional on the resource owners’ desires, regardless of media type. One way to do that would be by using custom HTTP header level. This is clearly a more general solution as it would allow resources of all media types to be lockable. If we want to avoid mingling with custom headers, we can focus on XML media types and opt for a XML fragment that can be included in an XML representation of a resource that provides the links HATEOAS requires to start a transaction. This approach could potentially be extended to other formats that can accommodate hyperlinks but probably not to binary files such as images or zip archives for which a different mechanism to indicate lockability must be devised. The inclusion of the following XML fragment indicates that a resource is lockable:

Figure 1 – (R) Example XML Fragment

Making available resources for locking is solely the responsibility of the server. However, the server must have the ability to keep resources stable once they have been locked. This means that if the manipulation of other resources will lead to the alteration of the state of a locked resource, those resources should behave as if they were locked as well, or at least to the degree that they affect the locked resource, to avoid causing consistency violations.

Lock Resource (T-L): The lock resource is represented by a dedicated media type (e.g. application/vnd.retro-lock+xml), and should contain the elements in Table 5.

Table 5 - Elements of T-L

As expected, a transaction cannot lock a resource that is locked by another transaction. However, if two or more transactions want guaranteed read-access to a resource, they are not going to change the resource state and therefore this can be accommodated to increase concurrency. The type element can take one of two values, X or S, corresponding to the available lock types. X stands for XLOCK: eXclussive Lock, and S stands for SLOCK: Shared Lock. To place a new lock, the server must authenticate the user as the owner of the transaction that is referenced by the lock. Table 6 shows the lock compatibility rules.

Table 6 – Legal lock sequences

The length of time of effectiveness that is granted to a lock is dependent on the maximum length of time that the server is prepared to grant a guarantee to the client. Once the duration of the lock expires, the lock is aborted. The lock resource can only be operated on by GET. Deletion a lock can only occur when a transaction is aborted or committed, to avoid violating the 2PL [8] protocol.

Table 7 - Available Operations for T-L

The result of the standard GET operation on the locked resource does not change until a lock of type X is committed. In this sense, the locks and transactions are transparent to the GET, the result of which does not change until a transaction that affected the resource has committed. At that point it reacts as if a simple PUT was applied just then. This was a specific design objective. Meanwhile, PUT and DELETE operations return a ‘405 Method Not Allowed’ HTTP response for the duration of a lock's effect. This behaviour maintains backwards compatibility, with the understanding that if a transaction-enabled client requires further guarantees on the future state of the resource, the client should seek to secure a lock on the resource. Consequently, the semantics of GET are unaffected, as a GET on a resource does not guarantee that the state will remain unchanged for any period of time after a response is sent. Regarding the POST operation, if a resource only has SLOCKs placed on it and the server can guarantee there are no concurrency conflicts such as changing the state of the resource, the POST operation can be satisfied.

Resource Lock Collection (R-Lc): The R-Lc contains all the locks that have been applied to a specific resource. Under normal operation, the locks should be in sequences that follow the compatibility rules stated in Table 6, rendering the transaction well-formed. The inferred rules constrain the set of allowed transaction histories. Histories that satisfy the locking constraints are called legal histories. We use the ‘PrevLockURI’ element of the lock resource to create a linked list of. The client can retrieve the lock collection via GET to determine if the resource is locked. An empty collection indicates an unlocked resource. The role of R-Lc is to allow clients to determine whether a resource can be locked by a new transaction. By retrieving the lock collection a client can determine whether the resource is locked, and what type of lock it has. By the expiration timestamp on the lock resource, the client can estimate when a locked resource will be available again for locking. To emphasise its intention to be solely for retrieval and not POSTing of new locks, we have made the resource read-only for the clients, although this is not strictly necessary. The locks reflected in this resource are the ones that are submitted to T-Lc and reference the lockable resource that the R-Lc is connected to.

Table 8 - Available Operations for R-Lc

Manipulating Resources within the Transaction Scope

Lock resources link to two other resources: the Initial and Conditional Resource representations, which are created when a lock resource is created. While the initial resource representation is a copy purely for future archiving reasons, the conditional resource representation is the resource that acts as the ‘shadow’ of the locked resource, with any changes made to it potentially being applied to the original locked resource when the transaction is committed and therefore the lock released.

Initial Resource Representation (L-IR): A resource that is of identical media type as the locked resource and stores its initial state. The initial representation is archived together with the lock to represent the change caused by the commit of the lock and enable rollback.

Table 9 - Available Operations for L-IR

Conditional Resource Representation (L-CR): A resource that is of identical media type as the locked resource and is created with the same state as well. The conditional resource representation essentially contains the state that will be applied to the resource once the XLOCK is committed. If an L-CR is produced from a SLock, it will only respond to GET and therefore exists purely as a guaranteed point of reference for the length of the transaction.

Conditional Resource Representations produced by an XLock can be manipulated like the resources they are a copy of would be, in an isolated service. This means that PUT and DELETE operations can be applied to the conditional representation freely. The resulting changes will be reflected on the original resource when the transaction is committed. One property of the locking system is that it can lock resources that do not exist yet, simply by referring to them as the ResourceURI of an XLock. This is similar to the creation semantics of PUT. While this may be counterintuitive, it allows the creation of resources directly within a transaction. The only requirement from the server is that it reserves the URI until the end of the transaction. Any updates to the L-CR of the not-yet-existent resource will become the state of the newly created resource at the time of commitment of the transaction. Correspondingly, the L-IR is null. Finally, the conditional representations can be operated on by POST as well, but any side-effects, such as modification, deletion or creation of resources should be limited within the transaction scope. In fact, for any operation on a conditional resource that the server allows to succeed, resources affected should appear within the transaction scope as conditional resources themselves and the appropriate locks should be added to the transaction. The server can continue to allow its state-space to be forked, to the extent where there are no real-world (and therefore irreversible) side-effects and also no potential conflicts if the forks were all to be merged at the same time. The locking system and its compatibility rules make sure this is the case. Also, the trust that the server places on the client may play a part in the amount of the state-space that a client is allowed to place locks on and for how long.

At this point, the links between conditional representations must be considered. Since conditional representations of resources in a transaction are interrelated and valid only within the context of each other, their hyperlinks must point to each other, for the duration of the transaction, as long as the linked to resource is also part of the transaction. A resource that is not part of the transaction can be linked to normally. This also implies a post-processing step that must be made by the server to replace all links to transactional conditional representations with their final and original URIs when the transaction is committed.

Transaction History Collection (THc): This collection contains all the operations performed on the conditional resource representations, serialized into URI-named resources themselves. For any point in time, it represents the path taken from the set of initial representations to the set of conditional representations and at the time of commit represents all the operations that are to be applied to the main state-space of the service.  This collection is read-only for anyone who wants to verify what the path has been so far. Its main purpose however is for archival reasons, as it represents the sequence of operations taken starting from the consistent state before the transaction to the consistent state after it.

Archiving

Once a transaction is executed, all its related resources are archived for durability purposes. This includes all the initial representations of the resources involved, all the operations applied to them as the transaction history, and the resulting conditional representations as the end state of the affected resources.

Model Overview

Having defined all the resource types, it is easy to see that an interconnected network arises. Figure 2 displays the interconnections of the resource graph. It can be observed that having a URI for R is enough to locate all other resources in the network. The URI of a given T is only returned as a response to the initial POST operation on Tc performed by the transaction’s owner.

Figure 2 – Resource Hypermedia connections

Tables 11 and 12 summarize all the relevant resource types that comprise our model together with a short description and a list of the allowed operations.

Table 11 – Transaction model resource types

 Table 12 - Allowed Operations on the Resources

Examples

The section that follows contains examples of transactional interactions between clients and servers. The first two examples focus on a simple service with two resources (R1, R2) while the third example focuses on a single client executing a transaction over multiple servers. Based on the current model, more advanced concurrency (multiple clients and multiple servers) can be depicted by combining the functionality seen in these examples.

Example 1: Creating a Transaction

The example in figure 3 focuses on a client attempting to perform a transaction on a server, placing the locks. It also shows the response that another client will get when it attempts to modify a locked resource.

Example 1.1 Aborting the Transaction

Figure 4 shows how the example in figure 3 could be continued if the client decides to abort the transaction.

Figure 4 – Aborting a transaction

Example 1.2 Committing the Transaction

Figure 5 shows how the example in figure 3 could be continued if the client decides to commit the transaction. On commit, the conditional representation of an active XLOCK becomes the new version of the locked resource. The transaction resource and all other relevant resources are archived for future rollback as they constitute an effective recording of all the changes made by the transaction. Finally, R1 and R2 are unlocked for future use.

Figure 5 – Committing a transaction

Example 2: Concurrent Transactions

The example in figure 6 deals with multiple transactions executing over the same resources. We can see that SLOCKs can be placed by both transactions on the same resource (R1) but XLOCKs cannot (R2). To XLOCK an already locked resource, the transaction must wait until it is unlocked. Once that happens, the second client can complete transaction T2 normally. Here, the transaction model enables concurrency and protects the two clients from adverse effects that their concurrent interaction would have which might have left them in an inconsistent state.

Figure 6 – Concurrent transactions

Example 3: Multi-service Transaction

The example in figure 7 shows a transaction over multiple services. In fact, it is an application of the 2 Phase Commit protocol [8]. This is equivalent to the travel arrangements service composition discussed earlier. Multiple services must be coordinated to avoid an incomplete booking. The example shows a highly ordered sequence; however the same result can be attained by interleaving or even parallelising the operations to the servers, as long as the operations to each server retain their relative order and the three commits are performed as the final operations of the transaction.

Figure 7 – Multi-service transactions

Yeah, but is it RESTful?

The RESTfulness of a model depends on the degree to which it satisfies the constraints of the REST architectural style.

Resource Identification

Contrary to most transaction models, our model explicitly identifies locks, transactions, owners and conditional representations as explicit, linkable resources. In fact, every significant entity in our model is represented as a resource in order to comply with this constraint.

Resource manipulation through representations

In order to comply with the manipulation through representation constraint, a model has to interface with the resources solely through their representations. Our model complies with this as updates to resources are performed by applying the uniform interface on the URI of the resource. For locked resources, the representation that will replace the locked resource when the transaction is committed is kept in a special resource named conditional resource representation, which is a resource itself.

Self-descriptive messages

The self-descriptive nature of messages in REST depends on the assumption that both client and server are aware of the same media types and the semantics which they enclose. This refers to both the contents of a resource as well as the results of a protocol operation on one of the links presented by the resource. In this regard, our model introduces two new media types, one for locks and one for transactions. Given that client and server are aware of these media types, the messages can be considered self-descriptive.

Uniform Interface

The model complies by using the operations provided by the HTTP protocol and also by maintaining the properties of each of the operations.

GET: This operation is used only for retrieving representations of resources and is therefore safe. No changes in the state of the server results from the use of this operation. Since it is safe, it is also idempotent as multiple invocations of this operation have no adverse effects on the state of the application.

POST: Although this operation implies no guarantees of safety or idempotency, it is a frequently misused method, as a tunnel for remote procedure calls. Our usage of POST consists of creating new resources when posted to a relevant collection with the specific URI of the new resource created by the server, or invoking a resource to trigger a message to the server such as ‘commit transaction’. By using this operation for these very specific use cases, we avoid its misuse.

PUT: This operation is meant to create or update a resource at a predetermined URI and guarantees idempotency. In our model we have used this operation purely for updating resources. The idempotency property remains as repetitions of the same operation do not cause unforeseen results.

DELETE: Similarly to PUT, this operation implies idempotency. Our model utilises DELETE as a terminating operation (e.g. for transactions) in a manner complies with the idempotency requirements.

Hypermedia as the engine of application state

Special care has been applied in order to avoid breaking this often misunderstood constraint. The model has been designed so that a client aware of only the relevant media types and given a single URI can interact with a server implementing the model. The URI can be of any lockable resource on the server, or of a transaction. Both these resources provide enough information for any relevant resource to be discovered at run-time. This allows for extremely loose coupling as the server is free to alter the naming scheme of its resources at any time, and the clients can be expected to adapt without any deliberate updating process. In fact, throughout this document, no specific URI structure has been referred to or proposed, specifically to avoid the assumption that the transaction is driven by URI structure and therefore out-of-band information.

Having defined all the resources and their interconnections, it is easy to see that a network arises. Figure 2 displays the interconnections of the resource graph. It can be observed that having a URI for R is enough to locate all other resources in the network. The connection from Tc to T is different from the other connections as there is no GET ability for the Tc resource. The URI of T is returned as a response to a POST operation on T performed by the transaction’s owner.

Statelessness

In our model, each request by the client includes all the information required to carry it out at the server. Authentication information is expected to be negotiated separately for each request. This produces a system that needs to keep no session information between operations.

Conclusion

Work on RETRO continues, the next step is to look at long-running transactions. The reason we have focused on ACID as the first step is to develop a basic model we can extend to long-running transactions in the future, but also to show that REST and Transactions can and do mix. Whether  or not we have accomplished our second goal remains to be seen.

In case you missed the link at the top, You can give us your feedback about RETRO here. 

References

1. Google, “Protocol Reference - Google Data APIs - Google Code.” URL: http://code.google.com/apis/gdata/docs/2.0/reference.html Accessed: 31/3/2009
2. Sun Microsystems, “The APIs for the Sun Cloud — Project Kenai.” URL: http://kenai.com/projects/suncloudapis Accessed: 31/3/2009
3. L.F. Cabrera, G. Copeland, M. Feingold, R.W. Freund, T. Freund, J. Johnson, S. Joyce, C. Kaler, J. Klein, D. Langworthy, M. Little, A. Nadalin, E. Newcomer, D. Orchard, I. Robinson, J. Shewchuk, and T. Storey, “Web Services Coordination (WS-Coordination),” Aug. 2005
4. P. Furnis and A. Green. Choreology Ltd. Contribution to the OASIS WS-TX Technical Committee relating to WS-Coordination, WSAtomicTransaction and WS-BusinessActivity. November 2005
5. Rest-Discuss http://tech.groups.yahoo.com/group/rest-discuss/message/12170?var=1
6. “OPAALS Project: Open Philosophies of Associative Autopoietic Digital Ecosystems” URL: http://www.OPAALS.org - Accessed: 31/3/2009
7. F. Nachira, A. Nicolai, P. Dini, M. Le Louarn, and L. Rivera Leon, Eds., Digital Business Ecosystems. European Commission, 2007.
8. Gray, J. & Reuter, A. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, 1993
9. D. Recordon and D. Reed, “OpenID 2.0: a platform for user-centric identity management,” Proceedings of the second ACM workshop on Digital identity management, ACM New York, NY, USA, 2006, pp. 11-16.
10. T. Bray, “ongoing · The Sun Cloud.”, URL: http://www.tbray.org/ongoing/When/200x/2009/03/16/Sun-Cloud Accessed: 31/3/2009
11. R. Fielding, “It is okay to use POST » Untangled.” URL: http://roy.gbiv.com/untangled/2009/it-is-okay-to-use-post Accessed: 31/3/2009
12. Bernstein, P.A., Hadzilacos, V., and Goodman, N. Concurrency control and recovery in database systems. Addison-Wesley, Boston, MA, USA, 1987
13. “IEEE Conference on Digital Ecosystems and Technologies.” URL: http://www.ieee-dest.curtin.edu.au/ Accessed: 31/3/2009