The Importance of Commutables

While developing the first more complicated tests for Shielded, at a time when the library had just the basics of transactional protection covered, I realized the importance of commutable operations for concurrency, even when not using an STM.

One of the most basic things a test needs – a counter of processed items – was automatically a horrible bottleneck. All the parallel transactions would read the current value, increment it, and store the result. But only one can succeed and write into the counter! All of them were in conflict with each other, fighting over that one field. The end result was that transactions would effectively execute serially. For an STM this meant a lot of useless repetitions, transactions working, then trying to make their commit, and then all but one of them failing and starting over. Not cool.

When using locks in a situation like this, the simplest approach is to wrap the counter incrementing together in the same lock block with the rest of your work, but you must use a global lock to protect a global counter, so then you also have pure serial code. Nobody (?) does that. Instead, you typically keep a more granular lock for the “payload” part of the job, and obtain a global counter lock just during incrementing. Or, if you know what you’re doing, you do this:

lock (itemLock)
{
<payload here>
Interlocked.Increment(ref _counter);
}

This works great. You leave your mark on the counter, regardless of how much competition you have. Perhaps you never noticed, but this works only because the individual increments are commutable – they can be freely reordered in time and still have the same net effect. With the introduction of a commutable, your transactions can now run in parallel (provided that they use different item locks). Congratulations, you’ve got pretty good concurrent code.

Naturally, I wanted to support this in Shielded. To be able to do something like this:

x.Commute((ref int n) => n++);

…and have the increment perform in parallel with other transactions, without causing your transaction to conflict with them. The main advantage of an STM is it’s simplicity of use, but not having something like this, and treating a simple, commutable increment as a conflict, makes it almost useless.

I had already encountered commutables in Clojure’s built-in STM. Clojure executes a commute under the global commit lock, by taking the value encountered in the field at that time and performing the op. This is perfectly safe – no one else is in that lock with you, no conflict possible, works great.

But, the Clojure implementation has two drawbacks. The first is, of course, running arbitrary code under the global lock. From my experience in experimenting with Shielded, small changes in time spent under that lock have noticeable effects on performance. The second drawback is more subtle, but maybe even more serious – if you read from the field after you have defined a commute op on it, Clojure throws an exception. The main advantage of STM, composability, is compromised – if you compose two operations into one, you better not compose one that commutes a field with another that reads from it. They work just fine by themselves, but together, boom.

In Shielded, I wanted to do this differently. For one thing, the commutes are executed just before entering the global lock! They will get a fresh reading stamp, so they can read the latest data, which reduces their chance of conflict. If they still conflict, only they get retried.

The other difference – if after defining a commute you read from that field, Shield detects this (as an STM, the library has to be notified of access to a field anyway) and automatically executes the commute sooner, right then and there, and you see it’s result. This guarantees safe composability. However, the commute is not a commute any more. It’s not a commutable increment if you know the result is 4. If another transaction jumps in and writes in 4 before you commit, your increment would be lost unless we repeat it. And since you read and used the number in your transaction, the entire transaction is compromised. The key is not to look – we can repeat just the commute, but only if it was not read.

Using Shielded, any kind of commutable operation can be defined, and the system takes care of consistency. If the rest of the transaction does not interfere with the operation, it will behave as a commute, minimizing conflicts. If the rest of the transaction does interfere, a commute is gracefully reduced into an ordinary part of your transaction, ensuring consistency.

For examples of various commutes, and how it all behaves in Shielded, check out the method ComplexCommute() in BasicTests.cs. You may notice how methods Append() and Clear() of a ShieldedSeq are both defined as commutables – they won’t conflict if you don’t read the sequence. That means no conflicts when adding things to queues.

Choosing the optimal granularity for locks, not forgetting to take a lock wherever it is needed, avoiding deadlocks – all of these problems disappear when using an STM. It just works, safely and consistently. And, with commutable operations support added in the mix, your code is automatically as concurrent as logically possible!