Envision VM（パート3）、アトムとデータストレージ

Victor Nicollet

この記事は、Envision 仮想マシンの内部動作―Envision スクリプトを実行するソフトウェア―についての全4部構成のシリーズの第3部です。パート1、パート2およびパート4を参照してください。このシリーズは Envision コンパイラについては扱っていません（おそらく別の機会に）、ですのでスクリプトが何らかの方法で Envision 仮想マシンが入力として受け取るバイトコードに変換されたものと仮定します.

実行中、thunk はしばしば大量の入力データを読み取り、出力データを書き込みます.

• 10億個のブール値（一つの値につき1ビット）は 125MB を占めます.
• 10億個の浮動小数点数（32ビット精度）は 4GB を占めます.
• 10億個の最小限の販売データ（日時、場所、EAN-13、数量）は、値のエンコーディング方法により14GBから33GB（またはそれ以上）を占めます.

これにより2つの課題が生じます。すなわち、データが生成された時から使用される時までどのように保持するか（解決策の一部は、複数のマシンに分散した NVMe ドライブ上に保存することです）と、RAM よりも遅いチャネル（ネットワークおよび永続的なストレージ）を通過するデータ量をどのように最小限に抑えるかです.

メタデータレイヤー

解決策の一部として、データの性質に応じて2つの別々のデータ層のいずれかにデータを押し込む方式があります。メタデータレイヤーは実際のデータに関する情報および実行中のスクリプトに関する情報を含みます：

• ある thunk が正常にデータを返すと、そのデータの一意の識別子がこの層に保存されます.
• thunk が失敗した場合、その thunk によって生成されたエラーメッセージがこの層に保存されます.
• thunk が新たな thunk（およびその親のDAG）を返した場合、シリアライズされた DAG がこの層に保存されます.
• thunk はメタデータレイヤーにチェックポイントを保存できます（通常はデータブロックの識別子で構成されます）。もし thunk が完了する前に中断された場合、メタデータレイヤーからチェックポイントを再読み込みし、その位置から作業を再開できます.

言い換えれば、メタデータレイヤーは thunk を結果にマッピングする辞書と見なすことができ、その結果の具体的な内容は、実際に thunk が返したものに依存します.

メタデータレイヤーは、参照されるデータの構造に関する追加情報を含むこともできます。例えば、ある thunk が2つのベクターのペアを返した場合、メタデータにはそれぞれのベクターの一意の識別子が含まれます。これにより、利用者は両方をロードすることなく、片方のベクターにアクセスできるようになります.

メタデータレイヤーに保存される値には2つの制限があります。エントリーは10MBを超えてはならず（シリアライズされた DAG も同様にこれを超えてはなりません！）、メタデータレイヤー全体の保存容量は1.5GBです。通常、この層には約100万の値があり、平均的なエントリーサイズは1.5KBです.

メタデータレイヤーは、常に高速なアクセスを保証するためにRAM上に存在します。これは thunk 実行の真実の情報源として機能し、メタデータレイヤーに対応する結果がある場合に限り、thunk は実行されたとみなされます――ただし、これがその結果で参照されるデータが利用可能であることを保証するものではありません.

クラスター内の各ワーカーは、メタデータレイヤーの独自のコピーを保持します。ワーカーは、この層へのすべての変更（ローカルな thunk の実行によって引き起こされたもの）をクラスター内の他のすべてのワーカーおよびスケジューラーにブロードキャストします。これは「ベストエフォート方式」で行われ、ブロードキャストメッセージが宛先に届かない場合、そのメッセージは再試行なしで破棄されます¹.

メタデータレイヤーは毎秒、増分的にディスクに永続化されます。クラッシュや再起動が発生した場合、ワーカーは何をしていたかを記憶するためにディスクから全体のレイヤーを再読み込みするのに1、2秒かかります.

大規模データベースをメモリ上に保持する

前述の通り、メタデータレイヤーには100万のエントリーが含まれる可能性があります。個々のDAGは数十万のノードを持ち、これらすべては数分から数時間という長いライフタイムを持ちます。数百万の長寿命オブジェクトをメモリ上に保持することは .NET のガベージコレクターにとって非常に負荷がかかります.

.NET におけるガベージコレクションは複雑な話題です（ただし、低レベルな詳細に踏み込むための Konrad Kokosa による優れたシリーズ もあります）が、全体的な問題は3つの事実の組み合わせによるものです：

• ガベージコレクションの処理コストは、対象となるメモリ領域内の 生存中 オブジェクト数に比例します。何百万ものオブジェクト、しばしば何十億もの参照関係を処理するには、ガベージコレクターが数 秒 を要します.
• このコストを回避するため、.NET ガベージコレクターはオブジェクトの世代に応じて、ジェネレーションと呼ばれる別々のメモリ領域で動作します。最も若い世代である Gen0 は、直近のコレクション以降に割り当てられたオブジェクトのみを含むため頻繁にガベージコレクションが実行されます（つまり、非常に少数です）。一方、最も古い世代である Gen2 は、Gen1 および Gen0 の両方がコレクションされた後も十分な空きメモリが確保できなかった場合にのみ収集されます。ほとんどのオブジェクト割り当てが小さく短命であれば、これは非常に稀なことです.
• しかしながら、通常の thunk 操作では大量の値の配列が関与し、これらは Large Object Heap 上で割り当て られるため、Gen0、Gen1、Gen2 とは異なる領域となります。Large Object Heap の領域が不足すると、完全なガベージコレクションが実行され、Gen2 も同時に収集されます.

そして、Gen2 には DAG やメタデータレイヤーからの何百万ものオブジェクトが配置されます.

これを回避するために、私たちは DAG とメタデータレイヤーの両方で非常に少数のオブジェクトのみを使用するように構築しました.

各 DAG は、ノードの配列とエッジの配列の2つの割り当てのみで構成されており、どちらもアンマネージドの値型であるため、GC はそれらの内容を辿らなくても済みます。実行のために thunk が必要なときは、メタデータレイヤーに存在する DAG のバイナリ表現²からデシリアライズされます.

メタデータレイヤーは可変長の内容を持つため、大きな byte[] からチャンクを切り出すことで構築され、ref struct と MemoryMarshal.Cast を使用してデータをコピーすることなく操作されます.

スクラッチスペース

クラスターは、512GiBから1.5TiBのRAMおよび15.36TBから46.08TBのNVMeストレージを備えており、これらのほとんどの領域は thunk の評価の中間結果を保存するために割り当てられています.

RAM は貴重な資産です。利用可能なストレージ全体のわずか3%を占めるのみですが、読み書き速度は100倍から1000倍高速です。thunk によって読み込まれようとしているデータが既にメモリ上にある（または最初からメモリから離れていない）ことを保証することは大きな利点があります.

さらに、.NET において利用可能なRAMの100%を使用することはほぼ不可能です。なぜなら、オペレーティングシステムは可変のメモリ需要を持ち、.NETプロセスに対して一部のメモリを解放するように確実に伝達する方法がないため、プロセスがOOM（メモリ不足）により強制終了されることになるからです.

Envision は、RAMからNVMeへの転送管理をオペレーティングシステムに委任することにより、この問題を解決します。このコードは Lokad.ScratchSpace としてオープンソース化されています。このライブラリは、NVMeドライブ上の利用可能なすべてのストレージ領域をメモリマップし、アプリケーションが以下のために使用できる blob ストアとして公開します：

1. スクラッチスペースに直接、または管理オブジェクトからのシリアライズによって（各最大2GBまでの）データブロックを書き込む。この操作はブロック識別子を返します.
2. その識別子を用いてデータブロックを読み込む。この操作はブロックをピン止めし、ReadOnlySpan<byte> としてアプリケーションに公開します。アプリケーションはそれを管理メモリにコピー（またはデシリアライズ）する必要があります.

スクラッチスペースがいっぱいになると、最も古いブロックが新しいデータのために破棄されます。つまり、識別子が破棄されたブロックを指している場合、読み込み操作が失敗する可能性がありますが、これは Envision スクリプトの実行中はまれな現象です――単一の実行で数十テラバイトが生成されることはほとんどありません。一方で、これにより新たな実行が前回の結果を再利用できなくなる場合もあります.

メモリマップされたスクラッチスペースを使用する際の鍵は、利用可能なRAMが3種類のページ³に分散されるということです：プロセスに属するメモリ（例えば Envision の .NET プロセス等）、ディスク上のファイルの一部をまるごとバイト単位でコピーしたメモリ、およびディスク上のファイルに書き出されることを意図したメモリです.

ディスク上のファイルのコピーであるメモリは、いつでもオペレーティングシステムによって解放され、別の目的に使われる可能性があります―例えば、プロセスに割り当てられてその用途に使用されたり、ディスク上の 別の 部分のコピーとして利用されたりします。即時に行われるわけではありませんが、これらのページは素早く他の用途に再割り当てできるバッファとして機能します。そして、再割り当てされるまでは、オペレーティングシステムはそれらが特定の永続メモリ領域のコピーを含んでいることを認識しているため、その領域への読み込み要求は既存のページにリダイレクトされ、ディスクからの読み込みが一切行われないのです.

ディスクに書き込まれることを意図されたメモリは、最終的には書き出され、その書き込まれた領域のコピーとなります。この変換は NVMe ドライブの書き込み速度（約1GB/s程度）によって制限されます.

プロセスに割り当てられたメモリは、プロセスによって解放されない限り、他の2種類のメモリに戻すことはできません（.NET GC は大量のメモリを解放した後、これを行うことがあります）。.NET を通じて割り当てられるすべてのメモリ、すなわち管理オブジェクトや GC が監視するすべてのものは、このタイプのメモリに属さなければなりません.

一般的なワーカーでは、メモリの25%が直接 .NET プロセスに割り当てられ、70%がファイル領域の読み取り専用コピーとして、5%が書き出し中の状態にあります.

アトムレイヤー

一般原則として、各 thunk は出力を1つまたは複数の アトム としてスクラッチスペースに書き込み、これらのアトムの識別子をメタデータレイヤーに保存します。その後の thunk はこれらの識別子をメタデータレイヤーから読み込み、必要なアトムをスクラッチスペースに問い合わせます.

「アトム」という名称が選ばれたのは、アトムの一部分だけを読み取ることが不可能であり、常に全体として取得されるためです。もし、データ構造がその内容の一部のみの取得をサポートする必要がある場合は、代わりに複数のアトムとして保存し、それぞれを独立して取得できるようにします.

一部のアトムは圧縮されています。例えば、ほとんどのブールベクターは、各要素が1バイトを消費する bool[] として表現されるのではなく、各値が1ビットに圧縮され、その後、同一の値が連続する長いシーケンスが除去されるように圧縮されます.

アトムが消失する可能性はありますが、これは稀な現象です。この現象が発生する主な状況は、メタデータレイヤーが前回の実行結果を覚えているにもかかわらず、対応するアトムがその間にスクラッチスペースから排除された場合と、アトムがもはやリクエストに応じなくなった別のワーカーに保存されていた場合です。さらに稀に、チェックサムエラーにより、保存されたデータが無効となり破棄されなければならないことが判明する場合もあります.

アトムが消失した場合、そのアトムを要求した thunk は中断され、リカバリモードに入ります：

1. システムは、thunk の入力で参照される他のすべてのアトムの存在（ただしチェックサムは確認しません）を検証します。これは、アトムが同時に、同一のワーカー上で生成される可能性が高く、あるアトムの消失が同じ時期・場所での他のアトムの消失と相関しているためです.
2. システムは前のステップで欠損と判明したアトムに関する参照をメタデータレイヤー内で徹底的に検索します。これにより、結果が破棄されたために、一部の thunk が「実行済み」から「未実行」に戻されます。その後、カーネルがこれを検出し、再度スケジュールします.

再実行された thunk は再びアトムを生成し、その後実行が再開されます.

アトム配列

アトムレイヤーの特定の側面として、シャッフルの実行方法があります。第1層の $M$ 個の thunk がそれぞれ数百万行のデータを生成し、その後、第2層の $N$ 個の thunk がそれぞれ前の層の出力を読み取って別の操作（通常は何らかの reduce 操作）を実行しますが、第1層の各行は、第2層の1つの thunk のみが読み取ります.

第2層の各 thunk が第1層のすべてのデータを読み取るのは非常に無駄であり（各行が $N$ 回読み取られ、そのうち $N-1$ 回は不要になります）、しかし、もし第1層のすべての thunk が正確に1つのアトムしか生成しなかった場合、まさにこのような事態が発生します.

一方で、第1層の各 thunk が第2層の各 thunk ごとに1つの atom を生成する場合、シャッフル操作では合計 $M\cdot N$ 個の atom が関与します—$M = N = 1000$ の場合は100万個の atom になります。atom のオーバーヘッドは過剰ではありませんが、atom 識別子、テナント識別子、atom データ型、サイズ、およびわずかな管理情報を合算すると、1つの atom あたり数百バイトに達することがあります。

この問題を解決するために、Envision は atom 配列をサポートしています:

• All the atoms in an atom array are written out at the same time, and are kept together both in memory and on the disk.
• Given the identifier of the atom array, it is easy to derive the identifier of the i-th atom in the array.

これにより、atom の配列は単一の atom と同じオーバーヘッドになります。シャッフルでは、第1層の thunk がそれぞれ $N$ 個の atom を含む $M$ 個の配列を生成します。第2層の thunk はそれぞれ、各配列からその thunk のシャッフル内でのランクに対応する位置にある1つの atom を要求し、合計 $M$ 個の atom を収集します。

締めくくりとして、いくつかの運用統計を紹介します！1時間あたり、典型的なワーカーは150 000個の thunk を実行し、200 000個の atom（atom 配列は1回のみカウントされる）を書き出し、750GiB の中間データを生み出します。

次回かつ本シリーズ最終回では、分散実行を可能にする各層について議論します。

控えめな宣伝ですが、ソフトウェアエンジニアを募集中です。リモートワークも可能です.