高性能JSONパーサの構築

 (dave.cheney.net)
1 ポイント 投稿者 GN⁺ 2023-11-06 | 1件のコメント | WhatsAppで共有
  • Dave CheneyのGopherCon Singapore 2023での発表は、GoでストリーミングJSONパーサを作りつつ、encoding/jsonと似たAPIを維持しながらスループットを高め、割り当てを減らす設計過程を扱っている
  • JSONには長さマーカーがないため、入力は最後まで読み切る必要があり、性能の下限は少なくともread(N)+parse(N) となる。したがって、バイトやトークンの再訪、コピー、割り当て、ホットパスでの関数呼び出しを減らすことが中核的な制約になる
  • encoding/json.Decoder.Tokenはトークンをinterface{}として返すため便利だが、具体値がヒープへescapeし、トークン数に比例した割り当てを生む。単一の"hello"トークンでも3 allocs/opが発生する
  • pkg/jsonは、入力[]byteのサブスライスを返すNextToken、byteReaderのスライディングウィンドウ、手動インライン化、状態メソッドの直接呼び出し、bounds checkの除去によって、ホットパスのコストを削減する
  • 最終的にpkg/json.Scannerは、バッファが与えられれば割り当てなしでトークン化を行い、Decoder.Tokenはencoding/json.Decoder.Tokenより2〜3倍高速で、割り当ての少ないDecoder.NextTokenは8〜10倍高速な性能を示す

目標と基本制約

  • 目標は、Goパッケージ設計の事例として高性能JSONパーサを作ること
  • 設計目標は3つある
    • 入力全体をメモリに載せないストリーミング処理のサポート
    • encoding/jsonの高水準json.Decoder APIと合理的に互換性を保ちながら、より高いスループットと少ない割り当てを提供すること
    • encoding/json APIに加えて、より効率的な無割り当て、または上限付きのAPIを提供すること
  • 入力全体を先にメモリへバッファリングすると、入力サイズが不明または無限の場合に可用性リスクが生じ、処理前の待ち時間も増える
  • ストリーミング読み取りでは、データが到着し次第すぐ処理でき、読み取りと処理を重ね合わせられる

JSONパースの時間計算量

  • JSONには長さマーカーがないため、どこまで読めばよいかを知るには入力全体を読み切る必要がある
  • JSON配列の1,000番目の要素をパースするには、その前の999個の要素も読んで処理しなければならず、入力処理をスキップすることはできない
  • 性能の下限は入力サイズに比例し、単に読むだけでなくJSON状態機械を通してトークンの開始と終了を見つける必要があるため、最低でもread(N)+parse(N)になる
  • 追加コストを減らす基準は次のとおり
    • Nバイト読んだなら、各バイトは可能な限り1回だけ処理する
    • 同じトークンも1回だけ処理する
    • ScannerやDecoderのホットパスでの関数呼び出し数をO(bytes)ではなくO(tokens)に抑える
    • コピーを減らし、同じバイトを再訪する回数を減らす
    • 割り当てを減らし、ヒープ割り当て、共有データ構造へのアクセス、ロック、キャッシュ競合、GCコストを下げる

トークン化とAPI設計

  • JSONデコーダは大きく2段階に分かれる
    • バイトストリームをJSONトークンストリームへ変換するスキャナまたはトークナイザ
    • JSONトークンストリームをGoオブジェクトへ適用するアンマーシャラ
  • encoding/json.Decoder.Tokenはトークンをinterface{}として返す
    • 文字列はstring、数値はfloat64、真偽値はbool、nullはnil、区切り記号はjson.Delimで表される
    • この方式はトークンの値と型を一緒に表現でき、使いやすい
  • 利便性にはコストが伴う
    • Brad FitzpatrickはToken APIをgarbage factoryと呼んでいる
    • Decoder.Token APIの設計上、各トークンに割り当てられる具体値はヒープへescapeする
    • 割り当て数は入力中のトークン数に縛られる
  • 単一の"hello"トークンのベンチマークでは、encoding/jsonは355ns/op、19.7MB/s、37.0B/op、3.00 allocs/opを示した
  • API設計が割り当てを左右し、割り当ては性能に直接影響しうる

[]byteトークンと暗黙の型情報

  • JSONトークンは先頭文字だけで型を判別できる
    • {, }: オブジェクトの開始と終了
    • [, ]: 配列の開始と終了
    • t: true
    • f: false
    • n: null
    • ": 文字列
    • -, 0~9: 数値
  • pkg/jsonのDecoder.NextToken APIは、入力[]byteをGo値へ変換せず、トークンを表すバイト列を入力から直接サブスライスとして返す
  • 返された[]byteの先頭バイトがトークン型を示す
  • このAPIには制約がある
    • 出力はコピーではなく入力のサブスライスなので、有効期間に制限がある
    • これはbufio.Scanner APIに似ている
    • トークン型や実際の文字列・数値をより扱いやすくするには、上位の抽象化が必要になる

効率的な読み取り: byteReader

  • 従来のio.Reader.Read方式では、データをリーダからバッファへコピーし、このコピー自体にもコストがかかる
  • io.Reader.Readはバッファ管理を呼び出し側に任せる
    • 1バイトずつ読むと、通過済みバイトを保存したり巻き戻したりするための領域が必要になることがある
    • 大きなバッファへ読んでからトークンの開始と終了を探す方式では、トークン末尾がバッファ内にないと、多くの管理作業、コピー、バッファ拡張が必要になる
  • 代替として、Steven SchveighofferのiopipeとPhil Pearlのアイデアに着想を得たbyteReaderを使う
  • byteReaderはio.Readerの上にスライディングウィンドウを提供し、bufio.Readerに似ているが、より効率的なAPIを持つ
    • window()は現在未読のデータウィンドウを返す
    • release(n)はウィンドウ先頭のnバイトを捨てる
    • extend()は下位リーダからさらにデータを読んでウィンドウを拡張する
  • 空白文字検索ベンチマークは、各文字を訪問して空白かどうかだけを調べる基準線であり、複数の入力で約2.04〜2.07GB/sを示す
  • 空白カウンタのサンプルコードはgithub.com/davecheney/whitespaceにある

スキャナ最適化

  • Scanner.Nextは途中の空白をスキップし、ウィンドウ先頭の文字でトークンを判別してから、トークン末尾まで読む
  • 初期のScanner.Next性能は、空白基準線に対して約1/4〜2/5程度だった
    • 例: Scanner/canada 510MB/s、citm_catalog 677MB/s、sample 837MB/s
  • 最初の最適化は、s.offsetフィールド更新をローカル変数offsetへ置き換えることだった
    • s.offsetは関数の入口と出口で0なので、内部での変更は外部から見えない
    • ローカル変数を使うことで、コンパイラは一時メモリ書き込みを避けられる
    • citm_catalogは2.52msから1.80msへ28.46%減少し、sampleは828µsから528µsへ36.24%減少した
  • 入力ごとに効果が異なる理由は、空白数の違いにある
    • canadaの空白は33個しかない
    • citmでは空白が1,227,563個ある
  • 2つ目の最適化は、Scanner.tokenをScanner.Nextへ手動インライン化することだった
    • Goコンパイラは、for文や関数の複雑さのため、Scanner.token、parseString、parseNumber、Scanner.Nextなどを自動でインライン化できない
    • Scanner.NextとScanner.tokenは入力トークンごとに呼ばれるため、トークンあたり2回の関数呼び出しコストが発生する
  • 手動インライン化後、スループットは9〜24%改善した
    • canadaは512MB/sから642MB/sへ24.50%増加
    • citm_catalogは960MB/sから1105MB/sへ15.16%増加
    • sampleは1.33GB/sから1.46GB/sへ9.11%増加
  • 最適化の効果は2点にまとめられる
    • s.offset更新をバイトごと1回からトークンごと1回へ減らした
    • ホットパスでの関数呼び出しを避けると、性能が改善しうる

検証とDecoder.NextToken

  • スキャナだけでもトークン分割はできるが、完全なJSON処理には状態検証が必要になる
  • JSONは状態機械であり、現在のトークンに応じて次に来られるトークンが制限される
    • たとえば{、"username"を読んだ後に有効なのは:だけである
  • Decoder.NextTokenはScanner.Nextの上に状態ロジックを重ね、トークン列が妥当かを確認する
  • 状態は、値、オブジェクトキー文字列、オブジェクトのコロン、オブジェクト値、オブジェクトのカンマ、配列値、配列のカンマ、終了状態などに分かれる
  • 初期の検証実装でも、pkg/jsonはencoding/jsonより8〜10倍高速な結果を示した
    • canada: pkg/json 399MB/s、encoding/json 34.6MB/s
    • citm_catalog: pkg/json 713MB/s、encoding/json 87.1MB/s
    • sample: pkg/json 1.23GB/s、encoding/json 216MB/s

状態遷移の最適化

  • Decoder.NextTokenの中心にはswitch文がある
  • 一般的なswitchは一連のif文のように実装されることがあり、長い分岐列が命令ストリームを分断し、CPUの分岐予測器に負荷をかける
  • 状態値から状態メソッドを見つけるためにテーブルを使う方法もあるが、例の実装は初期化ループのためコンパイルできない
  • その代わりにGoのmethod expressionを使い、d.stateには状態列挙値ではなくメソッドそのものを直接保存する
    • Decoder.NextTokenはreturn d.state(d, tok)のように現在の状態メソッドを直接呼び出す
  • このcomputed goto方式だけでは、性能改善は大きくない
    • 一部の入力ではほとんど変化がなく、twitter、code、exampleではわずかに遅くなる
    • sampleでは1.15%高速化した
  • この変更は、次の最適化であるアウトライニングを可能にした

アウトライニングとbounds checkの除去

  • アウトライニング後のDecoder.NextTokenはreturn d.state(d)だけを行い、各状態メソッドが直接d.scanner.Next()を呼び出す
  • tokを状態メソッド引数として渡さないため、呼び出しスタック上の3 wordsを削減できる
  • len(tok) < 1チェックとswitch tok[0]が同じ関数内に入ることで、bounds checkの除去が可能になる
    • 以前はlen(tok)チェックがDecoder.NextTokenにあり、状態メソッドはメソッド式として呼ばれてインライン化されなかった
    • そのため、状態メソッド内のtok[0]にはbounds checkが必要だった
    • 同じ関数内で長さチェックを行えば、コンパイラはtokの長さが最低1であることを証明できる
  • Decoder.NextToken自体も単純になり、インライン化可能になる
    • 呼び出し側にはdec.NextToken()ではなく、実質的に現在の状態メソッドを直接呼んでいるように見える
    • 関数呼び出しコストが除去される

最終ベンチマーク結果

  • 最下層のpkg/json.Scannerは、数KBのバッファが与えられれば無割り当てストリーミングトークン化を行う
    • canada: 638.78MB/s、0 B/op、0 allocs/op
    • citm_catalog: 1110.51MB/s、0 B/op、0 allocs/op
    • sample: 1471.01MB/s、0 B/op、0 allocs/op
  • pkg/json.Decoder.Tokenはencoding/json.Decoder.Tokenより2〜3倍高速
    • canada: 101.98MB/s vs 33.19MB/s
    • citm_catalog: 333.23MB/s vs 82.71MB/s
    • sample: 788.59MB/s vs 209.12MB/s
  • pkg/json.Decoder.NextTokenは割り当てが大幅に少なく、8〜10倍高速
    • canada: 466.52MB/s、136 B/op、3 allocs/op vs 34.42MB/s、17,740,399 B/op、889,106 allocs/op
    • citm_catalog: 798.58MB/s、136 B/op、3 allocs/op vs 86.08MB/s、5,661,597 B/op、324,692 allocs/op
    • sample: 1346.85MB/s、1144 B/op、9 allocs/op vs 217.44MB/s、723,781 B/op、26,095 allocs/op
  • 最も高水準のAPIでは、pkg/jsonはencoding/jsonと同じ方式でGoオブジェクトにunmarshalできる
    • canada: 82.08MB/s vs 58.70MB/s
    • citm_catalog: 215.66MB/s vs 104.00MB/s
    • sample: 615.99MB/s vs 128.04MB/s
  • 発表リンクはdave.cheney.net/paste/gophercon-sg-2023.html、コードはgithub.com/pkg/jsonにある

設計から得られるテーマ

  • 割り当ては性能に影響する

    • GCが高速に割り当てを行い効率よく回収できても、割り当てないほうが常に速い
    • API設計によって割り当てをなくせる
    • このパッケージの速度向上の大半は割り当て削減から生まれている
    • ヒープ割り当て経路やGCサイクルに使われなかった時間がスキャンに使われる
    • encoding/json.Decoder APIはprimitive値をinterface{}として返すため、割り当てを必要とする
    • 値はヒープへescapeし、実質的にその値へのポインタになる
    • データ処理では、割り当てがアルゴリズム中で最大の性能コストになることがある
    • バイトあたりのコストとトークンあたりのコストを注意深く下げることが、2番目に大きい性能改善要因だった
    • バイトごとの関数呼び出しをトークンごとの関数呼び出しへ変える方向が重要である
    • encoding/jsonがAPIのために遅くなりうるという仮説から出発し、別のAPIを受け入れられるなら、一部のunmarshal経路で2〜3倍、トークン化では8〜10倍の性能が得られる

関連記事

1件のコメント

 
GN⁺ 2023-11-06
Hacker News の意見

  • かなり良さそう。キャリアの中で JSON パーサーはもう作りすぎるほど作ってきたけれど、合理的で高速な JSON パーサーをどう設計するかを段階的に示してくれる参考資料があるのは本当にありがたい。
    ただし JSON には明示的な トークナイザーが必ずしも必要ではない。トークンという概念をなくして、パースとトークン化を完全に一体化できる。普通はそうするし、全体としてより単純になる。
    ECMAScript のような言語ではずっと難しい。アロー関数のように、括弧式構文の部分集合に見えて、=> が出てくるかどうかで確定するケースがあり、任意に長い先読みが必要になることがあるからだ。

    • キャリアの中で「JSON パーサーを作りすぎた」って、いったいどんな仕事をしていたらそうなるのか気になる。

  • 追いながら読むのに良い記事で、自分で実装するならこうすればよい、という流れがよくまとまっている。
    本番環境で純粋な性能を狙うなら、Daniel Lemire の https://github.com/simdjson/simdjson も見る価値がある。Go への移植である MinIO の https://github.com/minio/simdjson-go もある。

    • JSON の形が常に同じなら、汎用 JSON パーサーよりうまくやれる可能性もある。
    • 以前、複数の JSON パーサーの性能を比較したとき、SIMD ベースのパーサーは期待より残念なくらい遅いと感じた。
    • Go で最速の JSON ライブラリは、TikTok の背後にいる会社が作ったものだ。
    • simdjson はかなり前から最速の座にはいない。

  • 高速な JSON パーサーを作って学んだことは、言語ごとの特性がかなり混ざっているが、一般化するとこうなる。
    トークン化では ヒープ割り当てを避けるべき。トークナイザーはスタックに割り当てられる構造体を返すか、トークンの開始位置・長さ・型オフセットなどを詰め込んだ int64 トークンを返す関数にするのがよい。
    パースでもヒープ割り当てを避け、バッファをスライスして使いたいクライアントのために getString(key String) のようなインターフェースをサポートできる。
    コンパイル時点でフィールドが分かっているオブジェクトへデシリアライズする場合、文字列値を比較する前に、たいていはキー長を基準にした switch を生成する。
    JSON を大量に処理するデータパイプラインでは、JSON ライブラリの選択だけで 3〜10倍の性能差が出ることがあったし、主要なパーサーはおおむねオブジェクトを割り当てようとする。
    シリアライズ・デシリアライズするクラスがコンパイル時点で分かっているなら Java の Jackson はかなり優秀だが、慎重なコーディングとプロファイリングでさらに 2 倍程度まで引き上げられる。
    逆に任意の JSON を処理するなら、主流のパーサーは多くの割り当てをしようとするため、自前のより踏み込んだパーサーならそれを避けられ、毎秒数千〜数百万オブジェクトを処理する場面では性能上のメリットが非常に大きい。

  • 似たアプローチで GraphQL トークナイザーとパーサーを作った。これもメモリ割り当てがなく、かなり速い。コードが気になるなら https://github.com/wundergraph/graphql-go-tools を見るとよい。

    • 私の怪作も見る価値があるかもしれない: https://github.com/graph-guard/gqlscan
      このテーマで発表もしたが、残念ながら録画はされなかった。Go で限界まで引き出そうとして、ほとんど狂いそうになった :D
    • すべてのクエリを事前に知っている 許可リストベースの GQL サーバーでは、これがどれほど大きな問題なのか気になる。AST のパース結果をキャッシュしたり覚えておいたりできるので、コンテナ起動後の数分間だけ性能問題になるのではないかと思う。
      それとも別の形でも影響するのだろうか。

  • n2[1] で高速なトークナイザーが必要で、同じ ゴミ生成器問題にぶつかった。基本的には json.Delim のような定数トークン集合と、割り当てを引き起こす文字列が混ざる問題だった。
    かなり良いと思っている解決策は、トークナイザーをある T に対してジェネリックにし、バイトスライスを T に変える関数を受け取って、文字列の代わりに T を使うことだ。
    こうすれば呼び出し側がより効率的な表現、たとえば割り当ての少ない表現を持っているときにそれを提供でき、同時に単体テストでは気軽に恒等関数を使ってトークナイザーをテストできる。
    ある意味ではビルド時にトークナイザーとパーサーを融合するのに似ているが、ジェネリクスのおかげでトークナイザーがパーサー側の表現を知らなくても階層を保てる。
    [1] https://github.com/evmar/n2

  • より良い API 設計で標準ライブラリより改善することは可能だが、完全なストリーミングパーサーを作りつつ、エラーを見つける前に構造体を半分埋めた状態で途中離脱しないようにするのは、実際には難しい。標準ライブラリもこれを明示的な設計上の制約として置いているように見える。

  • 何か見落としているのかもしれないが、筆者は「ストリーミング」パーサーを作ったと繰り返しながら、それが実際に何を意味するのか説明していない。
    特に「ハッシュテーブル」で重複キーをどう扱ったのか説明がない。重複キーが出たらシンクコードを 2 回呼ぶのか、「ハッシュテーブル」全体を読み終えるまで待ってからシンクコードを呼ぶのか気になる。
    私の考えでは、JSON は階層構造で、長さを事前に分からず、何より 重複キーがあるため、本質的にストリーミングに向いていない。
    JSON の一部のサブセットをよりストリーミング向きにすることはできるだろうが、それならわざわざ JSON を直す理由はない。解決策が JSON を変えることなら、そもそも JSON ではない別の形式のほうがよいと思う。

  • Phil Pearl に触れているのがうれしい。
    https://github.com/bytedance/sonic も見る価値がある。

  • 大きすぎてインライン化されなかった関数について、「本当にこの関数は インライン化せよ」と言う方法がないのは意外だ。
    基本的な空白文字のカウント・検索処理は SIMD でベクトル化すればずっと速くなりそうだが、筆者の範囲外だというのは理解できる。

    • 当然、強制インライン化は可能だ。

  • 「入力全体をメモリ上に置けると期待するのは非現実的だ」という主張は、ほとんどのアプリケーションには当てはまらない。

    • ほとんどのアプリケーションはネットワークから JSON を読み、それはストリームだ。JSON が比較的小さくても、リクエスト全体をメモリにバッファリングしていじり回すと、レイテンシが大きく増える。
    • その通りだが、大きなデータセットに対して ETL 的な変換をしなければならないアプリケーションでは、ストリーミングはものすごく有用な戦略だ。
      Go がその作業に合った道具ではないと言うこともできるだろうが、こういう最適化をすればできない理由はないと思う。
    • ライブラリを作るなら、制限を明示するか、ストリーミングをサポートすべきだ。
      ギガバイト単位の JSON データを流し込んだことがあるので、ストリーミングパーサーはありがたい。さらに、ストリーミングをサポートしているということは、作者が複数のユースケースを理解しており、エンジニアリングをよりうまく行っているというサインでもある。
      メモリが安くてほぼ無料なのは理論上だけで、現実にはそうではない。
    • 「ディスクに収まる」程度で満足できるなら、mmap() も選択肢になり得るのでは？ 本当にストリーミングが必要な場合、たとえば単一の JSON ファイルから取引やジョブのストリームのように先頭側のデータを早めに処理したいケースは別だ。
    • HTTP リクエストボディも入力の一部と見るのか？