Transactions

​

​

Sami Rollins

Overview

• A transaction is a set of operations on objects that must be performed as an indivisible unit by the server(s) managing those objects.
• All operations are carried out or none of the operations are carried out.
• A successful transaction is committed
• An unsuccessful transaction is aborted

Example

• Bank account transfer
• a.withdraw(100)
• b.deposit(100)

ACID

• ACID is a mnemonic used to remember the properties of transactions
• Atomicity: all or nothing
• Consistency: the system goes from one consistent state to another consistent state
• Isolation: intermediate effects are not visible to other transactions
• Durability: effects are saved to permanent storage

ACID – Bank account example

• ACID is a mnemonic used to remember the properties of transactions
• Atomicity: either both deposit and withdrawal happen, or neither happen
• Consistency: the sum of all accounts equals the branch total
• Isolation: cannot see the state of accounts after withdrawal but before deposit
• Durability: recover operations if server crashes

Ensuring isolation

• Option 1: perform transactions serially
• Why is this suboptimal?

Ensuring isolation

• Option 1: perform transactions serially
• Why is this suboptimal?
• does not allow concurrency
• The transactions below could easily be interleaved

​

T1:                   T2:

a.withdraw(100)       c.withdraw(100)

b.deposit(100)        d.deposit(100)

​

Serial equivalence

• Transactions are serially equivalent or serializable if the effect is the same as a serial execution

​

T:                       U:

bal = b.getBalance()     bal = b.getBalance() 

b.setBalance(bal*1.1)    b.setBalance(bal*1.1)

a.withdraw(bal/10)       c.withdraw(bal/10)

​

Lost updates

T:

bal = b.getBalance()

b.setBalance(bal*1.1)

a.withdraw(bal/10)

​

​

​

U:

bal = b.getBalance()

b.setBalance(bal*1.1)

c.withdraw(bal/10)

​

• Suppose b.balance is initially $200
• Result should be $242
• T then U or U then T
• If execution is interleaved as above then result is $220

Inconsistent retrievals

T:

a.withdraw(100) 

​

b.deposit(100)

​

​

​

U:

aBranch.branchTotal()

• U sees a value that is $100 short

Read skew

T:

​

a.withdraw(100) 

b.deposit(100)

​

​

​

U:

balance = a.getBalance()

​

​

balance = b.getBalance()

​

• It looks like the total is $1,100

Dirty reads

T:                     U:

bal1 = a.getBalance()             

a.setBalance(bal1+10)

                       bal2 = a.getBalance()   

a.setBalance(bal2+20)

                       commit

abort

​

• U cannot be undone

Premature writes (Dirty writes)

• Some systems store the before image of an object with a write and roll back to that value in the event of an abort. This is a problem if another process overwrites the value before the abort.

​

T: a.setBalance($105) - (before image: 100)

U: a.setBalance($110) - (before image: 105)

​

• U commits and T aborts and resets to 100 – should be 110
• If T aborts then U aborts the result will be 105 but should be 100

Write skew

T:

bal = b.getBalance()

if a.balance >= bal/10

b.setBalance(bal*1.1)

a.withdraw(bal/10)

​

​

​

U:

bal = b.getBalance()

​

​

​

if c.balance >= bal/10

b.setBalance(bal*1.1)

c.withdraw(bal/10)

​

• Suppose b.balance = $200 a.balance = $20 c.balance = $20
• T then U - a = $0; U condition fails
• U then T - c = $0; T condition fails
• If execution is interleaved as above then a = $0 and c = $0

Serial equivalence

T:

bal = b.getBalance()

b.setBalance(bal*1.1)

a.withdraw(bal/10)

​

​

​

U:

​

bal = b.getBalance()

b.setBalance(bal*1.1)

c.withdraw(bal/10)

​

• This interleaving is OK
• resulting values are the same as they would be if T was executed before U
• How about a serially equivalent interleaving that would be the same as U before T

Serial equivalence

• For two transactions to be serially equivalent, all pairs of conflicting operations must execute in the same order on all objects they both access
• Which operations conflict below?  

​

​

T:                         U:

x=read(i);                 read(j);

write(i, 10);              write(j, 30);

write(j, 20)               z=read(i)

​

Example

• Give three serially equivalent interleavings of the following transactions T and U:

​

T: x=read(j); y=read(i); write(j, 44); write(i, 33)

U: x=read(k); write(i, 55); y=read(j); write(k, 66)

​

Achieving serial equivalence

• Locking
• most common approach
• transaction locks an object before it is accessed
• transaction releases the lock when complete
• May lead to deadlock
• transaction T waits for a lock held by U while transaction U waits for a lock held by T

​

Two-phase locking

• Phase 1: lock growing phase
• a client may acquire locks
• Phase 2: lock shrinking phase
• a client may release locks
• Once a lock is released, no new locks may be acquired
• Solves the lost update and inconsistent retrievals problem
• Does NOT solve the dirty read and premature write problem

Strict two-phase locking

• Locks are held until a transaction is committed or aborted
• Ensures that a transactions does not release locks on modified objects and then decide to abort

Recap

T:                         U:

read(a)                  read(d)

write(b, 10)               write(d, 30)

write(c, 20)               z=read(f)

​

​

Recap - Option 1: Global Lock

lock.acquire()                        

t1: read(a)                 

t2: write(b, 10)              

t3: write(c, 20)               

lock.release()

lock.acquire()

u1: read(d)

u2: write(d, 30)

u3: z=read(f)

lock.release()

Recap - Option 1: Global Lock

lock.acquire()                        

t1: read(a)                 

t2: write(b, 10)              

t3: write(c, 20)               

lock.release()

lock.acquire()

u1: read(d)

u2: write(d, 30)

u3: z=read(f)

lock.release()

No concurrency allowed!

Recap - Option 2: Lock per object

T locks a                        

t1: read(a)                 

T unlocks a

U locks d

u1: read(d)

u2: write(d, 30)

U unlocks d

T locks b

t2: write(b, 10)

U locks f

u3: z=read(f)

U unlocks f

T locks c    

t3: write(c, 20)             

T unlocks b; T unlocks c

​

Recap - Option 2: Lock per object

T locks a                        

t1: read(a)                 

T unlocks a

U locks a; U locks d

u1: read(d)

u2: write(a, 30)

U unlocks a; U unlocks d

T locks b

t2: write(b, 10)

U locks f

u3: z=read(f)

U unlocks f

T locks f    

t3: write(f, 20)             

T unlocks b; T unlocks f

​

Recap - Option 2: Lock per object

T locks a                        

t1: read(a)

T unlocks a

U locks a; U locks d

u1: read(d)

u2: write(a, 30)

U unlocks a; U unlocks d

T locks b

t2: write(b, 10)

U locks f

u3: z=read(f)

U unlocks f

T locks f    

t3: write(f, 20) 

T unlocks b; T unlocks f

​

Interleaving is not serially equivalent!

Recap - Option 2: Lock per object

T locks a                        

t1: read(a) (a -> 100)                 

T unlocks a

U locks a; U locks d

u1: read(d) (d -> 200)

u2: write(a, 30) (a = 30)

U unlocks a; U unlocks d

T locks b

t2: write(b, 10) (b = 10)

U locks f

u3: z=read(f) (f -> 300)

U unlocks f

T locks f    

t3: write(f, 20) (f = 20)

T unlocks b; T unlocks f

​

a=100; d=200; f=300

T sees a as 100; U sees f as 300

T then U - T sees a as 100 U sees f as 20

U then T - U sees f as 300 T sees a as 30

Recap - Option 3: Two-Phase Locking

T locks a                        

t1: read(a)                 

T unlocks a

U locks a; U locks d

u1: read(d)

u2: write(a, 30)

U unlocks a; U unlocks d

T locks b

t2: write(b, 10)

U locks f

u3: z=read(f)

U unlocks f

T locks f    

t3: write(f, 20)             

T unlocks b; T unlocks f

​

Cannot release a lock and then acquire a new lock.

Recap - Option 3: Two-Phase Locking

T locks a                        

t1: read(a)                 

U locks d

u1: read(d)

​

T locks b

t2: write(b, 10)

T locks f   

t3: write(f, 20)             

T unlocks a; T unlocks b

T unlocks f

U locks a; U locks f

u2: write(a, 30)

u3: z=read(f)

U unlocks a; U unlocks d; U ulocks f

​

Recap - Option 3: Two-Phase Locking

T locks a                        

t1: read(a)                 

U locks d

u1: read(d)

​

T locks b

t2: write(b, 10)

T locks f   

t3: write(f, 20)             

T unlocks a; T unlocks b

T unlocks f

U locks a; U locks f

u2: write(a, 30)

u3: z=read(f)

U unlocks a; U unlocks d; U ulocks f

T aborts

​

​

T may decide to abort!

Recap - Option 4: Strict Two-Phase Locking

T locks a                        

t1: read(a)                 

U locks d

u1: read(d)

​

T locks b

t2: write(b, 10)

T locks f   

t3: write(f, 20)

T aborts (unlock all)             

U locks a; U locks f

u2: write(a, 30)

u3: z=read(f)

U commits (unlock all)

​

​

Example

• Can we achieve concurrency if using strict two-phase locking in the following:

​

T: x=read(j); y=read(i); write(j, 44); write(i, 33)

U: x=read(k); write(i, 55); y=read(j); write(k, 66)

​

Deadlock

T: a.deposit(100); b.withdraw(100)

U: b.deposit(50); a.withdraw(50)

​

• T1: T locks a
• U1: U locks b
• T2: T tries to lock b – must wait for U
• U2: U tries to lock a – must wait for T

Preventing deadlock

• Atomically acquire all locks at the beginning of the transaction
• restricts concurrency
• may not know which locks are needed at the beginning of a transaction
• Request locks in a predefined order
• same issues

Wait-for graph

• A cycle in the graph indicates a deadlock

Detecting deadlock

• A lock manager maintains a wait-for graph
• If a cycle is detected the lock manager forces a transaction to abort

​

• Alternative: timeouts
• after a period of time, a lock becomes vulnerable
• if a transaction is waiting to access an object protected by a vulnerable lock then the lock is broken
• timeouts may be premature in heavily loaded system

​

Distributed transactions

• A transaction may access objects at multiple servers
• If a transaction commits at one server it must commit at all servers
• If a transaction aborts at one server it must abort at all servers

Distributed transactions

• A coordinator process manages the transaction. The coordinator process is on one of the servers.
• Each server that manages an object used in the transaction is a participant
• When a participant joins it informs the coordinator

Two-phase commit

• Two-phase commit is used by the coordinator to ensure that all participants either commit or abort
• Phase 1: The coordinator asks each participant whether it can commit. A participant may not change its vote to abort once it has voted commit.
• Phase 2: Once all participants have voted if any participant has voted to abort then an abort is sent to all participants. If all participants voted to commit then a commit is sent to all participants.
• The participants inform the coordinator that they have committed.

Handling failure

• Server crash: To address the failure of a participant server, servers store the state of the transaction to permanent storage so that processes may be restarted and recover.
• Communication failure: To address communication failure, timeouts are used. If the coordinator times out waiting for participants to vote then the transaction will eventually be aborted. If a participant times out waiting for the final vote from the coordinator it will ping the coordinator. If the coordinator has failed it will wait for it to be restarted.