Database Theory – Transaction Recovery and Rollback Explained

database-theoryrecoverytransaction

As I understand:

UNDO: Undoing a write item operation consists of examining its log entry [write_item, T, X, old_value, new_value] and setting the value of item X in the database to old_value. UNDO is always performed in the reverse order from the order in which the operations were written in the log.

REDO: Redoing a write item operation consists of examining its log entry [write_item, T, X, new_value] and setting the value of item X in the database to new_value.

In a transaction recovery algorithm, for example the one outlined in the Q & A Understanding Transaction Recovery

and let's say we have a schedule such as:

R1(X) R2(Y) W1(X) C W2(Y)

where C denotes a crash. According to the algorithm, we should UNDO T1, but REDO T2, since it is still active at the time of crash. But T2 hasn't had any Write operations, so what exactly does an UNDO entail here? Does anything need to actually happen? And where does the concept of a rollback come in? Is that just implicit in an UNDO?

Best Answer

Assuming that R means Read and W means Write, then the work you're proposing is like this:

W1(x) C

That's it. Reads are irrelevant for recovery. And a crash denotes the end, you can't have a write after crash. So the task of recovery is to redo the one write and then undo it, since there is no Commit.

The algorithm is very simple:

Redo everything, in forward order
Undo anything not committed, in reverse order, generating a compensating write for every action being undone.

A good explanation is the ARIES paper.

See also How to read and interpret the SQL Server log on my blog.

Related Solutions

Transaction and data consistency during a failure

Bear with me, this is a complicated question to clarify and we may go through a few rounds of edit and commenting to plug the gaps. From the way your question is phrased I'm guessing you're not differentiating the atomicity, isolation, consistency and durability elements of ACID.

When a database begins a transaction, all statements executed in that transaction are isolated and atomic (and consistent and durable). These are pretty much the definition of a transaction.

The isolation part of ACID is widely misunderstood. There is a degree to which transactions are isolated from each other, as determined by the transaction isolation level. The other elements of ACID are absolute.

Wikipedia states that there are some databases that insure a transaction remains isolated by locking the rows and not unlocking them until the transaction has committed.

This relates to the isolation part of ACID, it doesn't have any impact on your main question.

My question is: How can a database that solely relies on locking guarantee consistency? If a power outage occurs mid-transaction, there may be data partially written to the row.

Your example is not concerned with consistency, it's durability and atomicity. These are guarenteed by write ahead logging (WAL). With WAL, all changes are written to the undo/redo log before they are applied to the data.

In the event of a power failure, a recovery process is run which will read the log to identify a) "mid-flight" transactions that did not commit and b) transaction that did commit but which were not applied to the data. The changes from a) transactions are undone (rolled back), returning the data to its pre-transaction state. The changes from b) are redone (rolled forward), ensuring the data is in the expected post-transaction state.

Even for databases like SQL Server that use a Temporary DB to perform all the transactions, what happens if a power outage occurs as the database is committing the transactions to disk?

TempDB (assuming that's what you're referring to) has absolutely nothing to do with SQL Servers execution of transactions. Are you confusing the role of TempDB in snapshot isolation levels?

SQL Server Transaction Log File – Detailed Contents Explained

The difference is that what you call "standard commands" have implicit transactions (as in "not explicit" and not real implicit transactions which mean something different), so every time you issue an INSERT command without an explicit transaction, it will open a transaction, insert the data and automatically commit. This is called an autocommit transaction.

This is also why you can't rollback this INSERT: it's already committed. So the rule is the same as explicit transactions: you can't rollback once they've been committed.

You can see what I mean directly from inside SQL Server.

Microsoft ships SQL Server with a DMF called sys.fn_dblog that can be used to look inside the transaction log of a given database.

For this simple experiment I'm going to use the AdventureWorks database:

USE AdventureWorks2008;
GO

SELECT TOP 10 *
FROM dbo.Person;
GO

INSERT INTO dbo.Person (FirstName, MiddleName, LastName, Gender, Date)
VALUES ('Never', 'Stop', 'Learning', 'M', GETDATE());
COMMIT;

BEGIN TRAN;
INSERT INTO dbo.Person (FirstName, MiddleName, LastName, Gender, Date)
VALUES ('Never', 'Stop', 'Learning', 'M', GETDATE());
COMMIT;
GO

SELECT *
FROM sys.fn_dblog(NULL, NULL);
GO

Here I'm doing two inserts: one with and one without an explicit transaction.

In the log file you can see that there's absolutely no difference between the two:

Autocommit vs Explicit Transactions

The red one is the INSERT within an autocommit transaction and the blue one is the INSERT with an explicit transaction.

As for the 3rd party tools you mention, yes they analyse the database log and generate normal T-SQL code to "undo" or "redo" the operations. By normal I mean they don't do anything special other than generate a script that will have the effect of doing exactly the opposite of what is in the log file.

Best Answer

Related Solutions

Transaction and data consistency during a failure

SQL Server Transaction Log File – Detailed Contents Explained

Related Question