依存関係と階層構造の軛

21世紀現在のプログラミング言語において、モジュールという機能はほぼ必要不可欠である。ソースコードを分割し、明示的な依存関係を指定する仕組みであるモジュールは、以下のような様々な恩恵をもたらす。

  • インクリメンタルビルド: モジュールごとにコンパイル結果を保存し、変更されていない部分を再コンパイルするのを防ぐ。
  • 内部の隠蔽: 実装の詳細を隠蔽し、モジュール外から触れないようにする。プログラムの見通しをよくしたり、不正な操作をする機会を減らす。
  • アーキテクチャの整理: モジュールは他のモジュールを参照できるが、原則として相互参照はしない。依存の向きを定めることで、適切な抽象化と、 それに基づいた実装の分離を促す。

さて、いくらモジュールが便利と言えど、数が増えすぎるとさすがに扱いにくい*1。そのため、ディレクトリの構造をモジュールの階層構造として運用する仕組みが備わっていることが多い。 コンパイラから見れば、ドットなどで区切られたモジュール名から、対応するファイルを探すだけの話だ。あくまで人間の都合であり、上で挙げたような恩恵とはあまり関係してこない──だが、本当にそれでいいのだろうか。

若干わざとらしい例ではあるが、掲示板のアプリケーションを実装するに当たり、以下のようにモジュールを分割するとしよう。

UtilsとModelの二つのディレクトリを設ける。Model.Commentでは、投稿を表すデータ型や、データベースの操作を定義する。Utils.Miscには雑多な便利関数をまとめ、Utils.Markupでは、投稿をHTMLに変換する処理を記述する。

あからさまかもしれないがこの構造には問題がある。というのも、UtilsとModelsは、ディレクトリ単位で見ると、双方向に依存関係を持っているのだ。 先述した通り、コンパイラから見れば、モジュールがどこのディレクトリに属していようが本質は変わらないし、正しい入力である。しかし、開発者はディレクトリの分割に意味を見出しているという齟齬が発生する(そして、コンパイラはそれを指摘しようがない)。この齟齬を放置したまま開発を続けていくと、想定外に深い依存関係が発生してビルドが遅くなったり、「Modelに依存したUtils」という存在と辻褄を合わせるために、本来隠蔽すべき詳細がどんどん漏れ出したりしてしまう。

これを防ぐ手段として、それぞれのディレクトリをパッケージ化し、依存関係を明示するというものがある。これは双方向の依存を防ぐという意味では効果的な一方、パッケージごとのメタデータを管理するコストが高まったり、パッケージ単位でのキャッシュはできても、モジュール単位のインクリメンタルビルドが効きにくくなるなど、デメリットも無視できない。

ならば、新たに静的解析を実装し、こういった問題を検出しようではないか。まずはモジュールの依存関係のグラフを可視化して見通しを立てたい──dot形式に変換し、graphvizで表示するだけの簡単な話だ。

……どうやら、そんな簡単な話ではなかったようだ。

もう少し、ディレクトリ同士の依存関係に着目して考えてみよう。Foo.Bar.A.BがFoo.Baz.C.Dに依存しているとき、「BarがBazに依存している」という情報さえ残せば、それより深い部分の情報は削いでも構わない。つまり、以下のようなアルゴリズムでグラフを導き出す。

  • 依存元、依存先のモジュール名をドットで区切り、リストにする
  • どちらかのリストが空になったら、終了する
  • リストの先頭を見る
    • 名前が同じなら、先頭を取り除く
    • 名前が違っていたら、辺を作成する

「Foo.BarがFoo.Bar.Bazに依存している」のような関係は今回は考慮しない。もし考慮したい場合は、「リストが空になったら、辺を作成する」ように書き換えればよい。

このアルゴリズムを利用すると、親のディレクトリごとに分割されたグラフができ、graphvizのcircoを使うと図のようになる。最初のグラフとはえらい違いだ。

成分をクローズアップすると以下のようになる。ディレクトリに要約されているため、関係が読みやすくなっているのがわかる。

だが本題に戻ろう。ディレクトリの意義を保つためには、相互依存がない──いや、さらに有向閉路が存在しないことを保証したい。つまり、強連結成分分解すればよいのだ。早速会社のコードベースに適用してみると、かなりの大物が釣れた。各辺の重みはインポートの件数を表す。

このグラフは強連結であり、すなわちどの頂点の間にも道が存在する。本来、このようなことが発生しないようにパッケージを分割していたはずなので少々驚きの結果だ。パッケージが細かすぎたゆえに、抜け道ができてしまったのだろう。

有向非巡回グラフにするために取り除くべき辺はFeedback arc set(FAS)と呼ばれている。 最小のFASを求めるのはNP困難だが、今回のケースでは抜け道の重みが圧倒的に小さい。そのため、重い辺から順に再構築していき、閉路を生む候補だけ弾く貪欲法で実用的な結果が得られそうだ。

件のグラフについては、以下の四つを除去するとDAGになる。幸い、件数はそれほど多くないので、循環をなくすのはそれほど難しくなさそうだ。

Queries -> QueryServices
Effects -> JobWorker
SendGrid -> Effects
DomainObjects -> Effects

ここまでの処理を自動化するため、Haskellコンパイラプラグインとして実装した。もちろん、ここまでの議論はHaskell以外にも適用できるため、他の言語にも同等のものを実装することは可能なはずだ。

github.com

まとめ

今まではモジュールの階層構造に明確なルールがなく、ある意味飾りだった。しかし「ディレクトリ間の依存関係」という概念を導入することで、自然に「モジュールの依存関係がDAGであるように、ディレクトリの依存関係もまたDAGになる」という制約を導入でき、我々の直観とのすり合わせができた。この仕組みをクリーンアーキテクチャの促進・保守に活用していきたい。

PR枠

ここまで散々階層構造の話をしてきたが、HERPはオープンでフラットな組織を是としており、現在も積極的に技術者を募集している。興味のある方は、以下の資料を参照されたし。

github.com

*1:ワイルドカードを使うと、コマンドライン引数の長さが限界を超えてしまうなど、現実的な支障も発生する

株式会社HERPに転職しました

GitHubのプロフィールを見た人などはもしかしたら気づいているかもしれないが、Tsuru Capital LLCを退職し、2022年2月16日よりHERPの正社員となった。HERPは、大まかに言えば採用活動を管理するプラットフォームを提供している。

きっかけ

Tsuru CapitalはKospi(韓国株のインデックス)のデリバティブを半自動取引する企業で、Haskellを使っているというのが最大の特徴として知られる謎多き会社だ。2015年に入社し、2022年まで6年以上働いた。流石に同じ職場にずっといると経験が偏ってしまうし、感覚としても飽きがきたので転職を考えた。 また、ある時期からRustメインの開発をするようになったが、やはり自分の最大の強みであるHaskellを活かせる仕事をしたく、転職先を考える基準となった。 拙作のライブラリであるextensibleを使っているという情報もあったため、偵察がてらHERPに応募した。

入社までの流れ

採用プロセスを扱う企業なだけあってかなり迅速で、体験が良かった。

  • 2021/12/14: ウェブサイトから応募
  • 2021/12/15: カジュアル面談
  • 2021/12/16: 一次面接(構造化面接、事前のアンケートで答えた内容をもとに、前職の成果などについて話した)
  • 2021/12/21: 二次面接(価値観が適合するかどうかを、カジュアルな会話で確認した)
  • 2021/12/28: オファー面談

並行してリファレンスチェックを行った(上司、同僚、部下1名ずつを希望されたが、基本的に階層構造がない組織なので自分の裁量で3人選んだ)。

あまりにもスムーズというか、こちらが一方的に有利なように感じられたので、もう少し試して欲しかった気もする。だが、HERPの文化と自社の製品がなす候補者体験は確実に強みと言える。

現在

コードベースの品質を改善したり、新機能を実装したり、洗い物をしたりと自主的に色々なことをやっている。自分のスキルについて極端な不足や過剰を感じることはなく、コミュニケーションも盛んなため、面白い課題は尽きず、楽しくやっていけそうだと思う。開発者チームは適度にオタク性と社会性があり、キラキラしすぎていないところも好感を持てた。

かなり高い期待を受けて入社したので、それに応えるように成果を出していきたい。

リンク

Oath: 安全、高速、合成可能な並行処理

TL;DR

github.com

並行処理を簡潔かつ安全に記述できるライブラリを作った。ApplicativeDo拡張を使って、以下のようにoathの引数として与えたIOアクションを同時に実行し、結果を集める処理を書ける。いずれかが例外を投げた場合、残りをキャンセルするためリソースを漏らす心配がない。

evalOath $ do
   a <- oath $ ...
   b <- oath $ ...
   f a b

経緯

Haskellは並行処理が得意とされている。事実、軽量スレッド、MVar、STMといった処理系によるサポートが充実しており、HackageのConcurrencyカテゴリには235ものパッケージがあることからもユーザの関心の高さが窺える。 並行処理を実用する上では、単にスレッドをフォークするだけでなく、計算の結果を集める必要がある―—Scalaなどで言うFutureに近いものがあると嬉しい。案の定、並行計算の結果を取り出すためのHaskellライブラリは数多く作られてきた。

futuresというなかなかいい名前のパッケージがある。APIもかなりシンプルだ。 スレッドをフォークして、計算結果をMVarに代入し、MVarの中身を取り出すアクションを返すというものだ。

fork :: IO a -> IO (Future a)
fork io = do
  mv <- newEmptyMVar
  forkIO $ do
    a <- io
    putMVar mv a
  return $ Future $ readMVar mv

考え方はわかりやすいが、この実装には致命的な欠点がある―—例外処理である。forkに与えたアクションが例外を発生させても、誰も対応ができない。しかも、putMVarが呼ばれなくなるのでreadMVarが発散してしまう(実行時エラーになる)。これでは実用するのは難しい。また、forkIOの結果であるThreadIdが捨てられていることからわかるように、一度始めた計算を外部から止めるすべはない。

spawnは、Future型ではなく直接IOを返す点を除けばfuturesと似ている。

spawnTry :: IO a -> IO (IO (Result a))
spawnTry m = do
  v <- newEmptyMVar
  _ <- mask $ \restore -> forkIO (try (restore m) >>= putMVar v)
  return (readMVar v)

spawn :: IO a -> IO (IO a)
spawn m = do
  r <- spawnTry m
  return (r >>= either throwIO return)

こちらはきちんと例外処理をしており、putMVarが呼ばれることが保証されるためいくらか実用的だ。しかし、やはり計算は止められない。

promiseは、ApplicativeとMonadインスタンスであるPromise型が売りだ。

newtype Promise a = Promise { unPromise :: IO (Async a) }
  deriving (Functor)

instance Applicative Promise where
  pure = Promise . async . return
  Promise mf <*> Promise mx = Promise $ do  
      f <- mf
      x <- mx
      (f', x') <- waitBoth f x
      async $ return $ f' x'

instance Monad Promise where
   return = liftIO . return
   Promise m >>= f = Promise $ m >>= wait >>= unPromise . f 

liftIO :: IO a -> Promise a
liftIO = Promise . async

外側のIOでスレッドをフォークし、内側のAsyncで結果を待つという仕組みのようだ。だが、m <*> nはmとnをそれぞれ並行して実行したのち、両方の結果が返ってくるのをその場で待つ必要がある(「待つAsyncを返す」のではなく、「待ってからAsyncを返す」)。これでは(a *> b) *> ca *> (b *> c)の挙動が異なってしまうため、Applicativeの則を満たさない。また、Asyncは本来cancel`できるはずだが、合成中に結果を待ってしまうので事実上中断ができない(どちらにせよ、Promiseの実装が隠蔽されているのでどうしようもないが)。 さらに、Monadは左の計算の結果を待ってから右に進むという挙動で、Applicativeとの一貫性がない。いくらインスタンスがあっても、これでプログラムを組み立てるのは難しいだろう。

非同期処理の定番であるasyncパッケージには、Concurrentlyという型がある。

newtype Concurrently a = Concurrently { runConcurrently :: IO a }

instance Applicative Concurrently where
  pure = Concurrently . return
  Concurrently fs <*> Concurrently as =
    Concurrently $ (\(f, a) -> f a) <$> concurrently fs as

instance Alternative Concurrently where
  empty = Concurrently $ forever (threadDelay maxBound)
  Concurrently as <|> Concurrently bs =
    Concurrently $ either id id <$> race as bs

(<*>)concurrently :: IO a -> IO b -> IO (a, b)を使って両方の結果を待つ計算を表現し、(<|>)race :: IO a -> IO b -> IO (Either a b)はどちらかが返ってくるまで待つ計算を表現する。promiseと違い、その場で待機する必要がないので、Applicative則を満たしそうだ。 concurrentlyおよびraceは、スレッドを必ず二つフォークする上、かなり複雑な実装なので、オーバーヘッドが大きそうだ。ここまで見た中では一番正しそうで使いやすそうな実装だが、もっといい方法はないだろうか。

継続とSTMのコンボ

非同期処理を安全に合成する方法には覚えがある。単純で頑強なメッセージングシステム、franz - モナドとわたしとコモナドで紹介した、継続渡しを用いて結果を待つトランザクションを渡すという仕組みだ。この方法なら、継続が終了したタイミングで処理を中断できるため、待つもやめるも自由自在、お漏らしの心配はない(franzはこのメカニズムによって非同期リクエストを管理している)。そのエッセンスを独立したライブラリに蒸留できそうだ。それっぽい名前はだいたい取られていたので、Promiseからの連想でOathと名付けた。

github.com

newtype Oath a = Oath { runOath :: forall r. (STM a -> IO r) -> IO r } deriving Functor

instance Applicative Oath where
  pure a = Oath $ \cont -> cont (pure a)
  Oath m <*> Oath n
    = Oath $ \cont -> m $ \f -> n $ \x -> cont (f <*> x)

Oathは、IO (STM a)CPS変換したもので、Compose (Codensity IO) STMと等価である*1 *2。外側のIOで計算を起動し、内側のSTMで結果を待つ。OathApplicativeインスタンスを持ち、STM (a -> b)STM aを用意してから、それらを合成したSTM bを返す――計算の起動と、結果の待機を別々に合成するというわけだ。

oath :: IO a -> Oath a
oath act = Oath $ \cont -> do
  v <- newEmptyTMVarIO
  tid <- forkFinally act (atomically . putTMVar v)
  let await = readTMVar v >>= either throwSTM pure
  cont await `finally` killThread tid

oathは、IOアクションを別のスレッドで実行し、その結果をTMVar経由で取り出す。forkFinallyが例外を受け止め、throwSTMがそれを伝える。

生殺与奪の権は継続が握っており、終了したときにThreadKilled例外が投げられる。このような挙動をwithAsyncなどで安全に表現しようとすると、withAsync foo $ \a -> withAsync bar $ \b -> ...のように ネストが深くなってしまいがちだが、Oathは継続渡しの抽象化によって、combine <$> oathSTM foo <*> oathSTM barのようにフラットに書ける。それだけでなく、traverseでコンテナに対しても簡単に適用できるという利点もある。

Oathを実行するには、単にevalOathを呼び出す。もちろん、runOathを直接呼ぶべき場面もある。

evalOath :: Oath a -> IO a
evalOath m = runOath m atomically

Alternative<|>は、Concurrentlyと同様両方の計算を起動するが、一方が完了した段階でもう片方はキャンセルする(STMのAlternativeインスタンスを継承している)。 Control.Concurrent.STM.Delayのラッパーも提供しており、<|>で合成するだけで、タイムアウト処理を非常に簡単に記述できる。 また、「リソースの確保」「解放」「使用」という三つの挙動を一つにまとめられるという継続渡しの強みがdelayの実装によく表れている。

instance Alternative Oath where
  empty = Oath $ \cont -> cont empty
  Oath m <|> Oath n = Oath $ \cont -> m $ \a -> n $ \b -> cont (a <|> b)

delay :: Int -> Oath ()
delay dur = Oath $ \cont ->
  bracket (newDelay dur) cancelDelay (cont . waitDelay)

Concurrentlyと違い、Oathはフォークは必須ではないのもポイントだ。例えばネットワーク経由でリクエストを送信する処理は書いた順序で実行し、結果を待つ部分だけ非同期にするといった実装もできる。forkOnなど、forkIO以外のフォークも使えるため自由度が高く、決定性が求められる単体テストの実装などにも役に立つだろう。

パフォーマンス

最後に、Concurrentlyと比較するためのベンチマークを行った。他のパッケージはまともに動作しないため、評価の対象から外した(単体テストは残してある)。

  , bench "oath STM 100" $ nfIO $ O.evalOath $ traverse (O.oath . pure) [0 :: Int ..99]
  , bench "async 100" $ nfIO $ A.runConcurrently $ traverse (A.Concurrently . pure) [0 :: Int ..99]
  oath IO 10:   OK (0.86s)
    3.18 μs ± 206 ns
  oath STM 10:  OK (0.34s)
    5.10 μs ± 169 ns
  async 10:     OK (0.66s)
    10.0 μs ± 190 ns
  oath IO 100:  OK (0.60s)
    35.8 μs ± 2.4 μs
  oath STM 100: OK (0.39s)
    48.0 μs ± 1.3 μs
  async 100:    OK (0.21s)
    100  μs ± 5.6 μs

オーバーヘッドはConcurrentlyの約半分に抑えられている。Concurrentlyは(<*>)の左右ごとにスレッドをフォークするため、項の二倍フォークする必要があるという点が表れているのだろう。

まとめ

Oathは、継続渡しスタイルとSTMを組み合わせることによって、柔軟、安全、高速、そして合成可能な非同期処理の表現を可能にした。単にIOアクションを組み立てる道具としても便利だが、今後はOathに基づいたAPIデザインにも一考の余地があると考えている。並行処理の新定番を狙っていきたい。

新しいGHC拡張、NoFieldSelectorsについて

今まで不満の多かったHaskellのレコードの扱いを改善するための一歩として、NoFieldSelectorsというGHC拡張の実装を進めている。

動機

Haskellにはレコードを定義するための構文がある。

data User = User
    { userId :: Int
    , userName :: Text
    }

こう定義すると、各フィールドごとにuserId :: User -> IntuserName :: User -> Textというゲッターに相当する関数が生成される。これらの関数は特別な意味合いを持っており、以下のレコード操作の構文にも利用できる。

  • 構築 User { userId = 0, userName = "Zero" }
  • パターンマッチ case foo of User { userId = x, userName = name } -> ...
  • 更新 foo { userId = 1 }

しかし、フィールドと同じ名前の関数こそが使いづらさの原因となっている。 多くのプログラミング言語では、構造体のフィールドはそれぞれ固有の名前空間に属するが、Haskellはそうではない。以下のような定義は、idUserなのかArticleなのか、それともPreludeid :: a -> aなのか判別できないため、実際には使えない。

data User = User { id :: Int, name :: Text }
data Article = Article { id :: Int, title :: Text }

そのため、userIdarticleIdのように型名を接頭辞にするのが通例となっている。 するとタイプ数が増えるばかりか、JSONなどのフォーマットに変換する際に接頭辞を切り取るための仕組みなども必要になり、使い勝手がよくない。lensや拡張可能レコードなどの技法で改善できる面もあるものの、RecordWildCardsNamedFieldPunsなどの構文的な支援や、網羅性のチェックが受けられなくなるのは痛い。

DuplicateRecordFields拡張を用いれば、複数のデータ型で同じフィールド名を採用することも一応許される。しかし、ゲッター関数がどのデータ型に属するか判定するためのマジカルな実装があり、進んで使いたいものではないのが実情である(そのハックを無くす提案が最近受理された *1 )。

忘れがちだが、複数のコンストラクタを持つデータ型においてもレコードの構文は使える。その場合、対応するコンストラクタ以外にはエラーを出す部分関数が生成されるため大変使い勝手が悪く、実質的にないものとして扱われている。

提案

そんな問題を解決するアプローチとして、NoFieldSelectorsという拡張が提案された。

github.com

この拡張を有効にすると、レコードを定義しても、ゲッター関数としては使えなくなるが、レコードの構文としては使える――つまり、短い名前のデメリット(コンフリクト)をなくし、メリット(簡潔なコード)だけを得られるというわけだ。DuplicateRecordFieldsと併用すれば、複数のデータ型で同じフィールド名を気兼ねなく定義できる。

目の上のたんこぶだったゲッター関数の問題を回避できれば、他の言語と遜色ないレコード操作が可能になり、レコード自体の採用率も高まることが予想される。 プレーンなデータ型で起きがちな、変更に伴う破壊や、値の順番を間違えるバグを回避しやすくなり、Haskellの強みの一つであるジェネリクスを使った導出機構を活用できる場面も増える。

さらに、いずれ実装されるであろうRecordDotSyntax(プロポーザル, 日本語の紹介スライド)の実用性を飛躍的に高めるだろう。

要約すると、NoFieldSelectorsは以下のメリットをもたらす。

  • フィールド名に接頭辞を付けなくてよくなる
  • instance FromJSON Fooのように、そのままインスタンスを導出できる場面が増える
  • 今までは単なるバッドプラクティスだった、複数コンストラクタのレコードが実用的になる
  • 害を及ぼす心配なくレコードを導入できる

実装

提案者のSimon Hafner氏により、フラグの追加や試験的な実装が作られ、私が実際に機能する段階まであらかた完成させた。現在はレビュー段階にある。

Implement NoFieldSelectors (!4017) · Merge Requests · Glasgow Haskell Compiler / GHC · GitLab

単に関数の生成をやめればいいかと思いきや、そこまで単純な話ではなかったようだ。各種レコード操作をコンパイルするときの振る舞いは、ゲッター関数の存在を前提としている。それを省いてしまうと、単なるレコードでないデータ型と同じになってしまうのだ。フィールドに相当するシンボルは今まで通り作られるが、項としてコンパイルするときはそれを隠す、というアプローチをとった。この辺りは、DuplicateRecordFieldsなどの機能との兼ね合いで泥臭いものとなったが、Adam Gundry氏の助言のおかげで実装まで持っていくことができた。

このブランチはGHC 9.2までにはマージできるようにしたい。NoFieldSelectorsは、今まで避けようのなかった慣習を覆す機能であり、これが広まればGHC/Haskellという言語の全体像が変わるに違いない。まだ捕らぬ狸の皮算用でしかないが、GHCのレコードの進化を楽しみにしていただきたい。

2021/02/17 追記 Adam Gundry氏がGHCのレコード周りの内部仕様をブラッシュアップしたため、実装をリベースして再投稿していただいた。そしてついに16日、masterにマージされた。

gitlab.haskell.org

将来

PolyKindsやStrictDataと同様、NoFieldSelectorsはモジュール単位でしか振る舞いを制御できない。将来的には、データ型単位で挙動をコントロールしたり、その旨をドキュメントにも反映させるための仕組みが必要であると考えている。

動的配列の無難なHaskell実装

qiita.com

C++、Rust、Pythonなど、他の言語では当たり前のように多用される動的配列だが、Haskell実装は(開発を始めた時点では)見当たらなかったので作ってみたお話*1

動的配列とはミュータブルな配列の一種で、通常の配列操作だけでなく、末尾への要素の追加・削除が定数時間で行える構造である。確保しておいた領域がいっぱいになったら、その2倍の大きさの領域を確保するという方法によって、漸近的には要素の追加は定数時間となる。

内部の配列には、デファクトスタンダードであるvectorパッケージを用いる。Vectorには無印(boxed)、Unboxed、Storableの三種類の変種があり、それぞれ以下のように使い分ける。

  • 無印(Data.Vector): サンク含め、任意のHaskellのオブジェクトを格納できる。Traversableなどのインスタンスであり、汎用性が高い
  • Unboxed (Data.Vector.Unboxed): ポインタを経由せず、要素がメモリ上に連続的に配置される。タプルはfst側の配列とsnd側の配列の二つが内部で作られる。効率が求められるときに使う
  • Storable (Data.Vector.Storable): Storableクラスを通してメモリ上の表現と対応させる。外部のライブラリと連携したい際に有用

それぞれにミュータブル版(.Mutable)のモジュールも存在する。幸運なことに、これらのAPIを共通化するData.Vector.Genericというモジュールがあるので、それを土台として実装していく。完成したのがこれだ。

github.com

hackage.haskell.org

実装のポイント

vectorAPIは、primitiveパッケージによって抽象化されており、IOとSTの違いを吸収できる。こちらもそれに合わせて設計する。

data GVState v s a = GVState !Int !(v s a)

-- | 'Growable' is a dynamic vector based on mutable vector @v@.
newtype Growable v s a = Growable (MutVar s (GVState v s a))

Vectorの実装を表すパラメータv、世界の型を表すパラメータs、要素の型aを引数に持つGrowableを定義する。IORefの一般化であるMutVarに格納し、配列を入れ替える挙動を可能にする。 配列の末尾に要素を追加する操作pushを定義してみよう。

-- | Append an element to the vector (not atomic).
push :: (PrimMonad m, MVector v a) => Growable v (PrimState m) a -> a -> m ()
push (Growable ref) val = do
  GVState len vec <- readMutVar ref
  vec' <- if MV.length vec == len
    then MV.unsafeGrow vec (max 1 len)
    else pure vec
  writeMutVar ref $ GVState (len + 1) vec'
  MV.write vec' len val
{-# INLINE push #-}

定義について特筆すべきことはないが、ここではINLINE化が重要になってくる。インライン化しないと、PrimMonadMVectorも辞書渡しになってしまい、実行時のパフォーマンスに大きな影響を及ぼす。プリミティブな動作を定義するコードでは特に影響を受けやすいため、辞書渡しされないようしっかり対策を忘れないようにしたい。

まとめ

Haskellのエコシステムは、ありそうなものがないということが多々ある。自作する際も、ベストプラクティスをしっかりと押さえ丁寧に実装していきたい。

なお、当初はアトミック(複数のスレッドが同時に実行しても干渉せず正しく動く)なpushを実装する予定だった。アルゴリズムはさほど難しいものではないが*2、BoxedおよびUnboxed Vectorに対するCASを実装する必要があり、時間がなかったため断念した。しかし、役に立つ場面は必ず出てくるはずなのでいずれ実装したい。

追記 バージョン0.0.1で、ロックフリー版のatomicPushとatomicPopを追加した。

*1:改めて確認すると、grow-vector: Mutable vector with efficient appendsというパッケージが最近アップロードされたようだ

*2:Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup - Lock-free Dynamically Resizable Arrays

liszt: Append onlyでリーダーとライターが分離されたKVS

adventar.org

以前仕事で使おうとして没になったアイデアを改めて記事にまとめる。

動機

以前書いた記事で説明したものとほとんど一緒である。

fumieval.hatenablog.com

プログラムのログをリアルタイムに監視する仕組みが欲しいが、その仕組みがダウンしても監視対象には影響を及ぼさないようにしたいというのポイントだ。 そのため、ライター側はファイルに書き込み、リーダーはinotifyなどでファイルを監視するという、書き込みにサーバーを必要としない仕組みにした。 さらに、途中でクラッシュしても問題ないよう、ファイルはappend-onlyとし、ファイルの最後にページを書き込む。そのため、ページはなるべく小さくしたい。

ログしたいデータは大きく分けてスナップショットとイベントの二種類あり、内容に応じて20本程度のチャネルに分ける。それぞれのチャネルは、ペイロードのリストからなる。つまり、構造としてはMap Key [Value]のような感じとなる。 これらの点を総合し、Skew binary random access list2-3木に格納することにした。

  • Skew binary random access listは、完全二分木のリストからなる構造で、consは常に定数時間、任意の要素の取り出しが対数時間という特徴がある。
  • 2-3木はB木の特殊な場合で、ノードは2つか3つの子を持つ。

どちらも分岐が少ないため、append-onlyにしたときの空間的なオーバーヘッドが少ない(ただし、読み込むときのシーク回数が多く、パフォーマンスは悪い)。物は試し、さっそく実装してみた。

実装

github.com

バイナリ表現は以下のようになった。KeyおよびPayloadはバイト列で、ファイルに直に書き込む。アスタリスクはポインタを表す。

Node:
    Empty node: 0x00
    1-leaf: 0x01 *Key Spine
    2-leaf: 0x02 *Key Spine *Key Spine
    2-node: 0x12 *Node *Key Spine *Node
    3-node: 0x13 *Node *Key Spine *Node *Key Spine *Node

Spine: Int [Int *Tree]

Tree:
    Tip: 0x80 *Payload
    Bin: 0x81 *Payload *Tree *Tree

ライターのAPIは、モナドを活用したシンプルなものになった。Transactionモナドは、まだ書き込まれていないノードなどを管理しており、commitFileを実行すると内容を一斉に書き込む。

commitFile :: FilePath -> Transaction a -> IO a
insert :: Key -> Builder -> Transaction ()

ノードを表すデータ型を多相化し、各要素は「既にファイルに書き込まれたノード」「まだ書き込んでいないノード」のどちらかを含むStagePointer型で表した。コミットする際に再帰的にStagePointerをファイルのオフセットに変換するというHaskellらしいアプローチができた。

data StagePointer = Commited !RawPointer | Uncommited !(Node StagePointer) deriving Eq

data TransactionState = TS
  { dbHandle :: !LisztHandle
  , currentRoot :: !(Node StagePointer)
  , currentPos :: !Int
  }

type Transaction = StateT TransactionState IO

なお、insertの引数はByteStringではなくBuilderになっているため、アロケーションを抑えながらデータを書き込める。これは標準のBuilderではなく、最強にして最速のビルダー、mason - モナドとわたしとコモナドで紹介した自作のビルダーを使っている。標準にはないhPutBuilderLen関数が書き込んだペイロードのバイト数の取得を可能にしている。

リーダー(サーバー)側の実装には、クロスプラットフォームなファイル監視ライブラリのfsnotify: Cross platform library for file change notification.を使った。 クライアントとサーバーのコミュニケーションのプロトコルにはJSONを採用した。DerivingViaを使ってFromJSONとToJSONのインスタンスを導出するライブラリ、deriving-aesonで簡単に実装できる。 なお、レスポンス部分に関しては、sendfile(ユーザランドを介さずにファイルデスクリプタ同士でデータを転送するシステムコール)を使う都合上単純なバイナリフォーマットにした。

data Offset = SeqNo !Int
  | FromEnd !Int
  deriving (Show, Generic)
  deriving (FromJSON, ToJSON) via CustomJSON '[SumObjectWithSingleField] Offset

data Request = Request
  { reqKey :: !Key
  , reqTimeout :: !Int
  , reqLimit :: !Int
  , reqFrom :: !Offset
  , reqTo :: !Offset
  } deriving (Show, Generic)
  deriving (FromJSON, ToJSON) via PrefixedSnake "req" Request

実際に動かしてみるとこんな感じだ。まず、ライターのAPIを使ってデータベースに書き込む。

*Database.Liszt> :set -XOverloadedStrings
*Database.Liszt> commitFile "msg.liszt" $ insert "message" "hello" >> insert "message" "world" 
*Database.Liszt>

次にサーバーを立ち上げる。

$ cabal run lisztd

雑な作りだがコマンドラインツールも用意している。0番目から1番目までのペイロードを読み出し、改行区切りでターミナルに出力する。

$ cabal run liszt -- msg.liszt message -r 0:1 -f "%p\n"
Up to date
hello
world

無事動作が確認できた。

所感

凝った木構造全般に言えることだが、最も簡単であるはずの2-3木への挿入ですら分岐が多く(https://github.com/fumieval/liszt/blob/master/src/Database/Liszt/Internal.hs#L291)、実装するのに手間がかかった。QuickCheckを活用しながらまずは純粋に実装し、のちに本実装に書き換えるというアプローチをした。 Append onlyなDBMShttps://couchdb.apache.org/という先例がある(cf. The Power of B-trees)。あちらはかなりリッチなAPIを用意しており、実装の複雑さは計り知れない(少なくとも、私一人では実装できる気がしない)。DBというのは往々にしてそういうものなのかもしれない。

自動printfデバッグ

関数をデバッグするために、引数と戻り値をそれぞれ表示するというのを誰しもやったことがあると思う。今回はそれを自動化するからくりをHaskellで実装してみる。

目標となるのは、関数が与えられたとき、その引数と結果をターミナルに出力する関数に変換する高階関数probe :: Traceable a => String -> a -> aである。

testDelay :: Double -> Double -> IO ()
testDelay dur dur' = threadDelay $ round $ (dur + dur') * 1000000
*Probe> probe "testDelay" testDelay 1 2
testDelay 1.0 2.0: ()

これは型クラスを活用すればお茶の子さいさいである。以下のように型によって挙動を切り替える関数withTraceDataを定義すればよい。

  • 関数r -> aは、rの値を文字列にしてリストに積み、aについても再帰的にwithTraceDataを適用する。
  • IOアクションからは結果が返されるとみなし、与えられた引数のリストと結果を表示する。

実装するとこのようになる。

module Probe (Traceable(..), probe) where

import System.IO
class Traceable a where
    withTraceData :: String -- 名前
      -> [String] -- 文字列化した引数
      -> a -> a

instance (Show r, Traceable a) => Traceable (r -> a) where
    withTraceData name args cont arg = withTraceData name
      (showsPrec 11 arg "" : args) -- showsPrecを使うことで適切に括弧を表示する
      (cont arg)

instance Show a => Traceable (IO a) where
    withTraceData name args m = do
        hPutStr stderr $ unwords (name : args) ++ ": "
        hFlush stderr
        a <- m
        hPrint stderr a
        pure a

probe :: Traceable a => String -> a -> a
probe name = withTraceData name []

このままでは純粋な関数には使えないので、unsafePerformIOを使ったインスタンスも作っておこう。

newtype Result a = Result { unResult :: a }
instance Show a => Traceable (Result a) where
    withTraceData name args (Result a) = Result $ unsafePerformIO $ withTraceData name args $ pure a

Traceable Intなどを直接定義せず、まずnewtypeへのインスタンスとして定義するのには理由がある。 Haskellの多引数関数はカリー化されており、「a -> b -> cb -> cを結果として返す関数」でもあるため、どこで区切るかがwell-definedではない。そのため、明示的な型によって区別することは理にかなっている。 さらに、他のプリミティブ型の定義をDerivingViaとStandaloneDerivingによって簡潔に書けるという最近のGHCならではの利点もある。

deriving via Result Bool instance Traceable Bool
deriving via Result Int instance Traceable Int
deriving via Result Double instance Traceable Double
...

小さなコードではあるが、ここで紹介したテクニックは日常で役に立つに違いない。 この手法は色々と応用が利く。例えば、printする代わりにシリアライズして外部のファイルに書き込めば、probe関数を刺して動かすだけでテストケースを抽出できる道具にもなる。

最近やる気が出てきたので、これらのアイデアをそのうちライブラリにまとめるかもしれない。