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

Victor Nicollet

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

実行中、サンクは入力データを読み取り、出力データを書き込みます。これらのデータはしばしば大量に存在します。

• 10億のブール値（1つの値あたり1ビット）は125MBを占有します。
• 10億の浮動小数点数（32ビット精度）は4GBを占有します。
• 10億の最小限の販売行（日付、場所、EAN-13、数量）は、値のエンコード方法によって14GBから33GB（またはそれ以上！）を占有します。

これには2つの課題があります。データが作成された瞬間から使用されるまで（一部は複数のマシンに分散されたNVMeドライブに保存されます）このデータを保持する方法、およびRAMよりも遅いチャネル（ネットワークおよび永続ストレージ）を介して送信されるデータ量を最小限にする方法です。

メタデータレイヤー

解決策の一部は、データの性質に基づいてデータを2つの別々のレイヤーに分けることです。メタデータレイヤーには、実際のデータと実行されているスクリプトに関する情報が含まれます：

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

言い換えると、メタデータレイヤーは、サンクを結果にマッピングする辞書と見なすことができます。ただし、結果の正確な性質は、サンクが実際に返した内容に依存します。

メタデータレイヤーには、参照されているデータの構造に関する追加情報も含まれる場合があります。たとえば、サンクが2つのベクトルを返した場合、メタデータには各ベクトルの一意の識別子が含まれます。これにより、コンシューマは両方をロードせずに1つのベクトルにアクセスできます。

メタデータレイヤーに格納される値には2つの制限があります。エントリのサイズは10MBを超えることはできません（したがって、シリアライズされたDAGもこの量を超えることはできません！）。また、メタデータレイヤーの合計ストレージスペースは1.5GBです。通常、このレイヤーには約100万の値があり、平均エントリサイズは1.5KBです。

メタデータレイヤーは常にRAM上に存在し、高速なアクセスを保証します。これはサンクの実行の真実のソースであり、サンクに関連付けられた結果がメタデータレイヤーに存在する場合にのみ、サンクが実行されたことを意味します。ただし、その結果で参照されているデータが利用可能であることを保証するものではありません。

クラスター内の各ワーカーは、独自のメタデータレイヤーのコピーを保持しています。ワーカーは、ローカルなサンクの実行によって引き起こされるこのレイヤーのすべての変更を、クラスター内の他のすべてのワーカーとスケジューラにブロードキャストします。これは「ベストエフォート」の基準で行われます。ブロードキャストメッセージが宛先に届かない場合、再試行なしでドロップ¹されます。

メタデータレイヤーは、1秒ごとに増分でディスクに永続化されます。クラッシュや再起動の場合、ワーカーはディスクからレイヤー全体を再読み込みして、以前の状態を思い出すのに1〜2秒かかります。

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

上記のように、メタデータレイヤーには100万のエントリが含まれる場合があります。各個別のDAGには数十万のノードが含まれる場合があります。これらすべての寿命は長く、数分から数時間です。メモリに数百万の長寿命オブジェクトを保持することは、.NETガベージコレクタにとって非常に困難です。

.NETにおけるガベージコレクションは複雑なトピックです（低レベルの詳細については、Konrad Kokosa氏による優れたシリーズがあります）。ただし、全体的な問題は次の3つの事実の組み合わせです。

• ガベージコレクションの実行コストは、ガベージコレクションが行われるメモリ領域内の「生存している」オブジェクトの数に比例します。何百万ものオブジェクトを処理し、それらの間をたどるために数十億の参照を行うことは、ガベージコレクタに数秒かかります。
• このコストを支払わないために、.NETガベージコレクタは、オブジェクトの年齢に応じて「世代」と呼ばれる別々のメモリ領域で動作します。最も若い世代であるGen0は頻繁にガベージコレクションが行われますが、前回のパス以降に割り当てられたオブジェクトのみを含みます（つまり、わずか数個）。最も古い世代であるGen2は、Gen1とGen0の両方が収集されたが十分な空きメモリが得られなかった場合にのみ収集されます。これは、ほとんどのオブジェクトの割り当てが小さく短命である限り、非常にまれなことです。
• ただし、通常のサンク操作には、Gen0、Gen1、およびGen2とは別の領域であるLarge Object Heapに割り当てられた大きな値の配列が含まれます。Large Object Heapがスペース不足になると、フルガベージコレクションが実行され、Gen2も収集されます。

そして、DAGとメタデータレイヤーの数百万のオブジェクトはGen2に配置されています。

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

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

メタデータレイヤーには可変長のコンテンツがありますので、byte[]からチャンクを切り出すことでデータをコピーせずにデータを操作するためにref structとMemoryMarshal.Castを使用して構築されています。

スクラッチスペース

クラスタには512GiBから1.5TiBのRAMと15.36TBから46.08TBのNVMeストレージがあります。このスペースのほとんどは、サンクの評価の中間結果を保存するために使用されます。

RAMは貴重な不動産です。利用可能なストレージスペースのわずか3%を占めていますが、読み書きには100倍から1000倍の速さがあります。サンクによって読み取られるデータが既にメモリに存在している（または最初からメモリから離れていない）ことを確認することには、かなりの利点があります。

さらに、.NETでは利用可能なRAMの100%を使用することはほぼ不可能です。オペレーティングシステムは可変のメモリニーズを持ち、.NETプロセスにメモリを解放するように信頼できる方法がありません。その結果、プロセスはメモリ不足でoom-killed（メモリ不足）になります。

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

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

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

メモリマップされたスクラッチスペースの使用の鍵は、利用可能なRAMが3種類のページ³に分散されていることです。プロセス（Envisionの.NETプロセスなど）に属するメモリ、ディスク上のファイルの一部と完全にバイト単位で一致するメモリ、ファイルに書き込まれることを意図したメモリです。

ディスク上のファイルのコピーであるメモリは、いつでもオペレーティングシステムによって解放され、他の目的に使用されることができます。つまり、プロセスに使用するために提供されるか、ディスク上の別の領域のコピーになることができます。即座ではありませんが、これらのページは別の用途に迅速に再割り当てできるメモリバッファとして機能します。再割り当てされるまで、オペレーティングシステムはそれらが特定の領域のコピーを含んでいることを知っているため、その領域の読み取り要求は既存のページにリダイレクトされ、ディスクからの読み込みは一切必要ありません。

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

プロセスに割り当てられたメモリは、プロセスによって解放されない限り、他の2つのタイプに戻すことはできません（.NET GCがメモリの大量解放後に行う場合があります）。GCが監視するすべての管理オブジェクトとその他のすべての.NETを介して割り当てられたメモリは、このタイプのメモリに属する必要があります。

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

アトムレイヤー

一般的な原則は、各スラムクは、その出力をスクラッチスペースに1つ以上のアトムとして書き込み、それらのアトムの識別子をメタデータレイヤーに格納することです。その後のスラムクは、これらの識別子をメタデータレイヤーから読み込み、必要なアトムをスクラッチスペースからクエリするために使用します。

「アトム」という名前は、アトムの一部のみを読み取ることはできないため選ばれました。アトムは完全に取得することしかできません。データ構造がその内容の一部のみを要求する必要がある場合、代わりに複数のアトムとして保存し、それぞれを個別に取得します。

一部のアトムは圧縮されています。たとえば、ほとんどのブールベクトルはbool[]として表されず、1ビットごとにコンパクト化され、その後、同じ値の長いシーケンスを排除するために圧縮されます。

アトムが消えることもありますが、これはまれな出来事です。これが発生する主な状況は、メタデータレイヤーが前回の実行結果を覚えているが、対応するアトムがその間にスクラッチスペースから削除された場合、およびアトムが応答しなくなった別のワーカーに保存された場合です。頻度は低いですが、チェックサムエラーにより、保存されたデータが無効になり、破棄する必要があることが判明することもあります。

アトムが消えると、それを要求したスラムクは中断され、回復モードに入ります：

1. システムは、スラムクの入力で参照されている他のアトムの存在（チェックサムは除く）を検証します。これは、アトムが同じ時間と場所から生成される可能性が高く、アトムの消失は同じ時間と場所から他のアトムの消失と相関しているためです。
2. システムは、前のステップで見つかったアトムのいずれかへの参照をメタデータレイヤーで検索します。これにより、一部のスラムクが「実行済み」から「まだ実行されていない」に戻ることになります。その後、カーネルがこれを検出し、再スケジュールします。

再実行されたスラムクは、再びアトムを生成し、実行を再開します。

アトム配列

アトムレイヤーの特定の側面は、シャッフルが行われる方法です。つまり、最初の層の$M$個のスラムクはそれぞれ数百万行のデータを生成し、次の層の$N$個のスラムクは前の層の出力を読み取って別の操作（通常はリダクションの形式）を実行しますが、最初の層のすべての行は2番目の層のスラムクによって1回だけ読み取られます。

2番目の層のすべてのスラムクが最初の層のデータを読み取ると非常に無駄です（すべての行が$N$回読み取られ、そのうち$N-1$回は不要である）。しかし、最初の層のすべてのスラムクが正確に1つのアトムを生成した場合、これが起こることになります。

一方、最初の層のすべてのスラムクが2番目の層の各スラムクに対して1つのアトムを生成する場合、シャッフル操作には合計で$M\cdot N$個のアトムが関与します。$M = N = 1000$の場合、$1000$万個のアトムが関与します。アトムのオーバーヘッドは過度ではありませんが、アトムの識別子、テナントの識別子、アトムのデータ型、サイズ、および少しのブックキーピングを追加すると、アトムごとに数百バイトに達することがあります。実際のデータの4GBをシャッフルするために100MBを支払うというのは小さな価格に思えるかもしれませんが、実際のデータは大容量データ用に設計されたアトムレイヤーに存在し、100MBはメタデータレイヤーの1.5GBの総予算のかなりの部分を占めます。

これを解決するために、Envisionはアトム配列をサポートしています：

• アトム配列のすべてのアトムは同時に書き出され、メモリとディスク上でも一緒に保持されます。
• アトム配列の識別子が与えられた場合、配列内のi番目のアトムの識別子を簡単に導出することができます。

これにより、アトムの配列は単一のアトムと同じオーバーヘッドを持ちます。シャッフルでは、最初の層のスラムクは$M$個のアトム配列を生成し、2番目の層のスラムクはシャッフルのランクに対応する位置で各配列から1つのアトムを要求します。

最後に、いくつかの生産統計情報です！通常の労働者は1時間に15万のスラムクを実行し、20万のアトム（アトム配列は1回のみカウントされます）を書き込み、中間データとして750GiBを表します。

このシリーズの次で最後の記事では、分散実行を可能にするレイヤーについて説明します。

自己紹介: 私たちはソフトウェアエンジニアを募集しています。リモートワークも可能です。