Dicas para Melhoria de 10x no Desempenho do OpenResty: Estrutura de Dados `Table`

No OpenResty, além dos frequentes problemas de desempenho com operações de string, as operações com table também são um obstáculo de desempenho. Em artigos anteriores, abordamos funções relacionadas a table de forma esporádica, mas não especificamente em termos de melhorias de desempenho. Hoje, vou guiá-lo através do impacto no desempenho das operações com table.

Há duas razões principais pelas quais os desenvolvedores sabem pouco sobre a otimização de desempenho relacionada a table em comparação com as operações de string.

1. O Lua usado no OpenResty é um branch do LuaJIT mantido internamente, em vez do LuaJIT padrão ou do Lua padrão. A maioria dos desenvolvedores não está ciente dessa diferença e tende a usar a biblioteca table do Lua padrão para escrever código OpenResty.
2. Tanto no LuaJIT padrão quanto no branch do LuaJIT mantido pelo OpenResty, a documentação relacionada a operações de table está escondida e é difícil de ser encontrada pelos desenvolvedores. Além disso, não há exemplos de código na documentação, então os desenvolvedores precisam procurar exemplos em projetos de código aberto.

Esses dois pontos tornam o aprendizado do OpenResty uma barreira cognitiva relativamente alta, levando a resultados polarizados - desenvolvedores experientes em OpenResty podem escrever código de alto desempenho, enquanto aqueles que estão começando podem questionar se o alto desempenho do OpenResty é real. Mas, após aprender esta lição, você poderá facilmente superar a barreira de percepção e alcançar uma melhoria de desempenho de 10 vezes.

Antes de detalhar a otimização de table, gostaria de enfatizar um princípio simples relacionado à otimização de table.

Tente reutilizar tabelas e evite a criação desnecessária de tabelas.

Vamos introduzir a otimização em termos de criação de table, inserção de elementos, esvaziamento e uso de loops.

Pré-geração de array

O primeiro passo é criar um array. Em Lua, a maneira como criamos um array é simples.

local t = {}

A linha de código acima cria um array vazio. Você também pode adicionar os dados inicializados ao criar:

local color = {first = "red", "blue", third = "green", "yellow"}

No entanto, a segunda forma de escrita é mais custosa em termos de desempenho, pois envolve alocação de espaço, resize e rehash do array toda vez que um elemento é adicionado ou removido.

Então, como isso deve ser otimizado? Espaço por tempo é uma ideia comum de otimização. Como o gargalo de desempenho aqui é a alocação dinâmica de espaço do array, podemos pré-gerar um array de um tamanho especificado. Embora isso possa desperdiçar algum espaço de memória, as múltiplas alocações de espaço, resize e rehash podem ser combinadas em uma única operação, o que é muito mais eficiente.

A função table.new(narray, nhash) no LuaJIT foi adicionada.

Essa função pré-aloca o tamanho especificado do espaço do array e do hash, em vez de crescer automaticamente ao inserir elementos. Essa é a essência de seus dois parâmetros, narray e nhash.

Aqui está um exemplo simples para ver como usá-la. Como essa função é uma extensão do LuaJIT, precisamos requerê-la antes de usá-la.

local new_tab = require "table.new"
 local t = new_tab(100, 0)
 for i = 1, 100 do
   t[i] = i
 end

Além disso, como o OpenResty anterior não vinculava completamente o LuaJIT e ainda suportava o Lua padrão, alguns códigos antigos faziam isso para compatibilidade. Se a função table.new não for encontrada, uma função vazia será simulada para garantir a uniformidade do chamador.

local ok, new_tab = pcall(require, "table.new")
  if not ok then
    new_tab = function (narr, nrec) return {} end
  end

Cálculo manual do índice da table

Depois de ter um objeto table, o próximo passo é adicionar elementos a ele. A maneira mais direta de inserir um elemento é chamar a função table.insert:

local new_tab = require "table.new"
 local t = new_tab(100, 0)
 for i = 1, 100 do
   table.insert(t, i)
 end

Alternativamente, obtenha o comprimento do array atual primeiro e insira elementos usando índices:

local new_tab = require "table.new"
 local t = new_tab(100, 0)
 for i = 1, 100 do
   t[#t + 1] = i
 end

No entanto, ambos precisam calcular o comprimento do array primeiro e depois adicionar novos elementos. Essa operação tem complexidade de tempo O(n). No exemplo de código acima, o loop for calculará o comprimento do array 100 vezes, então o desempenho não é bom, e quanto maior o array, menor será o desempenho.

Vamos ver como a biblioteca oficial lua-resty-redis resolve esse problema.

local function _gen_req(args)
    local nargs = #args

    local req = new_tab(nargs * 5 + 1, 0)
    req[1] = "*" .. nargs .. "\r\n"
    local nbits = 2

    for i = 1, nargs do
        local arg = args[i]
        req[nbits] = "$"
        req[nbits + 1] = #arg
        req[nbits + 2] = "\r\n"
        req[nbits + 3] = arg
        req[nbits + 4] = "\r\n"
        nbits = nbits + 5
    end
    return req
end

Essa função pré-gera o array req, cujo tamanho é determinado pelos parâmetros de entrada da função, para garantir que o mínimo de espaço possível seja desperdiçado.

Ela usa a variável nbits para manter manualmente o índice do req, em vez de usar a função table.insert embutida no Lua e o operador # para obter o comprimento.

Você pode ver que no loop for, algumas operações como nbits + 1 estão inserindo elementos diretamente como índices e mantendo o índice no valor correto no final com nbits = nbits + 5.

A vantagem disso é óbvia, ela omite a operação O(n) de obter o tamanho do array e, em vez disso, acessa diretamente com o índice, e a complexidade de tempo se torna O(1). A desvantagem também é óbvia, ela reduz a legibilidade do código, e a probabilidade de erro aumenta muito, então é uma faca de dois gumes.

Reutilização de uma única table

Como o custo de criação de uma table é tão alto, naturalmente queremos reutilizá-la o máximo possível. No entanto, há condições para a reutilização. Primeiro, precisamos limpar os dados originais na table para evitar impactos no próximo usuário.

É aqui que a função table.clear é útil. Pelo nome, você pode ver o que ela faz: ela limpa todos os dados no array, mas o comprimento do array não muda. Ou seja, se você usar table.new(narray, nhash) para gerar um array de comprimento 100, após limpá-lo, o comprimento ainda será 100.

Para que você entenda melhor sua implementação, dei um exemplo de código abaixo que é compatível com o Lua padrão:

local ok, clear_tab = pcall(require, "table.clear")
  if not ok then
    clear_tab = function (tab)
      for k, _ in pairs(tab) do
        tab[k] = nil
      end
    end
  end

Como você pode ver, a função clear define cada elemento como nil.

Geralmente, colocamos esse tipo de table circular no nível superior de um módulo. Dessa forma, ao usar as funções no módulo, você pode decidir se as usa diretamente ou após limpá-las, dependendo da situação.

Vejamos um exemplo prático de aplicação. O seguinte pseudo-código é retirado do gateway de API de microsserviços de código aberto Apache APISIX, e esta é sua lógica ao carregar o plugin.

local local_plugins = core.table.new(32, 0)
local function load(plugin_names, wasm_plugin_names)
    local processed = {}
    for _, name in ipairs(plugin_names) do
        if processed[name] == nil then
            processed[name] = true
        end
    end
    for _, attrs in ipairs(wasm_plugin_names) do
        if processed[attrs.name] == nil then
            processed[attrs.name] = attrs
        end
    end

    core.log.warn("new plugins: ", core.json.delay_encode(processed))

    for name, plugin in pairs(local_plugins_hash) do
        local ty = PLUGIN_TYPE_HTTP
        if plugin.type == "wasm" then
            ty = PLUGIN_TYPE_HTTP_WASM
        end
        unload_plugin(name, ty)
    end

    core.table.clear(local_plugins)
    core.table.clear(local_plugins_hash)

    for name, value in pairs(processed) do
        local ty = PLUGIN_TYPE_HTTP
        if type(value) == "table" then
            ty = PLUGIN_TYPE_HTTP_WASM
            name = value
        end
        load_plugin(name, local_plugins, ty)
    end

    -- sort by plugin's priority
    if #local_plugins > 1 then
        sort_tab(local_plugins, sort_plugin)
    end

    for i, plugin in ipairs(local_plugins) do
        local_plugins_hash[plugin.name] = plugin
        if enable_debug() then
            core.log.warn("loaded plugin and sort by priority:",
                          " ", plugin.priority,
                          " name: ", plugin.name)
        end
    end

    _M.load_times = _M.load_times + 1
    core.log.info("load plugin times: ", _M.load_times)
    return true
end

Você pode ver que o array local_plugins é a variável de nível superior para o módulo plugin. No início da função load, a table é limpa, e uma nova lista de plugins é gerada com base na situação atual.

tablepool

Agora, você dominou a otimização de ciclos em uma única tabela. Então, você pode dar um passo adiante e usar um pool de cache para manter várias tabelas disponíveis para acesso a qualquer momento, que é a função do lua-tablepool oficial.

O código a seguir mostra o uso básico de um pool de tabelas. Podemos buscar uma tabela de um pool especificado e liberá-la de volta quando terminarmos de usá-la:

local tablepool = require "tablepool"
local tablepool_fetch = tablepool.fetch
local tablepool_release = tablepool.release


local pool_name = "some_tag"
local function do_sth()
     local t = tablepool_fetch(pool_name, 10, 0)
     -- -- usando t para alguns propósitos
    tablepool_release(pool_name, t)
end

tablepool usa vários dos métodos que introduzimos anteriormente, e tem menos de cem linhas de código, então eu recomendo fortemente que você pesquise e estude por conta própria. Aqui, vou principalmente apresentar suas duas APIs.

A primeira é o método fetch, que recebe os mesmos argumentos que table.new, mas com um pool_name adicional. fetch chamará table.new para criar um novo array se não houver um array livre no pool.

tablepool.fetch(pool_name, narr, nrec)

A segunda é release, uma função que coloca a tabela de volta no pool. Entre seus argumentos, o último, no_clear, é usado para configurar se deve chamar table.clear para limpar o array.

tablepool.release(pool_name, tb, [no_clear])

Veja como todos os métodos que introduzimos anteriormente agora estão inter-relacionados? No entanto, tenha cuidado para não abusar do tablepool por esse motivo. tablepool não é muito usado em projetos reais. Por exemplo, ele não é usado pelo Kong, e o APISIX tem apenas algumas chamadas relacionadas a ele. Na maioria dos casos, mesmo sem a encapsulação dessa camada tablepool, é suficiente para nós usarmos.

Resumo

A otimização de desempenho, uma área difícil no OpenResty, é um ponto quente. Hoje, apresentei dicas de otimização de desempenho relacionadas a table. Espero que elas possam ajudá-lo em seu projeto real.

Por fim, pense em uma pergunta: Você pode fazer um teste de desempenho e comparar a diferença de desempenho antes e depois de usar técnicas de otimização relacionadas a table? Mais uma vez, sinta-se à vontade para deixar um comentário e se comunicar comigo, pois adoraria saber sua prática e visão. Sinta-se à vontade para compartilhar este artigo para que mais pessoas possam participar juntas.