Mercari Engineering Blog

We're the software engineers behind Mercari. Check out our blog to see the tech that powers our marketplace.

Google Cloud Spannerのセッションリークを静的解析で防ぐ

この記事はMERPAY TECH OPENNESS MONTHの16日目の記事です。

メルペイ エキスパートチームの@tenntennです。 @sinmetalの記事でも紹介がされていたように、メルペイではGoogle Cloud Spannerを用いて開発しています。 Google Cloud Spannerはまだまだ世界的にもノウハウが乏しい状況です。そのため、メルペイにおいても各開発者が学んだノウハウをGo Fridayなどを通して社内で共有しながら開発を進めています。

社内でノウハウを共有する中で、うっかりミスをしがちでかつそのミスによってサービスに大きく影響を与えるものがいくつか出てきました。例えば、Google Cloud Spannerのセッションを閉じ忘れることによるセッションリークの問題は、うっかりミスをしがちですがサービスに大きな影響を与えかねません。

このような問題を発見するためにzaganeというツールを開発しました。zaganeは静的解析を行い、Cloud Client Library for Goを利用している時に起こりがちなコードのミスをコミットする前に発見できます。

この記事ではzaganeで提供している機能のうちの1つである、セッションリークを発見する方法について解説します。ここで紹介するアルゴリズムはGoogle Cloud Spanner以外にも応用の効くもので、ファイルの閉じ忘れの発見などにも用いることが可能でしょう。

セッションリークを起こすコード

セッションリークは、以下のように*spanner.RowIteratorの値を生成したあとに、StopメソッドDoメソッドを呼ばなかった場合に発生します。

iter := client.Single().Query(ctx, stmt)
for {
    row, err := iter.Next()
    // (略)
}

例えば、上記のコードは以下のように修正するべきです。

iter := client.Single().Query(ctx, stmt)
defer iter.Stop()
for {
    row, err := iter.Next()
    // (略)
}

Stopメソッド呼び出してイテレータを明示的に停止させるか、内部でStopメソッドを呼び出すDoメソッドを用いる必要があります。

deferを用いてStopメソッドを呼び出す場合だけを検出することは簡単です。しかし、実際にはdeferによって関数の出口にStopメソッドの呼び出しが仕掛けられている場合だけではなく、ifで分岐していたり、forの中にswitchがあってそのケースの1つで呼び出されていたりします。

このような場合に文字列としてソースコードを扱っていると検出は非常に難しく、事実上不可能でしょう。そこでソースコードから構文上の構造を表現した抽象構文木(Abstract Syntax Tree: AST)や型情報を取り出し、静的解析で検出することになります。今回のケースでは抽象構文木や型情報から静的単一代入(Static Single Assign: SSA)という形式に変換して解析を行うと比較的簡単に検出できます。

静的単一代入形式を用いた解析

静的単一代入をざっくり解説すると変数への代入を1度だけに制限した形式です。例えば、以下のようなコードがあった場合、変数nn += 10によって再代入されています。

n := 10
n += 10

静的単一代入形式はこれを以下のように代入の度に新しい変数を用意することによって、代入を1回に制限するというものです。

n0 := 10
n1 := n0 + 10

こうすることによって変数の値がコードの中で変化することがなくなるため、解析がしやすくなります。

静的単一代入形式はコンパイラの中間表現として最適化を容易にするために用いられます。実際にGoのコンパイラにおいても静的単一代入形式を用いた最適化が行われています(執筆当時の最新バージョンであるGo 1.12.5を使って確認しています)。

Goでは標準パッケージにて構文解析や型チェックの機能を提供しています。それに加え、準標準パッケージでは静的単一代入形式に関する機能を提供しています。

golang.org/x/tools/go/ssaパッケージ(以下go/ssaパッケージ)は、静的解析用に静的単一代入形式に関する機能を提供しています。なお、Goのコンパイラで用いられている静的単一代入形式とは異なるため混同しないよう注意が必要です。あくまでこのパッケージは静的解析ツールを開発するために用いられます。

go/ssaパッケージで定義されている静的単一代入形式は、関数を基本ブロックという単位で構成しています。基本ブロックは複数の命令で構成され、命令は複数のオペランドを持ちます。

関数はifswitchなどによる分岐で複数の基本ブロックに分割されます。例えば、以下のようなコードを考えます。

func f() {
    n := 10
    if n < 10 {
        println("n < 10")
    } else {
        println("n >= 10")
    }
}

関数fgo/ssaパッケージを用いて静的単一代入形式に変換すると下図のような基本ブロックに分割されます。例えばBlock 0は、10 < 10を表す*ssa.BinOp型の値とifを表す*ssa.If型の値の2つの命令で構成されています。なお、変数nは定数値の10が代入されており、変化することがありません。そのため、静的単一代入形式では変数nは定数値10と同様に扱われ、n := 10n < 10の2つは10 < 10という1つの命令にまとめられます。

ifによって分岐されるため、条件式n < 10が成り立つ場合はBlock 1に、そうでない場合Block 3に遷移します。Block 1とBlock 3はともに関数呼び出しを表す*ssa.Call型の値、他のブロックへの遷移を表す*ssa.Jump型の値の命令で構成されています。

それらの2つの基本ブロックから遷移されるBlock 2は関数のリターンを表す*ssa.Return型の値の命令で構成されています。関数fは明示的なreturnは持ちませんが、go/ssaパッケージの静的単一代入形式では必ずリターンを持つ基本ブロックが存在します。

f:id:uedatakuya275:20190610085220p:plain:w600
関数fを静的単一代入で表したもの

図を見ても分かるように、静的単一代入形式で表現された関数は基本ブロックをノードとし、ブロック間の遷移をエッジとした有向グラフとして表すことができます。静的単一代入形式を使った静的解析では、この有向グラフを探索しコードの検証を行います。

セッションリークを見つける

セッションリークの発生を検証するということは、言い換えればStopメソッドまたはDoメソッドが呼び出されていない*spanner.RowIterator型の値を見つけることと言えます。

go/ssaパッケージでは値を*ssa.Value型の値で表します。1つの値に着目した場合、静的単一代入形式で表現しているため、途中で*ssa.Value型の値で表されるGoのソースコード上の値が変更されることはありません。そのため、単に*spanner.RowIterator型の値に対応した*ssa.Valueの値に着目し、その値のStopメソッドかDoメソッドが必ず呼ばれているかどうかを調べれば良いことになります。

任意のメソッドがどんな分岐を経ても必ず呼ばれている事象を有向グラフに当てはめると、ある基本ブロックから*ssa.Returnを持つ基本ブロックにたどり着くまでパスに、必ずそのメソッドを呼び出している命令を持つ基本ブロックが存在しているということになります。

これを静的単一代入形式を一旦忘れて有向グラフで考えると、以下のような図で表すことができます。ここで黒いノードを開始ノード、二重丸ノードを終了ノードとします。このグラフの場合、開始ノードから終了ノードに向かうパスは始→0→1→終と始→0→1→3→終、始→0→2→3→終3つが存在します。

f:id:uedatakuya275:20190610085745p:plain:w600
基本ブロックのフローを有向グラフで表現したもの

ここでノード1に次のような星マークをつけてみます。

f:id:uedatakuya275:20190610085859p:plain:w600
ノードに星マークをつけた有向グラフ

そして、"開始ノードから終了ノードへ向かうすべてのパスで星マークのついたノードを通る"という命題を考えます。このグラフでは始→0→2→3のパスは星マークをついたノードを通らないので、この命題は偽になります。

次に以下のようにノード2にも星マークをつけた場合を考えます。この場合であれば、開始ノードから終了ノードへのすべてのパスで星マークがついたノードを通ることになり、先程の命題は真になります。

f:id:uedatakuya275:20190610090030p:plain:w600
2つのノードに星マークをつけた場合

さて、このグラフの問題がGoogle Cloud Spannerのセッションリークの問題とどう関係するのでしょうか?星マークのついたノードをStopメソッドまたはDoメソッドを呼び出している静的単一代入形式の基本ブロックだと考えると、実はセッションリークの問題は上述したグラフの問題として考えることが可能です。

筆者はツールを開発するにあたって、今回のような問題をグラフの問題に変換できれば、よく知られたアルゴリズムが使え、比較的簡単にセッションリークが起こる可能性があるか検証ができると考えていました。しかし、実際にはそう簡単にはいきませんでした。Goのソースコードには、forなどの繰り返し処理も含まれます。繰り返しがある場合、閉路が生まれてしまいます。

f:id:uedatakuya275:20190610090133p:plain:w600
閉路を持つ有向グラフ

このようなグラフではすべてのパスで星マークのノードを通るかどうか簡単に判断することができません。困った筆者はメルカリ競技プログラミング部の@johnielに相談しました(補足:メルカリには部活動という制度が存在し、競技プログラミングの集いがあります)。

@johnielに、問題の捉え方を変えて、星マークのついたノードをグラフから取り除き、開始ノードから終了ノードにたどりつけるパスの存在を調べればよいとアドバイスをもらいました。

つまり、グラフを以下のような状態にすれば良いということです。こうすると、星マークのついたノードをグラフから取り除いても、始→0→2→終のパスが存在してしまいます。このようなグラフに対応するコードであればStopメソッドやDoメソッドを呼ばない経路が存在し、セッションリークの可能性があるということになります。

f:id:uedatakuya275:20190610090251p:plain:w600
星マークのノードを取り除いた有向グラフ

まとめ

本稿では、zaganeというGoogle Cloud Spannerを用いて開発する場合に頻繁にミスをするケースを検出するツールの実装について解説しました。実際にzaganeを使ってメルペイ社内のソースコードを解析すると、いくつかセッションリークを起こしかねない部分を見つけることができました。どれもすぐにサービスに大きな影響を与えるほど深刻なものではありませんでしたが、早期に発見できて良かったです。

ここで紹介した方法はGoogle Cloud Spannerのセッションリークを検出すること以外にも応用できるでしょう。興味のある方は、ぜひzaganeのソースコードを読んでみてください。