EBRES: Efficient Buffer Replacement with Exponential Smoothing
Resumo
Os Sistemas gerenciadores de banco de dados (SGBD) implementam um algoritmo de substituição para determinar quais dados trocam entre as memórias principal e secundária. Esses algoritmos estão em constante evolução. Podemos estar iniciando uma nova era desses algoritmos com avanços extensivos no aprendizado de máquina. Este artigo propõe o algoritmo EBRES (Efficient Buffer Replacement with Exponential Smoothing) para incorporar uma política de substituição de página inteligente baseada em um modelo de previsão de baixa sobrecarga para prever acessos futuros a dados.
Palavras-chave:
gerenciamento de buffer, política de substituição, memória flash, aprendizado de máquina
Referências
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.
Publicado
19/09/2022
Como Citar
MORAES, Gustavo; BRAYNER, Angelo; MORAES FILHO, José de Aguiar.
EBRES: Efficient Buffer Replacement with Exponential Smoothing. In: SIMPÓSIO BRASILEIRO DE BANCO DE DADOS (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.
