January 2010

Volume 25 Number 01

The Polyglot Programmer - ACID Transactions with STM.NET

By Ted Neward | January 2010

While this column has focused specifically on programming languages, it’s interesting to note how language ideas can sometimes bleed over into other languages without directly modifying them.

One such example is the Microsoft Research language C-Omega (sometimes written Cw, since the Greek omega symbol looks a lot like a lower-case w on the US keyboard layout). In addition to introducing a number of data- and code-unifying concepts that would eventually make their way into the C# and Visual Basic languages as LINQ, C-Omega also offered up a new means of concurrency called chords that later made it into a library known as Joins. While Joins hasn’t, as of this writing, made it into a product (yet), the fact that the whole chords concept of concurrency could be provided via a library means that any run-of-the-mill C# or Visual Basic (or other .NET language) program could make use of it.

Another such effort is the Code Contracts facility, available from the Microsoft DevLabs Web site and discussed in the August 2009 issue of MSDN Magazine. Design-by-contract is a language feature that was prominent in languages like Eiffel, and originally came to .NET through the Microsoft Research language Spec#. Similar kinds of contractual guarantee systems have come through Microsoft Research as well, including one of my favorites, Fugue, which made use of custom attributes and static analysis to provide correctness-checking of client code.

Once again, although Code Contracts hasn’t shipped as a formal product or with a license that permits its use in production software, the fact that it exists as a library rather than as a standalone language implies two things. First, that it could (in theory) be written as a library by any .NET developer sufficiently determined to have similar kinds of functionality. And second, that (assuming it does ship) said functionality could be available across a variety of languages, including C# and Visual Basic.

If you’re sensing a theme, you’re right. This month I want to focus on yet another recently announced library that comes from the polyglot language world: software transactional memory, or STM. The STM.NET library is available for download via the DevLabs Web site, but in stark contrast to some of the other implementations I’ve mentioned, it’s not a standalone library that gets linked into your program or that runs as a static analysis tool—it’s a replacement and supplement to the .NET Base Class Library as a whole, among other things.

Note, however, that the current implementation of STM.NET is not very compatible with current Visual Studio 2010 betas, so the usual disclaimers about installing unfinished/beta/CTP software on machines you care about applies doubly so in this case. It should install side-by-side with Visual Studio 2008, but I still wouldn’t put it on your work machine. Here’s another case where Virtual PC is your very good friend.

Beginnings

The linguistic background of STM.NET comes from a number of different places, but the conceptual idea of STM is remarkably straightforward and familiar: rather than forcing developers to focus on the means of making things concurrent (focusing on locks and such), allow them to mark which parts of the code should execute under certain concurrency-friendly characteristics, and let the language tool (compiler or interpreter) manage the locks as necessary. In other words, just as database admins and users do, let the programmer mark the code with ACID-style transactional semantics, and leave the grunt work of managing locks to the underlying environment.

While the STM.NET bits may appear to be just another attempt at managing concurrency, the STM effort represents something deeper than that—it seeks to bring all four qualities of the database ACID transaction to the in-memory programming model. In addition to managing the locks on the programmer’s behalf, the STM model also provides atomicity, consistency, isolation and durability, which of themselves can make programming much simpler, regardless of the presence of multiple threads of execution.

As an example, consider this (admittedly wildly overused) pseudocode example:

BankTransfer(Account from, Account to, int amount) {
  from.Debit(amount);
  to.Credit(amount);
}

What happens if the Credit fails and throws an exception? Clearly the user will not be happy if the debit to the from account still remains on the record when the credit to the account isn’t there, which means now the developer has some additional work to do:

BankTransfer(Account from, Account to, int amount) {
  int originalFromAmount = from.Amount;
  int originalToAmount = to.Amount;
  try {
    from.Debit(amount);
    to.Credit(amount);
  }
  catch (Exception x) {
    from.Amount = originalFromAmount;
    to.Amount = originalToAmount;
  }
}

This would seem, at first blush, to be overkill. Remember, however, that depending on the exact implementation of the Debit and Credit methods, exceptions can be thrown before the Debit operation completes or after the Credit operation completes (but doesn’t finish). That means the BankTransfer method must ensure that all data referenced and used in this operation goes back to exactly the state it was in when the operation began.

If this BankTransfer gets at all more complicated—operating on three or four data items at once, for example—the recovery code in the catch block is going to get really ugly, really quickly. And this pattern shows up far more often than I’d like to admit.

Another point worth noting is isolation. In the original code, another thread could read an incorrect balance while it was executing and corrupt at least one of the accounts. Further, if you simply slapped a lock around it, you could deadlock if the from/to pairs were not always ordered. STM just takes care of that for you without using locks.

If, instead, the language offered some kind of transactional operation, such as an atomic keyword that handled the locking and failure/rollback logic under the hood, just as BEGIN TRANSACTION/COMMIT does for a database, coding the BankTransfer example becomes as simple as this:

BankTransfer(Account from, Account to, int amount) {
  atomic {
    from.Debit(amount);
    to.Credit(amount);
  }
}

You have to admit, this is a lot less to worry about.

The STM.NET approach, however, being library based, isn’t going to get quite this far since the C# language doesn’t allow quite that degree of syntactic flexibility. Instead, you’re going to be working with something along the lines of:

public static void Transfer(
  BankAccount from, BankAccount to, int amount) {
  Atomic.Do(() => {
    // Be optimistic, credit the beneficiary first
    to.ModifyBalance(amount);
    from.ModifyBalance(-amount);
  });
}

Insights: It’s Really a Language Change

In the course of reviewing Neward’s column, one thing jumped out at me as being, unfortunately, a basic misinterpretation. Neward tries to divide language extensions into those that require language changes and those that are (purely) library changes. It tries to classify STM.NET as the latter—a library-only change—whereas I would argue it most decidedly is not.

A library-only extension is one that is implementable completely in the existing language. Library-based STM systems do exist; these generally require that the data that should have transactional semantics be declared of some special type, such as “TransactionalInt”. STM.NET is not like that—it provides transactional semantics for ordinary data transparently, simply by virtue of being accessed within the (dynamic) scope of a transaction.

This requires every read and write occurring in code that is executed within the transaction to be modified to make additional associated calls that acquire necessary locks, create and populate shadow copies, and so on. In our implementation, we modified the CLR’s JIT compiler extensively to produce very different code to be executed within transactions. The atomic keyword (even if we’ve presented it via a delegate-based API) changes the language semantics at a pretty fundamental level.

Thus, I claim that we did change the language. In a .NET language like C#, the language semantics are implemented by a combination of the source-level language compiler, and its assumptions about the semantics of the MSIL that it emits—how the CLR runtime will execute that IL. We radically changed the CLR’s interpretation of the bytecodes, so I would say that this changes the language.

In particular, say the CLR’s JIT compiler encounters code like this:

try {
 <body> 
} 
catch (AtomicMarkerException) {}

The code within <body> (and, recursively, within methods it calls) is dynamically modified to ensure transactional semantics. I should emphasize that this has absolutely nothing to do with exception handling—it is purely a hack to identify an atomic block, since the try/catch construct is the only mechanism available in IL for identifying a lexically scoped block. In the long run, we would want something more like an explicit “atomic” block in the IL language. The delegate-based interface is implemented in terms of this ersatz atomic block.

In summary, the IL-level atomic block, however expressed, really does change the semantics of code that runs in it in a fundamental way. This is why STM.NET contains a new, significantly modified CLR runtime, not just changes to the BCL. If you took a stock CLR runtime and ran with the BCL from STM.NET, the result would not give you transactional semantics (in fact, I doubt it would work at all).

 —Dr. Dave Detlefs, Architect, Common Language Runtime, Microsoft

The syntax isn’t quite as elegant as an atomic keyword would be, but C# has the power of anonymous methods to capture the block of code that would make up the body of the desired atomic block, and it can thus be executed under similar kinds of semantics. (Sorry, but as of this writing, the STM.NET incubation effort only supports C#. There is no technical reason why it couldn’t be extended to all languages, but the STM.NET team only focused on C# for the first release.)

Getting Started with STM.NET

The first thing you’ll need to do is download the Microsoft .NET Framework 4 beta 1 Enabled to use Software Transactional Memory V1.0 bits (a long-winded name, which I’ll shorten to STM.NET BCL, or just STM.NET) from the DevLabs Web site. While you’re there, download the STM.NET Documentation and Samples as well. The former is the actual BCL and STM.NET tools and supplemental assemblies, and the latter contains, among the documentation and sample projects, a Visual Studio 2008 template for building STM.Net applications.

Creating a new STM.NET-enabled application begins like any other app, in the New Project dialog (see Figure 1). Selecting the TMConsoleApplication template does a couple of things, some of which aren’t entirely intuitive. For example, as of this writing, to execute against the STM.NET libraries, the .NET application’s app.config requires this little bit of versioning legerdemain:

<?xml version="1.0" encoding="utf-8" ?> 
<configuration> 
  <startup> 
    <requiredRuntime version="v4.0.20506"/> 
  </startup>
  ... 
</configuration>

Figure 1 Starting a New Project with the TMConsoleApplication Template

Other settings will be present, but the requiredRuntime value is necessary to tell the CLR launcher shim to bind against the STM.NET version of the runtime. In addition, the TMConsoleApplication template binds the assembly against versions of the mscorlib and System.Transactions assemblies installed in the directory where STM.NET is installed, rather than the versions that come with the stock .NET Framework 3.0 or 3.5 CLR. This is necessary, when you think about it, because if STM.NET is going to provide transactional access for anything beyond just the code that you write, it’s going to need to use its own copy of mscorlib. Plus, if it’s going to interact correctly with other forms of transactions—such as the lightweight transactions provided by the Lightweight Transaction Manager (LTM)—it needs to have its own version of System.Transactions as well.

Other than that, an STM.NET application will be a traditional .NET application, written in C# and compiled to IL, linked against the rest of the unmodified .NET assemblies, and so on. STM.NET assemblies, like the COM+ and EnterpriseServices components of the last decade, will have a few more extensions in them describing transactional behaviors for the methods that interact with the STM.NET transactional behavior, but I’ll get to that in time.

Hello, STM.NET

As with the Axum example in the September 2009 issue of MSDN Magazine, writing a traditional Hello World application as the starting point for STM.NET is actually harder than you might think at first, largely because if you write it without concern for transactions, it’s exactly the same as the traditional C# Hello World. If you write it to take advantage of the STM.NET transactional behavior, you have to consider the fact that writing text to the console is, in fact, an un-undoable method (at least as far as STM.NET is concerned), which means that trying to roll back a Console.WriteLine statement is difficult.

So, instead, let’s take a simple example from the STM.NET User Guide as a quick demonstration of the STM.NET bits. An object (called MyObject) has two private strings on it and a method to set those two strings to some pair of values:

class MyObject {
  private string m_string1 = "1";
  private string m_string2 = "2";

  public bool Validate() {
    return (m_string1.Equals(m_string2) == false);
  }
  public void SetStrings(string s1, string s2) {
    m_string1 = s1;
    Thread.Sleep(1);   // simulates some work 
    m_string2 = s2;
  }
}

Because the assignment of the parameter to the field is itself an atomic operation, there’s no concern around concurrency there. But just as with the BankAccount example shown earlier, you want either both to be set or neither, and you don’t want to see partial updates—one string being set, but not the other—during the set operation. You’ll spawn two threads to blindly set the strings over and over again, and a third thread to validate the contents of the MyObject instance, reporting a violation in the event Validate returns false (see Figure 2).

Figure 2 Manually Validating Atomic Updates to MyObject

[AtomicNotSupported]
static void Main(string[] args) {
  MyObject obj = new MyObject();
  int completionCounter = 0; int iterations = 1000;
  bool violations = false;

  Thread t1 = new Thread(new ThreadStart(delegate {
    for (int i = 0; i < iterations; i++)
      obj.SetStrings("Hello", "World");
    completionCounter++;
  }));

  Thread t2 = new Thread(new ThreadStart(delegate {
    for (int i = 0; i < iterations; i++)
      obj.SetStrings("World", "Hello");
    completionCounter++;
  }));

  Thread t3 = new Thread(new ThreadStart(delegate {
    while (completionCounter < 2) {
      if (!obj.Validate()) {
        Console.WriteLine("Violation!");
        violations = true;
      }
    }
  }));

  t1.Start(); t2.Start(); t3.Start();
  while (completionCounter < 2)
    Thread.Sleep(1000);

  Console.WriteLine("Violations: " + violations);
...

Note that the way this example is constructed, validation fails if the two strings in obj are set to the same thing, indicating that Thread t1’s SetStrings(“Hello”, “World”) is partially updated (leaving the first “Hello” to match the second “Hello” set by t2).

A cursory glance at the SetStrings implementation shows that this code is hardly thread-safe. If a thread switch occurs in the middle (which is likely given the Thread.Sleep call, which will cause the currently-executing thread to give up its time slice), another thread could easily jump into the middle of SetStrings again, putting the MyObject instance into an invalid state. Run it, and with enough iterations, violations will start to appear. (On my laptop, I had to run it twice before I got the violations, proving that just because it runs without an error once doesn’t mean the code doesn’t have a concurrency bug.)

Modifying this to use STM.NET requires only a small change to the MyObject class, as shown in Figure 3.

Figure 3 Validating MyObject with STM.NET

class MyObject {
  private string m_string1 = "1";
  private string m_string2 = "2";

  public bool Validate() {
    bool result = false;
    Atomic.Do(() => { 
      result = (m_string1.Equals(m_string2) == false);
    });
    return result;
  }

  public void SetStrings(string s1, string s2) {
    Atomic.Do(() => {
      m_string1 = s1;
      Thread.Sleep(1); // simulates some work 
      m_string2 = s2;
    });
  }
}

As you can see, the only modification required was to wrap the bodies of Validate and SetStrings into atomic methods using the Atomic.Do operation. Now, when run, no violations appear.

Transactional Affinity

Observant readers will have noticed the [AtomicNotSupported] attribute at the top of the Main method in Figure 2, and perhaps wondered at its purpose, or even wondered if it served the same purpose as those attributes from the COM+ days. As it turns out, that’s entirely correct: the STM.NET environment needs some assistance in understanding whether methods called during an Atomic block are transaction-friendly so that it can provide the necessary and desirable support for those methods.

Three such attributes are available in the current STM.NET release:

• AtomicSupported—the assembly, method, field or delegate supports transactional behavior and can be used inside or outside of atomic blocks successfully.
• AtomicNotSupported—the assembly, method, field or delegate doesn’t support transactional behavior and thus shouldn’t be used inside of atomic blocks.
• AtomicRequired—the assembly, method, field or delegate not only supports transactional behavior, it should only be used inside of atomic blocks (thus guaranteeing that using this item will always be done under transactional semantics).

Technically there is a fourth, AtomicUnchecked, which signals to STM.NET that this item shouldn’t be checked, period. It’s intended as an escape hatch to avoid checking the code altogether.

The presence of the AtomicNotSupported attribute is what leads the STM.NET system to throw an AtomicContractViolationException when the following (naïve) code is attempted:

[AtomicNotSupported]
static void Main(string[] args) {
  Atomic.Do( () => {
    Console.WriteLine("Howdy, world!");
  });

  System.Console.WriteLine("Simulation done");
}

Because the System.Console.WriteLine method is not marked with AtomicSupported, the Atomic.Do method throws the exception when it sees the call in the atomic block. This bit of security ensures that only transaction-friendly methods are executed inside of the atomic block, and provides that additional bit of safety and security to the code.

Hello, STM.NET (Part Two)

What if you really, really want to write the traditional Hello World? What if you really want to print a line to the console (or write to a file, or perform some other non-transactional behavior) alongside two other transactional operations, but only print it out if both of those other operations succeed? STM.NET offers three ways to handle this situation.

First, you can perform the non-transactional operation outside the transaction (and only after the transaction commits) by putting the code inside of a block passed to Atomic.DoAfterCommit. Because the code inside that block will typically want to use data generated or modified from inside the transaction, DoAfterCommit takes a context parameter that is passed from inside the transaction to the code block as its only parameter.

Second, you can create a compensating action that will be executed in the event that the transaction ultimately fails, by calling Atomic.DoWithCompensation, which (again) takes a context parameter to marshal data from inside the transaction to the committing or compensating block of code (as appropriate).

Third, you can go all the way and create a Transactional Resource Manager (RM) that understands how to participate with the STM.NET transactional system. This is actually less difficult than it might seem—just inherit from the STM.NET class TransactionalOperation, which has OnCommit and OnAbort methods that you override to provide the appropriate behavior in either case. When using this new RM type, call OnOperation at the start of your work with it (effectively enlisting the resource into the STM.NET transaction). Then call FailOperation on it in the event that the surrounding operations fail.

Thus, if you want to transactionally write to some text-based stream, you can write a text-appending resource manager like the one shown in Figure 4. This then allows you—in fact, by virtue of the [Atomic-Required] attribute, requires you—to write to some text stream via the TxAppender while inside an atomic block (see Figure 5).

Figure 4 A Transactional Resource Manager

public class TxAppender : TransactionalOperation {
  private TextWriter m_tw;
  private List<string> m_lines;

  public TxAppender(TextWriter tw) : base() {
    m_tw = tw;
    m_lines = new List<string>();
  }

  // This is the only supported public method
  [AtomicRequired]
  public void Append(string line) {
    OnOperation();

    try {
      m_lines.Add(line);
    }
    catch (Exception e) {
      FailOperation();
      throw e;
    }
  }

  protected override void OnCommit() {
    foreach (string line in m_lines) {
      m_tw.WriteLine(line);
    }
    m_lines = new List<string>();
  }

  protected override void OnAbort() {
    m_lines.Clear();
  }
}

Figure 5 Using TxAppender

public static void Test13() {
  TxAppender tracer = 
    new TxAppender(Console.Out);
  Console.WriteLine(
    "Before transactions. m_balance= " + 
    m_balance);

  Atomic.Do(delegate() {
    tracer.Append("Append 1:  " + m_balance);
    m_balance = m_balance + 1;
    tracer.Append("Append 2:  " + m_balance);
  });
            
  Console.WriteLine(
    "After transactions. m_balance= " 
    + m_balance);

  Atomic.Do(delegate() {
    tracer.Append("Append 1:  " + m_balance);
    m_balance = m_balance + 1;
    tracer.Append("Append 2:  " + m_balance);
  });

  Console.WriteLine(
    "After transactions. m_balance= " 
    + m_balance);
}

This is obviously the longer route and will be suitable only in certain scenarios. It could fail for some kinds of media types, but for the most part, if all the actual irreversible behavior is deferred to the OnCommit method, this will suffice for most of your in-process transactional needs.

Putting STM.NET to Work

Working with an STM system takes a little getting used to, but once you’re acclimated, working without it can feel crippling. Consider some of the potential places where using STM.NET can simplify coding.

When working with other transacted resources, STM.NET plugs in to existing transacted systems quickly and easily, making Atomic.Do the sole source of transacted code in your system. The STM.NET examples demonstrate this in the TraditionalTransactions sample, posting messages to an MSMQ private queue and making it obvious that, when the Atomic block fails, no message is posted to the queue. This is probably the most obvious usage.

In dialog boxes—particularly for multi-step wizard processes or settings dialogs—the ability to roll back changes to the settings or dialog data members when the user hits the Cancel button is priceless.

Unit tests such as NUnit, MSTest, and other systems exert great effort to ensure that, when written correctly, tests cannot leak results from one test to the next. If STM.NET reaches production status, NUnit and MSTest can refactor their test case execution code to use STM transactions to isolate test results from each other, generating a rollback at the end of each test method, and thus eliminating any changes that might have been generated by the test. Even more, any test that calls out to an AtomicUnsupported method will be flagged at test execution time as an error, rather than silently leaking the test results to some medium outside the test environment (such as to disk or database).

STM.NET can also be used in domain object property implementation. Although most domain objects have fairly simple properties, either assigning to a field or returning that field’s value, more complex properties that have multiple-step algorithms run the risk of multiple threads seeing partial updates (if another thread calls the property during its set) or phantom updates (in the event another thread calls the property during its set, and the original update is eventually thrown away due to a validation error of some form).

Even more interesting, researchers outside of Microsoft are looking into extending transactions into hardware, such that someday, updating an object’s field or a local variable could be a transaction guarded at the hardware level by the memory chip itself, making the transaction blindingly fast in comparison to today’s methods.

However, as with Axum, Microsoft depends on your feedback to determine if this technology is worth pursuing and productizing, so if you find this idea exciting or interesting, or that it’s missing something important to your coding practice, don’t hesitate to let them know.                                  

Ted Neward is a Principal with Neward and Associates, an independent firm specializing in .NET and Java enterprise systems. He has written numerous books, is a Microsoft MVP Architect, INETA speaker, and PluralSight instructor. Reach Ted at ted@tedneward.com, or read his blog at blogs.tedneward.com.

Thanks to the following technical experts for reviewing this article:Dave Detlefs and Dana Groff