Buying some kickass hardware for Multiverse

April 23, 2009

This week I’m going to order my kick ass system for Multiverse, a STM implementation I’m working on. 2 Intel Xeon E5520 cpu’s (4 cores each + hyperthreading -> 16 virtual processors in total!). 12 Gig DDR3 1066 Mhz ram, a super fast Intel 32 gigabyte SSD and 2x 1.5 terabyte old school disk drives. And it is going to run Linux and perhaps even Solaris (I want to play with D-trace).

As soon as I have this up and running (and moved it somewhere so I don’t have to look at it) I can run some serious performance and scalability tests. At the moment I only have a dual core laptop for this purpose and that is not sufficient.

And if I’m lucky, I can upgrade the cpu’s in the near future to 8 cores each (resulting in 32 virtual processors!).

MVCC & TL2: concurrency

April 22, 2009

Last month I have been studying TL2 (Transactional Locking 2) and one thing occurred to me: the difference between MVCC and TL2 isn’t that big. The biggest reason to prefer MVCC above traditional lock based concurrency control systems, is that the former allows higher concurrency. With traditional lock based concurrency control systems, to provide a consistent view (so a transaction won’t observe changes made by other transactions executing in parallel) records are locked as they are encountered (encounter time locking). This leads to writers blocking readers, and readers blocking writers.

With MVCC there is no need to rely on locking to provide a consistent view; instead of relying on locks, previous versions of a record can be reconstructed for reading purposes. This means that only writers block writers, and this should have a positive impact on concurrency. For MVCC it doesn’t matter if you use encounter time locking or commit time locking (databases typically use encounter time locking as soon as a insert/delete/update occurs).

In TL2 a field/object (depending on the granularity of the Transactional Memory) doesn’t need to be locked or reconstructed, because as soon as field is read, it is localized: a transaction gets its own private copy (TL2 uses commit time locking). This serves the following consistency purposes:

  1. a read done by a transaction, will never see writes made by other transactions executing in parallel.
  2. a read done by a transaction, will always see the writes made by itself

So just as MVCC, with TL2 readers don’t block writers and a writers don’t block readers. But unlike MVCC, instead of revering back to an older version if a ‘too’ new version is found, the transaction is retried. And this in principle looks a lot like the ORA-01555 Snapshot Too Old error from Oracle.

Multiverse and the JMM

April 18, 2009

You don’t need to worry about the JMM while using Multiverse. The JMM is defined in happens before rules, and Multiverse provides a happens before relation on a transaction commit and transaction start. It probably will be based on a CAS write and read of object state. A CAS write/read can be compared to a volatile write/read and the last one is one of the before rules. So one of the things you can say goodbye to is using volatile variables.

Some STM thoughts, Part I

April 14, 2009

Last 5 months I have been working on Multiverse and I have gained a lot of new insights:

  1. Concurrency control in an stm is nothing else than saying something about the ordering of transaction execution.
    If there is no shared state, the result of executing transactions will be the same no matter the order, so they are allowed to execute concurrently. If there is shared state, the result of the transactions needs to be the same as one of the 2 possible sequential executions. So concurrency control is creating a partial ordering in the execution of transactions.
  2. Locking essentially leads to an ordering of concurrent executing transactions.
  3. A write-conflict is nothing more than an illegal interleaving of concurrent executing transactions. A write-conflicts happens when an another transaction writes to one or more shared addresses after the current transaction starts and before it commits. A write-conflict would be impossible if transactions execute sequentially.
  4. A deadlock also is nothing more than an illegal interleaving of concurrent executing transactions. Since there is shared state (the locks for example) one transaction needs to execute before the other, or after the other. In both cases a deadlock is impossible because one transaction has finished completely, and releases its locks, before the other begins.