liblpm: Lookups de prefixo com aceleração de hardware (SIMD) SSE2, AVX2 e AVX512!
A High-Performance Longest Prefix Match Library
Boa tarde galera, recentemente me deparei com um problema de performance em uma aplicaçao que estava desenvolvendo recentemente, e resolvi dar uma atenção especial há este problema após fazer um profiling na aplicação.
A aplicação em si aqui não importa, mas uma das responsabilidades dela é verificar de qual subnet um IP pertence, o profiling em questão, me mostrou que estes lookups de IPv4 e IPv6 eram as partes que mais estavam demorando para serem executadas:
(470k de um total de 870k calls, mais da metade 👀)
Após perceber este garbalo no sistema, comecei a pesquisar algumas libs alternativas que focam em performance para tentar melhorar esse tempo de execução. Acabei encontrando poucas com o este propósito, algumas delas foram:
- liblpm- Bem antiguinha e pouco performática, utilizando muita RAM para vários prefixos.
- rte_lpm - LPM implementada no DPDK com algumas modificações específicas.
Após testar ambas, ainda não havia sentido firmeza nos resultados, então resolvi estudo um pouco mais afundo a implementaçao e como eu poderia deixá-las o mais performático o possível para o meu caso de uso.
Peguei algumas boas referências outros artigos de implementações já existentes, como: Implementing Poptrie in DynASM, Trie IP and Forwarding Lookups e
Branchless Programming, when Predication Is Beneficial
Para a minha versão da lib em si, resolvi utilizar tries de 8-bits de stride, para não utilizar muita RAM, mas também não sofrer muito com cachemiss, como percebi que acontecia nos testes da liblpm já existente, que utiliza strides de 1 bit. Decidi também, adicionar suporte à aceleração de hardware com instruções SIMD como SSE2, AVX2 e AVX512 para realizar diversas operação em paralelo a nível de hardware para economizar alguns ciclos de CPU. Outro ponto foi no design branchless das operações, maxizando a predição das operações de lookup.
Bom, resumindo, as funcionalidades dispostas na lib são as básicas de qualquer outra LPM simples, com uma adiçao do lookup all, retornande todos os prefixos que dão match.
Core Functions
lpm_create(max_depth)- Create LPM trie (32 for IPv4, 128 for IPv6)lpm_add(trie, prefix, prefix_len, next_hop)- Add prefix to trielpm_delete(trie, prefix, prefix_len)- Remove prefix from trielpm_destroy(trie)- Free all resources
Lookup Functions
lpm_lookup(trie, addr)- Single address lookuplpm_lookup_ipv4(trie, addr)- IPv4-specific lookuplpm_lookup_ipv6(trie, addr)- IPv6-specific lookuplpm_lookup_all(trie, addr)- Lookup for multiple match
Os resultados de performance foram bem satisfatórios quando executados utilizando a aceleração de hardware AVX2, em modo batch lookup:
Infelizmente para meu caso de uso, o que preciso mesmo é da funcionalidade de Batch All (as operações mais lentas), mas mesmo assim já foi um bom avanço de performance em relação aos testes que estava fazendo com as outras libs.
Apesar de passar por alguns perrengues depois de executar alguns rounds de fuzzing e testes com edge cases, a lib se mostrou bem estável e performática, alcançando meu objetivo inicial.
Caso queiram testar por ai, ela está publicamente aberta no Github.
Feedbacks e sugestões são bem vindas, valeu.