遅いッ！遅すぎるッ！Java の正規表現のお話。

Java

こんにちは、ミドルウェア開発チームの青木です。

先日、アプリケーションサーバーが応答を返さなくなるトラブルに遭遇しました。 今回はその時のトラブルの原因と対策の顛末についてお話しようと思います。

現象

アプリケーションサーバーが突如応答を返さなくなりました。 現象が発生したアプリケーションサーバーのスタックトレースを見ると、あるスレッドの先頭が上記のようになっていました。

"qtp258153142-514386" prio=10 tid=0x00007f40b8dbf000 nid=0x7b4e runnable [0x00007f415ccb0000]
   java.lang.Thread.State: RUNNABLE
        at java.util.regex.Pattern$Loop.match(Pattern.java:4692)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
        at java.util.regex.Pattern$BranchConn.match(Pattern.java:4466)
        at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4502)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4683)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
        at java.util.regex.Pattern$BranchConn.match(Pattern.java:4466)
        at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4502)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4683)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
        at java.util.regex.Pattern$BranchConn.match(Pattern.java:4466)
        ...

どうやら正規表現のマッチ処理に時間がかかっており、現象から見るとおそらく数百秒以上経っても処理が終了していないようです。

調査

コードを追ったところ、メールアドレスの正規表現のマッチ処理で時間がかかっていました。ただ、メールアドレスの正規表現のパターンが遅くなる場合があるのは既知でした。下記はサイボウズ・ラボ中谷による解説記事です。

メールアドレスの正規表現がめちゃめちゃ遅くなることがある件について http://d.hatena.ne.jp/n_shuyo/20111020/regular_expression

サイボウズでは既に上記を踏まえ、遅くならない正規表現を書いていましたが、今回は別の現象を踏んでしまったみたいです。

今回問題になった正規表現は、簡単にするとこのような感じの正規表現でした。メールアドレスにマッチさせることを目的とした正規表現で、後半は今回は無用のため省略しています。

(\\w|[-\\%_+!/=.]){1,64}@

\w は "A word character", つまり単語に使える文字一覧のエイリアスです。よってこの正規表現は、「単語に使える文字か、もしくはいくつかの指定された記号が 1 文字以上 64 文字以内で、最後に @ マークがくる文字列にマッチする」を意味します。この正規表現のどこかに、猛烈に時間を消費するパターンが潜んでいます。

解明

結論から言うと、今回の現象の原因はアンダースコアでした。

たとえば、下記の Java コードは実行におよそ 70 秒かかります。

Pattern pattern = Pattern.compile("(\\w|_){1,64}@");
pattern.matcher("______________________________").matches();

僕が手元で行った実験の結果から明らかなように、アンダースコアの個数に応じて時間が二倍ずつ伸びています。横軸はアンダースコアで構成された文字列の長さで、縦軸はマッチにかかった時間(ミリ秒)、対数軸です。 文字列長とマッチ時間の関係

調べたところ、\w 、つまり単語として使える文字一覧には、A-Za-z0-9 だけでなく、アンダースコアも含まれていることがわかりました(参考)。つまり、アンダースコア OR アンダースコアのような正規表現になってしまっていたのです。僕は A-Za-z0-9 しか使えないものだと勘違いしており、後半の記号部のところにアンダースコアを入れてしまっていました。

その結果、正規表現エンジンはアンダースコア一文字ごとに内部で管理しているパターンが二倍になり、数十文字もあれば膨大な数のパターンが生成され、今回の現象を引き起こしてしまったのでしょう。

対策

対策は簡単です。OR の後半から、アンダースコアを取り除きました。

これだけで十分な解決になるのですが、実は、もうひとつ取れる対策があります。

改めて今回の現象を振り返ってみましょう。 まず今回の現象を引き起こした原因としては、僕の勘違いにより同じ文字を OR でつないでしまったというのもあるのですが、Java ライブラリの正規表現エンジンがバックトラッキングを用いているというのも一つの原因と言えます。

バックトラッキングを用いた正規表現エンジンはほとんどの場合にはうまく動きますが、稀に今回のようにマッチに膨大な時間がかかってしまうことがあります。今回の件も、途中で紹介したメールアドレスの正規表現が遅くなる件もバックトラッキングによる落とし穴です。

では、Java で使えるバックトラッキングを用いない正規表現エンジンはあるのでしょうか？

Google 製の RE2/J はその要望を満たします。

このライブラリはマッチにかかる時間が入力文字列に対して線形で済むことを保証してくれており、今回のようにマッチ時間が倍々で増えていくことが無いとしています。

早速実験してみましょう。

com.google.re2j.Pattern pattern = com.google.re2j.Pattern.compile("(\\w|_){1,64}@");
pattern.matcher("______________________________").matches();

上記コードが RE2/J を使ったコードで、1ms 以下でマッチが終了します。Java の正規表現ライブラリではおよそ 70 秒程度です。

このライブラリの素晴らしいところは Java の正規表現ライブラリと同等のインターフェースを保っているところです。パッケージ名さえ変更すれば RE2/J への移植が完了するでしょう。我々は、短期的には前者の方法(アンダースコアを取り除く)を取り、長期的には RE2/J へ移行することを目的として部分的に取り込み始めているところです。

宣伝

サイボウズ・ラボが開催している、サイボウズ・ラボユース出身の新屋良磨さん、鈴木勇介さんが著者に名を連ねてる本、正規表現技術入門が好評を博しているようです！

追記: 同書著者の鈴木勇介さんの名前が漏れておりましたので追記しました。 新屋さんご指摘ありがとうございました。

正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

僕も今回の件を受けて読みましたが、今回のような落とし穴について1章まるまる割いて深く記してあります。今回のトラブルについても、先に本書を読んでおけば回避できただろうという内容でした。正規表現の概念や実装が凝縮された濃厚な一冊です。

まとめ

正規表現はループや分岐が見えないので計算量を想定しにくいですが、正規表現を書く際は最悪のケースを考えて注意深く書く必要がある、ということです。

また、Google の RE2/J はサイボウズ社内ではまだ評価中ではありますが、README の下記文言にあるとおりならば RE2/J を使うだけで今回のような問題は再発しなくなると思われます。

In the worst case, the java.util.regex matcher may run forever, or exceed the available stack space and fail; this will never happen with RE2/J.

意訳: 最悪のケースでは java.util.regex のマッチャーは実行が止まらなかったりスタックを消費し尽くして失敗したりしますが、RE2/J ではそのようなことは決して起こりえません。

素晴らしいですね。RE2/J は非公式ライブラリとのことですが、今後も継続してメンテナンスされることを望みます。

それでは良い正規表現ライフを！

追記 2015/05/13 09:43

RE2/J は後方参照をサポートしておらず、そのため、マッチ時間が線形時間で済むことを保証しています。

cybozuinsideout

関連記事
このエントリーをはてなブックマークに追加