July 2007 - Posts
The API for my .NET Software Transactional Memory (NSTM) I´ve described so far is straightforward, I´d say. It´s close to what you´re used to from transactional dabase access and it´s even integrated with System.Transactions: open a transaction, do some stuff with transactional objects, commit the transaction. All very explicit.
Despite its familiarity this explicitness kind of stands in the way of what a piece of object oriented code is supposed to accomplish. It´s something you´ve to concern yourself with although it does not add to the raw functionality you want to achieve. And by being imperative it´s prone be done incorrectly. A more declarative way to do in-memory transactions and less explicitness thus would be nice now that objects have become transactional and automatically threadsafe in general.
I thought about that from the being when I started to work on NSTM. Microsofts STM implementation SXM shows, how transactionality could be made more declarative and "invisible": With SXM you just adorn a class with the attribute [Atomic] to make its instances transactional. That´s cool - but so far I did not consider it for NSTM, since it seemed to require fiddling around with proxies. That´s why with SXM you need to instanciate transactional objects through a factory which you´ve to create for each transactional class:
1 [Atomic]
2 public class Node
3 {
4 private int value;
5 private Node next;
6 ...
7 }
8 ...
9 XObjectFactory factory = new XObjectFactory(typeof(Node));
10 Node node = (Node)factory.Create(value);
The benefits of using an attribute to make classes transactional to me seem to be lost through this cumbersome instanciation process. That´s why I did not go down this road until now.
PostSharp to the rescue
But then one day - lo and behold! - a very, very cool tool was revealed to me by InfoQ (which I´ve come to like as much as theserverside.net):
PostSharp from Gael Fraiteur is a godsend! It´s one of those technologies you´ve waited for all along without really knowing. It´s a technology that will change how you approach software development. At least that´s what his done for me since I first read about it.
What PostSharp does is not new, though. It´s a kind of Aspect Oriented Programming (AOP) weaver. And it´s a tool to alter the MSIL code in assemblies. But there are already several APO frameworks out there - also for .NET -, so why another one? There are already tools to alter assemblies like Phoenix from Microsoft and Cecil from the Mono project.
What makes PostSharp so remarkable to me, though, is in which way it combines AOP with MSIL modification. It makes it so dead easy!
- You´re not forced to learn MSIL.
- The weaving is done automagically for you by an invisible post build step.
- No factories needed to instanciate classes annotated with aspects, because no proxies are used.
- For many common types of aspects (e.g. pre/post processing of method calls, field access interception) there are templates that help you get your own aspects up and running in just a few minutes.
Congratulations Gael! And thanks for being so responsive to questions and bug reports!
Aspect oriented transactions
The first thing I tried with PostSharp to make NSTM transactions declarative. This seemed to be easy to do and would result in an also familiar transactional programming model. COM+/EnterpriseServices, ASMX, and not WCF all sport some attribute to make methods transactional. Here´s an excerpt from Juval Löwy´s article [1] on that topic:
1 [ServiceContract]
2 interface IMyContract
3 {
4 [OperationContract]
5 [TransactionFlow(TransactionFlowOption.Mandatory)]
6 void MyMethod(...);
7 }
8
9 class MyService : IMyContract
10 {
11 [OperationBehavior(TransactionScopeRequired = true)]
12 public void MyMethod(...)
13 {
14 ...
17 }
18 }
MyMethod in the service contract is declared as to be wrapped in a mandatory transaction. The service implementation does not have to do anything imperatively for that. The WCF infrastructure will create a new System.Transactions transaction if necessary behind the scene.
That´s what I wanted for NSTM, too, and what now seemed within reach through PostSharp. And indeed it was very easy to implement. Here´s my transactional aspect whipped up in some 30 minutes after downloading PostSharp:
1 [Serializable]
2 [AttributeUsage(AttributeTargets.Method |
3 AttributeTargets.Property |
4 AttributeTargets.Constructor)]
5 public class NstmAtomicAttribute : OnMethodBoundaryAspect
6 {
7 private NstmTransactionScopeOption transactionScope;
8 private NstmTransactionIsolationLevel isolationLevel;
9 private NstmTransactionCloneMode cloneMode;
10 private bool createdNewTx;
...
35 public override void OnEntry(MethodExecutionEventArgs eventArgs)
36 {
37 NstmMemory.BeginTransaction(this.transactionScope,
38 this.isolationLevel,
39 this.cloneMode,
40 out this.createdNewTx);
41 }
42
43 public override void OnException(MethodExecutionEventArgs eventArgs)
44 {
45 if (this.createdNewTx) NstmMemory.Current.Rollback();
46 }
47
48 // will always be called, also after OnException()
49 public override void OnExit(MethodExecutionEventArgs eventArgs)
50 {
51 // only commit, if no exception has been thrown
52 if (eventArgs.Exception == null && this.createdNewTx)
53 NstmMemory.Current.Commit();
54 }
55 }
How does it work? First have a look at some code which uses this attribute:
1 static INstmObject<int> myAccount, yourAccount;
2
3 static void Main()
4 {
5 myAccount = NstmMemory.CreateObject<int>(1000);
6 yourAccount = NstmMemory.CreateObject<int>(500);
7
8 try
9 {
10 TransferMoney(350);
11 }
12 catch (Exception ex)
13 {
14 Console.WriteLine("*** {0}", ex.Message);
15 }
16
17 Console.WriteLine("my account: {0}", myAccount.Read());
18 Console.WriteLine("your account: {0}", yourAccount.Read());
19 }
20
21 [NstmAtomic()]
22 static void TransferMoney(int amountToTransfer)
23 {
24 myAccount.Write(myAccount.Read() - amountToTransfer);
25 yourAccount.Write(yourAccount.Read() + amountToTransfer);
26 throw new ApplicationException("Money transaction failed!");
27 }
The method TransferMoney() does not open explicitly a transaction. Rather this is done by the NSTM infrastructure because the method is adorned with the [NstmAtomic()] attribute. The default then is to commit the transaction when the method returns; but it´s aborted if the method throws an unhandled exception.
Of course, if you like, you can pass a transaction scope or isolationlevel etc. to the attribute to influence how the transaction is created. By default the scope is Required so nested calls don´t each created new transactions.
Now, how is this magic woven (sic!) by PostSharp? I won´t explain PostSharp in depth here, but a quick glimpse behind the curtain won´t hurt, wouldn´t it ;-)
Remember, PostSharp modifies the original assembly in a post build step like an O/R Mapper´s enhancer (e.g. Vanatec OpenAccess) or an obfuscator (e.g. Xenocode). So here´s the "enhanced" TransferMoney() method as seen through Reflector:
private static void TransferMoney(int amountToTransfer)
{
MethodExecutionEventArgs args;
try
{
object[] arguments = new object[] { amountToTransfer };
args = new MethodExecutionEventArgs(methodof(Program.TransferMoney, Program), null, arguments);
~PostSharp~Laos~Implementation.~aspect~1.OnEntry(args);
if (args.FlowBehavior != FlowBehavior.Return)
{
myAccount.Write(myAccount.Read() - amountToTransfer);
yourAccount.Write(yourAccount.Read() + amountToTransfer);
throw new ApplicationException("Money transaction failed!");
~PostSharp~Laos~Implementation.~aspect~1.OnSuccess(args);
}
}
catch (Exception exception)
{
args.Exception = exception;
~PostSharp~Laos~Implementation.~aspect~1.OnException(args);
switch (args.FlowBehavior)
{
case FlowBehavior.Continue:
case FlowBehavior.Return:
return;
}
throw;
}
finally
{
~PostSharp~Laos~Implementation.~aspect~1.OnExit(args);
}
}
I greyed out the original method body so you can more clearly what PostSharp has woven around it. Basically it´s a try-catch-block which calls the On...() methods of NstmAtomicAttribute. Where .NET needs context bound objects and proxies at runtime to let you intercept calls PostSharp does it by statically inserting code which calls your interception methods.
Aspect oriented transactional data
Since success was so easy to gain with PostSharp I did not want to stop with transactional methods. Wouldn´t it be nice to hide transactionality almost altogether? If enhancer based O/R Mappers can hide persistence behind an attribute and don´t require object creation through factories, why shouldn´t I be able to do the same? If SXM falls short of this, that´s not my problem ;-)
So I set down with PostSharp and had a close look at the different kinds of aspect it provides out of the box. And really there was a way to accomplish what O/R Mapper enhancers have done before. I just had to combine a "generic field" aspect with a "type composition" aspect using a "compound" aspect. And here´s the result:
1 [NstmTransactional]
2 public class Account
3 {
4 private int amount;
5 private int maxOverdraftAmount;
6
7 public Account()
8 {
9 this.amount = 0;
10 this.maxOverdraftAmount = 0;
11 }
12
13 public Account(int initialAmount, int maxOverdraftAmount)
14 {
15 this.amount = initialAmount;
16 this.maxOverdraftAmount = maxOverdraftAmount;
17 }
18
19 public int Amount
20 {
21 get
22 {
23 return this.amount;
24 }
25 set
26 {
27 if (value < maxOverdraftAmount)
28 throw new ApplicationException(...);
29 this.amount = value;
30 }
31 }
32 }
Put the [NstmTransactional] on an ordinary class to make it transactional. That´s it. It´s the same as wrapping INstmObject<T> around it. NSTM will care for buffering writes to instances and committing any changes at the end of a transaction. The money transfer example thus looses almost any trait of its transactionality:
35 static Account myAccount, yourAccount;
36
37 static void Main()
38 {
39 myAccount = new Account(1000, 0);
40 yourAccount = new Account(500, 0);
41
42 try
43 {
44 TransferMoney(1001);
45 }
46 catch (Exception ex)
47 {
48 Console.WriteLine("*** {0}", ex.Message);
49 }
50
51 Console.WriteLine("my account: {0}", myAccount.Amount);
52 Console.WriteLine("your account: {0}", yourAccount.Amount);
53 }
54
55
56 [NstmAtomic()]
57 static void TransferMoney(int amountToTransfer)
58 {
59 myAccount.Amount -= amountToTransfer;
60 yourAccount.Amount += amountToTransfer;
61 }
This is just ordinary object oriented code. (Please don´t get too critical with my account business logic ;-) With PostSharp´s AOP the impact of Software Transactional Memory on your code is reduced to two attributes: make classes transactional with [NstmTransactional] and wrap transactions around methods with [NstmAtomic].
If you don´t have a class you want to make transactional, but just a scalar type or a struct, then use NstmTransactional<T>:
1 static NstmTransactional<int> myAccount, yourAccount;
2
3 static void Main()
4 {
5 myAccount = 1000;
6 yourAccount = 500;
7
8 try
9 {
10 TransferMoney(1001);
11 }
12 catch (Exception ex)
13 {
14 Console.WriteLine("*** {0}", ex.Message);
15 }
16
17 Console.WriteLine("my account: {0}", myAccount.Value);
18 Console.WriteLine("your account: {0}", yourAccount.Value);
19 }
20
21
22 [NstmAtomic()]
23 static void TransferMoney(int amountToTransfer)
24 {
25 myAccount.Value -= amountToTransfer;
26 yourAccount.Value += amountToTransfer;
27
28 if (myAccount < 0)
29 throw new ApplicationException("No overdraft allowed!");
30 }
NstmTransactional<T> works almost like Nullable<T>. It´s just for scalar and value types. However NstmTransactional<T> is a class, not a struct! This is due to the need for identity and addressability of transactional data. When a transaction commits it needs to update a memory location it knows the address of. That´s not possible for value types which live on the stack. So if you want a value type to be transactional you need to be make it into an object.
Please note: [NstmAtomic] keeps only track of changes to one level of an object hierarchy! If you want to make more than one level transactional, you need to put [NstmAtomic] on all classes on all levels!
In this example a contact has an address. If you want to work transactionally with both, it´s not sufficient to just adorn the Contact class with [NstmAtomic], though! The attribute does not cause NSTM to track changes recursively on all objects pointed to by a Contact. Rather you need to make Address also transactional.
1 [NstmTransactional]
2 class Contact
3 {
4 private string name;
5
6 public string Name
7 {
8 get { return name; }
9 set { name = value; }
10 }
11
12 private Address location;
13
14 public Address Location
15 {
16 get { return location; }
17 set { location = value; }
18 }
19 }
20
21 [NstmTransactional]
22 class Address
23 {
24 private string city;
25
26 public string City
27 {
28 get { return city; }
29 set { city = value; }
30 }
31 }
With all levels of the object model made transactional code like this works correctly:
1 Contact c = new Contact();
2 c.Name = "John Doe";
3 c.Location = new Address();
4 c.Location.City = "Hamburg";
5
6 using (INstmTransaction tx = NstmMemory.BeginTransaction())
7 {
8 c.Name = "Peter Doe";
9 c.Location.City = "Berlin";
10 }
11
12 Console.WriteLine(c.Name);
13 Console.WriteLine(c.Location.City);
Neither the contact name nor the location´s city are changed, since the transaction is aborted.
This of course means, you cannot use the .NET collection classes as is. For example you could set up a contact with several addresses like this:
1 [NstmTransactional]
2 class ContactWithManyAddresses
3 {
4 private string name;
5 private List<Address> addresses;
6
7 public ContactWithManyAddresses()
8 {
9 this.addresses = new List<Address>();
10 }
11
12 public string Name
13 {
14 get { return name; }
15 set { name = value; }
16 }
17
18 public List<Address> Addresses
19 {
20 get { return this.addresses; }
21 }
22 }
Then you would want to be able to do the following:
100 ContactWithManyAddresses c = new ContactWithManyAddresses();
101 c.Name = "John Doe";
102 Address a = new Address();
103 a.City = "Hamburg";
104 c.Addresses.Add(a);
105
106 using (INstmTransaction tx = NstmMemory.BeginTransaction())
107 {
108 c.Name = "Peter Doe";
109 c.Addresses[0].City = "Berlin";
110
111 a = new Address();
112 a.City = "Munich";
113 c.Addresses.Add(a);
114 }
115
116 Console.WriteLine(c.Name);
117 foreach (Address b in c.Addresses)
118 Console.WriteLine(b.City);
But the output at the end of this code would surprise you:
The name of the contact and the city of the first address were rolled back correctly. But there is a second city in the list of addresses without a name. That´s the object to which the code assigned "Munich" and which was added to the address collection. The city of this address also got rolled back correctly, but the entry in the ArrayList was not. That´s because standard .NET collections are not transactional.
So, how then should you model 1:n relationships between transactional objects? True transactional collections are needed. I´m already working on some, so stay tuned. Or start building your own transactional list, queue, stack, tree etc. and let me know.
Preliminary conslusion
I´ve presented you my view of Software Transactional Memory for .NET. NSTM is written in C#, so it´s fully managed code. You can download the sources and play around with it. What will it gain you in terms of ease, productivity, or performance? Find out yourself. It´s programming model at least promises to make many multithreading tasks much easier. No need to think about locking, but rather work on on graphs of objects like on databases: open a transaction, do your work, commit the transaction. If something goes wrong, no changes are visible. That´s also an interesting propsal for GUI programming where you often want to display objects in dialogs, let the user enter changes, but also let him discard all changes. Especially with nested dialogs the nested NSTM transactions could help quite a bit to keep the frontend code straightforward, where IEditableObject falls short.
Enjoy!
PS: NSTM is not finished, of course. I´ll continue working on transactional collections. And there are some concepts from STM research I´d like to add, like a Retry() operation and blocking reads and notifications.
Download
You can download NSTM (short for .NET Software Transactional Memory) from the Google project hosting site.
Enjoy - and let me know how you like it, how it performs for you, or what you think needs to be improved.
Installation
- Download PostSharp from www.postsharp.org and install it.
- Download NSTM and install it by unzipping the file.
- Open the solution in the NSTM directory and try to compile it.
(It might fail due to incorrect references to PostSharp assemblies. The remedy is to update the PostSharp.Laos and PostSharp.Public references in the NSTM projects.)
There are a lot of NUnit compatible tests in the source code. You can use Testrunner like I do to run them in VS2005, or you can use NUnit itself. If you want to throw out all tests, just compile in Release mode.
Resources
[1] Juval Löwy, WCF Transaction Propagation, http://msdn.microsoft.com/msdnmag/issues/07/05/Foundations/default.aspx?loc=en
So far I´ve described my own .NET Software Transactional Memory´s (NSTM) API for managing transactions. It´s close to what you are used to from relational databases, I´d say. But still, it´s my own API and it stands beside what .NET already provides in terms of transactions. With System.Transactions there is already a general way to work transactionally across different resources like database and message queue, so it would be nice if NSTM was another such resource.
Juval Löwy [1] has described how this can be accomplished for in-memory data structures. However, making a data structure transactional like he did with the .NET collections does not make it threadsafe. .NET transactions - although attached to a thread - are not designed help make multithreading easier. In addition they cannot be nested truely. Also the data duplication in Juval´s collections is very coarse grained so it will become pretty slow pretty quickly once they are growing larger. Nevertheless the article is worth reading and provides very helpful insights in how .NET transactions work. It helped me a great deal making NSTM compatible with System.Transactions.
From the point of view of System.Transactions a NSTM transaction is a resource. Its state - the transaction log (txlog) - is changed during a .NET transaction and either discarded at the end if the .NET transaction is rolled back, or committed which means the transaction log is applied to the transactional objects (txo).
Recognition of .NET transactions is not switched on automatically, though. To check, if a .NET transaction is running and whether a NSTM transaction is already enlisted with it, is somewhat costly. NSTM needs to walk up the stack of active transactions for this. But you can switch on System.Transaction integration easily with the flag NstmMemory.SystemTransactionMode:
- EnlistOnAccess: NSTM checks on each access to a txo whether a .NET transaction is running. If there is no NSTM enlisted with the .NET transaction it begins a new NSTM transaction, enlists it, and will commit it/roll it back, when the .NET transaction ends.
- EnlistOnBeginTransaction: NSTM checks only for a .NET transaction when a NSTM transaction is explicity started using NstmMemory.BeginTransaction(). If a .NET transaction is running, the new NSTM transaction is enlisted with it. (To be more precise, NSTM even creates two nested transactions: the outer transaction is enlisted with the .NET transaction and the inner transaction is passed back to the application. That way the application can commit/rollback the inner transaction as usual and still get the final vote on the changes automatically from the out transaction coupled to the .NET transaction.)
- Ignore: NSTM does not care if a .NET transaction is already running. All NSTM transactions are independent of System.Transactions.
Here some sample code showing how to use NSTM with System.Transactions:
1 NstmMemory.SystemTransactionMode = NstmSystemTransactionMode.EnlistOnAccess;
2
3 INstmObject<int> o = NstmMemory.CreateObject<int>(1);
4 using (TransactionScope tx = new TransactionScope())
5 {
6 o.Write(2);
7 tx.Complete();
8 }
9 Console.WriteLine(o.Read());
10
11 NstmMemory.SystemTransactionMode = NstmSystemTransactionMode.EnlistOnBeginTransaction;
12 using (TransactionScope tx = new TransactionScope())
13 {
14 using (INstmTransaction txNSTM = NstmMemory.BeginTransaction())
15 {
16 o.Write(3);
17 txNSTM.Commit();
18 }
19 tx.Complete();
20 }
21 Console.WriteLine(o.Read());
In line 1 .NET transaction recogniction is switched on. From then on each read/write access to a txo like o checks, if a .NET transaction is running and if so creates an implicit new NSTM transaction. That way the change to o get committed when the .NET transaction is finished in line 7. Please note, this option - although most convenient - is quite expensive since it requires transactional objects to check upon each and every call whether to create a NSTM transaction or not.
This is why the second example is more economic: It just checks for a .NET transaction in line 14. The price to pay for this option is an explicit NSTM transaction, i.e. a little less convenient programming model.
What´s next?
In my previous posting I said, System.Transactions integration was the final piece missing for your understanding of NSTM. But that´s not true anymore. Since then I stumbled across a very cool tool and have spiced up NSTM a bit. Stay tuned for automatic transactions like with COM+ and truely transparent transactionality for your classes.
Resources
[1] Juval Löwy, Can´t Commit: Volatile Resource Managers in .NET Bring Transactions to the Common Type, http://msdn.microsoft.com/msdnmag/issues/05/12/transactions/default.aspx
I´ve explained in my previous posting, how a single transaction weaves its magic of isolating changes to transactional objects (txo) and atomically making them visible on commit. But what´s the "reach" or "scope" of a NSTM transaction? How many transaction can be open at the same time?
Transactions are kept in TLS
To answer these questions it´s vital to understand where transactions are stored: in thread local storage (TLS). NSTM transactions are bound to a single thread, the thread they were created on. This is different from System.Transactions which are thread-independent (see [1] for details). But binding NSTM transactions to a thread is on purpose. NSTM is supposed to make multithreaded programming easier by isolating the work done in parallel on shared in-memory data structures. Thus transactions need to thread-local to keep changes made to txos in local transaction logs (txlog).
Application code in each thread works with its own transactions which of course can work on the same txos:
A txo is just briefly locked during access to avoid inconsistencies during single reads/writes. Since a txo is not just a singel value but containes at least a value and a version number which must not get out of step that´s necessary. But this kind of locking is hidden from you. Don´t worry about it. Nothing is permanently locking for the duration of a transaction. No deadlocks can occur. Rather NSTM bets on optimistic locking as already explained: txos are validated during commit (at latest) to check if they were changed by some other transaction and if so, the transaction fails. It´s the same as with ADO.NET when saving changes made to a DataSet.
When you call Read() or Write() on a INstmObject the object retrieves the current NSTM transaction from TLS and delegates further processing of your request to the transaction.
The usual transaction scopes
TLS does not just point to a single transaction, though. Rather it contains a stack of transactions (txstack) because you can nest them. Check out this code:
1 using (INstmTransaction txOuter = NstmMemory.BeginTransaction())
2 {
3 ...
4 using (INstmTransaction txInner = NstmMemory.BeginTransaction(NstmTransactionScopeOption.RequiresNew, ...))
5 {
6 ...
7 }
8 ...
9 }
In line 3 there is one transaction on the TLS txstack, in line 6 there are two on txstack with txInner being the topmost. In line 8 it´s again just one transaction: txOuter.
Each transaction of course keeps its own transaction log. By default they are independent. However, they need to be ended in reverse order despite their independence. A transaction opened while another was active needs to be committed or rolled back first. That´s why you should nest transactions like above with using statements. They ensure the right order.
But there are several transaction scope options. Above the inner transaction is opened with RequiresNew. This ensures a new transaction is opened although another one is already active. The default however is just Required:
10 using (INstmTransaction txOuter = NstmMemory.BeginTransaction())
11 {
12 ...
13 using (INstmTransaction txInner = NstmMemory.BeginTransaction())
14 {
15 ...
16 }
17 ...
18 }
The inner transaction is opened with the default scope Required which means, a new transaction is only created if none is active yet. But in line 13 there is already txOuter active so no new transaction is started and txInner equals txOuter. In line 15 there´s still only one transaction on the txstack. This mirrors what EnterpriseServices or System.Transactions have offered all the time.
Truely nested transactions
NSTM goes beyond that, though, by providing for real nested transactions:
100 using (INstmTransaction txOuter = NstmMemory.BeginTransaction())
101 {
102 ...
103 using (INstmTransaction txInner = NstmMemory.BeginTransaction(NstmTransactionScopeOption.RequiresNested, ...))
104 {
105 ...
106 }
107 ...
108 }
Using RequiresNested not only ensures there is a new transaction active in line 105, but also that any changes committed with txInner can be undone by rolling back txOuter! In the first sample above txOuter and txInner were independent. Whatever txInner committed txOuter could not undo. Although syntactically nested the transactions had no more to do with each other than transactions on different threads. But nested transactions are different: When txInner is started in line 103 is clones the txlog of txOuter and thus sees all changes already made to txos. And when txInner it commits, it does not write any changes to the txos, but just to its parent transaction txOuter. That means, changes of inner transactions are not visible "to the public" until its parent transactions "reaffirms" them by also committing.
Finally there is the RequiredOrNested scope option. If there is already a transaction running no new one is created, as long the options (scope, isolation level, clone mode) of this transaction are "compatible" with the options stated for the new transaction. If the existing transaction´s options are less strict, though, then a nested transaction is created. This option seems useful for library developers who don´t want to necessarily open new transactions for whatever their library code does - but also don´t want to sacrifice transactional strictness. Consider this scope option an experiment and food for thought ;-)
Summary
See, there answers to the initial questions were easy: A transactions scope is the thread. And you can have as many transactions open as you like. They just cannot overlap, but the can truely be nested. Threadsafety is guaranteed for transactions as a whole and INstmObject transactional objects. If you use CloneOnRead you´re pretty much on the safe side also for the values of txos, though. But this depends on how deep your clones are. For scalar types and value types containing just scalars you don´t have to worry. Deep object hierarchies, though, are not locked in any way! Take this into account when you implement ICloneable. Nevertheless NSTM is a very convenient and efficient way to parallelize work.
What´s next?
You know almost everything about my Software Transactional Memory implementation. There´s only the integration with System.Transactions missing - but not for long ;-)
Resources
[1] Juval Löwy, Can´t Commit: Volatile Resource Managers in .NET Bring Transactions to the Common Type, http://msdn.microsoft.com/msdnmag/issues/05/12/transactions/default.aspx
Now that the basic data unit of my .NET Software Transactional Memory (NSTM) has been introduced - transacational objects (txo) aka INstmObject - who implement the Isolation property of transactions, the question is, where Atomicity comes from. Enter: the transaction log.
Recording Memory Interactions
The transaction log (txlog) records all objects you tackle during during a transaction. Whenever you write to a txo that´s logged in the txlog. Whenever you read from a txo that´s logged in the txlog. So the txlog contains a list of all objects interacted with in a transaction including their current values. Even though my previous posting might have suggested txo maintain a clone for their value it is in fact the txlog attached to each transaction.
When you read from or write to a txo you don´t really directly access its value. Rather the INstmObject goes to the current transaction and asks it what to do, which value to return or where to store a new value. The transaction then consults with its transaction log:
- If an object is accessed for the first time during the transaction a log entry for it is added to the txlog.
- If a txo is written to, the new value is put into its txlog entry instead of the txo itself. This is to isolate changes made to the same txo in different transactions from each other.
- If a txo is read from, the transaction checks which value to return. If a new value is already present then that´s chosen. If no new value has been assigned the current value is returned. Either the real current value from the txo - or the current value as cloned on the first read access if the clone option is CloneOnRead.
- Also the txo is validated if the transaction´s isolation level is Serializable. That means the current version number of the txo is compared to the version number when it was first access during the transaction. Validation fails if those versions do not match, which means some other transaction has committed changes to the object in the meantime. This is to avoid inconsistencies in the form of different values read from the same txo during a transaction. If you want to allow such changes then set the isolation level to ReadCommitted.
Any changes to transactional objects during a transaction are accumulated in the transaction log. Txo are thus never changed directly by an application. This provides Isolation and the first half of Atomicity: nothings happens to transactional objects if a transaction fails. Because if it fails, all changes recorded in the txlog are lost.
Ending a Transaction
A transaction can be ended in two ways: either by rolling it back and discarding all changes or by committing it.
Rolling back is easy: the transaction log simply is discarded. That´s it. No further effort is needed. No locks were helt on txo which would need unlocking. No changes were made which would need to be undone.
Committing a transaction on the other hand is a two step process:
- First all txo read from with more than just PassingReadOnly mode are validated. (Currently this is also true for ReadWrite mode txo, but I´m unsure if that´s necessary. Also currently I´m not content with how to switch between validation on Commit() only and validation on each Read().) During validation all transactional objects opened in ReadWrite mode also are locked. This is to freeze the current view on transactional memory for the duration of the commit. No other transactions must commit at the same time to the same txo.
Where locking comes into play deadlocks need to be avoided. Therefore all txos are kept in a sorted list so each transaction would lock them in the same order. This is a common way to give deadlocks no chance.
If any transactional object cannot be validated the commit is aborted and the transaction is rolled back. - Second all locked txos written to are visited again to copy their new values to the txo itself. At the same time the version number of each txo is incremented to allow for easy optimistic locking aka validation. Afterwards the txo is unlocked.
By locking modified txos (for a very short time) during commit Atomicity is ensured. An application either sees no changes at all when a transaction is rolled back - or all changes at once after Commit() has finished and all modified objects have been updated and unlocked.
What´s next?
Now that I´ve explained how a single transaction works it´s time to look at how mutiple concurrent transactions on one or more threads are managed. Stay tuned if you are interested to see how NSTM implements truely nested transactions.
In yesterday´s posting I introduced my C# implementation (NSTM) of the Software Transactional Memory (STM) concept. It is supposed to make concurrent programming easier than it is today using explicit locking of shared in-memory resources. With NSTM multithreaded processing becomes as easy as accessing RDBMS from multiple applications isolated from each other with transactions.
How ACID is NSTM?
Since NSTM provides transactionality on some resource and you´ve come to love the usual transaction ACID properties of database transactions [1], I should quickly explain in how far NSTM supports them:
- Atomicity: The whole purpose of NSTM is to provide atomicity across several operations on in-memory data. Any changes applied to INstmObjects between opening a NSTM transaction with NstmMemory.BeginTransaction() and closing it with INstmTransaction.Commit() are either all successful or none of them.
- Consistency: NSTM does not have a metadata concept so there are no independent consistency rules that could be observed during a transaction. If, for example, you want to implement a transactional queue data structure which of course internally defines some consistency rules, then your code needs to take care of enforcing consistency. However, you´ll get some help for this from the Isolation property of NSTM transactions.
- Isolation: Like with Atomicity the whole purpose of NSTM is to isolate changes to shared in-memory data structures from each other if they happen in different transactions which at the same time means on different threads. Changes during one transaction become only visible to others upon committing the transaction.
- Durability: Durability, i.e. protecting committed data against unexpected process abortion (e.g. through a power outage), obviously is of no concern when working just in-memory ;-) Volatile data is just that: volatile.
NSTM is not ACID, but just AI. But I think that´s perfectly ok. It´s not a lack, it´s a feature ;-) ACID properties are not absolute, but mirror what can go wrong when concurrently accessing databases. A non-persistent resource with no inherent rules thus does not need C and D. But how does it ensure A and I?
Transactional Objects
The basic unit of NSTM transactional memory is the INstmObject<T> which can be called a transactional object or txo for short. It´s allocated on the heap, so you can trust the .NET garbage collection to take care of it once it´s not needed anymore. Each txo wraps a piece of your application data ranging from scalar type values to complex object models, e.g.
1 INstmObject<int> i;
2 INstmObject<string> s;
3 INstmObject<MyStruct> r;
4 INstmObject<MyClass> c;
with MyStruct and MyClass defined as:
1 struct MyStruct
2 {
3 public int j;
4
5 public MyStruct(int value)
6 {
7 this.j = value;
8 }
9 }
10
11 class MyClass : ICloneable
12 {
13 public int i;
14
15 public MyClass(int value)
16 {
17 this.i = value;
18 }
19
20 #region ICloneable Members
21
22 public object Clone()
23 {
24 return new MyClass(this.i);
25 }
26
27 #endregion
28 }
You can allocate space for any type in transactional memory provided its values can be cloned by the NSTM infrastructure. Scalar types and strings don´t pose a problem here. Value types (struct) are easy too, as long as they just aggregate scalar type values. All other types need to implement ICloneable to let NSTM create a copy of their instances.
ICloneable is used instead of [Serializable] because so far it seemed to me that serialization leads to more problems than it solves:
- Serialization is slower by nature than cloning.
- Serialization (or deserialization to be more precise) leads to problems if your own txo types contain references to other transactional objects, since they must not be serialized and need to regain their identity during deserialization. Some overall management of txo would be necessary.
Values of transactional objects need to be cloneable to isolate transactions from each other. The default mode of NSTM transactions is CloneOnRead. That means, when you first read a txo in a transaction its value is cloned. Any subsequent reads will then also return the cloned value (or any changes you made to it). If some other transaction overwrites the txo´s value in the meantime you won´t see those changes. You keep on working with your own clone. This makes working with NSTM threadsafe out of the box. No need for you to worry about locking your own values stored in transactional objects.
If a transaction is opened in CloneOnWrite mode, though, the values of transactional objects are not cloned by default when you just read them. That makes working with NSTM a little bit faster, but it opens the door to inconsistencies. If after first reading a txo and later on reading it again another transaction commits a new value to the txo, then two different values would be returned within the same transaction. However, CloneOnWrite might be ok for you, if you keep an eye on when and how often you read from a txo.
Reading and Writing Transactional Memory
Reading from and writing to transactional objects unfortunately are very explicit:
int iValue = i.Read();
This is due to the difficulty to intercept regular memory access. If I had chosen to not allow scalar types for txo I could have used some form of proxy to intercept read/write to transactional object values. But I did not want to limit the type range in that way. Maybe in the future I find some easier way to interact with txo values or to get rid of explicit transactional objects alltogether. Code enhancing could be a way to achieve that. But right now I opted for a quick implementation with a reasonable programming model instead of the most intuitive and unobtrusive one.
Just calling Read() on a txo opens it in ReadWrite mode, though. Again, this is the safest option: Even if the clone mode is not CloneOnRead a clone of the current value is created, because the read mode signals, that your application intends to write to the txo at some point in the future.
i.Read()
is the same as
i.Read(NstmReadOption.ReadWrite)
However, if you know you will never write to a txo you can spare NSTM the effort to clone it (except for if clone mode is CloneOnRead). Just state ReadOnly as the read mode:
i.Read(NstmReadOption.ReadOnly)
Inconsistencies that might occur due to changes to transactional objects you read in your transaction by other transactions committing their changes in the meantime are then of course still detected. Either on the next read access to the txo or during commit of your transaction.
If you don´t care for such inconsistencies and want to save the effort of this kind of validation - e.g. because you just want to traverse a couple of txo - then read from a txo with PassingReadOnly:
i.Read(NstmReadOption.PassingReadOnly)
No consistency checks will be performed upon future reads with this option or during commit - unless you´ve subsequently read the txo with another option.
So much for reading from transactional objects. It´s explicit, but it´s simple.
Changing txo works likewise. You just call Write() and pass the new value to it:
i.Write(99);
If the value had already been cloned the clone is overwritten. In any case will the new value not yet be visible to any other parallel transaction. You have to call Commit() on the transaction to make new values public. Until then they are kept in a transaction local buffer, the transaction log.
Explicitly writing to a txo is the surest way for changing its value. And it´s the only way for scalar types and strings and any other value type. Objects, however, can also be changed implicitly. That´s why there is the ReadWrite read option:
1 MyClass x = c.Read();
2 x.i = 99;
Read() returns a clone of c´s value which then is changed. Although no explicit write happens afterwards the txo´s value is changed and can be committed. Were it not for the automatic clone of the txo´s value due to ReadWrite assigning 99 would change the original and "true" value of c. But that must not happen in order to isolate transactions from each other. That´s why the default read option is ReadWrite.
You could habe read the value with ReadOnly and change the field and NSTM would not have detected this violation, though. I did not build in any checks against that as explained above. Some form of proxy would have been necessary. So the only checks are the ReadWrite default read option and the CloneOnRead default clone option for transactions.
If you change them, NSTM assumes you know what you´re doing ;-) Feel free to do so and you´ll find many places in my collection implementations where I did it. But be careful! It´s a form of optimization and should not be done too easily.
What´s next?
Single transactional objects are isolated from each other by making changes only to copies of their values. But where are those changes kept? How are changes detected? How is the Atomicity of all changes ensured? That´s all a matter of the transaction log and will be explained in my next posting.
Resources
[1] Wikipedia, ACID, http://en.wikipedia.org/wiki/ACID
A while ago Carl Rosenberger - chief architect of db4o - mentioned in a personal conversation the concept of Software Transactional Memory (STM) [1, 8]. I was immediately intrigued by the idea - but the conversation went on. So I sat down later and read up on STM. And what I found made me very confident, STM was a very useful idea. Microsoft has recognized this too and is working on two versions of STM: a Haskell implementation [2, 3] and a more palatable version for mere mortal C# programmers called SXM [4].
However, these implementations are either not so close to the usual transactional programming model or need some unmanaged code like LibCMT [5] with its C# API. That made think about an easy to use purely managed code STM. And here it is: the .NET Software Transactional Memory. It´s written entirely in C# and integrates well with the overall .NET Framework, I´d say. But see for yourself...
What is a Software Transactional Memory all about?
So what´s the fuzz about STM? They make it much, much easier to program multithreaded code sharing in-memory resources. And I´d like to emphasize, an STM makes it easier, not necessarily more performing.
Parallel programming traditionally is quite hard. Once you go beyond starting just a couple of threads in the background using the .NET ThreadPool and try to access shared in-memory structures you´ll realize, multithreading is not for the faint of heart. Synchronizing access to those shared data structures can become very difficult to get right. Juggling around with all the locking options of the .NET Framework to avoid deadlock and not make the whole thing too slow by locking in a too coarse grained fashion quickly uses up a lot of your brainpower. And then comes debugging multiple threads...
To make a long story short: Multithreading with access shared in-memory resources today is much too difficult for the masses really exploit it. That means, all the brandnew multi-core/multi-processor power is of little use at least for your own applications. Sad, isn´t it?
But fortunately STM comes to the rescue. It promises to aleviate you from all the nitty gritty detail of shared data structure access synchronization by giving you the same programming model for in-memory data access as you are used to for database access. Instead of locking individual records in a database you just wrap all your access code in a transaction and let the database engine do the locking.
That´s right what STM offers: just wrap a transaction around your in-memory work and in the end commit all changes. Juval Löwy has already demonstrated something along this line based on the System.Transactions namespace [6]. However, his transaction aware collections are very coarse grained. Also .NET Transactions don´t care for threadsafety. They isolate work done on volatile data structures in different transactions - but they don´t help avoiding access conflicts of concurrently running code.
Sounds too abstract to you? Ok, let´s look at some code...
Simple Example
The canonical example for transactions probably is transfering money between two accounts. So why deviate from this? Here´s how such a transfer could look in memory:
1 static void Main()
2 {
3 double myAccount;
4 double yourAccount;
5
6 myAccount = 1000;
7 yourAccount = 500;
8
9 double amountToTransfer = 150;
10 myAccount -= amountToTransfer;
11 yourAccount += amountToTransfer;
12 }
All´s fine as long as nothing bad happens between subtracting the amount to be transferred from one account and adding it to the other account. If an error occurred during some processing between above lines 10 and 11 the accounts would be in an inconsistent state. It´s right the same as with databases. And as with databases the solution to the problem are transactions.
There´s the solution to the same problem using .NET Software Transactional Memory:
1 static void Main(string[] args)
2 {
3 INstmObject<double> myAccount;
4 INstmObject<double> yourAccount;
5
6 myAccount = NstmMemory.CreateObject<double>(1000);
7 yourAccount = NstmMemory.CreateObject<double>(500);
8
9 using (INstmTransaction tx = NstmMemory.BeginTransaction())
10 {
11 double amountToTransfer = 150;
12
13 myAccount.Write(myAccount.Read() - amountToTransfer);
14 yourAccount.Write(yourAccount.Read() + amountToTransfer);
15
16 tx.Commit();
17 }
18
19 Console.WriteLine("My account balance: {0}", myAccount.Read());
20 Console.WriteLine("Your account balance: {0}", yourAccount.Read());
21 }
The code structure has not changed - but the outcome is threadsafe and transactional at the same time. No explicit locks needed.
The only price to pay: You have to allocate transactional volatile data as NstmObjects in the transactional memory represented by NstmMemory. Instead of
double myAccount;
you write
INstmObject<double> myAccount;
And instead of calling new on the type you ask the transactional memory as a factory to create instances:
myAccount = NstmMemory.CreateObject<double>(1000);
This also entails an explicit Read() and Write() to get at the data wrapped in INstmObjects. Although, I think this is not too high a price to pay at the moment, I´d have liked to make the programming model easier. Microsoft´s STM implementations provide somewhat more simplicity in this regard - but overall I found them not really easy to use. For the time being and version 1.0 of my NSTM I´ll stick with the above approach. At least you´ll find it in other publications, too ;-) (see [7] for example)
But although it´s a little bit clumsy to have this indirection of INstmObject in the programming model I deem the translation from non-transactional, not threadsafe code to transactional and threadsafe code very straightforward. It becomes even more straightforward, if you switch to System.Transactions for the transaction handling:
1 using System.Transactions;
2 using NSTM;
3
4 namespace SimpleSample
5 {
6 class Program
7 {
8 static void Main(string[] args)
9 {
10 INstmObject<double> myAccount;
11 INstmObject<double> yourAccount;
12
13 myAccount = NstmMemory.CreateObject<double>(1000);
14 yourAccount = NstmMemory.CreateObject<double>(500);
15
16 NstmMemory.SystemTransactionMode = NstmSystemTransactionMode.EnlistOnAccess;
17 using (TransactionScope tx = new TransactionScope())
18 {
19 double amountToTransfer = 150;
20
21 myAccount.Write(myAccount.Read() - amountToTransfer);
22 yourAccount.Write(yourAccount.Read() + amountToTransfer);
23
24 tx.Complete();
25 }
26
27 Console.WriteLine("My account balance: {0}", myAccount.Read());
28 Console.WriteLine("Your account balance: {0}", yourAccount.Read());
29 }
Microsoft does not even offer this for its own STM implementations.
Looking ahead
STM promises to make parallel programming tasks on shared in-memory data structures much easier than it is today using all those pretty locking facilities. But of course there is more to it than the above simple example shows. How about isolation levels? How does the STM actually make concurrent access threadsafe? What about all those beloved collection data structures?
If you like, stay tuned. I´ll talk about all this in a future posting.
Download
You can download NSTM (short for .NET Software Transactional Memory) from its Google project hosting site: http://code.google.com/p/nstm/.
Enjoy - and let me know how you like it, how it performs for you, or what you think needs to be improved.
Resources
[1] Wikipedia, Software transactional memory, http://en.wikipedia.org/wiki/Software_transactional_memory
[2] Microsoft Channel9, Programming in the Age of Concurrency: Software Transactional Memory, http://channel9.msdn.com/Showpost.aspx?postid=231495
[3] Tim Harris et al., Composable Memory Transactions, http://research.microsoft.com/~simonpj/papers/stm/stm.pdf
[4] Microsoft Research, C# Software Transactional Memory, http://research.microsoft.com/research/downloads/Details/6cfc842d-1c16-4739-afaf-edb35f544384/Details.aspx
[5] Duilio Protti, LibCMT, http://libcmt.sourceforge.net
[6] Juval Löwy, Can´t Commit: Volatile Resource Managers in .NET Bring Transactions to the Common Type, http://msdn.microsoft.com/msdnmag/issues/05/12/transactions/default.aspx
[7] Maurice Herlihy et al., Software Transactional Memory for Dynamic-Sized Data Structures, http://www.cs.rice.edu/~wns1/papers/2003-PODC-DSTM.pdf
[8] Derrick Coetzee, Developing for Developers: Software Transactional Memory, http://blogs.msdn.com/devdev/archive/2005/10/20/483247.aspx
[9] Robert Ennals, Software Transactional Memory Should Not Be Obstruction-Free, http://web.cecs.pdx.edu/~walpole/class/cs510/papers/19.pdf
More Posts