Transaction Scheduling: VATS and CATS
Variance-aware and contention-aware scheduling for reducing tail latency and throughput collapse under high contention.
VATS
CATS
Research question
How should a database schedule lock contention to improve throughput and reduce latency variance?
Approach
Profile latency sources and schedule waiting transactions using variance-aware and contention-aware policies.
Production adoption
Our CATS algorithm has become the default transaction scheduler in MySQL and Percona Server for MySQL, estimated to be running on hundreds of millions of deployments worldwide. Our earlier VATS algorithm was also adopted as the default transaction scheduler in older versions of MariaDB.
Key results
- Variance-Aware Transaction Scheduling (VATS) prioritizes older transactions to reduce latency variance under contention.
- Contention-Aware Transaction Scheduling (CATS) prioritizes transactions that block the most others.
- Our CATS algorithm has become the default transaction scheduler in MySQL and Percona Server for MySQL, estimated to be running on hundreds of millions of deployments worldwide. Our earlier VATS algorithm was also adopted as the default transaction scheduler in older versions of MariaDB.
Publications
Contention-Aware Lock Scheduling for Transactional Databases
PVLDB 2018 · Proceedings of the VLDB Endowment
Paper ↗Technical Report ↗Project ↗
Cite
@article{5d2dbe3f-c6e6-40c8-9a82-9f8e042ef4a2,
title = {Contention-Aware Lock Scheduling for Transactional Databases},
author = {Boyu Tian and Jiamin Huang and Barzan Mozafari and Grant Schoenebeck},
journal = {Proceedings of the VLDB Endowment},
year = {2018},
doi = {10.1145/3187009.3177740}
}Statistical Analysis of Latency Through Semantic Profiling
EuroSys 2017 · ACM European Conference on Computer Systems
Paper ↗Code ↗Project ↗
Cite
@inproceedings{593a1faa-d447-439a-aca4-9dc5a037630e,
title = {Statistical Analysis of Latency Through Semantic Profiling},
author = {Jiamin Huang and Barzan Mozafari and Thomas F. Wenisch},
booktitle = {ACM European Conference on Computer Systems},
year = {2017},
doi = {10.1145/3064176.3064179}
}Identifying the Major Sources of Variance in Transaction Latencies: Towards More Predictable Databases
CoRR 2016 · Computing Research Repository
Project ↗
Cite
@article{79a739c2-69af-4e7a-9fab-9e1ca9ca9730,
title = {Identifying the Major Sources of Variance in Transaction Latencies: Towards More Predictable Databases},
author = {Jiamin Huang and Barzan Mozafari and Thomas F. Wenisch},
journal = {Computing Research Repository},
year = {2016}
}SnappyData: A Unified Cluster for Streaming, Transactions and Interactive Analytics
CIDR 2017 · Conference on Innovative Data Systems Research
Paper ↗Project ↗
Cite
@inproceedings{e6de4a52-07a5-47c5-8196-ace46d2a49c2,
title = {SnappyData: A Unified Cluster for Streaming, Transactions and Interactive Analytics},
author = {Barzan Mozafari and Jags Ramnarayan and Sudhir Menon and Yogesh Mahajan and Soubhik Chakraborty and Hemant Bhanawat and Kishor Bachhav},
booktitle = {Conference on Innovative Data Systems Research},
year = {2017}
}DBSherlock: A Performance Diagnostic Tool for Transactional Databases
SIGMOD 2016 · ACM SIGMOD International Conference on Management of Data
Paper ↗Code ↗Data ↗Project ↗
Cite
@inproceedings{a5460b19-8bff-4fd2-ae5e-d0ce7477454b,
title = {DBSherlock: A Performance Diagnostic Tool for Transactional Databases},
author = {Dong Young Yoon and Ning Niu and Barzan Mozafari},
booktitle = {ACM SIGMOD International Conference on Management of Data},
year = {2016},
doi = {10.1145/2882903.2915218}
}SnappyData: A Hybrid Transactional Analytical Store Built On Spark
SIGMOD 2016 · ACM SIGMOD International Conference on Management of Data
Paper ↗Project ↗
Cite
@inproceedings{cea59a03-38c4-4acb-bd2d-a41ecabe154a,
title = {SnappyData: A Hybrid Transactional Analytical Store Built On Spark},
author = {Jags Ramnarayan and Barzan Mozafari and Sumedh Wale and Sudhir Menon and Neeraj Kumar and Hemant Bhanawat and Soubhik Chakraborty and Yogesh Mahajan and Rishitesh Mishra and Kishor Bachhav},
booktitle = {ACM SIGMOD International Conference on Management of Data},
year = {2016},
doi = {10.1145/2882903.2899408}
}