Many Faces of Ad Hoc Transactions

All DB operations vs. specific DB operations. With ad hoc transactions, developers can coordinate only specific database operations instead of all operations in the transaction scope. Consider the following example from the Spree e-commerce application.

1 in: sku_id, requested
2 lock(sku_id)
3 sku := Select * From SKUs Where id=sku_id
4 if sku.quantity >= requested:
5   sku.quantity -= requested
6   // the following statements are auto-generated by ORM.save(sku)
7   Transaction Start
8   Update SKUs Set quantity=sku.quantity Where id=sku.id
9   Update Products Set updated_at=now() Where id=sku.product_id
10  category_ids := Select category_id
11        From Categories Join ProductCategories Using category_id
12        Where product_id=sku.product_id
13  Update Categories Set updated_at=now() Where id In category_ids
14  Transaction Commit
15 unlock(sku_id)

This transaction processes customer orders. It first fetches the stock-keeping unit (SKU) data from the SKUs table, checks and updates the SKU’s stock quantity, and then persists changes to the database system by invoking the ORM.save() method. ORM.save() automatically starts a database transaction, within which it issues three updates and one query (lines 8–13). This transaction is running in the RDBMS’ default isolation level. The first update changes the quantity in the SKUs table, and other updates refresh the update_at timestamps of corresponding Products and Categories rows. Categories rows are identified by querying the ProductCategories table, which encodes the many-to-many relationship between products and categories. In this example, the only critical operations are those over SKUs (lines 3 and 8). Therefore, developers explicitly lock over sku_id in their ad hoc transaction implementation. Other operations, such as product and category updates (lines 9 and 13), require no coordination but are still in the lock scope, as the application-level ORM.save() call automatically generates them. Interestingly, replacing the lock()/unlock() primitives with Transaction Start/Commit may worsen performance due to indiscriminately upgrading all operations to the same isolation level. Furthermore, developers cannot exclude these timestamp updates from the scope of database transactions as the ORM hides the generation of such database operations.

Overall, 22 ad hoc transactions coordinate only a portion of the database operations in the transaction scope. Other operations require no coordination but are located in the transaction scope as they are either automatically generated by the ORM or needed by critical operations.

Individual requests vs. multiple requests. Database transactions spanning multiple HTTP requests are a performance anti-pattern, as they introduce long-lived transactions (LLTs). Yet, we have found 10 ad hoc transactions with life spans across multiple requests. Below is an example derived from the Discourse forum application of editing a post that spans two user requests. The user fetches the post content for local editing in the first request. Then, the user’s edits are applied in the second request. This ad hoc transaction ensures that other concurrent edits do not overwrite the content read by the first request when editing the post.

1 Request 1 // fetch a post & increment view count
2   in: post_id
3   Update Post Set view_cnt=view_cnt+1, ver=ver+1 Where id=post_id
4   post := Select * From Posts Where id=post_id
5   response render(post) // this response includes the version
6 Request 2 // detect interruptions & apply user updates
7   in: post_id, new_content , prev_ver
8   lock(post_id)
9   current := Select * From Posts Where id=post_id
10  if current.ver!=prev_ver: unlock(post_id); response FAILURE
11  Update Posts Set content=new_content , ver=ver+1 Where id=post_id
12  unlock(post_id); response SUCCESS

Specifically, developers use an optimistic ad hoc transaction to ensure the consistency of the post content. They associate a version number with each post to track updates. Before updating a post, the ad hoc transaction checks the consistency (that is, not overwritten) by validating the version. Furthermore, it needs to use a lock to ensure the validate-and-commit atomicity. If the validation fails, the current request handler will not update the content, thus avoiding overwriting others’ changes. Interestingly, unlike database transactions that undo all effects if aborted, this ad hoc transaction does not roll back the view count increment made in the previous request handler. Normally, Web applications choose optimistic coordination instead of pessimistic coordination to coordinate multiple requests to avoid long blocking. Extensions to database transactions were proposed for LLTs, such as Sagas⁷ and savepoints. Unfortunately, they usually provide (potentially unnecessarily) stronger semantics than what ad hoc transactions provide.

DB operations vs. non-DB operations. Ad hoc transactions’ flexibility also shines in coordinating non-database operations. A Web application may use multiple storage systems. Thus, it needs to ensure data consistency across different systems. There are eight cases of ad hoc transactions that coordinate both database operations and non-database operations, such as operations over in-memory shared variables, local file systems, and remote object/key–value (KV) stores. Consider the following example of the timeline feature from the Mastodon social network application.

1 Create Post
2   in: follower_id, post_id, content
3   lock(post_id)
4   Insert Into Posts Value (post_id, content)
5   REDIS.add_to_set("timeline"+follower_id, post_id)
6   unlock(post_id)
7 Delete Post
8   in: follower_id, post_id
9   lock(post_id)
10  REDIS.delete_from_set("timeline"+follower_id, post_id)
11  Delete From Posts Where id=post_id
12  unlock(post_id)

It uses a Redis KV store and an RDBMS as its backend storage. Redis holds the IDs of posts shown on each user’s timeline, while the concrete post contents are resident in the RDBMS. Mastodon must guarantee consistency between the post contents in the RDBMS and the post IDs in Redis. Specifically, the post IDs in Redis should always refer to some posts in the RDBMS, and this cannot be achieved solely with database transactions. Thus, developers implement ad hoc transactions to coordinate these operations. In general, when applications require data consistency across multiple storage systems (including multiple RDBMSs), the alternative option is to use distributed transactions, such as WS-TX or XA transactions. However, storage systems rarely support such distributed transaction protocols, making writing ad hoc transactions the only feasible solution.

Locks from existing systems vs. manually crafted locks.  All eight applications studied have lock-based pessimistic ad hoc transactions. They usually use a single locking primitive implementation, from either existing systems or scratch.

Four applications directly use the locking primitives provided by the database systems or language runtimes. Specifically, Spree, Saleor, and Redmine use the database Select For Update statements, while SCM Suite implements ad hoc transactions based on the Java synchronized keyword. Most commercial databases accept Select For Update statements, which atomically fetch target rows and acquire corresponding writer locks. The lock will be released when the currently active transaction ends.

Three other applications, Discourse, Mastodon, and Jump-Server, have locks implemented from scratch. Interestingly, they all store lock information, including lock keys and status (locked/unlocked), in the Redis KV store. However, their implementation details are different. As shown in Figure 1b, Mastodon developers use the Redis SETNX (short for SET if Not eXists) command to insert an entry for the requested lock. Similar to the compare-and-swap instruction, this command succeeds only if no entry with the same key exists. In contrast, Discourse developers use a combination of WATCH, GET, MULTI, and SET commands to optimistically ensure the atomicity of checking existing locks and setting new locks. As a result, Discourse’s Redis lock requires six additional roundtrips compared to Mastodon’s, which only needs one. Saleor uses SETNX to implement locks as Mastodon; it also adds a re-entrant feature, allowing locks to be repeatedly acquired by the same thread.

Broadleaf is the only application using both from-scratch lock implementations and existing systems’ primitives—the Java synchronized keyword. More interestingly, it has three from-scratch implementations: One uses a separate database table to store lock information similar to Redis-based locks; the other two use in-memory maps for lock information. The latter two implementations differ in the specific maps used: One directly uses a concurrent map from the standard library, ConcurrentHashMap; the other uses a customized ConcurrentHashMap, where developers added a least recently used (LRU) eviction policy to remove excessive lock entries. These implementations are introduced by different developers, and we have not found clear evidence that they serve different purposes.

ORM-assisted validation vs. manual validation.  Six out of eight applications studied have validation-based optimistic ad hoc transactions. Their validation procedures are either provided by the ORM or the developers themselves.

Four applications use ORM-provided validation procedures via framework-specific interfaces. For example, Active Record recognizes columns named lock_version and uses them to store versions for individual rows. Upon each update, as shown in Figure 1c, Active Record automatically adds version checking to the Where clause and increment version along with user-initiated updates, ensuring the atomicity between validation and commit.

When using hand-crafted validation procedures, developers must ensure the atomicity between validation and commit. As shown in the listing from §3.1, additional locks are employed for this purpose. All validation procedures in Discourse’s and SCM Suite’s optimistic ad hoc transactions are manually implemented. Broadleaf uses both implementations, introduced by different developers.

Single access vs. multiple accesses.  Fifty-eight ad hoc transactions use only one lock to coordinate multiple database accesses, thanks to the following two access patterns in the applications.

Associated access: Given two database rows, r1 and r2, if accesses to r2 always happen in a transaction that also accesses r1, we say r2 is associatively accessed with r1. Access to rows associated with a one-to-many relationship, such as an is-part-of relationship, often follows this pattern. Consider the example in Broadleaf, shown in Figure 1a. A cart is represented as one Carts row and several Items rows. When a user modifies the cart, the transaction will associatively access these rows. This pattern provides an opportunity to replace multiple locks (for example, row locks) with one lock that coordinates these accesses. In the above example, developers use a single cart lock to coordinate accesses to both Carts and Items tables. This lock explicitly serializes conflicting transactions up front, thus avoiding potential aborts when using database transactions.

There are about 37 ad hoc transactions that leverage the associated access pattern. In all these cases, the associated rows are connected by either one-to-many or one-to-one relationships. We find that such one-to-many relationships all stem from the application-specific data modeling that reflects the business semantics, like the cart-item relationship in the example. Meanwhile, such one-to-one relationships all come from inheritance.

Read–modify–write (RMW): With RMW, a transaction first reads data from the database, then modifies it, and finally writes it back. In a typical 2PL system such as MySQL, deadlocks arise if concurrent transactions perform RMW on the same row. Consider the example shown in Figure 1b: In the forum application Discourse, RMW operations are issued when creating a new account via invitations. The invitation is first read from the RDBMS. After checking its validity, it gets updated and written back to the RDBMS. If two users concurrently use the same invitation to join the forum, a deadlock can easily appear, making both users unable to succeed. To mitigate this, developers craft ad hoc transactions to acquire exclusive locks before the first read, avoiding possible deadlocks. Fifty-six out of 91 cases leverage this access pattern. Among them, 35 cases also use the associated access pattern.

Fine-grained vs. coarse-grained.  Ad hoc transactions can also use fine-grained column- or predicate-based coordination.

Knowing which columns are used in the business logic allows developers to coordinate database operations at the column granularity, and there are five such ad hoc transactions. For example, in the forum application Discourse, two transactions, create-post and toggle-answer, will issue the following database operations accessing the Topics table.

1 Create Post
2   in: topic_id, content
3   lock("create_post"+topic_id)
4   next_post_id := Select max_post From Topics Where id=topic_id
5   Insert Into Posts Value (next_post_id, content, topic_id)
6   Update Topics Set max_post=max_post+1 Where id=topic_id
7   unlock("create_post"+topic_id)
8 Toggle Answer
9   in: topic_id, post_id
10  lock("toggle_answer"+topic_id)
11  Update Posts Set is_answer=true Where id=post_id
12  Update Topics Set answer=post_id Where id=topic_id
13  unlock("toggle_answer"+topic_id)

Line 6 increments the max_post field; line 12 sets the answer field. Though these operations have no column-level conflicts, if they access the same row, an RDBMS using row locks cannot execute them in parallel. Therefore, instead of using database transactions, Discourse developers implement two lock namespaces for these two transactions so that their locks do not interfere with each other.

Likewise, knowing the search conditions, developers can use the precise predicate for coordination, and there are 10 such cases. Predicate-based coordination can avoid false conflicts caused by the gap lock used in the major RDBMSs, including MySQL and PostgreSQL. For example, in the Spree e-commerce application, RDBMSs might concurrently execute the following code with order_id of 10 and 11, corresponding to two orders created by transaction Txn 1 and Txn 2, respectively.

1 in: o_id, ..
2 lock(order_id=o_id)
3 pays := Select * From Payments Where order_id=o_id
4 if pays is empty:
5   Insert Into Payments Value (o_id, ..)
6 unlock(order_id=o_id)

In Txn 1, line 3 checks if any payment row exists for the order identified by order_id=10. Since an order can have many payments (to allow mixed payment methods), the order_id index of the Payments table is non-unique. Suppose it currently indexes values 9 and 12. Executing line 3 of Txn 1 causes the RDBMS to acquire a gap lock on the index interval (9, 12), blocking concurrent inserts to this range so that re-executing line 3 can obtain repeatable results. Meanwhile, line 5 in Txn 2 inserts a new payment row for another order whose order_id equals 11. Though this insert does not interfere with Txn 1’s line 3, it would nevertheless be blocked by the gap lock. By manually locking on specific order_id values, developers can avoid such false conflicts.

Automated rollback vs. manual rollback.  We first consider runtime failures, which include deadlocks or validation failures. Unlike database transactions, which have a system-level catch-all rollback mechanism, application developers need to craft failure-handling logic on a case-by-case basis.

Each pessimistic ad hoc transaction either uses a single lock (52/65) or acquires locks in a consistent order (13/65). Thus, none needs to handle deadlock at runtime. The same applies to locking in optimistic ad hoc transactions. Interestingly, some optimistic cases do not acquire any lock during the validate-and-commit process, which eliminates deadlocks but sacrifices correctness (see §4.1).

Therefore, rollback is only needed for validation failures in optimistic ad hoc transactions. In 19 optimistic cases, developers follow the classic OCC paradigm, where no update is persisted before validation, thus avoiding the need for rollback. In other cases, early persisted updates require developers to either use certain rollback methods to negate the effect of updates or use repair techniques to roll forward and finalize changes.

To roll back, ad hoc transactions rely on either database transactions’ atomicity property or hand-crafted rollback procedures. There is 1 case using the former approach, where a Read Committed database transaction is used to enclose update and validation operations. If validation fails, the application aborts the database transaction to roll back all enclosed updates. Meanwhile, two cases use manually programmed rollback procedures triggered by validation failures and will undo persisted updates. Unlike database rollback, developers can selectively undo only critical updates. For example, in Broadleaf, if validation on SKU state fails during checkout, updates to payment and order status are rolled back, while other updates like total order price calculation are kept unaffected.

Meanwhile, four cases choose to repair the inconsistent values instead of rolling back on conflicts. This idea relies on developers’ knowledge of program dependency and is similar to recently proposed transaction repair optimizations.^4,5,14 For example, in Discourse, multiple posts can reference the same image and thus changes to images must be propagated to all relevant posts. During a background image-shrinking job, if a referencing post is updated by the user, instead of aborting the whole process, Discourse uses per-post versions to identify the changed post, only redoes updates for it, and commits the image-shrinking process.

Crash handling.  Since ad hoc transactions are not automatically rolled back upon crashes, developers need to manually ensure coordination metadata (for example, locks) and database states are properly recovered. Among the former case, version numbers and most lock states require no special handling, as optimistic ad hoc transactions can always retry reading the latest version, and both in-memory and Redis-based locks do not (forever) persist across crashes. However, the database-based persistent locks in Broadleaf require special handling. To avoid deadlock caused by unreleased locks, developers associate each lock using a boot-time generated universally unique identifier (UUID) to distinguish each run. Thus, Broadleaf can ignore prior unreleased locks after reboot by examining the saved UUIDs.

Recovering database states after crashes is more challenging than validation failure rollback since developers are unaware of the progress of interrupted ad hoc transactions. Though in the case of database crashes, applications can spin-wait for database restart and then either roll back or continue, all ad hoc transactions simply terminate immediately and leave the database in an intermediate state. Only one application, Discourse, has a fsck-like checker that runs every 12 hours to actively restore inconsistent references, such as missing avatars and thumbnails. Other applications either tolerate intermediate states with preventative measures or simply let the inconsistency propagate to end users (§4.3). An example of preventative measures is Broadleaf, which sets any payment record left unconfirmed during an interrupted checkout before starting a new one.

Incorrect lock usage.  When developers reuse existing systems’ locking primitives, misuses arise. Issues exist for both types of locking primitive reuse: Select For Update from database systems and Java’s synchronized keyword (§3.2). For example, in some Spree cases, Select For Update statements are not explicitly enclosed inside database transactions, which causes the database lock to release as soon as the statement returns. Another type of misuse happens when developers use a single lock to coordinate RMW operations, and they omit the first query from protection. This happens often when developers have to first perform the query to obtain the lock key, for example, an ID. In these situations, developers should re-execute the query after acquiring the lock to protect the entire RMW. There are two cases where the developers forget to re-execute queries, leaving the initial read in RMW uncoordinated.

Incorrect lock implementation.  The locking primitives implemented from scratch can also have correctness issues, especially those using Redis or in-memory lock tables. For example, the Redis lock in Mastodon implements the lease semantics, where the lock might be released early when the entry times out before the coordinated critical section finishes. Unfortunately, Mastodon does not check whether the lock has expired early and experiences inconsistency, such as deleted posts appearing in followers’ timelines.

Non-atomic validate-and-commit.  Validation-based optimistic ad hoc transactions need to avoid conflicting updates between validation and commit. Thus, they need to guarantee validate-and-commit atomicity. However, atomicity violation happens only when developers manually implement validation procedures (16 cases); all cases using ORM-generated validation procedures we studied are correct.

Omitting critical operations.  Though the flexibility of choosing what to coordinate is an advantage of ad hoc transactions (§3.1), it comes with an increased chance of leaving critical operations uncoordinated. For example, in Broadleaf, the ad hoc transaction that coordinates the check-out process omits coordination for all SKU-related operations. As a result, concurrent check-outs for the same SKU can lead to inconsistency between the SKU quantity decrement and the number of sold items.

Forgetting ad hoc transactions.  Forgetting to coordinate certain business logic with transactions is a general problem with both ad hoc and database transactions. However, it is more disastrous with ad hoc transactions. A conflicting business procedure (for example, a request handler) without proper ad hoc transactions installed can freely interleave with other ad hoc transaction–coordinated procedures, reading and writing “coordinated” data. For example, in Spree, all ad hoc transactions are deployed in the request handlers that return HTML responses. However, another uncoordinated set of handlers with the same functionality exists and produces JSON responses. As a result, JSON handlers’ interleaving with HTML handlers leaves RDBMS states inconsistent.

Incomplete repair.  When using transaction repair to roll forward an interrupted transaction, developers might derive an incomplete repair, such that not all affected operations are re-executed. In Discourse, when updating image references of posts, developers use versions to detect concurrent modification to fetched posts that use a given image (shown in §3.4). However, their implementation cannot detect newly added posts referencing this image. These new posts will end up having dangling image references, showing end-users broken links. There is only one case that has this issue.

Unexpected intermediate states after crashes.  If an application is not designed to tolerate intermediate database states, and rollback handlers fail to prevent such states, the application might fail to provide normal services if server or database crashes occur. We thoroughly investigated the impact of crashes in ad hoc transactions from Broadleaf and Spree. We identified 31 unique crash scenarios where a crash leaves writes partially executed and found that 28 of these scenarios have user-noticeable unexpected behaviors. For example, in Spree, a crash during check-out can leave payments in an intermediate state (that is, having the status column equalling “processing”). Since these payments are not rolled back after reboot, Spree can neither initiate new payment operations due to the unfinished ones nor resume payments initiated before the crash because they are considered under “processing” by active threads. Therefore, users can never finish the check-out.