Советы для 10-кратного улучшения производительности в OpenResty: структура данных `Table`

API7.ai

December 9, 2022

OpenResty (NGINX + Lua)

В OpenResty, помимо частых проблем с производительностью операций с string, операции с table также являются узким местом в производительности. В предыдущих статьях мы уже затрагивали функции, связанные с table, но не в контексте улучшения производительности. Сегодня я расскажу о влиянии операций с table на производительность.

Есть две основные причины, по которым разработчики мало знают об оптимизации производительности, связанной с table, по сравнению с операциями с string.

  1. Lua, используемая в OpenResty, — это самостоятельно поддерживаемая ветка LuaJIT, а не стандартный LuaJIT или стандартный Lua. Большинство разработчиков не знают об этом различии и склонны использовать стандартную библиотеку table Lua для написания кода OpenResty.
  2. Как в стандартном LuaJIT, так и в ветке LuaJIT, поддерживаемой OpenResty, документация, связанная с операциями с таблицами, скрыта глубоко и трудна для поиска разработчиками. Кроме того, в документации нет примеров кода, поэтому разработчикам приходится искать примеры в открытых проектах.

Эти два момента делают изучение OpenResty относительно сложным, что приводит к поляризованным результатам — опытные разработчики OpenResty могут писать очень производительный код, а те, кто только начинает, могут сомневаться в реальности высокой производительности OpenResty. Однако, изучив этот урок, вы сможете легко преодолеть этот барьер и добиться 10-кратного улучшения производительности.

Прежде чем углубляться в детали оптимизации table, я хотел бы подчеркнуть простой принцип оптимизации, связанной с table.

Старайтесь повторно использовать таблицы и избегайте ненужного создания таблиц.

Мы рассмотрим оптимизацию с точки зрения создания таблиц, вставки элементов, очистки и использования циклов.

Предварительно сгенерированный массив

Первый шаг — создание массива. В Lua способ создания массива прост.

local t = {}

Приведенная выше строка кода создает пустой массив. Вы также можете добавить инициализированные данные при создании:

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

Однако второй способ написания более затратен с точки зрения производительности, так как он включает выделение памяти, изменение размера (resize) и повторное хеширование (rehash) массива каждый раз при добавлении и удалении элементов.

Как же это оптимизировать? Оптимизация "пространство в обмен на время" — это распространенный подход. Поскольку узким местом здесь является динамическое выделение памяти для массива, мы можем предварительно сгенерировать массив заданного размера. Хотя это может привести к некоторому расходу памяти, множественные выделения памяти, изменение размера и повторное хеширование можно объединить в одно действие, что значительно повышает эффективность.

В LuaJIT была добавлена функция table.new(narray, nhash).

Эта функция предварительно выделяет указанный размер массива и хеш-таблицы, вместо того чтобы увеличивать их при вставке элементов. Это и есть смысл двух параметров narray и nhash.

Вот простой пример, показывающий, как ее использовать. Поскольку эта функция является расширением LuaJIT, нам нужно выполнить require, чтобы использовать ее.

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

Кроме того, поскольку предыдущие версии OpenResty не полностью связывались с LuaJIT и все еще поддерживали стандартный Lua, в некоторых старых кодах для совместимости делают следующее. Если функция table.new не найдена, будет создана пустая функция, чтобы обеспечить единообразие вызова.

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

Ручной расчет индекса table

После создания объекта table следующим шагом является добавление элементов в него. Самый прямой способ вставки элемента — вызов функции table.insert:

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

Или сначала получить длину текущего массива и вставлять элементы с использованием индексов:

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

Однако оба этих способа требуют сначала вычисления длины массива, а затем добавления новых элементов. Временная сложность этой операции составляет O(n). В приведенном выше примере кода цикл for будет вычислять длину массива 100 раз, что негативно сказывается на производительности, и чем больше массив, тем ниже будет производительность.

Давайте посмотрим, как официальная библиотека lua-resty-redis решает эту проблему.

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

Эта функция предварительно генерирует массив req, размер которого определяется входными параметрами функции, чтобы минимизировать потери памяти.

Она использует переменную nbits для ручного управления индексом req, вместо использования встроенной функции Lua table.insert и оператора # для получения длины.

Вы можете видеть, что в цикле for такие операции, как nbits + 1, вставляют элементы напрямую как индексы и поддерживают индекс на правильном значении в конце с помощью nbits = nbits + 5.

Преимущество этого очевидно: оно исключает операцию O(n) получения размера массива и вместо этого напрямую обращается к элементам по индексу, что снижает временную сложность до O(1). Недостаток также очевиден: это снижает читаемость кода и значительно увеличивает вероятность ошибки, так что это обоюдоострый меч.

Повторное использование одной таблицы

Поскольку создание таблицы требует значительных ресурсов, естественно, мы хотим повторно использовать ее как можно чаще. Однако для повторного использования есть условия. Сначала нам нужно очистить исходные данные в таблице, чтобы избежать влияния на следующего пользователя.

Здесь на помощь приходит функция table.clear. Из названия видно, что она делает: очищает все данные в массиве, но длина массива не изменяется. То есть, если вы используете table.new(narray, nhash) для создания массива длиной 100, после очистки его длина останется равной 100.

Чтобы лучше понять ее реализацию, я привел пример кода, совместимого со стандартным Lua:

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

Как видно, функция clear устанавливает каждый элемент в nil.

Обычно мы размещаем такие циклические таблицы на верхнем уровне модуля. Таким образом, при использовании функций модуля вы можете решить, использовать ли их напрямую или после очистки, в зависимости от ситуации.

Давайте рассмотрим практический пример. Следующий псевдокод взят из открытого микросервисного API-шлюза Apache APISIX, и это его логика при загрузке плагина.

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

    -- сортировка по приоритету плагина
    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

Вы можете видеть, что массив local_plugins является переменной верхнего уровня для модуля plugin. В начале функции load таблица очищается, и на основе текущей ситуации генерируется новый список плагинов.

tablepool

К этому моменту вы освоили оптимизацию циклического использования одной таблицы. Затем вы можете сделать шаг вперед и использовать пул кэша для хранения нескольких таблиц, доступных в любое время, что и делает официальный lua-tablepool.

Следующий код показывает базовое использование пула таблиц. Мы можем получить таблицу из указанного пула и вернуть ее обратно после использования:

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)
     -- -- использование t для каких-либо целей
    tablepool_release(pool_name, t)
end

tablepool использует несколько методов, которые мы рассмотрели ранее, и содержит менее ста строк кода, поэтому я настоятельно рекомендую изучить его самостоятельно. Здесь я в основном расскажу о двух его API.

Первый — это метод fetch, который принимает те же аргументы, что и table.new, но с дополнительным параметром pool_name. Если в пуле нет свободных массивов, fetch вызовет table.new для создания нового массива.

tablepool.fetch(pool_name, narr, nrec)

Второй — это release, функция, которая возвращает таблицу обратно в пул. Среди ее аргументов последний, no_clear, используется для настройки, вызывать ли table.clear для очистки массива.

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

Видите, как все методы, которые мы рассмотрели ранее, теперь связаны? Однако будьте осторожны, чтобы не злоупотреблять tablepool по этой причине. tablepool не так часто используется в реальных проектах. Например, он не используется в Kong, а в APISIX есть лишь несколько вызовов, связанных с ним. В большинстве случаев даже без этой обертки tablepool нам достаточно.

Итог

Оптимизация производительности — это сложная область в OpenResty, но она также является важной темой. Сегодня я рассказал о советах по оптимизации производительности, связанных с table. Надеюсь, они помогут вам в ваших реальных проектах.

Наконец, подумайте над вопросом: можете ли вы сами провести тест производительности и сравнить разницу в производительности до и после использования техник оптимизации, связанных с table? Снова приглашаю вас оставить комментарий и поделиться своими практиками и взглядами. Поделитесь этой статьей, чтобы больше людей могли принять участие в обсуждении.