STM and MVCC considerations

I’m working on a Software Transaction Memory (STM) implementation for experimentation purposes. And it uses Multi Version Concurrency Control (MVCC) just like Oracle. The big advantage of MVCC is that it is highly concurrent because it doesn’t rely on locks to prevent other transactions from interfering when you only need to read data. When a transaction begins, it gets a snapshot of the world and this snapshot remains constant even if other transactions are making changes. Changes made by the transaction are visible to itself of course.

The problem however is that MVCC could give subtle isolation problems. Eg.

StmStack stack1 = new StmStack();
StmStack stack2 = new StmStack();

void foo(){
	transaction{
		stack1.push(stack2.size());	
	}
}

void bar(){
	transaction{
		stack2.push(stack1.size());	
	}
}

If foo en bar are called concurrently, you would expect one of the following states:

  1. stack1 contains 0 and stack2 contains 1 (if transaction1 is executed first)
  2. stack1 contains 1 and stack2 contains 0 (if transaction2 is executed first)

But with MVCC stack1 and stack2 both can contain the value 0! This is because the transactions don’t see the changes made by other the transaction, and since there is no write conflict (both transactions write to a different stack), both transactions can be committed. If this is an issue in practice.. I don’t know.. but it is something to keep in mind. I have placed a similar post about this issue in Oracle.

Advertisements

3 Responses to STM and MVCC considerations

  1. Patrick Wright says:

    Hi–I assume you’ve looked at Clojure? It is a Lisp dialect, written for the JVM–which implements an STM model using MVCC. See http://clojure.org/refs as well as the many presentations available online. If you haven’t found it, this discussion (http://blogs.azulsystems.com/cliff/2008/05/clojure-stms-vs.html) for and against STM covers a lot of material, including input from Rich Hickey, author of Clojure, and João Cachopo, author of JVSTM http://web.ist.utl.pt/~joao.cachopo/jvstm/.

    Cheers
    Patrick

  2. pveentjer says:

    Hi Patrick. I have stumbled upon it while looking for other STM/MVCC implementations. This morning I read most of the paper but it seems that a large part of the document is nothing more then implementation details of their approach or explanation of general MVCC concepts.

    With the PerTransactionBoxes and delayed computations it gets more interesting. I have to read the last few pages.

  3. […] and MVCC Considerations II In my previous post I mentioned an isolation anomaly that can happen with MVCC systems (for example in Oracle). The […]

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: