Apache APISIX はなぜ高速なのか？

Navendu Pottekkat

Navendu Pottekkat

June 12, 2023

Technology

「高速」、「最小レイテンシ」、「究極のパフォーマンス」といった言葉は、Apache APISIX を特徴付けるためによく使われます。私がAPISIXについて尋ねられたときも、常に「高性能なクラウドネイティブAPIゲートウェイ」という答えが含まれます。

パフォーマンスベンチマーク（Kong、Envoy との比較）は、これらの特性が確かに正確であることを裏付けています（自分でテストすることもできます）。

高速、最小レイテンシ、究極のパフォーマンス

テストは、Standard D8s v3（8 vCPU、32 GiBメモリ）上で5000のユニークなルートに対して10回実行されました。

しかし、APISIXはどのようにしてこれを実現しているのでしょうか？

その質問に答えるためには、etcd、ハッシュテーブル、基数木の3つを見る必要があります。

この記事では、APISIXの内部を覗き、これらが何であり、どのように連携してAPISIXが大量のトラフィックを処理しながらピークパフォーマンスを維持しているのかを見ていきます。

etcdを設定センターとして使用

APISIXは、設定を保存および同期するためにetcdを使用します。

etcdは、大規模な分散システムの設定をキーバリューストアとして動作するように設計されています。APISIXは、最初から分散型で高いスケーラビリティを持つことを意図しており、従来のデータベースではなくetcdを使用することでそれを容易にしています。

APISIXアーキテクチャ

APIゲートウェイにとってもう一つの重要な機能は、ダウンタイムやデータ損失を避けるために高可用性を確保することです。これは、etcdの複数のインスタンスをデプロイすることで、フォールトトレラントなクラウドネイティブアーキテクチャを効率的に実現できます。

APISIXは、最小のレイテンシでetcdから設定を読み書きできます。設定ファイルの変更は即座に通知されるため、APISIXはデータベースを頻繁にポーリングする必要がなく、パフォーマンスのオーバーヘッドを追加することなくetcdの更新を監視できます。

このチャートは、etcdが他のデータベースとどのように比較されるかをまとめています。

IPアドレスのためのハッシュテーブル

IPアドレスベースの許可リスト/拒否リストは、APIゲートウェイの一般的なユースケースです。

高性能を実現するために、APISIXはIPアドレスのリストをハッシュテーブルに保存し、リストを反復処理する（O(N)）よりもハッシュテーブルを使用してマッチングを行います（O(1)）。

リスト内のIPアドレスの数が増えると、ハッシュテーブルを使用した保存とマッチングのパフォーマンスへの影響が明らかになります。

内部では、APISIXはlua-resty-ipmatcherライブラリを使用してこの機能を実装しています。以下の例は、このライブラリの使用方法を示しています：

local ipmatcher = require("resty.ipmatcher")
local ip = ipmatcher.new({
    "162.168.46.72",
    "17.172.224.47",
    "216.58.32.170",
})

ngx.say(ip:match("17.172.224.47")) -- true
ngx.say(ip:match("176.24.76.126")) -- false

このライブラリは、ハッシュテーブルであるLuaテーブルを使用しています。IPアドレスはハッシュ化され、テーブルのインデックスとして保存されます。特定のIPアドレスを検索するには、テーブルをインデックスして、それがnilかどうかをテストするだけです。

ハッシュテーブルにIPアドレスを保存

IPアドレスを検索するために、まずハッシュ（インデックス）を計算し、その値をチェックします。それが空でない場合、マッチがあります。これは定数時間O(1)で行われます。

ルーティングのための基数木

データ構造のレッスンに誘導してしまったことをお許しください！しかし、ここからが面白いところです。

APISIXがパフォーマンスを最適化する重要な領域の一つがルートマッチングです。

APISIXは、リクエストのURI、HTTPメソッド、ホスト、その他の情報（ルーターを参照）からルートをマッチングします。そして、これは効率的である必要があります。

前のセクションを読んだ場合、ハッシュアルゴリズムを使用することが明らかな答えでしょう。しかし、ルートマッチングは複数のリクエストが同じルートにマッチする可能性があるため、トリッキーです。

例えば、ルート /api/* がある場合、/api/create と /api/destroy の両方がそのルートにマッチする必要があります。しかし、これはハッシュアルゴリズムでは不可能です。

正規表現は代替の解決策になる可能性があります。ルートは正規表現で設定でき、各リクエストをハードコードする必要なく複数のリクエストにマッチできます。

前の例を取ると、正規表現 /api/[A-Za-z0-9]+ を使用して /api/create と /api/destroy の両方にマッチさせることができます。より複雑な正規表現を使用すれば、より複雑なルートにマッチさせることができます。

しかし、正規表現は遅いです！そして、APISIXは高速であることが知られています。そのため、APISIXは基数木を使用します。基数木は、高速なルックアップに非常に適した圧縮されたプレフィックス木（トライ）です。

簡単な例を見てみましょう。以下の単語があるとします：

  • romane
  • romanus
  • romulus
  • rubens
  • ruber
  • rubicon
  • rubicundus

プレフィックス木は次のように保存されます：

プレフィックス木

ハイライトされたトラバーサルは、単語「rubens」を示しています。

基数木は、ノードが子ノードを1つしか持たない場合に子ノードをマージすることで、プレフィックス木を最適化します。この例のトライは、基数木として次のようになります：

基数木

ハイライトされたトラバーサルは、依然として単語「rubens」を示しています。しかし、木ははるかに小さくなりました！

APISIXでルートを作成すると、APISIXはそれらをこれらの木に保存します。

APISIXは、ルートをマッチングする時間がリクエストのURIの長さにのみ依存し、ルートの数には依存しないため（O(K)、Kはキー/URIの長さ）、完璧に動作できます。

そのため、APISIXは最初に10のルートをマッチングするときと同じ速さで、スケールアップして5000のルートをマッチングするときも同じ速さで動作します。

この粗い例は、APISIXが基数木を使用してルートを保存およびマッチングする方法を示しています：

APISIXでのルートマッチングの粗い例

ハイライトされたトラバーサルは、*がプレフィックスを表すルート /user/* を示しています。したがって、/user/navendu のようなURIはこのルートにマッチします。以下の例のコードは、これらのアイデアをより明確にするはずです。

APISIXは、lua-resty-radixtreeライブラリを使用しています。このライブラリは、Cで実装された基数木であるraxをラップしています。これにより、純粋なLuaでライブラリを実装するよりもパフォーマンスが向上します。

以下の例は、このライブラリの使用方法を示しています：

local radix = require("resty.radixtree")
local rx = radix.new({
    {
        paths = { "/api/*action" },
        metadata = { "metadata /api/action" }
    },
    {
        paths = { "/user/:name" },
        metadata = { "metadata /user/name" },
        methods = { "GET" },
    },
    {
        paths = { "/admin/:name" },
        metadata = { "metadata /admin/name" },
        methods = { "GET", "POST", "PUT" },
        filter_fun = function(vars, opts)
            return vars["arg_access"] == "admin"
        end
    }
})

local opts = {
    matched = {}
}

-- 最初のルートにマッチ
ngx.say(rx:match("/api/create", opts)) -- metadata /api/action
ngx.say("action: ", opts.matched.action) -- action: create

ngx.say(rx:match("/api/destroy", opts)) -- metadata /api/action
ngx.say("action: ", opts.matched.action) -- action: destroy

local opts = {
    method = "GET",
    matched = {}
}

-- 2番目のルートにマッチ
ngx.say(rx:match("/user/bobur", opts)) -- metadata /user/name
ngx.say("name: ", opts.matched.name) -- name: bobur

local opts = {
    method = "POST",
    var = ngx.var,
    matched = {}
}

-- 3番目のルートにマッチ
-- `arg_access`の値は`ngx.var`から取得されます
ngx.say(rx:match("/admin/nicolas", opts)) -- metadata /admin/name
ngx.say("admin name: ", opts.matched.name) -- admin name: nicolas

多数のルートを効率的に管理する能力により、APISIXは多くの大規模プロジェクトで選ばれるAPIゲートウェイとなっています。

内部を覗く

1つの記事でAPISIXの内部動作について説明できることは限られています。

しかし、ここで言及したライブラリとApache APISIXは完全にオープンソースであり、自分で内部を覗いて変更を加えることができるというのが最大の利点です。

そして、APISIXをさらに最適化して最後の一押しのパフォーマンスを得ることができれば、変更をプロジェクトに貢献し、誰もがその恩恵を受けられるようにすることができます。

Tags:
Performance
Traffic Management
etcd