Haskellのnothunksライブラリーはメモリーリークを過去の遺物とする長い道のりを行く
2020年9月24日 Edsko de Vries 読了時間25分
不定期の技術ブログ、「Developer Deep Dive（開発者が掘り下げる）」シリーズでは、IOHKのエンジニアを招き、最新の作業やインサイトについて紹介します。
Haskellは遅延評価を用いた言語である。遅延評価の重要性はいたるところで議論されている。Why Functional Programming Matters（関数型プログラミングが重要である理由）は本テーマの古典に挙げられる。また、A History of Haskell:Being Lazy with Class（Haskellの歴史：クラスで怠惰になる）でもこの議論に多くを割いている。本ブログの目的のため、ここでは遅延評価が望ましいものであることを前提とする。ただし遅延評価には代償が伴う。その欠点としてはメモリーリークが挙げられるだろう。これは時に検出が困難なこともある。この記事では、こうしたリークの大規模なクラスを早期発見し、デバッグに役立てることを目的とした、nothunksと呼ばれる新ライブラリーを紹介する。このライブラリーはCardanoブロックチェーンに関連して開発されたが、他のプロジェクトにも幅広く流用できると確信している。
モチベーション例
次の小規模な適用を考えてみる。受信する文字数を処理し総文字数を報告する。また文字ごとの統計も行う。
このコードバージョンでは、文字ごとの統計は単純に各文字が現れる頻度を表している。このコードに「aabbb」をフィードすると、文字数は5で、うち2つは「a」、3つは「b」であると返ってくる。
さらに、アプリケーションに巨大なデータをフィードし、メモリープロフィールを構築すると、
図1で見るようにアプリケーションは一定のスペースで実行される。
図1：例1のメモリープロフィール
ここまではいいだろう。しかしここで無難に見える変更を加えてみよう。各文字の発生頻度に加えて、ファイル内でその文字が発生した直近のオフセットも調べると、
アプリケーションは想定通りに作動する
そして、変更はGitHubのPRコードレビューで承認され、マージされる。しかし、コードは作動するものの、かなり遅くなる。
作業量がさほど増えたわけでもないのに、スピードはほぼ1桁下がる。明らかに何かがおかしい。明らかにメモリーリークが生じている（図2）。
図2：例2のメモリープロフィール
残念ながら、このようなプロフィールをコード内の実際の問題まで追うことは、非常に困難だ。さらに悪いことに、変更によりデグレードがもたらされたが、アプリケーションは普通に作動しており、テストスイートはおそらく失敗となることはない。こうしたメモリーリークはプロダクションにおいて不具合が生じるほど悪くなって初めて検知される（サーバーのメモリーが枯渇するなど）。ここまで来ると、緊急事態だ。
ここで確認しておくが、このブログの目的は、いかに「nothunks」がこうした問題を早期に検知し、デバッグするのに役立つかを解説することである。
コードの挿入
ではまず、nothunksの使用がどのように表示されるか例で見てみよう。コードを変更して新しいクラスインスタンスを「AppState」用に導出する。
NoThunksのクラスはnothunksライブラリーで定義されている（詳細は後述）。加えて、「foldl’」を新しい関数と置き換える。
「repeatedly」の定義方法は後に見ることにして、今はとりあえず「foldl’に少し魔法をかけたもの」と考えておこう。コードを再び実行すると、アプリケーションはほぼ即座に例外を投げる。
nothunksライブラリーの本質は、特定の値が予想外のサンクを含む場合にチェックできるということであり、これこそAppStateにサンクを不注意に導入しないようrepeatedlyが使用しているものだ。このチェックが失敗し、例外を引き起こしている。HasCallStackバックトレースを使ってサンクを導入した場所を特定する。さらに、より重要なことに、この例外はサンクの場所を特定するうえでに役立つ。
このコンテクストにより、AppStateにタプルを含むMapが含まれていることがわかる。このすべてはWHNF（サンクではない）であったが、タプルにWHNFではないIntが含まれていた。これがサンクである。
このようなコンテクストから、何が間違ったかが明らかとなる。Strict Mapを使用しているが、Mapを遅延ペア型にインスタンス化しており、Mapはペアを強制するがペアの要素の強制はしない。さらに、サンクを導入した瞬間に例外を得る。これはこのようなデグレードをテストスイートで捕捉できることを意味する。ここで、サンクの結果となる最小反例を構築することもできる（後述）。
Nothunksの使用
ライブラリーの仕組みを解説する前に、まずこれがどのように使用されるかを見てみよう。前章では、摩訶不思議な関数「repeatedly」を使用したが、これをどのように定義するかまだ説明していない。ここではこの関数について見てみる。
repeatedlyとfoldl’の唯一の違いはunsafeNoThunksのコールである。これは所与の値が予想外のサンクを含むかを確認する関数である。この関数は「unsafe」とマークされている。これは値に拘わらずサンクは通常Haskellで検知不可能なためだ。これを検知可能にすることで等式推論が破れる。したがってこれはデバッグもしくはアサーションにのみ使用されるべきだ。repeatedlyが提供された関数ｆをアキュムレーターを更新するために適用するたびに、結果として得られる値がいかなる予想外のサンクも含んでいないことを確認する。含まれている場合には、エラーとなる（実際のコードではこのようなチェックはテストスイートでのみ可能となりプロダクションでは不可能である）。
ここで強調しておくべきは、repeatedlyは、unsafeNoThunksをコールする前に値をWHNFにするということだ。これはもちろん、strict fold-leftをstrictにするものであり、repeatedlyがfoldl’の代替となるうえで欠かせない。しかし、repeatedlyがこれを行わない場合に、unsafeNoThunksのコールにより自明かつ即座にサンクが報告されると理解することは重要だ。結局のところ、私たちが作成したのはｆ ｂ a サンクである！一般に、unsafeNoThunks（またはそのIOバージョンであるnoThunks）をすでにWHNFでない値にコールしても無駄である。
一般に、長寿命のアプリケーションステートは想定外のサンクを一切含むべきではない。そうすれば同種のパターンの異なるシナリオを適用できる。例えば、ほぼ純粋なコードベース上に薄いIO層であるサーバーがあるとする。アプリケーションステートはIORefに保管されている。ここでも、IORefが絶対に予想外のサンクを含む値を指すことがないようにしたい。
checkがすでにIOにあるため、安全でないピュアラッパーを使用する代わりにnoThunksディレクトリーを使用することができる。ただしそうしないとこのコードは非常に類似したパターンを辿る。サンクを導入するや否や、代わりに例外を投げるのである。例えばStateTで非常に似たことができるのではないかと想像する人もいるだろう。put内のサンクのチェックである。
最小反例
一部のアプリケーションではプログラムへのインプットと、作成されるや否やのサンクとの間に複雑なやり取りが生じる場合がある。これについて、やや複雑ながらも願わくば理解しやすい例で検討する。AとBという2種類のイベントを処理しているサーバーがあるとする。
サーバーの内部ステートは2つのカウンター、AとBからなる。Aイベントが生じるたびに、最初のカウンターがインクリメントされる。Bイベントが起こると、aとbが1に達していないときのみインクリメント1、その他の場合には2となる。残念ながら、コードにはバグが含まれている。こうしたケースの1つに、サーバーステートの一部は強制されず、サンクが導入される。（免責事項：このブログ内の抜粋コードはコーディングの好例であることではなく、メモリーリークが導入される場所を明確にすることを意図している。通常、メモリーリークはコードの修正によってではなく、適切なデータ型を使用することによって避けるべきである）
したがって、バグを示す最小反例は2つのイベント、AとBが生じ（順不同）、もう1つBイベントが続く。例外を導入すると即座に例外を得ることから、このようなバグの検知にquickcheck-state-machineのようなフレームワークを使用して、こうした最小反例を構築することができる。
ここにテスト設定方法の一例を示す。quickcheck-state-machine（QSM）の作用を説明することは、本ブログの主旨から大幅にそれる。An in-depth look at quickcheck-state-machineは取っ掛かりとして適切だろう。本ブログでは、QSMでリアル実装とある種のモデルに「コマンド」を出すことにより両者を比較して、レスポンスマッチを確認するということだけわかれば十分である。ここで、サーバーとモデルの両方が更新関数を使用するが、「リアル」な実装は上記のStrictIORef型を、模擬実装は純粋なコードをサンクチェックなしで使用する。したがって、リアル実装をモデルと比較するとき、レスポンスはリアル実装が例外（サンクにより生じた）を投げるたびに異なることになる。
（ここではMunihac 2019 hackathonで紹介された新しいLockstepマシンをQSMで使用する）
このテストを実行すると、期待した通りに最小反例が得られる。HasCallStackバックトレースとコンテクストにより、正確にlazyペア内にサンクがあることがわかる。
最小反例、明確なコンテクスト、バックトレースの組み合わせにより、こうしたメモリーリークの検知がほぼ自明となる。
フードの下
nothunksライブラリーのコアはNoThunksのクラスである。
すべてのNoThunksのクラスメソッドが、インスタンスがそうであり得る、そして非常に多くの場合そうであるように、まったく空の、もしくは-同等に-DeriveAnyClassを使用して導出されたデフォルトを持つ。
noThunks関数はアプリケーションコードの主要エントリーポイントであり、その使用状況はすでに見た。しかしながらNoThunksのインスタンスは、NoThunksの再定義をほぼ必要とすることはなく、デフォルト実装で使用できる（後述）。反対に、wNoThunksはアプリケーションコードにはほぼ役に立たないが、データ型専用のロジックがあるところでnoThunksのデフォルト実装によって使用される。これに関しては数例を紹介する。最後にshowTypeOfはサンクコンテキストを構築する際に型の文字列表現を構築するために使用する。Geenricに関してはデフォルトがある。
noThunks
ペアにサンクが含まれるかをチェックすることにする。パターンマッチを行う前に、まずペアそのものがサンクである可能性を調べる。結局のところ、ペアにパターンマッチを行うと強制されるため、これがサンクであった場合、後からでは判別できなくなる。したがって、noThunksはまず値そのものがサンクであるかをチェックし、そうでなかった場合にwNoThunksをコールする。wはWHNFを意味する。wNoThunksは、そのアーギュメントがそれ自身サンクではなく、パターンマッチをかけられると（前提条件が満たされていると）推定できる。
注：wNoThunksがコールされると型a（の文字列表現）はすでにコンテクストに追加されている。
wNoThunks
ほとんどのデータ型専用の作業はwNoThunksで起こる。つまりパターンマッチが行えるということである。シンプルな例から始めよう。ストリクトペアの型のマニュアルインスタンスである。
ペアそのものがWHNFであることは検証済みであるため、単に両コンポーネントを抽出し、双方に再帰的にnoThunksをコールする。関数allNoThunksはヘルパーであり、複数のサンクチェックを実行し、サンクが最初に報告された時点で止まるというライブラリーで定義されている。
時に、特定のサンクを許可したいときもある。例えば、totalフィールドがキャッシュされた整数のセットがあるが、実際に使用された場合のみ合計を計算するものとする。
totalはサンクであることを許可する必要があるため、wNoThunksで飛ばす。
こうした構築はおそらく慎重に使用されるべきものだ。セット内のさまざまな操作が慎重に定義されなければ、セットはあらゆる種類のデータをtotalサンクを通じてキープすることもある。このようなコードには熟慮と注意深いレビューが必要となる。
ジェネリックインスタンス
wNoThunksに実装が与えられなかった場合、GHCジェネリックに基づいたデフォルトが使用される。すなわち、Genericを実装した型の場合、NoThunksインスタンスの導出は上記AppStateの例と同じくらい容易となる。
ライブラリー内の多くのインスタンスもジェネリックインスタンスを使用して定義される。例えば、（デフォルト、lazy）ペアのインスタンスの場合は単に以下のようになる。
ラッパー経由の導出
時にはジェネリックインスタンスによって実装されたデフォルトビヘイビアが不要の場合があるが、インスタンスを手動で定義するのは厄介だ。従って、ライブラリーは、カスタムインスタンスを導出するために便利に使用できるいくつかのnewtypeラッパーを用意している。ここではその中から3つのラッパーを紹介するが、ライブラリーにはほかにもいくつかある。
WHNF用OnlyCheck
もし値がWHNFかどうかを確認すること（サンクを含むことはあっても、それ自身がサンクでないということを確認すること）だけが目的であるなら、OnlyCheckIsWhnfを使用できる。例えば、ライブラリーはBoolのインスタンスを以下のように定義する。
Boolにはこれで十分である。BoolはWHNFの場合にサンクを含むことはない。ライブラリーもこれを関数に使用できる。
（ここで、Namedバージョンにより、サンクコンテキストに含まれる型の文字列表現は明示的に定義できる）OnlyCheckIsWhnfを関数に使用するということはすなわち、関数閉包内のいかなる値もサンクにチェックされないということを意味する。これは意図的かつ設計上の繊細な決定事項である。この点については、後述の「許容サンク」のセクションで改めて触れる。
一部フィールドのスキップ
IntSetのような場合、ほとんどのフィールドはサンクチェックを行うが、一部のフィールドではスキップしたいときにAllowThunksInを使用できる。
これは記録が大規模な場合に便利である。手描きのインスタンスは面倒であるばかりでなく、型の変更（新フィールドなど）がwNoThunksの定義に反映されない場合に容易に一致しなくなりかねない。
ヒープディレクトリーの検証
クラスシステムとNoThunksインスタンスを経由する代わりに、GHCヒープディレクトリーを検証することもできる。ライブラリーはInspectHeap新型でこれを可能にする。ここには以下のインスタンスが含まれる。
注：これはaのNoThunksインスタンスには依拠しておらず、他のラッパー経由の導出と同じように使用することができる。例えば、
このようなインスタンスの利点は、ネストされたいかなる型のインスタンスも必要としないことである。例えば、TimeOfDayにはPico型のフィールドがあるが、このためのNoThunksインスタンスは不要である。
不利な点はすべての構成性が失われる点だ。サンクを許可したい中にネストされた型があった場合、そうした型にサンクチェックをしないよう上書きする方法はない。ヒープディレクトリーを検証しており、ランタイムシステムは型情報を記録しないため、こうした型のNoThunksインスタンスは無関係となり、ここで検知されたすべてのサンクがレポートされる。さらに、こうしたサンクが検知された場合、有益なコンテクストをレポートできない。なぜなら - ここでも - 型情報がないためだ。noThunksがT（そのNoThunksインスタンスはInspectHeapを使って導出された）内に深くネストしているサンクを検知した場合、単に"…": "T"がコンテクスト（およびおそらくTそのものへ導くあらゆるコンテクスト）としてレポートされる。
許容サンク
データ型には本質的にサンクの存在に依存するものがある。例えば、Data.Sequenceで定義されるSeq型はフィンガーツリーを使用する。フィンガーツリーはRalf HinzeとRoss Patersonが導入した専用データ型だ。ここでは、フィンガーツリーは、その漸近的複雑さの限界に達するためにスパインでサンクの使用が不可欠だという点だけを押さえておけばいい。すなわち、SeqのNoThunksインスタンスはデータ型のスパインでサンクを許可せざるを得ない。その場合もシーケンスのすべてのエレメントでサンクがないことを確認するべきだ。これは簡単に実行できる。ライブラリーのインスタンスは以下だ。
ここで、noThunksInVluesはサンクの値のリストをチェックするヘルパー関数である。この時リストそのもののチェックは行わない。
しかし、Seqのような型が存在することは、InspectHeapの非構成性が大問題となりかねないことを意味している。これもまた、関数に関して、単にその関数がWHNFであるかどうかをチェックする理由となる。関数が閉包内にサンクを含むことはあっても、その型を知ることはない。関数閉包のサンクをチェックすることも可能ではあるが（InspectHeapを使用）、それをしたとして、そして閉包に例えばSeqが値に含まれていたとしても、予想外のサンクを不正確にレポートしてしまう恐れがある。ないバグをあるとテストでレポートされることのほうが、実際のバグがレポートされないことよりも問題であるため、ライブラリーではWHNFの関数のみをチェックすることを選んでいる。関数を保管しているアプリケーションでその関数のサンクチェックが重要である場合は、InspectHeapで定義したNoThunksインスタンスでa -> bの辺りをカスタムの新型で定義することができる（ただし、関数がサンクの許可が必要な型を参照しないことが確かな場合に限る）。
ヒープ/スタックサイズ制限メソッドとの比較
2016年、Neil MitchellがHaskellXで素晴らしいトークを行った。ここで彼は、メモリーリークを検知するメソッドを提示した（彼はこのテーマでブログも投稿している）。このメソッドの概要は、スタックおよびヒープ上限を大幅に下げてテストスイートを実行することだ。これにより、メモリーリークがコードに存在する場合、プロダクションに至る前にこれに気づくことができる。さらに、このような「スタック不足」の例外が投げられた際にスタックトレースが得られるよう、-xcランタイムフラグの使用を推奨している。
この投稿で推奨されるテクニックには多くの利点がある。サンクが生成された瞬間に例外を得るため、ここで得られるスタックトレースは一層役立つことが多い。noThunksでレポートされるコンテキストと合わせて、問題の検出は通常容易だ。-xcによりレポートされたスタックの解釈はもっと難しい。この例外は限界に達したときに投げられるものであり、そもそもリークを起こしたコードに関連している場合もしていない場合も考えられるからだ。その上問題は、制限に達して初めて明らかとなる。最小反例など問題外だ。適した制限値を選ぶのも難しい。テストサイトで実際に必要とされるメモリーは、そしてリークを構成するのはいったいどの程度か。最後に、-xcにはプログラムがプロファイリング可能な状態でコンパイルされていなければいけない。したがって、プロダクションを実行するのと異なる形でデバッグすることになるが、これは問題となることもある。
そうは言っても、nothunksメソッドはヒープ/スタック制限メソッドに置き換わるものではなく、これを補完するものだ。nothunksアプローチは主に、通常長期的アプリケーションステートで、いかなるサンクの蓄積も望ましくないことが明白な場合に、データ内のスペースリークを検知するのに役立つ。ところが、より「ローカル」なスペースリークの検出、関数アキュムレーターが厳格に更新されていないといった場合などにはさほど役に立たない。こうしたリークの検知には、スタック/ヒープ制限を設定することが有効である。
結論
長期的アプリケーションデータには、通常サンクが蓄積されるべきでない。nothunksライブラリーはこれをnoThunksおよびunsafeNoThunks関数のコールを通じて検証することができる。これは所与のアーギュメントに想定外のサンクが含まれるかをチェックすることである。こうしたチェックはアサーションでサンクが生成されていないことの確認にも使用できる。誤ってサンクを導入した場合に、即座にテストが失敗し、サンクが生成された場所のコールスタックが得られると同時に、サンクがどこにあるかについて有効な手掛かりとなるコンテキストも得ることができる。テストフレームワークと合わせて、これはメモリーリークのデバッグおよび回避をとても容易にする。実際に、このアプローチを始めて以来、Cardanoでの作業において、それはほぼ過去のものとなってきている。