Introduction to Database Systems CSE 444 Lecture 13 Transactions: Concurrency Control (part 1)Outline 2 Serial'and'Serializable'Schedules'(18.1)' Conflict'Serializability'(18.2)' Locks'(18.3)'The Problem 3 Mul?ple'transac?ons'are'running'concurrently'T1,'T2,'…' They'read/write'some'common'elements'A1,'A2,'…' How'can'we'prevent'unwanted'interference'?' The'SCHEDULER'is'responsible'for'that'Some Famous Anomalies 4 What'could'go'wrong'if'we'didn’t'have'concurrency'control:' Dirty'reads'(including'inconsistent'reads)' Unrepeatable'reads' Lost'updates'Many'other'things'can'go'wrong'too'Dirty Reads 5 T1:''WRITE(A)''T1:''ABORT'T2:''READ(A)'WriteWRead'Conflict'Inconsistent Read 6 T1:''A':='20;''B':='20;'T1:''WRITE(A)''T1:''WRITE(B)''T2:''READ(A);'T2:''READ(B);''WriteWRead'Conflict'Unrepeatable Read 7 T1:''WRITE(A)'T2:''READ(A);'T2:''READ(A);''ReadWWrite'Conflict'Lost Update 8 T1:'READ(A)''T1:'A':='A+5'T1:'WRITE(A)''T2:'READ(A);'T2:'A':='A*1.3'T2:'WRITE(A);'WriteWWrite'Conflict'Schedules 9 Given'mul?ple'transac?ons' A'schedule'is'a'sequence'of'interleaved'ac?ons'from'all'transac?o ns'Example 10 T1' T2'READ(A ,'t)' READ(A ,s)'t':='t+100' s':='s*2'WRITE(A,'t)' WRITE(A,s)'READ(B,'t)' READ(B,s)'t':='t+100' s':='s*2'WRITE(B,t)' WRITE(B,s)'A Serial Schedule 11 T1' T2'READ(A ,'t)'t':='t+100'WRITE(A,'t)'READ(B,'t)'t':='t+100'WRITE(B,t)'READ(A ,s)'s':='s*2'WRITE(A,s)'READ(B,s)'s':='s*2'WRITE(B,s)'A' B'25' 25'125'125'250'250'Serial'schedule:'(T1,T2)'A Serial Schedule (version 2) 12 T1' T2'READ(A ,s)'s':='s*2'WRITE(A,s)'READ(B,s)'s':='s*2'WRITE(B,s)'READ(A ,'t)'t':='t+100'WRITE(A,'t)'READ(B,'t)'t':='t+100'WRITE(B,t)'A' B'25' 25'50'50'150'150'Serial'schedule:'(T2,T1)'Serializable Schedule 13 A'schedule'is'serializable'if'it'is'equival ent'to'a'serial'schedule'A'schedule'S' i s'serializable,'if'there'is'a'serial'schedule'S’,'such'that'for'every'ini?al'database'state,'the'effects'of'S'and'S’'are'the'same'A Serializable Schedule 14 No?ce:''This'is'NOT'a'serial'schedule'T1' T2'READ(A ,'t)'t':='t+100'WRITE(A,'t)'READ(A ,s)'s':='s*2'WRITE(A,s)'READ(B,'t)'t':='t+100'WRITE(B,t)'READ(B,s)'s':='s*2'WRITE(B,s)'A' B'25' 25'125'250'125'250'A Non-Serializable Schedule 15 T1' T2'READ(A ,'t)'t':='t+100'WRITE(A,'t)'READ(A ,s)'s':='s*2'WRITE(A,s)'READ(B,s)'s':='s*2'WRITE(B,s)'READ(B,'t)'t':='t+100'WRITE(B,t)'A' B'25' 25'125'250'50'150'Transaction Semantics 16 T1' T2'READ(A ,'t)'t':='t+100'WRITE(A,'t)'READ(A ,s)'s':='s+200'WRITE(A,s)'READ(B,s)'s':='s+200'WRITE(B,s)'READ(B,'t)'t':='t+100'WRITE(B,t)'A' B'25' 25'125'325'225'325'Is'this'serializable?'Ignoring Details 17 Serializability'is'undecidable!' Scheduler'should'not'look'at'transac?on'details' Assume'worst'case'updates' Only'care'about'reads'r(A)'and'writes'w(A)' Not'the'actual'values'involved'Notation 18 T1: r1(A); w1(A); r1(B); w1(B) T2: r2(A); w2(A); r2(B); w2(B) ac?ons'transac?on'r1(A); w1(A); r2(A); w2(A); r1(B); w1(B); r2(B); w2(B) schedule'Conflict Serializability 19 Conflicts:'ri(X);'wi(Y)'Two'ac?ons'by'same'transac?on'Ti:'wi(X);'wj(X)'Two'writes'by'Ti,'Tj'to'same'element:'wi(X);'rj(X)'Read/write'by'Ti,'Tj'to'same'element:'ri(X);'wj(X)'Conflict Serializability 20 A'schedule'is'conflict'serializable'if'i t'can'be'transformed'into'a'serial'schedule'by'a'series'of'swappings'of'adjacent'nonWconflic?ng'ac?ons'r1(A);'w1(A);'r1(B);'w1(B);'r2(A);'w2(A);'r2(B);'w2(B)'r1(A);'w1(A);'r2(A);'w2(A);'r1(B);'w1(B);'r2(B);'w2(B)'r1(A);'w1(A);'r2(A);'r1(B);'w2(A);'w1(B);'r2(B);'w2(B)'r1(A);'w1(A);'r1(B);'r2(A);'w2(A);'w1(B);'r2(B);'w2(B)'r1(A);'w1(A);'r1(B);'r2(A);'w1(B);'w2(A);'r2(B);'w2(B)'The Precedence Graph Test 21 Is'a'schedule'conflictWserializable'?'Simple'test:' Build'a'graph'of'all'transac?ons'Ti' Edge'from'Ti'to'Tj'if'Ti'makes'an'ac?on'th at'conflicts'with'one'of'Tj'and'comes'first' The'test:'if'the'graph'has'no'cycles,'then'it'is'conflict'serializable'!'Example 1 22 r2(A);'r1(B);'w2(A);'r3(A);'w1(B);'w3(A);'r2(B);'w2(B)'1' 2' 3'This'schedule'is'conflictWserializable'A'B'Example 2 23 r2(A);'r1(B);'w2(A);'r2(B);'r3(A);'w1(B);'w3(A);'w2(B)'1' 2' 3'This'schedule'is'NOT'conflictWserializable'A'B'B'Conflict Serializability 24 A'serializable'schedule'need'not'be'conflict'serializable,'even'under'the'“worst'case'update”'assump?on'w1(Y);'w1(X);'w2(Y);'w2(X);'w3(X);'w1(Y);'w2(Y);'w2(X);'w1(X);'w3(X);'Equivalent,''but'can’t'swap'Lost'write'Scheduler 25 The'scheduler'is'the'module'that'schedules'the'transac?o n’s'ac?ons,'ensuring'serializability' How?''We'discuss'three'techniques'in'class:' Locks' Time'stamps'(next'lecture)' Valida?on'(next'lecture)'Locking Scheduler 26 Simple'idea:' Each'element'has'a'unique'lock' Each'transac?on'must'first'acquire'the'lock'before'reading/wri?ng'that'element' If'the'lock'is'taken'by'another'transac?on,'then'wait' The'tran sac?on'mu st'release'the'lock(s)'Notation 27 li(A)'='transac?on'Ti'acquires'lock'for'element'A'ui(A)'='transac?on'Ti'releases'lock'for'element'A'Example 28 T1' T2'L1(A);'READ(A,'t)'t':='t+100'WRITE(A,'t);'U1(A);'L1(B)'L2(A);'READ(A,s)'s':='s*2'WRITE(A,s);'U2(A);''L2(B);'DENIED…'READ(B,'t)'t':='t+100'WRITE(B,t);'U1(B);''…GRANTED;+READ(B,s)'s':='s*2'WRITE(B,s);'U2(B);''Scheduler has ensured a conflict-serializable scheduleExample 29 T1' T2'L1(A);'READ(A,'t)'t':='t+100'WRITE(A,'t);'U1(A)'L2(A);'READ(A,s)'s':='s*2'WRITE(A,s);'U2(A);''L2(B);'READ(B,s)'s':='s*2'WRITE(B,s);'U2(B);''L1(B);'READ(B,'t)'t':='t+100'WRITE(B,t);'U1(B);''Locks did not enforce conflict serializability!!Two Phase Locking (2PL) 30 The'2PL'rule:' In'every'transac?on,'all'lock'requests'must'precede'all'unlock'requests' This'ensures'conflict'serializability!''(why?)'Example: 2PL transactions 31 T1' T2'L1(A);'L1(B);'READ(A,'t)'t':='t+100'WRITE(A,'t);'U1(A)'L2(A);'READ(A,s)'s':='s*2'WRITE(A,s);''L2(B);'DENIED…'READ(B,'t)'t':='t+100'WRITE(B,t);'U1(B);''…GRANTED;+READ(B,s)'s':='s*2'WRITE(B,s);'U2(A);'U2(B);''Now it is conflict-serializableWhat about Aborts? 32 2PL'enforces'conflictWserializable'schedules' But'what'if'a'transac?on'releases'its'locks'and'then'aborts?' Serializable'schedule'defini?on'only'considers'transac?o ns'th at'commit' Relies'on'assump?ons'that'aborted'transac?o ns'can'be'undone'completely'Example with Abort 33 T1'
View Full Document
Unlocking...