Transcription
15-721DATABASESYST EM S[Source]Lecture #04 – Concurrency ControlPart IIAndy Pavlo // Carnegie Mellon University // Spring 2016
2TO DAY ’ S AG E N DAIsolation LevelsModern Multi-Version Concurrency ControlCMU 15-721 (Spring 2016)
3O B S E R VAT I O NSerializability is useful because it allowsprogrammers to ignore concurrency issues butenforcing it may allow too little parallelismand limit performance.We may want to use a weaker level ofconsistency to improve scalability.CMU 15-721 (Spring 2016)
4I S O L AT I O N L E V E L SControls the extent that a txn is exposed to theactions of other concurrent txns.Provides for greater concurrency at the cost ofexposing txns to uncommitted changes: Dirty Read Anomaly Unrepeatable Reads Anomaly Phantom Reads AnomalyCMU 15-721 (Spring 2016)
5Isolation (High Low)A N S I I S O L AT I O N L E V E L SSERIALIZABLE 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)
6I S O L AT I O N L E V E L H I E R A R C H YSERIALIZABLEREPEATABLE READSREAD COMMITTEDREAD UNCOMMITTEDCMU 15-721 (Spring 2016)
7A N S I I S O L AT I O N L E V E L SDefaultMaximumSERIALIZABLESERIALIZABLEREAD COMMITTEDSERIALIZABLEMySQL 5.6REPEATABLE READSSERIALIZABLEMemSQL 1bREAD COMMITTEDREAD COMMITTEDMS SQL Server 2012READ COMMITTEDSERIALIZABLEOracle 11gREAD COMMITTEDSNAPSHOT ISOLATIONPostgres 9.2.2READ COMMITTEDSERIALIZABLESAP HANAREAD COMMITTEDSERIALIZABLEScaleDB 1.02READ COMMITTEDREAD COMMITTEDSERIALIZABLESERIALIZABLEActian Ingres 10.0/10SGreenplum 4.1VoltDBSource: Peter BailisCMU 15-721 (Spring 2016)
7A N S I I S O L AT I O N L E V E L SDefaultMaximumSERIALIZABLESERIALIZABLEREAD COMMITTEDSERIALIZABLEMySQL 5.6REPEATABLE READSSERIALIZABLEMemSQL 1bREAD COMMITTEDREAD COMMITTEDMS SQL Server 2012READ COMMITTEDSERIALIZABLEOracle 11gREAD COMMITTEDSNAPSHOT ISOLATIONPostgres 9.2.2READ COMMITTEDSERIALIZABLESAP HANAREAD COMMITTEDSERIALIZABLEScaleDB 1.02READ COMMITTEDREAD COMMITTEDSERIALIZABLESERIALIZABLEActian Ingres 10.0/10SGreenplum 4.1VoltDBSource: Peter BailisCMU 15-721 (Spring 2016)
8C R I T I C I S M O F I S O L AT I O N L E V E L SThe isolation levels defined as part of SQL-92standard only focused on anomalies that canoccur in a 2PL-based DBMS.Two additional isolation levels: CURSOR STABILITY SNAPSHOT ISOLATIONA CRITIQUE OF ANSI SQL ISOLATION LEVELSSIGMOD 1995CMU 15-721 (Spring 2016)
9C U R S O R S TA B I L I T Y ( C S )The DBMS’s internal cursor maintains a lockon a item in the database until it moves on tothe next item.CS is a stronger isolation level in betweenREPEATABLE READS and READ COMMITTEDthat can (sometimes) prevent the Lost UpdateAnomaly.CMU 15-721 (Spring 2016)
10LO S T U P DAT E A N O M A LY READ(A)WRITE(A)COMMITBEGINTxn #1 WRITE(A)COMMITBEGINTxn #2CMU 15-721 (Spring 2016)
10LO S T U P DAT E A N O M A LY READ(A)WRITE(A)COMMITBEGINTxn #1 WRITE(A)COMMITBEGINTxn #2CMU 15-721 (Spring 2016)
10LO S T U P DAT E A N O M A LY READ(A)WRITE(A)COMMITBEGINTxn #1 WRITE(A)COMMITBEGINTxn #2CMU 15-721 (Spring 2016)
10LO S T U P DAT E A N O M A LY READ(A)WRITE(A)COMMITBEGINTxn #1 WRITE(A)COMMITBEGINTxn #2CMU 15-721 (Spring 2016)
10LO S T U P DAT E A N O M A LY READ(A)WRITE(A)COMMITBEGINTxn #1 WRITE(A)COMMITBEGINTxn #2CMU 15-721 (Spring 2016)
10LO S T U P DAT E A N O M A LY READ(A)WRITE(A)COMMITBEGINTxn #1 WRITE(A)COMMITBEGINTxn #2CMU 15-721 (Spring 2016)
10LO S T U P DAT E A N O M A LY READ(A)WRITE(A)Txn #2’s write to Awill be lost eventhough it commitsafter Txn #1.COMMITBEGINTxn #1 WRITE(A)COMMITBEGINTxn #2CMU 15-721 (Spring 2016)
10LO S T U P DAT E A N O M A LY READ(A)WRITE(A)Txn #2’s write to Awill be lost eventhough it commitsafter Txn #1.COMMITBEGINTxn #1 WRITE(A)COMMITBEGINTxn #2A cursor lock on Awould prevent thisproblem (but notalways).CMU 15-721 (Spring 2016)
11S 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 aconsistent snapshot of the database thatexisted at the time the txn started. A txn will commit under SI only if its writes do notconflict with any concurrent updates made since thatsnapshot.SI is susceptible to the Write Skew AnomalyCMU 15-721 (Spring 2016)
12W R I T E S K E W A N O M A LYCMU 15-721 (Spring 2016)
12W R I T E S K E W A N O M A LYCMU 15-721 (Spring 2016)
12W R I T E S K E W A N O M A LYTxn #1Change whitemarbles to black.Txn #2Change blackmarbles to white.CMU 15-721 (Spring 2016)
12W R I T E S K E W A N O M A LYTxn #1Change whitemarbles to black.Txn #2Change blackmarbles to white.CMU 15-721 (Spring 2016)
12W R I T E S K E W A N O M A LYTxn #1Change whitemarbles to black.Txn #2Change blackmarbles to white.CMU 15-721 (Spring 2016)
12W R I T E S K E W A N O M A LYTxn #1Change whitemarbles to black.Txn #2Change blackmarbles to white.CMU 15-721 (Spring 2016)
12W R I T E S K E W A N O M A LYTxn #1Change whitemarbles to black.Txn #2Change blackmarbles to white.CMU 15-721 (Spring 2016)
12W R I T E S K E W A N O M A LYCMU 15-721 (Spring 2016)
12W R I T E S K E W A N O M A LYTxn #1Change whitemarbles to black.Txn #2Change blackmarbles to white.CMU 15-721 (Spring 2016)
13I S O L AT I O N L E V E L H I E R A R C H YSERIALIZABLEREPEATABLE READSSNAPSHOT ISOLATIONCURSOR STABILITYREAD COMMITTEDREAD UNCOMMITTEDCMU 15-721 (Spring 2016)
14M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O LTimestamp-ordering scheme that maintainsmultiple versions of database objects: When a txn writes to an object, the DBMS creates anew version of that object. When a txn reads an object, it reads the newestversion that existed when the txn started.First proposed in 1978 MIT PhD dissertation.CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) WRITE(A)COMMITBEGINTxn #1CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) GINTxn #1CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) GINTxn #110001CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) GINTxn #110001CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) GINTxn #110001CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) OMMITBEGINTxn #110001CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) OMMITBEGINTxn #110001CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) OMMITBEGINTxn #110001CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) 210003COMMITBEGINTxn #110001CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) 210003COMMITBEGINTxn #110001CMU 15-721 (Spring 2016)
15M U LT I - V E R S I O N CO N C U R R E N C Y CO N T R O L READ(A)WRITE(B) 210003COMMITBEGINTxn #110001CMU 15-721 (Spring 2016)
16M O D E R N M V CCMicrosoft Hekaton (SQL Server)TUM HyPerHPI HYRISESAP HANACMU 15-721 (Spring 2016)
17M I C R O S O F T H E K ATO NIncubator project started in 2008 to create newOLTP engine for MSFT SQL Server (MSSQL). Led by DB ballers Paul Larson and Mike ZwillingHad to integrate with MSSQL ecosystem.Had to support all possible OLTP workloadswith predictable performance. Single-threaded partitioning (e.g., H-Store) workswell for some applications but terrible for others.CMU 15-721 (Spring 2016)
18H E K ATO N M V CCEvery txn is assigned a timestamp (TS) whenthey begin and when they commit.DBMS maintains “chain” of versions per tuple: BEGIN: The BeginTS of the active txn or the EndTS ofthe committed txn that created it. END: The BeginTS of the active txn that created thenext version or infinity or the EndTS of thecommitted txn that created it. POINTER: Location of the next version in the chain.HIGH-PERFORMANCE CONCURRENCYCONTROL MECHANISMS FOR MAINMEMORY DATABASESVLDB 2011CMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SINDEXATTR1ATTR220John 100 John 110BEGINEND1020POINTERCMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SINDEXBEGIN @ 25ATTR1ATTR220John 100 John 110BEGINEND1020POINTERCMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”INDEXATTR1ATTR220John 100 John 110BEGINEND1020POINTERCMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”INDEXATTR1ATTR220John 100 John 110BEGINEND1020POINTERCMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”INDEXATTR1ATTR220John 100 John 110BEGINEND1020POINTERCMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”INDEXATTR1ATTR220John 100 John 110BEGINEND1020POINTERCMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”INDEXATTR1ATTR220John 100 John 110BEGINEND1020POINTERCMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”INDEXATTR1ATTR220John 100 John 110BEGINEND1020POINTERCMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”INDEXATTR1ATTR220John 100 John 110BEGINEND1020POINTERCMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”INDEXATTR1ATTR220John 100 John 110BEGINEND1020Txn25POINTERCMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”COMMIT @ 35INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”COMMIT @ 35INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”COMMIT @ 35INDEXBEGINEND102020Txn253535Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
19H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”COMMIT @ 35INDEXREWINDBEGINEND102020Txn253535Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
20H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
20H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”BEGIN @ 30INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
20H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”BEGIN @ 30Read “John”INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
20H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”BEGIN @ 30Read “John”INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
20H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”BEGIN @ 30Read “John”INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
20H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”BEGIN @ 30Read “John”Update “John”INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
20H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”BEGIN @ 30Read “John”Update “John”INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
20H E K ATO N : O P E R AT I O N SBEGIN @ 25Read “John”Update “John”BEGIN @ 30Read “John”Update “John”INDEXBEGINEND102020Txn25Txn25 POINTERATTR1ATTR2John 100John 110John 130CMU 15-721 (Spring 2016)
21H E K ATO N : T R A N S AC T I O N S TAT E M A PGlobal map of all txns’ states in the system: ACTIVE: The txn is executing read/write operations. VALIDATING: The txn has invoked commit and theDBMS is checking whether it is valid. COMMITTED: The txn is finished, but may have notupdated its versions’ TS. TERMINATED: The txn has updated the TS for all ofthe versions that it created.CMU 15-721 (Spring 2016)
22H E K ATO N : T R A N S AC T I O N L I F E C YC L ETxneventsTxnphasesSource: Paul LarsonCMU 15-721 (Spring 2016)
22H E K ATO N : T R A N S AC T I O N L I F E C YC L ETxneventsBeginTxnphasesGet txn start timestamp, set state to ACTIVESource: Paul LarsonCMU 15-721 (Spring 2016)
22H E K ATO N : T R A N S AC T I O N L I F E C YC L ETxneventsBeginTxnphasesNormalprocessingGet txn start timestamp, set state to ACTIVEPerform normal processing Track txn’s read set, scan set, and write set.Source: Paul LarsonCMU 15-721 (Spring 2016)
22H E K ATO N : T R A N S AC T I O N L I F E C YC L et txn start timestamp, set state to ACTIVEPerform normal processing Track txn’s read set, scan set, and write set.Get txn end timestamp, set state to VALIDATINGSource: Paul LarsonCMU 15-721 (Spring 2016)
22H E K ATO N : T R A N S AC T I O N L I F E C YC L ETxneventsBeginTxnphasesNormalprocessingGet txn start timestamp, set state to ACTIVEPerform normal processing Track txn’s read set, scan set, and write set.Get txn end timestamp, set state to VALIDATINGPrecommitValidationValidate reads and scans If validation OK, write new versions to redo logSource: Paul LarsonCMU 15-721 (Spring 2016)
22H E K ATO N : T R A N S AC T I O N L I F E C YC L ETxneventsBeginTxnphasesNormalprocessingPerform normal processing Track txn’s read set, scan set, and write set.Get txn end timestamp, set state to VALIDATINGPrecommitValidationCommitGet txn start timestamp, set state to ACTIVEValidate reads and scans If validation OK, write new versions to redo logSet txn state to COMMITTEDSource: Paul LarsonCMU 15-721 (Spring 2016)
22H E K ATO N : T R A N S AC T I O N L I F E C YC L ETxneventsBeginTxnphasesNormalprocessingGet txn start timestamp, set state to ACTIVEPerform normal processing Track txn’s read set, scan set, and write set.Get txn end timestamp, set state to VALIDATINGPrecommitValidationValidate reads and scans If validation OK, write new versions to redo logSet txn state to COMMITTEDCommitPostprocessingFix up version timestamps Begin TS in new versions, end TS in old versionsSource: Paul LarsonCMU 15-721 (Spring 2016)
22H E K ATO N : T R A N S AC T I O N L I F E C YC L ETxneventsBeginTxnphasesNormalprocessingPerform normal processing Track txn’s read set, scan set, and write set.Get txn end timestamp, set state to VALIDATINGPrecommitValidationValidate reads and scans If validation OK, write new versions to redo logSet txn state to COMMITTEDCommitPostprocessingTerminateGet txn start timestamp, set state to ACTIVEFix up version timestamps Begin TS in new versions, end TS in old versionsSet txn state to TERMINATEDRemove from txn mapSource: Paul LarsonCMU 15-721 (Spring 2016)
23H E K ATO N : T R A N S AC T I O N M E TA - DATARead Set Pointers to every version read.Write Set Pointers to versions updated (old and new), versionsdeleted (old), and version inserted (new).Scan Set Stores enough information needed to perform eachscan operation.Commit Dependencies List of txns that are waiting for this txn to finish.CMU 15-721 (Spring 2016)
24H E K ATO N : T R A N S AC T I O N VA L I DAT I O NRead Stability Check that each version read is still visible as of theend of the txn.Phantom Avoidance Repeat each scan to check whether new versionshave become visible since the txn began.Extent of validation depends on isolation level: SERIALIZABLE: Read Stability Phantom AvoidanceREPEATABLE READS: Read StabilitySNAPSHOT ISOLATION: NoneREAD COMMITTED: NoneCMU 15-721 (Spring 2016)
25H E K ATO N : O P T I M I S T I C V S . P E S S I M I S T I COptimistic Txns: Check whether a version read is still visible at theend of the txn. Repeat all index scans to check for phantoms.Pessimistic Txns: Use shared & exclusive locks on records and buckets. No validation is needed. Separate background thread to detect deadlocks.CMU 15-721 (Spring 2016)
26H E K ATO N : O P T I M I S T I C V S . P E S S I M I S T I CMillionsThroughput (txn/sec)Database: Single table with 1000 tuplesWorkload: 80% read-only txns 20% update txnsProcessor: 2 sockets, 12 coresOptimistic2Pessimistic1.510.500612# Threads1824Source: Paul LarsonCMU 15-721 (Spring 2016)
27H E K ATO N : I M P L E M E N TAT I O NUse only lock-free data structures No latches, spin locks, or critical sections Indexes, txn map, memory alloc, garbage collector We will discuss Bw-Trees Skip Lists later Only one single serialization point in the DBMSto get the txn’s begin and commit timestamp Atomic Addition (CAS)CMU 15-721 (Spring 2016)
28H E K ATO N : P E R F O R M A N C EBwin – Large online betting company Before: 15,000 requests/sec Hekaton: 250,000 requests/secEdgeNet – Up-to-date inventory status Before: 7,450 rows/sec (ingestion rate) Hekaton: 126,665 rows/secSBI Liquidity Market – FOREX broker Before: 2,812 txn/sec with 4 sec latency Hekaton: 5,313 txn/sec with 1 sec latencySource: Paul LarsonCMU 15-721 (Spring 2016)
29M V CC D E S I G N C H O I C E SVersion ChainsVersion StorageGarbage CollectionCMU 15-721 (Spring 2016)
30VERSION CHAINSApproach #1: Oldest-to-Newest Just append new version to end of the chain. Have to traverse chain on look-ups.Approach #2: Newest-to-Oldest Have to update index pointers for every new version. Don’t have to traverse chain on look ups.The ordering of the chain has differentperformance trade-offs.CMU 15-721 (Spring 2016)
31V E R S I O N S TO R AG EApproach #1: Insert Method New versions are added as new tuples to the table.Approach #2: Delta Method Copy the current version to a separate storagelocation and then overwrite it with the new data. Rollback segment with deltas, Time-travel tableCMU 15-721 (Spring 2016)
32R O L L BAC K S E G M E N T SMain Data TableBEGINENDATTR1ATTR21020John 100CMU 15-721 (Spring 2016)
32R O L L BAC K S E G M E N T SMain Data TableBEGINENDATTR1ATTR21020John 100CMU 15-721 (Spring 2016)
32R O L L BAC K S E G M E N T SMain Data TableBEGINENDATTR1ATTR21020John 100On every update, copy the oldversion to the rollbacksegment and overwrite thetuple in the main data table.CMU 15-721 (Spring 2016)
32R O L L BAC K S E G M E N T SMain Data TableRollback Segment (Per Tuple)BEGINENDATTR1ATTR21020John 100BEGINENDDELTAOn every update, copy the oldversion to the rollbacksegment and overwrite thetuple in the main data table.CMU 15-721 (Spring 2016)
32R O L L BAC K S E G M E N T SMain Data TableRollback Segment (Per Tuple)BEGINENDATTR1ATTR2BEGINENDDELTA1020John 1001020(ATTR2 100)On every update, copy the oldversion to the rollbacksegment and overwrite thetuple in the main data table.CMU 15-721 (Spring 2016)
32R O L L BAC K S E G M E N T SMain Data TableRollback Segment (Per Tuple)BEGINENDATTR1ATTR2BEGINENDDELTA10202025John 100 1101020(ATTR2 100)On every update, copy the oldversion to the rollbacksegment and overwrite thetuple in the main data table.CMU 15-721 (Spring 2016)
32R O L L BAC K S E G M E N T SMain Data TableRollback Segment (Per ohn 100 130 1101020(ATTR2 100)2025(ATTR2 110)On every update, copy the oldversion to the rollbacksegment and overwrite thetuple in the main data table.CMU 15-721 (Spring 2016)
32R O L L BAC K S E G M E N T SMain Data TableRollback Segment (Per ohn 100 130 1101020(ATTR2 100)2025(ATTR2 110)On every update, copy the oldversion to the rollbacksegment and overwrite thetuple in the main data table.Txns can recreate oldversions by applying thedelta in reverse order.CMU 15-721 (Spring 2016)
33G A R BAG E CO L L E C T I O NApproach #1: Vacuum Thread Use a separate background thread to find oldversions and delete them.Approach #2: Cooperative Threads Worker threads remove old versions that theyencounter during scans.GC overhead depends on read/write ratio Hekaton authors report about a 15% overhead on awrite-heavy workload. Typically much less.CMU 15-721 (Spring 2016)
34O B S E R VAT I O N SRead/scan set validations are expensive if thetxns access a lot of data.Appending new versions hurts theperformance of OLAP scans due to pointerchasing & branching.Record-level conflict checks may be too coarsegrained and incur false positives.CMU 15-721 (Spring 2016)
35H Y P E R M V CCRollback Segment with Deltas In-Place updates for non-indexed attributes Delete/Insert updates for indexed attributes.Newest-to-Oldest Version ChainsNo Predicate LocksAvoids write-write conflicts by aborting txnsthat try to update an uncommitted object.FAST SERIALIZABLE MULTI-VERSIONCONCURRENCY CONTROL FOR MAINMEMORY DATABASE SYSTEMSSIGMOD 2015CMU 15-721 (Spring 2016)
36H Y P E R M V CCMain Data TableATTR1ATTR2Tupac 100IceT 200B.I.G 150DrDre 99Rollback Segment (Per Txn)VersionVectorTxn 263(ATTR2 100)(ATTR2 139)Txn 263 1(ATTR2 122)Txn 123(ATTR2 199)CMU 15-721 (Spring 2016)
37H Y R I S E M V CCInsert Method (no rollback segment)Oldest-to-NewestNo garbage collection.All updates are executed as DELETE/INSERT.EFFICIENT TRANSACTION PROCESSING FORHYRISE IN MIXED WORKLOADENVIRONMENTSIMDM 2014CMU 15-721 (Spring 2016)
38S A P H A N A M V CCInsert Method (no rollback segment)Background GC thread (optional)It’s not clear what else they are doing HIGH-PERFORMANCE TRANSACTIONPROCESSING IN SAP HANAIEEE Data Engineering Bulletin 2013CMU 15-721 (Spring 2016)
39PA R T I N G T H O U G H T SMVCC is currently the best approach forsupporting txns in mixed workoads Readers are not blocked by writers.HyPer’s MVCC makes a lot of good decisions forHTAP workloads.CMU 15-721 (Spring 2016)
40NEXT CLASSStored ProceduresOptimistic Concurrency ControlCMU 15-721 (Spring 2016)
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 4 . CMU 15-721 (Spring 2016)
