貳佰伍拾陸夜日記

bullet-scala: N+1クエリ問題を回避する

scala

Scala関西 Summit 2015での発表で触れていたN+1クエリ問題をなんとかするためのライブラリを公開した.

発表は以下のもので, ここでは「関係モナド」という名前で紹介していたけれど, これは口頭でも説明したように便宜上てきとーにつけた名前であって, とくにそういう名前のよく知られたモナドがあるというわけでもなければ, そもそもモナドであるかどうかはあまり本質的ではない. この発表のあとに, Rails (Active Record)でのbulletのようにN+1問題の検出をScalaでやる方法はないだろうか, と言っている人がいたので, そういうものを探していて辿りつけるとよかろうということで, bullet-scalaという名前にした. もちろんN+1問題の検出のためのライブラリというわけではないし, 動的に検出するのではなく原理的に問題が発生しないようにするものなので, 思想は全く異なる.

どういうものか

英語で書いたREADMEの説明を和訳したものを載せておこう.

問題

CarとEngineというクラスがあって, Carが持つEngineが型クラスのメソッドtoEngineによって解決できるとしよう.

type CarId = Long
type EngineId = Long

case class Car(id: CarId)
case class Engine(id: EngineId, carId: CarId)

implicit class CarRelation(val car: Car) extends AnyVal {
  def toEngine: Option[Engine] = ...
}

toEngineの実装をDBクエリをともなうリポジトリクラスを用いて実装するのは極めて普通のことだろう.

implicit class CarRelation(val car: Car) extends AnyVal {
  def toEngine: Option[Engine] = EngineRepository.findByCarId(car.id)
}

val db = ...
object EngineRepository {
  def findByCarId(carId: CarId): Option[Engine] = db.run {
    sql"SELECT * FROM engine WHERE car_id = $carId LIMIT 1".as[Engine]
  }.headOption
}

ひとつのCarのインスタンスからEngineのインスタンスを解決するなら, とくになんの問題もない. この場合, 内部的にひとつのSELECTクエリが実行される.

val car: Car = Car(1234L)
val engine: Option[Engine] = car.toEngine
// SELECT * FROM engine WHERE car_id = 1234 LIMIT 1

もし複数のCarインスタンスがあって, それらの持つEngineインスタンスを得ようとおもうと, こう書いたらよさそうに思える.

val cars: Seq[Car] = Seq(Car(1L), Car(2L), Car(3L), ...)
val engines: Seq[Engine] = cars.map(_.toEngine).flatten
// SELECT * FROM engine WHERE car_id = 1 LIMIT 1
// SELECT * FROM engine WHERE car_id = 2 LIMIT 1
// SELECT * FROM engine WHERE car_id = 3 LIMIT 1
// ...

これは確かに動く. けれど, SELECTクエリがcarsの各idごとに実行されてしまう. carsの要素数がある程度以上になってくるとこれはパフォーマンス上の問題となる.

この問題を解決するひとつの方法は, あらかじめテーブルをJOINしておくこと. 複数のCarをDBのcarテーブルから引いてきてインスタンス化するときに, engineテーブルもINNER JOINなどしておけばよいだろう. これはよく知られた解決方法ではあるものの, 最善ではない. もしEngineの他にもWheel, Bumper, DoorなどをCarが持っているとしたら, これらもすべてJOINする? けれど, これらすべてが(Carを使うときに)常に必要というわけでもないだろう. だとしたら, これらのうち必要なものの組み合わせのみJOINしながらCarをインスタンス化するメソッドをいちいち用意してまわる?

理想的には, 上の例の最後の式で, 単一のSELECTクエリになってくれると嬉しい.

val engines: Seq[Engine] = cars.map(_.toEngine).flatten
// SELECT * FROM engine WHERE car_id IN (1, 2, 3, ...)

こんなことできるの? できる. そう, Scalaならね!

bullet-scalaによる解決方法

toEngineメソッドの返り値をあるモナドにするだけでよい. このモナドは, CarからEngineを解決する方法を指定するHasA[Car, Engine]を, HasA.Monadicに渡すことで作られる.

import com.github.tarao.bullet.HasA

implicit class CarRelation(val car: Car) extends AnyVal {
  def toEngine = HasA.Monadic(car, hasEngine)
}
val hasEngine: HasA[Car, Engine] = ...

toEngineの使い方はほとんど変わらない. 返り値を受け取る変数の型(今回はOption[Engine]やSeq[Engine])を省略できない点と, もはやflattenを呼ぶ必要がない点にだけ注意する.

import com.github.tarao.bullet.Implicits._

val car: Car = ...
val engine: Option[Engine] = car.toEngine

val cars: Seq[Car] = ...
val engines: Seq[Engine] = cars.map(_.toEngine)

hasEngineの実装では, 複数のCarからEngineをひとつのクエリで解決する. このために, HasA[Car, Engine]のmap()というSeq[Car] => Seq[Engine]な型のメソッドを実装する. 実装は次のような具合になる.

val hasEngine: HasA[Car, Engine] = new HasA[Car, Engine] {
  def map(cars: Seq[Car]): Seq[Engine] = db.run {
    sql"SELECT * FROM engine WHERE car_id IN (${cars.map(_.id)})".as[Engine]
  }
}

このmap()メソッドはOption[Engine]を解決するときにも, Seq[Engine]を解決するときにも使用される. どちらの場合も, 結果的にそれぞれひとつのSELECT-WHERE-INクエリが実行されることになる.

val car: Car = Car(1234L)
val engine: Option[Engine] = car.toEngine
// SELECT * FROM engine WHERE car_id IN (1234L)

val cars: Seq[Car] = Seq(Car(1L), Car(2L), Car(3L), ...)
val engines: Seq[Engine] = cars.map(_.toEngine)
// SELECT * FROM engine WHERE car_id IN (1, 2, 3, ...)

どうやって動くのか

鍵はtoEngineの返り値のモナドで, 例で見たように返り値を受け取る変数の型は(モナドの型ではなく)Option[Engine]かSeq[Engine]になっている. これは実は暗黙変換で, もし明示的に書くなら次のようになる.

val car: Car = ...
val engine: Option[Engine] = car.toEngine.run

val cars: Seq[Car] = ...
val engines: Seq[Engine] = cars.map(_.toEngine).run

HasA[].map()を実際に呼ぶのはこのrun()ということになる. これが呼ばれるまでは, HasA[].map()の呼出しはモナドの中で遅延される. レシーバがモナドのリストの場合は, これらはHasA[].map()の単一の呼出しにまとめられる*1.

なぜモナドなのか

ここまではモナドとしての使い方は一切説明してこなかった. 実際, 本質的にはモナドである必要はなく, なんらかの遅延オブジェクトでさえあればよい. モナドになっているのは利便性のためでしかない.

例を見てみよう. EngineがさらにCrankshaftを持つとして, toEngineのときと同様にtoCrankshaftで引けるとしよう. もしモナドとしての性質がなければ, CarのインスタンスからEngineのインスタンスを経由してCrankshaftのインスタンスを得るには, 次のようにする必要がある.

val car: Car = ...
val engine: Option[Engine] = car.toEngine
val crankshaft: Option[Crankshaft] =
  engine.map(_.toCrankshaft: Option[Crankshaft]).flatten

モナドになっていれば, 次のように書ける.

val car: Car = ...
val crankshaft: Option[Crankshaft] = for {
  e <- car.toEngine
  c <- e.toCrankshaft
} yield(c)

もしeやc(これらはモナドの中身を参照しているので直接Engine型およびCrankshaft型として扱える)を使ってなにか複雑な操作をする必要がある場合はとくに, この書き方ができると簡単になる.

関係のあるオブジェクトを結合する

関係性を解決して得られた2つのオブジェクトを1つにまとめたい場合もある. たとえば, CarとEngineがあったら, CarWithEngineにまとめてしまいたいかもしれない. このためには, Join.Monadicを使って以下のようにwithEngineメソッドを実装するとよい.

import com.github.tarao.bullet.Join

type CarWithEngine = (Car, Engine)

implicit class CarRelation(val car: Car) extends AnyVal {
  def withEngine = Join.Monadic(car, joinEngine)
}

type JoinEngineToCar = Join[CarWithEngine, CarId, Car, Engine]
val joinEngine: JoinEngineToCar = new JoinEngineToCar {
  def map(cars: Seq[Car]): Seq[Engine] = ... // HasA[Car, Engine]と同じ
  def leftKey(car: Car): CarId = car.id
  def rightKey(engine: Engine): CarId = engine.carId
  def merge(car: Car, engine: Engine): CarWithEngine = (car, engine)
}

今回は実装すべきメソッドが4つある: map(), leftKey(), rightKey(), merge(). map()はHasA[Car, Engine]のときとまったく同じ. leftKey()とrightKey()は関係元のオブジェクトと関係先のオブジェクトの結びつけ方を提供する. 今回の場合, CarとEngineは共通するCarIdを持つ. 結びつけられた2つのオブジェクトはmerge()に渡される.

使い方はtoEngineに非常によく似ている.

val car: Car = ...
val enginedCar: Option[CarWithEngine] = car.withEngine

val cars: Seq[Car] = ...
val enginedCars: Seq[CarWithEngine] = cars.map(_.withEngine)

補足事項

結合する際の結果の型

上の例ではCarWithEngineはただの組になっていて, これだと明らかにまずい. たとえばwithBumperとかしたくなったら今度は(Car, Bumper)にするのか, でもEngineもBumperも両方ほしいときがあって, (Car, Engine, Bumper)なのか(Car, Bumper, Engine)なのかで互換性がないのはどうなのか.

setterにするとそういう問題は起きないかもしれないけれど, そもそもsetterがあるということは型安全ではないし不変でもない. あるいは型安全なsetterというものも想定できないわけではなくて,

val engine: Engine = ...
val bumper: Bumper = ...
val car1: Car = ...
val car2 : Car with { def engine: Engine } =
   car1.withEngine(engine)
val car3 : Car with { def engine: Engine } with { def bumper: Bumper } =
   car2.withBumper(bumper)

みたいなことができればよいのかもしれない. そんなことできるだろうか? 何をsetできるかが予め決まっているのなら, いちおうできなくはない.

object Engine { trait Field { val engine: Engine } }
object Bumper { trait Field { val bumper: Bumper } }
sealed case class Car(id: CarId) {
  protected def detailed: Car.Detailed = new Car.Detailed(id)
}
object Car {
  class Detailed private[Car] (
    id: CarId,
    val engine: Engine = null,
    val bumper: Bumper = null
  ) extends Car(id)
      with Engine.Field
      with Bumper.Field {
    override protected def detailed: Detailed = this
    private[Car] def as[C >: Detailed <: Car](
      engine: Engine = null,
      bumper: Bumper = null
    ): C = new Detailed(
      id,
      Option(engine).getOrElse(this.engine),
      Option(bumper).getOrElse(this.bumper)
    )
  }

  implicit class Setter[C >: Detailed <: Car](val car: C) extends AnyVal {
    def withEngine(
      engine: Engine
    ): C with Engine.Field = car.detailed.as(engine = engine)

    def withBumper(
      bumper: Bumper
    ): C with Bumper.Field = car.detailed.as(bumper = bumper)
  }
}

うーん, けっこうめんどくさい. こういうことを汎用的にやる方法はないものだろうか?

このような型安全なsetterを実現する型というのは一般的な名前をつけるならExtensible Recordと呼ばれる. Scalaにそれをやれるライブラリはないだろうか? 実はshapelessにある. ただこれはまぁコンパイルがすごく遅くなる.

他のやり方でレコード型を実現するものにはscala-recordsがある. ただしこれは拡張できない(setterはない). 拡張できるようなレコード型の実験的な実装としてはcompossibleがあり, この作者はどうやらscala-recordsに機能をマージしようとしているので, これが完成すれば非常に期待できそう.

遅延することの是非

一般的になにかを遅延して実行すると, 実際にそれがいつ実行されるのかわかりにくくなる. それが副作用のある計算であれば, わかりにくくなることでメンテナンス性が下がるかもしれない. なのでbullet-scalaのような仕組みをただ闇雲に導入するのはあまりおすすめしない.

もともと, これを導入することに決めた動機はドメイン駆動設計(DDD)の徹底した実践のためだった. 曰く, 実装の都合をドメインロジックに持ち込んではならない.

N+1問題をただ回避したいだけであれば, SELECT-WHERE-INで引いてくるメソッドを別で用意してそれを使えばよい. けれどひとつのCarからひとつのEngineを引いてくるメソッドを残したままで, どうやってループの中でそのメソッドを引いてしまうのを防ぐのだろう? コードレビューで? クエリを監視してN+1クエリになってそうなものを潰していく? 次の10年間もそれをし続ける? 実際のところ, 現状のはてなブックマークではうんざりするほどそうしてきた. もう本当にうんざりしたので二度とそういうことはしたくない.

まとめて引いてくるメソッドを用意して使いわけるにせよ, とにかく実装上の都合でドメインロジックの記述方法が変わってしまうのは避けたい. それがbullet-scalaが作られた理由だった.

逆に, DDDをきちんと遂行していれば, おそらくCarRelationは自明にドメインサービスの一種として配置されることになるだろう. これを触ってよいのはアプリケーションサービスか他のドメインサービスのみで, run()せずにモナドをメソッドの外に返してはならない. なぜならモナド自体はドメインに記述されたモデルを表すものではないから.

toEngineしているメソッド内で必ずrun()されているなら, そう酷いことにはならないだろう, というのがいまのところの感触.

暗黙変換か明示的なrun()か

遅延していても, せめてrun()が明示的に書いてあれば, 実際にどこで実行されるのかまだわかりやすい, という意見があった. まぁこれはそうかもしれない. もし前述のDDDのきちんとした実践ができないなら, 間違いなく明示的にrun()を呼んだ方がよいとおもう. 局所的な範囲内で必ずrun()されるようなモデルになっているのであれば, toEngineしている箇所のすぐ近くで実行されているはずなので, それほど酷いことにはならない.

暗黙変換でクエリが走るのがキモいという意見もある. まぁキモいかキモくないかで言えば当然キモいとおもう. キモいのがいいのか悪いのかというのは主義によるとおもう. 個人的にはキモい言語大好きなのでキモいことはいくらでもすればいいとおもっているし, これを受け入れられないなら世の中のアレもコレもダメじゃないの? とおもうけれど細かくは書かないでおこう. とにかく, キモいのはまぁそうかとおもったしとにかくキモいのを排除いたい人もいるとおもうので, デフォルトではrun()が必要で, 暗黙変換でやりたければそれ用のimportが必要なようにした.

実装の詳細

まとめてrun()する方法

ふつうに考えると, HasA[].map()を利用してSeq[Monad[R]​] => Monad[Seq[R]​]のような変換をしなければならない. けれど一般的にはそんなことはできなくて, Monad[R]と言ってもRの値からそのまま作られたものだったり, map()やflatMap()で別の型から変換されてきたものかもしれない. HasA[].map()でまとめてやれるのは, Seq[Monad[R]​]の要素すべてがHasA.Monadic()で生成されたものの場合のみということになる.

HasA.Monadic()で作られたモナドをMonad.Resolve[]型で表し, R型の値から直接作られたものをMonad.Unit[]型で, flatMap()で作られたものをMonad.FlatMapped[]型で表すことにしよう(map()はflatMap()とUnit()の組み合わせで実現できるので専用の型は必要ない).

まとめてrun()しようとしているのがSeq[Monad.Resolve[]​]であれば, 要素のうちのどれかひとつのHasA[].map()を使って全要素の解決を一度にできる. Seq[Unit[]​]だったときには元の値をただ取り出せばよいし, Seq[FlatMapped[]​]だったときには, 各要素に対してそれぞれflatMap()に渡された関数を適用していけばよい.

一点だけ注意が必要なのは, flatMap()に渡された関数を適用した結果もまたモナドだということ. その結果のモナドのリストをまた再帰的にrun()する必要がある. このときはふたたび, リスト要素のモナドが実際にはどの型なのかによってrun()の計算の仕方を分岐する必要がある.

型安全性

簡単に「Seq[Monad.Resolve[]​]であれば」と言っているけれど, リスト内のモナドの型が全部いっしょかどうかに注意しないといけない. とくに, flatMap()した先のモナド型が, リストの各要素について全て揃っている必要がある. これを保証するために, Monad.FlatMapped[]の型にはflatMap()する前と後の型が型引数に現れるようなものになっている. 具体的に言うと, たとえば以下の2つはSeq[]に入れてもまとめてrun()できない(できてはいけない).

val car: Car = ...
val crankshaft: Crankshaft = ...
val m1 = car.toEngine.flatMap(_.toCrankshaft)
val m2 = car.toEngine.flatMap { _ => Monad.Unit(crankshaft) }
val crankshafts: Seq[Crankshaft] = Seq(m1, m2).run // type error

もしモナドの型を単にMonad[R]で表すとすると, m1とm2はどちらもMonad[Crankshaft]型ということになる. そのままrun()できるとすると, 最初のtoEngineではどちらもHasA[].map()で解決すべきモナドになっているはずなので問題ない. けれど, flatMap()された後の返り値のモナドは, m1の方はHasA[].map()で解決すべきもので, m2の方はcrankshaftの値をそのまま返す必要があって, これらは到底まとめてrun()できない*2. なのでこのような組み合わせの場合はどうやってrun()するかという以前にrun()できないように静的なエラーにしなければならない.

感想

今回のモナドはflatMap()などした途中の操作が型引数に蓄積されていくので, あんまりふつうのものではない気がする. こういうのが既に提案されていないか探してみたけれどちょっとよくわからなかった. Sig[]とか出てくるせいで, モナド則を満たすかどうかもcontextual equivalenceではなくrun()した結果が等しいというくらい(β-同値性のようなもの)でしか言えない. まとめて実行するrun()ではなく, リストの要素を個別に実行するrun()(ライブラリ内では.diverge.runで呼び出せるようになっている)でだけ考えればいいならMonad[R]上に定義されているのでcontextual equivalenceまで成り立つはず. ただ, そもそもモナド則に出てくる同値性がどういう意味の同値性であるべきなのかよく知らないのでどこまで保証すべきなのかよくわからない.

なにかもっとよい抽象化をするともう少し汎用的にできるような気もしないでもない. けれど労力の割にはきっとオーバースペックになるような気がして, いまのところはこの程度に留めている.

ツイートする

Permalink | コメント(0) | トラックバック(0) | 14:43