Concurrency Control

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

2 . 2 TO DAY ’ S AG E N DA Transaction Models Concurrency Control Overview Many-Core Evaluation CMU 15-721 (Spring 2016) 

3 . 3 T R A N S AC T I O N D E F I N I T I O N CMU 15-721 (Spring 2016) 

4 . 3 T R A N S AC T I O N D E F I N I T I O N A txn is a sequence of actions that are executed on a shared database to perform some higher- level function. Txns are the basic unit of change in the DBMS. No partial txns are allowed. CMU 15-721 (Spring 2016) 

5 . 4 AC T I O N C L A S S I F I C AT I O N Unprotected Actions → These lack all of the ACID properties except for consistency. Their effects cannot be depended upon. Protected Actions → These do not externalize their results before they are completely done. Fully ACID. Real Actions → These affect the physical world in a way that is hard or impossible to reverse. CMU 15-721 (Spring 2016) 

6 . 5 T R A N S AC T I O N M O D E L S Flat Txns Flat Txns + Savepoints Chained Txns Nested Txns Saga Txns Compensating Txns CMU 15-721 (Spring 2016) 

7 . 6 F L AT T R A N S AC T I O N S Standard txn model that starts with BEGIN, followed by one or more actions, and then completed with either COMMIT or ROLLBACK. Txn #1 Txn #2 BEGIN BEGIN READ(A) READ(A) WRITE(B) WRITE(B) COMMIT ROLLBACK CMU 15-721 (Spring 2016) 

8 . 7 L I M I TAT I O N S O F F L AT T R A N S AC T I O N S The application can only rollback the entire txn (i.e., no partial rollbacks). All of a txn’s work is lost is the DBMS fails before that txn finishes. Each txn takes place at a single point in time CMU 15-721 (Spring 2016) 

9 . 8 L I M I TAT I O N S O F F L AT T R A N S AC T I O N S Multi-Stage Planning → An application needs to make multiple reservations. → All the reservations need to occur or none of them. Bulk Updates → An application needs to update one billion records. → This txn could take hours to complete and therefore the DBMS is exposed to losing all of its work for any failure or conflict. CMU 15-721 (Spring 2016) 

10 . 9 T R A N S AC T I O N S AV E P O I N T S Save the current state of processing for the txn and provide a handle for the application to refer to that savepoint. The application can control the state of the txn through these checkpoints: → ROLLBACK – Revert all changes back to the state of the DB at the savepoint. → RELEASE – Destroys a savepoint previously defined in the txn. CMU 15-721 (Spring 2016) 

11 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 BEGIN WRITE(A) SAVEPOINT 1 WRITE(B) ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

12 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 BEGIN WRITE(A) SAVEPOINT 1 WRITE(B) ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

13 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) SAVEPOINT 1 WRITE(B) ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

14 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) SAVEPOINT 1 WRITE(B) ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

15 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A SAVEPOINT 1 WRITE(B) ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

16 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A SAVEPOINT 1 WRITE(B) ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

17 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A Savepoint#2 SAVEPOINT 1 WRITE(B) ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

18 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A Savepoint#2 SAVEPOINT 1 WRITE(B) ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

19 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A Savepoint#2 SAVEPOINT 1 WRITE(B) B ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

20 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A Savepoint#2 SAVEPOINT 1 WRITE(B) B ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

21 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A X Savepoint#2 SAVEPOINT 1 WRITE(B) B ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

22 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A X Savepoint#2 SAVEPOINT 1 WRITE(B) B Savepoint#3 ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

23 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A X Savepoint#2 SAVEPOINT 1 WRITE(B) B Savepoint#3 ROLLBACK TO 1 WRITE(C) COMMIT CMU 15-721 (Spring 2016) 

24 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A X Savepoint#2 SAVEPOINT 1 WRITE(B) B Savepoint#3 ROLLBACK TO 1 WRITE(C) C COMMIT CMU 15-721 (Spring 2016) 

25 . 10 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A X Savepoint#2 SAVEPOINT 1 WRITE(B) B Savepoint#3 ROLLBACK TO 1 WRITE(C) C COMMIT CMU 15-721 (Spring 2016) 

26 . 11 T R A N S AC T I O N S AV E P O I N T S Txn #1 BEGIN WRITE(A) SAVEPOINT 1 WRITE(B) SAVEPOINT 2 WRITE(C) SAVEPOINT 3 RELEASE 2 WRITE(D) ROLLBACK TO 3 CMU 15-721 (Spring 2016) 

27 . 11 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) SAVEPOINT 1 WRITE(B) SAVEPOINT 2 WRITE(C) SAVEPOINT 3 RELEASE 2 WRITE(D) ROLLBACK TO 3 CMU 15-721 (Spring 2016) 

28 . 11 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A SAVEPOINT 1 WRITE(B) SAVEPOINT 2 WRITE(C) SAVEPOINT 3 RELEASE 2 WRITE(D) ROLLBACK TO 3 CMU 15-721 (Spring 2016) 

29 . 11 T R A N S AC T I O N S AV E P O I N T S Txn #1 Savepoint#1 BEGIN WRITE(A) A Savepoint#2 SAVEPOINT 1 WRITE(B) SAVEPOINT 2 WRITE(C) SAVEPOINT 3 RELEASE 2 WRITE(D) ROLLBACK TO 3 CMU 15-721 (Spring 2016)