ZIO 2.0について

この記事はScala Advent Calendar 2021の17日目の記事です。

qiita.com

参考

この記事では下記のサイトから説明、コード、画像を引用しています。

ZIOとは

ZIOは純粋な関数型プログラミングを促進する非同期・並行プログラミング用ライブラリです。 モナドなどを知らなくても、ZIOを使うことで関数型プログラミングを始めることができます。

ZIO 2.0

つい先日ZIO2.0-RC1がリリースされました。 github.com

ZIO2.0では以下の4つの領域で大きな変更が加えられています。

  • Performance
  • Ergonomics
  • Operations
  • Streaming

ZIO2.0への移行ガイドはこちらになります。 zio.dev

以下では、上記の中からZIO 2.0での変更点で私が気になった点を取り上げました。

[Performance] 新しいスケジューラー

ZIO2.0ではスケジューラが新しくなりました。 ZIOではfiberという論理的なプロセスの単位で処理が実行されます。アプリケーションは無数のfibterから構成され、スケジューラーはfiberのOSスレッドへの割り当てを制御します。 ZIO 1.xではスケジューラーはグローバルな単一のキューとして実装されていました。

f:id:takatorix:20211216154206p:plain
ZIO1.xでのスケジューラーの実装。画像出典はhttps://ziverge.com/blog/advances-in-the-zio-2-scheduler/から

この実装の場合、全てのワーカースレッドが同じキューから取り出すため、多くのワーカースレッドが同時に操作しようとするとパフォーマンスに悪影響を及ぼす可能性がありました。また、グローバルキューを使用するとキャッシュの局所性を損ねパフォーマンスを向上させることができませんでした。

ZIO2.0では以下のようになりました。

f:id:takatorix:20211216165518p:plain
ZIO2.0でのスケジューラー 画像出典はhttps://ziverge.com/blog/advances-in-the-zio-2-scheduler/から

各ワーカースレッドごとにローカルのキューを持つことで、グローバルなリソースの競合を排除しキャッシュの局所性を最大化させることができます。しかしながら、それだけでは特定のワーカーにタスクが偏った場合リソースを効率的に使用できない可能性があります。そこで新しいスケジューラーはワーカーが自身のキューにタスクが存在しない場合に他のワーカーからタスクを盗むことができるようになっています。

詳細は以下のブログに記載されているのでご参照ください。 ziverge.com

ちなみにRustのTokioプロジェクトに触発されて開発したようです。

また、関連していそうなPRはこちらです。 github.com

[Ergonomics] Layerが使いやすくなった

fromService*がなくなりtoLayerに統一される

ZIO 1.xでは他のServiceに依存したServiceを作る場合、以下のように書かないといけませんでした。

val live: URLayer[Clock with Console, Logging] =
  ZLayer.fromServices[Clock.Service, Console.Service, Logging.Service] {
    (clock: Clock.Service, console: Console.Service) =>
      new Service {
        override def log(line: String): UIO[Unit] =
          for {
            current <- clock.currentDateTime.orDie
            _ <- console.putStrLn(current.toString + "--" + line).orDie
          } yield ()
      }
  }

ZIO 2.0ではtoLayerが導入されボイラープレートを書かなく済むようになります。

case class LoggingLive(console: Console, clock: Clock) extends Logging {
  override def log(line: String): UIO[Unit] =
    for {
      current <- clock.currentDateTime.orDie
      _       <- console.putStrLn(current.toString + "--" + line).orDie
    } yield ()
}

object LoggingLive {
  val layer: URLayer[Console with Clock, Logging] =
    (LoggingLive(_, _)).toLayer[Logging]
}

依存関係の構築が簡単に

ZIO 1.xでは複数のレイヤーを以下のように組み合わせてアプリケーション全体の依存グラフを構築する必要がありました。

val appLayer: URLayer[Any, DocRepo with UserRepo] =
  (((Console.live >>> Logging.live) ++ Database.live ++ (Console.live >>> Logging.live >>> BlobStorage.live)) >>> DocRepo.live) ++
    (((Console.live >>> Logging.live) ++ Database.live) >>> UserRepo.live)
    
val res: ZIO[Any, Nothing, Unit] = myApp.provide(appLayer)

依存関係が大きくなってくると上記をメンテするのが大変でした。また依存関係の宣言に間違いがあった場合、以下のようなメッセージがコンパイル時に出力されるのですが、わかりづらく解決するのが難しかったです。

type mismatch;
 found   : zio.URLayer[zio.Logging with zio.Database with zio.BlobStorage,zio.DocRepo]
    (which expands to)  zio.ZLayer[zio.Logging with zio.Database with zio.BlobStorage,Nothing,zio.DocRepo]
 required: zio.ZLayer[zio.Database with zio.BlobStorage,?,?]
    ((Database.live ++ BlobStorage.live) >>> DocRepo.live) ++

ZIO 2.0ではinjectを使用することで自動で依存関係が解決されるようになります!

val res: ZIO[Any, Nothing, Unit] =
  myApp.inject(
    Console.live,
    Logging.live,
    Database.live,
    BlobStorage.live,
    DocRepo.live,
    UserRepo.live
  )

Module Patternが変わる

ZIO1.xでのModule Patternは以下のようになっていました。

object logging {
  // Defining the service type by wrapping the service interface with Has[_] data type
  type Logging = Has[Logging.Service]

  // Companion object that holds service interface and its live implementation
  object Logging {
    trait Service {
      def log(line: String): UIO[Unit]
    }
    
    // Live implementation of the Logging service
    val live: ZLayer[Clock with Console, Nothing, Logging] =
      ZLayer.fromServices[Clock.Service, Console.Service, Logging.Service] {
        (clock: Clock.Service, console: Console.Service) =>
          new Logging.Service {
            override def log(line: String): UIO[Unit] =
              for {
                current <- clock.currentDateTime.orDie
                _       <- console.putStrLn(s"$current--$line")
              } yield ()
          }
      }
  }

  // Accessor Methods
  def log(line: => String): URIO[Logging, Unit] =
    ZIO.accessM(_.get.log(line))
}

ZIO 2.0 では Hasが削除され以下のようになります。

// Defining the Service Interface
trait Logging {
  def log(line: String): UIO[Unit]
}

// Accessor Methods Inside the Companion Object
object Logging {
  def log(line: String): URIO[Logging, Unit] =
    ZIO.serviceWithZIO(_.log(line))
}

// Implementation of the Service Interface
case class LoggingLive(console: Console, clock: Clock) extends Logging {
  override def log(line: String): UIO[Unit] =
    for {
      time <- clock.currentDateTime
      _    <- console.printLine(s"$time--$line").orDie
    } yield ()
}

// Converting the Service Implementation into the ZLayer
object LoggingLive {
  val layer: URLayer[Console with Clock, Logging] =
    (LoggingLive(_, _)).toLayer[Logging]
}

ZIO1.x系のmoduleパターンについては以前書きましたが、 Hasが削除された結果、覚えることが少なくなりよりシンプルに書けるようになっている気がします。

takatorix.hatenablog.com

[Ergonomics] Smart Constructorの導入

ZIO 1.xではZIOのコンストラクタとしてZIO.fromEitherZIO.fromOptionのような形で、元になるデータ型ごとにメソッドが用意されていました。

ZIO 2.0ではfromだけで様々なデータ型からZIOを生成できるようになっています。

ZIO.from {
  println("Entering example")
  for {
    result1 <- ZIO.from(Future.successful(1))
    result2 <- ZIO.from(Right(2))
    result3 <- ZIO.from(ZIO.from(3))
    result4 <- ZIO.from(Try(4))
  } yield result1 + result2 + result3 + result4
}

[Operations] Loggingがビルトインされるようになった

ZIO 2.0 では標準のlogging facadeが提供されるようになりました。 facadeなのでlogbacklog4jなどのloggingバックエンドはこれまで通り必要となります。

ZIO.logLevel(LogLevel.Warning) {
  ZIO.log("The response time exceeded its threshold!")
}

ZIO.logError("File does not exist: ~/var/www/favicon.ico")

今まではLogging Moduleを毎回自作していたので、その手間がなくなりそうです。

ziverge.com

まとめ

ZIO 2.0で導入される機能や変更の一部を紹介しました。様々な改善点が盛り込まれていてリリースされるのが待ち遠しいです。 今回は変更点が多すぎてほんの一部しか紹介できなかったので、ぜひマイグレーションガイドを読んでみてください。

ZIOのZLayerについて

この記事はただの集団 Advent Calendar 2020の23日目の記事です。

adventar.org

本記事では、ZIOのDI機能であるZLayerの使い方を説明します。 対象読者はZIOをある程度知っている方を想定しています。 ZIOについて詳しく知らない方はまず公式ページのドキュメントを読むことをお勧めします。

zio.dev

ZIOとは

ZIOは純粋な関数型プログラミングを促進する非同期・並行プログラミング用ライブラリです。 モナドなどを知らなくても、ZIOを使うことで関数型プログラミングを始めることができます。

ZIOには便利なデータ型が複数存在しますが、中心となるのはeffectを表すデータ型であるZIO[-R, +E, +A]です。 このデータ型はの3つの型パラメータを持ちます。

R: Environment Type => 実行に必要な環境の型, Anyの場合は環境を必要としない
E: Failure Type  => 失敗した時の型, Nothingの場合は失敗しない
A: Success Type => 成功した時の型

E,Aに関しては説明不用だと思うので、今回はこのRについて詳しくみていきます。

環境型Rの使い方

題材としてZIOで書かれた以下のプログラムを考えます。 このコードは、公式ドキュメントのものを参考にしています。 https://zio.dev/docs/howto/howto_use_layers#our-first-zio-module

val user2: User = User(UserId(123), "Tommy")
val makeUser: ZIO[Logging with UserRepo, DBError, Unit] = for {
  _ <- ZIO.accessM[Logging](_.get.info(s"inserting user"))  
  _ <- ZIO.accessM[UserRepo](_.get..createUser(user2))
  _ <- ZIO.accessM[Logging](_.get.info(s"user inserted"))
} yield ()

このプログラムは、最初に処理をはじめることをログに出力し、 つぎに、ユーザをRepositoryに登録します。 最後にログに処理が完了したことを再度出力します。

Logging with UserRepomakeUserを実行するために必要な環境の型です。 ここではLoggingUserRepoは以下のようなメソッドを持つ型だと考えてください。

trait Logging {
  def info(s: String): UIO[Unit]
}

trait UserRepo {
  def createUser(user: User): IO[DBError, Unit]
}

ZIO.accessMを使うことでeffectの環境にアクセスすることができます。 このプログラムmakeUserを実行するためには、 以下のようにLoggingUserRepoの実装を提供する必要があります。

val runnable: ZIO[Any, DBError, Unit] = 
    makeUser.provide(new Logging with UserRepo { // なんらかの実装 }) 

runtime.unsafeRun(runnable)

ZIO.provideによってeffectに環境を提供することで、Rから必要な環境が削除され、環境型がAnyのeffectが生成されます。 こうして作成されたeffectはruntime.unsafeRunで実行できるようになります。 ZIOのバージョンv1.0.0-RC17までは実際にこのようにして、依存性を注入していました。

しかしながら、このアプローチにはいくつかの欠点があります。 まず、環境の一部だけを提供することができません。必要な環境を全て揃えた上でprovideする必要があります。 また、環境の一部を動的に更新することができず、アプリケーションの一部でサービスをカスタマイズしようとするときに苦労します。

これらの問題の解決のために、v1.0.0-RC18ではHasとZLayerという2つの新しいデータ型が導入されました。

ZIO module

HasZLayerの詳細に入る前に、ZIOで環境を定義する際の典型的なパターンを紹介します。

type UserRepo = Has[UserRepo.Service]

object UserRepo {
  // インタフェース
  trait Service {
    def getUser(userId: UserId): IO[DBError, Option[User]]
    def createUser(user: User): IO[DBError, Unit]
  }

  // 実装
  val testRepo: ZLayer[Any, Nothing, UserRepo] = ZLayer.succeed(???)


  // ZIO.accessMを毎回書くのは大変なので、ここでアクセサメソッドを定義しておく
  def getUser(userId: UserId): ZIO[UserRepo, DBError, Option[User]] =
    ZIO.accessM(_.get.getUser(userId))

  def createUser(user: User): ZIO[UserRepo, DBError, Unit] =
    ZIO.accessM(_.get.createUser(user))
}

この書き方のパターンをモジュールパターンと呼びます。 モジュールとは、1つの問題のみを扱う機能のグループです。 モジュールの範囲を限定することで、頭の中であまりにも多くの概念を一緒に扱うことなく、 一度に一つのトピックだけに集中することができます。

何かしらの環境を定義する必要がある場合は、まずこのパターンにのっとってインタフェースを定義します。 このパターンさえ覚えておけば、どのようなものでも同じようにアプリケーションの環境として扱えます。

Has

先ほどのコードでHas[UserRepo.Service]というものがありました。 Has[A] は、型 A のサービスに対するeffectの依存性を表現するための型です。 たとえば、RIO[Has[Console.Service], Unit] はこのeffectがConsole.Serviceを必要とすることを表しています。

Has++演算子を使用して組み合わせることができます。

val repo: Has[UserRepo.Service] = Has(new UserRepo.Service{})
val logger: Has[Logger.Service] = Has(new Logger.Service{})
val mix: Has[UserRepo.Service] with Has[Logger.Service] = repo ++ logger

先ほどは UserRepo with Loggingとmixinで2つの環境を組み合わせていました。 これでも環境の組み合わせはできていたのに、 なぜtype UserRepo = Has[UserRepo.Service]のような型エイリアスを用いてまでHasを使っているのでしょうか?

Hasが優れているところは、以下のように複数のHasを結合したあとでも、 それぞれの環境を分離して取り出すことができる点です。

// get back the logger service from the mixed value:
val log = mix.get[Logger.Service].log("Hello modules!")

これが可能であるということは、型安全に環境の一部を動的に更新することができるということです。

Hasでなぜこのようなことが可能なのかというと、TypeTagを用いているためです。 Hasの定義は以下のようになっています。 https://github.com/zio/zio/blob/master/core/shared/src/main/scala/zio/Has.scala

 final class Has[A] private (
  private val map: Map[LightTypeTag, scala.Any],
  private var cache: Map[LightTypeTag, scala.Any] = Map()
 ) extends Serializable ..

ここでmap: Map[LightTypeTag, scala.Any]でインタフェースと実装のマッピングを保持しています。
他の JVM言語同様に、Scala の型はコンパイル時に消去されますが、 TypeTagを用いることで実行時でも型情報を保持することができます。
Has++で結合するということは、単にmapに新しい項目を追加しているということです。 またmapのキーに同じ型を指定することで実装を後から入れ替えることもできます。

余談ですが、ZIOではscala-reflectのTypeTagの代わりに独自実装のizumi-reflectを使用しているようです。 github.com

ZLayer

さて、データ型Hasを見てきましたが、つぎにZLayerについて説明します。 Zlayerは環境Rを作るためのレシピを表すデータ型です。ZLayer[-RIn, +E, +ROut <: Has[_]]という3つの型パラメータを持ちます。

RIn - 構築するために必要な依存関係 (依存関係がない場合は Any になります)
E - 作成時に発生する可能性があるエラー(失敗する可能性がない場合はNothing)
ROut - 作成される環境の型

つまり、RIn型からRout型を生成する方法を表すデータ型です。 これはJavaScalaアプリケーションのコンストラクタに似ていて、依存するサービスを受け取り、構築したサービスを返します(コンストラクタベースの依存性注入)。 しかし、コンストラクタとは異なり、ZLayers はいくつかの方法で型安全に構成されたファーストクラスの値であり、1つのサービスだけではなく、多くのサービスを構築することができます。 さらに、データベースに接続し、データベースのスレッドプールを作成し、サービスが不要になったら、スレッドプールを解放し、データベースから切断するといった、リソースの管理も行うことができます。

では、ZLayerの作り方を見ていきます。

まず、RIntがAnyかつ失敗しない場合は、ZLayer.succeedを使うことでZLayerを作成できます。

type UserRepo = Has[UserRepo.Service]

object UserRepo {
  trait Service {
    def getUser(userId: UserId): IO[DBError, Option[User]]
    def createUser(user: User): IO[DBError, Unit]
  }

  val inMemory: ZLayer[Any, Nothing, UserRepo] = ZLayer.succeed(
    new Service {
      def getUser(userId: UserId): IO[DBError, Option[User]] = UIO(???)
      def createUser(user: User): IO[DBError, Unit] = UIO(???)
    }
  )

  //accessor methods
  def getUser(userId: UserId): ZIO[UserRepo, DBError, Option[User]] =
    ZIO.accessM(_.get.getUser(userId))

  def createUser(user: User): ZIO[UserRepo, DBError, Unit] =
    ZIO.accessM(_.get.createUser(user))
}

つぎに、構築時に他のコンポーネントが必要な場合を見てみます。

type Logging = Has[Logging.Service]

object Logging {
  trait Service {
    def info(s: String): UIO[Unit]
    def error(s: String): UIO[Unit]
  }

  import zio.console.Console
  val consoleLogger: ZLayer[Console, Nothing, Logging] = ZLayer.fromFunction( console =>
    new Service {
      def info(s: String): UIO[Unit]  = console.get.putStrLn(s"info - $s")
      def error(s: String): UIO[Unit] = console.get.putStrLn(s"error - $s")
    }
  )

  //accessor methods
  def info(s: String): URIO[Logging, Unit] =
    ZIO.accessM(_.get.info(s))

  def error(s: String): URIO[Logging, Unit] =
    ZIO.accessM(_.get.error(s))
}

ZLayerの構築方法は以下のように様々な種類があります。 一つ一つの説明は行いませんが、どのメソッドを使うべきかの判断するには各メソッドの実装を見て型から考えていくのが早いと思います。

ZLayer.succeed  // or ZIO#asService to create a layer from an existing service
ZLayer.succeedMany  // to create a layer from a value that's one or more services
ZLayer.fromFunction   // to create a layer from a function from the requirement to the service
ZLayer.fromEffect       // to lift a ZIO effect to a layer requiring the effect environment
ZLayer.fromAcquireRelease // for a layer based on resource acquisition/release. The idea is the same as ZManaged
ZLayer.fromService    // to build a layer from a service
ZLayer.fromServices // to build a layer from a number of required services
ZLayer.identity          // to express the requirement for a layer
ZIO#toLayer              // or ZManaged#toLayer to construct a layer from an effect

最後に、ZLayerの使い方をみていきます。

ZLayerは++メソッドで水平に合成することができます。

val inMemory: ZLayer[Any, Nothing, UserRepo] = UserRepo.inMemory
val consoleLogger: ZLayer[Console, Nothing, Logging]  = Logging.consoleLogger
val horizontal: ZLayer[Console, Nothing, Logging with UserRepo] = Logging.consoleLogger ++ inMemory

これはHasのところで見た形と似ていると思います。 実際にZLayerの++メソッドは内部でHasのunionメソッド、すなわち++メソッドを呼び出しています。

また、ZLayerを縦に合成することもできます。 つまり、1 つのレイヤーの出力を後続のレイヤーの入力として使用して次のレイヤーを構築することができます。

val horizontal: ZLayer[Console, Nothing, Logging with UserRepo] = Logging.consoleLogger ++ inMemory
val console: ZLayer[Any, Nothing, Console] = Console.live
val fullLayer: ZLayer[Any, Nothing, Logging with UserRepo] = console >>> horizontal
makeUser.provideLayer(fullLayer)

このようにZLayerを使うことで、柔軟に環境の構築を行うことができます。 継承ベースの環境組み合わせから、ZLayerを用いて値ベースで環境を組み合わせになったことで柔軟に環境の構築・変更ができるようになりました。

まとめ

ZIOのデータ型であるZLayerを紹介しました。

参考

PlayFramework+GuiceでDIしているときに型クラスインスタンスでインジェクションされたクラスを使用する

PlayFrameworkでGuiceを使ってDIしているときに、 型クラスインスタンスでインジェクションされたクラスを使う方法を調べました。

以下のようなコードがあるとします。

// Factory.scala

trait Factory[T] {
  def create: T
}

case class Type1()

object Type1Factory {
  implicit object Type1Factory extend Factory[Type1] {
     override def create: Type1  = Type1()
  }
}

case class Type2(value: String)

object Type2Factory {
  implicit object Type2Factory extend Factory[Type2] {
     //  どうやってここに、type2Repositoryを渡せば良い?
     override def create: Type2 = type2Repository.load()  
  }
}
// UseCase.scala

class UseCase @Inject()(type2Repository: Type2Repository) {
  def create[T: Factory]: T = {
    // 共通処理
    ... 

    implicitly[Factory[T]].create
  }
}
// Controller.scala

class Controller @Inject()(usecase: UseCase) {
  import Factory._
  def create1: Type1  = usecase.create()
  def create2: Type2 = usecase.create()
}

Factoryというcreateというメソッドをもつ型クラスがあって、 その型クラスインスタンスとしてType1FactoryType2Factoryが定義されています。 Type1Factoryはとくに他に依存しないcreateメソッドを持ちますが、 Type2Factorycreateメソッドでは、Type2Repositoryを使う必要があります。 Type2Repositoryはインタフェースで、他のところにDBからデータを取得する処理を行うType2RepositoryImplクラスが定義されています。 Type2RepositoryGuiceUseCaseクラスにInjectされます。

このとき、DI管理下のType2RepositoryインスタンスType2Factoryに渡す方法がわからず、困っていました。 Type2Repositoryが必要なのはType2Factoryだけなので、Factoryのメソッドの引数にType2Repositoryを渡したくありません。 型クラスインスタンスが増え、そのインスタンスが別のRepositoryを要求する場合、引数を追加していかなければならないためです。

良い方法が思いつかなくて悩んでいたところ、Twitterで教えていただきました。

値に対するimportでうまくいきそうです。以下が、改良版のコードになります。

// UseCase.scala

class UseCase @Inject()(type2Repository: Type2Repository) {

  def create[T: Factory]: T = {
    // 共通処理
    ... 

    implicitly[Factory[T]].create
  }

  implicit val type1Factory: Factory[Type1] = new Factory[Type1] {
    override def create: Type1  = Type1()
  }
  
  implicit val Type2Factory: Factory[Type2] = new Factory[Type2] {
     override def create: Type2 = type2Repository.load()  
  }
}
// Controller.scala

class Controller @Inject()(usecase: UseCase) {
  import usecase._
  def create1: Type1  = usecase.create()
  def create2: Type2 = usecase.create()
}

型クラスインスタンスをDI管理下のUseCaseクラスで定義することで、Type2Repositoryを呼び出すことができました。 また、先程はControllerクラスでimport Factory._で型クラスインスタンスをimportしていましたが、 scalaでは値に対してimportできるようなので、インジェクトされたUseCaseインスタンスに対してimportすることでimplicitが解決できるようになります。

社内の検索技術勉強会ふりかえり

これはただの集団 Advent Calendar 2019の16日目の記事です。

adventar.org

昨日はTapanさんのMonixの話でした。

medium.com

最初はZIOについて書こうと思っていたのですが、 TapanさんのMonixの話と内容がほとんどおなじになってしまったので 社内で行っている検索技術勉強会について書くことにします。

概要

昨年2月頃から社内のエンジニアを中心に始めた勉強会です。 検索技術を勉強する機会を作るためにふわっとはじめました。 週一回お昼休みに集まって、ご飯を食べながら進めています。

メンバー

メンバーは開発チームのエンジニアがだいたい6名ほどで、 それ以外にAIチームの方が1名参加してくれています。 初期はもっと参加者がいましたが、このぐらいの人数で落ち着きました。

内容

はじめに取り組んだのは情報検索の基礎という有名な本です。

タイトルどおり情報検索の基礎を学ぶ上で外せない本です。 特に第1章〜第8章まではポスティングリストやTF-IDFなどの検索技術の基本的な概念・手法がつまっていて非常に勉強になりました。 それ以降の章に関してはどちらかというと機械学習の話になってきたので、 この本を使わずに機械学習に強いメンバーに独自で資料を作ってもらったりしました。 また、機械学習に関しては他の本で学んだほうが効率が良さそうだねということで、 第11章〜第18章は飛ばして読み、逆に第19〜第21章はウェブ検索についての章だったのでしっかり読みました。

この本は一番最初、全員で本を読みながらホワイトボードを使って議論するスタイルで進めていました。 このやり方はしっかり理解ができるという点では良かったのですが、あまりにも進みが遅かったためすぐに変えなければなりませんでした。 その後は、各章ごとに担当を割り振りスライドを作ってもらって発表する形式になり、結果的に進みは良くなりましたが、 自分の担当箇所以外の理解度が低くなってしまった印象があります。 例えば、ジグソー法などでもう少しうまく議論が発生する仕組みを取り入れてみても良かったかもしれません。

achievement-hrs.co.jp

余談ですが、この本で学んだことをまとめた同人誌を技術書典7で販売しました。

booth.pm

情報検索の基礎を読み終わったので、現在はランク学習(Learning to Rank)に取り組んでいます。 ランク学習とは機械学習で文書の並びを予測する手法です。

この題材に関しては、なんと昨年のアドベントカレンダーで一人でランク学習についての記事を書かれている方がいたので、 この記事を読みながら少しづつすすめていっています。

adventar.org

また、同じ方が発表されたヤフーにおける機械学習検索ランキングの取り組みの資料も非常に参考になります。

speakerdeck.com

上記の資料をもとに、ランク学習を用いた検索基盤を構築するのが目下の目標です。 情報検索の基礎は良かったのですが、あまり手を動かせておらずアウトプットが少なかったため、今回は モブプログラミングなどでメンバー全員でコードを書きながら進めてみようと思っています。

その後のことについては、やりたいことが多すぎて何をやるか決まっていません。 案としては以下のようなものが上がっています。

まとめ

ふりかえってみると、9ヶ月ほど続いている勉強会になっていました。 まだ検索技術の初歩的な部分しか触れていませんが、 なにより継続することが一番難しいと思うので、これからも続けていければと思います。

Go言語でフレーズ検索を実装してみる

この記事はただの集団 AdventCalendar PtW.2019の6日目の記事です。 昨日はumeneriさんのGKE上にElasticsearchとcerebro環境を構築するでした。

本記事では、Golangを使って検索エンジンのフレーズ検索機能を実装してみます。

フレーズ検索とは

文章の集合からダブルクォートでくくった文字に合致する部分を見つける検索です。 例えば、"エンジニア 東京"で検索するとエンジニア 東京というフレーズに合致するものだけを取得します。 エンジニア東京だけに合致するものは結果に含みません。 検索エンジンはフレーズ検索を実現するだけでなく、効率的に処理する必要があります。 本記事では、フレーズ検索を行うためのアルゴリズムの実装を行います。

転置インデックス

一般的に、時間がかかるテキストの線形走査を避けるためには、事前に文書をインデックス付します。 ほとんどすべての情報検索エンジンでは、インデックスに転置インデックスを用います。

転置インデックスとは、簡単に言うと「用語とその用語の文書集合内の出現位置のマッピング」です。 転置インデックスは、文書集合内に含まれる用語のリストである辞書と各用語に紐づく出現位置のリストであるポスティングリストから構成されます。

今回は簡単のため、ポスティングリストにはその用語のテキスト集合内での出現位置の配列を持つようにします。 このようにポスティングリストに構造を持たないものをschema-independent-indexと呼びます。

package index

// schema independent index
type Index struct {
    Dictionary map[string][]int
}

また、Indexを作成するメソッドも追加しておきます。

func NewIndex(dictionary map[string][]int) *Index {
    index := new(Index)
    index.Dictionary = dictionary
    return index
}

準備

まず、今回実装する関数の説明をしておきます。 今回は以下の4つの関数を実装します。

  • next(t string, current int) int
    • 現在の位置(current)より後ろにある最初の用語tの場所を返す。
  • prev(t string, current int) int
    • 現在の位置(current)より前にある最初の用語tの場所を返す。
  • nextPhrase(phrase []string, current) (int, int)
    • 現在の位置(current)より後ろにある最初のフレーズ(phrase)の開始位置と終了位置を返す。
  • allPhrase(phrase []string, current) [][2]int
    • 現在の位置(current)より後ろにある全てのフレーズの開始位置と終了位置を返す。

アルゴリズムの実装の前にまずテストを書きましょう。

func TestNext(t *testing.T) {

    index := NewIndex(map[string][]int{
        "大阪": {316669, 745434},
        "営業":    {36898, 137236, 745397, 745419, 1247139},
        "エンジニア":      {1598, 27555, 745407, 745429, 745451, 745467, 1245276},
        "事務":   {265197},
    })

    type test struct {
        t        string
        current  int
        expected int
    }

    testCases := []test{
        {"エンジニア", 745429, 745451},
        {"大阪", 345678, 745434},
        {"エンジニア", 1245276, END_OF_FILE},
        {"エンジニア", BEGINNING_OF_FILE, 1598},
        {"エンジニア", END_OF_FILE, END_OF_FILE},
    }

    for _, testCase := range testCases {
        actual := index.next(testCase.t, testCase.current)
        if actual != testCase.expected {
            t.Errorf("\n got: %v\n want: %v", actual, testCase.expected)
        }
    }

}

func TestPrev(t *testing.T) {

    index := NewIndex(map[string][]int{
        "大阪": {316669, 745434},
        "営業":    {36898, 137236, 745397, 745419, 1247139},
        "エンジニア":      {1598, 27555, 745407, 745429, 745451, 745467, 1245276},
        "事務":   {265197},
    })

    type test struct {
        t        string
        current  int
        expected int
    }

    testCases := []test{
        {"エンジニア", 745451, 745429},
        {"大阪", 456789, 316669},
        {"エンジニア", 1598, BEGINNING_OF_FILE},
        {"エンジニア", END_OF_FILE, 1245276},
        {"エンジニア", BEGINNING_OF_FILE, BEGINNING_OF_FILE},
    }

    for _, testCase := range testCases {
        actual := index.prev(testCase.t, testCase.current)
        if actual != testCase.expected {
            t.Errorf("\n got: %v\n want: %v", actual, testCase.expected)
        }
    }

}

func TestNextPhrase(t *testing.T) {

    index := NewIndex(map[string][]int{
        "東京": {2205, 2268, 745406, 745466, 745501, 1271487},
        "エンジニア": {1598, 27555, 745407, 745429, 745451, 745467, 745502, 1245276},
    })

    type test struct {
        t             []string
        current       int
        expectedStart int
        expectedEnd   int
    }

    testCases := []test{
        {[]string{"東京", "エンジニア"}, BEGINNING_OF_FILE, 745406, 745407},
        {[]string{"東京", "エンジニア"}, 745500, 745501, 745502},
    }

    for _, testCase := range testCases {
        u, v := index.nextPhrase(testCase.t, testCase.current)
        if u != testCase.expectedStart || v != testCase.expectedEnd {
            t.Errorf("\n got: [%v, %v]\n want: [%v, %v]", u, v, testCase.expectedStart, testCase.expectedEnd)
        }
    }

}

func TestAllPhrase(t *testing.T) {

    index := NewIndex(map[string][]int{
        "東京": {2205, 2268, 745406, 745466, 745501, 1271487},
        "エンジニア": {1598, 27555, 745407, 745429, 745451, 745467, 745502, 1245276},
    })

    type test struct {
        t        []string
        current  int
        expected [][]int
    }

    testCases := []test{
        {[]string{"東京", "エンジニア"},
            BEGINNING_OF_FILE,
            [][]int{
                {745406, 745407},
                {745466, 745467},
                {745501, 745502},
            },
        },
    }
    for _, testCase := range testCases {
        results := index.allPhrase(testCase.t, testCase.current)
        for i, result := range results {
            if result[0] != testCase.expected[i][0] || result[1] != testCase.expected[i][1] {
                t.Errorf("\n got: %v\n want: %v", result, testCase.expected[i])
            }
        }
    }
}

実装

まず、現在位置の前後に最初に用語が出現する位置を返すnextとprevを実装します。

// next(t, current) returns the position of t's first occurrence after the current position
func (index *Index) next(t string, current int) int {

    if postingList, ok := index.Dictionary[t]; !ok {
        return END_OF_FILE
    } else {
        for _, p := range postingList {
            if p > current {
                return p
            }
        }
        return END_OF_FILE
    }
}

// prev(t, current) returns the position of t's last occurrence before the current position
func (index *Index) prev(t string, current int) int {

    if postingList, ok := index.Dictionary[t]; !ok {
        return BEGINNING_OF_FILE
    } else {
        for i := len(postingList) - 1; i >= 0; i-- {
            p := postingList[i]
            if p < current {
                return p
            }
        }
        return BEGINNING_OF_FILE
    }

}

単に引数で渡された用語のポスティングリストをたどり、条件に合致するものを返します。 見つからない場合は、ファイルの開始や終了を表す定数(BEGINNING_OF_FILE, END_OF_FILE)を返しています。 簡単のため以下のように定義しておきます。

const (
    BEGINNING_OF_FILE = -math.MaxInt32
    END_OF_FILE       = math.MaxInt32
)

それでは、実際にフレーズ検索を行う部分を実装します。

nextPhraseは現在の位置より後ろにあるフレーズを見つけ、その開始位置uと終了位置vを返す関数です。

func (index *Index) nextPhrase(phrase []string, current int) (int, int) {

    length := len(phrase)

    v := current
    for _, t := range phrase {
        v = index.next(t, v)
    }
    if v == END_OF_FILE {
        return END_OF_FILE, END_OF_FILE
    }
    u := v
    for i := length - 2; i >= 0; i-- {
        u = index.prev(phrase[i], u)
    }
    if v-u == length-1 {
        return u, v
    } else {
        return index.nextPhrase(phrase, u)
    }
}

この関数は大まかに2つの処理に分けることができます。 まず、はじめに引数で渡された用語のリスト(phrase)の順に用語が出現している箇所を探索します。

   v := current
    for _, t := range phrase {
        v = index.next(t, v)
    }
    if v == END_OF_FILE {
        return END_OF_FILE, END_OF_FILE
    }

現在の位置からフレーズに含まれる用語の順にnextを呼び出し、フレーズの最後尾の用語の位置を割り出します。 これにより、フレーズに含まれる用語(t1,t2....,tn)が文書中にこの順で出現していることが明らかになりました。 ここで、文書内にフレーズ内の用語が文書中に順番通り含まれていなければ、そのフレーズは見つからなかったとして探索を終了します。

次に、それらの用語の出現箇所が隣接しているかをチェックします。

   u := v
    for i := length - 2; i >= 0; i-- {
        u = index.prev(phrase[i], u)
    }
    if v-u == length-1 {
        return u, v
    } else {
        return index.nextPhrase(phrase, u)
    }

フレーズ最後尾の用語の位置からフレーズに含まれる用語の逆順にprevを呼び出し、フレーズの開始位置uを特定します。 uが特定できたらu,vの距離を計算し、その長さがフレーズの長さと一致していれば、検索できたのでその位置を返します。 長さが異なっていれば、現在位置を更新して再度nextPhraseを呼び出します。このようにしてフレーズが見つかるまで探索します。

すべてのフレーズを検索するには単にnextPhraseを文書集合の末尾に到達するまで開始位置uを更新しながらforでまわします。

func (index *Index) allPhrase(phrase []string, current int) [][2]int {

    var results [][2]int
    var u,v int

    u = current

    for u < END_OF_FILE {
        u, v = index.nextPhrase(phrase, u)
        if u != END_OF_FILE {
            results = append(results, [2]int{u, v})
        }
    }
    return results
}

以上が、フレーズ検索の実装になります。

まとめ

全文検索エンジンのフレーズ検索機能をGo言語で実装してみました。 今回実装したnextやprevメソッドはポスティングリストをたどるのに単にループしてしまっていますが、 キャッシュやbinary searchなどを使用して計算量を改善することができます。

参考

Godogの実装を見てみる

この記事はただの集団 Advent Calendar 2018の23日目の記事です。
昨日は hajimeniさんのプログラム上で時間を扱う際に気をつけることでした。
Advent Calendarもいよいよ終りが見えてきました。

本記事では、GolangでATTDを実践するためのツールであるGodogがどのように動いているかを探ってみます。

adventar.org

TL;DR

  • Godogはコマンド実行時にファイルを読み込んでテスト用のソースコードを生成し、それをコンパイルしたものを実行している
  • go/buildgo/parsergo/astなどのパッケージを活用してソースコードを解析して、対象となるstep関数を見つけ出している

はじめに

GodogとはCucurmberのGolang版です。GithubのCucumberのリポジトリには存在しませんが、 Cucurmberチームの開発メンバーがメンテナンスしているようなので安心して使って良いと思われます。

github.com

Godogは以下のような自然言語で書かれたfeatureファイルと、それに対応するstepファイルを記述しgodogコマンドを実行することでテストが実行されます。

Feature: eat godogs
  In order to be happy
  As a hungry gopher
  I need to be able to eat godogs

  Scenario: Eat 5 out of 12
    Given there are 12 godogs
    When I eat 5
    Then there should be 7 remaining
package main

import (
    "github.com/DATA-DOG/godog"
)

func thereAreGodogs(arg1 int) error {
    return godog.ErrPending
}

func iEat(arg1 int) error {
    return godog.ErrPending
}

func thereShouldBeRemaining(arg1 int) error {
    return godog.ErrPending
}

func FeatureContext(s *godog.Suite) {
    s.Step(`^there are (\d+) godogs$`, thereAreGodogs)
    s.Step(`^I eat (\d+)$`, iEat)
    s.Step(`^there should be (\d+) remaining$`, thereShouldBeRemaining)
}

f:id:takatorix:20181222171824j:plain

godogコマンドが実行されたときにどのようにしてこれらのテストが実施されるのでしょうか? godogコマンドはどのようにしてstepファイルを認識しているのでしょうか? これらの疑問を解消するため、実際にgodogのコードを見てみることにしました。

Godogの動き

call graphは以下のようになっています。今回着目する箇所は印がついている部分になります。

f:id:takatorix:20181222180312j:plain

ちなみに、こちらはgo-callvisを使って出力しました。

github.com

main

godogを実行するとはじめに、cmd/godog/main.goのmainが呼び出されます。

https://github.com/DATA-DOG/godog/blob/master/cmd/godog/main.go#L61-L105

package main

...

func main() {
    
    (省略)

    status, err := buildAndRun() // ここからスタート
    
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }
    // it might be a case, that status might not be resolved
    // in some OSes. this is attempt to parse it from stderr
    if parsedStatus > status {
        status = parsedStatus
    }
    os.Exit(status)
}

mainでは、引数のParseなどを行ったあと、同じファイル内のbuildAndRun関数を呼び出しています。

buildAndRun

https://github.com/DATA-DOG/godog/blob/master/cmd/godog/main.go#L17-L59

package main

...

var parsedStatus int

func buildAndRun() (int, error) {
    var status int

    bin, err := filepath.Abs("godog.test")
    if err != nil {
        return 1, err
    }
    if build.Default.GOOS == "windows" {
        bin += ".exe"
    }
    if err = godog.Build(bin); err != nil { // テストの実行ファイルをビルド
        return 1, err
    }
    defer os.Remove(bin) // 処理が終わったら実行ファイルを削除

    cmd := exec.Command(bin, os.Args[1:]...)
    cmd.Stdout = os.Stdout
    cmd.Stderr = os.Stderr
    cmd.Stdin = os.Stdin
    cmd.Env = os.Environ()

    if err = cmd.Start(); err != nil { // テストを実行
        return status, err
    }

    (省略)
}

buildAndRunの中で行っていることはgodog.testという実行ファイルをgodog.Buildで生成し、 それをexec.Commandで実行するということです。

どうやら、godogコマンドを実行すると直接テストが走るのではなく、 テスト用の実行ファイルをビルドしそれを実行することで テストが動くという仕組みになっているようです。

では、Buildの中の処理を追っていきます。

Build(前半)

https://github.com/DATA-DOG/godog/blob/master/builder.go#L48-L219

Buildの中で最初に重要なのは以下の部分です。

func Build(bin string) error {
    abs, err := filepath.Abs(".") // (1)
    if err != nil {
        return err
    }

    // we allow package to be nil, if godog is run only when
    // there is a feature file in empty directory
    pkg := importPackage(abs) // (2)
    src, anyContexts, err := buildTestMain(pkg) // (3)
    if err != nil {
        return err
    }

    ...
}

はじめに、(1)のfilepah.Abs(".")でカレントディレクトリの絶対パスを取得しています。

次に(2)で、 同じファイル内のimportPackageを呼び出しています。 importPackageではgo/buildパッケージのImportDirメソッドを呼び出すことで、 指定したディレクトリ以下のGoファイルを調べ、goのパッケージ情報を抽出しています。 返り値は以下のような情報を持つPackageの構造体へのポインタです。

https://golang.org/pkg/go/build/#Package

type Package struct {
        Dir           string   // directory containing package sources
        Name          string   // package name
        ...
        
        // Source files
        GoFiles        []string // .go source files (excluding CgoFiles, TestGoFiles, XTestGoFiles)
        
        ...

        Imports   []string                    // import paths from GoFiles, CgoFiles
        ImportPos map[string][]token.Position // line information for Imports

        // Test information
        TestGoFiles    []string                    // _test.go files in package
        TestImports    []string                    // import paths from TestGoFiles
        ...
        XTestGoFiles   []string                    // _test.go files outside package
        XTestImports   []string                    // import paths from XTestGoFiles
        ...
}

その後(3)で、抽出したパッケージ情報をbuildTestMain関数の引数として呼び出しています。

buildTestMain(前半)

https://github.com/DATA-DOG/godog/blob/master/builder.go#L272-L303

buildTetMain関数ではtestのmainとなるソースコードを生成します。 ここで生成されたコードがコンパイルされexec.Commandで実行されることでgodogは動いています。

func buildTestMain(pkg *build.Package) ([]byte, bool, error) {
    var contexts []string
    var importPath string
    name := "main"
    if nil != pkg {
        ctxs, err := processPackageTestFiles( // (1)
            pkg.TestGoFiles,
            pkg.XTestGoFiles,
        )
        if err != nil {
            return nil, false, err
        }
        contexts = ctxs
        importPath = pkg.ImportPath
        name = pkg.Name
    }

       ...
}

buildTetMainの前半で重要なのは(1)の箇所です。 受け取ったパッケージ情報の中から、godog_test.goのようなテストファイル の名前をprocessPackageTestFilesに渡します。

processPackageTestFiles

https://github.com/DATA-DOG/godog/blob/master/builder.go#L322-L347

processPackageTestFilesでは、受け取ったファイル名を go/parseParseFileメソッド に渡してASTを生成します (1)。

その後、生成したASTをastContextsに渡しメソッド名を抽出します (2)。

// processPackageTestFiles runs through ast of each test
// file pack and looks for godog suite contexts to register
// on run
func processPackageTestFiles(packs ...[]string) ([]string, error) {
    var ctxs []string
    fset := token.NewFileSet()
    for _, pack := range packs {
        for _, testFile := range pack {
            node, err := parser.ParseFile(fset, testFile, nil, 0) // (1)
            if err != nil {
                return ctxs, err
            }

            ctxs = append(ctxs, astContexts(node)...) // (2)
        }
    }
    
    ...
}

astContexts

https://github.com/DATA-DOG/godog/blob/master/ast.go

astContextsでは、受け取ったASTを解析して、 func (*godog.Suite)型の関数が存在していたら、その関数名を返します。

というわけでgodogがどうやって処理する関数を見つけ出しているかは、ここにかかれていました。

func astContexts(f *ast.File) []string {
    var contexts []string
    for _, d := range f.Decls {
        switch fun := d.(type) {
        case *ast.FuncDecl:
            for _, param := range fun.Type.Params.List {
                switch expr := param.Type.(type) {
                case *ast.StarExpr:
                    switch x := expr.X.(type) {
                    case *ast.Ident:
                        if x.Name == "Suite" {
                            contexts = append(contexts, fun.Name.Name)
                        }
                    case *ast.SelectorExpr:
                        switch t := x.X.(type) {
                        case *ast.Ident:
                            if t.Name == "godog" && x.Sel.Name == "Suite" {
                                contexts = append(contexts, fun.Name.Name)
                            }
                        }
                    }
                }
            }
        }
    }
    return contexts
}

buildTestMain(後半)

https://github.com/DATA-DOG/godog/blob/master/builder.go#L292-L303

processPackageTestFilesの処理が終わったら、buildTestMainに戻ります。

    if nil != pkg {
        ctxs, err := processPackageTestFiles( 
            pkg.TestGoFiles,
            pkg.XTestGoFiles,
        )
    ...


    data := struct {
        Name       string
        Contexts   []string
        ImportPath string
    }{name, contexts, importPath}

    var buf bytes.Buffer
    if err := runnerTemplate.Execute(&buf, data); err != nil { // (1)
        return nil, len(contexts) > 0, err
    }
    return buf.Bytes(), len(contexts) > 0, nil

buildTestMainでは、テンプレートにimportPackageprocessPackageTestFilesで抽出した情報を埋め込み、 testのmainとなるソースコードを生成します。

templateは以下のようになっており、 main関数を持つgoのファイルを生成していることがわかります。

https://github.com/DATA-DOG/godog/blob/master/builder.go#L30-L46

var runnerTemplate = template.Must(template.New("testmain").Parse(`package main

import (
  "github.com/DATA-DOG/godog"
  {{if .Contexts}}_test "{{.ImportPath}}"{{end}}
  "os"
)

func main() {
  status := godog.Run("{{ .Name }}", func (suite *godog.Suite) {
      os.Setenv("GODOG_TESTED_PACKAGE", "{{.ImportPath}}")
      {{range .Contexts}}
          _test.{{ . }}(suite)
      {{end}}
  })
  os.Exit(status)
}`))

実際にgodogのテストを実行するのはgodog.Run()の部分です。 godog.Run()の内部ではこれまでの処理で発見した、ステップ関数の実行を行う処理が書かれています。

ここまでで、ようやくbuildTestMainの処理が完了し、実行すべきtestmainソースコードが得られました。

Build(後半)

最後にBuild関数で得られたソースコードコンパイルします。 exec.Command(compiler, args...)(1)やexec.Command(linker, args...)(2)を実行して コンパイルが行われていることが確認できます。

func Build(bin string) error {
    
    (省略)

    src, anyContexts, err := buildTestMain(pkg)
    if err != nil {
        return err
    }
    
    (省略)

    args = append(args, "-pack", testmain)
    cmd = exec.Command(compiler, args...) // (1)
    cmd.Env = os.Environ()
    out, err = cmd.CombinedOutput() 
    if err != nil {
        return fmt.Errorf("failed to compile testmain package: %v - output: %s", err, string(out))
    }

    // link test suite executable
    args = []string{
        "-o", bin,
        "-buildmode=exe",
    }
    for _, link := range pkgDirs {
        args = append(args, "-L", link)
    }
    args = append(args, testMainPkgOut)
    cmd = exec.Command(linker, args...) // (2)
    cmd.Env = os.Environ()

    out, err = cmd.CombinedOutput()
    if err != nil {
        msg := `failed to link test executable:
  reason: %s
  command: %s`
        return fmt.Errorf(msg, string(out), linker+" '"+strings.Join(args, "' '")+"'")
    }

    return nil
}

まとめ

Godogがどのように実行されるかを理解するために実装を見てみました。 最初はGodogの使い方を解説する記事にしようとしていたのに、 いつのまにかGodogの内部の処理を追ってしまっていましたが、 go/buildgo/astなど普段はあまり使わない パッケージの使い方を知ることができてよかったです。

TDDをやっていて学んだこと

最近、TDDを会社でやっているので、学んだことをまとめておく。

学んだこと

  • TDDでは、まずテストを書き実行する。するとエラーになるので、すぐさまテストを通るようにコードを実装する。 テストが通るようになったら、リファクタリングをする。そしてまたテストを書く。このようにしてRed->Green->Refactoring繰り返す。

  • テストを書きRedの状態になったらすぐに、Greenになるようにコードを実装する。その際、コードを一般化して書こうとしないように気をつける。 とにかく一秒でも早くGreenにする。たとえば文字列を返すメソッドで"a"という文字列が返ってくることをテストで期待する場合は、return "a"だけを実装する。 その後、別のテストを追加し、両方のテストが通るように実装を変更する。

  • 設計はrefactoringのフェーズでおこなう。必ずテストがリファクタリングの前後で通っている状態になっているはず。

  • なにか迷ったらすぐにテストを実行する。答えはテスト結果に書いている。とにかく細かくテストを回す。

  • テストを何度も実行するので、テストの実行に時間がかかると効率が落ちる。Scalaだとsbtを起動するのに時間がかかるのでsbtは常に起動しておく。

感想

  • テストが整備されていないコードで途中からTDDをやるのは辛い、テストを書くのに時間がかかってしまう。
  • テンポよくリズムに乗って開発するには、そもそもその言語に習熟している必要がありそう。逆に言語の習熟度が上がるほど効率よく開発できそう。
  • TDDが良いと思ったのは、余計なことを考えずに手を動かせるところ。いつも先に設計を考えてしまってコードを書くのに時間がかかってしまっていたが、先にコードを書いてから設計を考えるほうが短い時間で効率的に実装できる気がする。