Page 1 1 CSE 444: Database Internals Lectures 15 Transactions: Optimistic Concurrency Control 1 Magda Balazinska - CSE 444, Spring 2012 Motivation •? Locking ensures serializability –? BUT adds overhead and slows-down transactions •? Observations: –? Many transactions are read-only –? Many transactions touch unrelated parts of database •? Can we: –? Assume no unserializable behavior will occur –? Abort transactions in case of violations •? Yes: this is optimistic concurrency control Magda Balazinska - CSE 444, Spring 2012 2 Locking vs Optimistic •? Locking prevents unserializable behavior from occurring: it causes transactions to wait for locks •? Optimistic methods assume no unserializable behavior will occur: they abort transactions if it does •? Locking typically better in case of high levels of contention; optimistic better otherwise Magda Balazinska - CSE 444, Spring 2012 3 Outline •? Concurrency control by timestamps (18.8) •? Concurrency control by validation (18.9) Magda Balazinska - CSE 444, Spring 2012 4 Timestamps •? Each transaction receives unique timestamp TS(T) Could be: •? The system’s clock •? A unique counter, incremented by the scheduler Magda Balazinska - CSE 444, Spring 2012 5 Timestamps The timestamp order defines the serialization order of the transaction Main invariant: Magda Balazinska - CSE 444, Spring 2012 6 Page 2 1 CSE 444: Database Internals Lectures 15 Transactions: Optimistic Concurrency Control 1 Magda Balazinska - CSE 444, Spring 2012 Motivation •? Locking ensures serializability –? BUT adds overhead and slows-down transactions •? Observations: –? Many transactions are read-only –? Many transactions touch unrelated parts of database •? Can we: –? Assume no unserializable behavior will occur –? Abort transactions in case of violations •? Yes: this is optimistic concurrency control Magda Balazinska - CSE 444, Spring 2012 2 Locking vs Optimistic •? Locking prevents unserializable behavior from occurring: it causes transactions to wait for locks •? Optimistic methods assume no unserializable behavior will occur: they abort transactions if it does •? Locking typically better in case of high levels of contention; optimistic better otherwise Magda Balazinska - CSE 444, Spring 2012 3 Outline •? Concurrency control by timestamps (18.8) •? Concurrency control by validation (18.9) Magda Balazinska - CSE 444, Spring 2012 4 Timestamps •? Each transaction receives unique timestamp TS(T) Could be: •? The system’s clock •? A unique counter, incremented by the scheduler Magda Balazinska - CSE 444, Spring 2012 5 Timestamps The timestamp order defines the serialization order of the transaction Main invariant: Magda Balazinska - CSE 444, Spring 2012 6 2 Main Idea •? For any two conflicting actions, ensure that their order is the serialized order: In each of these cases •? w U (X) . . . r T (X) •? r U (X) . . . w T (X) •? w U (X) . . . w T (X) Answer: Check that TS(U) < TS(T) When T wants to read X, r T (X), how do we know U, and TS(U) ? Read too late ? Write too late ? 7 Magda Balazinska - CSE 444, Spring 2012 Timestamps With each element X, associate •? RT(X) = the highest timestamp of any transaction that read X •? WT(X) = the highest timestamp of any transaction that wrote X •? C(X) = the commit bit: true when transaction with highest timestamp that wrote X committed If 1 element = 1 page, these are associated with each page X in the buffer pool Magda Balazinska - CSE 444, Spring 2012 8 Magda Balazinska - CSE 444, Spring 2012 9 Time-based Scheduling •? Note: simple version that ignores the commit bit •? Transaction wants to read element X –? If TS(T) < WT(X) abort –? Else read and update RT(X) to larger of TS(T) or RT(X) •? Transaction wants to write element X –? If TS(T) < RT(X) abort –? Else if TS(T) < WT(X) ignore write & continue (Thomas Write Rule) –? Otherwise, write X and update WT(X) to TS(T) Details Read too late: •? T wants to read X, and TS(T) < WT(X) START(T) … START(U) … w U (X) . . . r T (X) Need to rollback T ! Magda Balazinska - CSE 444, Spring 2012 10 Details Write too late: •? T wants to write X, and TS(T) < RT(X) START(T) … START(U) … r U (X) . . . w T (X) Need to rollback T ! Magda Balazinska - CSE 444, Spring 2012 11 Details Write too late, but we can still handle it: •? T wants to write X, and TS(T) >= RT(X) but WT(X) > TS(T) START(T) … START(V) … w V (X) . . . w T (X) Don’t write X at all ! (but see later…) Magda Balazinska - CSE 444, Spring 2012 12 Page 3 1 CSE 444: Database Internals Lectures 15 Transactions: Optimistic Concurrency Control 1 Magda Balazinska - CSE 444, Spring 2012 Motivation •? Locking ensures serializability –? BUT adds overhead and slows-down transactions •? Observations: –? Many transactions are read-only –? Many transactions touch unrelated parts of database •? Can we: –? Assume no unserializable behavior will occur –? Abort transactions in case of violations •? Yes: this is optimistic concurrency control Magda Balazinska - CSE 444, Spring 2012 2 Locking vs Optimistic •? Locking prevents unserializable behavior from occurring: it causes transactions to wait for locks •? Optimistic methods assume no unserializable behavior will occur: they abort transactions if it does •? Locking typically better in case of high levels of contention; optimistic better otherwise Magda Balazinska - CSE 444, Spring 2012 3 Outline •? Concurrency control by timestamps (18.8) •? Concurrency control by validation (18.9) Magda Balazinska - CSE 444, Spring 2012 4 Timestamps •? Each transaction receives unique timestamp TS(T) Could be: •? The system’s clock •? A unique counter, incremented by the scheduler Magda Balazinska - CSE 444, Spring 2012 5 Timestamps The timestamp order defines the serialization order of the transaction Main invariant: Magda Balazinska - CSE 444, Spring 2012 6 2 Main Idea •? For any two conflicting actions, ensure that their order is the serialized order: In each of these cases •? w U (X) . . . r T (X) •? r U (X) . . . w T (X) •? w U (X) . . . w T (X) Answer: Check that TS(U) < TS(T) When T wants to read X, r T (X), how do we know U, and TS(U) ? Read too late ? Write too late ? 7 Magda Balazinska - CSE 444, Spring 2012 Timestamps With each element X, associate •? RT(X) = the highest timestamp of any transaction that read X •? WT(X) = the highest timestamp of any transaction that wrote X •? C(X) = the commit bit: true when transaction with highest timestamp that wrote X committed If 1 element = 1 page, these are associated with each page X in the buffer pool Magda Balazinska - CSE 444, Spring 2012 8 Magda Balazinska - CSE 444, Spring 2012 9 Time-based Scheduling •? Note: simple version that ignores the commit bit •? Transaction wants to read element X –? If TS(T) < WT(X) abort –? Else read and update RT(X) to larger of TS(T) or RT(X) •? Transaction wants to write element X –? If TS(T) < RT(X) abort –? Else if TS(T) < WT(X) ignore write & continue (Thomas Write Rule) –? Otherwise, write X and update WT(X) to TS(T) Details Read too late: •? T wants to read X, and TS(T) < WT(X) START(T) … START(U) … w U (X) . . . r T (X) Need to rollback T ! Magda Balazinska - CSE 444, Spring 2012 10 Details Write too late: •? T wants to write X, and TS(T) < RT(X) START(T) … START(U) … r U (X) . . . w T (X) Need to rollback T ! Magda Balazinska - CSE 444, Spring 2012 11 Details Write too late, but we can still handle it: •? T wants to write X, and TS(T) >= RT(X) but WT(X) > TS(T) START(T) … START(V) … w V (X) . . . w T (X) Don’t write X at all ! (but see later…) Magda Balazinska - CSE 444, Spring 2012 12 3 More Problems Read dirty data: •? T wants to read X, and WT(X) < TS(T) •? Seems OK, but… START(U) … START(T) … w U (X). . . r T (X)… ABORT(U) If C(X)=false, T needs to wait for it to become true Magda Balazinska - CSE 444, Spring 2012 13 More Problems Write dirty data: •? T wants to write X, and WT(X) > TS(T) •? Seems OK not to write at all, but … START(T) … START(U)… w U (X). . . w T (X)… ABORT(U) If C(X)=false, T needs to wait for it to become true Magda Balazinska - CSE 444, Spring 2012 14 Timestamp-based Scheduling •? When a transaction T requests r(X) or w(X), the scheduler examines RT(X), WT(X), C(X), and decides one of: •? To grant the request, or •? To rollback T (and restart with later timestamp) •? To delay T until C(X) = true Magda Balazinska - CSE 444, Spring 2012 15 Timestamp-based Scheduling RULES including commit bit •? There are 4 long rules in Sec. 18.8.4 •? You should be able to derive them yourself, based on the previous slides •? Make sure you understand them ! READING ASSIGNMENT: 18.8.4 Magda Balazinska - CSE 444, Spring 2012 16 Multiversion Timestamp •? When transaction T requests r(X) but WT(X) > TS(T), then T must rollback •? Idea: keep multiple versions of X: X t , X t-1 , X t-2 , . . . •? Let T read an older version, with appropriate timestamp TS(X t ) > TS(X t-1 ) > TS(X t-2 ) > . . . Magda Balazinska - CSE 444, Spring 2012 17 Details •? When w T (X) occurs, create a new version, denoted X t where t = TS(T) •? When r T (X) occurs, find most recent version X t such that t < TS(T) Notes: –? WT(X t ) = t and it never changes –? RT(X t ) must still be maintained to check legality of writes •? Can delete X t if we have a later version X t1 and all active transactions T have TS(T) > t1 Magda Balazinska - CSE 444, Spring 2012 18 Page 4 1 CSE 444: Database Internals Lectures 15 Transactions: Optimistic Concurrency Control 1 Magda Balazinska - CSE 444, Spring 2012 Motivation •? Locking ensures serializability –? BUT adds overhead and slows-down transactions •? Observations: –? Many transactions are read-only –? Many transactions touch unrelated parts of database •? Can we: –? Assume no unserializable behavior will occur –? Abort transactions in case of violations •? Yes: this is optimistic concurrency control Magda Balazinska - CSE 444, Spring 2012 2 Locking vs Optimistic •? Locking prevents unserializable behavior from occurring: it causes transactions to wait for locks •? Optimistic methods assume no unserializable behavior will occur: they abort transactions if it does •? Locking typically better in case of high levels of contention; optimistic better otherwise Magda Balazinska - CSE 444, Spring 2012 3 Outline •? Concurrency control by timestamps (18.8) •? Concurrency control by validation (18.9) Magda Balazinska - CSE 444, Spring 2012 4 Timestamps •? Each transaction receives unique timestamp TS(T) Could be: •? The system’s clock •? A unique counter, incremented by the scheduler Magda Balazinska - CSE 444, Spring 2012 5 Timestamps The timestamp order defines the serialization order of the transaction Main invariant: Magda Balazinska - CSE 444, Spring 2012 6 2 Main Idea •? For any two conflicting actions, ensure that their order is the serialized order: In each of these cases •? w U (X) . . . r T (X) •? r U (X) . . . w T (X) •? w U (X) . . . w T (X) Answer: Check that TS(U) < TS(T) When T wants to read X, r T (X), how do we know U, and TS(U) ? Read too late ? Write too late ? 7 Magda Balazinska - CSE 444, Spring 2012 Timestamps With each element X, associate •? RT(X) = the highest timestamp of any transaction that read X •? WT(X) = the highest timestamp of any transaction that wrote X •? C(X) = the commit bit: true when transaction with highest timestamp that wrote X committed If 1 element = 1 page, these are associated with each page X in the buffer pool Magda Balazinska - CSE 444, Spring 2012 8 Magda Balazinska - CSE 444, Spring 2012 9 Time-based Scheduling •? Note: simple version that ignores the commit bit •? Transaction wants to read element X –? If TS(T) < WT(X) abort –? Else read and update RT(X) to larger of TS(T) or RT(X) •? Transaction wants to write element X –? If TS(T) < RT(X) abort –? Else if TS(T) < WT(X) ignore write & continue (Thomas Write Rule) –? Otherwise, write X and update WT(X) to TS(T) Details Read too late: •? T wants to read X, and TS(T) < WT(X) START(T) … START(U) … w U (X) . . . r T (X) Need to rollback T ! Magda Balazinska - CSE 444, Spring 2012 10 Details Write too late: •? T wants to write X, and TS(T) < RT(X) START(T) … START(U) … r U (X) . . . w T (X) Need to rollback T ! Magda Balazinska - CSE 444, Spring 2012 11 Details Write too late, but we can still handle it: •? T wants to write X, and TS(T) >= RT(X) but WT(X) > TS(T) START(T) … START(V) … w V (X) . . . w T (X) Don’t write X at all ! (but see later…) Magda Balazinska - CSE 444, Spring 2012 12 3 More Problems Read dirty data: •? T wants to read X, and WT(X) < TS(T) •? Seems OK, but… START(U) … START(T) … w U (X). . . r T (X)… ABORT(U) If C(X)=false, T needs to wait for it to become true Magda Balazinska - CSE 444, Spring 2012 13 More Problems Write dirty data: •? T wants to write X, and WT(X) > TS(T) •? Seems OK not to write at all, but … START(T) … START(U)… w U (X). . . w T (X)… ABORT(U) If C(X)=false, T needs to wait for it to become true Magda Balazinska - CSE 444, Spring 2012 14 Timestamp-based Scheduling •? When a transaction T requests r(X) or w(X), the scheduler examines RT(X), WT(X), C(X), and decides one of: •? To grant the request, or •? To rollback T (and restart with later timestamp) •? To delay T until C(X) = true Magda Balazinska - CSE 444, Spring 2012 15 Timestamp-based Scheduling RULES including commit bit •? There are 4 long rules in Sec. 18.8.4 •? You should be able to derive them yourself, based on the previous slides •? Make sure you understand them ! READING ASSIGNMENT: 18.8.4 Magda Balazinska - CSE 444, Spring 2012 16 Multiversion Timestamp •? When transaction T requests r(X) but WT(X) > TS(T), then T must rollback •? Idea: keep multiple versions of X: X t , X t-1 , X t-2 , . . . •? Let T read an older version, with appropriate timestamp TS(X t ) > TS(X t-1 ) > TS(X t-2 ) > . . . Magda Balazinska - CSE 444, Spring 2012 17 Details •? When w T (X) occurs, create a new version, denoted X t where t = TS(T) •? When r T (X) occurs, find most recent version X t such that t < TS(T) Notes: –? WT(X t ) = t and it never changes –? RT(X t ) must still be maintained to check legality of writes •? Can delete X t if we have a later version X t1 and all active transactions T have TS(T) > t1 Magda Balazinska - CSE 444, Spring 2012 18 4 Example using Basic Timestamps T 1 150 R 1 (A) W 1 (A) Magda Balazinska - CSE 444, Spring 2012 19 T 2 200 R 2 (A) W 2 (A) T 3 175 R 3 (A) Abort A RT=0 WT=0 RT=150 WT=150 RT=200 WT=200 RT=225 T 4 225 R 4 (A) Example using Multiversion T 1 150 R 1 (A) W 1 (A) Magda Balazinska - CSE 444, Spring 2012 20 T 2 200 R 2 (A) W 2 (A) T 3 175 R 3 (A) A 0 Read T 4 225 R 4 (A) A 150 Create Read Read A 200 Create Read Tradeoffs •? Locks: –? Great when there are many conflicts –? Poor when there are few conflicts •? Timestamps –? Poor when there are many conflicts (rollbacks) –? Great when there are few conflicts •? Compromise –? READ ONLY transactions ? timestamps –? READ/WRITE transactions ? locks Magda Balazinska - CSE 444, Spring 2012 21 Outline •? Concurrency control by timestamps (18.8) •? Concurrency control by validation (18.9) Magda Balazinska - CSE 444, Spring 2012 22 Concurrency Control by Validation •? Each transaction T defines a read set RS(T) and a write set WS(T) •? Each transaction proceeds in three phases: –? Read all elements in RS(T). Time = START(T) –? Validate (may need to rollback). Time = VAL(T) –? Write all elements in WS(T). Time = FIN(T) Main invariant: the serialization order is VAL(T) Magda Balazinska - CSE 444, Spring 2012 23 Avoid r T (X) - w U (X) Conflicts U: Read phase Validate Write phase START(U) VAL(U) FIN(U) T: Read phase Validate ? START(T) IF RS(T) n WS(U) and FIN(U) > START(T) (U has validated and U has not finished before T begun) Then ROLLBACK(T) conflicts Magda Balazinska - CSE 444, Spring 2012 24 Page 5 1 CSE 444: Database Internals Lectures 15 Transactions: Optimistic Concurrency Control 1 Magda Balazinska - CSE 444, Spring 2012 Motivation •? Locking ensures serializability –? BUT adds overhead and slows-down transactions •? Observations: –? Many transactions are read-only –? Many transactions touch unrelated parts of database •? Can we: –? Assume no unserializable behavior will occur –? Abort transactions in case of violations •? Yes: this is optimistic concurrency control Magda Balazinska - CSE 444, Spring 2012 2 Locking vs Optimistic •? Locking prevents unserializable behavior from occurring: it causes transactions to wait for locks •? Optimistic methods assume no unserializable behavior will occur: they abort transactions if it does •? Locking typically better in case of high levels of contention; optimistic better otherwise Magda Balazinska - CSE 444, Spring 2012 3 Outline •? Concurrency control by timestamps (18.8) •? Concurrency control by validation (18.9) Magda Balazinska - CSE 444, Spring 2012 4 Timestamps •? Each transaction receives unique timestamp TS(T) Could be: •? The system’s clock •? A unique counter, incremented by the scheduler Magda Balazinska - CSE 444, Spring 2012 5 Timestamps The timestamp order defines the serialization order of the transaction Main invariant: Magda Balazinska - CSE 444, Spring 2012 6 2 Main Idea •? For any two conflicting actions, ensure that their order is the serialized order: In each of these cases •? w U (X) . . . r T (X) •? r U (X) . . . w T (X) •? w U (X) . . . w T (X) Answer: Check that TS(U) < TS(T) When T wants to read X, r T (X), how do we know U, and TS(U) ? Read too late ? Write too late ? 7 Magda Balazinska - CSE 444, Spring 2012 Timestamps With each element X, associate •? RT(X) = the highest timestamp of any transaction that read X •? WT(X) = the highest timestamp of any transaction that wrote X •? C(X) = the commit bit: true when transaction with highest timestamp that wrote X committed If 1 element = 1 page, these are associated with each page X in the buffer pool Magda Balazinska - CSE 444, Spring 2012 8 Magda Balazinska - CSE 444, Spring 2012 9 Time-based Scheduling •? Note: simple version that ignores the commit bit •? Transaction wants to read element X –? If TS(T) < WT(X) abort –? Else read and update RT(X) to larger of TS(T) or RT(X) •? Transaction wants to write element X –? If TS(T) < RT(X) abort –? Else if TS(T) < WT(X) ignore write & continue (Thomas Write Rule) –? Otherwise, write X and update WT(X) to TS(T) Details Read too late: •? T wants to read X, and TS(T) < WT(X) START(T) … START(U) … w U (X) . . . r T (X) Need to rollback T ! Magda Balazinska - CSE 444, Spring 2012 10 Details Write too late: •? T wants to write X, and TS(T) < RT(X) START(T) … START(U) … r U (X) . . . w T (X) Need to rollback T ! Magda Balazinska - CSE 444, Spring 2012 11 Details Write too late, but we can still handle it: •? T wants to write X, and TS(T) >= RT(X) but WT(X) > TS(T) START(T) … START(V) … w V (X) . . . w T (X) Don’t write X at all ! (but see later…) Magda Balazinska - CSE 444, Spring 2012 12 3 More Problems Read dirty data: •? T wants to read X, and WT(X) < TS(T) •? Seems OK, but… START(U) … START(T) … w U (X). . . r T (X)… ABORT(U) If C(X)=false, T needs to wait for it to become true Magda Balazinska - CSE 444, Spring 2012 13 More Problems Write dirty data: •? T wants to write X, and WT(X) > TS(T) •? Seems OK not to write at all, but … START(T) … START(U)… w U (X). . . w T (X)… ABORT(U) If C(X)=false, T needs to wait for it to become true Magda Balazinska - CSE 444, Spring 2012 14 Timestamp-based Scheduling •? When a transaction T requests r(X) or w(X), the scheduler examines RT(X), WT(X), C(X), and decides one of: •? To grant the request, or •? To rollback T (and restart with later timestamp) •? To delay T until C(X) = true Magda Balazinska - CSE 444, Spring 2012 15 Timestamp-based Scheduling RULES including commit bit •? There are 4 long rules in Sec. 18.8.4 •? You should be able to derive them yourself, based on the previous slides •? Make sure you understand them ! READING ASSIGNMENT: 18.8.4 Magda Balazinska - CSE 444, Spring 2012 16 Multiversion Timestamp •? When transaction T requests r(X) but WT(X) > TS(T), then T must rollback •? Idea: keep multiple versions of X: X t , X t-1 , X t-2 , . . . •? Let T read an older version, with appropriate timestamp TS(X t ) > TS(X t-1 ) > TS(X t-2 ) > . . . Magda Balazinska - CSE 444, Spring 2012 17 Details •? When w T (X) occurs, create a new version, denoted X t where t = TS(T) •? When r T (X) occurs, find most recent version X t such that t < TS(T) Notes: –? WT(X t ) = t and it never changes –? RT(X t ) must still be maintained to check legality of writes •? Can delete X t if we have a later version X t1 and all active transactions T have TS(T) > t1 Magda Balazinska - CSE 444, Spring 2012 18 4 Example using Basic Timestamps T 1 150 R 1 (A) W 1 (A) Magda Balazinska - CSE 444, Spring 2012 19 T 2 200 R 2 (A) W 2 (A) T 3 175 R 3 (A) Abort A RT=0 WT=0 RT=150 WT=150 RT=200 WT=200 RT=225 T 4 225 R 4 (A) Example using Multiversion T 1 150 R 1 (A) W 1 (A) Magda Balazinska - CSE 444, Spring 2012 20 T 2 200 R 2 (A) W 2 (A) T 3 175 R 3 (A) A 0 Read T 4 225 R 4 (A) A 150 Create Read Read A 200 Create Read Tradeoffs •? Locks: –? Great when there are many conflicts –? Poor when there are few conflicts •? Timestamps –? Poor when there are many conflicts (rollbacks) –? Great when there are few conflicts •? Compromise –? READ ONLY transactions ? timestamps –? READ/WRITE transactions ? locks Magda Balazinska - CSE 444, Spring 2012 21 Outline •? Concurrency control by timestamps (18.8) •? Concurrency control by validation (18.9) Magda Balazinska - CSE 444, Spring 2012 22 Concurrency Control by Validation •? Each transaction T defines a read set RS(T) and a write set WS(T) •? Each transaction proceeds in three phases: –? Read all elements in RS(T). Time = START(T) –? Validate (may need to rollback). Time = VAL(T) –? Write all elements in WS(T). Time = FIN(T) Main invariant: the serialization order is VAL(T) Magda Balazinska - CSE 444, Spring 2012 23 Avoid r T (X) - w U (X) Conflicts U: Read phase Validate Write phase START(U) VAL(U) FIN(U) T: Read phase Validate ? START(T) IF RS(T) n WS(U) and FIN(U) > START(T) (U has validated and U has not finished before T begun) Then ROLLBACK(T) conflicts Magda Balazinska - CSE 444, Spring 2012 24 5 Avoid w T (X) - w U (X) Conflicts U: Read phase Validate Write phase START(U) VAL(U) FIN(U) T: Read phase Validate Write phase ? START(T) VAL(T) IF WS(T) n WS(U) and FIN(U) > VAL(T) (U has validated and U has not finished before T validates) Then ROLLBACK(T) conflicts 25 Magda Balazinska - CSE 444, Spring 2012 Validation Rules Summary •? Check that RS(T) n WS(U) is empty for any previously validated U that did not finish before T started (i.e., FIN(U) > START(T)) •? Check that WS(T) n WS(U) is empty for any previously validated U that did not finish before T validated (i.e, FIN(U) > VAL(T)) Magda Balazinska - CSE 444, Spring 2012 26Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!