Previous | Next --- Slide 42 of 64
Back to Lecture Thumbnails

This log is called Write-ahead log (WAL) in database systems, and is generally used to guarantee durability and atomicity.


In eager versioning, if there's a memory write, memory is immediately updated, but because we have to consider the case that the transaction is aborted, we maintain a log of the old values. When an abort needs to occur (when you see someone else's write before you commit), you walk through the undo log and write those contents to memory. This makes committing easy because you just have to squash the undo log, but aborting takes more work.


When exactly do we know to abort the transaction? Is it when the memory realizes there is a race going on? Or is this implementation specific?

But if we are allowing two processors to write to memory at the same time and just aborting the changes, won't this lead to lots of cache invalidations, resulting in poor performance?


How would we be able to tell if we are observing a write that has not occurred if we are only looking at memory? Would we need to look at the undo log from other transactions in order to tell, and wouldn't that make writing expensive?


Also confused about when the abort would occur. In this diagram, it seems like the write occurs at the same time the undo log is created. So, in this case, how would it know that it needs to abort?

The only situation I can think of is that since there are two steps (writing and creating the undo log), you do one first (create the undo log) and then immediately try to write. If the write observes a different value from what the undo log holds, then it will abort. Otherwise, it will commit.


Eager versioning can cause other processors to observe an uncommitted value right? ie. in this example, a different processor might be able to see x=15 before the undo happens. This seems problematic, even if we aren't trying to write from the other processor.


From the property of isolation of transactions, transaction results shouldn't be visible to others before committing. How is this achieved with eager versioning since memory is already modified?


@trappedin418 @qqkk This is achieved with pessimistic detection. At each read/write, the transactions checks the others for conflicts. If there is a conflict, then the conflicting transaction is either aborted or stalled. So right before the transaction sees the "already committed write", the transaction system prevents it from continuing. This maintains the eager versioning invariant.


@trappedin418: this is a problem when you try to access memory locations that are supposed to be transactional without going through the transaction interface. There are various names for safety properties that deal with this, and various schemes to deal with it. I don't have time to elaborate right now but this has a summary of some of the issues in one of the later sections.

Also, this is part of the reason why Haskell people particularly like STM, since the type system of that language prevents such things (accessing transactional memory without going through transactions) from happening.