Transactional Objects

Every now and then, developers run into a situation where they need an in-memory object to participate in a transaction, and do all the things that transactional things do. One example of a situation that calls for transactional objects is caching. Suppose you’re in a transaction, inserting, updating, deleting things in a database. After making each of these changes, you update your cache as well.

Then something goes wrong. The transaction rolls back. The database is restored to a pristine state, just as it was at the beginning of your transaction. Your cache, on the other hand, is tainted. There are data in your cache that aren’t in your database.

You may come up with a strategy for delaying cache updates until after the transaction has completed. That’s fine, except that you rely on your cache being up-to-date – if you have changes in the database that aren’t reflected in the cache, you’ve got a different kind of tainting. All sorts of unreliability and special casing begin to creep in. So in the end, you either have to cache only things that will never change, or you have to make your cache transaction-aware.

This is an important use-case, however it’s surprisingly rarely discussed. Haskell has Software Transactional Memory (STM), but there’s nothing like that in .Net. On the other hand, the .Net framework offers an interface, IEnlistmentNotification, that you can implement in classes that need to react to transaction events like commit and rollback. It’s actually fairly easy to implement, but there are some tricky areas that I’ll point out. With IEnlistmentNotification in hand, we can create our transactional cache.

Planning

Let’s first agree on what we’re trying to build. To simplify the problem a little, we’ll leave out caches for the moment, and just ask: What would it take to make a transactional dictionary? Such a dictionary would have to support the sorts of guarantees that people expect of transactions. These guarantees are known as ACID – Atomicity, Consistency, Isolation, and Durability.

Atomicity

This means that the transaction succeeds or fails as a single unit. If anything goes wrong in a transaction, all of the work done in that transaction must be undone, as if it never happened.

Consistency

The system moves from one consistent state to another. At no point can the system be inconsistent.

Isolation

The changes that one transaction makes are undetectable to code that’s running in a different transaction, until the transaction commits. Once the transaction is complete, its results are visible throughout the system.

Durability

Once a transaction has been committed, it remains so – it cannot be undone, nor can it be lost due to power failure or other catastrophe. In our case, we’re talking about a volatile resource, a dictionary residing in memory, so we’re not really concerned with durability in the same sense that a database management system would be.

The Approach

The transactional dictionary we’re going to build will have the following properties:

  • Changes made to the dictionary within a transaction will not be visible outside of that transaction, until the transaction completes.
  • If the transaction rolls back, there will be no changes made to the dictionary.
  • If the transaction commits, the dictionary will be permanently updated with the changes executed during the transaction
  • Unlike a database, we’re not going to concern ourselves with locking or trying to manage the order of transaction execution, we simply want to make sure that failed transactions don’t leave stale data in the dictionary. However, we will lock the dictionary while each transaction is committing.

The Implementation

We know that we need to implement IEnlistmentNotification to participate in a transaction. We also need to enlist in the transaction in order to get the notifications. Enlisting is easy enough, and looks like this:

txn.EnlistVolatile(this, EnlistmentOptions.None)

Where txn is a reference to a Transaction, usually obtained via Transaction.Current. The “this” argument needs to be a class that implements IEnlistmentNotification.

The implementation of IEnlistmentNotification is also fairly straightforward. Suppose that we have a dictionary that represents the consistent state of our transactional dictionary. We’ll call this the “backing store.” While things are happening during a transaction, the backing store doesn’t change, instead we store those changes in a different location that we’ll call the “transactional values.” When the transaction commits, we need to update the backing store with the results of transaction, i.e. the contents of the transactional values.

A Word on F#

I’m implementing this in F#, rather than C#. This is not because this problem is particularly well suited to functional programming or immutable data structures – in fact, this problem is mostly about state and mutability. I do favor a functional approach in general, but I’m using F# here mostly because it’s shorter and clearer than C#, which means it takes me less time to read, write, and debug. Since I’m doing this on my own time and have no other constraints that dictate what language I should use, I choose what I perceive as the best general-purpose language available for .Net, F#. Your mileage may vary, use what makes you happy.

One additional note: I’ve used generic classes based on built-in framework interfaces, and type variable names in the style of the Framework Design Guidelines ('TKey instead of 'k, for instance) to encourage reuse from other .Net languages. This is not intended to be an F#-specific library.

The Tricky Bits

The first tricky bit is that when the transaction notifies your code that the transaction is done, either via calling Commit or Rollback, Transaction.Current is null, and there’s no Transaction property on the enlistment object that is passed by the transaction manager. This means that the class that gets the notification must know what transaction it’s being notified about already, meaning it must only be working with one and only one transaction. This forces our design to be one in which we create a new instance of a class for each transaction, and assign the management of that transaction to the new instance, rather than handling it in the transactional dictionary itself.

The second tricky bit is that we need to track both the addition of new keys as well as the removal of keys. That means we need a data structure that will track both. We’ll deal with this by storing an F# Option<'T> type instead of the raw value – values that are present in the dictionary will be represented by (Some value) and values that have been removed will be represented by None.

The third tricky bit is that our transactional dictionary needs to keep track of which of its transactional values helpers should receive each particular call, depending on the transaction of the current thread, but it also needs to remove its references to each transactional values helper when the transaction associated with that helper completes. Even if we enlisted the transactional dictionary in the transaction directly, it still wouldn’t know which transaction had committed, so it wouldn’t know which one to remove. So the helper has to be empowered to clean itself up. We’ll do this by passing a function to the helper that it can call to let the transactional dictionary know it’s ready to be cleaned up.

Working with transactions can be full of little surprises, which leads us to the fourth tricky bit. As reported by Ayende a couple of years ago (and other places as well), it is actually possible for a use (C#: using) statement to end before your transaction commits, or rather, before your enlistment’s Commit method returns. The Prepare, Commit, and other methods on IEnlistmentNotification are called in a different thread from the one that creates and disposes the TransactionScope, so we’ll have to take appropriate steps (i.e. locking) to make sure that things work the user of our transactional dictionary would expect.

With those in mind, let’s dive into the implementation.

TransactionalDictionary

The transactional dictionary doesn’t reinvent the actual storage of the data – we have perfectly good data structures for that already. It takes a dictionary (the “backing store” we mentioned earlier) as a constructor argument. This is the “one source of truth” for our data, like a table in a database. We may overlay that data with changes, but we will never actually update the backing store until it comes time to commit the transaction.

type TransactionalDictionary<'TKey, 'TValue
        when 'TKey:equality
         and 'TValue: equality>
            (backingStore:IDictionary<'TKey,'TValue>) = 

    //A mapping from transaction to our TransactionValues helper class
    let transactions = new Dictionary<Transaction,TransactionValues<'TKey, 'TValue>>()
    //A synchronization object for locking
    let sync = obj()
    //The lock that we use during the transaction commit process
    let transactionLock = new TransactionLock()

Since this is F#, we don’t have to explicitly store the backingStore parameter, it’s automatically available to all the methods of the type. We create a dictionary to map from transactions to a transaction-specific helper class that we’ll rely on heavily for most of the implementation of TransactionalDictionary. Then we create two synchronization objects – one, “sync” that we’ll use to control access to the transactions dictionary, and one, “transactionLock,” that will ensure that transactions don’t try to commit simultaneously. We do not require the backing store to be thread safe, so we have to provide the locking to ensure only one thread commits at a time.

The IDictionary<’TKey,’TValue> Implementation

The implementation of the dictionary operations themselves is almost trivial – they all involve calling a function called getTxnValues that returns the TransactionValues helper that we have stored for the current transaction, and then delegating the method call to the method of the same name on the TransactionValues helper. Here’s a sample, the implementation of the indexer:

        member this.Item
                with get key = let tv = getTxnValues()
                               tv.[key]
                and  set key value = let tv = getTxnValues()
                                     tv.[key] <- value

The getTxnValues Function

This function is critical to the operation of the dictionary – it checks Transaction.Current to find out which transaction the code is participating in, and returns (via the getValues function) the TransactionValues helper instance associated with that transaction. If there is no instance assigned yet assigned to the current thread, and the thread is in a transaction, it creates one. If the thread is not in a transaction, then it can access the backing store directly.

let getValues txn : IDictionary<'TKey, 'TValue> =
        if txn = null then
            backingStore
        else
            let dict = lock sync (fun () ->
                                    let (containsKey,value) = transactions.TryGetValue txn
                                    match (containsKey,value) with
                                    | true, v -> v
                                    | false, _ ->
                                        let v = TransactionValues<'TKey, 'TValue>(
                                                            backingStore,
                                                            (fun () -> transactionLock.Lock(txn)),
                                                            (fun () -> transactionLock.Unlock |> ignore
                                                                       lock sync (fun () -> transactions.Remove txn |> ignore)))
                                        transactions.[txn] <- v
                                        v)
            dict :> IDictionary<'TKey,'TValue>
    let getTxnValues () = getValues (Transaction.Current)

First, we lock the synchronization object for the dictionary. After that, we’re free to read or modify our Transaction-to-TransactionValues dictionary as we like. If needed, we create a new TransactionValues helper instance, passing it the backing store for the TransactionalDictionary, and two functions. The first function is the one that TransactionValues will call when it’s ready to begin committing its changes to the backing store, and the second function will be called when it has completed its work, either by committing, or rolling back.

The TransactionValues Helper

TransactionValues is really the type that does the greatest part of the work. Each TransactionValues instance manages the changes that have been executed in the context of a single transaction. It stores the changes in a dictionary of its own. While TransactionalDictionary<'TKey, 'TValue> maps 'TKey to 'TValue, TransactionValues maps 'TKey to Option<'TValue>. Storing a value of None means that in the current transaction, that key was removed. Storing a value of (Some v) for a key means that in the current transaction, that key was set to a the value of v. Keys that are not present in the TransactionValues dictionary have to be looked up from the backing store.

We create this dictionary of changes in the constructor:

    let transactionValues =
        if backingStore.IsReadOnly then
            raise (System.ArgumentException("Source dictionary is ReadOnly"))
        new Dictionary<'TKey, 'TValue option>()

 

Another important task for the constructor is to fix the knowledge of the transaction to which this instance is bound. It is at this point that we actually enlist in the transaction:

 

    let transaction =
        let txn = System.Transactions.Transaction.Current
        if txn = null then
            let msg = "TransactionValues can only be created in the context of an open transaction"
            raise (System.InvalidOperationException(msg))
        txn.EnlistVolatile(this, EnlistmentOptions.None) |> ignore
        txn

 

Let’s look at the implementation of the indexer for TransactionValues:

member this.Item
        with get key = getOrFail key
        and  set key value = transactionValues.[key] <- Some value

 

Clearly, we need to see getOrFail as well! Here it is:

    let get key =
        let (succ, value) = transactionValues.TryGetValue(key)
        match (succ, value) with
        | true, ((Some _) as v) -> v
        | true, None -> None
        | false, _ -> match backingStore.TryGetValue(key) with
                      | true, v -> Some v
                      | false, _ -> None

    let getOrFail key = match get key with
                        | None -> raise (KeyNotFoundException())
                        | Some v -> v

 

You can see now how TransactionalDictionary delegates to the TransactionValues instance for the current transaction, and TransactionValues stores changes in a separate dictionary that it uses as an overlay over the original backing store.

Commit, or Don’t

So far, the code we have can store different changes for different transactions, and those transactions won’t be able to see each other’s changes. At some point, however, we’ll  want to actually commit or roll back the transaction. To do this, we implement the IEnlistmentNotification interface in the TransactionValues type. Here is the implementation, along with a few relevant functions:

//The undo data needed to undo changes if a rollback happens during
//a 2-phase commit. Generated during the IEnlistmentNotification.Prepare method.
let mutable undo:seq<'TKey * 'TValue option> = Seq.empty

//Tracks whether the Prepare method has been run or not. Under some circumstances,
//Commit can be called without calling Prepare first, so Commit has to be be
//able to do the work of Prepare as well.
let mutable prepared = false

let updateWithPair (dictionary:IDictionary<'a,'b>) (kv:'a * 'b option) =
    let (k,value) = kv
    match value with
    | Some v ->
        dictionary.[k] <- v
    | None ->
        dictionary.Remove k |> ignore

let update (dictionary:IDictionary<'TKey,'TValue>) : seq<'TKey*'TValue option> =
    let undo = seq {
                    for kv in transactionValues do
                        let (has,old) = dictionary.TryGetValue(kv.Key)
                        updateWithPair dictionary (kv.Key, kv.Value)
                        yield kv.Key, (if has then Some old else None)
                        } |> List.ofSeq :> seq<'TKey *'TValue option>
    undo

let prep() = lockStore()
             undo <- update backingStore
             prepared <- true
interface System.Transactions.IEnlistmentNotification
        with
        member this.Commit(enlistment) =
            if not prepared then
                prep()
            finished()
            enlistment.Done()
        member this.InDoubt(enlistment) =
            enlistment.Done()
        member this.Prepare(enlistment) =
            try
                prep()
                enlistment.Prepared()
            with e -> enlistment.ForceRollback(e)
        member this.Rollback(enlistment) =
            for kv in undo do
                updateWithPair backingStore kv
            undo <- Seq.empty
            finished()
            enlistment.Done()

Notice the calls to finished() and lockStore(). These are the functions that were passed by the TransactionalDictionary to the TransactionValues instance in the constructor. The lockStore function locks the dictionary while it’s being updated, so no other transaction can update it at the same time. Then we replay all the changes that have been made over the course of the transaction, updating and deleting keys in the backing store. As we go, we keep a record of the changes that we made. If something goes wrong and the transaction has to be rolled back, we undo the changes we just made using the undo information.

When the transaction either commits or rolls back, then finished() is called to release the lock on the dictionary so that other transactions can update it.

The normal course of events is that the Completed method is called on the TransactionScope before it is disposed, then the transaction manager will call Prepare on each IEnlistmentNotification. If each of them replies with a call to Prepared on the enlistment object, then the transaction manager calls Commit on each IEnlistmentNotification.

Note that Commit is never supposed to fail – you’re expected to have already done the work you needed to do in Prepare, and Commit is just letting you know that this transaction is officially done. If something goes wrong in Prepare, you call the ForceRollback method on the enlistment, and this causes the transaction to roll back.

The documentation says that the methods may not necessarily be called in this order, however, which is why the Commit implementation above is built to also do the work of Prepare if the Prepare method was never called.

The Result

Now we have a fully transaction-aware dictionary. The same kind of logic can be extended to your cache, or to other kinds of transaction-aware objects you may need. I hope you find it useful. Please let me know if you have any comments, questions, or suggestions.

Get The Code

All the code for this article and more is available on GitHub as part of the xoltar-sharp repository. The xoltar-sharp repository is a (currently very small) collection of utilities to simplify the development of complex applications. The transactional dictionary discussed in this article is the first of hopefully many tools that will be added to the xoltar-sharp package over time. I’ll also be releasing it as a NuGet package when it’s ready.

References and Acknowledgements

Thanks to F# guru Phil Trelford for graciously reviewing the transactional dictionary code!

Thanks to Microsoft for making a version of Visual Studio that supports F# available for free!

By far the most useful article I read while researching this one was Juval Lowy’s article, Volatile Resource Managers in .Net Bring Transactions to the Common Type, on MSDN. The TransactionLock type in xoltar-sharp (mentioned in this article, but not examined) is almost entirely based on on Lowy’s C# TransactionLock

 

Others that were useful include:

4 Comments