Non-Volatile Memory and Java (2) The view from software

このエントリは以下の一連のエントリをベースにしたものです。
This entry is based on the following ones written by Mario Wolczko (Architect, Oracle Labs) and Bill Bridge (Software Architect, Oracle).

また、筆者がこのテーマで語った際のスライド、動画は以下からご覧頂けます。

PROGRAMMING LANGUAGE IMPLEMENTATION SUMMER SCHOOL 2019
The Coming Persistence Apocalypse
https://pliss2019.github.io/mario_wolczko_slides.pdf

Part 2: The view from software

利用時には、NVRAMはDRAMのように見え、通常のメモリ関連の命令(ロード、ストアなど)を使って仮想アドレスメモリとしてNVRAMにアクセスします。

Data structures in a filesystem

NVRAMのデータの長期的な編成とアクセスを可能にするために、データをファイルシステムにカプセル化します。ファイルシステムを使うと、独立した構造を個別のファイルに含めることができ、ファイル名やアクセス権、タイムスタンプといったメタデータを持たせることができます。ある年齢の読者であれば、1980年代のPCの象徴的な機能であるRAMディスクを思い出すことでしょう。でも今回の場合、コンテンツはマシンを再起動しても消失することはありません。RAMディスクのように、データにファイルシステムの操作を使ってアクセスできますが、load-store の利点(即時性と粒度)が失われます。

最高のパフォーマンスと真のメモリセマンティクスを得るには、OSのファイルシステムドライバーは、データをコピーするのではなく、直接ロードストアアクセスを提供する必要があります。典型的なアクセスパターンは、このファイルシステムのファイルを開き、アプリケーションのアドレス空間にマップし、データを直接操作して、ファイルを閉じ、データマッピングを解除する、というものでしょう。これはDirect Access (DAX) モデルとして知られており、すでにメジャーなOS (LinuxとWindows) でサポートされています。

Operating System OS for Intel® Optane™ DC Persistent Memory
https://www.intel.com/content/www/us/en/support/articles/000032860/memory-and-storage/data-center-persistent-memory.html

寿命の長いデータをファイルシステムに配置すると、明らかな利点があります。 バックアップとアーカイブ、階層編成、アクセス制御、space accountingなどの確立されたソリューションがあるからです。

Position independence

DAXファイル内のデータを位置に依存しないよう配置するべきでしょう。コンテンツを特定のアドレスにロードする必要がある場合、独立したファイル間でアドレスが競合する可能性があるためで、ファイルをさまざまなシステムやアプリケーションに移植できるようになると、その可能性が高くなります。さらに、DAXファイル内のデータは、異なるプロセス、または同じプロセス内の異なるアドレスに同時にマッピングされる場合があります。さらに、最新のOSではアドレス空間配置のランダム化(Address Space Layout Randomization、ASLR)が可能で、マルウェアによるデータの変更を困難にしています。具体的には、実行ごとにデータセグメントのアドレスが変わるため、後続の実行でデータを改ざんしようとして、1回の実行でデータのアドレスを学習してもメリットはありません。

Address space layout randomization
https://en.wikipedia.org/wiki/Address_space_layout_randomization

位置非依存を実現する方法の一つに、すべての内部参照を自己相対にする方法があります。そのほかに、再配置メタデータを埋め込み、ファイルのマッピング時にコンテンツを一度にすべて、または増分(たとえば、最初のページフォルトで呼び出される)に再配置できるようにする方法もあります。一部のファイルは(テラバイト以上に)非常に大きくなる場合があり、非増分の再配置により、非揮発性の高速起動の利点が損なわれる場合があります。また、再配置は同時マッピングに対応していません。

現在のソフトウェアは通常、自己相対データで動作しませんし、プログラミング言語は通常、それをサポートしていません。非マネージド言語(Cなど)で記述されたアプリケーションを自己相対アドレス指定を使用するように変更することは、大きな取り組みになる可能性があります。そのほか、言語とコンパイラのサポートを提供することも考えられます。例えば、Cの拡張バージョンであるNVM-Directでは、プログラマが永続メモリ内の参照を区別する必要があり、それらを自己相対化して、コンパイラが詳細を処理します。これにより、JVMなどのマネージドランタイムが、アプリケーションに透過的に自己相対アドレッシングを提供することで支援でき、アプリケーションは変更を認識しません。

NVM Direct – A C library to support applications that map Non-Volatile Memory into their address space for load/store access.
https://github.com/oracle/nvm-direct

The volatile memory hierarchy above NVRAM

NVRAMへのアクセスは通常、いくつかのレベルのキャッシュとバッファリングを含むメモリ階層が介在します。この階層は、従来の揮発性メモリから構築されており、電力が失われると内容が失われます。したがって、NVRAMへの格納は、変更されたデータを含むキャッシュラインがNVRAMに書き込まれるまで、永続的にはなりません。

鋭い読者であれば、「どの時点で永続化されるのか」と尋ねるのではないでしょうか。キャッシュとNVRAMチップの間には、追加のバッファリングなどの揮発性状態を保持する制御ロジックがあります。キャッシュをフラッシュした後であっても、データがこれらのバッファを離れ、NVMチップに到達したことを知る方法はあるでしょうか?その答えは、「あまり重要ではない」ということです。つまり、電源消失時にメモリコントローラの揮発状態をNVMにコミットすることをIntelは保証しているからです。おそらく、利用可能な(スーパーキャパシタなどの)エネルギー源が十分あるのでしょう。やや紛らわしいですが、この特性は非同期DRAMリフレッシュ(Asynchronous DRAM Refresh、ADR)と呼ばれます。DRAMリフレッシュへの接続はあまり明確ではありません。詳細については、Andy RudoffによるPersistent Memory Programmingの記事とこのIntelの記事を参照してください。

Memory refresh
https://en.wikipedia.org/wiki/Memory_refresh
Persistent Memory Programming
https://www.usenix.org/system/files/login/articles/login_summer17_07_rudoff.pdf
Deprecating the PCOMMIT Instruction
https://software.intel.com/en-us/blogs/2016/09/12/deprecate-pcommit-instruction

ついでに言うと、CPUに保持されている状態(レジスタ、キャッシュ)が、たとえば10年以内に不揮発性になることはまずないでしょう。Spin-Transfer Torque RAMのような開発中の技術は、SRAM(キャッシュに使用されるStatic RAM)の不揮発性の代替品として有望ですが、すぐに競合になる可能性は低いです。

Emerging Memory Technologies: Recent Trends and Prospects (Yu and Chen, et al. 2016)
https://ieeexplore.ieee.org/document/7495087

1つの例外は、いわゆる不揮発性プロセッサ(Non-Volatile Processors)という新しい分野です。ここでのアイデアは、エナジーハーベスティングなIoTアプリケーション(つまり、環境から十分なエネルギーを取得できる場合にのみ短時間実行する)のためのプロセッサ内で不揮発性状態を使用する、というものです。ただし、データセンターやデスクトップのプロセッサには関係ないため、これについてはこれ以上検討しません。

Nonvolatile processors: Why is it trending?
https://ieeexplore.ieee.org/document/7927131

Writing cache lines to NVRAM

Intelは、キャッシュラインの書き戻しを支援するためにx64に2つの命令を追加しました。

  • CLFLUSHOPT(Flush Cache Line Optimized、最適化されたキャッシュラインのフラッシュ)
    指定されたアドレスを含むすべてのキャッシュラインを削除します。古いCLFLUSHとは異なり、他のキャッシュラインへの書き込みに関しては順序付けされていません。
  • CLWB(Cache Line Write Back、キャッシュラインライトバック)
    変更されたキャッシュラインを書き戻しますが、強制的な追い出しはしないため、この2つ(または3つ)の中で、より有用です。

耐久性を確保するには、各キャッシュ・ラインの不揮発性更新後に書き戻し命令をアプリケーションに、アンマネージド言語(あるいは、不揮発性データがいつ変更されるかをコンパイラが知っていれば)であればプログラマ(またはライブラリの作者)が、またはマネージド言語のランタイムが挿入する必要があります。こうした命令でNVRAMを非同期で更新します。フェンス命令(バリア命令)を使って更新が永続化されるまで待機できます。代替策として、msync()もしくは相等の機能を使う方法もありますが、これは書き戻しとバリアのための単なるラッパーであり、システムコールのオーバーヘッドが発生します。

msync – synchronize a file with a memory map
http://man7.org/linux/man-pages/man2/msync.2.html

書き戻しおよびバリアを回避する1つの提案されたスキームは、電力損失時に、保存されていないすべての不揮発性データをキャッシュから書き戻すことができるだけの十分なエネルギーをシステムが保持させることです。このスキームを実装するシステムでは、書き込みは実質的に即座に耐久性を持ち、特別な命令を不要になるでしょう。これは拡張ADRとして知られるようになりましたが、これを組み込んだシステムは発表されていないと思います。WBINVDU(Write Back and Invalidate Cache、ライトバックとキャッシュの無効化)命令はある程度関連していますが、完全な解決策ではありません。WBINVD命令はすべてのキャッシュの内容を書き戻しますが、キャッシュを無効にします(好ましくありません)。実行が即座に継続されるため、書き戻しがいつ完了したかを知る方法はなさそうです。そして、これは特権命令ゆえ、システムコールのオーバーヘッドが発生します。WBNOINVD(Write Back and Do Not Invalidate Cache、Ice Lakeで導入される、ライトバックによりキャッシュを無効にしない)命令も同じですが、無効にはなりません。

The Observability Problem

同僚のBill Bridgeが以下の文章で指摘しているように、耐久性とは別の可視性を持つことは不注意を招く罠になります。まとめると、スレッドがNVRAMの共有されたロケーションを更新した後、(ライトバック後に)値が永続化される、その前に更新が(キャッシュの一貫性を介して)見えるようになります。これにより、新しい値の表示に基づいて別のスレッドがアクションを実行できるウィンドウが残されますが、その前にその値が永続的であることがわかります。これには、他のメモリロケーションでの依存する更新(オリジナルを永続化する前に永続化可能です)の実行が含まれる場合があります。この時点での障害は、例えば、クラッシュや電源障害が原因で、リカバリ中に一貫性のない状態になる可能性があります。


THE OBSERVABILITY PROBLEM WITH PERSISTENT MEMORY

by Bill Bridge, Oracle

これまで聞いたことがあるすべての永続的なメモリ設計で、可観測性の問題を発見しました。基本的な問題は、永続メモリへの格納が永続化前に見えてしまう、というものです。別のプロセッサがデータを参照して、見えたデータが永続化される前に永続化する別の更新ができてしまいます。これにより、電源障害が発生した場合に一貫性のないデータが永続メモリに残るウィンドウが作成されます。修正は、永続的なデータのみを表示するために、永続メモリからのロードに対する修正が必要です。問題を認識している場合は、常にソフトウェアの方法で問題を回避できると思いますが、それは信頼できる解決策ではありません。

Controlling Persistent Memory Contents

一般に、ソフトウェアは、プロセッサのリセットまたは電源障害の後、データの一貫性を確保するために、永続メモリへの更新の順序を制御する必要があると認識されています。

現在のプロセッサでは、永続的なメモリがなく、メモリへのストアがプロセッサキャッシュに格納されます。最終的に、変更されたキャッシュラインがキャッシュからDRAMにフラッシュされる場合があります。変更されたデータをDRAMに読み込む前に別のプロセッサがその変更されたデータをロードすると、元のプロセッサのキャッシュからデータを取得します。したがって、新しいデータはDRAMに到達する前に観察できます。電源障害やシステムリセットが発生すると、すべてのDRAMコンテンツが失われるため、DRAMにとってはこれで十分です(これは、すべてのコンピューターにとって重要な回復手法です)。

永続メモリでは、ストアの結果が無期限にプロセッサキャッシュに置かれ、永続化されないため、このメカニズムは受け入れられません。この問題に対して一般的に提案されている解決策は、変更されたキャッシュラインを永続メモリに強制的に書き込むメカニズムをソフトウェアが提供する、というものです。このメカニズムには、データが正常に書き込まれ、リセットまたは電源障害時に表示されることを永続メモリが確認するまで一時停止する手段が含まれています。

あるプログラムが2つの永続メモリロケーションAとBを更新する必要があり、Aが永続的な場合にのみBが永続することを保証するとします。手順は次のとおりです。

  1. Aに新しい値を保存する
  2. Aを永続化する
  3. Bに新しい値を保存する
  4. Bを永続化する

これにより、Bの新しい値を見る任意のプログラムは、Aの新しい値も見るようになります。これは、ステップ4の後にシステムがリブートされた場合でも当てはまります。ただし、ステップ4が完了する前にリセットまたは電源障害が発生した場合、新しいBの値がステップ3の後、他のプロセッサーから見えていたとしても、リブート後に見えなくなります。

The Observability Problem

上記の例では、ステップ3が完了するとすぐに、別のソフトウェアスレッドがBの新しい値を読み取ることができます。その後、Bの新しい値に基づいて他の永続的なメモリロケーションを更新できます。他のメモリロケーションは別のメモリコントローラ上にある可能性があるため、Bの新しい値が永続する前に永続的になる可能性があります。

これまでに聞いたことがある永続メモリの提案の中で、リーダー(reader)が読み込み命令によって取得されたデータが永続的かどうかを知るための効率的な手段はありません。ロード直後にメモリロケーションを強制的に永続化することはできるでしょう。通常、強制によってデータがダーティであるとは判断されませんが、それでも多くのオーバーヘッドがあります。読み込みの前に強制することはできません。強制直後に新しい値を保存する可能性があるため、読み込みの前に強制することはできません。

A Realistic Example

循環バッファは、2つの異なる実行スレッド間で非同期通信するために使用される一般的な手法です。データ構造を永続メモリに配置することで、再起動してもキューの内容が保持されると考える人がいるかもしれませんが、永続メモリで同じアルゴリズムを使用すると、観測性の問題(Observability problem)が発生します。キューは、永続メモリへ正しく強制したとしても、永続的に破損する可能性があります。

この例での永続的な循環キューには、次の特性があります。

  • レコードを永続キューに保存しているProducerスレッドがあります。
  • 永続キューからレコードをフェッチしているConsumerスレッドがあります。
  • レコードがキューに保存された後、Producerが進める永続的なINポインターがあります。
  • レコードが処理された後、Consumerが進める永続的なOUTポインターがあります。
  • OUTポインターとINポインターが等しい場合、キューは空です。
  • OUTポインターの後、INポインターの前にあるレコードが、キューで待機しているレコードです。

可観測性の問題が原因でキューが破損するシナリオは以下の通りです。

Producer Thread:

  1. INポインターとOUTポインターが等しいことを読み取り、新しいレコードを保存する余地があることを確認します。
  2. INポインターが指す循環バッファースロットにレコードを格納します。
  3. レコードデータを永続化します。
  4. INポインターを進めて、新たなレコードをキューに入れます。
  5. 割り込み命令によって、OSコンテキストに切り替わります。Producerスレッドの実行は、10マイクロ秒後に再開されます。
  6. INポインターを永続化するものの、新しい値が永続化される前に電源が落ちます。

Consumer Thread:

  1. INとOUTが等しいことを読み取り、処理対象のレコードがないことを確認します。
  2. MWAIT命令が完了し、新たなINポインターが処理対象のレコードの存在を示していることを確認します。しかし、INポインターはまだ更新が永続化されていません(これが可観測性の問題、observability problemです)。
  3. Producerを一時停止するハンドラーに割り込むよりも先に新たなレコードを処理します。
  4. 新たなINポインターに一致するようにOUTポインターを進め、キューが空であることを示すようにします。
  5. OUTポインターを永続化します。これでOUTポインターが永続化されました。
  6. 電源障害で、INポインターは進んでいないのに、OUTポインターを永続化ポインターはすでに進んでいる、という状態になります。

再起動後、キューは空ではありません。INポインターは進んでいないため、OUTポインターはIN + 1に等しくなります。循環バッファーのロジックでは、これはバッファーがいっぱいであることを意味します。キューが固定個数のレコードを保持する場合、キューの内容はすでに処理されたすべての古いレコードになります。キューが可変個数のレコードを処理する場合、OUTポインターは古いレコードの中にある可能性があり、コンテンツはゴミになります。

満杯のキューでも同様の問題が発生します。OUTポインターの進行が永続化されないのに対し、INポインターの進行が永続化すると、固定個数のレコードを扱うキューの場合、キュー全体が空になります。

The Solution

最も堅牢なソリューションは、永続的なメモリ位置からのロードが永続的なデータのみを参照するようにすることです。これには、メモリコントローラーがデータを永続化するまでロードを一時停止するキャッシュコヒーレンシアルゴリズムの変更が含まれる可能性があります。これにより、ほとんどの人が想定している方法で永続メモリが機能します。

循環バッファの問題に対するソフトウェアのみの解決策があります。 INポインターがDRAMと永続メモリにあります(OUTポインターも同様です)。キューにレコードを追加もしくは削除すると、最初に永続ポインターを更新した後に永続化を確保した上で、永続ポインターを反映するべくDRAMポインターを更新します。DRAMポインターはキュー内のスペースまたはレコードを見つけるために使います。再起動時に、DRAMポインターは永続ポインターの値で再初期化されます。

別の解決策は、ローカル変数にロードした後、NVMへのINまたはOUTポインターの現在の値をフラッシュすることです。これにより、ローカル変数の値が現在の永続値または永続バージョンの前のバージョンの値のいずれかになることが保証されます。ロードする前にNVMにフラッシュすると、永続化されない新しい値が表示される可能性があります。

すべてのデータ構造に対して、問題に対するソフトウェアでの解決策があることを期待しています。 ただし、これをソフトウェアに任せるにはいくつかの問題があります。

  • 多くの開発者は問題があることに気付かないでしょう
  • DRAMの基本概念とすべてのメタデータの永続的なコピーが多くの場合に機能する場合でも、すべてのデータ構造に異なるソリューションがある可能性があります。
  • 問題は非常にまれである可能性が高いため、ストレステストでも発見されない可能性があります。
  • ストレステストまたは顧客サイトで問題が発生した場合、診断が非常に困難になります。
  • 開発者がこの問題を考慮してコーディングした場合、競合状態でのコードのテストを強制する方法はないようです。 賢者がかつて言ったように、”If it is not tested, it is broken.”(テストしていないなら壊れてる by Bruce Eckel)ということになるでしょう。

Conclusion

永続メモリの可観測性の問題は、永続データの実際の破損を引き起こす可能性があります。破損は非常にまれであるため、診断されることはありません。最善の解決策は、永続的なメモリの場所からのロードが永続的なデータのみを見るようにプロセッサを設計することです。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中