OpenResty で 10 倍のパフォーマンス向上を実現するためのヒント: `Table` データ構造

API7.ai

December 9, 2022

OpenResty (NGINX + Lua)

OpenRestyでは、string操作に加えて、table操作もパフォーマンスのボトルネックとなることがあります。これまでの記事では、table関連の関数について断片的に触れてきましたが、パフォーマンス改善の観点からは詳しく説明していませんでした。今日は、table操作がパフォーマンスに与える影響について詳しく解説します。

開発者がtable関連のパフォーマンス最適化についてstring操作よりも知らない理由は、主に2つあります。

  1. OpenRestyで使用されているLuaは、標準のLuaJITや標準のLuaではなく、独自にメンテナンスされているLuaJITブランチです。多くの開発者はこの違いに気づかず、標準のLua tableライブラリを使用してOpenRestyのコードを書く傾向があります。
  2. 標準のLuaJITやOpenRestyが独自にメンテナンスしているLuaJITブランチにおいても、table操作に関するドキュメントは深く隠されており、開発者が見つけにくい状況です。また、ドキュメントにはサンプルコードが含まれていないため、開発者はオープンソースプロジェクトから例を探す必要があります。

これらの理由から、OpenRestyを学ぶことは比較的高い認知障壁となり、結果として二極化が生じます。経験豊富なOpenResty開発者は非常に高性能なコードを書くことができますが、初心者はOpenRestyの高性能さが本当なのか疑問に思うかもしれません。しかし、このレッスンを学ぶことで、簡単に認知障壁を乗り越え、10倍のパフォーマンス向上を実現できます。

tableの最適化について詳しく説明する前に、table関連の最適化における簡単な原則を強調しておきます。

tableを再利用し、不必要なtableの作成を避けること。

tableの作成、要素の挿入、クリア、ループ使用の観点から最適化を紹介します。

事前生成された配列

最初のステップは配列の作成です。Luaでは、配列を作成する方法は簡単です。

local t = {}

上記のコードは空の配列を作成します。初期化データを追加することもできます。

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

ただし、2番目の書き方はパフォーマンスの面でコストがかかります。なぜなら、配列要素の追加や削除のたびに、スペースの割り当て、resize、rehashが行われるためです。

では、どのように最適化すべきでしょうか？時間を節約するためにスペースを犠牲にするというのは、一般的な最適化の考え方です。ここでのパフォーマンスのボトルネックは配列スペースの動的割り当てなので、指定されたサイズの配列を事前に生成することができます。これにより、メモリスペースが多少無駄になるかもしれませんが、複数回のスペース割り当て、resize、rehashを1回にまとめることができ、効率が大幅に向上します。

LuaJITにはtable.new(narray, nhash)関数が追加されました。

この関数は、指定された配列とハッシュスペースのサイズを事前に割り当てます。要素を挿入する際に自分自身を成長させるのではなく、これがその2つのパラメータ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を事前に生成し、できるだけスペースを無駄にしないようにしています。

Luaの組み込み関数table.insertや#演算子を使用して長さを取得する代わりに、nbits変数を使用してreqの添字を手動で管理しています。

forループ内で、nbits + 1などの操作を行い、要素を直接添字として挿入し、最後にnbits = nbits + 5で添字を正しい値に保っています。

この方法の利点は明らかで、配列のサイズを取得するO(n)の操作を省略し、代わりにインデックスで直接アクセスするため、時間計算量がO(1)になります。欠点も明らかで、コードの可読性が低下し、エラーの確率が大幅に増加するため、諸刃の剣です。

単一のtableを再利用する

tableの作成コストが高いため、できるだけ再利用したいと考えます。ただし、再利用には条件があります。まず、table内の元のデータをクリアして、次のユーザーに影響を与えないようにする必要があります。

ここで役立つのが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に設定します。

一般的に、この種の循環tableはモジュールの最上位に配置します。これにより、モジュール内の関数を使用する際に、状況に応じて直接使用するか、クリアしてから使用するかを決定できます。

実際のアプリケーション例を見てみましょう。以下の疑似コードは、オープンソースのマイクロサービス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

    -- 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

local_plugins配列はpluginモジュールのトップレベル変数であることがわかります。load関数の開始時にtableがクリアされ、現在の状況に基づいて新しいプラグインのリストが生成されます。

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)
     -- -- using t for some purposes
    tablepool_release(pool_name, t)
end

tablepoolは、これまでに紹介したいくつかの方法を使用しており、100行未満のコードです。そのため、自分で検索して研究することを強くお勧めします。ここでは、主にその2つのAPIを紹介します。

1つ目はfetchメソッドで、table.newと同じ引数を取りますが、pool_nameが1つ追加されています。プールに空き配列がない場合、fetchはtable.newを呼び出して新しい配列を作成します。

tablepool.fetch(pool_name, narr, nrec)

2つ目はreleaseで、テーブルをプールに戻す関数です。その引数の中で、最後のno_clearは、table.clearを呼び出して配列をクリアするかどうかを設定するために使用されます。

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

これまでに紹介したすべての方法がどのように関連しているかがわかりますか？ただし、このためtablepoolを乱用しないように注意してください。tablepoolは実際のプロジェクトではあまり使用されていません。例えば、Kongでは使用されておらず、APISIXでもそれに関連する呼び出しはわずかです。ほとんどの場合、この層のtablepoolのカプセル化がなくても十分です。

まとめ

OpenRestyにおけるパフォーマンス最適化は難しい分野ですが、ホットなトピックです。今日はtable関連のパフォーマンス最適化のヒントを紹介しました。これが実際のプロジェクトに役立つことを願っています。

最後に、1つ質問を考えてみてください。table関連の最適化技術を使用する前後のパフォーマンスの違いを自分でテストして比較できますか？また、コメントを残して私とコミュニケーションを取ることを歓迎します。あなたの実践や意見を知りたいです。この記事を共有して、より多くの人々が一緒に参加できるようにしてください。