Transactions

Tracking Library addresses this challenge by providing a Software Transactional Memory (STM) system to manage entity data. Software Transactional Memory enables treating collections of in-memory entities as if they were a database. Reads and writes of entity data are performed in Transactions that are both atomic and isolated.

Transactions are atomic in the sense that either all of the individual modifications made within the transaction are carried out, or none of them are. For example, if a single transaction updates both the position and orientation of an aircraft, either the change to both position and orientation will be visible outside of the transaction, or neither will. Another transaction will never see the change in position without also seeing the change in orientation.

Transactions are isolated in the sense that the actions of one transaction are not visible outside of that transaction until the transaction is committed. In database systems, different isolation levels are possible. The STM system in Tracking Library uses snapshot isolation, which will be discussed later.

To visualize how this works in practice, let's look at the simple set of transactions in the table below. Assume we start with x = 3 and y = 4.

There are 3 threads performing transactions. Transaction 1 starts at time 2, modifies x, then multiplies the values to produce z = 20. While that is happening, transaction 2 starts and multiplies x times y. Because x was 3 when the transaction started, it produces w = 12, even though transaction 1 has modified its own copy of x, because it has not yet been committed. Finally, transaction 3 starts, modifies y, then multiplies, producing u = 21. By the time the 4th transaction begins, transactions 1 and 3 have been committed, so it sees x = 5 and y = 7, and so it produces w = 35.

Suppose instead that transaction 1 and 3 were both modifying the same variable, x. This would cause a TransactionConflictException for whichever transaction was committed second. The transaction can then decide to retry, or abort.

The following code sample shows how to create a TransactionContext:

TransactionContext context = new TransactionContext();

Each TransactionContext can be thought of as a separate in-memory database. An application can have as many TransactionContexts as it needs, but each Transaction operates in exactly one context. A typical application will have just one context, though more complicated applications might have more.

Transactions are started with the DoTransactionally method:

TransactedProperty<int> transactedInt = new TransactedProperty<int>(context, null, 5);

context.DoTransactionally(transaction =>
{
    int oldValue = transactedInt.GetValue(transaction);
    transactedInt.SetValue(transaction, oldValue * 2);
});

DoTransactionally takes a delegate. It creates a transaction and passes the transaction to the delegate. The code inside the delegate can then use the transaction to read or write values. When the delegate returns, the transaction is committed. If at any time during this process the actions of this transaction conflict with another, the transaction is aborted and the entire process repeats: a new transaction is created, the delegate is invoked with the new transaction, etc. The transaction will be retried an unlimited number of times until it commits without a conflict.

Internally, DoTransactionally works like this:

bool transactionSuccessful = false;
while (!transactionSuccessful)
{
    try
    {
        using (Transaction transaction = new Transaction(context))
        {
            int oldValue = transactedInt.GetValue(transaction);
            transactedInt.SetValue(transaction, oldValue * 2);
            transaction.Commit();
        }
        transactionSuccessful = true;
    }
    catch (TransactionConflictException)
    {
        // Ignore exception until we succeed.
    }
}

Because the code inside the delegate passed to DoTransactionally may be executed multiple times, it is very important that it not have any side-effects outside of the transaction system, such as performing I/O or modifying non-transacted values.

The Software Transactional Memory (STM) implementation in DME Component Libraries achieves snapshot isolation using multiversion concurrency control. It is roughly based on the paper Versioned Boxes as the Basis for Memory Transactions (Cachopo and Rito-Silva 2005), with some significant changes to make it more suitable for use with Tracking Library. Specifically, this STM has the following characteristics:

• Transactions see a consistent snapshot of all transacted objects during their lifetime. This means that a single transaction can never read the same transacted object twice and see two different values unless the transaction itself modified the object in between.

• Arbitrary groups of changes can be made atomically. A transaction will never see a partial update made by another transaction.

• Reading transacted objects is completely lock-free. Readers will never block writers or other readers.

• Writing transacted objects requires a lock only on commit. Even transactions that write can execute almost completely in parallel.

• Transactions can be aborted without committing changes.

TransactedProperty<T>, which is used in the example above, is the most common transacted object in DME Component Libraries. It is a generic class that turns any immutable type into a participant in the transactional memory system. An immutable type is one that cannot be changed after it is created. All primitives, such as int and double are immutable, as are common DME Component Libraries value types such as Cartesian and UnitQuaternion. The following example shows how to create a TransactedProperty<Cartesian> and get and set its value:

TransactedProperty<Cartesian> position = new TransactedProperty<Cartesian>(context, null);

context.DoTransactionally(transaction => position.SetValue(transaction, new Cartesian(6891423.0, 0.0, 84869.8)));

context.DoTransactionally(transaction => Console.WriteLine(position.GetValue(transaction)));

While it cannot be enforced, it is important that TransactedProperty<T> be used only with immutable types. Otherwise, as in the following example, the value of the property can be changed behind the transaction system's back, and no thread-safety or transactional guarantees can be made.

TransactedProperty<PointCartographic> position = new TransactedProperty<PointCartographic>(context, null);

context.DoTransactionally(transaction => position.SetValue(transaction, new PointCartographic(earth, new Cartographic(0.1, 0.2, 1000.0))));

PointCartographic pointCartographic = context.SelectTransactionally(transaction => position.GetValue(transaction));

// Modifying a property of the TransactedProperty's value behind the transaction
// system's back.  No transactional guarantees can be made!
pointCartographic.Location = new Cartographic(1.23, 0.1, 500.0);

The following interactions with a TransactedProperty<T> will lead to a TransactionConflictException:

• Transaction #1 and Transaction #2 both call SetValue on the same TransactedProperty<T>. Transaction #1 commits. Transaction #2 will throw a TransactionConflictException when it tries to commit.

• Transaction #1 calls SetValue while Transaction #2 calls EnsureValue on the same TransactedProperty<T>. Transaction #1 commits. Transaction #2 will throw a TransactionConflictException when it tries to commit.

EntitySet<TEntity> is a set of entities, such as aircraft or satellites, that can be manipulated transactionally. Modifications to the entity set are not visible to other transactions until committed. Therefore a transaction reading the entity set will see a consistent snapshot of the set for the transaction's lifetime, even if other transactions are manipulating it and committing.

The following interactions with an EntitySet<TEntity> will lead to a TransactionConflictException:

• Transaction #1 and Transaction #2 both call Add with an entity with the same identifier. Transaction #1 commits. Transaction #2 will throw a TransactionConflictException when it tries to commit. This is true even if both add the same entity.

• Transaction #1 calls Remove with an entity or removes all entities by calling Clear. Transaction #2 calls Add with the same entity, causing an exception because in Transaction #2's snapshot the entity still exists in the set. Transaction #1 commits. Transaction #2 will throw a TransactionConflictException when it tries to commit.

• Transaction #1 and Transaction #2 both call Remove with the same entity. Transaction #1 commits. Transaction #2 will throw a TransactionConflictException when it tries to commit.

• Transaction #1 calls Add with an entity. Transaction #2 calls Remove with the same entity, even though it is not yet visible to Transaction #2. Transaction #1 commits. Transaction #2 will throw a TransactionConflictException when it tries to commit.

• Transaction #1 does any operation on the entity set, such as adding or removing an entity, or clearing the entity set. Transaction #2 calls Clear on the entity set. Transaction #1 commits. Transaction #2 will throw a TransactionConflictException when it tries to commit.

• Transaction #1 does any operation on the entity set, such as adding or removing an entity, or clearing the entity set. Transaction #2 calls EnsureAll on the entity set. Transaction #1 commits. Transaction #2 will throw a TransactionConflictException when it tries to commit.

• Transaction #1 calls Remove with an entity that exists in the entity set or calls Add with an entity that does not yet exist in the entity set. Transaction #2 calls Ensure with the same entity. Transaction #1 commits. Transaction #2 will throw a TransactionConflictException when it tries to commit.

The STM system raises numerous events to inform the user of changes to transacted objects.

TransactionContextCommitted is raised once for each transaction that is committed. TransactionCommittedEventArgsCommittedObjects contains the list of the transacted objects that were committed by the transaction.

TransactedPropertyTChanged is raised when a property is changed by a committed transaction. TransactedPropertyChangedEventArgs<T> contains the old value and the new value.

EntitySetTEntityChanged is raised when entities are added to or removed from an entity set by a committed transaction. EntitySetChangedEventArgs<TEntity> contains a collection of entities that were added by the transaction and a collection of the identifiers of the entities that were removed by the transaction.

While any of these events are being handled, further transactions cannot be committed. If another thread attempts to commit a transaction while a transaction event is being handled, that thread will block until all event handlers complete. For that reason, it is very important that transaction event handlers complete as quickly as possible.

The event args for all of the events described above have a ChainedTransaction property. This chained transaction can be used to make additional transactional changes as a result of the event. It will be committed automatically after all event handlers return, so you should not call Commit on it yourself. The chained transaction is guaranteed to commit successfully without any conflicts. Additional events may be raised as a result of committing the chained transaction.