Software Transactional Memory

Software Transactional Memory

By R. Mark Volkmann, OCI Partner

September 2009

Contents

• Overview
• Lock-based Concurrency
• Actor-based Concurrency
• Transactional Memory
• Software Transactional Memory (STM)
• Persistent Data Structures
• STM Implementations
• Clojure Overview
• Clojure Reference Types
• Clojure Validators and Watchers
• Clojure STM - High Level
• Clojure STM - Low Level
• Conclusion
• References

Overview

Writing software applications in which parts of the application run in concurrent threads introduces many challenges not present in single-threaded applications. Since the order of operations isn't fixed, failures can be difficult to repeat. Also, thoroughly testing the software requires more effort.

There are two general categories of multithreaded software. In one category the goal is to divide the work involved in processing a single "job" into pieces and run the pieces concurrently in order to complete the job sooner. In the other category the goal is to coordinate the execution of multiple "jobs", allowing them to execute concurrently so that as a group they complete sooner than if they were run serially. In both cases there can be contention over the data being accessed. However, the issue is perhaps more common and harder to avoid in the second category.

There are many models for creating concurrent software. The most popular today are based on locks, actors and transactional memory. This article briefly describes all three models and then dives deeper into software-based transactional memory (STM) [4].

The goals of this article are to:

• spread knowledge about STM
• support reasoning about the performance characteristics of STM
• encourage implementations of STM for many programming languages
• facilitate the ability of interested developers to suggest improvements to the STM implementation in the Clojure programming language
• provide developers with enough understanding of the Clojure STM implementation that they can develop tools to help with tuning STM usage (such as tracking the number of times a transaction retries and why it retries)

Please send feedback on errors and ways to improve explanations to mark@ociweb.com. Updates to this article that indicate the "last updated" date and provide a dated list of changes will be provided at [1].

Lock-based Concurrency

Lock-based concurrency provides a mechanism for threads to safely access shared memory. In its simplest form, exclusive ownership of a lock must be acquired before a given block of code is executed. This is used to ensure that only one thread at a time can execute the code. In object-oriented programming languages, often the lock is associated with an object that is accessed by code in the block. Sometimes multiple objects are accessed and a single lock object is designated to provide exclusive access to that group of objects.

Benefits of using lock-based concurrency include the following:

• Developers have explicit control over when locks are obtained and released which allows optimal solutions.
• Many developers are already familiar with this form of managing concurrency.
• Many programming languages support the use of locks.

Issues with using lock-based concurrency include the following:

• It can be difficult to determine which lock(s) need to be obtained in order for a given block of code to execute safely.
• Variables for which a lock should be acquired can be accessed even when the wrong lock(s) are acquired and even when no locks are acquired.
• A thread is in a deadlock state when it is unable to acquire all the locks it needs to proceed because other threads own them and are themselves deadlocked. This can easily occur unless locks are acquired in a common order.
• Recovering from errors can be complicated because developers must remember to release locks that were acquired by the failing code.
• Correctly synchronized methods cannot be composed into compound methods without additional synchronization.
• The lock-based approach is pessimistic. It assumes that if multiple threads are each running sections of code that access the same memory then only one at a time can safely run. This is not always true. Making this assumption reduces the amount of concurrent processing that can occur.

Actor-based Concurrency

The actor model [3] is an alternative to shared memory concurrency, such as lock-based concurrency and transactional memory. Actors are software entities that execute as separate processes or light-weight threads. Rather than accessing shared memory, actors only use and retain data that is passed to them in asynchronous messages. When an actor receives a message, it can do the following things concurrently or in any order:

• create new actors
• send messages to other actors
• specify how the next message it receives will be handled

Benefits of using actor-based concurrency include the following:

• Since no memory is shared between actors, access to data doesn't need to be synchronized.

Issues with using actor-based concurrency include the following:

• Since memory isn't shared between actors, some messages may need to be large. This negatively affects performance.
• Since memory isn't shared between actors, the data each actor holds can become inconsistent with the data held by other actors. There is no general mechanism for coordinating the activities of multiple actors.

The actor model is a central feature of the Erlang programming language. It is also supported by Scala and Haskell, but not Clojure [13].

For a more detailed description of actors, see http://en.wikipedia.org/wiki/Actor_model.

Transactional Memory

Transactional memory provides an alternative to lock-based and actor-based concurrency that simplifies writing applications in which concurrently running threads access shared memory.

The concept is similar to that of database transactions which provide ACID characteristics:

• "A" is for atomic.
• "C" is for consistent.
• "I" is for isolated.
• "D" is for durable.

"Atomic" means that either all the changes in a transaction will be made successfully (commit) or none of them will be (rollback). "Consistent" means that all the data seen by a transaction at its start and end will be consistent. In other words, constraints on the data will not be violated. "Isolated" means that changes made inside a transaction are not visible outside the transaction until it commits. "Durable" means that after a transaction has committed, changes it made will not be lost, even if there is a network, hardware or software malfunction.

Transactions are demarcated in code by a special syntax that varies across implementations. From the perspective of other threads, all the memory changes made within a transaction appear to happen at the same moment when a transaction is finished committing. The changes are not visible to other threads before then. Transactions operate on a consistent snapshot of the memory. If any memory that is written within transaction "A" is modified and committed by transaction "B" before "A" commits, the code in "A" is rerun. These characteristics make transactional memory atomic, consistent and isolated. Note that transactional memory is not durable. If the software crashes or there is a hardware malfunction, data in memory is typically lost. When durability is required, using a relational database is often recommended.

Transactional memory is optimistic. Each transaction assumes it will be able to run its code without concurrently running threads changing the values it writes. When this assumption doesn't hold, the transaction discards all the work it has done and retries from the beginning. The possibility of retries makes it necessary to avoid any actions (side effects) that shouldn't be repeated or cannot be undone. This includes I/O operations. Clojure provides a solution for this that involves a combination of Refs and Agents. This is discussed later.

In descriptions of the retry process later, this article distinguishes between a "transaction" and a "transaction try". A transaction includes one or more transaction tries. A transaction that completes without having to retry runs a single transaction try. Otherwise there are more than one.

Transactional memory distinguishes between committed values of variables and in-transaction values. Inside a transaction, the value of a variable starts out as either its initial value or the last value committed by a transaction. When the value of a variable is modified inside a transaction, that change is only seen and used in the transaction. When the transaction commits, changes become visible to code outside the transaction.

Benefits of using transactional memory include the following:

• It provides increased concurrency which means there are more opportunities for processing to be performed simultaneously instead of serially. This is especially true for transactions that only read data. Lock-based concurrency doesn't allow this kind of overlapping execution because it takes a pessimistic approach rather than an optimistic one.
• It is easier to write correct code using transactional memory than writing code that uses locks. The need to determine the locks to be acquired and the order in which to acquire them is removed. Instead, developers identify sections of code that require a consistent view of the set of variables it reads and writes.
• Implementations can guarantee that deadlock [5], livelock [6] and race conditions [7] will never occur.

Issues with using transactional memory include the following:

• There is a potential for a large number of transaction retries resulting in wasted work.
• There is overhead imposed by transaction bookkeeping such as storing histories of committed values, storing in-transaction values and acquiring locks before committing changes.
• Tool support is currently lacking. For example, having tools that identify how often each transaction retries and why they retry (such as learning which variables had write conflicts) would make it easier to tune applications when necessary.

Transactional memory works best in programming languages that distinguish between mutable and immutable variables and require mutable variables to be mutated inside a transaction (like in Clojure and Haskell). Without these features, developers are on their honor to only modify mutable variables inside transactions. They must ensure that no data that requires coordinated changes is modified outside an STM transaction. This is similar to the issue with lock-based concurrency where developers are on their honor to acquire the correct lock(s) before accessing variables where this is expected.

Garbage Collection Analogy

Dan Grossman, an associate professor at the University of Washington, wrote a paper titled "The Transactional Memory / Garbage Collection Analogy" [8]. The paper illustrates several ways in which transactional memory (TM) is similar to garbage collection (GC). Some quotes from a related presentation follow:
"Many used to think GC was too slow without hardware."
"Many used to think GC was about to take over, decades before it did."
"Many used to think we needed a back door for when GC was too approximate."
These same thoughts are often expressed about TM today. Perhaps over time these thoughts will change in the same way they have changed for GC. Dan discusses this paper in episode 68 of the "Software Engineering Radio" podcast [9].

Software Transactional Memory (STM)

Transactional memory can be implemented by hardware or software. This article focuses on software implementations which are commonly referred to as STM. STM is an integral part of some programming languages. For others, it is supported through add-on libraries.

Persistent Data Structures

One way programming languages avoid the issue of data being modified by concurrently running threads is by providing immutable data structures or collection classes. Clearly data that cannot change doesn't need to be protected. It is often desirable to be able to create new data structures that are similar to existing ones, for example, a list with a new item added at one end or a hash map with a new key/value pair added. Persistent data structures [14] provide a way to do this where new data structures share memory with existing ones. Using these saves both memory and time. The benefit of having immutable data structures that are not persistent is questionable since creating new ones from them is slow and can consume a large amount of memory.

STM Implementations

Many STM implementations are listed in the STM Wikipedia entry [15]. Programming languages for which STM implementations exist include: C, C++, C#, Clojure, Common Lisp, Haskell, Java, MUMPS, OCaml, Perl 6, Python, Scheme and Smalltalk. For many of these languages there are multiple STM implementations from which to choose.

Just as there are many ways to implement garbage collection, there are many ways to implement STM. It is difficult to make general statements about the characteristics of STM implementations, such as memory usage and performance. The remainder of this article focuses on the Clojure implementation.

One aspect of the Clojure STM implementation that differs from many others is that data coordinated by transactions cannot be modified outside a transaction. With some implementations, developers are "on their honor" to use them correctly (for example, Deuce STM).

Clojure Overview

Clojure is a functional programming language that is a Lisp dialect and runs on the Java Virtual Machine (JVM). It was created by Rich Hickey. For a detailed discussion on Clojure, see my earlier article [2].

Clojure Reference Types

In Clojure all variables are immutable unless they refer to a reference object. There are four types of reference objects: Var, Atom, Agent and Ref. Each type is described below. For more detail, including sample code, see my earlier article.

Vars

Vars are variables that have a root value that is shared between all threads and can have thread-specific values. The functions that modify the value of a Var include def, set! and binding. The value of a Var is obtained by directly referencing it, as in other programming languages. Vars are mainly used for constants. In general, modifying the value of a Var is discouraged.

One use of Vars where modifying the value is seen as acceptable is for configuration variables. For example, if the special variable *warn-on-reflection* is set to true, Clojure will output warning messages whenever it uses reflection to determine the type of an object. This is useful while tuning an application for performance as it provides guidance in determining where adding optional type hints may help.

Atoms

Atoms are variables that have a single value that is shared across all threads. They are accessed in an atomic way, so it is safe for multiple threads to concurrently read and write them. The functions that modify the value of an Atom include reset!, compare-and-set! and swap!. The value of an Atom is obtained by dereferencing it using @var-name.

Agents

Agents are variables that, like Atoms, have a single value that is shared across all threads. They are modified asynchronously by invoking a function, called an "action", in another thread. The value returned by the action becomes the new value of the Agent. The value of an Agent is obtained by dereferencing it using @var-name.

Actions sent to the same Agent are queued up so that only one action at a time will be run per Agent. The functions that queue an action are send and send-off. They return immediately since the specified action is executed asynchronously. They differ only in the thread pool that is used. One pool has a fixed size and the other has a variable size. The action is is passed the current value of the Agent and any other arguments that were passed to send or send-off.

The await function pauses the current thread until all actions sent to a given set of Agents have completed. The await-for function is similar, but supports a timeout.

Actions sent to agents inside a transaction are held until after the transaction commits. This feature is sometimes used as a way to attach code that has side effects, such as I/O, to a transaction.

Refs

Refs are variables that, like Atoms and Agents, have a single value that is shared across all threads. They can only be modified inside an STM transaction. The functions that modify the value of a Ref include ref-set, alter and commute. The value of a Ref is obtained by dereferencing it using @var-name.

In this article, when discussing Refs, the terms "read" and "dereference" are used synonymously. A transaction is not required in order to dereference a Ref, but one is needed to get a consistent snapshot when dereferencing multiple Refs.

Refs are the only type of variable in Clojure that is coordinated by STM. For this reason, they are the focus of this article.

The most direct way to change the value of a Ref is to use the ref-set function. It takes the Ref whose value is to be modified and the new value.

For both the alter and commute functions the first argument is the Ref whose value is to be modified and the second argument is a function that returns the new value. When this function is invoked, it is passed the current value of the Ref and any additional arguments that were passed to alter or commute. The return value becomes the new value of the Ref.

Using alter instead of ref-set is typically seen as more idiomatic. A conversation with the CIP (Clojure Idiomatic Police) might go as follows:
CIP: Why did you use ref-set instead of alter?
You: Well, I already had the value I wanted to use for the Ref, so I just passed it to ref-set.
CIP: Where did you get that value?
You: It was computed in a function I called.
CIP: Why didn't you just pass the Ref, the function and its arguments to alter? Don't be afraid to pass functions to functions. This is encouraged in functional programming.

In most cases, alter is preferred over commute. Using commute is only appropriate when the order of changes to the Ref made by concurrently running transactions doesn't matter. This is related to the mathematical definition of "commutative" which includes the phrases "the result obtained ... does not differ with the order". Choosing to use commute basically says "I'm going to modify a Ref, but I don't care if another transaction modifies it before I commit my change. Decisions I make in this transaction based on my value of the Ref will still be correct. I want the value of the Ref to be recomputed when I'm ready to commit based on the newest value of the Ref."

Some situations where commute makes sense include accumulating objects in a collection and storing values calculated from a collection (such as a minimum, maximum or average). Suppose a collection is held in a Ref. If two concurrent transactions add an object to the collection, in many cases it doesn't matter which adds to it first. There may be no reason for transaction "A" to retry just because transaction "B" added to the collection before "A" committed. Suppose another Ref holds a value computed from the collection such as the maximum value in it. There may be no reason for transaction "A" to retry just because transaction "B" committed a change to the maximum value. It can be safely and correctly computed again based on the latest contents of the collection.

When ref-set or alter is used and another transaction has committed a change to the Ref since the current transaction try began, the current transaction will be retried. When commute is used, the current transaction will continue and the in-transaction value of the Ref will be passed to the function that is passed to commute. This results in better performance because retries aren't required.

The functions and arguments passed to commute during a single transaction execution are saved in a sorted map. The keys in the map are Ref objects and the values are lists of objects that describe the functions and their arguments. The map is sorted based on the order in which the Ref objects were created. When the transaction is committing, a write lock is acquired for each Ref in the map in sorted order and all its commute functions are called a second time to determine the Ref values that will be committed. Obtaining the write locks in this sorted order prevents deadlocks that might otherwise occur if multiple transactions attempt to commit their changes at the same time. The Ref values passed to the commute functions this time depend on whether another transaction has committed a new value since the current transaction try started. If so then the newest committed values are used. Otherwise, the in-transaction value is used. This means the values passed to the commute functions can differ from the values passed the first time they are called.

Within a transaction, a Ref cannot be set to a new value using ref-set or alter after commute has been called on it.

Sometimes it is desirable to prevent other transactions from changing the value of a Ref that will be read by the current transaction, or perhaps modified later in the current transaction. (An example is preventing write skew which is discussed later.) This is achieved by calling ensure on the Ref. While this guarantees that no other transaction can modify the Ref, it doesn't guarantee that the current transaction will be able to modify it. This is because any number of transactions can call ensure on the same Ref.

The following table is useful for selecting between Atoms, Agents and Refs when creating mutable variables. The word "coordinated" here means managed by a transaction.

Clojure Validators and Watchers

Before diving into the implementation details of Clojure STM, it is important to have a basic understanding of some features of Clojure that are related to the implementation.

Validators are functions that are invoked whenever the value of a given reference type object is being modified. If the function determines that the change isn't "valid", it can return false or throw an exception to prevent the change from occurring. Each reference type object can have only one validator function. The set-validator! function assigns a validator function to a reference object.

There are two mechanisms for being notified when the value of a reference object may have changed, watch functions and watcher Agents.

Watch functions must take four arguments which are an identifier "key", the reference object that may have changed, its old value and its new value. The key can be used to indicate the purpose of the watch or it can be any data to be made available to the watch function when it is invoked. Each reference object being watched can have a single watch function for each key value. A watch function is registered with a reference object by calling the add-watch function which takes the reference object, a key and a watch function. A watch function is removed from a reference object by calling the remove-watch function. which takes a reference object and a key.

Watcher Agents are notified that a reference object has changed by sending a given action to the Agent. The action function is passed the current value of the Agent and the reference object that changed, but not the old value. A watcher Agent is registered with a reference object by calling the add-watcher function which takes a reference object, a send type (which identifies the thread pool to be used), an Agent, and the action function to be sent. The add-watcher function creates an anonymous function that sends the action to the Agent and registers that with the reference object by passing it to the add-watch function. The Agent is used as the key. A watcher Agent is removed from a reference object by calling the remove-watcher function which takes the reference object and the Agent.

Clojure STM - High Level

This section describes the current Clojure STM implementation at a high level. Low level details are provided later in this article. The information is accurate as of Clojure 1.0 (git commit 94c4a6a on 8/3/2009), but is subject to change in the future. This article should not be viewed as a specification for Clojure STM.

It should be emphasized that understanding the details of the Clojure STM implementation is NOT required in order to use it successfully. Still, there are many reasons (listed in the goals of this article) that one might be interested in the details.

Currently Clojure is implemented by a combination of Java and Clojure source code. Nearly all the STM implementation is written in Java. An effort is underway to dramatically increase the amount that is implemented in Clojure. When that effort is complete, most or all of the code described in this and the next section will be discarded. It seems reasonable to speculate that the STM mechanisms will remain similar.

My intention is to update this article whenever the Clojure STM implementation changes so it remains an accurate source of information that is easier to digest than simply reading the source code.

Design

The Clojure STM implementation is based on multi-version concurrency control (MVCC) [16] and snapshot isolation [17]. The main difference between the standard definition of these concepts and the Clojure implementation is that Clojure works with in-memory values of variables instead of database tables, rows and columns. Wikipedia describes these concepts very well as follows. Parts related to databases are in square brackets. My clarifiations are in non-italic text.

"MVCC uses timestamps or increasing transaction IDs to achieve serializability. MVCC ensures a transaction never has to wait for a [database] object by maintaining several versions of an object. Each version would have a write timestamp and it would let a transaction read the most recent version of an object which precedes the transaction timestamp."

"If a transaction (Ti) wants to write to an object, and if there is another transaction (Tk) (that also wants to write it), the timestamp of Ti must precede the timestamp of Tk for the object write operation to succeed. Which is to say a write cannot complete if there are outstanding transactions with an earlier timestamp."

"Every object would also have a read timestamp, and if a transaction Ti wanted to write to object P, and the timestamp of that transaction is earlier than the object's read timestamp, the transaction Ti is aborted and restarted. Otherwise, Ti creates a new version of P and sets the read/write timestamps of P to the timestamp of the transaction." (The Clojure STM implementation does not use read timestamps.)

"The obvious drawback to this system is the cost of storing multiple versions of objects [in the database]. On the other hand reads are never blocked, which can be important for workloads mostly involving reading values [from the database]. MVCC is particularly adept at implementing true snapshot isolation, something which other methods of concurrency control frequently do either incompletely or with high performance costs."

"A transaction executing under snapshot isolation appears to operate on a personal snapshot [of the database], taken at the start of the transaction. When the transaction concludes, it will successfully commit only if the values updated by the transaction have not been changed externally since the snapshot was taken."

An issue with snapshot isolation is that it allows write skew . This happens when concurrent transactions read common sets of data and make changes to different data within that set and there are constraints on the data.

For example, suppose a town places a restriction (constraint) on the total number of dogs and cats that a family can own. Let's say the limit is three. When a person obtains a new dog or cat, they are entered in a database. John and his wife Mary have one dog and one cat. John adopts another dog while at the same time Mary adopts a cat. These transactions occur concurrently. Remember that transactions only see changes made by other transactions that have committed. John's transaction attempts to modify the number of dogs they own. The constraint isn't violated because they now have a total of three. Mary's transaction attempts to modify the number of cats they own. Like in the other transaction, the constraint isn't violated because they now have a total of three. Both transactions are allowed to commit, resulting in a total of four dogs and cats which violates the constraint. This is permitted because neither transaction attempts to commit a change to data that is being modified by another concurrent transaction.

Clojure provides a mechanism for avoiding write skew. See the ensure function discussed later.

Transaction Creation

In Clojure an STM transaction is created by passing any number of expressions, called the body, to the dosync macro (defined in src/clj/clojure/core.clj). This greatly simplifies coding for concurrency over using explicit locks. It is not necessary to indicate which Refs might be modified in the transaction. However, developers still need to make good decisions about what code should be inside it a dosync call, based on the set of Refs that need to be in a consistent state while the body executes.

Java Concurrency

The current Clojure STM implementation utilizes several Java concurrency classes. These include:

• java.util.concurrent.AtomicInteger
• java.util.concurrent.AtomicLong
• java.util.concurrent.Callable
• java.util.concurrent.CountDownLatch
• java.util.concurrent.TimeUnit
• java.util.concurrent.locks.ReentrantReadWriteLock

LockingTransaction and Ref Classes

The main classes in the Clojure STM implementation are LockingTransaction and Ref, both in the clojure.lang package. Both are located in the src/jvm/clojure/lang directory. UML class diagrams showing the attributes and methods of those classes and related classes appear below. It will be useful to refer to these diagrams often while reading the remainder of this article.

The dosync macro call that wraps each transaction body calls the sync macro which calls the LockingTransaction static method runInTransaction. The sync macro passes body of the transaction to runInTransaction as an anonymous function. Each thread has one LockingTransaction object, maintained as a ThreadLocal variable. If a LockingTransaction object hasn't yet been created for the current thread then one is created. If the current thread is already running a transaction then the anonymous function is called inside it, i.e., transactions compose. Otherwise a new transaction is started and the function is called inside it.

Transaction Status

The status of a transaction is always one of the following five values:

• RUNNING
• COMMITTING
• RETRY
• KILLED
• COMMITTED

The meaning of each of these status values is self evident, except perhaps RETRY and KILLED.

When the status is RETRY, the transaction will attempt a retry but hasn't started the next try yet. When that occurs, the status changes to RUNNING.

There are two situations that cause the status of a transaction to be set to KILLED. The first is when the abort method is called on a transaction. That sets the status to KILLED and throws an AbortException which causes the transaction to stop without retrying. (In the current version of Clojure, no code calls abort.) The second is when the barge method (see the section "Barging" below) is called on a transaction. That sets the status to KILLED and allows the transaction to retry.

Committed Values

Each Ref object maintains a chain of its committed values (history) in its tvals field. The length of the chain is controlled by the fields minHistory and maxHistory. These default to zero and ten, respectively, but can differ for each Ref object. Other values can be specified when Refs are created by passing options to the ref function. They can also be modified using the ref-min-history and ref-max-history functions. See the section "Faults" below to learn why the chain length matters.

Locks

Each Ref object has a ReentrantReadWriteLock. Any number of concurrent transactions can hold its read lock OR a single transaction can hold its write lock. The only time one of these locks is held for the duration of a transaction is when ensure is called on a Ref. In that case the transaction will hold the read lock until either the Ref is modified in the transaction or the transaction commits. There is no circumstance under which a write lock will be held for the duration of a transaction. Write locks are obtained only briefly when certain things occur during a transaction and then quickly released. They are acquired again when the transaction commits and then released when the commit completes. For more details on how these ReentrantReadWriteLocks are used, see the "Clojure STM - Low Level" section which describes the lock field in Ref class.

Calling ref-set or alter on a Ref gives it an in-transaction value that isn't seen by other transactions until the transaction commits. This also sets the tinfo field of the Ref to refer to an object that describes the transaction that modified the Ref, including the order in which it started relative to others and its current status. This is how one transaction knows that another one has modified a Ref and hasn't yet committed. Think of this like giving the Ref a ticket for admission into the commit party that will hopefully happen later. A Ref cannot have a ticket for more than one of these parties. For more details on how the tinfo field of a Ref is set, see the "Clojure STM - Low Level" section which describes the lock method in the LockingTransaction class.

In-transaction Values

Each LockingTransaction object maintains a map of in-transaction values for the Refs it has modified in its vals field. The keys in this map are Ref objects and the values are the java.lang.Object values of the Refs. If a Ref is only read inside a transaction, its value is always retrieved from the tvals chain. This requires walking the chain to find the newest value that was committed before the current transaction started. This can make it inefficient to dereference a Ref multiple times in a transaction unless it is modified before the second dereference. The first time a Ref is modified in transaction, its new value is placed in the vals map. For the remainder of the transaction, its value is retrieved from the vals map.

Faults

A "fault" occurs when there is an attempt to read the value of a Ref inside a transaction, but the Ref has no in-transaction value and all the values in its chain of committed values were committed after the current transaction began. This can happen when other transactions have committed a change to the Ref since the current transaction try began. When a fault occurs, the transaction will retry. When a transaction commits a change to a Ref that has experienced a fault in another transaction AND the chain is shorter than maxHistory, a new node is added to the chain of committed values for the Ref. This also happens if the chain is shorter than minHistory. Lengthing the chain reduces the likelihood that another fault will occur for the Ref in the future. If no fault has occurred for Ref, instead of adding a new node, the last node in the chain becomes the first and it is modified to describe the newly committed value.

It should be clear from the discussion above that the length of the history chain for each Ref can differ. The chains adapt based on the faults that occur. If a fault never occurs for a given Ref and it has a minHistory of zero (the default) then the length of its chain will never exceed one. These chains never become shorter. After a fault causes a chain to grow, it either remains at that length or grows even longer when more faults occur.

Barging

The term "barge" is used to describe the process of determining whether a given transaction should retry while the current transaction continues. When one transaction attempts to barge another, it will only succeed if three conditions are met. First, the transaction doing the barge must have been running for at least 1/100th of a second (see the BARGE_WAIT_NANOS constant). Second, this transaction must have started before the transaction to be barged. This means older transactions are favored over newer ones. Third, the status of the other transaction must be RUNNING and must be successfully changed to KILLED. The check of the transaction status and changing it are done atomically. The last condition means that if the other transaction is in the process of committing (status = COMMITTING) its changes, it will not be barged.

Retries

When a transaction retries, all the in-transaction changes it has made to Refs are discarded and execution returns to the beginning of the transaction body. There are many scenarios that can cause a transaction to retry. Each is described below.

1. The ref-set or alterfunction is called on a Ref. This causes an attempt to "lock" the Ref, but one of the following situations occur:
   • A write lock cannot be obtained for the Ref because another thread holds a read or write lock for the Ref.
   • A change to the Ref has been committed since the current transaction try started.
   • Another transaction has made an in-transaction change to the Ref that hasn't been committed yet and an attempt to barge the other transaction fails.
2. An attempt is made to read the value of a Ref inside a transaction (i.e., dereference it), but one of the following situations occur:
   • Another transaction has barged the current one.
   • The Ref has no in-transaction value yet, and a fault occurs. This means the chain of committed values for the Ref doesn't contain a value that was committed before the current transaction began.
3. The ref-set, alter, commute or ensure function is called on a Ref, but another transaction has barged the current one.
4. The current transaction is committing its changes, but another running transaction has an in-transaction change and an attempt to barge it fails.

A transaction won't retry indefinitely. There is a limit that is specified by the RETRY_LIMIT constant in the LockingTransaction class. It is currently set to 10,000. This is used in the retry loop inside the run method in the LockingTransaction class. If it is exceeded then a generic Exception object is thrown.

Retries are triggered by throwing a RetryEx which is a custom subclass of java.lang.Error defined in LockingTransaction.java. It extends Error instead of Exception so that it won't be caught by user code that simply catches Exception. The retry loop contains a try block with a catch for RetryEx. The catch simply allows execution to return to the top of the loop. No other kinds of exceptions are caught, so they cause the retry loop to exit.

IllegalStateException

An IllegalStateException is thrown from many methods in the Clojure implementation. When thrown inside a transaction, the transaction will not retry. Those related to STM are thrown when the following occur:

• An attempt is made to get the LockingTransaction for the current thread, but it hasn't been created yet or it isn't running. This happens when any of the following functions are called outside a transaction: ref-set, alter, commute or ensure.
• An attempt is made to get the value of Ref, but no value has been bound to it yet (like an uninitialized variable).
• An attempt is made to set the in-transaction value of a Ref using ref-set or alter, but the commute function has already been called on the Ref in the current transaction.
• A validation function for a Ref either returns false or throws an exception.

Deadlocks, Livelocks and Race Conditions

The Clojure STM implementation guarantees that deadlocks, livelocks and race conditions will not occur.

In the context of multithreaded software applications, these terms can be described as follows. A deadlock occurs when concurrently running threads cannot proceed because they are each waiting on a resource for which another has acquired exclusive access. A livelock occurs when concurrently running threads are performing work (as opposed to be being blocked, waiting on resources), but cannot complete due to something that other threads have done or not done. A race condition occurs when the outcome of a thread is affected by the timing of changes to shared state made by another concurrently running thread.

In Clojure STM, this applies to modifying a Ref within a transaction. Suppose transactions A and B start in that order and are running concurrently. If they both attempt to modify the same Ref using ref-set or alter (write conflict), preference is given to transaction A because it has been running the longest (provided it has been running for a minimal amount of time). This avoids livelock that might occur if retries were based on the order in which refs are set. Transaction B will retry, possibly multiple times, and will be able to modify the Ref after transaction A commits its changes. When transaction B finally runs to completion, it will do so with a consistent view of the changes committed by transaction A.

When transactions modify Refs using commute, no write conflicts occurs. Deadlocks are avoided during the commit by obtaining write locks for the Refs in a consistent order (which is the order in which the Ref objects were created).

Clojure STM Overhead

Using STM instead of explicit locks adds processing overhead. This doesn't necessarily mean that the STM approach is slower. Since STM is optimistic and locks are pessimistic, it is possible for STM to provide better overall performance for some applications due to greater concurrency.

When a Ref that has not yet been modified inside a transaction is read inside the transaction, a value is selected from its chain of committed values. As long as no other transaction has committed a new value for the Ref since the current transaction began, this will be fast since the value used will be that of the first node in the chain. Otherwise some chain walking will take place.

The value of a Ref can only be modified inside a transaction. When this is done, there is overhead incurred to verify that a transaction is running. It also must verify that the commute function hasn't already been called on the Ref. (It wouldn't make sense to allow this because commute functions are called a second time during the commit and any other setting of the Ref wouldn't have any lasting effect after the transaction completes.) If this is the first time the Ref has been modified in the current transaction, there is overhead incurred in adding the Ref to a set of Refs that the transaction has modified and marking the Ref as being modified by the current transaction (see the description of the lock method in the next paragraph). Finally, the new value is added to the map of in-transaction values for the current transaction. Subsequent reads of the Ref inside the transaction will use the value from that map instead of selecting a value from the chain of committed values.

The lock method in the LockingTransaction class introduces overhead. This involves many steps that are summarized below:

1. If ensure was called earlier in this transaction try on the Ref then release the read lock for the Ref.
2. Attempt to acquire a write lock for the Ref. If it cannot be acquired then trigger a retry for the current transaction.
3. If another transaction has committed a change to the Ref since the current transaction try began then trigger a retry for the current transaction.
4. If another transaction has made an as-yet uncommitted change to the Ref, attempt to barge it. If that fails then trigger a retry for the current transaction.
5. Mark the Ref is marked as being locked by the current transaction by setting its tinfo field to refer to an Info object that describes the current transaction.
6. In any case, release the write lock for the Ref.

When the end of the transaction is reached, there is overhead incurred in committing the modified Refs, which makes their new, in-transaction values visible outside the current transaction. This involves many steps that are summarized below:

1. Change the status of the current transaction from RUNNING to COMMITTING.
2. Rerun any commute functions called on Refs in the transaction. This involves acquiring a write lock for each commuted Ref.
3. Acquire write locks for all other Refs modified in the transaction.
4. Call all the validate functions that were registered on the Refs that were modified. Retry the current transaction if any of them disapprove of a change.
5. Add a node to the chain of committed values, or modify an existing node, for each Ref to be modified (depending on faults, minHistory and maxHistory).
6. Create a Notify object for each Ref that was modified and has at least one registered watcher.
7. Change the status of the current transaction from COMMITTING to COMMITTED.
8. Release all the write locks acquired previously.
9. Release all the read locks still held due to calls to ensure.
10. Clear the locked (local), ensures, vals, sets and commutes collections in preparation for the next retry or new transaction in the current thread.
11. If the commit was successful, notify all registered watchers of the changes using data in the Notify objects and dispatch all actions sent to Agents in the transaction.
12. Clear the notify (local) and actions collections in preparation for the next retry or new transaction in the current thread.
13. Return the value of the last expression in the transaction body.

Clojure STM - Low Level

It is not necessary to learn the details presented in this section in order to effectively use Clojure STM. However, this information will be very useful to anyone that wishes to:

• understand exactly what is happening at runtime in Clojure STM
• read the source code for the Clojure STM implementation
• suggest improvements to Clojure STM
• add features to the Clojure STM
• compare the Clojure STM implementation to that of another language
• create an STM implementation for another language

Feel free to skip to the "Conclusion" section near the end if you don't have a need for additional detail.

While reading about the low-level details of the Clojure STM implementation, refer to the earlier class diagrams to aid with understanding the relationships between the many related classes and interfaces. It is also helpful to look at the source code in core.clj, ARef.java, Ref.java and LockingTransaction.java while reading this section.

STM Macros

These macros are defined in src/clj/clojure/core.clj.

STM Functions

These functions are defined in src/clj/clojure/core.clj. The alter, commute, ensure and ref-set functions must be called inside a transaction, i.e., inside a call to the dosync macro. When the phrase "in-transaction value" is used below it means either the in-transaction value if there is one or the newest committed value before the transaction try began.

ARef Fields

The ARef class is defined in src/jvm/clojure/lang/ARef.java. It is the superclass of the Ref class.

ARef Methods

Ref Nested Classes

The Ref class is defined in src/jvm/clojure/lang/Ref.java. It is a subclass of the ARef class.

One static nested class is defined inside the clojure.lang.Ref class.

TVal Fields

Ref Fields

All fields in the Ref class are package level, so LockingTransaction objects can directly access them.

Ref Methods

The methods in the Ref class that play a significant role in the STM implementation are described below.

LockingTransaction Constants

The LockingTransaction class is defined in src/jvm/clojure/lang/LockingTransaction.java.

LockingTransaction Nested Classes

These are static nested classes defined inside the LockingTransaction class.

CFn Fields

Info Fields

Notify Fields

LockingTransaction Fields

All fields in the LockingTransaction class are package level. However, in the current version of Clojure no other classes extend LockingTransaction and no other classes in the same package directly access its fields.

LockingTransaction Methods

The methods in the LockingTransaction class that play a significant role in the STM implementation are described below.

Conclusion

STM implementations are somewhat complicated. However, developing applications that use STM is less complicated and easier to get correct than using a lock-based approach. It seems likely that over time using STM will become as common and trusted as using garbage collection is today.

Watch for updates to this article as the Clojure STM implementation improves, eventually being replaced by an implementation written in Clojure instead of Java.

References

• [1] my STM site
  https://objectcomputing.com/mark/stm/
• [2] my SETT article: Clojure - Functional Programming for the JVM
• [3] Wikipedia Actor Model entry
  http://en.wikipedia.org/wiki/Actor_model
• [4] Wikipedia STM entry
  http://en.wikipedia.org/wiki/Software_transactional_memory
• [5] Wikipedia deadlock entry
  http://en.wikipedia.org/wiki/Deadlock
• [6] Wikipedia livelock entry
  http://en.wikipedia.org/wiki/Deadlock#Livelock
• [7] Wikipedia race condition entry
  http://en.wikipedia.org/wiki/Race_condition
• [8] The Transactional Memory / Garbage Collection Analogy
  paper by Dan Grossman
  http://www.cs.washington.edu/homes/djg/papers/analogy_oopsla07.pdf
• [9] Software Engineering Radio podcast on STM and Garbage Collection
  http://www.se-radio.net/podcast/2007-09/episode-68-dan-grossman-garbage-collection-and-transactional-memory
• [10] State, You're Doing It Wrong
  slides by Jonas Boner
  http://jonasboner.com/talks/state_youre_doing_it_wrong/html/all.html
• [11] Software Transactional Memory Should Not Be Obstruction-Free
  paper by Robert Ennals
  http://www.acc.ncku.edu.tw/chinese/faculty/shulc/courses/adb/transactional-memory/notlockfree.pdf
• [12] Clojure: STMs vs Locks
  discussion with Cliff Click, Rich Hickey and others
  http://blogs.azulsystems.com/cliff/2008/05/clojure-stms-vs.html
• [13] Clojure main site - http://clojure.org
• [14] Persistent data structures
  http://en.wikipedia.org/wiki/Persistent_data_structures
• [15] STM implementations
  http://en.wikipedia.org/wiki/Software_transactional_memory#Implementations
• [16] Multi-version concurrency control (MVCC)
  http://en.wikipedia.org/wiki/Multiversion_concurrency_control
• [17] Snapshot isolation
  http://en.wikipedia.org/wiki/Snapshot_isolation