Notes: https://pdos.csail.mit.edu/6.824/notes/l-2pc.txt
Video: https://youtu.be/B6btpukqHpM
Prep:
Topics
2 Phase Locking 2pl
2 Phase Commit 2pc
Problem to tackle → cross machine atomic ops
goals → atomicity wrt failures & concurrency
Transactions
2 txns
begin txn
add(x, -1)
add(y, +1)
commit/abort
begin txn
v1 ← get(x)
v2 ← get(y)
print v1 v2
commit/abort
(all or nothing)
ACID
- Atomic
- Consistent
- Isolation
- Durable
Isolation
serializability ⇒ if t1 t2 happens concurrently either t1 should be executed before or t2 i.e., there should be serial order, same outcome as result of complete operation of t1, t2
serializability is weaker than linearizability
Concurrency Control
- Pessimistic (locks)
- ask for permission
- Optimistic (no locks) (just abort if not serializable)
- ask for forgiveness, not permission
Two Phase Locking
2 phases
- growing (acquires locks)
- once grown, reaches locking point
- shrinking (releases locks)
lock per record
txn acquires lock before using and holds until committed
any other txn have to wait for lock
Deadlock
different records getting locked by diff txn and records are part of txns
then abort a txn, once other one is done, do txn
deadlock detected using wait-for graph, when there’s cycle between 2 nodes, there’s a deadlock
Two Phase Commit
logs are written to stable storage which help to recover state if crashed
using raft like algo for replication, coordinator (to be FT)
apart from parallels drawn b/w raft and 2pc
conceptual diff is, in raft, all servers do same things but in 2pc, servers operate on different data
raft → HA, 2pc → atomic transactions