Lightweight Asynchronous Repartitioning for Local State Partitioned Systems
Resumo
Partitioning strategies combined with rebalancing algorithms can be used to balance the load in high-throughput systems. Keeping the load balanced constantly is desirable, but the cost of repartitioning can be high. This work presents a rebalancing strategy based on balanced graph partitioning algorithms with low impact during rebalancing operations. The new technique allows for frequent partitioning updates by decoupling the repartitioning process from the rest of the system, thereby avoiding disruptions within the system due to the calculation of new partitioning schemas. In experimental evaluation, the proposed strategy, implemented in an in-memory key-value store prototype, eliminated scheduler pauses and increased throughput by 19% in workloads predominantly composed of scanning requests.Referências
Alchieri, E., Dotti, F., Mendizabal, O. M., and Pedone, F. (2017). Reconfiguring parallel state machine replication. In Proceedings of SRDS ’17, pages 104–113.
Cooper, B. F., Silberstein, A., Tam, E., Ramakrishnan, R., and Sears, R. (2010). Benchmarking cloud serving systems with ycsb. In Proceedings of SoCC ’10, page 143–154.
Curino, C., Jones, E., Zhang, Y., and Madden, S. (2010). Schism: a workload-driven approach to database replication and partitioning. Proc. VLDB Endow., 3(1–2):48–57.
Didona, D. and Zwaenepoel, W. (2019). Size-aware sharding for improving tail latencies in in-memory key-value stores. In Proceedings of the 16th USENIX Conference on Networked Systems Design and Implementation, NSDI’19, page 79–93, USA. USENIX Association.
Goulart, H., Trombeta, J., Franco, A., and Mendizabal, O. (2023). Achieving enhanced performance combining checkpointing and dynamic state partitioning. In Proceedings of SBAC-PAD ’2023, pages 149–159.
Hoang Le, L., Fynn, E., Eslahi-Kelorazi, M., Soulé, R., and Pedone, F. (2019). Dynastar: Optimized dynamic partitioning for scalable state machine replication. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pages 1453–1465.
Karypis, G. and Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, pages 359–392.
Li, B., Xu, W., Abid, M. Z., Distler, T., and Kapitza, R. (2016). Sarek: Optimistic parallel ordering in byzantine fault tolerance. In 2016 12th European Dependable Computing Conference (EDCC), pages 77–88. IEEE.
Li, B., Xu, W., and Kapitza, R. (2018). Dynamic state partitioning in parallelized byzantine fault tolerance. In 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W), pages 158–163. IEEE.
Mendizabal, O. M., De Moura, R. S., Dotti, F. L., and Pedone, F. (2017). Efficient and deterministic scheduling for parallel state machine replication. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 748–757. IEEE.
Quamar, A., Kumar, K. A., and Deshpande, A. (2013). Sword: Scalable workload-aware data placement for transactional workloads. In Proceedings of the 16th International Conference on Extending Database Technology, EDBT ’13, page 430–441, New York, NY, USA. Association for Computing Machinery.
Cooper, B. F., Silberstein, A., Tam, E., Ramakrishnan, R., and Sears, R. (2010). Benchmarking cloud serving systems with ycsb. In Proceedings of SoCC ’10, page 143–154.
Curino, C., Jones, E., Zhang, Y., and Madden, S. (2010). Schism: a workload-driven approach to database replication and partitioning. Proc. VLDB Endow., 3(1–2):48–57.
Didona, D. and Zwaenepoel, W. (2019). Size-aware sharding for improving tail latencies in in-memory key-value stores. In Proceedings of the 16th USENIX Conference on Networked Systems Design and Implementation, NSDI’19, page 79–93, USA. USENIX Association.
Goulart, H., Trombeta, J., Franco, A., and Mendizabal, O. (2023). Achieving enhanced performance combining checkpointing and dynamic state partitioning. In Proceedings of SBAC-PAD ’2023, pages 149–159.
Hoang Le, L., Fynn, E., Eslahi-Kelorazi, M., Soulé, R., and Pedone, F. (2019). Dynastar: Optimized dynamic partitioning for scalable state machine replication. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pages 1453–1465.
Karypis, G. and Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, pages 359–392.
Li, B., Xu, W., Abid, M. Z., Distler, T., and Kapitza, R. (2016). Sarek: Optimistic parallel ordering in byzantine fault tolerance. In 2016 12th European Dependable Computing Conference (EDCC), pages 77–88. IEEE.
Li, B., Xu, W., and Kapitza, R. (2018). Dynamic state partitioning in parallelized byzantine fault tolerance. In 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W), pages 158–163. IEEE.
Mendizabal, O. M., De Moura, R. S., Dotti, F. L., and Pedone, F. (2017). Efficient and deterministic scheduling for parallel state machine replication. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 748–757. IEEE.
Quamar, A., Kumar, K. A., and Deshpande, A. (2013). Sword: Scalable workload-aware data placement for transactional workloads. In Proceedings of the 16th International Conference on Extending Database Technology, EDBT ’13, page 430–441, New York, NY, USA. Association for Computing Machinery.
Publicado
23/10/2024
Como Citar
LUIZ, Douglas Pereira; MENDIZABAL, Odorico Machado.
Lightweight Asynchronous Repartitioning for Local State Partitioned Systems. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 25. , 2024, São Carlos/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 204-215.
DOI: https://doi.org/10.5753/sscad.2024.244785.
