Danian: Redução da latência de calda de aplicações em rede através de um escalonador O(1)
Resumo
A alocação de núcleos para threads de programas é um problema complexo e de grande custo computacional dentro de ambientes Unix. O escalonador Caladan é uma solução que otimiza na escala dos microssegundos a forma como threads e núcleos são escalonados. O sistema Danian proposto, melhora o algoritmo de escolha de threads para um núcleo a ser escalonado através de memoization. O custo dessa operação foi reduzido de O(n) para O(1), o tempo de CPU reduzido em 7%, a latência de calda reduziu em 3% para o experimento Synthetic e 5% para o experimento Netperf.
Referências
Anderson, T. E., Bershad, B. N., Lazowska, E. D., and Levy, H. M. (1991). Scheduler activations: Effective kernel support for the user-level management of parallelism. SIGOPS Oper. Syst. Rev., 25(5):95–109.
Barbette, T., Katsikas, G. P., Maguire, G. Q., and Kosti´c, D. (2019). Rss++: Load and state-aware receive side scaling. In Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies, CoNEXT ’19, page 318–333, New York, NY, USA. Association for Computing Machinery.
Belay, A., Bittau, A., Mashtizadeh, A., Terei, D., Maziéres, D., and Kozyrakis, C. (2012). In 10th USENIX SympoDune: Safe user-level access to privileged CPU features. sium on Operating Systems Design and Implementation (OSDI 12), pages 335–348, Hollywood, CA. USENIX Association.
Bellman, R. (1954). The theory of dynamic programming. Bulletin of the American Mathematical Society, 60(6):503 – 515.
Bosshart, P., Daly, D., Gibb, G., Izzard, M., McKeown, N., Rexford, J., Schlesinger, C., Talayco, D., Vahdat, A., Varghese, G., and Walker, D. (2014). P4: Programming protocol-independent packet processors. SIGCOMM Comput. Commun. Rev., 44(3):87–95.
Introduction to Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Algorithms, Third Edition. The MIT Press, 3rd edition.
Dean, J. and Barroso, L. A. (2013). The tail at scale. Communications of the ACM, 56:74–80.
DPDK (2021 (acessado em Março de 2021)). Data Plane Development Kit.
Duplyakin, D., Ricci, R., Maricq, A., Wong, G., Duerig, J., Eide, E., Stoller, L., Hibler, M., Johnson, D., Webb, K., Akella, A., Wang, K., Ricart, G., Landweber, L., Elliott, C., Zink, M., Cecchet, E., Kar, S., and Mishra, P. (2019). The design and operation of cloudlab. In 2019 USENIX Annual Technical Conference (USENIX ATC 19), pages 1–14, Renton, WA. USENIX Association.
Fried, J., Ruan, Z., Ousterhout, A., and Belay, A. (2020). Caladan: Mitigating interference at microsecond timescales. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 281–297. USENIX Association.
Høiland-Jørgensen, T., Brouer, J. D., Borkmann, D., Fastabend, J., Herbert, T., Ahern, D., and Miller, D. (2018). The express data path: Fast programmable packet processing in the operating system kernel. In Proceedings of the 14th International Conference on Emerging Networking EXperiments and Technologies, CoNEXT ’18, page 54–66, New York, NY, USA. Association for Computing Machinery.
Moon, Y., Lee, S., Jamshed, M. A., and Park, K. (2020). Acceltcp: Accelerating network In 17th USENIX Symposium on Networapplications with stateful TCP ofoading. ked Systems Design and Implementation (NSDI 20), pages 77–92, Santa Clara, CA. USENIX Association.
Ousterhout, A., Fried, J., Behrens, J., Belay, A., and Balakrishnan, H. (2019). Shenango: In 16th Achieving high CPU efficiency for latency-sensitive datacenter workloads. USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), pages 361–378, Boston, MA. USENIX Association.
Pantuza, G., Sampaio, F., Vieira, L. F. M., Guedes, D., and Vieira, M. A. M. (2014). Network management through graphs in software defined networks. In 10th International Conference on Network and Service Management (CNSM) and Workshop, pages 400–405.
Rushing’s, S. (2021 (acessado em Março de 2021)). Coroutine library threads.
Vieira, M. A. M., Castanho, M. S., Pacífico, R. D. G., Santos, E. R. S., Câmara Júnior, E. P. M., and Vieira, L. F. M. (2019). Processamento Rápido de Pacotes com eBPF e XDP. In Minicursos do XXXVII Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC), Porto Alegre, RS, Brasil. SBC.
Waldspurger, C. A. and Weihl, W. E. (1994). Lottery scheduling: Flexible proportionalshare resource management. In Proceedings of the 1st USENIX Conference on Operating Systems Design and Implementation, OSDI ’94, page 1–es, USA. USENIX Association.
Yang, X., Eggert, L., Ott, J., Uhlig, S., Sun, Z., and Antichi, G. (2020). Making quic quicker with nic ofoad. In Proceedings of the Workshop on the Evolution, Performance, and Interoperability of QUIC, EPIQ ’20, page 21–27, New York, NY, USA. Association for Computing Machinery.
Barbette, T., Katsikas, G. P., Maguire, G. Q., and Kosti´c, D. (2019). Rss++: Load and state-aware receive side scaling. In Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies, CoNEXT ’19, page 318–333, New York, NY, USA. Association for Computing Machinery.
Belay, A., Bittau, A., Mashtizadeh, A., Terei, D., Maziéres, D., and Kozyrakis, C. (2012). In 10th USENIX SympoDune: Safe user-level access to privileged CPU features. sium on Operating Systems Design and Implementation (OSDI 12), pages 335–348, Hollywood, CA. USENIX Association.
Bellman, R. (1954). The theory of dynamic programming. Bulletin of the American Mathematical Society, 60(6):503 – 515.
Bosshart, P., Daly, D., Gibb, G., Izzard, M., McKeown, N., Rexford, J., Schlesinger, C., Talayco, D., Vahdat, A., Varghese, G., and Walker, D. (2014). P4: Programming protocol-independent packet processors. SIGCOMM Comput. Commun. Rev., 44(3):87–95.
Introduction to Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Algorithms, Third Edition. The MIT Press, 3rd edition.
Dean, J. and Barroso, L. A. (2013). The tail at scale. Communications of the ACM, 56:74–80.
DPDK (2021 (acessado em Março de 2021)). Data Plane Development Kit.
Duplyakin, D., Ricci, R., Maricq, A., Wong, G., Duerig, J., Eide, E., Stoller, L., Hibler, M., Johnson, D., Webb, K., Akella, A., Wang, K., Ricart, G., Landweber, L., Elliott, C., Zink, M., Cecchet, E., Kar, S., and Mishra, P. (2019). The design and operation of cloudlab. In 2019 USENIX Annual Technical Conference (USENIX ATC 19), pages 1–14, Renton, WA. USENIX Association.
Fried, J., Ruan, Z., Ousterhout, A., and Belay, A. (2020). Caladan: Mitigating interference at microsecond timescales. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 281–297. USENIX Association.
Høiland-Jørgensen, T., Brouer, J. D., Borkmann, D., Fastabend, J., Herbert, T., Ahern, D., and Miller, D. (2018). The express data path: Fast programmable packet processing in the operating system kernel. In Proceedings of the 14th International Conference on Emerging Networking EXperiments and Technologies, CoNEXT ’18, page 54–66, New York, NY, USA. Association for Computing Machinery.
Moon, Y., Lee, S., Jamshed, M. A., and Park, K. (2020). Acceltcp: Accelerating network In 17th USENIX Symposium on Networapplications with stateful TCP ofoading. ked Systems Design and Implementation (NSDI 20), pages 77–92, Santa Clara, CA. USENIX Association.
Ousterhout, A., Fried, J., Behrens, J., Belay, A., and Balakrishnan, H. (2019). Shenango: In 16th Achieving high CPU efficiency for latency-sensitive datacenter workloads. USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), pages 361–378, Boston, MA. USENIX Association.
Pantuza, G., Sampaio, F., Vieira, L. F. M., Guedes, D., and Vieira, M. A. M. (2014). Network management through graphs in software defined networks. In 10th International Conference on Network and Service Management (CNSM) and Workshop, pages 400–405.
Rushing’s, S. (2021 (acessado em Março de 2021)). Coroutine library threads.
Vieira, M. A. M., Castanho, M. S., Pacífico, R. D. G., Santos, E. R. S., Câmara Júnior, E. P. M., and Vieira, L. F. M. (2019). Processamento Rápido de Pacotes com eBPF e XDP. In Minicursos do XXXVII Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC), Porto Alegre, RS, Brasil. SBC.
Waldspurger, C. A. and Weihl, W. E. (1994). Lottery scheduling: Flexible proportionalshare resource management. In Proceedings of the 1st USENIX Conference on Operating Systems Design and Implementation, OSDI ’94, page 1–es, USA. USENIX Association.
Yang, X., Eggert, L., Ott, J., Uhlig, S., Sun, Z., and Antichi, G. (2020). Making quic quicker with nic ofoad. In Proceedings of the Workshop on the Evolution, Performance, and Interoperability of QUIC, EPIQ ’20, page 21–27, New York, NY, USA. Association for Computing Machinery.
Publicado
16/08/2021
Como Citar
PANTUZA, Gustavo; BLEME, Lucas A. C.; VIEIRA, Marcos Augusto M.; VIEIRA, Luiz Filipe M..
Danian: Redução da latência de calda de aplicações em rede através de um escalonador O(1). In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC), 39. , 2021, Uberlândia.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 169-181.
ISSN 2177-9384.
DOI: https://doi.org/10.5753/sbrc.2021.16719.
