HN 日本語サマリー

← 一覧へ戻る
科学・技術

パンゲノミクス向けフェイクシェル

A Fake Shell for Pangenomics (cs.cornell.edu)

8 pointsby matt_d0 コメント

要約

この記事では、筆者が開発したパンゲノミクスツール「FlatGFA」をゲノム研究者に使いやすくするための「フェイクシェル」について解説しています。FlatGFAはゼロコピーのデータ形式により高速ですが、一般的なCLIやRust APIでは合成の限界や開発の難しさがありました。そこで、Unixシェルスクリプトの利便性とRust APIのパフォーマンスを両立させる、パイプラインのデータをインメモリで処理する新しいアプローチが提案されています。

全文翻訳

パンゲノミクス向けフェイクシェル

私は効率的なパンゲノミクスツールキットであるFlatGFAに取り組んできました。他のパンゲノミクスツールであるodgiと比較して、FlatGFAは唯一の特長として、ゼロコピーデータフォーマットを持っています。メモリ上のデータフォーマットはディスク上のフォーマットと同一であるため、FlatGFAはシリアライゼーションとデシリアライゼーションのコストをすべてスキップできます。ファイルを開くことは、mmap(2)によるものです。不当に厳選されたワークロードでは、FlatGFAはodgiよりも数千倍高速になる可能性があります。

ここからが難しい部分です。私は、パンゲノミクス専門の同僚にFlatGFAを実際に使ってもらいたいと考えています。高性能な操作の目録を作成し、実際の科学者たちがそれらを組み合わせて完全なワークフローを構築できるようにしたいのです。

彼らがそのような構成を行えるようにするために、2つの単純な選択肢がありました。それは、(1) すべてのオペレーターを公開するコマンドラインインターフェース(CLI)を作成し、科学者たちがシェルスクリプトを書いてそれらを組み合わせるか、または (2) Rust APIを設計し、科学者たちがRustコードを書くかです。どちらの選択肢もあまり魅力的ではありませんでした。

  1. CLIアプローチは、実行できる構成の種類を制限します。すべての中間体はファイルまたはパイプである必要があり、これは扱いにくく、いくらかのオーバーヘッドが伴うことは間違いありません。
  2. 私たちの内部Rust APIは、データ構造のトリックを多用しているため、愛らしいほど独特なスタイルを使用しています。生物学者の協力者は優れたRustハッカーですが、彼らが喜んで使用するような良いAPIを提供しているとは、良心の呵 должн(責任)をもって言えません。

この記事は、私たちが最近構築した非常にばかげた代替案、つまりオプション1を提供しているように見せかけながら、オプション2のパフォーマンスに近似するフェイクシェルについてです。

Ousterhoutの二分法について

長い間、FlatGFAのようなパフォーマンス重視のライブラリを「パッケージ化」する正しい方法は、標準的なOusterhoutの二分法であると考えていました。パフォーマンスに敏感なルーチンはRustに残し、それらのルーチンを組み合わせて完全なワークフローを構築するための、より高レベルな言語へのバインディングを作成します。結果はPyTorchに似たものになるでしょう。MLエンジニアにとってPythonがあまり速くないことは問題になりません。なぜなら、時間の99%以上はC++やCUDAで書かれた最適化されたカーネルルーチンで費やされるからです。

現代において、Ousterhoutの二分法の「グルー言語」部分の自然な選択肢はPythonです。1 そこで、優れたPyO3プロジェクトを使用して、FlatGFAのPythonバインディングの構築を開始しました。基本的な部分は比較的うまく機能しました。例えば、以下のコードで動作を確認できます。

$ curl -LO https://raw.githubusercontent.com/pangenome/odgi/refs/heads/master/test/LPA.gfa
$ uv run --with flatgfa python
>>> import flatgfa
>>> graph = flatgfa.parse("LPA.gfa")
>>> [path.name for path in graph.paths]

しかし、Pythonバインディングにはいくつかの深刻な欠点がありました。

  • PyO3を使用しても、バインディングを効率的に記述するのは困難です。問題は、Rustの静的なライフタイムとPythonの動的に管理されるヒープとの間の根本的な複雑さの不一致です。FlatGFAのパフォーマンス上の利点は、コピー、アロケーション、ポインタ追跡を排除することから来ていますが、これらはすべてRust/Pythonの境界で再び忍び寄る可能性があります。
  • ワークロードの全体像を把握できません。単純なPythonバインディングということは、高速化できる唯一の機会はライブラリの各呼び出し内であり、複数の呼び出しにまたがる処理はあまりできません。例えば、ユーザーがFlatGFAデータ構造を反復処理するPythonのforループを記述した瞬間、私たちはほぼ確実にパフォーマンスゲームで敗北します。これは、PyTorchに別途、オプションのコンパイル済みモードがあるのと同じ根本的な理由です。
  • 結局のところ、私たちの生物学者の協力者はPythonにあまり熱中していないのです!パンゲノムパイプラインを構成する伝統的で馴染みのある方法は、Unixシェルを介したものです。個人的には、Pythonがアプローチしやすさのデフォルトの選択肢であることに慣れすぎてしまいました。当然、ドメインエキスパート間の好みは文脈依存であり、多様です。

odgiとその仲間たちがすべて使用しているCLI指向のアプローチを再検討することが理にかなっていました。

シェルを再考する

この分野におけるシェルベースの構成の例を見てみましょう。odgiドキュメントのチュートリアルの1つは、odgi自体とbedtoolsのオペレーターを組み合わせて、ヒト染色体8の繰り返し配列を見つける方法を示しています。

odgi depth -i chr8.pan.og -r chm13#chr8 | \
    bedtools makewindows -b /dev/stdin -w 5000 > chm13.chr8.w5kbps.bed

odgi depth -i chr8.pan.og -b chm13.chr8.w5kbps.bed --threads 2 | \
    bedtools sort > chr8.pan.depth.w5kbps.bed

シェルスクリプトをフル機能の動的スクリプト言語よりも好むのは奇妙に思えるかもしれませんが、このようなシェルスクリプトにはPythonに対するいくつかの実質的な利点があります。

  • パイプを介したストリーミングI/Oは、適切な状況であれば大規模データセットに最適です。
  • 単純なパイプライン並列処理を簡単に表現できます。
  • 中間結果をファイルに永続化するのは簡単です。
  • シェルは、ある意味で究極のグルー言語です。別々に開発された、異なる言語で書かれたコンポーネントを、特別なバインディング作業なしに組み合わせることができます。(唯一の「バインディング」はUnixユーザーランドAPIです。)

この例のワークフローは、2つの異なるパッケージからの4つのオペレーター、2つのUnixパイプ、および1つの中間ファイルを使用しています。この例ではあまり重要ではないかもしれませんが、シェルパイプラインがコマンドの2つのペアを並行して実行できるのは良いことです。Greenbergらの言葉を借りれば、シェルは実際に優れているのです。2

しかし、1つの巨大な欠点があります。操作間でデータを交換する唯一の方法は、ファイルとパイプです。ファイルは、すべてのバイトがメモリに快適に収まる場合でも、不必要にディスクに書き込むことを伴う可能性があります。パイプはディスクI/Oを回避でき、ストリーミングオペレーターに最適ですが、一般的にはすべてをテキストにシリアライズすることを伴い、すべてのプロデューサー・コンシューマー関係が自然にストリーミングをサポートするわけではありません。例えば、あるコマンドが新しいバリエーショングラフ(新しいGFAファイル)を生成した場合、次のコマンドはおそらくその作業を開始する前に全体を読み取る必要があります。

パンゲノミクスに関する助成金の週次会議で、このシェルベースの構成の根本的な限界について、グループは少し白熱した議論になりました。OSのディスクキャッシュがファイルI/Oのコストを大部分軽減できるでしょうか?RAMディスクにファイルを置いて強制できますか?(RAMディスク上のファイルにmmapすると何が起こるのでしょうか?)データセットがメインメモリをオーバーフローするほど大きくなると、それらのトレードオフは実用的ではないでしょうか?もし、すべての基盤となるコマンドをテキストベースのストリーミングではなく、ゼロコピーバイナリファイルフォーマットを使用するように変更した場合、これらのトレードオフはどうなるでしょうか?そのアプローチはスクリプトをより乱雑にし、パイプラインのすべての利点を犠牲にするでしょうか?

その議論の中で、私はこれらのダウンサイドをすべて回避できる、ばかげて非実用的ですが非常に楽しい代替案があることに気づきました。

余談:ベクトル化されたインタプリタ

[画像: Graydonの「19世紀の技術コール」と題されたトークからのスライド。列車の写真が写っている。](https://venge.net/graydon/talks/VectorizedInterpretersTalk-2023-05-12.pdf)

2023年、Graydon Hoareは「ベクトル化されたインタプリタ」に関するUCSCでの講演を行い、私に大きな感銘を与えました。3 彼は、ネイティブコードコンパイラ(特にJIT)は、コードからパフォーマンスを抽出するための非常に複雑な方法であると指摘しています。私の心に残ったアイデアは、プログラミングモデルからの適切な協力を得られれば、バルクで操作するインタプリタはシンプルで高速な代替手段になりうるということです。もしあなたのバイトコードの各命令が、単一のスカラー整数加算などではなく、大量のデータに対する大きな計算を表すなら、そのバイトコードを単純に解釈するだけで十分に効率的です。バイトコード命令のディスパッチコストなどを気にする必要はありません。なぜなら、時間の99.99%は、それらのチャンキーな命令の実装を実行するために費やされるからです。

Graydonのプレゼンテーションでは、PyTorchとNumPyはどちらもベクトル化されたインタプリタの例です。しかし、前述したように、それらはPythonのプログラム表現とインタプリタを再利用しているため、アドレス指定可能な「命令ウィンドウ」は限られています。

パンゲノミクス操作のためのカスタムベクトル化されたインタプリタで、より良い方法があるはずだと考えていました。そして、シェルスクリプトワークフローの問題は、それに対処しようとする口実となりました。

フェイクシェル

そのアイデアは、フェイクシェルを構築することです。これは、POSIXシェルの構文のほんの一部をサポートし、パンゲノミクスオペレーターを実行する際に「ずるをする」ものです。目標は、odgiやbedtoolsのような、従来のCLIツールを使用した、変更されていないシェルスクリプトを実行し、パイプとファイルを通じて通信することです。私たちは、より高速な実装に機会的に切り替え、I/Oを回避することで、同じ生物学者によって書かれたシェルスクリプトをより高速に実行します。

このシェルはFlash(FlatGFAシェル)と呼ばれ、もしあなたが試したいなら、私たちのパンゲノミクスモノリポジトリで見つけることができます。インタラクティブなプロンプトを表示するにはcargo runを使用してください。

シェルの基本

Flashができる最初のことは、実際のシェルと同じように、通常のコマンドを実行することです。これは、例えば次のように機能します。

echo llenroc | rev > message.txt ; cat message.txt

これを機能させるために、私は「Rustで書き直す」シェルプロジェクトから既存のシェル構文パーサーを借用しました。しかし、FlashはシェルASTを直接解釈するのではなく、まずそれを命令ベースの中間表現(IR)に変換します。上記の小さなスクリプトは、実行される各コマンドに対応する3つの命令に変換されます。Flashは、-pretend(-p)フラグを付けた場合にIRをきれいに表示できます。

$ flash -p -c 'echo llenroc | rev > message.txt ; cat message.txt'
shell("echo", ["llenroc"], input=stdin) -> pipe-0
shell("rev", [], input=pipe-0) -> "message.txt"
shell("cat", ["message.txt"], input=stdin) -> stdout

これまでのところ、私たちはshell命令のみを使用しており、これは実際には(実際のシェルと同様に)サブプロセスをフォークします。FlashのIRはリソースを中心に構築されています。これらは命令の入力および出力になりうるものです。このプログラムは、stdinとstdoutリソース、Unixパイプ、およびファイルを使用します。FlashのIRエバリュエータは、各命令に代わってパイプのセットアップとファイルのオープンを担当します。

フェイクする

Flashをフェイクシェルにしているのは、組み込みの既知のパンゲノミクスCLIツールのセットを特別扱いしている点です。例えば、前述のスクリプトの一部を借用してみましょう。

$ flash -p -c 'odgi depth -i chr8.pan.gfa -r chm13#chr8'
parse-gfa("chr8.pan.gfa") -> gfa-store-0
path-depth(gfa-store-0, path="chm13#chr8") -> stdout

Flashはodgi depthの呼び出しを認識し、shell命令の代わりに、内部で実行できるいくつかの特殊化された命令を生成しました。path-depth命令は、FlatGFAライブラリ内のRust関数を直接呼び出すことで機能し、サブプロセスをフォークすることはありません。

上記のshell命令は、入力と出力のリソースを使用しました。これらは、上記のIRリストではpipe-0や"message.txt"のような名前で表示されます。shellの場合、許可されるリソースの種類はバイトストリーム(つまり、パイプとファイル)のみです。しかし、parse-gfa命令は、新しい種類のリソース、つまりパンゲノミクスバリエーショングラフの効率的なメモリ内表現であるGFAストアを生成します。これは、Flashインタプリタの環境に格納されているプレーンなRust値です。最終的にpath-depth命令を評価する際に、Flashインタプリタはその値を取得し、関連するライブラリ関数に渡します。

これはフェイクシェルを発明した理由のすべてです。それはずるをすることができるからです。Flashは、組み込みの豊富なライブラリを優先して、実際のコマンドの実行を機会的に回避します。

完全な例

より完全なワークフローのIR表現を見てみましょう。このスクリプトをwdepth.shというファイルに保存します。

#!/bin/sh
odgi depth -i chr8.pan.gfa -r chm13#chr8 \
    | bedtools makewindows -b /dev/stdin -w 5000 > chm13.chr8.w5kbps.bed
odgi depth -i chr8.pan.gfa -b chm13.chr8.w5kbps.bed
rm -f chm13.chr8.w5kbps.bed

ここにIRリストを示します。

$ flash -p wdepth.sh
parse-gfa("chr8.pan.gfa") -> gfa-store-0
path-depth(gfa-store-0, path="chm13#chr8") -> pipe-0
parse-bed(pipe-0) -> bed-store-0
make-windows(bed-store-0, size=5000) -> "chm13.chr8.w5kbps.bed"
parse-gfa("chr8.pan.gfa") -> gfa-store-1
parse-bed("chm13.chr8.w5kbps.bed") -> bed-store-1
interval-depth(gfa-store-1, bed-store-1) -> stdout
shell("rm", ["-f", "chm13.chr8.w5kbps.bed"], input=stdin) -> stdout

Flashのデザインで気に入っている点は、異なるリソースタイプを自然に混在させることができることです。一部の命令はファイルシステムやUnixパイプを介して外部世界と対話しますが、他の命令はFlashの内部データ構造と対話します。両方の種類の命令は共存し、データを交換できます。

この例のスクリプトは、通常のshとFlashの両方で実行できます。パフォーマンスを比較してみましょう。4

[画像: 例のスクリプトを、ネイティブなodgi入力ファイルを持つshで実行した場合、ネイティブなFlatGFA入力ファイルを持つflashで実行した場合、テキストGFA入力ファイルを持つflashで実行した場合を比較した棒グラフ。]

最初の2つのバーは重要な比較です。odgi(プレーンなsh経由)とFlatGFA(Flash経由)は、どちらもそれぞれの効率的なバイナリファイルフォーマットで入力グラフを読み取ります。最後のバーは、入力のために標準テキストGFAフォーマットを解析する必要がある場合でも、Flashのパフォーマンスを示しています。

この特定の小さなシェルスクリプトは、実際のシェルと基盤となるodgiを使用した場合と比較して、Flashでは28倍高速に実行されます。これはすでに満足のいくスピードアップだと感じています!また、テキストGFAフォーマットから開始するという不利な条件でも、Flashがodgiを上回ることができるのを見るのは楽しいです。(テキストGFAを読み取るodgiのバーは7分以上かかるため省略しました。証拠はありませんが、FlatGFAが世界最速のGFAパーサーであると信じています。)

最適化

これらすべてが楽しい言語実装の趣味になりますが、このすべてのセットアップの本当の理由は、最適化を行うことです。Flashの命令ベースのIRは最適化を可能にします(シェルASTで直接実装する方法は想像できません)。これまでに実装した最適化は次のとおりです。

  • プログラムがBEDファイルを出力し、それをparse-bed命令で再度ロードする場合、バイトを介した往復を回避します。メモリ内BEDリソースを生成し、それを直接使用します。
  • 実際には塩基対数のみを必要とするpath-depthの使用を認識し、より安価なpath-length命令に置き換えます。(これはこじつけです。odgi depth -rは、深さを不必要に計算する場合でも、パス長を取得するための便利なCLI方法であるというだけです。)
  • 同じファイルを2回ロードする同一のmap-file命令を見つけ、重複を排除します。(もし私がもっと優れた人間なら、これは一般的なCSEになるでしょう。)
  • 最もこじつけなもの:プログラムがparse-gfa("foo.gfa")を使用し、foo.flatgfaという名前のファイルが偶然存在する場合、それをmap-file("foo.flatgfa")に置き換えます。つまり、テキストGFAフォーマットを効率的なバイナリフォーマットに既に変換したと仮定して、それを使用します。(このばかげた最適化は、主に、実際のPOSIXシェルと完全に互換性のあるシェルスクリプトの記述に役立ちます。)

上記の小さなスクリプトを最適化した結果を示します。

$ flash -O -p wdepth.sh
map-file("chr8.pan.flatgfa") -> mmap-0
path-length(mmap-0, path="chm13#chr8") -> bed-store-0
make-windows(bed-store-0, size=5000) -> bed-store-1
interval-depth(mmap-0, bed-store-1) -> stdout
shell("rm", ["-f", "chm13.chr8.w5kbps.bed"], input=stdin) -> stdout

コードを大幅にクリーンアップしました。効率的なFlatGFAファイルを直接使用し(そして一度だけ開きます)、すべてのパイプと中間ファイルをスキップします。パフォーマンスを見てみましょう。5

[画像: 最適化なしのFlashで実行した場合と、最適化ありのFlashで実行した場合の例のスクリプトを比較した棒グラフ。]

追加で1.7倍のスピードアップは、まずまずの結果と言えるでしょう。現時点で実装した最適化は、この特定のワークロードに悲劇的に過剰適合していることを覚えておいてください。これは、Flashの開発中に私の「ハローワールド」デモとして使用されてきたものです。

これは手の込んだいたずらですか?

Flashは、ばかげたシェル構文のハロウィンの衣装を着た、少しドメイン固有の言語です。私は、基盤となるDSL、ベクトル化されたインタプリタ、およびそれが可能にする粗粒度の最適化に非常に興奮しています。これらすべての仕組みが、FlatGFAを実用的に使用可能にする方法になる可能性があると考えています。表面的な構文が偶然シェルのように見えるという事実は、結局のところ、それほど重要ではありません。たとえそれが少しおかしいとしても。しかし、それは、生物学者が既に書いた既存のシェルスクリプトを実行し、それらを透過的に高速化できることを意味します。

今のところ、Flashの構文はシェル構文です。これは良い出発点であり、馴染みがあり、既存のコマンドラインツールの組み合わせと比較して直接比較することができます。私たちは、それを超えるまで、「フェイクシェル」入力言語を使い続けるつもりです。


この投稿のドラフトに対するフィードバックを提供してくれたKevin Laeufer、Ernest Ng、Michael Xing、Ayaka Yorihiroに多大な感謝を捧げます。

  1. すみません、Tclです。↩

  2. シェルスクリプトをプログラミングモデルとして、より広く捉えるための考え方については、HotOS 2021の「Unix Shell Programming: The Next 50 Years」を強くお勧めします。非常に楽しい読み物です。特に、PaShもシェルスクリプトをデータフローIRにコンパイルすることで高速化します。Flashでその並列化アプローチを採用したいと考えています。↩

  3. もしあなたがこれを読んでいるなら、Graydon、私のポイントをおそらく過度に単純化していることをお詫びします。↩

  4. これらの実験は、デュアルXeon Gold 6230プロセッサ(2.10 GHz)、512 GB RAM、Ubuntu 22.04を搭載したサーバーで実行しました。Hyperfineを使用してエンドツーエンドの実行時間を比較しました。設定は3回の実行と1回のウォームアップです(hyperfine -w1 -r3 -N)。ウォームアップは入力ファイルがキャッシュされていることを意味するため、実際のディスクI/Oの多くを測定しているとは考えていません。Odgiはバージョンをv0.6.3-9-ge1940cdと報告しており、Flashはコミット2421a7fから使用しました。↩

  5. エラーバーは標準偏差を示しています。他のプロットではエラーバーが非常に小さいため含めていません。↩