CIS 455/555: Internet and Web Systems
2PL and 2PC November 29, 2020
© 2020 A. Haeberlen, Z. Ives, V. Liu University of Pennsylvania
1
Plan for today
n Cloud computing
n Utility computing model n Brief overview of EC2
n Transactions n ACID properties
n Concurrency control: 2PL
n Distributed transactions: 2PC
n Consensus n Paxos
n Fault models
n Byzantine Fault Tolerance
© 2020 A. Haeberlen, Z. Ives, V. Liu University of Pennsylvania
2
NEXT
“No Payment” isn’t the only source of failure
n Suppose we start to transfer the money, but a server goes down…
Purchase:
Write Item.sold = True Write Buyer.bal= Buyer.bal – $100 Write Seller.bal= Seller.bal + $100
CRASH!
© 2020 A. Haeberlen, Z. Ives, V. Liu
3
ACID Semantics
n Atomicity: operations are atomic, either committing or aborting as a single entity
n Consistency: the state of the data is internally consistent
n Note: NOT like the consistency of “sequential consistency” n Isolation: all operations act as if they were
run by themselves
n Durability: all writes stay persistent!
n What would a violation of each property
look like? © 2020 A. Haeberlen, Z. Ives, V. Liu
4
Plan for today
n Transactions
n ACID properties
n Concurrency control: 2PL
n Distributed transactions: 2PC
n Consensus n Paxos
n Fault models
n Byzantine Fault Tolerance
© 2020 A. Haeberlen, Z. Ives, V. Liu University of Pennsylvania
5
NEXT
© 2020 A. Haeberlen, Z. Ives, V. Liu
Concurrency control
n A means of ensuring that transactions are serializable
n There are many methods, of which we’ll
see one
n Lock-based concurrency control (2-phase locking)
n Optimistic concurrency control (no locks – based on
timestamps)
n Multiversion CC n…
6
Recall: Locking
Critical section
n Idea: Implement locks
n If LOCK(X) is called and X is not locked, lock X and continue n If LOCK(X) is called and X is locked, wait until X is unlocked n If UNLOCK(X) is called and X is locked, unlock X
n From Lecture 3, different ways to use locks
n One for each critical section
n One for each object
© 2020 A. Haeberlen, Z. Ives, V. Liu University of Pennsylvania
7
void transferMoney(customer A, customer B, int amount)
{
showMessage(“Transferring “+amount+” to “+B);
int balanceA = getBalance(A);
int balanceB = getBalance(B);
setBalance(B, balanceB + amount);
setBalance(A, balanceA – amount);
showMessage(“Your new balance: “+(balanceA-amount));
}
Two-phase locking (2PL)
© 2020 A. Haeberlen, Z. Ives, V. Liu
Strict time Non-strict time
n Strict Two-phase Locking (Strict 2PL) Protocol:
n Each transaction must obtain:
n aS(shared)lockonobjectbeforereading
n anX(exclusive)lockonobjectbeforewriting
n AnownerofanSlockcanupgradeittoXifnooneelseis holding the lock
n All locks held by a transaction are released when the transaction completes
n Locksarehandledina“growing”phase,thena“shrinking”phase
n (Non-strict)2PLVariant:Releaselocksanytime,butcannotacquire locks after releasing any lock.
#locks held
#locks held
© 2020 A. Haeberlen, Z. Ives, V. Liu
Aborting a transaction
Strict 2PL
n Shadowdata:throwitaway
n Logging:rollbackloggedchanges
Non-strict 2PL:
n If a transaction Ti is aborted, all its actions have to be undone
n Not only that, if Tj reads an object last written by Ti, Tj must be aborted as well!
n Actionsareundonebyconsultingatransactionlog n Intheworstcase:cascadingaborts
© 2020 A. Haeberlen, Z. Ives, V. Liu
A danger with locks: Deadlocks
n Deadlock: Cycle of transactions waiting for locks to be released by each other
n A waits for a lock that B holds n B waits for a lock that A holds
n Three ways of dealing with deadlocks: n Deadlock prevention
n Deadlock avoidance n Deadlock detection
© 2020 A. Haeberlen, Z. Ives, V. Liu
Deadlock avoidance
n Need to break symmetry somehow!
n When we notice that a cyclic dependency may be about to form (unsafe!),
we abort one of the involved transactions.
n Idea: Assign priorities based on timestamps
n Let’s say we have two transactions: Told and Tyoung
n Wait-die approach:
n If Told wants a lock Tyoung holds, Told waits. n If Tyoung wants a lock Told holds, Tyoung dies.
n Wound-wait approach:
n If Told wants a lock Tyoung holds, Tyoung dies.
n If Tyoung wants a lock Told holds, Tyoung waits.
n Older transactions never have to wait for younger transactions!
n If a transaction re-starts, make sure it keeps its original timestamp. Why?
Plan for today
n Transactions
n ACID properties
n Concurrency control: 2PL
n Distributed transactions: 2PC
n Consensus n Paxos
n Fault models
n Byzantine Fault Tolerance
NEXT
© 2020 A. Haeberlen, Z. Ives, V. Liu University of Pennsylvania
12
Distributed Commit
Let’s COMMIT!
What happened?
But I already aborted!
n Terminology:
n Node at which a transaction originates is the coordinator n Other nodes at which it executes are subordinates
n Subordinate can’t independently abort the transaction (e.g., because of a deadlock)
© 2020 A. Haeberlen, Z. Ives, V. Liu University of Pennsylvania
13
OK!
COMMIT
COMMIT
© 2020 A. Haeberlen, Z. Ives, V. Liu
Two-Phase Commit (2PC)
n Two rounds of communication, initiated by the coordinator:
n Phase #1: Voting
n Coordinator sends prepare messages, waits for yes or no votes
n Phase #2: Decision or termination
n Coordinator sends commit or abort messages, waits for acks
n All messages are logged
n Any site can decide to abort a transaction!
© 2020 A. Haeberlen, Z. Ives, V. Liu
Steps in 2PC
n When a transaction wants to commit:
n Coordinator sends prepare message to each subordinate
n Subordinate logs “abort” or “prepare” and then sends a no (abort) or yes (prepare) message to coordinator
n Coordinator considers votes:
n If unanimous yes votes, logs “commit” and sends commit
message to all subordinates
n Else, logs “abort”, and sends abort message
n Subordinates log abort/commit based on message they get, then send ack message to coordinator
n Coordinator writes “end” log record after getting all acks
15
Illustration of 2PC
Coordinator log begin
send “prepare”
send “yes”
log commit
send “commit”
send “ack” log end
Subordinate 1
send “prepare”
log prepare send “yes”
send “commit” log commit
send “ack”
Subordinate 2
log prepare
log commit
© 2020 A. Haeberlen, Z. Ives, V. Liu
16