David Devecsery, Michael Chow, Xianzheng Dou, Jason Flinn, and Peter M. Chen:
Eidetic Systems
11th USENIX Symposium on Operating System Design and Implementation (OSDI)
システム系論文紹介 Advent Calandar 第22日目（実質12日目）です。 ちなみにlast authorの Peter M. Chen は When Virutual is Better than Real で2001年の段階でVM全体をマイグレーションすることでプロセスマイグレーションより便利な世界を目指すことを提案したりしている（実装はしていないが）システム系の有名研究者です。
"eidetic" とは「はっきりと目に浮ぶ, 前に見たものをはっきりと思い出す」こと（weblioより引用）。 本論文では trace and replay の技術を発展させ、下記のようなシステムを実現する。
自分の書きかけの論文におかしな citation を見つけた。明らかに引用するものを間違っているが、さてもともとどの論文を引用するつもりだったのか？（下図は当該論文のスライドより引用。）
この例に対し、Eidetic System は下記を可能にする。 (1) 書きかけのpdfから lineage をたどることにより、その citation をコピペした時のブラウザのインスタンスを復元できる。ユーザはこれをみて「ああ、これじゃなくて隣のタブで開いていた論文と間違えたな」などと思い出せる。 (2) ブラウザのインスタンスから lineage を逆向きにたどることにより、同じ間違いをしている別の個所（例えば別の論文にも同じ citation をコピペしている、メールでその citation に関する情報を誰かに送った、等）を発見できる。
基本的にはよく知られた record and replay を用いる。record and replay（あるいは trace and replay）とは、あるシステムへのキーボード、ネットワーク等の入力を全て記録することによってそのシステムがどう動作したかを後から再実行（replay）可能にする技術のことである。
Eidetic System を record and replay を用いて実現する際の技術的課題は以下である。
システム（マシン）への入力のみを記録する。たとえばVMへの全入力を記録して後からVMの挙動を再生といった場合に利用される。 この方式はマシン全体への入力（キーボード、ネットワーク等）のみを記録すればよいためストレージ効率はよいが、 たった1バイトの linage をたどるためにシステム全体を replay する必要があり replay のコストが高い。
各プロセスへの入力を全て記録する。システムレベルの record とは逆に、replay のコストは低いがプロセス間通信等を全て記録する必要があるためストレージ効率は悪い。 またプロセス間の関係（プロセスAへの入力がどこから来たのか？）が失われる。
メモリを共有しているプロセス等はひとつのグループとして扱い、そのグループへの入力を record する。 頻繁なプロセス間通信を記録する必要がないためストレージ効率がよく、またグループごとに replay すればよいため replay の効率も比較的よい。 しかし、プロセス間の関係は失われたままである。
そこで本論文では「プロセスグラフ」をプロセスグループの record に追加で実装する。 プロセスグラフとは、record をする際に記録したデータがどのプロセスから来たのかを追加で記録することでプロセス間の関係を保持するものである。 （traditionalな record and replay では入力データのみを記録。）
プロセス間の lineage は通常のプロセスレベル/プロセスグループレベルの record and replay では追跡できなかったが、 プロセスグラフによって明らかに一部は追跡できる。 しかし、人間が関わる lineage はプロセスグラフのみでは追跡できない。 例えば Motivating Example では、人がブラウザで開いている論文情報をvimに手入力した場合がこれにあたる。これを human linkage と呼ぶ（linage ではなくて linkage）。
Human linkage はデータの内容および時間を見て検出する。 もちろん100%完璧に発見することはできないが、プロセスグループでは見逃してしまうデータの関係を発見できる。 また citation 間違いの例の評価では false positive は容易にそれとわかるので問題ないことが示されている。
細かい実装とか、それでもでかいrecord logをどうやって普通のデスクトップPCで扱えるくらい圧縮するか等については本文を参照してください。Motivating Exampleが非常に面白いので紹介しました。