Rethinking File Mapping for Persistent Memory

文献

https://www.usenix.org/conference/fast21/presentation/neal

概要

Persistent MemoryはDRAMとHDD・SSDとの架け橋として注目されている。その中で、PMの高速化の研究が行われているが、IO pathの70%を占めるfile mappingは古い方法を使っている。今回は既存の2つのファイルマッピングの方法に加え、ハッシュテーブルを用いた2つで計4つのファイルマッピングの手法を評価する。

結果としてHashFSという手法は低いメモリーオーバヘッドと低い遅延でベストパフォーマンスを出した。YCSB workloadsにおいて、既存のStrataのページキャッシュextent treesを45%上回った。

file mappingとは?

file mappingとは、デバイス上のファイルのオフセットを、メモリ上の論理オフセットに変換する構造のことである（file mapping構造）。
このfile mapping構造には3つの役割がある。

lookup
insertions
deletions

file mappingの課題

Fragmentation

フラグメンテーションはファイルシステムのオーバヘッドを大きくする一つの要因である。
端的に言うと容量不足。
正確には、全ての連続した領域にファイルを配置できない場合、もしくはファイルを拡大しようとした時に全ての隣接するブロックが他のファイルに使用されているときに起こる。
フラグメンテーションはファイルシステムが大きくなる際には避けることができない、かつ頻繁に発生する。

さらにフラグメンテーションが発生するとsequential accessesの性能が低下する。ごく当たり前だが、メモリをバラバラに配置し直すと読み込む際には強制的にランダムアクセスになるため、性能が低下する。

フラグメンテーションが発生した際には、それを解消するdefragmentationが発生するのだが、これがとても害悪。
OSにおいてこの動作はexpensive operationとされ、時間がかかる。さらに、SSDにおいてdefragmentaitonを行うと、メモリの寿命が10%も低下することがわかっている。PMにおいてもdefragmentationは好ましくない動作である。

lacality

ファイルを読み込む際には、OSはキャッシュを利用することでオーバヘッドを減らすことができる。localityとはつまり、ファイルがある順番に並べられていると、①のファイルにアクセスすると、隣のファイルが次にアクセスされるのを予測し、事前にファイルを読み込んでおくといった動作が可能になる。
また、file mapping構造においてもキャッシュを残しておくと、全てのデータにアクセスする際に毎回構造を辿る必要がなくなり、オーバヘッドが改善される。
さらに、効率的にキャッシュを配置すると、ランダムアクセスに対しても性能が向上するとのこと。

Mapping structure size

ファイルの配置を記憶するマッピング構造そのもののサイズも需要である。一般的にマッピング構造が問題になることはないが、サイズが大きくなるとファイルそのものを扱う領域が圧迫されたり、キャッシュを残す領域が減ってしまい、性能が劣化する。

既存のファイルシステムにおいてマッピング構造がelasticとされる。
つまり、マッピング構造が可変であり、ファイルのサイズや数が増えればそれに応じてマッピング構造のサイズも大きくなるというもの。しかし、メモリを効率的に扱うことができる一方、ファイルに応じてマッピング構造をリサイズするので、オーバヘッドが発生する。

Concurrency（同時変更）

整合性を保ったまま同時変更を可能にすることは、システムにとっては高価な機能である。

Isolationと呼ばれるファイルを孤立させる動作（同時変更するためにロックすること）は、既存のファイルマッピングの構造にとっては簡単である。ファイルのアップデートや読み取り、上書きを行う際は、readに対するロックさえすれば全ての場合に対応することができる。

問題は、writerとreaderが同時に発生した場合である。通常のファイルマッピングでは、特にextent trees(後述)では時々リサイズを行う必要がある。整合性のため、クリティカルセクション内で行われるが、これは構造が閾値を超えた場合のみ行われる。またextent treesは木構造を分割、マージを行う際に部分的な木構造のロックを行うがこれもアップデートの時のみである。

グローバルなファイルマッピング（後述）でも同時変更を念頭に入れて設計する必要がある。ファイルのグローバルアクセスにおいて、木構造の利用は好まれないが、ハッシュを扱う提案手法では、ハッシュ値が被った際にのみロックを行うので比較的簡単である。