Distributed Databases CS347 Lecture 15 June 4 2001 1 Topics for the day Concurrency Control Schedules and Serializability Locking Timestamp control Reliability Failure models Two phase commit protocol 2 Example constraint X Y X Y Node 1 Node 2 T1 1 2 3 4 X X a 100 b Y Y b 100 a T2 5 6 7 8 X X 2c d Y Y 2d c 3 Possible Schedule 1 2 5 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 Y Y b 100 d Y Y 2d b Precedence intra transaction inter transaction 4 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 2 S i 3 for any two conflicting operations p q S either p S q or q S p Note In centralized systems we assumed S was a total order and so condition 3 was unnecessary 5 Example w1 X r2 X w2 Y w2 X r3 X w3 X w3 Y w3 Z T1 r1 X T2 T3 r2 X S w2 Y w2 X r3 Y w3 X w3 Y w3 Z r1 X w1 X 6 Precedence Graph 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 r3 X w3 X S r1 X w1 X w1 Y r2 X w2 Y P S T2 T1 T3 7 Serializability Theorem A schedule S is serializable iff P S is acyclic Enforcing Serializability Locking Timestamp control 8 Distributed Locking Each lock manager maintains locks for local database elements A transaction interacts with multiple lock managers scheduler 1 D1 locks for D1 DN node 1 access lock data scheduler N access lock data T locks for DN node N 9 Locking Rules Well formed consistent transactions Legal schedulers Each transaction gets and releases locks appropriately Schedulers enforce lock semantics Two phase locking In every transaction all lock requests precede all unlock requests These rules guarantee serializable schedules 10 Locking replicated elements Example 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 How do we get global lock on logical element X from local locks on one or more copies of X 11 Primary Copy Locking For each element X designate specific copy Xi as primary copy Local lock Xi Global lock X Synthesizing Global Locks Element X with n copies X1 Xn Choose s and x such that 2x n s x n Shared lock s copies Global shared lock X Exclusive lock x copies Global exclusive lock X 12 Special cases 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 Majority Locking s x n 1 2 Many messages for both kinds of locks Acceptable for broadcast environments Partial operation under disconnected network possible 13 Timestamp Ordering Schedulers 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 TO Rule If pi X and qj X are conflicting operations then pi X S qj X iff ts Ti ts Tj Supply proof Theorem If S is a schedule that satisfies TO rule P S is acyclic hence S is serializable 14 Example ts T1 ts T2 Node X X T1 X a 100 T2 c X T2 X 2c abort T1 T1 a abort T2 Node Y Y Y 2d b Y Y b 100 reject abort T1 T2 d T2 T1 T1 abort T2 15 Strict T O Problem Transaction reads dirty data Causes cascading rollbacks Solution Enforce strict schedules in addition to T O rule Lock written items until it is certain that the writing transaction has committed 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 16 Revisit example under strict T O ts T1 ts T2 Node X X c Node Y Y b T1 a X T2 d Y T1 a 100 T2 2d X T1 T2 abort T1 X T2 c X T2 2c delay Y reject abort T1 17 Enforcing T O 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 18 T O Scheduler ri 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 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 T O Scheduler wi X arrives 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 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 Thomas Write Rule MAX R X MAX W X ts Ti Ti wants to write X wi X arrives If ts Ti MAX R X abort Ti If ts Ti MAX W X ignore this write Rest as before 21 Optimization Update MAX R and MAX W when operation is executed not when enqueued Example queue X W ts 9 W ts 8 W ts 7 MAX W X 7 instead of 9 active write Multi version timestamps X Value written with ts 9 Value written with ts 7 ri x ts Ti 8 22 2PL T O T O schedules Think of examples for these cases 2PL schedules T1 w1 Y T2 r2 X r2 Y w2 Z ts T1 ts T2 ts T3 T3 w3 X Schedule S r2 X w3 X w1 Y r2 Y w2 Z 23 Timestamp management MAX R MAX W X1 X2 Xn Too much space Additional IOs 24 Timestamp Cache Item MAX R MAX W X Y Z tsMIN If a transaction reads or writes X make entry in cache for X add row if required Choose tsMIN current time d Periodically purge all items X with MAX R X tsMIN MAX W X tsMIN and …