CMU 15-721 paper takeaway 1-5

Youtube Playlist: 15-721 Advanced Database Systems (Spring 2020)

01 - History of Databases

What goes around comes around

M. Stonebraker, et al., What Goes Around Comes Around, in Readings in Database Systems, 4th Edition, 2006 (Optional)

Main idea:

1. Understand the history of database to try not to repeat it.
2. Ideas of databases: data model or interface. Few new ideas occurred.
3. Advantages in field of database: L/P isolation(for agility and optimization), easy to standardize.

Takeaway:

• Elephants of the market often settles technical debate.
• Complex data model will fail, its simplified subset will live.
• Aware when too many players enter a niche market.

Systems:

What’s Really New with NewSQL?

A. Pavlo, et al., What’s New with NewSQL?, in SIGMOD Record (vol. 45, iss. 2), 2016 (Optional)

02 In-Memory Databases (No In-Class Lecture)

Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores

X. Yu, et al., Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores, in VLDB, 2014

Main idea:

7 concurrent control algrithms, in 2 schemes(2PL and Timestamp Ordering), on a 1024 core simulator.

Bottlenecks to scalability: lock-thrashing, preemptive abort, deadlock, timestamp allocation, memory copying.

Takeaway:

System:

• mit-carbon/Graphite

Workload:

• YCSB: Yahoo! Cloud Serving Benchmark.
  • Ziphan distribution.
• TPC-C: For OLTP systems.
  • Implement 2/5 of transactions, a good faith implementation.

03 Multi-Version Concurrency Control (Design Decisions)

An Empirical Evaluation of In-Memory Multi-Version Concurrency Control

Main idea:

Scaling MVCC on modern multi-core, in-memory hardware setting.

Key design decisions:

• concurrency control protocol
  • Timestamp Ordering, Optimistic Concurrency Control, 2-Phase Locking, Serialization Certifier.
• version storage
  • Append Only(N2O/O2N), Time travel Storage(master table), Delta Storage
• garbage collection
  • Tuple level(Basic, Cooperative), Transaction level
• index management
  • Secondary key index: logical/physical pointer.

Takeaway:

• Storage scheme is important, some are influenced by allocation scheme.
  • Delta storage: high write performance, not good at read/table scan.

• MVTO works well for most workloads.

• Transaction level gc has small memory footprint, which is good.

• Logical pointer has higher throughput, especially when workload is update-intensive.

System:

Workload:

YCSB and TPC-C04 - Multi-Version Concurrency Control [Protocols]

Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems

• T. Neumann, et al., Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems, in SIGMOD, 2015

Main idea:

• Serializability validation: Transaction level validation(modified/deleted/created objects), use a Predicate Tree. Marginal overhead.
  • What goes around: Precision locks - SIGMOID 81’
• Scan: Update in-place and VersionedPositions. Strides in between two versioned objects are in the order of millions.
• GC with tombstone, index update by delete then insert.

Takeaway:

It’s good to know internals of current databases’ implementation. They might be simple and out-dated with state-of-art hardware.

Eg: Current serializability validation implementation in 2.3, check entire read set and re-checked in the end. It may be a suitable way in in-disk era.

• Check what goes around: Precision locks - SIGMOID 81’

System used:

Research on HyPer.

This MVCC model suits HTAP databases best, like SAP HANA. Can be implemented in high-performance transactional systems, H-Store/VoltDB. Little need to prefer snapshot isolation in the future.

Workload evaluated:

05 - Multi-Version Concurrency Control [Garbage Collection] (CMU Databases / Spring 2020)

Scalable Garbage Collection for In-Memory MVCC Systems

J. Böttcher, et al., Scalable Garbage Collection for In-Memory MVCC Systems, in VLDB, 2019

Main idea:

• STEAM: Eagerly prune obsolete version.
• Thread local minimum and peek.
• Extra information in tuple: Insert list, attribute mask.

Takeaway:

In place GC would make system more robust to skew.

System used:

Hyper.

Workload evaluated:

CH benchmark, a stress test for GC.

TPC-C, scalability and overhead.

[Back to top]

* Style sheet refers to Dr. Brian Robert Callahan