この記事は「A Journey into Stellarator: Part 1」を引用/翻訳しています。
Internet Computerにおけるデータ永続性
著者：Stefan Schneider
この3部作のシリーズでは、Internet Computer Protocol (ICP)上で実行されるアプリケーションのデータ処理能力を大幅に向上させる技術的成果について明らかにします。
このアップグレードは、現在ネットワーク全体に展開されているICPロードマップのStellaratorマイルストーンを指します。Stellaratorはオンチェーンデータストレージにおけるブレークスルーであり、各サブネットがサブネットあたり1TB以上のメモリを提供することを可能にし、これまでのストレージ制約によって制限されていたデータ集約型アプリケーションの機会を解放します。
この進歩により、開発者は大規模なデータ処理を必要とする高度なアプリケーションを構築できるようになり、ブロックチェーン技術に新しいレベルの有用性をもたらします。
それでは、このシリーズを始めるにあたり、Stellaratorアップデートによって現在ICPがどのようにデータを保存しているかを見ていきましょう。
Internet Computerにおけるデータ永続性
このブログ投稿では、Internet Computerのレプリカマシンにおけるストレージの仕組みについて概要を説明します。特に、最近導入されたログ構造化マージツリー（LSMT）ベースのストレージに焦点を当てています。これにより、Internet Computerのサブネットでより多くのレプリケートされたストレージが可能になり、重いワークロードをより適切に処理できるようになりました。
Internet Computerは、13～40台のレプリカマシンにわたって同一にレプリケートされた仮想マシンであるサブネットで構成されています。これらの各レプリカは、そのサブネット上のキャニスターへのすべてのメッセージを実行し、すべてのキャニスターデータを保存する責任があります。したがって、すべてのレプリカはサブネットの完全な状態を同一に保持しています。
開発者はInternet Computerにキャニスターをデプロイできます。キャニスターは他のブロックチェーンのスマートコントラクトに似ていますが、より一般的な計算を実行でき、他のチェーンのスマートコントラクトよりも桁違いに多くのデータを保存できます。
キャニスターが保持するデータは、最終的に何らかの物理ハードウェアに保存される必要があります。Internet Computer上のサブネットは、最近導入されたLSMTベースのストレージレイヤーと多くの最適化や改善により、最大1TBのキャニスターデータを保存できます。
キャニスターのデータの大部分は、ヒープメモリ（執筆時点で最大4GB）またはステーブルメモリ（執筆時点で最大500GB）のいずれかに保存されます。また、キャニスターコード、処理中のメッセージ、コントローラーのリストやサイクル残高などの関連情報など、キャニスターに関連する他の形式のデータもあります。
ICPのストレージレイヤーは、ヒープやステーブルメモリなどのキャニスターのストレージと、ディスクやRAMなどの基盤となるレプリカマシンのストレージハードウェアの間のギャップを埋めます。
Stellaratorマイルストーンの一部として、ストレージレイヤーは将来のスケーラビリティの課題に対応し、旧ストレージレイヤーの最も重要なスケーラビリティのボトルネックを解決するために、広範な再設計と再実装が行われました。関連するすべての変更は最近完了し、Internet Computerは数ヶ月前から新しいストレージレイヤーの実装で動作しています。
このブログ投稿の残りの部分では、ストレージレイヤーのログ構造化マージツリーデータ構造としての再設計について説明します。この再設計は、ストレージ関連のボトルネックを解消することを目的としており、ストレージ重視のキャニスターのユーザーと開発者の双方にとってより良い体験への道を開きます。
ICPユーザーにとって最も注目すべき点は、この作業により、単一のサブネットで1TBのレプリケート状態への最近の引き上げが可能になったことです。さらに、この再設計により、Internet Computerは大量のデータを書き込むキャニスターをより適切に処理できるようになりました。
チェックポイント
一般的に、Internet Computerのストレージレイヤーは、ディスク上の永続ストレージとRAM内の一時的ストレージを組み合わせて使用します。Internet Computerが状態を保存する方法の重要な概念は、いわゆるチェックポイントです。チェックポイントは、サブネット全体の状態がディスクに保存される論理的な時点です。チェックポイントは500ブロックごと、または数分ごとに、決定論的な方法で作成されます。これは、すべてのレプリカが同じ高さで同じチェックポイントを書き込むことを意味します。チェックポイントは、各レプリカノードのディスク上にファイルディレクトリの形式で保存され、ディレクトリ構造は以下のようになっています
（大幅に簡略化）：
< checkpoint_height >
キャニスター
< canister_id_1 >
ヒープメモリ、 安定した
メモリ
、メッセージキュー
< canister_id_2 >
ヒープメモリ、 安定した
メモリ、
メッセージキューこの構造では、各キャニスターは独自のサブディレクトリに保存され、各キャニスターディレクトリには、ヒープメモリ、ステーブルメモリ、および処理中のメッセージなどの他の情報用の個別のファイルが含まれています。
データがチェックポイントの形式でディスクに永続化される理由は複数あります。
データ永続性：レプリカマシンは任意の時点で再起動する可能性があります。レプリカコードにソフトウェアのバグがある可能性や、ハードウェアに障害がある可能性、またはデータセンターの電源供給に問題がある可能性があります。このような場合、最新のチェックポイントを再読み込みすることができます。
チェックポイントは500ラウンドごとにしか作成されませんが、レプリカは非チェックポイント高さの状態を再作成できることに注意してください。レプリカは、最新のチェックポイントとチェックポイントと最新の状態の間のすべての確定ブロックだけを必要とします。すべての実行は決定論的であるため、これらのブロックを再生することで、再作成された状態は正確に同じであることが保証されます。必要なブロックは、チェックポイントとは別にディスクに永続化されるか、他のレプリカから取得されます。
同期：すべての（レプリケートされた）メッセージはすべてのレプリカによって実行されます。その結果、任意の高さhにおいて、すべてのレプリカは同じ状態を持つことになっています。プロトコルは、状態をまずハッシュ化し、その結果のハッシュに対してしきい値署名を行うことで、発散（つまり、一部の誠実なレプリカがコンセンサス状態と異なる状態になること）を防ぎます。レプリカの少なくとも⅔（より正確には2f + 1）が同じハッシュに同意した場合にのみ、そのようなしきい値署名が作成され、サブネットは前進できます。
しかし、Internet Computerのサブネットは大きな状態を持つことができます。この記事の執筆時点での制限は1TBです。Internet Computerの最速のサブネットが現在行っているような1秒あたり最大2.5ブロックを維持しながら、すべてのブロック後にそれほど多くのデータをハッシュ化することは実現不可能です。このため、Internet Computerは非チェックポイント高さでは状態の選択された部分のみをハッシュ化します - 例えば、各キャニスターに関する基本的な情報、イングレスメッセージへの最近の応答、他のサブネットに向けられたXNetメッセージなどです。
チェックポイントの場合、プロトコルは状態全体をハッシュ化してマニフェストと呼ばれるデータ構造を取得します。このマニフェストは、チェックポイントディレクトリ内のすべてのファイルをハッシュ化することで計算され、1MBのチャンクに分割されたすべての個別ファイルのハッシュが含まれています。マニフェストの計算の最後に、マニフェスト内のすべての個別ハッシュをカバーするマニフェストのルートハッシュが計算され、これがサブネットによってしきい値署名されます。マニフェストの計算には数十秒かかる場合がありますが、その作業は500ブロックごとにのみ必要で、バックグラウンドでキャニスター実行と並行して実行されます。
状態同期：Internet Computerは、NNS提案によるサブネットトポロジーの変更を許可します。レプリカノードがサブネットに参加する際、他のレプリカノードから最新のチェックポイントを取得できます。チェックポイントはファイルのコレクションであることを思い出してください。したがって、マニフェストのルートハッシュとそれに対するサブネットのしきい値署名を使用して検証した後、状態同期プロトコルは、取得したチャンクのハッシュをマニフェスト内のものと比較しながら、チャンクごとにファイルを取得できます。すべてのチェックが成功すると、レプリカは取得した状態がチェックポイント高さにおける各サブネットの合意された状態に対応していると結論付けることができます。状態同期は、レプリカが他の理由で遅れを取り、健全な状態とのギャップがブロックの純粋な再生で追いつくには大きすぎる場合にもトリガーされることがあります。
大規模な状態サイズ：現在、最大状態サイズは1TBですが、レプリカノードマシンは512GBのRAMを持っています。したがって、状態全体をRAMにロードすることはできません。Internet Computerは、RAMを主に、まだ永続化されていない最近のデータの保持と、パフォーマンスを向上させるためのデータのキャッシングに使用します。
PageMapと非チェックポイント高さ
チェックポイントは500ブロックごとにしか作成されないため、ICPは非チェックポイント高さでキャニスターにストレージを異なる方法で利用可能にする必要があります。ストレージレイヤーが従うこの基本的なアイデアは、このデータが最後のチェックポイント（ディスク上）とRAMに保存されたそれ以降の変更の組み合わせとして保存されるということです。
PageMapは、サブネットの状態の最大部分についてのこのレプリカの実装です。サブネットの状態の大部分はキャニスター状態、特にキャニスターのヒープとステーブルメモリです。
現在、キャニスターは最大4GBのヒープメモリ、500GBのステーブルメモリを持つことができ、サブネットの総状態は1TBに制限されていますが、これらの制限は将来変更される可能性があります。両方のメモリは、レプリケートされた（更新）コールと非レプリケートされた（クエリ）キャニスターコールによって読み取ることができ、レプリケートされたコールによって変更できます。
PageMapデータ構造は、メモリへの効率的な読み書きを可能にし、チェックポイントの効率的な書き込みをサポートするように設計されています。特に、メモリの総サイズに関係なくパフォーマンスが維持されることが目標です。なお、PageMapという名前は、すべての読み書きの粒度が基礎となるオペレーティングシステムが使用するのと同じ4KBのページサイズであることに由来しています。
PageMapは状態を2つの層で保存します。ストレージと呼ばれる最初の層は、最後のチェックポイントからのファイルです。これらは最後のチェックポイント高さでの状態を表します。2番目の層であるページデルタは、そのチェックポイント以降のすべての変更を表し、RAMに保存されています。
PageMapから読み取る際、返されるデータはページデルタから取得されるか、存在しない場合はチェックポイントファイルから読み取られます。PageMapへの書き込みは、新しいデータでページデルタを修正することによって行われます。
チェックポイントのライフサイクル
ストレージレイヤーの主な任務は、チェックポイントをディスクに書き込み、すべてのPageMapを最新の状態に保つことです。新しいチェックポイントが書き込まれると、すべてのページデルタがディスクにフラッシュされ、すべてのPageMapのストレージ部分が更新されます。
すべてのデータが保存されることを保証するために、レプリカは常に最新のしきい値署名されたチェックポイントを保持する必要があります。これは、古いチェックポイントファイルを単純に上書きすることができないことを意味します。なぜなら、そのような修正は新しいチェックポイントを完全に書き込む前に前のチェックポイントを変更してしまい、データを失うリスクがあるためです。同時に、500ラウンドごとに完全なチェックポイント（最大1TB）をディスクに書き込むことは、非常にコストがかかります。代わりに、新しいチェックポイントの作成は3つの基本的なステップで構成されています
古いチェックポイントを一時フォルダ（tipと呼ばれる）に「コピー」する。
新しいチェックポイントのデータを表すようにtipを修正する。
tipを新しいチェックポイントディレクトリに名前変更する（新しいチェックポイントをアトミックに作成する）。
最初のステップは、状態が大きくなるほどファイルのコピーに時間がかかるため、潜在的に最もコストのかかるステップです。したがって、チェックポイントファイルが大きくなるほど、このステップはより時間がかかります。
しかし、ここでチェックポイントのファイル形式とログ構造化マージツリーが活きてきます。LSMTを使用することで、このステップは安価であり、状態サイズに応じてスケールすることはありません。対照的に、ストレージレイヤーのLSMT再設計以前は、このステップは遅く、予測不可能でした。
ログ構造化マージツリー
ログ構造化マージツリー（LSMT）は、特にデータベースで人気のある広く使用されているデータ構造です。Internet Computerでは、PageMapのストレージ部分の基礎として使用されています。特に解決できる問題は、すべてのファイルが一度書き込まれ、決して変更されないため、チェックポイントライフサイクルの「コピー」ステップを簡略化することです。
LSMTでは、（論理的な）状態への変更は、追加のオーバーレイファイルを書き込むことによって行われます。ページの値を読み取るために、アルゴリズムはまず最も最近書き込まれたオーバーレイファイルでそのページが存在するかどうかをチェックします。存在する場合、そのページの値はそのオーバーレイファイルから読み取られます。存在しない場合は、次に古いオーバーレイファイルがチェックされます。Internet Computerで使用される実装では、ページがどのオーバーレイファイルにも存在しない場合、すべてゼロとして読み取られます。
以下の画像は、キャニスターの状態を表す3つのオーバーレイファイルのセットを示しており、垂直の矢印は異なるデータの読み取りと、データが最終的に読み取られるファイルを示しています。
LSMTを使用したチェックポイントのライフサイクルは次のようになります
前のチェックポイントからすべてのファイルを一時フォルダ（tipと呼ばれる）にハードリンクする。
最後のチェックポイント以降のすべての変更を含む新しいオーバーレイファイルを書き込む。
tipを新しいチェックポイントディレクトリに名前変更する（アトミック性のため）。
重要なポイントは、各オーバーレイファイルが正確に一度だけ書き込まれ、決して変更されないことです。これにより、ハードリンクを介して一部のファイルを共有する複数のチェックポイントをディスク上に安全に持つことができます。チェックポイントのライフサイクルがファイルを修正しようとした場合、このプロセスは機能しないことに注意してください。ファイルに複数のハードリンクがある場合、そのいずれかを修正すると、すべてのデータが変更されます。これは、以前の既に認証済みのチェックポイントを改ざんすることになります。
ログ構造化マージツリーは、同じデータ範囲の複数のバージョンを保存する可能性があります。これにより、すべてのオーバーレイファイルのサイズと表現されるデータの論理サイズの比率として定義されるストレージオーバーヘッドが発生します。さらに、データは複数のファイルに分散している可能性があります。
ストレージオーバーヘッドまたはオーバーレイファイルの数が増加すると、ストレージレイヤーの実装はマージをスケジュールします。マージは、オーバーレイファイルのセットを取得し、各データの最新バージョンのみを含む単一のファイルに置き換えることでデータを再編成します。マージは、特に高いストレージオーバーヘッドまたはファイル数を持つPageMapに対してスケジュールされ、キャニスターメッセージの実行を妨げないようにバックグラウンドで実行されます。
リフリンクを使用した以前の設計
Internet Computerの元のストレージレイヤーは、LSMTに依存していませんでした。2021年のInternet Computerの創設から2024年まで、ストレージレイヤーは代わりにリフリンクに大きく依存していました。
リフリンク（時にはコピーオンライトとも呼ばれる）は、ファイルをコピーするファイルシステムの操作です。これは一部のファイルシステムでサポートされています。Internet Computerのレプリカは、これをサポートするXFSファイルシステムを使用しています。リフリンクは、ファイルの内容全体を複製しないという点で通常のファイルコピーとは異なります。代わりに、ファイルシステムは元のファイルと新しいファイルの間で共有されているデータを記憶します。リフリンクは、両方のファイルが互いに独立して修正できるという点でハードリンクとも異なります。
ストレージレイヤーのこの古い設計では、チェックポイントのライフサイクルは以下のように機能していました：
前のチェックポイントからすべてのファイルを一時フォルダ（tipと呼ばれる）にリフリンクする。
最後のチェックポイント以降のすべての変更に基づいてtip内のファイルを修正する。
tipを新しいチェックポイントディレクトリに名前変更する。
潜在的な利点は、PageMapがチェックポイントで単一のファイルとして表現され、ストレージオーバーヘッドを避けることができたことです。しかし、新しいチェックポイント高さのためにファイルを修正するには、前のチェックポイントから対応するファイルをハードリンクではなくリフリンクする必要がありました。
リフリンクに対するLSMTの利点
原理的には、リフリンクはハードリンクの速度とコピーの使いやすさを約束します。しかし、残念ながら、Internet Computerのデータニーズが増加するにつれて、I/Oスループットと総データ量の両方の観点から、リフリンクはいくつかの理由でパフォーマンスのボトルネックとなることが判明しました。
遅いリフリンク速度：ファイルをリフリンクするのにかかる時間は大きく変動する可能性があります。特定のケースでは数秒で済むこともありますが、実験では370GBのリフリンクに最大10時間かかることも観察されました。Internet Computerの古いチェックポイントロジックの文脈では、10時間のリフリンクステップはサブネット全体の10時間の停止を引き起こすことになります。
悪いリフリンク速度は断片化によってトリガーされます。内部的に、XFSファイルシステムはファイルの一部を実際のディスク上のデータブロックにマッピングするデータ構造を維持しています。断片化、そして遅いリフリンク速度は、これらのデータ構造のトラバースが高コストになったときに発生します。
断片化は特に、ファイルに大量に書き込んだ後、それをリフリンクし、コピーの1つに大量に書き込み、再びリフリンクするなどの一連の操作によってトリガーされる可能性があります。残念ながら、Internet Computer上のチェックポイントワークフローを考えると、重用されるキャニスターはまさにこの動作をトリガーする可能性があります。
一方、ハードリンクは断片化の問題に関係なく一貫したパフォーマンスを持っています。
ログ構造化マージツリーを導入する前に、いくつかの暫定的な緩和策が実装されました。これらには、ファイルを読み取って書き戻すことによる手動のデフラグメンテーションや、より大きな連続セクションでファイルを書き込むことが含まれていました。これらの方法はどちらも大きな書き込み増幅のコストがかかり、それでも最大30分の停止を引き起こす可能性がありました。
最大状態サイズ：過剰な断片化による非常に長いリフリンク時間を超えて、中程度の断片化レベルでさえも、リフリンク時間はサブネットに保存される総データ量に応じてスケールします。ストレージレイヤーの以前の実装では、Internet Computerはサブネットあたり700GBの保存制限を課していました。この数値は、主に中程度に断片化されたデータを最大20-30秒以内にリフリンクできる量の関数です。
ハードリンクを使用すると、チェックポイント時間は同じ方法でデータのサイズに応じてスケールせず、このボトルネックを解消します。
不十分なマルチスレッディング：チェックポイントロジックの目標の1つは、キャニスター実行がチェックポイントの期間中停止する同期操作を可能な限り避けることです。当然、リフリンクが遅くても実行を継続しながらバックグラウンドで実行できるかどうかが検討されました。残念ながら、同時にファイルをリフリンクして読み取ることは不可能であることが分かりました。そのため、実行と並行してリフリンクを行うと、単に実行が遅くなるだけでした。
ストレージレイヤーの新しい設計では、ハードリンクは実行と並行して実行され、互いに速度を低下させることはありません。
キャッシング：上述のように、キャニスターのメモリからの読み取りは、RAMからのデータの読み取りと基礎となるチェックポイントファイルからの読み取りの組み合わせになります。同じファイルから繰り返し読み取ることは、通常、実際のハードドライブやSSDから複数回データを読み取る必要はありません。代わりに、そのようなデータはオペレーティングシステムによってキャッシュされます。残念ながら、リフリンクはキャッシングを妨げます。つまり、まずファイルをリフリンクしてから新しいコピーから読み取ることは、キャッシュを利用しません。その結果、Internet Computer上では、チェックポイントが書き込まれた直後に大きな（そして遅い）ディスク読み取りのスパイクが見られました。なぜなら、すべての読み取りが新しいファイルに切り替わるためです。さらに、マニフェストの計算、つまりコンセンサスの目的ですべてのチェックポイントファイルのハッシュを計算することも、より良いキャッシングから大きな恩恵を受けます。
対照的に、ファイルをハードリンクする場合、すべてのキャッシュは保持されます。最近読み取られたり書き込まれたデータは、それが以前のチェックポイント間隔で発生した場合でもまだキャッシュされており、したがって取得が速くなります。
結果
LSMTストレージレイヤーは2024年第2四半期の数週間にわたってInternet Computerのすべてのサブネットに展開されました。以下のグラフは、レプリカコードのアップグレード時期の指標を示しており、赤い縦線はLSMTストレージレイヤーが有効化された時点を示しています。
最初のグラフは、ビットコイン統合のためのキャニスターをホストするw4remサブネットのチェックポイント時間を示しています。他の多くのサブネットと比較して、ビットコインサブネットは、ヒープとステーブルメモリの両方に対して書き込みの多いワークロードを持つキャニスターをホストしています。その結果、このサブネットでは断片化が特に懸念されていました。
指標が示すように、チェックポイント時間は20秒以上から1-2秒に低下しています。これは主に、20秒の大部分を占めていたリフリンクステップを排除したことによるものです。
ビットコインキャニスターのユーザーにとっての利点は、より迅速な応答です。チェックポイント中、サブネットは更新コールやレプリケートされたクエリを処理しません。ユーザーがちょうどチェックポイントが開始されたときにビットコインキャニスターに更新コールやレプリケートされたクエリを送信した場合、応答を受け取るまでに少なくとも20秒かかっていました。このような不安定な応答時間は、LSMTストレージレイヤーによって本質的に排除されました。
2番目のグラフはk44fsサブネットの確定率を示しています。確定率、またはブロックレートは、サブネットが1秒あたりに生成するブロックの数です。
Internet Computerは、1ラウンドあたりの命令実行数を、1秒で実行できる作業量にほぼ対応する値に制限しています。これにより、確定率を1秒あたり1ブロック以上に維持できます。
LSMTストレージレイヤーへのアップグレード前は、確定率は定期的な低下を示しており、これはまさにチェックポイントに対応しています。チェックポイントは主に2つの理由で確定率に影響を与えます。1つ目は、チェックポイントの作成にかかる時間で、その間ブロックは実行されません。この側面の影響は、チェックポイント時間が一般的にはるかに小さくなったため、アップグレード後に減少しています。2つ目の理由は、LSMTストレージレイヤーのより良いキャッシング動作です。特に、古いストレージレイヤーの実装でのリフリンクステップは、キャッシュの無効化を引き起こしました。そのため、チェックポイント後にキャニスターがメモリから読み取ると、レプリカはそのデータをディスクから取得する必要がありました。これは、同じデータがRAMに保存されているキャッシュで利用可能な場合と比べて桁違いに遅くなります。この問題は新しいLSMTストレージレイヤーには存在しません。
指標が示すように、確定率の低下は、アップグレード後は大幅に小さくなっています。これは、リフリンクを必要としなくなったためチェックポイント自体が速くなったことと、ファイルキャッシュが無効化されなくなったためです。
そのサブネット上のキャニスターのユーザーにとって、これはより迅速な応答時間と増加したスループットを意味します。
結論
ログ構造化マージツリーデータ構造を中心にInternet Computerのストレージレイヤーを再設計することは、プラットフォームのスケーラビリティとパフォーマンスへの重要な投資でした。これは、メモリを多用するワークロードを可能にするだけでなく、Internet Computerがキャニスターにより大きな状態を提供することを可能にします。
大量のデータを扱うキャニスターは、人工知能とオンチェーンでの大規模言語モデルの実行の文脈で特に興味深いものです。そのようなキャニスターは、大量のデータストレージに依存するだけでなく、I/Oスループットにも大きく依存します。
さらに、これは、重いワークロードをクリティカルパスから外すために並行性をより良く活用することで、Internet Computerをより応答性の高いものにするような後続の改善の基礎を形成します。元のストレージレイヤーでの経験は、これを達成するためにリフリンクを避けることが重要であることを示し、LSMTデータ構造はこれを実現します。
この記事は参考になりましたか？
DFINITY Developers Xチャンネルであなたの考えを共有してください。
次回は「Stellaratorへの旅」のパート2で、Luc BläserによるEnhanced Orthogonal Persistenceについてご紹介します。
Comments