1. Today’s Papers EECS 262a • Granularity of Locks and Degrees of Consistency in a Advanced Topics in Computer Systems Shared Database (2-up version) Lecture 8 J.N. Gray, R.A. Lorie, G.R. Putzolu, I.L. Traiger. Appears In IFIP Working Conference on Modeling of Data Base Management Systems. 1975 Transactions and Isolation Levels • Generalized Isolation Level Definitions, September 18th, 2018 A. Adya, B. Liskov, and P. O'Neil, 2000 John Kubiatowicz Based on slides by Ali Ghodsi and Ion Stoica • Thoughts? http://www.eecs.berkeley.edu/~kubitron/cs262 9/18/2018 cs262a-F18 Lecture-08 2 The ACID properties of Transactions Example: Transaction 101 • Atomicity: all actions in the transaction happen, or none happen BEGIN; --BEGIN TRANSACTION • Consistency: if each transaction is consistent, UPDATE accounts SET balance = balance - 100.00 WHERE name = 'Alice'; and the database starts consistent, it ends up consistent, e.g., UPDATE branches SET balance = balance - 100.00 WHERE name = (SELECT branch_name FROM accounts WHERE name = 'Alice'); – Balance cannot be negative UPDATE accounts SET balance = balance + 100.00 WHERE name = – Cannot reschedule meeting on February 30 'Bob'; • Isolation: execution of one transaction is isolated UPDATE branches SET balance = balance + 100.00 WHERE name = (SELECT branch_name FROM accounts WHERE name = 'Bob'); from others COMMIT; --COMMIT WORK • Durability: if a transaction commits, its effects persist Transfer $100 from Alice’s account to Bob’s account 9/18/2018 cs262a-F18 Lecture-08 3 9/18/2018 cs262a-F18 Lecture-08 4 

2. Why is it Hard? Concurrency • Failures: might leave state inconsistent • When operations of concurrent threads are or cause updates to be lost interleaved, the effect on shared state can –Remember last lecture? be unexpected • Concurrency: might leave state • Well known issue in operating systems, inconsistent or cause updates to be lost thread programming –This lecture and the next one! –Critical section in OSes –Java use of synchronized keyword 9/18/2018 cs262a-F18 Lecture-08 5 9/18/2018 cs262a-F18 Lecture-08 6 Transaction Scheduling Anomalies with Interleaved Execution • Why not run only one transaction at a time? • May violate transaction semantics, e.g., • Answer: low system utilization some data read by the transaction changes – Two transactions cannot run simultaneously even if before committing they access different data • Goal of transaction scheduling: – Maximize system utilization, i.e., concurrency • Inconsistent database state, e.g., some » Interleave operations from different transactions – Preserve transaction semantics updates are lost » Logically all operations in a transaction are executed atomically » Intermediate state of a transaction is not visible to other transactions • Anomalies always involves a “write”; Why? 9/18/2018 cs262a-F18 Lecture-08 7 9/18/2018 cs262a-F18 Lecture-08 8 

3. P0 – Overwriting uncommitted data P1 – Reading uncommitted data (dirty read) • Write-write conflict • Write-read conflict (reading uncommitted data – T2 writes value modified by T1 before T1 commits, or dirty read) e.g, T2 overwrites W(A) before T1 commits –T2 reads value modified by T1 before T1 commits, T1:W(A), W(B) e.g., T2 reads A before T1 modifies it T2: W(A),W(B) T1:R(A),W(A), • Violates transaction serializability T2: R(A), … • If transactions were serial, you’d get either: – T1’s updates of A and B – T2’s updates of A and B 9/18/2018 cs262a-F18 Lecture-08 9 9/18/2018 cs262a-F18 Lecture-08 10 P3 – Non-repeatable reads Goals of Transaction Scheduling • Read-Write conflict • Maximize system utilization, i.e., concurrency – T2 reads value, after which T1 modifies it, e.g., T2 – Interleave operations from different transactions reads A, after which T1 modifies it T1: T2:R(A), R(A),W(A) R(A),W(A) • Preserve transaction semantics – Semantically equivalent to a serial schedule, i.e., one • Example: Mary and John want to buy a TV set transaction runs at a time on Amazon but there is only one left in stock T1: R, W, R, W T2: R, W, R, R, W – (T1) John logs first, but waits… – (T2) Mary logs second and buys the TV set right away Serial schedule (T1, then T2): Serial schedule (T2, then T1): – (T1) John decides to buy, but it is too late… R, W, R, W, R, W, R, R, W R, W, R, R, W, R, W, R, W 9/18/2018 cs262a-F18 Lecture-08 11 9/18/2018 cs262a-F18 Lecture-08 12 

4. Two Key Questions Transaction Scheduling • Serial schedule: 1) Is a given schedule equivalent to a serial – A schedule that does not interleave the operations of different transactions execution of transactions? – Transactions run serially (one at a time) Schedule: R, R, W, W, R, R, R, W, W • Equivalent schedules: ? ? – For any storage/database state, the effect (on storage/database) Serial schedule (T1, then T2): Serial schedule (T2, then T1): and output of executing the first schedule is identical to the effect R, W, R, W, R, W, R, R, W R, W, R, R, W, R, W, R, W of executing the second schedule : • Serializable schedule: 2) How do you come up with a schedule equivalent – A schedule that is equivalent to some serial execution of the to a serial schedule? transactions – Intuitively: with a serializable schedule you only see things that could happen in situations where you were running transactions one-at-a-time 9/18/2018 cs262a-F18 Lecture-08 13 9/18/2018 cs262a-F18 Lecture-08 14 Conflict Serializable Schedules Conflict Equivalence – Intuition • Two operations conflict if they • If you can transform an interleaved schedule by swapping consecutive non-conflicting operations – Belong to different transactions of different transactions into a serial schedule, – Are on the same data then the original schedule is conflict – At least one of them is a write serializable, e.g., • Two schedules are conflict equivalent iff: T1:R(A),W(A), R(B),W(B) – Involve same operations of same transactions T2: R(A),W(A), R(B),W(B) – Every pair of conflicting operations is ordered the T1:R(A),W(A), R(B), W(B) same way T2: R(A), W(A), R(B),W(B) • Schedule S is conflict serializable if S is conflict equivalent to some serial schedule T1:R(A),W(A),R(B), W(B) T2: R(A),W(A), R(B),W(B) 9/18/2018 cs262a-F18 Lecture-08 15 9/18/2018 cs262a-F18 Lecture-08 16 

5. Conflict Equivalence – Intuition Conflict Equivalence – Intuition • If you can transform an interleaved schedule by • If you can transform an interleaved schedule by swapping consecutive non-conflicting operations swapping consecutive non-conflicting operations of of different transactions into a serial schedule, then the original schedule is conflict different transactions into a serial schedule, then serializable, e.g., the original schedule is conflict serializable, e.g., T1:R(A), W(A) T1:R(A),W(A),R(B), W(B) T2: R(A),W(A), T2: R(A),W(A), R(B),W(B) T1:R(A),W(A),R(B), W(B) • Is this schedule serializable? T2: R(A), W(A),R(B),W(B) T1:R(A),W(A),R(B),W(B) T2: R(A), W(A),R(B),W(B) 9/18/2018 cs262a-F18 Lecture-08 17 9/18/2018 cs262a-F18 Lecture-08 18 Dependency Graph Example • Dependency graph: • Conflict serializable schedule: T1:R(A),W(A), R(B),W(B) – Transactions represented as nodes T2: R(A),W(A), R(B),W(B) – Edge from Ti to Tj: » an operation of Ti conflicts with an operation of Tj A B » Ti appears earlier than Tj in the schedule T1 T2 Dependency graph • Theorem: Schedule is conflict serializable if and only if its dependency graph is acyclic • No cycle! 9/18/2018 cs262a-F18 Lecture-08 19 9/18/2018 cs262a-F18 Lecture-08 20 

6. Example Notes on Conflict Serializability • Conflict that is not serializable: • Conflict Serializability doesn’t allow all schedules T1:R(A),W(A), R(B),W(B) that you would consider correct T2: R(A),W(A),R(B),W(B) – This is because it is strictly syntactic - it doesn’t consider the meanings of the operations or the data A • Many times, Conflict Serializability is what gets used, because it can be done efficiently T1 T2 Dependency graph B – See isolation degrees/levels next • Cycle: The output of T1 depends on T2, and vice-versa • Two-phase locking (2PL) is how we implement it 9/18/2018 cs262a-F18 Lecture-08 21 9/18/2018 cs262a-F18 Lecture-08 22 Serializability ≠ Conflict Serializability Locks • Following schedule is not conflict serializable • “Locks” to control access to data Dependency graph A T1:R(A), W(A), T1 A T2 • Two types of locks: T2: W(A), A A – shared (S) lock: multiple concurrent transactions allowed T3: WA T3 to operate on data – exclusive (X) lock: only one transaction can operate on • However, the schedule is serializable since its output is data at a time equivalent with the following serial schedule T1:R(A),W(A), Held\Request S X Lock T2: W(A), S Yes Block Compatibility X Block Block T3: WA Matrix • Note: deciding whether a schedule is serializable (not conflict-serializable) is NP-complete 9/18/2018 cs262a-F18 Lecture-08 23 9/18/2018 cs262a-F18 Lecture-08 24 

7. Two-Phase Locking (2PL) Two-Phase Locking (2PL) • Each transaction must obtain: • 2PL guarantees conflict serializability – S (shared) or X (exclusive) lock on data – Doesn’t allow dependency cycles. Why? before reading • Answer: a dependency cycle leads to deadlock – X (exclusive) lock on data before writing – Assume there is a cycle between Ti and Tj • A transaction can not request additional locks – Edge from Ti to Tj: Ti acquires lock first and Tj needs to wait once it releases any locks – Edge from Tj to Ti: Tj acquires lock first and Ti needs to wait – Thus, each transaction has a “growing phase” followed by a “shrinking phase” – Thus, both Ti and Tj wait for each other Lock Point! – Since with 2PL neither Ti nor Tj release locks before 4 acquiring all locks they need  deadlock Growing Shrinking # Locks Held 3 • Schedule of conflicting transactions is conflict equivalent 2 1 Phase Phase to a serial schedule ordered by “lock point” 0 1 3 5 7 9 11 13 15 17 19 Time 9/18/2018 cs262a-F18 Lecture-08 25 9/18/2018 cs262a-F18 Lecture-08 26 Example Is this a 2PL Schedule? • T1 transfers $50 from account A to account B 1 2 Lock_X(A) <granted> Read(A) Lock_S(A) 3 A: = A-50 T1:Read(A),A:=A-50,Write(A),Read(B),B:=B+50,Write(B) 4 Write(A) 5 Unlock(A) <granted> 6 Read(A) • T2 outputs the total of accounts A and B 7 8 Unlock(A) Lock_S(B) <granted> 9 Lock_X(B) T2:Read(A),Read(B),PRINT(A+B) 10 Read(B) 11 <granted> Unlock(B) 12 PRINT(A+B) • Initially, A = $1000 and B = $2000 13 14 Read(B) B := B +50 15 Write(B) 16 Unlock(B) • What are the possible output values? No, and it is not serializable 9/18/2018 cs262a-F18 Lecture-08 27 9/18/2018 cs262a-F18 Lecture-08 28 

8. Is this a 2PL Schedule? Strict 2PL (cont’d) 1 Lock_X(A) <granted> 2 3 Read(A) A: = A-50 Lock_S(A) • All locks held by a transaction are released only 4 Write(A) when the transaction completes 5 Lock_X(B) <granted> 6 Unlock(A) <granted> – In effect, “shrinking phase” is delayed until: 7 Read(A) a) Transaction has committed (commit log record on disk), 8 Lock_S(B) 9 Read(B) or 10 B := B +50 b) Decision has been made to abort the transaction (then 11 Write(B) 12 Unlock(B) <granted> locks can be released after rollback). 13 Unlock(A) 14 Read(B) 15 Unlock(B) 16 PRINT(A+B) Yes, it is serializable 9/18/2018 cs262a-F18 Lecture-08 29 9/18/2018 cs262a-F18 Lecture-08 30 Is this a Strict 2PL schedule? Granularity 1 Lock_X(A) <granted> 2 Read(A) Lock_S(A) • What is a data item (on which a lock is obtained)? 3 A: = A-50 4 Write(A) – In most modern systems: item is one tuple in a table 5 6 Lock_X(B) <granted> Unlock(A) <granted> – Sometimes (especially in early 1970s): item is a page (with 7 Read(A) several tuples) 8 Lock_S(B) 9 Read(B) – Sometimes: item is a whole table 10 B := B +50 11 Write(B) 12 Unlock(B) <granted> 13 Unlock(A) 14 Read(B) 15 Unlock(B) 16 PRINT(A+B) No: Cascading Abort Possible 9/18/2018 cs262a-F18 Lecture-08 31 9/18/2018 cs262a-F18 Lecture-08 32 

9. Granularity trade-offs Multigranular locking • Larger granularity: fewer locks held, so less overhead; • Care needed to manage conflicts properly but less concurrency possible among items of varying granularity – “false conflicts” when txns deal with different parts of the same item – Note: conflicts only detectable among locks on a given item name • Smaller “fine” granularity: more locks held, so more overhead; but more concurrency is possible • System gets “intention” mode locks on • System usually gets fine grain locks until there are too larger granules before getting actual S/X many of them; then it replaces them with larger locks on smaller granules granularity locks – Conflict rules arranged so that activities that do not commute must get conflicting locks on some item 9/18/2018 cs262a-F18 Lecture-08 33 9/18/2018 cs262a-F18 Lecture-08 34 Lock Mode Conflicts Lock manager internals • Hash table, keyed by hash of item name – Each item has a mode and holder (set) Held\Request IS IX S SIX X – Wait queue of requests IS Yes Yes Yes Yes Block – All requests and locks in linked list from IX Yes Yes Block Block Block transaction information S Yes Block Yes Block Block SIX Yes Block Block Block Block – Transaction table X Block Block Block Block Block » To allow thread rescheduling when blocking is finished – Deadlock detection » Either cycle in waits-for graph, or just timeouts 9/18/2018 cs262a-F18 Lecture-08 35 9/18/2018 cs262a-F18 Lecture-08 36 

10. Problems with serializability Explicit isolation levels • The performance reduction from isolation is high • A transaction can be declared to have isolation properties that are less stringent than serializability – Transactions are often blocked because they want to read data that another transactions has changed – However SQL standard says that default should be serializable (Gray’75 called this “level 3 isolation”) • For many applications, the accuracy of the data they – In practice, most systems have weaker default level, read is not crucial and most transactions run at weaker levels! – e.g. overbooking a plane is ok in practice – e.g. your banking decisions would not be very different if • Isolation levels are defined with respect to data you saw yesterday’s balance instead of the most up-to- access conflicts (phenomena) they preclude date 9/18/2018 cs262a-F18 Lecture-08 37 9/18/2018 cs262a-F18 Lecture-08 38 Phenomena Phantom • P0: T2 writes value modified by T1 before T1 commits 1. A transaction T1 reads a set of rows – Transactions cannot be serialized by their writes that satisfy some condition • P1: Dirty Read: T2 reads value modified by T1 before T1 commits – If T1 aborts it will be as if transaction T2 read values that 2. Another transaction T2 executes a have never existed statement that causes new rows to be • P2: Non-Repeatable Read: T2 reads value, then T1 added or removed from the search modifies it – If T2 attempts to re-read value it can read another value condition • P3: Phantom: (see next) 3. If T1 repeats the read it will obtain a different set of rows. 9/18/2018 cs262a-F18 Lecture-08 39 9/18/2018 cs262a-F18 Lecture-08 40 

11. Phantom Example Isolation Levels T1 Isolation levels Degree Proscribed Read locks on Write locks on data Select count(*) T2 Phenomena data items and items and where dept = “Acct” phantoms (same phantoms (always // find and S-lock (“Sue”, “Acct”, unless noted) the same) 3500) and (“Tim”, “Acct, 2400) 0 none none Short write locks Insert (“Joe”,”Acct”, 2000) READ 1 P0 none Long write locks // X-lock the new record UNCOMMITTED Commit READ 2 P0, P1 Short read locks Long write locks Select sum(salary) // release locks COMITTED where dept = “Acct” REAPEATABLE P0, P1, P2 Long data-item Long write locks // find and S-lock (“Sue”, “Acct”, 3500) and (“Tim”, “Acct, 2400) READ read locks, short and (“Joe”, “Acct”, 2000) phantom locks SERIALIZABLE 3 P0, P1, P2, P3 Long read locks Long write locks ANSI Gray’s isolation degrees 9/18/2018 cs262a-F18 Lecture-08 41 9/18/2018 cs262a-F18 Lecture-08 42 Direct Serialization Graph (DSG) Conflict Name Description DSG T1 writes value, then T2 ww Directly write-depends T1 T2 overwrites it Directly read-depends T1 writes value, then T2 reads it T1 wr T2 rw Directly anti-depends T1 reads value, then T2 writes it T1 T2 Generalized Isolation Levels Example: T1:W(A), W(B), W(C) T2: R(B), W(C) T3: W(B) R(C), W(B) wr rw wr T1 T2 T3 ww ww 9/18/2018 cs262a-F18 Lecture-08 43 9/18/2018 cs262a-F18 Lecture-08 44 

12. Disallowing P0 G0 • Writes by T1 are not overwritten by T2 while T1 is • G0: DSG contains a directed cycle consisting uncommitted entirely of write-dependency edges – Simplifies recovery from aborts, e.g., – Just ensure serialization on writes alone » T1 updates x, T2 overwrites x , and then T1 aborts » The system must not restore x to T1’s pre-state – More permissive than Degree 1 as allows concurrent transactions to modify same object » However, if T2 aborts later, x must be restored to T1’s pre- state! • Example: – Serializes transactions based on their writes alone T1:W(A) W(B), … » all writes of T2 must be ordered before or after all writes of T1 T2: W(A), W(B), … G0 only addresses this one ww T1 T2 ww 9/18/2018 cs262a-F18 Lecture-08 45 9/18/2018 cs262a-F18 Lecture-08 46 Disallowing P1 G1 • Writes of T1 could not be read by T2 while T1 is • G1a – Aborted reads: T2 has read a value written by an still uncommitted aborted transaction T1 – It prevents a transaction T2 from committing if T2 has read the updates of a transaction that might later abort • G1b – Intermediate Reads: Committed transaction T2 has – It prevents transactions from reading intermediate read an intermediate value written by transaction T1 modifications of other transactions – It serializes committed transactions based on their • G1c – Circular Information Flow: DSG contains a directed read/write-dependencies (but not their • cycle consisting entirely of dependency edges antidependencies), i.e., – Disallowing G1c ensures that if transaction T2 is affected by » If transaction T2 depends on T1, T1 cannot depend on T2 transaction T1, T2 does not affect T1 9/18/2018 cs262a-F18 Lecture-08 47 9/18/2018 cs262a-F18 Lecture-08 48 

13. Disallowing P2 G2 • T1 cannot modify value read by T2 • Just prevent transactions that perform inconsistent reads or writes from committing –Precludes a transaction reading inconsistent data and making inconsistent • G2 – Anti-dependency Cycles: DSG contains a directed updates cycle with one or more anti-dependency edges • G2-item – Item Anti-dependency Cycles: DSG contains a directed cycle having one or more item-antidependency edges 9/18/2018 cs262a-F18 Lecture-08 49 9/18/2018 cs262a-F18 Lecture-08 50 Generalized Isolation Levels Summary • Transactions, key abstractions on databases – Application defined sequence of operations on one or Isolation levels G0 G1 G2-Item G2 more databases that is atomic READ NA NA NA NA • Key challenge: trade performance to correctness UNCOMMITTED – On one hand we want to interleave transactions to READ COMITTED Not possible Possible Possible Possible increase throughput REAPEATABLE Not possible Not possible Not possible Possible READ – On the other hand we want to isolate transactions from SERIALIZABLE Not possible Not possible Not possible Not possible each other • Solution: increase interleaving by providing – Multi-granularity locks – Relax the isolation semantics 9/18/2018 cs262a-F18 Lecture-08 51 9/18/2018 cs262a-F18 Lecture-08 52 

14. Were these good papers? Extra slides… • What were the authors’ goals? • What about the evaluation / metrics? • Did they convince you that this was a good system /approach? • Were there any red-flags? • What mistakes did they make? • Does the system/approach meet the “Test of Time” challenge? • How would you review this paper today? 9/18/2018 cs262a-F18 Lecture-08 53 9/18/2018 cs262a-F18 Lecture-08 54 Snapshot Isolation (SI) Snapshot Isolation (SI) • A multiversion concurrency control • Read of an item may not give current value mechanism was described in SIGMOD ’95 by H. Berenson, P. Bernstein, J. Gray, J. • Instead, use old versions (kept with Melton, E. O’Neil, P. O’Neil timestamps) to find value that had been most recently committed at the time the txn started –Does not guarantee serializable execution! – Exception: if the txn has modified the item, use the • Supplied by Oracle DB for “Isolation Level value it wrote itself Serializable” (also in PostgreSQL before rel 9.1) • The transaction sees a “snapshot” of the • Available in Microsoft SQL Server 2005 as database, at an earlier time “Isolation Level Snapshot”, and in – Intuition: this should be consistent, if the database was consistent before PostgreSQL (since rel 9.1) as “Isolation Level Repeatable Read” 9/18/2018 cs262a-F18 Lecture-08 55 9/18/2018 cs262a-F18 Lecture-08 56 

15. First committer wins (FCW) Benefits of SI • T will not be allowed to commit a • Reading is never blocked, and reads don’t modification to an item if any other block writes transaction has committed a changed value • Avoids common anomalies for that item since T’s start (snapshot) –No dirty read • T must hold write locks on modified items at –No lost update time of commit, to install them. –No inconsistent read –In practice, commit-duration write locks may be –Set-based selects are repeatable (no set when writes execute. phantoms) –These simplify detection of conflicting • Matches common understanding of modifications when T tries to write the item, isolation: concurrent transactions are not instead of waiting till T tries to commit. aware of one another’s changes 9/18/2018 cs262a-F18 Lecture-08 57 9/18/2018 cs262a-F18 Lecture-08 58 Is every execution serializable? • For any set of txns, if they all run with Two Phase Locking, then every interleaved execution is serializable • For some sets of txns, if they all run with SI, then every execution is serializable – Eg the txns making up TPC-C • For some sets of txns, if they all run with SI, there can be non-serializable executions – Undeclared integrity constraints can be violated 9/18/2018 cs262a-F18 Lecture-08 59