EBRES: Efficient Buffer Replacement with Exponential Smoothing
Abstract
Database management systems (DBMS) implement a replacement algorithm to determine which data to swap between main and secondary memories. Such algorithms are constantly evolving. We may be starting a new era of these algorithms with extensive advances in machine learning. This article proposes the EBRES (Efficient Buffer Replacement with Exponential Smoothing) algorithm to embed an intelligent page replacement policy based on a low-overhead prediction model to predict future data accesses.
Keywords:
buffer management, replacement policy, flash memory, machine learning
References
Association, S. N. I. (2007a). Microsoft Storage File Server Traces. http://iotta.snia.org/traces/158.
Association, S. N. I. (2007b). TPC-C SNIA Traces. http://iotta.snia.org/traces/131.
Association, S. N. I. (2007c). TPC-E SNIA Traces. http://iotta.snia.org/traces/133.
Choi, H. and Park, S. (2022). Learning future reference patterns for efficient cache replacement decisions. IEEE Access, 10:25922-25934.
Effelsberg, W. and Härder, T. (1984). Principles of database buffer management. ACM Trans. Database Systems.
Fan, Z., Du, D. H. C., and Voigt, D. (2014). H-arc: A non-volatile memory based cache policy for solid state drives. In 2014 30th Symposium on Mass Storage Systems and Technologies (MSST), pages 1-11.
Gardner Jr, E. S. (2006). Exponential smoothing: The state of the art-part ii. International journal of forecasting, 22(4):637-666.
Harizopoulos, S., Abadi, D. J., Madden, S., and Stonebraker, M. (2008). Oltp through the looking glass, and what we found there. In Proceedings of the 2008 ACM SIGMOD, SIGMOD ’08.
He, J., Jia, G., Han, G., Wang, H., and Yang, X. (2017). Locality-aware replacement algorithm in flash memory to optimize cloud computing for smart factory of industry 4.0. IEEE Access, 5:16252-16262.
Hellerstein, J. M., Stonebraker, M., and Hamilton, J. (2007). Architecture of a database system. Found. Trends databases, 1(2):141-259.
Jiang, S. and Zhang, X. (2002). Lirs: An efficient low interreference recency set replacement policy to improve buffer cache performance. In Proceedings of the 2002 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’02, page 31-42, New York, NY, USA. Association for Computing Machinery.
Levandoski, J. J., Larson, P.-Å., and Stoica, R. (2013). Identifying hot and cold data in main-memory databases. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pages 26-37. IEEE.
Li, Z., Jin, P., Su, X., Cui, K., and Yue, L. (2009). Ccf-lru: a new buffer replacement algorithm for flash memory. IEEE Transactions on Consumer Electronics, 55(3):1351-1359.
Megiddo, N. and Modha, D. S. (2003). Arc: A self-tuning, low overhead replacement cache. In Proceedings of the 2Nd USENIX Conference on File and Storage Technologies.
Ou, Y., Härder, T., and Jin, P. (2009). Cfdc: A flash-aware replacement policy for database buffer management. In Proceedings of the Fifth International Workshop on Data Management on New Hardware, DaMoN ’09, page 15-20, New York, NY, USA. Association for Computing Machinery.
Park, S., Kim, Y., Urgaonkar, B., Lee, J., and Seo, E. (2011). A comprehensive study of energy efficiency and performance of flash-based ssd. volume 57, pages 354-365.
Park, S.-y., Jung, D., Kang, J.-u., Kim, J.-s., and Lee, J. (2006). Cflru: A replacement algorithm for flash memory. In Proceedings of the 2006 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, page 234-241, New York, NY, USA. Association for Computing Machinery.
Rodriguez, L. V., Yusuf, F., Lyons, S., Paz, E., Rangaswami, R., Liu, J., Zhao, M., and Narasimhan, G. (2021). Learning cache replacement with CACHEUS. In 19th USENIX Conference on File and Storage Technologies (FAST 21), pages 341-354. USENIX Association.
Tavares, J. A. (2015). Database Buffer Management Strategies for Asymmetric Media. Master dissertation, Universidade de Fortaleza-Unifor.
Veríssimo, A. J., da Cunha Alves, C., Henning, E., do Amaral, C. E., and da Cruz, A. C. (2013). Métodos estatísticos de suavização exponencial holt-winters para previsão de demanda em uma empresa do setor metal mecânico. Revista Gestão Industrial, 8(4).
Vietri, G., Rodriguez, L. V., Martinez, W. A., Lyons, S., Liu, J., Rangaswami, R., Zhao, M., and Narasimhan, G. (2018). Driving cache replacement with ml-based lecar. In Proceedings of the 10th USENIX Conference on Hot Topics in Storage and File Systems, HotStorage’18, page 3, USA. USENIX Association.
Wu, X., Cai, D., and Guan, S. (2019). A multiple LRU list buffer management algorithm. IOP Conference Series: Materials Science and Engineering, 569:052002.
Association, S. N. I. (2007b). TPC-C SNIA Traces. http://iotta.snia.org/traces/131.
Association, S. N. I. (2007c). TPC-E SNIA Traces. http://iotta.snia.org/traces/133.
Choi, H. and Park, S. (2022). Learning future reference patterns for efficient cache replacement decisions. IEEE Access, 10:25922-25934.
Effelsberg, W. and Härder, T. (1984). Principles of database buffer management. ACM Trans. Database Systems.
Fan, Z., Du, D. H. C., and Voigt, D. (2014). H-arc: A non-volatile memory based cache policy for solid state drives. In 2014 30th Symposium on Mass Storage Systems and Technologies (MSST), pages 1-11.
Gardner Jr, E. S. (2006). Exponential smoothing: The state of the art-part ii. International journal of forecasting, 22(4):637-666.
Harizopoulos, S., Abadi, D. J., Madden, S., and Stonebraker, M. (2008). Oltp through the looking glass, and what we found there. In Proceedings of the 2008 ACM SIGMOD, SIGMOD ’08.
He, J., Jia, G., Han, G., Wang, H., and Yang, X. (2017). Locality-aware replacement algorithm in flash memory to optimize cloud computing for smart factory of industry 4.0. IEEE Access, 5:16252-16262.
Hellerstein, J. M., Stonebraker, M., and Hamilton, J. (2007). Architecture of a database system. Found. Trends databases, 1(2):141-259.
Jiang, S. and Zhang, X. (2002). Lirs: An efficient low interreference recency set replacement policy to improve buffer cache performance. In Proceedings of the 2002 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’02, page 31-42, New York, NY, USA. Association for Computing Machinery.
Levandoski, J. J., Larson, P.-Å., and Stoica, R. (2013). Identifying hot and cold data in main-memory databases. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pages 26-37. IEEE.
Li, Z., Jin, P., Su, X., Cui, K., and Yue, L. (2009). Ccf-lru: a new buffer replacement algorithm for flash memory. IEEE Transactions on Consumer Electronics, 55(3):1351-1359.
Megiddo, N. and Modha, D. S. (2003). Arc: A self-tuning, low overhead replacement cache. In Proceedings of the 2Nd USENIX Conference on File and Storage Technologies.
Ou, Y., Härder, T., and Jin, P. (2009). Cfdc: A flash-aware replacement policy for database buffer management. In Proceedings of the Fifth International Workshop on Data Management on New Hardware, DaMoN ’09, page 15-20, New York, NY, USA. Association for Computing Machinery.
Park, S., Kim, Y., Urgaonkar, B., Lee, J., and Seo, E. (2011). A comprehensive study of energy efficiency and performance of flash-based ssd. volume 57, pages 354-365.
Park, S.-y., Jung, D., Kang, J.-u., Kim, J.-s., and Lee, J. (2006). Cflru: A replacement algorithm for flash memory. In Proceedings of the 2006 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, page 234-241, New York, NY, USA. Association for Computing Machinery.
Rodriguez, L. V., Yusuf, F., Lyons, S., Paz, E., Rangaswami, R., Liu, J., Zhao, M., and Narasimhan, G. (2021). Learning cache replacement with CACHEUS. In 19th USENIX Conference on File and Storage Technologies (FAST 21), pages 341-354. USENIX Association.
Tavares, J. A. (2015). Database Buffer Management Strategies for Asymmetric Media. Master dissertation, Universidade de Fortaleza-Unifor.
Veríssimo, A. J., da Cunha Alves, C., Henning, E., do Amaral, C. E., and da Cruz, A. C. (2013). Métodos estatísticos de suavização exponencial holt-winters para previsão de demanda em uma empresa do setor metal mecânico. Revista Gestão Industrial, 8(4).
Vietri, G., Rodriguez, L. V., Martinez, W. A., Lyons, S., Liu, J., Rangaswami, R., Zhao, M., and Narasimhan, G. (2018). Driving cache replacement with ml-based lecar. In Proceedings of the 10th USENIX Conference on Hot Topics in Storage and File Systems, HotStorage’18, page 3, USA. USENIX Association.
Wu, X., Cai, D., and Guan, S. (2019). A multiple LRU list buffer management algorithm. IOP Conference Series: Materials Science and Engineering, 569:052002.
Published
2022-09-19
How to Cite
MORAES, Gustavo; BRAYNER, Angelo; MORAES FILHO, José de Aguiar.
EBRES: Efficient Buffer Replacement with Exponential Smoothing. In: BRAZILIAN SYMPOSIUM ON DATABASES (SBBD), 37. , 2022, Búzios.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 103-115.
ISSN 2763-8979.
DOI: https://doi.org/10.5753/sbbd.2022.224643.
