This is the second article in the GemStone 101 series. If you haven’t already done so, I recommend that you read GemStone 101: Transactions and Unlimited GemStone VMs in every Garage? ….and a Stone in every Pot before reading this post. It also wouldn’t hurt to take a gander at The Pillars of Concurrency for background on concurrency issues.
Today we’re going to delve a bit into the world of transaction conflicts. In GemStone/S a transaction conflict occurs when two or more sessions attempt to commit changes to the same object. A commit conflict is an error condition and in most cases you will end up aborting the transaction (for a discussion transaction conflicts in more detail read Chapter 6.1 in the GemStone/S Programming Guide). The best medicine for transaction conflicts is to avoid them.
[Updated: 3/17/2008] See GLASS 101: Simple Persistence for an alternative to conflict avoidance.
Avoiding transaction conflicts is really not that much different than dealing with concurrent access to a shared data structure in a single vm when multiple processes are running. In Squeak, you would simply protect shared data from concurrent access by using a Semaphore and a critical: block. In GemStone/S you can’t use Semaphores to protect persistent shared data, since each session is running in separate operating system processes (potentially on a different machine). You can, however, use object locks to control concurrent access to persistent shared data (See Chapter 6.3 in the GemStone/S Programming Guide for complete details on manipulating object locks).
Object locks are session based. Once a session obtains an object lock, other sessions will not be allowed to obtain a lock on the same object until the lock is released. For protecting access to shared data, you can arrange to release the lock on transaction boundaries (commit or abort), so that the access to the shared data is protected for the duration of the transaction.
If you are denied an object lock, you must wait for the lock to be released via polling or by using a variant of the object lock called an application lock. A request for an application lock will automatically block until the lock is available. Application locks are more convenient than standard object locks, but there are restrictions on the number of application locks that you can use.
Using a object lock on an object to protect access to shared data is a perfectly valid technique, but it should be used sparingly to avoid getting into potential deadlock situations and to avoid delays waiting for the lock to be released. Object locks are also relatively expensive to use, as they involve interaction with the stoned process.
Reduced Conflict Classes
As an alternative to using object locks to avoid transaction conflicts, GemStone/S provides a set of reduced conflict classes (See Chapter 6.4 in the GemStone/S Programming Guide for complete details on reduced conflict classes), that in many cases allow one to perform concurrent, conflict-free updates on the same object:
In GemStone/S, a transaction conflict occurs when the same object is modified by two different sessions, even when the modifications are not logically inconsistent. For example, adding two different objects to an IdentityBag is not logically inconsistent, but will result in a transaction conflict if performed by two different sessions.
The reduced conflict classes were added to GemStone/S to allow logically consistent updates to be made to the same object by different sessions, while avoiding transaction conflicts.
Logically inconsistent operations on reduced conflict classes will still result in a failed transaction. For example, two sessions adding the same key to a RcKeyValueDictionary is logically inconsistent and will result in a failed transaction.
Reduced conflict classes should be used as your first line of defense in avoiding transaction conflicts.
A separate object is allocated for tracking the contributions from each session. The value of the RcCounter is calculated when you request its value by traversing over the contributions for each session.
For RcQueue, entries are timestamped and added to a separate collection for each producer session. A consumer session then ‘removes’ the elements from the queue keeping track of the elements removed without actually removing them from the producer session’s collection. You can avoid conflicts under the following conditions:
- Any number of sessions read objects in the queue at the same time.
- Any number of sessions add objects to the queue at the same time.
- One session removes an object from the queue while any number of sessions are adding objects.
For RcIdentityBag, the contents are managed by keeping an ‘adds Bag’ and ‘removals Bag’ for each session. When you enumerate the contents, a cache of the bag (in transient session state) is created by adding and removing objects recorded for each session. You can avoid conflicts under the following conditions:
- Any number of sessions read objects in the bag at the same time.
- Any number of sessions add objects to the bag at the same time.
- One session removes an object from the bag while any number of sessions are adding objects.
- Any number of sessions remove objects from the bag at the same time, as long as no more than one of them tries to remove the last occurrence of an object.
For RcKeyValueDictionary, reduced conflict operation is achieved by recording adds and removes in a RedoLog. If a transaction conflict is encountered, objects within the dictionary are selectively aborted and the add and remove operations are replayed and a second commit is attempted. You can avoid conflicts under the following conditions:
- Any number of sessions read values in the dictionary at the same time.
- Any number of sessions add keys and values to the dictionary at the same time, unless a session tries to add a key that already exists.
- Any number of sessions remove keys from the dictionary at the same time, unless more than one session tries to remove the same key at the same time.
- Any number of users perform any combination of these operations.
Reduced Conflicts for Indexed Collections
In a future GemStone 101 article, I will go into a little more detail about indexed collections, suffice to say that if you need ordered access to, or need to perform queries on elements in a shared collection, you can use an RcIdentityBag with an RC equality index or two to reduce the likelihood of transaction conflicts.
Concurrency Control in Seaside
In GLASS we have modified the Seaside framework to use both object locks and reduced conflict classes to avoid transaction conflicts.
As I have written before, when a request comes into a GLASS vm, the framework does a beginTransaction before passing the HTTP request to the Seaside application code and the framework does a commitTransaction before passing the HTTP response to the user’s web browser.
Before we do the beginTransaction, we acquire a write lock on the WASession instance to ensure that no two vms are handling a request for the same WASession concurrently. The write lock is then released when the commitTransaction is performed. The object lock is the correct construct to use here, because the intent is to block other sessions from running concurrently. As an intended side effect, this also means that all session-specific data is protected from transaction conflicts.
Each WAApplication maintains a couple of handler dictionaries that are protected by a Semaphore in the standard Seaside code base. For GLASS, we use instances of the reduced conflict dictionary class RcKeyValueDictionary. In this case it isn’t necessary to completely block access to the dictionaries while they are updated. It is sufficient to ensure that the dictionaries are logically consistent at the end of the transaction – reduced conflict classes are the right answer in this case.
For the data structures (that aren’t already protected by the session lock) in your Seaside application, you can apply these tests to help decide what technique to use to avoid transaction conflicts:
- use write locks when concurrent updates to a data structure cannot be tolerated
- use reduced conflict classes when your usage pattern conforms to the restrictions imposed by the particular reduced conflict class