Lei Yang
Xuntao Cheng
Skip Abstract Section
Abstract
Frequency-based cache replacement policies that work well on page-based database storage engines are no longer sufficient for the emerging LSM-tree (Log-Structure Merge-tree) based storage engines. Due to the append-only and copy-on-write techniques applied to accelerate writes, the state-of-the-art LSM-tree adopts mutable record blocks and issues frequent background operations (i.e., compaction, flush) to reorganize records in possibly every block. As a side-effect, such operations invalidate the corresponding entries in the cache for each involved record, causing sudden drops on the cache hit rates and spikes on access latency. Given the observation that existing methods cannot address this cache invalidation problem, we propose Leaper, a machine learning method to predict hot records in an LSM-tree storage engine and prefetch them into the cache without being disturbed by background operations. We implement Leaper in a state-of-the-art LSM-tree storage engine, X-Engine, as a light-weight plug-in. Evaluation results show that Leaper eliminates about 70% cache invalidations and 99% latency spikes with at most 0.95% overheads as measured in real-world workloads.
- M. Y. Ahmad and B. Kemme. Compaction management in distributed key-value datastores. PVLDB, 8(8):850--861, 2015. Google Scholar
Digital Library
- Apache. Hbase. http://hbase.apache.org/.Google Scholar
- C. Berthet. Approximation of lru caches miss rate: Application to power-law popularities. arXiv preprint arXiv:1705.10738, 2017.Google Scholar
- B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422--426, 1970. Google ScholarDigital Library
- C. J. Burges. From ranknet to lambdarank to lambdamart: An overview. Learning, 11(23--581):81, 2010.Google Scholar
- DMLC. Treelite. http://treelite.io/.Google Scholar
- Facebook. Rocksdb. https://github.com/facebook/rocksdb.Google Scholar
- T. Feng. Benchmarking apache samza: 1.2 million messages per second on a single node. URL https://engineering.linkedin.com/performance/benchmarking-apache-samza-12-million-messagessecond-single-node, 2015.Google Scholar
- J. H. Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pages 1189--1232, 2001.Google Scholar
- Google. Leveldb. https://github.com/google/leveldb.Google Scholar
- L. Guo, D. Teng, R. Lee, F. Chen, S. Ma, and X. Zhang. Re-enabling high-speed caching for lsm-trees. arXiv preprint arXiv:1606.02015, 2016.Google Scholar
- M. Hashemi, K. Swersky, J. Smith, G. Ayers, H. Litz, J. Chang, C. Kozyrakis, and P. Ranganathan. Learning memory access patterns. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 1919--1928. PMLR, 2018.Google Scholar
- S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural Computation, 9(8):1735--1780, 1997. Google ScholarDigital Library
- G. Huang, X. Cheng, J. Wang, Y. Wang, D. He, T. Zhang, F. Li, S. Wang, W. Cao, and Q. Li. X-engine: An optimized storage engine for large-scale e-commerce transaction processing. 2019 International Conference on Management of Data (SIGMOD'19), 2019. Google ScholarDigital Library
- H. V. Jagadish, P. P. S. Narayan, S. Seshadri, S. Sudarshan, and R. Kanneganti. Incremental organization for data recording and warehousing. In VLDB'97, pages 16--25. Morgan Kaufmann, 1997. Google ScholarDigital Library
- G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T.-Y. Liu. Lightgbm: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems, pages 3146--3154, 2017. Google ScholarDigital Library
- S. Kimak and J. Ellman. Performance testing and comparison of client side databases versus server side. Northumbria University, 2013.Google Scholar
- A. Kopytov. Sysbench: A system performance benchmark, 2004, 2004.Google Scholar
- T. Kraska, M. Alizadeh, A. Beutel, E. H. Chi, J. Ding, A. Kristo, G. Leclerc, S. Madden, H. Mao, and V. Nathan. Sagedb: A learned database system. 2019.Google Scholar
- T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, pages 489--504, 2018. Google ScholarDigital Library
- G. Li, X. Zhou, S. Li, and B. Gao. Qtune: A query-aware database tuning system with deep reinforcement learning. PVLDB, 12(12):2118--2130, 2019. Google ScholarDigital Library
- J. M. Lobo, A. Jiménez-Valverde, and R. Real. Auc: a misleading measure of the performance of predictive distribution models. Global ecology and Biogeography, 17(2):145--151, 2008.Google Scholar
- L. Ma, D. Van Aken, A. Hefny, G. Mezerhane, A. Pavlo, and G. J. Gordon. Query-based workload forecasting for self-driving database management systems. In Proceedings of the 2018 International Conference on Management of Data, pages 631--645. ACM, 2018. Google ScholarDigital Library
- R. Marcus, P. Negi, H. Mao, C. Zhang, M. Alizadeh, T. Kraska, O. Papaemmanouil, and N. Tatbul. Neo: A learned query optimizer. PVLDB, 12(11):1705--1718, 2019. Google ScholarDigital Library
- R. Marcus and O. Papaemmanouil. Deep reinforcement learning for join order enumeration. In Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, pages 1--4, 2018. Google ScholarDigital Library
- Microsoft. Lightgbm. https://github.com/microsoft/LightGBM.Google Scholar
- B. Mozafari, C. Curino, and S. Madden. Dbseer: Resource and performance prediction for building a next generation database cloud. In CIDR, 2013.Google Scholar
- E. J. O'neil, P. E. O'neil, and G. Weikum. The lru-k page replacement algorithm for database disk buffering. Acm Sigmod Record, 22(2):297--306, 1993. Google ScholarDigital Library
- A. Pavlo, G. Angulo, J. Arulraj, H. Lin, J. Lin, L. Ma, P. Menon, T. C. Mowry, M. Perron, I. Quah, et al. Self-driving database management systems. In CIDR, volume 4, page 1, 2017.Google Scholar
- F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al. Scikit-learn: Machine learning in python. Journal of machine learning research, 12(Oct):2825--2830, 2011. Google ScholarDigital Library
- W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 1990. Google ScholarDigital Library
- M. Richardson, E. Dominowska, and R. Ragno. Predicting clicks: estimating the click-through rate for new ads. In Proceedings of the 16th international conference on World Wide Web, pages 521--530. ACM, 2007. Google ScholarDigital Library
- J. T. Robinson and M. V. Devarakonda. Data cache management using frequency-based replacement. In Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, pages 134--142, 1990. Google ScholarDigital Library
- S. Salza and M. Terranova. Workload modeling for relational database systems. In Database Machines, Fourth International Workshop, Grand Bahama Island, March 1985, pages 233--255. Springer, 1985.Google Scholar
- S. Sarkar, T. I. Papon, D. Staratzis, and M. Athanassoulis. Lethe: A tunable delete-aware LSM engine. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14--19, 2020, pages 893--908. ACM, 2020. Google ScholarDigital Library
- D. C. Schmidt and T. Harrison. Double-checked locking. Pattern languages of program design, (3+):363--375, 1997. Google ScholarDigital Library
- R. Sears and R. Ramakrishnan. blsm: a general purpose log structured merge tree. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 217--228. ACM, 2012. Google ScholarDigital Library
- Y. Sheng, A. Tomasic, T. Zhang, and A. Pavlo. Scheduling oltp transactions via learned abort prediction. In Proceedings of the Second International Workshop on Exploiting Artificial Intelligence Techniques for Data Management, aiDM '19, New York, NY, USA, 2019. Association for Computing Machinery. Google ScholarDigital Library
- J. Tan, T. Zhang, F. Li, J. Chen, Q. Zheng, P. Zhang, H. Qiao, Y. Shi, W. Cao, and R. Zhang. ibtune: individualized buffer tuning for large-scale cloud databases. PVLDB, 12(10):1221--1234, 2019. Google ScholarDigital Library
- D. Teng, L. Guo, R. Lee, F. Chen, S. Ma, Y. Zhang, and X. Zhang. Lsbm-tree: Re-enabling buffer caching in data management for mixed reads and writes. In 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS), pages 68--79. IEEE, 2017.Google ScholarCross Ref
- H. D. Thoreau. Probability and random processes with applications to signal processing - united states edition. Experimental Cell Research, 139(1):63--70, 2002.Google Scholar
- D. Van Aken, A. Pavlo, G. J. Gordon, and B. Zhang. Automatic database management system tuning through large-scale machine learning. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1009--1024, 2017. Google ScholarDigital Library
- J. Zhang, Y. Liu, K. Zhou, G. Li, Z. Xiao, B. Cheng, J. Xing, Y. Wang, T. Cheng, L. Liu, et al. An end-to-end automatic cloud database tuning system using deep reinforcement learning. In Proceedings of the 2019 International Conference on Management of Data, pages 415--432, 2019. Google ScholarDigital Library
Recommendations
TLB Improvements for Chip Multiprocessors: Inter-Core Cooperative Prefetchers and Shared Last-Level TLBs
Translation Lookaside Buffers (TLBs) are critical to overall system performance. Much past research has addressed uniprocessor TLBs, lowering access times and miss rates. However, as Chip MultiProcessors (CMPs) become ubiquitous, TLB design and ...
High performance cache replacement using re-reference interval prediction (RRIP)
ISCA '10Practical cache replacement policies attempt to emulate optimal replacement by predicting the re-reference interval of a cache block. The commonly used LRU replacement policy always predicts a near-immediate re-reference interval on cache hits and ...
Comments