Deep in Transaction (2)

In last blog, we have mentioned that the job of a transaction is to keep state consistent when

• there are multiple transactions access object concurrent;
• there are server crash/failure;

And we have discussed how a transaction will handle crash of server & client in deign level. Today, we focus on how transaction make objects consistent when multiple client access them, i.e. the Concurrency Control of transaction.

Why Transaction

Before dive into how to do it, we need to understand why we need it, or what problems may arise when concurrent access happens and we don’t control them.

Access at Same Time

We will illustrate two famous problems of concurrent problems by bank deposit/withdraw examples.

Lost Update

Transaction T	Transaction U
balance=b.getBalance();	balance=b.getBalance();
b.setBalance(balance+10);	b.setBalance(balance+20);
b 10	b 10
balance=b.getBalance(); 10
	balance=b.getBalance(); 10
	b.setBalance(balance+20); 30
b.setBalance(balance+10); 20

If transaction is used correctly, the result should be 40, not 20, which is because the Transaction U's update is lost.

Inconsistent Retrieval

Transaction V	Transaction W
a.withdraw(10);	sum=b.getBalance()+a.getBalance()
b.deposit(10);
a 10, b 0	a + b = 10
a.withdraw(10); 10
	sum=b.getBalance()+a.getBalance(); 0
b.deposit(10); 10

The Transaction W read a inconsistent state of account a & b, which causes the wrong sum.

Conflicting Operations

The reason that Lost Update & Inconsistent Retrieval happens is there exists conflicting operations between multiple transactions. When we say that a pair of operations conflicts we mean that their combined effect depends on the order in which they are executed.

For example, the following Transaction T & U has conflicts (1 & 4, 2 & 3).

Timeline	Transaction T	Transaction U
1	x = read(i); write(i, 10)
2		y = read(j); write(j, 30)
3	write(j, 20)
4		z = read (i)

This problem can be solved by making two transactions serially equivalent. For two transactions to be serially equivalent, it is necessary and sufficient that all pairs of conflicting operations of the two transactions be executed in the same order at all of the objects they both access.

For example, Transaction order of conflicting operations in T & U is like following, which is why this execution is not right:

1, 4: T -> U
2, 3: U -> T

After Transaction Aborts

Even we make two transactions serially equivalent, some problems are still not solved, which caused by transaction aborts.

Dirty Read:

Transaction T	Transaction U
balance=b.getBalance();	balance=b.getBalance();
b.setBalance(balance+10);	b.setBalance(balance+20);
b 10	b 10
balance=b.getBalance(); 10
b.setBalance(balance+10); 20
	balance=b.getBalance(); 20
	b.setBalance(balance+20); 40
	commit U
abort T

The Transaction T abort finally, so the final result should be 30, but not 40,

Premature Writes

Transaction T	Transaction U
b.setBalance(15);	b.setBalance(20);
b 10	b 10
b.setBalance(15); 15
	b.setBalance(20); 20

Now, if U commit first, then T aborted, the balance should be 20, but Transaction T only know b last value is 10, so it will revert to b 10.

Two Phase Locking

Generally, it is required that transactions delay both their read and write operations so as to avoid both dirty reads and premature writes.
We saw that because transactions may abort, strict executions are needed to prevent dirty reads and premature writes. Under a strict execution regime, a transaction that needs to read or write an object must be delayed until other transactions that wrote the same object have committed or aborted. To enforce this rule, any locks applied during the progress of a transaction are held until the transaction commits or aborts. This is called strict two-phase locking.

To Be Continued

In this blog, we talk about four kinds of problems when we lack of transactions:

• Lost Update;
• Inconsistent Retrieval;
• Dirty Read;
• Premature Write;

Later, we will go on about how we implement a transaction to solve those problems.

Written with StackEdit.