基数木を使った効率的なパスルーティング

背景

次のようなwildcardを含んだpathをフレームワークに頼らず、自前で実装する場合にどうパターンマッチさせるか考えてみます。

• /users/:id
• /articles/:id/comments

単純に考えると正規表現で次のようなパターンを使ってforループで回す、といったものがありますが

• ^/users/[a-zA-Z0-9_]*$
• ^/articles/[a-zA-Z0-9_]*/comments$

一方で次のような課題が生まれてきます。

• pathのリストが増えてくると、正規表現ｘfor文ではスケールしにくい
• /users/:id/favoritesのようなpathにも/users/:idがマッチングしてしまう可能性がある

こういった課題を解決する上で、基数木というデータ構造が適切なので紹介します。

環境

Go v1.20.3

基数木（Radix tree/Patricia tree）とは

基数木は、prefixを共有する文字列を木構造で表現することで、検索や挿入、削除を高速に行えるデータ構造です。

例えば以下のようなpathを基数木で表現すると、

• /abc
• /abc/:id
• /abc/:id/def
• /abc/:id/ghi
• /xyz
• /xyz/vw

次の図のようになります。

Radix Tree Visualization

APIのpathのように、文字列がまとまっている場合はトライ木よりも基数木の方が空間効率が高いのでパフォーマンスが良くなります。

Goで実装

それでは具体的にGo言語で実装してみます。

実装

radix tree

package main

import (
    "net/http"
    "strings"
)

type Route struct {
    Path    string `json:"path"`
    handler http.HandlerFunc
}

type Node struct {
    Part     string  `json:"part"`
    Children []*Node `json:"children"`
    IsWild   bool    `json:"isWild"`
    Route    Route   `json:"route"`
}

func (n *Node) insert(pattern string, route Route) {
    parts := strings.Split(pattern, "/")[1:]

    for _, part := range parts {
        child := n.matchChild(part)
        if child == nil {
            child = &Node{
                Part:   part,
                IsWild: part[0] == ':' || part[0] == '*' || part[0] == '{',
            }
            n.Children = append(n.Children, child)
        }
        n = child
    }

    n.Route = route
}

func (n *Node) search(path string) Route {
    parts := strings.Split(path, "/")[1:]

    for _, part := range parts {
        child := n.matchChild(part)
        if child == nil {
            return Route{}
        }
        n = child
    }

    return n.Route
}

func (n *Node) matchChild(part string) *Node {
    for i := range n.Children {
        if n.Children[i].Part == part || n.Children[i].IsWild {
            return n.Children[i]
        }
    }
    return nil
}

ポイントは以下です。

• Part：/で区切った場合のパスの一部を格納
• Node：基数木のデータ構造を表現するため自己参照を含む構造体
• IsWild：wildcardかどうかの判定。wildcardかどうかはよくある:, *, {があるかで判定
• Route：パスとハンドラの関数を持つ

http server

基数木のデータ構造ができたら実際にハンドラを登録します。

func Index(w http.ResponseWriter, r *http.Request) {
    fmt.Fprint(w, "Welcome!\n")
}

func Hello(w http.ResponseWriter, r *http.Request) {
    name := strings.TrimPrefix(r.URL.Path, "/hello/")
    fmt.Fprintf(w, "Hello, %s!\n", name)
}

func Hello2(w http.ResponseWriter, r *http.Request) {
    name := strings.TrimPrefix(r.URL.Path, "/hello/")
    fmt.Fprintf(w, "Hello2, %s!\n", name)
}

func main() {
    routes := []Route{
        {Path: "/hello", handler: Index},
        {Path: "/hello/:name", handler: Hello},
        {Path: "/hello/:name/foo", handler: Hello2},
        {Path: "/foo", handler: Index},
    }

    tree := &Node{}
    for _, route := range routes {
        tree.insert(route.Path, route)
    }

    http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
        path := r.URL.Path
        route := tree.search(path)

        route.handler(w, r)
    })

    http.ListenAndServe(":8080", nil)
}

上のコードでは

• ハンドラを基数木に登録する
• ルートpath/でリクエストを受けつけてから、r.URL.Pathで生のpathを受け取り、それを前述の基数木ので検索する
• ヒットしたハンドラを実行する

となっています。

動作確認

実際に

• /hello
• /hello/123
• /hello/234/foo

のようなリクエストを投げてみます。

$ curl localhost:8080/hello
Welcome!
$ curl localhost:8080/hello/123
Hello, 123!
$ curl localhost:8080/hello/234/foo
Hello2, 234/foo!

きちんと区別してルーティングできています。

正規表現とのベンチマーク

では正規表現と比較してどの程度パフォーマンスが変わるか確認してみます。

次のようなルーティングを用意し、

• /hello
• /hello/{name}
• /hello/{name}/foo
• /foo
• /foo/bar
• /foo/bar/{name}
• /bar
• /bar/baz
• /bar/baz/{name}
• /bar/baz/{name}/hoge

テストパターンとして以下の４つで検証してみます。

• First: 正規表現で最初に登録した/helloにルーティングする場合
• Mid: 真ん中の/foo/bar/{name}にルーティングする場合
• Last: 最後の/bar/baz/{name}/hogeにルーティングする場合
• Round: 全pathをラウンドロビンでルーティングする場合

結果

次のような結果になりました。

BenchmarkRegexFirst-10          11028405                97.70 ns/op            0 B/op          0 allocs/op
BenchmarkRadixFirst-10          31994204                36.53 ns/op           32 B/op          1 allocs/op
BenchmarkRegexMid-10             3229677               363.4 ns/op             0 B/op          0 allocs/op
BenchmarkRadixMid-10            17497344                67.78 ns/op           64 B/op          1 allocs/op
BenchmarkRegexLast-10            2487745               482.7 ns/op             0 B/op          0 allocs/op
BenchmarkRadixLast-10           12847460                94.01 ns/op           80 B/op          1 allocs/op
BenchmarkRegexRound-10           1506157               791.6 ns/op             0 B/op          0 allocs/op
BenchmarkRadixRound-10          19155417                61.50 ns/op           51 B/op          1 allocs/op

Firstでさえ基数木の方が速く、3~13倍ほど高速でした。
10個程度のルーティングでこの結果なので、数が増えればより基数木の方が良い結果になると考えられます。

その他

サンプルコード

今回のサンプルコードはこちらです。

github.com

フレームワークを使えばいいのでは？

もちろんパフォーマンスや利便性が最適化されたフレームワークがある以上、ルーティングを自前で実装するメリットはあまりありません。

しかし例えば

• wildcardを含む特定のpathを認証のホワイトリストにしたい
• wildcardを含む特定のpathだけCache-Controlを変更したい

のようなユースケースで、フレームワークでは実現できない場合にこのようなやり方を知っていればパフォーマンスを落とすこと無く解決できます。

まとめ

パスルーティングにおいて基数木を使うことで効率的にパターンマッチできることを確認できました。

参考