MVCC & TL2: concurrency

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.

Advertisements

5 Responses to MVCC & TL2: concurrency

  1. Colin says:

    Hey Peter, thanks for posting your thoughts and links on transactions, it’s an interesting series.

    Cheers,
    Colin

    • pveentjer says:

      Thanks! 🙂

      Atm I’m rewriting multiverse btw. The single snapshot approach is removed so that it scales better and I also have less worries about gc. The new approach resembles the TL2 approach more (although I don’t need to re-read the version field to prevent zombie threads) because I use an object that contains the state + version, so both can be read atomic. I don’t know how well this is going to perform, but I’ll see.

      • Colin says:

        Ok, great – I’ll be interested to take a look. I’m totally swamped at the moment, but when I get a chance I’d like to take a look at the code. I’ll read that TL2 paper when I get a chance too.

      • Christian Vest Hansen says:

        That sounds like it’s closer to the Clojure STM. 🙂

        Clojure is also said to implement a form of barging. I’m not totally sure, but I think it is to mitigate the problem of many small transaction causing a longer-running one to constantly retry and thereby starve.

        Is this something that multiverse deals with?

  2. pveentjer says:

    At the moment Multiverse has no protection against starvation, but I have been thinking how to add a contention manager that is non blocking (unless you have a blocking policy of course). I have placed it on the backlog.

    So much to do, so little time.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: