Concurrency Control II — Multi-versioning

1 .15-721 DATABASE SYST EM S [Source] Lecture #04 – Concurrency Control Part II Andy Pavlo // Carnegie Mellon University // Spring 2016 

2 . 2 TO DAY ’ S AG E N DA Isolation Levels Modern Multi-Version Concurrency Control CMU 15-721 (Spring 2016) 

3 . 3 O B S E R VAT I O N Serializability is useful because it allows programmers to ignore concurrency issues but enforcing it may allow too little parallelism and limit performance. We may want to use a weaker level of consistency to improve scalability. CMU 15-721 (Spring 2016) 

4 . 4 I S O L AT I O N L E V E L S Controls the extent that a txn is exposed to the actions of other concurrent txns. Provides for greater concurrency at the cost of exposing txns to uncommitted changes: → Dirty Read Anomaly → Unrepeatable Reads Anomaly → Phantom Reads Anomaly CMU 15-721 (Spring 2016) 

5 . 5 Isolation (High→Low) A N S I I S O L AT I O N L E V E L S SERIALIZABLE → No phantoms, all reads repeatable, no dirty reads. REPEATABLE READS → Phantoms may happen. READ COMMITTED → Phantoms and unrepeatable reads may happen. READ UNCOMMITTED → All of them may happen. CMU 15-721 (Spring 2016) 

6 . 6 I S O L AT I O N L E V E L H I E R A R C H Y SERIALIZABLE REPEATABLE READS READ COMMITTED READ UNCOMMITTED CMU 15-721 (Spring 2016) 

7 . 7 A N S I I S O L AT I O N L E V E L S Default Maximum Actian Ingres 10.0/10S SERIALIZABLE SERIALIZABLE Greenplum 4.1 READ COMMITTED SERIALIZABLE MySQL 5.6 REPEATABLE READS SERIALIZABLE MemSQL 1b READ COMMITTED READ COMMITTED MS SQL Server 2012 READ COMMITTED SERIALIZABLE Oracle 11g READ COMMITTED SNAPSHOT ISOLATION Postgres 9.2.2 READ COMMITTED SERIALIZABLE SAP HANA READ COMMITTED SERIALIZABLE ScaleDB 1.02 READ COMMITTED READ COMMITTED VoltDB SERIALIZABLE SERIALIZABLE Source: Peter Bailis CMU 15-721 (Spring 2016) 

8 . 7 A N S I I S O L AT I O N L E V E L S Default Maximum Actian Ingres 10.0/10S SERIALIZABLE SERIALIZABLE Greenplum 4.1 READ COMMITTED SERIALIZABLE MySQL 5.6 REPEATABLE READS SERIALIZABLE MemSQL 1b READ COMMITTED READ COMMITTED MS SQL Server 2012 READ COMMITTED SERIALIZABLE Oracle 11g READ COMMITTED SNAPSHOT ISOLATION Postgres 9.2.2 READ COMMITTED SERIALIZABLE SAP HANA READ COMMITTED SERIALIZABLE ScaleDB 1.02 READ COMMITTED READ COMMITTED VoltDB SERIALIZABLE SERIALIZABLE Source: Peter Bailis CMU 15-721 (Spring 2016) 

9 . 8 C R I T I C I S M O F I S O L AT I O N L E V E L S The isolation levels defined as part of SQL-92 standard only focused on anomalies that can occur in a 2PL-based DBMS. Two additional isolation levels: → CURSOR STABILITY → SNAPSHOT ISOLATION A CRITIQUE OF ANSI SQL ISOLATION LEVELS SIGMOD 1995 CMU 15-721 (Spring 2016) 

10 . 9 C U R S O R S TA B I L I T Y ( C S ) The DBMS’s internal cursor maintains a lock on a item in the database until it moves on to the next item. CS is a stronger isolation level in between REPEATABLE READS and READ COMMITTED that can (sometimes) prevent the Lost Update Anomaly. CMU 15-721 (Spring 2016) 

11 . 10 LO S T U P DAT E A N O M A LY Txn #1 COMMIT BEGIN • • • READ(A) WRITE(A) Txn #2 COMMIT BEGIN • • • • • • • • WRITE(A) CMU 15-721 (Spring 2016) 

12 . 10 LO S T U P DAT E A N O M A LY Txn #1 COMMIT BEGIN • • • READ(A) WRITE(A) Txn #2 COMMIT BEGIN • • • • • • • • WRITE(A) CMU 15-721 (Spring 2016) 

13 . 10 LO S T U P DAT E A N O M A LY Txn #1 COMMIT BEGIN • • • READ(A) WRITE(A) Txn #2 COMMIT BEGIN • • • • • • • • WRITE(A) CMU 15-721 (Spring 2016) 

14 . 10 LO S T U P DAT E A N O M A LY Txn #1 COMMIT BEGIN • • • READ(A) WRITE(A) Txn #2 COMMIT BEGIN • • • • • • • • WRITE(A) CMU 15-721 (Spring 2016) 

15 . 10 LO S T U P DAT E A N O M A LY Txn #1 COMMIT BEGIN • • • READ(A) WRITE(A) Txn #2 COMMIT BEGIN • • • • • • • • WRITE(A) CMU 15-721 (Spring 2016) 

16 . 10 LO S T U P DAT E A N O M A LY Txn #1 COMMIT BEGIN • • • READ(A) WRITE(A) Txn #2 COMMIT BEGIN • • • • • • • • WRITE(A) CMU 15-721 (Spring 2016) 

17 . 10 LO S T U P DAT E A N O M A LY Txn #1 Txn #2’s write to A will be lost even COMMIT BEGIN • • • though it commits READ(A) WRITE(A) after Txn #1. Txn #2 COMMIT BEGIN • • • • • • • • WRITE(A) CMU 15-721 (Spring 2016) 

18 . 10 LO S T U P DAT E A N O M A LY Txn #1 Txn #2’s write to A will be lost even COMMIT BEGIN • • • though it commits READ(A) WRITE(A) after Txn #1. Txn #2 A cursor lock on A would prevent this problem (but not COMMIT BEGIN • • • • • • • • always). WRITE(A) CMU 15-721 (Spring 2016) 

19 . 11 S N A P S H OT I S O L AT I O N ( S I ) Guarantees that all reads made in a txn see a consistent snapshot of the database that existed at the time the txn started. → A txn will commit under SI only if its writes do not conflict with any concurrent updates made since that snapshot. SI is susceptible to the Write Skew Anomaly CMU 15-721 (Spring 2016) 

20 . 12 W R I T E S K E W A N O M A LY CMU 15-721 (Spring 2016) 

21 . 12 W R I T E S K E W A N O M A LY CMU 15-721 (Spring 2016) 

22 . 12 W R I T E S K E W A N O M A LY Txn #1 Change white marbles to black. Txn #2 Change black marbles to white. CMU 15-721 (Spring 2016) 

23 . 12 W R I T E S K E W A N O M A LY Txn #1 Change white marbles to black. Txn #2 Change black marbles to white. CMU 15-721 (Spring 2016) 

24 . 12 W R I T E S K E W A N O M A LY Txn #1 Change white marbles to black. Txn #2 Change black marbles to white. CMU 15-721 (Spring 2016) 

25 . 12 W R I T E S K E W A N O M A LY Txn #1 Change white marbles to black. Txn #2 Change black marbles to white. CMU 15-721 (Spring 2016) 

26 . 12 W R I T E S K E W A N O M A LY Txn #1 Change white marbles to black. Txn #2 Change black marbles to white. CMU 15-721 (Spring 2016) 

27 . 12 W R I T E S K E W A N O M A LY CMU 15-721 (Spring 2016) 

28 . 12 W R I T E S K E W A N O M A LY Txn #1 Change white marbles to black. Txn #2 Change black marbles to white. CMU 15-721 (Spring 2016) 

29 . 13 I S O L AT I O N L E V E L H I E R A R C H Y SERIALIZABLE REPEATABLE READS SNAPSHOT ISOLATION CURSOR STABILITY READ COMMITTED READ UNCOMMITTED CMU 15-721 (Spring 2016)