Topics for the day Concurrency Control Schedules and Serializability Locking Timestamp control Distributed Databases Reliability Failure models Two phase commit protocol CS347 Lecture 15 June 4 2001 1 2 Example constraint X Y X Y Node 1 2 3 4 X X a 100 b Y Y b 100 a 1 Node 2 T1 1 Possible Schedule 2 T2 5 6 7 8 5 X X 2c d Y Y 2d c 6 node X T1 a X T1 X a 100 T2 c X T2 X 2c node Y 3 T1 4 T1 7 T2 8 T2 If X Y 0 initially X Y 200 at end 3 Y Y b 100 d Y Y 2d b Precedence intra transaction inter transaction 4 1 Example Definition of a Schedule Let T T1 T2 TN be a set of transactions A schedule S over T is a partial order with ordering relation S where 1 S Ti w1 X r2 X w2 Y w2 X r3 X w3 X w3 Y w3 Z T1 r1 X T2 T3 2 S i 3 for any two conflicting operations p q S either p S q or q S p r2 X S Note In centralized systems we assumed S was a total order and so condition 3 was unnecessary w2 Y w2 X r3 Y w3 X w3 Y w3 Z r1 X w1 X 5 Precedence Graph 6 Serializability Precedence graph P S for schedule S is a directed graph where Nodes Ti Ti occurs in S Edges Ti Tj p Ti q Tj such that p q conflict and p S q Theorem A schedule S is serializable iff P S is acyclic Enforcing Serializability Locking Timestamp control r3 X w3 X S r1 X w1 X w1 Y r2 X w2 Y P S T2 T1 T3 7 8 2 Distributed Locking Locking Rules Each lock manager maintains locks for local database elements A transaction interacts with multiple lock managers Well formed consistent transactions Legal schedulers scheduler 1 D1 locks for D1 access lock data access lock data locks for DN Two phase locking In every transaction all lock requests precede all unlock requests node N T These rules guarantee serializable schedules 9 Locking replicated elements 10 Primary Copy Locking For each element X designate specific copy Xi as primary copy Local lock Xi Global lock X Example Schedulers enforce lock semantics scheduler N DN node 1 Each transaction gets and releases locks appropriately Element X replicated as X1 and X2 on sites 1 and 2 T obtains read lock on X1 U obtains write lock on X2 Possible for X1 and X2 values to diverge Possible that schedule may be unserializable Synthesizing Global Locks Element X with n copies X1 Xn Choose s and x such that How do we get global lock on logical element X from local locks on one or more copies of X 2x n s x n Shared lock s copies Global shared lock X Exclusive lock x copies Global exclusive lock X 11 12 3 Special cases Timestamp Ordering Schedulers Read Lock One Write Locks All s 1 x n Global shared locks inexpensive Global exclusive locks very expensive Useful when most transactions are read only Basic idea Assign timestamp ts T to transaction T If ts T1 ts T2 ts Tn then scheduler produces schedule equivalent to serial schedule T1 T2 T3 Tn Majority Locking s x n 1 2 TO Rule If pi X and qj X are conflicting operations then pi X S qj X iff ts Ti ts Tj Many messages for both kinds of locks Acceptable for broadcast environments Supply proof Partial operation under disconnected network possible 13 Example Strict T O ts T1 ts T2 Node X c X Problem Transaction reads dirty data Causes cascading rollbacks Solution Enforce strict schedules in addition to T O rule Node Y Theorem If S is a schedule that satisfies TO rule P S is acyclic hence S is serializable 14 T1 a X T2 d T1 X a 100 T2 Y 2d T2 X T1 b 2c T1 Y Lock written items until it is certain that the writing transaction has committed abort T1 Y Y b 100 reject abort T1 abort T2 abort T2 Use a commit bit C X for each element X C X 1 iff last transaction that last wrote X committed If C X 0 delay reads of X until C X becomes 1 T2 15 16 4 Revisit example under strict T O Enforcing T O ts T1 ts T2 Node X c T1 a X T2 d T1 X a 100 T2 Y 2d T2 X T1 b delay abort T1 T2 c T2 X For each element X MAX R X maximum timestamp of a transaction that read X MAX W X maximum timestamp of a transaction that wrote X rL X number of transactions currently reading X 0 1 2 wL X number of transactions currently writing X 0 or 1 queue X queue of transactions waiting on X Node Y Y Y reject abort T1 X 2c 17 18 T O Scheduler T O Scheduler ri X arrives wi X arrives If ts Ti MAX W X abort Ti If ts Ti MAX R X then MAX R X ts Ti If queue X is empty and wL X 0 If ts Ti MAX W X or ts Ti MAX R X abort Ti MAX W X ts Ti If queue X is empty and wL X 0 AND rL X 0 rL X rL X 1 begin ri X Else add r Ti to queue X Note If a transaction is aborted it must be restarted with a larger timestamp Starvation is possible 19 wL X 1 begin wi X wait for Ti to complete Else add w Ti to queue Work out the steps to be executed when ri X or wi X completes 20 5 Thomas Write Rule MAX R X Optimization Update MAX R and MAX W when operation is executed not when enqueued Example MAX W X queue X ts Ti Ti wants to write X MAX W X 7 instead of 9 W ts 9 W ts 8 W ts 7 wi X arrives active write Multi version timestamps If ts Ti MAX R X abort Ti X If ts Ti MAX W X ignore this write Rest as before Value written with ts 9 Value written with ts 7 ri x ts Ti 8 21 22 2PL T O Timestamp management MAX R T O schedules Think of examples for these cases MAX W X1 X2 2PL schedules Xn T1 w1 Y T2 r2 X r2 Y w2 Z Too much space ts T1 ts T2 ts T3 Additional IOs T3 w3 X Schedule S r2 X w3 X w1 Y r2 Y w2 Z 23 24 6 Timestamp Cache Item MAX R MAX W X Y Z Distributed T O Scheduler tsMIN scheduler 1 D1 If a transaction reads or writes X make entry in cache for X add row if required D1 ts cache scheduler N DN node …