Lecture 9 Granularity of Locks Degrees of Consistency Sept 26 2007 ChengXiang Zhai Most slides are adapted from Kevin Chang s lecture slides CS511 Advanced Database Management Systems 1 Transactions Transactions each as a program of atomic database operations atomic units of database transformation recovery Consistency guaranteed if each transaction is well behaved start end with consistent DB each transaction runs in serial no interleaving to mess up CS511 Advanced Database Management Systems 2 ACID Properties of Transactions Atomicity all or nothing at all Consistency from one consistent state to another Isolation as if executed alone Durability results permanent after commit CS511 Advanced Database Management Systems 3 Transaction Concurrency Concurrency control ensures that transactions are interleaved correctly Xact T1 read A A A 1 write A read B B B 1 write B Xact T2 read A A A 2 write A read B B B 2 write B CS511 Advanced Database Management Systems 4 Transaction Interleaving Before A 0 B 0 then Correct schedule Wrong schedule Why Xact T1 read A A A 1 write A read B B B 1 write B Xact T2 read A A A 2 write A read B B B 2 write B Xact T1 read A A A 1 write A read B B B 1 write B schedule 1 CS511 Advanced Database Management Systems Xact T2 read A A A 2 write A read B B B 2 write B schedule 2 Xact T1 read A A A 1 write A read B B B 1 write B Xact T2 read A A A 2 write A read B B B 2 write B schedule 3 5 Transaction Interleaving Schedule 1 interleaved more concurrent Schedule 3 serial Consistency and isolation transform DB in serial A 0 B 0 T1 A 1 B 1 T2 A 2 B 2 Xact T1 read A A A 1 write A read B B B 1 write B Xact T2 read A A A 2 write A read B B B 2 write B schedule 1 CS511 Advanced Database Management Systems Xact T1 read A A A 1 write A read B B B 1 write B Xact T2 read A A A 2 write A read B B B 2 write B schedule 3 6 Dependency of Transactions Dependencies defining ordering of transactions rw wr ww Serialization graph Ti Tj for a dependency from Ti to Tj Serializable if called conflict serializable Xact T1 read A A A 1 write A read B B B 1 write B Xact T2 T1 read A A A 2 write A read B B B 2 write B schedule 1 CS511 Advanced Database Management Systems T2 Xact T1 read A A A 1 write A read B B B 1 write B Xact T2 T1 read A A A 2 write A read B B B 2 write B schedule 2 T2 7 Atomic Actions Why only reads and writes How does CC know what actions are Will knowing more action semantics help CS511 Advanced Database Management Systems 8 More Semantics of Atomic Actions Atomic action inc x i read x x x i write x Any dependencies between T1 and T2 Xact T1 inc A 1 inc B 1 CS511 Advanced Database Management Systems Xact T2 inc A 2 inc B 2 9 Locking Protocol Locking a protocol for accessing data well formed xacts lock unlock access units before after using them lock manager grants manages locks Goals of locking protocol ensure serializability preserve high concurrency Parameters of a locking protocol CS511 Advanced Database Management Systems 10 Locking Protocol Parameters What modes of locks to provide Compatibility e g S for shared X for exclusive What units to lock database table tuple what else How to well behave to obtain and hold locks in what sequence how long to hold CS511 Advanced Database Management Systems 11 Motivation A Simple Protocol Lock modes S for shared and X for exclusive access compatibility S S T otherwise F Unit a relation Behavior lock the maximal mode before access unlock immediately after CS511 Advanced Database Management Systems 12 Simple Protocol What s Wrong Xact T1 Xact T2 X lock A s relation read A A A 1 write A X unlock A s relation X lock A s relation read A A A 2 write A X unlock A s relation X lock B s relation read B B B 1 write B X unlock B s relation X lock B s relation read B B B 2 write B X unlock B s relation CS511 Advanced Database Management Systems 13 Simple Protocol Serializability Serializability fail to interleave dependencies in same order Solution 2PL protocol for well formed xacts legal scheduler 2PL serializable Xact T1 X lock A X unlock A Xact T2 X lock A X unlock A X lock B X lock B X unlock B X unlock B CS511 Advanced Database Management Systems Xact T1 X lock A X lock B X unlock A X unlock B Xact T2 X lock A X lock B X unlock A X unlock B 14 Simple Protocol Granularity Unit of locking How to increase concurrency coarse units fine units Granularity concurrence vs overhead hierarchical lockable units DB areas files pages tuples attributes Correctness problem T1 S locks a tuple T2 X locks the file solution CS511 Advanced Database Management Systems 15 Granularity Locking Database as hierarchy of lockable units Locking to lock a unit first lock all containing units with intension why intension locks IS IX SIX intension to upgrade why not just I Unlocking release all relevant locks at once or leaf to root CS511 Advanced Database Management Systems 16 Granularity Locking DAG Generalization DAG of units S locks at least one path to the node X locks all paths to the node Q Why implicit S if one parent is X or S SIX CS511 Advanced Database Management Systems 17 Lock Compatibilty Table X SIX S IX IS NL privilege ordering CS511 Advanced Database Management Systems 18 Compatibility Examples SIX SIX SIX Relation Enrollment X Tuple DB Relation Student X Grant S IS IX Tuple Tuple Tuple Questions why SIX is useful SIX S No SIX IS Yes SIX IX No CS511 Advanced Database Management Systems 19 Consistency Dirty Data Based T does not overwrite dirty data of other xacts 0 T does not commit any writes until EOT 1 T does not read dirty data from other xacts 2 other xacts do not dirty any data read by T before T completes 3 How to lock for each degree CS511 Advanced Database Management Systems 20 Consistency Locking Based Corresponding to each condition T does not overwrite dirty data of other xacts set write locks on dirty data well formed on w T does not commit any writes until EOT set long write locks 2P EOT on w T does not read dirty data from other xacts set read locks well formed on r other xacts do not dirty any data read by T before T completes set long read locks 2P EOT on r CS511 Advanced Database Management Systems 21 How long to hold a lock …