STM and MVCC Considerations II

In my previous post I mentioned an isolation anomaly that can happen with MVCC systems (for example in Oracle). The cause of this issue is that a transaction in a MVCC system doesn’t care if the data it only reads, is updated by a different transaction. MVCC provides a stable view over the system by maintaining multiple versions of the same data, so it doesn’t need to worry about other transactions updating data it has read, because the transaction won’t see these updates. The only thing it needs to worry about it is detecting if another transaction has updated the same data the transaction wants to update. If such a write conflict is found, the transaction can’t commit. If better serialization behavior is needed, all data that was touched by the transactions (the reads and the writes) needs to be checked for conflicts.

If we look at the example again:

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

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

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

If transaction1 (calling foo) executes concurrently with transaction2 (calling bar) one of the the following 2 scenario’s happens (the commit is atomic):

  1. transaction1 commits before transaction2: transaction2 is aborted because the stack1 it has read, has been updated by transaction1
  2. transaction2 commits before transaction1: transaction1 is aborted because the stack2 it has read, has been updated by transaction2

Of course this improved isolation is not free because there is more data to check. And it can leads to more retries of transactions and this increases the chance of a livelock. But is nice to see that this problem can be solved.

With the STM implementation I’m currently working on, it is quite easy to realize. When an object is read in a transaction, and it has not been read before, the dehydrated version (stored in the STM) of that object is asked to provide a hydrated version. This hydrated version is logged inside the transaction, to make sure that the same hydrated version is returned every time. So since the transaction tracks all reads and writes, enhancing the conflict detection would be easy.

Advertisements

One Response to STM and MVCC Considerations II

  1. […] are exploring is Software Transactional Memory (STM). Clojure uses an STM and seems like lots of folks are exploring it right now as a […]

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: