日本ソフトウェア科学会第 38 回大会 (2021 年度) 講演論文集

オブジェクトの到達可能性による永続化をリードバリ
アを使わずに実現するアルゴリズムとその予備評価
鵜川 始陽, 松本 康太郎, 岩崎 英哉
到達可能性による永続化は，DRAM と不揮発性メモリ (NVM) を併用するシステムのマネージド言語に適した抽象化のひとつである．この抽象化では，オブジェクトは特定の変数から到達可能になった時に永続化される．これを実現する既存のアルゴリズムは，リードバリアを使って永続化されたオブジェクトにアクセスするため，読み出しとポインタの比較にオーバヘッドがかかる．本研究では，リードバリアを使わずに到達可能性による永続化を実現するア
ルゴリズムを提案する．提案アルゴリズムでは，DRAM 上のオブジェクトを NVM に複製することで永続化する．
プログラムはリードバリアなしに DRAM のオブジェクトを使い続ける一方，書込みでは複製も更新する．複製は書込みバリアによって他のスレッドと非同期に作られるので，並行実行より生じる競合に対処したアルゴリズムになっている．このアルゴリズムを HotSpot VM に実装して評価した．

DRAM の 3 倍遅い．さらに，アプリケーションは

1 はじめに永続するデータを書き込むと，適切なタイミングで近年，不揮発性メモリ (NVM) が登場したことによキャッシュラインを明示的にフラッシュし，NVM 上り，メモリ中のデータを小さいコストで永続化できのデータが不整合なタイミングが存在しないようにるようになった．NVM 登場以前のシステムでは，ア

しなければならない．このキャッシュフラッシュの時

プリケーションは OS の力を借りて，永続化したい間も含めると，書込みには最大で DRAM の 588 倍

データをディスクなどの二次記憶に送るか，ネットの時間がかかる [33]．そのため，既存の NVM を使っワークで他のシステムに送る必要があった．NVM は，たフレームワークでは，一般に NVM と DRAM を

DRAM 同様にバイト単位でアクセスでき，主記憶と併用し，重要なデータだけを NVM に配置するアプ

して DRAM と併用できる不揮発性の記憶装置であローチをとっている．

る．アプリケーションプログラムは，データを NVM永続化するデータを選択する方法や，どの時点のがマップされた仮想アドレスに配置するだけで，そデータが永続化されるかは，フレームーワークによっのデータを永続化できる．つまり，システムの電源が失われるなどのシステムクラッシュがあっても，そのて異なる．例えば，C++用のデファクトスタンダー
ドのフレームワークである PMDK†1 ではプログラマ

データを保持することができる．

が明示的に指定したクラスのインスタンスか，明示的

しかし，現状では，NVM のアクセス速度は DRAMに指定したオブジェクトを永続化する．また，適切にと比べると遅い．Friedman ら [15] によれば読出しはキャッシュラインをフラッシュするのはプログラマの∗ This is an unrefreed paper. Copyrights blong to the

Authors.
Tomoharu Ugawa, 東京大学, The University of Tokyo.
Kotaro Matsumoto, 高知工科大学, Kochi University ofTechnology.
Hideya Iwasaki, 電 気 通 信 大 学, The University ofElectro-Communications.

責任としている．
一方で，近年，Java のようなマネージド言語に適したフレームワークが開発されている．この中には，
到達可能性に基く永続化モデル [6] を採用しているフ†1 https://pmem.io/pmdk/. 古いバージョンは NVML
[22] と呼ばれていた．

レームワークがある．到達可能性に基づく永続化モデ

ための新しいアルゴリズムである，複製永続化を提ルでは，オブジェクトを連結して作ったデータ構造を案する．このアルゴリズムは，AutoPersist に比べ，まとめて永続化することができる．プログラマは永リードバリアが不要であり，永続化されたオブジェク

続化したいデータ構造のルートとなるオブジェクト

トも DRAM から読み出すという利点がある．複製永が格納された static 変数を指定する．これを durable

続化は，データレースのないプログラムを想定して

roots と呼ぶ．ランタイムシステムは，durable roots

いる．そのようなプログラムに対して，durable rootから到達可能なデータが常に永続化されていること

から到達可能な全てのオブジェクトが永続化され，かを保証するように，自動的に必要な動作を行う．このつ，永続化されたオブジェクトが，各スレッドの現在モデルには，他の永続化モデルに比べて二つの利点が実行中か，直前の書込みのいずれかの結果を反映してある．まず，プログラミングが簡単になる．さらに，いることを保証する．データレースのないプログラ

既存のライブラリが内部で作るデータも必要に応じムであっても，永続化している最中のオブジェクトにて自動的に永続化される．

他のスレッドが書込む可能性はあり，その解消は自明

しかし，このモデルを実現するための既存のアルではない．提案アルゴリズムは，起こり得る競合を解

ゴリズムは大きなオーバヘッドを伴う．AutoPersist

消している．提案したアルゴリズムを OpenJDK の[24] は，このモデルを Java に実装した state of the

HotSpot VM のインタプリタに実装し，正しく動作

art である．AutoPersist では，このモデルの実現のすることを確認した．

ために，DRAM 上のオブジェクトが durable rootsから到達可能になると，直ちにそのオブジェクトを

2 準備

NVM に移動させるアプローチをとっている．つま2. 1 用語の定義

り，DRAM 上のあるオブジェクト o1 へのポインタ

本節では，以降で用いる用語を定義する．オブジェ

を NVM 上のオブジェクト o2 のフィールドに書き込

クトとは，プログラムの視点でのデータ構造を指す．

もうとすると，書込みバリアによって，o1 と，o1 か

例えば，

ら到達可能な全てのオブジェクトを NVM にコピー

C x = new C(...);

する．そして，DRAM 上にあるコピーしたオブジェ

によって，変数 x はクラス C のコンストラクタによっ

クトのコピー元には，コピー先を指すフォワーディンて作られたオブジェクトを持つ．永続化されていない

グポインタを残す．以降，コピーされたオブジェク

オブジェクトは揮発性オブジェクト，永続化されたオ

トへのアクセスはリードバリアによって NVM 上のブジェクトは永続化オブジェクトと呼ぶ．

コピーへのアクセスとなる．次のごみ集め（GC）にランタイムシステムは，オブジェクトのデータをよって，コピーされたオブジェクトへの参照が NVM

メモリ上に割り当てる．DRAM 上に割り当てられた上のコピーへの参照で置き換えられ，間接参照は解消

オブジェクトのデータは揮発性コピー，NVM 上に割されるが，アクセスしようとしているオブジェクトがり当てられたデータは永続化コピーと呼ぶ．ただし，フォワーデイングポインタを持つかどうかを調べる

あいまいでない時は，揮発性コピーや永続化コピー

リードバリアは常に必要になる．また，二つの参照がを揮発性オブジェクトや永続化オブジェクトと呼ぶこ

同じオブジェクトを指すかどうかを調べる操作（==演とがある．疑似コードでは，揮発性コピーと永続化コ算子）でも，フォワーディングポインタを調べる必要

ピーをそれぞれ VCopy 型と PCopy 型の変数で表す．

がある．これらのオーバヘッドは，オブジェクトを全く永続化しないプログラムにもかかる．さらに，永続

2. 2 キャッシュラインフラッシュ化されたオブジェクトからの読出しは NVM からのNVM に格納されたデータは電源が失われても保存

読出しとなり，DRAM 上のオブジェクトよりも遅い．

されるが，NVM がマップされた仮想アドレスに書き本研究では，到達可能性に基づく永続化を実現する込んだデータが直ちに永続化される訳ではない．書込みは CPU のキャッシュメモリを介して行われるからである．キャッシュメモリは揮発性であり，電源が失われるとダーティであるキャッシュラインのデータは失われる．書込みを永続化するには，その書込みを行ったキャッシュラインのデータを NVM に書き戻す必要がある．

Intel x64 アーキテクチャ [18] の CPU でキャッシュ(a) C から B への参照の書込み前.

ラインを書き戻すには，CLWB 命令が利用できる．この命令は，指定したキャッシュラインを無効化することなく書き戻す．キャッシュラインを無効化するかど
うかはアルゴリズムの正しさには影響しないので，以降では，キャッシュラインの無効化に関係なく，キャッ
シュラインを書き戻すことを，キャッシュラインをフ
ラッシュすると言う．

(b) C から B への参照の書込み後.
図1

到達可能性に基づく永続化モデル.

CLWB 命令はキャッシュフラッシュが完了するのを待つことなく次の命令を実行する．キャッシュフラッ

ジェクトが揮発性オブジェクトを参照することがない

シュの完了を保証するためには，SFENCE などのメモことを保証する．これによって，NVM 上のデータか

リバリア命令を実行する必要がある．メモリバリア命ら復元する際に，NVM 上の全てのオブジェクトの参令の完了によって，先行する全ての CLWB 命令による照先が NVM 上に存在することが保証される．

キャッシュフラッシュが完了したことが保証される．

例えば，オブジェクト A, B, C, D が図 1 (a) のよより正確には，CLWB 命令によるキャッシュラインフ

うに接続されている場合を考える．ここで x と y は

ラッシュは，不可分な compare-and-swap に用いるプログラム上の変数であり，灰色の変数とオブジェク

ロックプレフィックス付きの命令などのストアフェン

トは永続化されていることを表す．この例では，y がスの機能を持つ命令との間で順序が保証される．まdurable roots として指定されており，それにより C

た，同じアドレスに対する書込みとも順序が保証さが永続化されている．ここで，C から B への参照がれる．

作られたとする．このとき，ランタイムシステムは Bだけでなく，D も永続化し，図 1 (b) のようになる．

2. 3 到達可能性に基づく永続化

D が B から到達可能だからである．

到達可能性に基く永続化モデルには，第 1 章で示したような利点があり，マネージド言語に適したモデ

3 設計

ルである．特に，プログラマは個々のオブジェクトがこの章では，提案アルゴリズムを概観し，シングル

DRAM にあるか NVM にあるかを気にすることなくスレッド向けに簡単化したアルゴリズムを説明する．

プログラミングすることができる．プログラマは，オ

その後，第 4 章でマルチスレッド向けに拡張する．

ブジェクトを作る時にそのオブジェクトを永続化するかどうかを指定する必要はない．全てのオブジェクト

3. 1 永続化モデル

は，作られた時は DRAM 上の揮発性コピーだけを持再起動後，システムのクラッシュ前のデータを正つ．その後，そのオブジェクトが durable roots からしく復元するためには，直観的には，NVM 上のデー

到達可能になった時に，タンタイムシステムが自動的

タが整合性のとれた状態を保つ必要がある．しかし，に永続化する．

NVM に書き込まれる順序がプログラム順序と異なる

ランタイムシスムは，durable roots や永続化オブ可能性があると，NVM 上のデータの整合性がとれた

状態を保つのは難しい．

トが永続化される時，そのオブジェクトを NVM に移そこで，本研究では，先行研究である AutoPersist

動させる．具体的には，そのオブジェクトの永続化コ[24] と同様に，永続化オブジェクトへの書込みの結果

ピーを作り，揮発性コピーの領域に永続化コピーへのが，その書込みが完了するまでに NVM に書き込まフォワーディングポインタを上書きする．その結果，れることを保証する．これにより，同じスレッドが実

オブジェクトは常に揮発性コピーか永続化コピーのい行する複数の書込みは，プログラム順序で永続化さずれか一方を持つことになる．

れる．

例えば，オブジェクト A, B, C, D が図 2 (a) のよ

一方で，複数のスレッドが排他制御せずに同じフィーうに接続されているとする．ここで x と y は変数でルドにアクセスする場合は，この保証では不十分なある．また，灰色は永続化されていることを表す．つことがある．あるスレッド T1 の書込み w1 が永続化

まり，y は durable roots であり，C と D は永続化オされる前に，その値を別のスレッド T2 が読み出し，

ブジェクトである．AutoPersist では，この時の内部スレッド T2 は読み出した値に依存した書込み w2 を

実装は図 2 (b) のようになっている．ここで C や D

行ったとする．このとき，w2 は w1 より早く永続化の移動前の位置は点線の丸で表している．これらはされる可能性がある．例えば，スレッド T1 と T2 がC や D へのフォワーディングポインタを持っており，

次のようなプログラムを並行に実行したとする．

移動前の C や D へのポインタを使ったアクセスがあT1: x.v = 1

ると，リードバリアや書込みバリアによって移動先に

T2: if (x.v == 1) y.v = 1;

対してアクセスされる．さらに，二つの参照が等しい

このとき，x.v = 1 が行われて，その結果が永続化か調べる操作（Java では if acmpeq 命令）でも，一されないうちに，T2 はキャッシュメモリから x.v の方の参照が移動前を，他方が移動先を指すポインタ

値を読み出すことが可能である．その結果，y.v = 1である可能性があるので，適切なバリアが必要であが行われて，その結果が先に永続化されることがある．GC が起こると，A は直接 D を指すようになるる．そこでシステムがクラッシュすると，復元した時が，それでもオブジェクトが移動していないかどうかに x.v == 0 && y.v == 1 ということが起こり得る．

調べるためのリードバリアは必要である．また，永本研究では，データレースのないプログラムのみ続化したオブジェクトは永続化コピーしか持たないを対象とし，このような問題は取り扱わない．なお，ため，永続化したオブジェクトからの読出しは NVM

AutoPersist では，トランザクションの全ての書込みからの読出しになる．

がコミット時に不可分に永続化される永続化トラン

それに対して，提案する複製永続化はオブジェク

ザクションの機能も提供しており，同じフィールドへ

トを複製することによって永続化する．複製永続化のアクセスは，従来のモニタロックを用いるか，永続では，オブジェクトを永続化しても揮発性コピーを化トランザクションを用いて排他制御することになっ保持し続ける．つまり，永続化オブジェクトは揮発性ている．永続化トランザクションは本研究の提案とはコピーと永続化コピーの両方を持つ．揮発性コピー

直交しており，対象としない．

をフォワーディングポインタで上書きするのを避けるため，オブジェクトヘッダ内に専用に設けた pcopy

3. 2 基本的なアイデア

フィールドにフォワーディングポインタを書き込む．

我々は，到達可能性に基づく永続化を実現する新し揮発性コピーと永続化コピーは同じ内容を保持するいアルゴリズムとして，複製永続化を提案する．このように，書込みバリアによって同期する．同じ内容をアルゴリズムはリードバリアを用いず，かつ，永続化保持するとは，プリミティブ型のフィールドは同じ値されたオブジェクトからの読み出しに NVM アクセを保持し，参照型のフィールドに対しては揮発性コ

スを伴わない．

ピーと永続化コピーがそれぞれ同じオブジェクトの揮先行研究である AutoPersist [24] では，オブジェク

発性コピーと永続化コピーを指すポインタを保持す(b) AutoPersist.

(a) プログラマの視点.
図2(c) 複製永続化.

永続化のアプローチ.

ることを言う．

1. 白オブジェクトは永続化コピーを持たない．

複製永続化では，図 2 (a) のヒープの内部実装は図2. 灰色オブジェクトは永続化コピーの領域は持つ

2 (c) のようになる．全てのオブジェクトは DRAM

が，その内容は揮発性コピーと同期していない．

上の揮発性コピーを持つ．さらに，永続化オブジェク

灰色オブジェクトから直接指されるオブジェクト

トは NVM 上の永続化コピーも持つ．図では，C と D

は，永続化コピーを持たないかもしれない．

が揮発性コピーであり，C’ と D’ がそれぞれ対応する

3. 黒オブジェクトは揮発性コピーと同期された永続化コピーである．揮発性コピーは pcopy フィー

永続化コピーを持つ．永続化コピーの存在する

ルドに永続化コピーへのポインタを持つ．

キャッシュラインに対して CLWB 命令も発行してJava プログラムの参照は常に揮発性コピーへのポインタで表現される．つまり，参照を持つ変数はいるが，キャッシュラインのフラッシュは完了していないかもしれない．

揮発性コピーへのポインタか null を持つ．ただし，

4. 青オブジェクトはキャッシュフラッシュが完了

durable roots として指定された static 変数は例外で，している．さらに，青オブジェクトから指される

そのような変数は DRAM と NVM に領域を持ち，揮発性コピーと永続化コピーの両方を持つ．

オブジェクトも青である．
白，灰色，黒の 3 色は，Dijkstra による 3 色の抽象化

アプリケーションがオブジェクトから読み出す時[14] と似ているが，永続化に関する条件も追加されては，永続化されているかどうかに関係なく揮発性コ

いる．青になったオブジェクトはクラッシュの後に復ピーから読み出す．オブジェクトへの参照が揮発性コ元できる．なお，色は説明のためのもので，オブジェ

ピーへのポインタで表現されているので，リードバリ

クトは明示的に色を表すデータを持つことはない．

アは必要ない．一方，永続化オブジェクトに書き込む

オブジェクトを複製する処理は，この 4 色を使って時は，揮発性コピーと永続化コピーを同期させるた説明できる．白オブジェクトを複製するときは，そのめに，書込みバリアによって両方に書き込む．この両オブジェクトの永続化コピーの領域を割り当てて，そ方に書き込む処理を double update と呼ぶ．doubleのポインタを揮発性コピーの pcopy フィールドに書

update の間には，一方だけに書き込まれた瞬間が存込む．これによってそのオブジェクトは灰色になる．

在するが，データレースがないプログラムを仮定し次に，揮発性コピーの内容を永続化コピーにコピーているので，この瞬間を他のスレッドが読む心配はする．このとき，このオブジェクトから指される子オ

ない．

ブジェクトが白であれば，子オブジェクトにも永続化
コピーの領域を割り当て，灰色にする．さらに，永3. 3 オブジェクトの色と不変条件

続化コピーの領域に CLWB を発行することで，そのオオブジェクトを永続化する処理の説明のために，以ブジェクトを黒にする．最後に，そのオブジェクトか下の色でオブジェクトの状態を表すことにする．

ら到達可能な全てのオブジェクトのキャッシュフラッシュの完了を待って，オブジェクトは青，つまり復元可能な状態になる．
複製永続のアルゴリズムは，白，灰色，黒のオブジェクトに対して強い 3 色不変条件を満たす．つまり，不変条件 1 黒オブジェクトが白オブジェクトを直接指すことはない．
また，青オブジェトに関して，不変条件 2 青オブジェクトが青以外のオブジェクトを指すことはない．
これに加えて，次の二つの不変条件も満たす．
不変条件 3 黒か青のオブジェクトでは，書込みバリアの実行中を除いて，揮発性コピーと永続化コピーの内容が一致する．
不変条件 4 青オブジェクトでは，書込みバリアの実行中を除いて，永続化コピーの内容が NVM に書込まれている．
不変条件 3 と 4 より，システムがクラッシュした後でも，クラッシュの時にちょうど書込みバリアを実行していたオブジェクトを除いて，青オブジェクトにつ/∗ make r persistent ∗/ensure_recoverable(VCopy r) {if (shade(r) == TRUE) {/∗ r is gray ∗/worklist.add(r);while (not worklist.empty()) {VCopy o = worklist.remove();
PCopy on = o.pcopy;/∗ Object o is gray ∗/foreach(Field f in o.fields) {VCopy p = o[f];if (shade(p) == TRUE)
worklist.add(p);on[f] = p.pcopy;}
FLUSH_RANGE(on, on.size());/∗ Object o is black ∗/}SFENCE;}}/∗ I f o is white , shade(o) colors o gray andreturns TRUE ∗/shade(VCopy o) {if (o.pcopy != NULL) /∗ o is not white ∗/return FALSE;/∗ Allocate a persistent copy ∗/o.pcopy = alloc_NVM(o.size());
return TRUE;}

いては，揮発性コピーと同じ内容の永続化コピーがNVM 上に存在する．システムがクラッシュした時に

図3シングルスレッド版 ensure recoverable.

ちょうど書込みバリアが実行されていたオブジェクトについては，揮発性コピーだけが更新されている可能存在しない．つまり，全てのオブジェクトは白か青で性がある．そのような場合は，書込み前にクラッシュある．

したとみなす．データレースのないプログラムでは，永続化するオブジェクトの揮発性コピーへのポ

揮発性コピーだけが更新された状態が他のスレッドかインタを r とする．ensure recoverable は，まず，ら観測されておらず，書込みの前にクラッシュしたと

shade を呼び出して，r で指されるオブジェクトが白みなしても NVM のデータの一貫性が崩れることはであれば灰色にする．この処理は，r に永続化コピー

ない．さらに，不変条件 2 より，NVM 上のオブジェの領域を割り当て，そのポインタを揮発性コピーのクトの参照先は NVM に存在することが保証できる．

pcopy フィールドに書き込むことにより行われる．
その後，灰色オブジェクトを管理するワークリスト

3. 4 シングルスレッド版永続化アルゴリズム

worklist を使って，r から到達できる白オブジェク

まず，簡単のために，シングルスレッドのプログラ

トを再帰的にたどり，灰色を経由して黒に変える．具ムを仮定して永続化のアルゴリズムを説明する．図 3

体的には，ワークリストから灰色オブジェクト o をに永続化処理の関数 ensure recoverable を示す．こ取り出し，

こで，オブジェクト o のフィールド f を o[f] と書く．

1. o のフィールド f に書き込まれたポインタ p を

簡単のために，全てのオブジェクトは，ただ一つの参

shade 関数に渡して p で指されるオブジェクト

照型のフィールドを持つとする．シングルスレッドプ

を灰色にする．

ログラムを仮定しているので，ensure recoverable
が呼び出されたとき，永続化の最中のオブジェクトは

2. p の永続化コピーへのポインタを o の永続化コ
ピーのフィールド f に書込む．

シュと SFENCE を実行するとオーバヘッドが大きい
putfield(VCopy o, Field f, VCopy v) {PCopy on = o.pcopy;
if (on == NULL) {/∗ o is white ∗/o[f] = v;
return;}/∗ o is blue ∗/ensure_recoverable(v);o[f] = v;
on[f] = v.pcopy;
FLUSH(&on[f]);SFENCE;}

が，これは必要なコストである．なお，既存研究である AutoPersist [23] [24] でも同じ処理を行っている．

4 並列実行
第 3 章で示したアルゴリズムは，マルチスレッド環
境では正しく動作しない可能性がある．本アルゴリズ
ムは，データレースのないプログラムを仮定しているが，それでも，マルチスレッド環境では以下に挙げる
競合が起こる可能性があるからである．

図4

シングルスレッド版 putfield.

1. あるスレッドが putfield である白オブジェク
ト o に書き込んでいる最中に，別のスレッドが oo の全てのフィールドを処理し終えたら，o の永続化

を永続化する．

コピーが配置されている全てのキャッシュラインのフ2. あるスレッドがオブジェクト o を永続化していラッシュを開始する．フラッシュの完了は，ここではる最中に，別のスレッドが putfield で o に書待たない．この時点で，o は黒になる．

込む．

最後に，r から到達できる全ての白だったオブジェ
クトが黒になると，SFENCE 命令を発行し，これらの黒オブジェクトを同時に青にする．

3. 複数のスレッドが同時に同じオブジェクト o を永続化する．
プログラマは注意深くプログラミングすることで，プ
ログラム上のデータレースは避けることができる．一3. 5 書込みバリア

方，オブジェクトの永続化はランタイムシステムが自図 4 にシングルスレッド版の書込みバリアを示す．

動的に行うため，オブジェクトを永続化する処理が関

putfield は v を o のフィールド f に書き込む関数

連する競合はプログラマが避けることはできない．こである．putfield では，3. 3 節で示した不変条件をれは，我々の目指すマネージドランタイムに適した永守るために，二種類の書込みバリアを用いる．

続化モデルでは，オブジェクトの永続化状態はプログ

まず，不変条件 2 を守るために，挿入バリア [14] をラマが気にする必要がないためである．例えば，上記用いる．シングルスレッドプログラムを仮定している

3 の競合は，複数のスレッドが o や青でないオブジェ

ので，o の pcopy フィールドが NULL でなければ o はクトだけをたどって o に到達できるオブジェクトの参青である．青オブジェクトに書き込む時は，書き込む値

照を，同時に永続化オブジェクトに書込むことで起こ

v が青であるよう，書込み前に ensure recoverable

る．この競合はプログラマには制御できず，ランタイ関数で v を青に変える．

ムシステムが解決する必要がある．

次に，不変条件 3 を守るために，揮発性コピーとこの章では，上記の競合条件を，Intel x86 などの永続化コピーの両方に書き込む double update バリ

total store ordering (TSO) [1] のメモリ一貫性を持

アを用いる．o のフィールド f に v を書き込む時は，

つ CPU でどのように解決するかを示す．

同時に，v の永続化コピーへのポインタ v.pcopy を

o の永続化コピーのフィールド f に書き込む．
さらに，不変条件 4 を守るために，永続化コピー

4. 1 オブジェクトを永続化するスレッド間の依存関係の書き込んだフィールドに対してキャッシュフラッ

ensure recoverable 関数（図 3）は，引数の r かシュを発行し，それが完了するのを SFENCE で待つ．

ら青でないオブジェクトだけをたどって到達できる全永続化オブジェクトに書込むたびにキャッシュフラッてのオブジェクトを青にする．この，r から青でないshade(VCopy o) {PCopy on = alloc_NVM(o.size());
PCopy fwd;
while ((fwd = CAS(&o.pcopy, NULL, on)) == BUSY);
if (fwd != NULL) {/∗ o is gray , black , or blue ∗/t = responsible_thread(fwd);
if (t != current_thread) {/∗ thread t is making o recoverable ∗/depends_on(t);}return FALSE;}
return TRUE;}
図5

PS 集合.
図6

マルチスレッド版 shade.

オブジェクトだけをたどって到達できるオブジェクトの集合を ensure recoverable を呼び出したスレッ

ルドに書き込む．ここで，CAS は第一引数のアドレス

ドの永続化対象集合（persistent subject 集合; PS 集の値が第二引数の値と一致すれば，不可分に第三引数合）と呼ぶことにする．複数のスレッドが並行しての値で更新する関数とし，戻り値は更新の成否によらensure recoverable 関数を呼び出すと，これらのず，関数実行前に第一引数のアドレスに書かれていた関数の PS 集合が重なる可能性がある．PS 集合が値とする．CAS の戻り値が NULL であれば，CAS が成重なるスレッドの関係の推移閉包は同値関係になる．

功したことを表す．このとき，o は灰色になり，このこの同値関係による同値類を干渉スレッドグループ

スレッドが o の担当スレッドになる．図 6 では，担(interfering thread group; ITG) と呼ぶことにする．

当スレッドは responsible thread 関数で得られる

例 え ば ，図 5 の よ う な 状 況 を 考 え る ．こ こ で ，としている．responsible thread の実装は第 5 章

ス レッド S と T が そ れ ぞ れ A と D を 引 数 にで述べる．

ensure recoverable を呼び出したとする．このとCAS が失敗した場合，以下の状況が考えられる．

き，S の PS 集合は {A, B, C, E, F, H} であり，T の• オブジェクト o が CAS を実行しているスレッド

PS 集合は {C, D, E, F, G, H} である．二つの PS 集合

自身によって既に灰色にされていた場合．オブには重なりがあるので，S と T は同じ ITG に属する．

ジェクトグラフが循環を含むような場合に，こ複数のスレッドの PS 集合に重なりがあるとき，このようなことが起こる．o が既に灰色になっておれらのスレッドは同じオブジェクト o を永続化しより，カレントスレッドが担当スレッドになっていうとする．この競合を解決するために，o にフォワー

るので，加えて何かする必要はない．

ディングポインタを書込む操作に不可分な compare-• オブジェクト o が他のスレッド t によって灰色

and-swap を使い，これに成功したスレッドが o を黒や黒になっている場合．この場合は，担当スレッにすることにする．このスレッドを o の担当スレッ

ドは t である．depends on 関数によって，カレドと呼ぶ．

ントスレッドと t が同じ ITG に属することを記

図 6 にマルチスレッド版の shade 関数を示す．もし永続化対象オブジェクト o の pcopy フィールドがNULL であれば，o は白である．このスレッドは，永録する．

• o が既に青になっている場合．この場合は何もする必要がない．

続化コピーの領域を割り当てて，そのポインタを不可• 他のスレッドが putfield によって o に書き込

分な compare-and-swap（CAS）命令で pcopy フィー

んでいる最中の場合．この場合，4. 3 節で後述するように，o の pcopy フィールドには特別な値

BUSY が書込まれている．カレントスレッドは書込みが終わって BUSY がクリアされるまで待つ．
詳細は 4. 3 節で述べる．

4. 2 同一 ITG に属するスレッド間のバリア同期
スレッド T の PS 集合に，別のスレッド S が担当
スレッドであるオブジェクトが属するとき，T が Sに依存しているという．不変条件 2 を守るためには，T がスレッド S に依存しているとき，S が S の PS
セットを青にするまでは，T は T の PS セットを青にできない．しかし，同一 ITG に属するスレッドは，互いに依存する可能性がある．例えば，図 5 で，C とE の担当スレッドがそれぞれ S と T だったとする．
このとき，C について T は S に依存する．一方で，E について S は T に依存する．
このような場合には，S と T が同時にそれぞれのPS 集合を青にする．そのために，各スレッドは PS
集合を黒にし，SFENCE を実行した後，同一 ITG に属

ensure_recoverable(VCopy r) {if (shade(r) == TRUE) {worklist.add(r);while (not worklist.empty()) {VCopy o = worklist.remove();
PCopy on = o.pcopy;/∗ o is gray ∗/#RETRY:/∗ copy ∗/for (Field f in o.fields) {VCopy p = o[f];if (shade(p) == TRUE)
worklist.add(p);on[f] = p.pcopy;}#
MFENCE;
CLWB_RANGE(on, on.size());#/∗ verify ∗/#foreach (Field f in o.fields)#
if (o[f].pcopy != on[f])#goto RETRY;/∗ complete −− o is black ∗/}SFENCE;/∗ We s t i l l don ’ t know about the color of
objects beyond the objects for which otherthreads are responsible . ∗/}SYNC();/∗ r ’ s transitive closure is blue ∗/}するスレッドとバリア同期をとる．このバリア同期の完了をもって，この ITG に属するスレッドの PS セッ

図7

マルチスレッド版 ensure recoverable.

トに属する全てのオブジェクトは同時に青になる．
図 7 はマルチスレッド版の ensure recoverable
である．この関数の最後でバリア同期（SYNC）を実認すると同時に，そのオブジェクトが灰色にならない
ようにロックをかける．

行している．SYNC 以外のシングルスレッド版との違

図 8 に マ ル チ ス レッド 版 の putfield を 示 す．

いは#の印の行である．この違いの詳細は 4. 4 節で述

putfield を実行しているスレッドは書込み先のオブべる．

ジェクト o に対して，o が白であれば pcopy フィール
ドに特別な値 BUSY を書込むことで，ロックをかける．

4. 3 白オブジェクトへの書込み

o が白であるかどうかは pcopy が NULL かどうかであるスレッド T が白オブジェクト o に書き込んで判定する．この判定と書込みは，不可分な compare-

いる最中に別のスレッド S が o を永続化しようとす

and-swap 命令により行う．他のスレッドが既にロッる可能性がある．T は o が白から灰色や黒に変わった

クをとっていた場合は，CAS 命令は BUSY を返す．こことに気づかなければ，T は double update バリアの場合，BUSY がクリアされるのを待つ．CAS 命令がを実行せず，不変条件 3 に反して o の揮発性コピー

BUSY でも NULL でもない値を返すと，o が白ではなと永続化コピーに不整合が生じる．さらに，スレッド

かったことを意味する．このときは，3. 5 節で述べた

T は白オブジェクトへのポインタを黒や青に変わっように，挿入バリアと double update バリアを実行たオブジェクト o に書き込んでしまうかもしれない．

する．

その結果，不変条件 2 が崩れることになる．このよ

参照ではなくプリミティブ型の値を書き込む時はバ

うな問題を防ぐために，白オブジェクトに書き込もう

リアを簡単にできる．不変条件 2 が崩れる心配がないとするスレッドは，オブジェクトが白であることを確からである．プリミティブ型の値を書き込む putfieldo の永続化コピー on にコピーしているとする．この
putfield(VCopy o, Field f, VCopy v) {PCopy on;while ((on = CAS(&o.pcopy, NULL, BUSY)) ==BUSY);
if (on == NULL) {/∗ o is white ∗/o[f] = v;o.pcopy = NULL;
return;}/∗ o is gray , black , or blue ∗/ensure_recoverable(v);PCopy vn = v.pcopy;o[f] = v;
on[f] = vn;
CLWB(&on[f]); /∗ write back the cache line
for o. f in persistent copy ∗/SFENCE;}

とき，別のスレッド S がほぼ同時に v を f に書き込んだとすると，以下のような順序で実行される可能性
がある．
step

1:

thread T

thread S

p = o[f]2:o[f] = v

3:

on[f] = v.pcopy

4:on[f] = p.pcopy

その結果，S によって NVM 上の on[f] に書かれた

v は T によって上書きされ，失われてしまう．これ
により，不変条件 3 が崩れる．
この競合は，並行コピー GC である Transactional

図8

マルチスレッド版 putfield （参照用）.

Sapphire GC [28] で使われているコピープロトコル
を用いて解決する．このプロトコルは，データレース

putfield(VCopy o, Field f, Primitive v) {o[f] = v;
MFENCE;
PCopy on = o.pcopy;
if (on == NULL || on == BUSY) {/∗ o is white ∗/return;}/∗ o is gray , black , or blue ∗/on[f] = v;
CLWB(&on[f]);SFENCE;}のないプログラムに対して，TSO メモリ一貫性モデ
ルの CPU で利用できる，高速に一貫性を保ちながらコピーするプロトコルである．図 7 の “#” の印を付けた行がこのプロトコルを実装している．
このコピープロトコルはコピーと検証の二つのステップからなる．コピーステップでは，通常のロードとストア命令を使ってナイーブに揮発性コピーから永続化コピーにフィールドの値をコピーする．この時，並行して他のスレッドが書き込んでいるかもしれない．検証ステップでは，他のスレッドの書込みが

図9

マルチスレッド版 putfield （プリミティブ用）.

なかったか，あるいは影響のない書込みだったことを検証する．具体的には，検証ステップになっても，を図 9 に示す．この putfield は，まず無条件に v を

o の揮発性コピーに書き込む．その後，pcopy フィー
ルドを調べて，o が白かどうかを確認する．もし白であれば，白のオブジェクトの揮発性コピーに値を書き込んだことになっており，これ以上することはない．
白でなければ，double update バリアを実行する．揮
発性コピーへの書込みと，オブジェクトの色を調べる

ensure recoverable がコピーステップで読み出したのと同じ値が揮発性コピーから読み出せることを確認する．検証に失敗すれば，コピーステップに戻ってやり直す．コピーステップと検証ステップの間にはMFENCE を実行し，書込みが完了する前に検証を始めるのを防ぐ．このプロトコルの正しさは，文献 [27] で検証している．

読出しとの間には，オブジェクトの色を調べる前に書込みが完了するように MFENCE を実行する．

4. 5 補助関数
複製永続化のアルゴリズムは，responsible thread,

4. 4 コピーと書込みの競争
いま，スレッド T が o を引数に ensure recoverable
関数を実行しており，その中で，o のフィールド f を

depends on, SYNC の三つの補助関数を用いる．ここでは，これらの補助関数が満たすべき条件を述べる．

responsible thread 関数はオブジェクト o の永続

オブジェクトが青になるとクリアする．

化コピーのポインタを受けとり，o が灰色か黒であれば，具体的には，shade 関数（図 6）内の alloc NVM がその担当スレッドを返す．o が青であれば，NULL を返す

永続化コピーに対して 2 ワード余分にメモリを割りことが期待される．しかし，o が青になるのは，o の担当てる．この 2 ワードは，担当スレッドへのポイン

当スレッドと同じ ITG に属する最後のスレッドがバリタを保持するためと，同じ担当スレッドを持つオブ

ア同期に到達した瞬間なので，responsible thread

ジェクトのリストを構成するために用いる．永続化がブロックせずに，そのタイミングを正確に知るの

コピーの領域を割り当てると，そのポインタを揮発は難しい．そこで，responsible thread は青のオブ

性コピーに書き込む前に担当スレッドへのポインタ

ジェクトに対しては，NULL の他に，どんなスレッドを書き込む．これにより，永続化コピーへのポインタを返してもよいことにする．

を揮発性コピーに書き込むことに成功すると同時に，

depends on 関数は responsible thread 関数が返

このスレッドが担当スレッドになる．担当スレッドがした，o の担当スレッドと期待されるスレッド T を引バリア同期 (SYNC) を抜けると，リストに連結された数に受け取る．depends on は，カレントスレッドがオブジェクトの担当スレッドポインタをクリアする．

属する ITG と T が属する ITG を併合する．
ただし，depends on が呼び出された時には，T は

5. 2 Recoverable Bit

既に ensure recoverable を抜けている可能性があ

複製永続化のアルゴリズムでは，オブジェクトが青る．より正確には，SYNC によるバリア同期を終えてかどうかの判定は頻繁に行われる．青かどうかの判いる可能性がある．depends on 関数はこのようなス定は，(1) 揮発性コピーの pcopy フィールドが NULL

レッドを検出して，誤った処理をしないようにしなけ

でないことを確認し，さらに (2) 永続化コピーの担当

ればならない．幸いなことに，ITG の仕組みを素直

スレッドのポインタが NULL であることを確認するこに実装すると，各スレッドはスレッド構造体に，どのとで判定できるが，この判定には時間がかかる．そこITG に属するかを示すフィールドを持つことになる．

で，各オブジェクトの揮発性コピーに青になるとセッ

そのため，スレッドがいずれかの ITG に属するかどトされる recoverable bit を持たせる．NVM 上のオブうか調べることで，ensure recoverable の実行中

ジェクトは 8 バイトに整列されていることを利用しかどうかを判定できる．また，ensure recoverableて，recoverable bit には pcopy フィールドの最下位を抜けたスレッドが別のオブジェクトの永続化のたビットを流用する．

めに再度 ensure recoverable の実行を始めた場合，

recoverable bit がクリアされていても青である可

本来依存していないスレッド間でもバリア同期を行う

能性はあるので，その場合は，詳細に調べる必要があことになるが，正しさに影響はない．

る．しかし，recoverable bit がクリアされている場
合，過渡的な場合を除いて，そのオブジェクトは白で5 実装

あり，pcopy フィールドが NULL である．そのため，複製永続化のアルゴリズムが正しく動作することほとんどの場合は，pcopy を調べるだけで青かどうかを確認するために，我々は，OpenJDK の HotSpot

を判定できる．

VM のインタプリタに実装した．ここでは，実装の詳
細を説明する．

6 評価
第 5 章で示した実装を用いて，性能を評価した．こ

5. 1 担当スレッドの評価は，提案アルゴリズムが既存研究である Au-

responsible thread は，永続化コピーに担当ス

toPersist より高速であることを定量的に示すためのレッドへのポインタを持たせることで実現する．このものではなく，提案アルゴリズムに予想外のオーバ

ポインタは，永続化コピーを作るときに設定し，そのヘッドがないことを確認するためのものである．この

章では，実験の結果に加えて，既存研究との定性的な

表1

ベンチマクプログラムの基本データ.

比較を示す．既存研究との定量的な比較は今後の課題

time

である．

name
avrorawrites(s)pri (M/s)ref (M/s)

17.7

23.47

1.23

6. 1 Evaluation Settings

fop

7.6

2.56

0.90

本研究では，OpenJDK 13 の JIT コンパイラを

h2

110.6

0.87

0.42

無効化した HotSpot VM を用いた．また，DRAM

jython

86.9

2.02

1.42

領域の GC には stop-the-world の serial GC を用い，

luindex

13.7

6.48

0.67

NVM 領域には GC は実装していない．しかし，NVM

lusearch

2.7

123.1321.81の領域は十分に大きく，ベンチマークプログラムの実

lusearch-ﬁx

2.7

121.7821.57

行で NVM の領域が不足することはなかった．NVM

pmd

7.9

8.65

5.02

のメモリ割り当てのためには，各スレッドには 50KB

sunﬂow

14.2

49.70

6.27

のスレッドローカルアロケーションバッファを持た

tradebeans

82.8

2.97

1.90

せた．

tradesoap

36.0

13.71

6.40

xalan

3.5

60.34

12.14

実験環境の計算機には，128 GB の第一世代 In-

tel Optane DC persistent memory を 2 枚搭載した．
CPU は Intel Xeon Gold 6240 (18 コア，36 スレッド，

はなされていない．そこで，恣意的に durable roots

クロックは 2.60 GHz に固定) を 1 台搭載し，DRAM

を選ぶのを避けるために，durable roots を全く指定

は 48 GB の DDR4 を搭載した．OS は Linux 4.8

しない none-durable と，全ての static 変数を durable

Ubuntu 18.04.5 LTS を用いた．NVM は NOVA ファ

roots とする all-durable の二つの設定で実験した．

イルシステムでフォーマットし，アプリケーション

DAX モードで mmap して用いた．HotSpot VM は

6. 2 基本的オーバヘッド“server” の設定でビルドした．この環境での初期ヒー

複製永続化には，オブジェクトを一切永続化しなくプサイズは 734 MB，最大ヒープサイズは 11 GBても発生する基本的オーバヘッドが存在する．その原だった．

因は以下の二つである．

ベンチマークプログラムには DaCapo ベンチマー
ク集 [9] バージョン dacapo-9.12-MR1-bach を用いた．

1. 書込み中に他のスレッドがそのオブジェクトを永続化するのを防ぐためのロック

評価には，複製永続化を実装していない HotSpot VM

2. double update が必要かどうかのチェックでも実行できなかった batik, eclipse, tomcat を除く

前者は，図 8 の CAS 命令によるもので，参照を書き

全てのベンチマークプログラムを用いた．各実行では込む putfield のたびに実行される．後者は，チェッ

十分にウォームアップし，各イテレーションの実行時

ク自身は軽量だが，プリミティブ型の値を書き込む時間が収束するまで繰返した（-C オプション）．さらには，チェックの前に MFENCE 命令が必要になり（図に，各ベンチマークを最低 5 回実行した．実験結果

9 参照），このコストは無視できない．

のグラフには，中央値と四分位点を示している．

none-durable の設定を用いて，基本的オーバヘッド

表 1 に DaCapo ベンチマーク集のプログラムの基を計測した．図 10 の左の棒でオリジナルの HotSpot

本的な性質を掲載する．time は，複製永続化を実装

VM を基準にした実行時間の比と各書込みバリアに費していない HotSpot VM での実行時間，pri はプリ

した時間の内訳を示す．‘no barrier’ はバリアを無効

ミティブ型の書込み頻度，ref は参照の書込み頻度で化した時の実行時間，‘primitive write’ はプリミティ

ある．

ブ型の書込みバリアだけを有効にした時の実行時間

ベンチマークプログラムには durable roots の指定の差分，‘reference barrier’ は，さらに参照の書込み

バリアを有効にした時の実行時間の差分である．fop,

小さいため，スレッド当たりの書込み頻度は大きい．

luindex, luindex-ﬁx, sunﬂow については，参照の書込

なお，double update は NVM に書き込む時間と書

みバリアを有効にた方が参照の書込みバリアを無効に込みをフラッシュする時間を含んでいる．NVM へのするよりも高速に実行されたため，参照の書込みバリ

書込みは，NVM を使って永続化するためには必ず行

アの時間は 0 としている．同様に，h2, jython, xalan

う必要がある．それ以外の永続化のコストは，NVM

では，プリミティブ型の書込みバリアの時間を 0 とへの書込みの時間と比べると十分に小さい．

している．
全体のオーバヘッドは最大で avrora の 11.6 %だっ

6. 4 AutoPersist との定性的な比較

た．参照の書込みバリアとプリミティブ型の書込みバ

複製永続化は，既存研究である AutoPersit で用い

リアのどちらが大きなオーバヘッドになるかはベンているリードバリアと，永続化オブジェクトから読みチマークプログラムによって異なった．全体に，表 1

出す際の NVM へのアクセスを行わないように設計

でプリミティブ型の書込みが頻繁なプログラムで，プした．ここでは，書込みバリアのコストを定性的に比リミティブ型の書込みバリアのオーバヘッドが大きい

較する．

傾向にある．

まず，永続化されていないオブジェクトへの書込み

書込みバリアのオーバヘッドの主な原因は，MFENCEを考える．AutoPersist の書込みバリアでは，永続化

命令と CAS 命令と考えられる．これらの命令は CPU

されていないオブジェクトであっても，最低でも 1 回

が out-of-order 実行できる命令に制限を付け，それがの MFENCE が必要になる．これは，書込みの最中にこなくなると，CPU のストールを引き起こすためであのオブジェクトが永続化されたのを検出するためである．それを確認するために，MFENCE を消し，CAS をる．これに対して複製永続化では，プリミティブの値

通常のロードとストア命令の組合わせに置き換えた実の書込みでは MFENCE が，参照の書込みでは CAS が行を計測した．その結果を図 10 の右の棒で示す．こそれぞれ 1 回必要になる．したがって，AutoPersistの結果，MFENCE と CAS を実行しないようにした VMと複製永続化には，参照の書込みにおける MFENCE とでは，‘no barrier’ と同等の実行速度となった．このCAS の違いがある．

ことから，MFENCE と CAS が主な原因と確認できた．

次に永続化されたオブジェクトへの書込みを考える．永続化したオブジェクトへの書込みでは，複製永6. 3 永続化のコスト続化では DRAM と NVM の両方に書き込む必要がall-durable の設定を用いて，永続化のコストを計測ある．一方で，AutoPersist では NVM への書込みだ

した．表 2 にプログラムの実行を通して 1 秒当たりけでよい．しかし，NVM への書込みは DRAM へのに永続化されたオブジェクトの数，ワード数を掲載す

書込みと比べて最大で 588 倍も遅い [33]．そのため，る．また，永続化されたオブジェクトの 1 ワード当た

DRAM への書込みの時間は無視でき，AutoPersit とりのキャッシュライン数 (cl/obj) と，1 秒当たりにフ複製永続化のオーバヘッドはほぼ同等と言える．

ラッシュしたキャッシュラインの数，永続化オブジェ
クトへの書込みの頻度（pri と ref でそれぞれプリミ

7 関連研究ティブ型と参照の書込みを表す）も掲載する．

プログラミング言語の分野で NVM を利用する研図 11 に all-durable の実行時間とその内訳を示す．

究には，NVM を大容量な DRAM として用いる方向

永続化のコストの大部分は double update(‘WUPD’)がある [30] [2]．この方向の研究では，永続化は興味のによるものだった．特に，表 2 で永続化オブジェクト対象になっておらず，アプリケーションのスループッ

への書込みが多いプログラムで double update のオートを高めたり，NVM の寿命への対処をしたり，消費バヘッドが大きい．luindex は書込みの頻度が lusearch

電力を抑えることが興味の対象になっている．

などと比べると小さいが，このプログラムは並列度がもう一つの研究の方向はデータを永続化する方向で

/PSNBMJ[FE&YFDVUJPO5JNF

SFGFSFODFXSJUFQSJNJUJWFXSJUFOPCBSSJFS
OP.'&/$&$"4







SB

SP
BW

Q
GP

I

KZ

PO
UI

Y
EF

JO
MV

DI
BS
TF

MV

BS
TF
MV

JY
G
DI

QN

E
O
TV

GMP

X
US

Q
OT
PB
FB
FT
FC
BE
BE
US

O
MB
YB

#FODINBSL

図 10
表2

none-durable の設定での実行時間.

オブジェクトの永続化と永続化オブジェクへの書込み回数.

persistent objects
namepersistent writes(Kobj/s)(Kword/s)

cl/obj(Mcl/s)pri (M/s)ref (M/s)

total (M/s)

4.5

32.1

1.8

0.0

6.3

0.3

6.6

fop

9.9

145.4

2.7

0.0

0.2

0.0

0.2

h2

19.7

215.7

2.2

0.0

0.3

0.2

0.5

jython106.8

1160.0

2.2

0.2

0.3

0.1

0.5

luindex

3.3

60.6

3.2

0.0

1.3

0.2

1.4

lusearch

203.6

1439.8

1.8

0.4

24.0

4.4

28.4

lusearch-ﬁx

209.7

1483.1

1.8

0.4

24.7

4.5

29.2

pmd

86.9

992.7

2.3

0.2

0.0

0.0

0.1

sunﬂow

1.4

21.6

2.8

0.0

0.0

0.0

0.0

tradebeans

180.5

1667.9

2.0

0.4

0.2

0.2

0.5

tradesoap

415.0

5437.1

2.5

1.0

3.4

1.2

4.6

xalan

231.5

10657.0

6.6

1.5

17.7

3.2

20.9

avroraある．この方向では，どのように NVM をプログラミ

をトランザクションと組合わせているという点で，以ング言語に組み込むかが議論されている．Mnemosyne

前のシステムを踏襲している．

[29] と NV-Heaps [13] は NVM とトランザクションをマネージドランタイムでは，トランザクションや組合わせた初期の研究である．これを発展させた，ロックよりも密接に言語に連携した永続化モデルが可

永続化トランザクションは盛んに研究されている能になる．マネージドランタイムでは，書込みバリア[7] [11] [8] [16]．Atlas [12] は NVM とロックを組み合わによって自動的に書き込んだデータのキャッシュライ

せたシステムである．このプログラミングモデルはンをフラッシュできる．AutoPersist [24] はキャッシュ

Boehm [10] によって議論されている．Espresso [32] はラインのフラッシュにランタイムシステムが責任を持

NVM をマネージドランタイムである Java VM に組つシステムである．AutoPersist は，研究用の Java合わせたシステムである．しかし，Espresso は NVM

VM である Maxine VM [20] に到達可能性による永/PSNBMJ[FE&YFDVUJPO5JNF

861%



FOTVSF@SFDPWFSBCMF
FYFDVUJPO








SB

SP
BW

Q

GP

I

KZ

PO
UI

Y
EF

JO
MV

DI
BS
TF

MV

BS
TF
MV

JY
G
DI

QN

E

X

GMP

O
TV

US

Q
OT
PB
FB
FT
FC
BE
BE
US

O
MB
YB

#FODINBSL

図 11

all-durable の設定での実行時間（オリジナル VM の時間で正規化）.

続化 [23] を実装した．AutoPersist は永続化するオブジェクトを直ちに NVM に移動させるアプローチを

8 おわりにとった．このバリアのオーバヘッドは QuickCheck [25]

本研究では，オブジェクトの到達可能性に基づく永の文献で評価されており，JIT を有効にした Maxine

続化を実現する新しいアルゴリズムとして，複製永続

VM の実行の 8.8 %程度と報告されている．しかし，化を提案した．このアルゴリズムは，既存研究である

QuickCheck は AutoPersist の実現に必要なメモリバ

AutoPersist のオーバヘッドの原因であるリードバリ

リア（MFENCE）のオーバヘッドを計測していない．そアと，永続化されたオブジェクトからの読み出しにのため，8.8 %はメモリバリアの時間を含まないオー

NVM へのアクセスを伴う点を解決している．また，バヘッドと考えられる．P-INSPECT [19] はバリアの書込みバリアで行うメモリバリアを伴う命令の回数

オーバヘッドを緩和するためにハードウェアを拡張すは AutoPersist と同等である．

ることを提案している．GCPersist [31] はオブジェク

アルゴリズムの設計では，マルチスレッド環境で起トの永続化を次の GC まで遅延することで，オブジェ

こる可能性のある競合を指摘し，それを解消するアルクトの永続化がすぐに行われない代わりにオーバヘッ

ゴリズムを示した．さらに，OpenJDK の HotSpot

ドを大幅に削減した．

VM にプロトタイプを実装し，正しく動作すること到達可能性に基く永続化のモデルは，orthogonallyを確認した．

persistence [6] [5] [3] に関する一連の研究で提案されJIT コンパイラを有効にした HotSpot VM に実装たものである．Atokinson ら [6] は一般的な二次記憶

し，先行研究との定量的な評価を行うことは今後の課を使ってオブジェクトを永続化するシステムを提案し題である．

た．PJama プラットフォーム [4] はその実装である．
複製永続化では，GC のテクニックを利用している．

謝辞 本研究の一部は，JSPS 科研費 19K11904 の助成を受けたものです．

複製は Nettles [21] らによって提案された．double

update バリアは複製に基づく GC [17] [26] [28] で使

参 考 文 献われている．さらに，複製永続化では Transactional[ 1 ] Adve, S. V. and Gharachorloo, K.: Shared Memory Consistency Models: A Tutorial, Computer,Vol. 29, No. 12(1996), pp. 66–76.
[ 2 ] Akram, S., Sartor, J. B., McKinley, K. S., andEeckhout, L.: Write-rationing garbage collection
for hybrid memories, Proceedings of the 39th ACM

Sapphire [28] の並行コピープロトコルを利用している．

SIGPLAN Conference on Programming Language
Design and Implementation, PLDI 2018, Philadelphia, PA, USA, June 18-22, 2018, Foster, J. S. and
Grossman, D.(eds.), ACM, 2018, pp. 62–77.
[ 3 ] Atkinson, M. P., Daynès, L., Jordan, M. J.,
Printezis, T., and Spence, S.: An Orthogonally Persistent Java, SIGMOD Rec., Vol. 25, No. 4(1996),
pp. 68–75.
[ 4 ] Atkinson, M. P. and Jordan, M. J.: Issues Raisedby Three Years of Developing PJama: An Orthogonally Persistent Platform for Java, Database
Theory - ICDT ’99, 7th International Conference,
Jerusalem, Israel, January 10-12, 1999, Proceedings, Beeri, C. and Buneman, P.(eds.), Lecture
Notes in Computer Science, Vol. 1540, Springer,
1999, pp. 1–30.
[ 5 ] Atkinson, M. P., Jordan, M. J., Daynès, L., andSpence, S.: Design Issues for Persistent Java: A
Type-Safe, Object-Oriented, Orthogonally Persistent System, Proceedings of the 7th Workshop on
Persistent Object Systems, Cape May, New Jersey,
USA, 1996, Connor, R. C. H. and Nettles, S.(eds.),
Morgan Kaufmann, 1996, pp. 33–47.
[ 6 ] Atkinson, M. P. and Morrison, R.: Orthogonally Persistent Object Systems, VLDB J., Vol. 4,
No. 3(1995), pp. 319–401.
[ 7 ] Avni, H., Levy, E., and Mendelson, A.: Hardware Transactions in Nonvolatile Memory, Distributed Computing - 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9,
2015, Proceedings, Moses, Y.(ed.), Lecture Notes
in Computer Science, Vol. 9363, Springer, 2015,
pp. 617–630.
[ 8 ] Baldassin, A., Murari, R., de Carvalho, J. P. L.,
Araujo, G., Castro, D., Barreto, J., and Romano,P.: NV-PhTM: An Eﬃcient Phase-Based Transactional System for Non-volatile Memory, EuroPar 2020: Parallel Processing - 26th International
Conference on Parallel and Distributed Computing,
Warsaw, Poland, August 24-28, 2020, Proceedings,
Malawski, M. and Rzadca, K.(eds.), Lecture Notes
in Computer Science, Vol. 12247, Springer, 2020,
pp. 477–492.
[ 9 ] Blackburn, S. M., Garner, R., Hoﬀman, C.,
Khan, A. M., McKinley, K. S., Bentzur, R., Diwan, A., Feinberg, D., Frampton, D., Guyer, S. Z.,
Hirzel, M., Hosking, A., Jump, M., Lee, H., Moss, J.
E. B., Phansalkar, A., Stefanović, D., VanDrunen,T., von Dincklage, D., and Wiedermann, B.: The
DaCapo Benchmarks: Java Benchmarking Development and Analysis, OOPSLA ’06: Proceedingsof the 21st annual ACM SIGPLAN conference on
Object-Oriented Programing, Systems, Languages,
and Applications, New York, NY, USA, ACM Press,
October 2006, pp. 169–190.
[10] Boehm, H. and Chakrabarti, D. R.: Persistence
programming models for non-volatile memory, Proceedings of the 2016 ACM SIGPLAN International

Symposium on Memory Management, Santa Barbara, CA, USA, June 14 - 14, 2016, Flood, C. H.
and Zhang, E. Z.(eds.), ACM, 2016, pp. 55–67.
[11] Castro, D., Romano, P., and Barreto, J. P.:
Hardware Transactional Memory Meets Memory
Persistency, 2018 IEEE International Parallel andDistributed Processing Symposium, IPDPS 2018,
Vancouver, BC, Canada, May 21-25, 2018, IEEE
Computer Society, 2018, pp. 368–377.
[12] Chakrabarti, D. R., Boehm, H., and Bhandari,
K.: Atlas: leveraging locks for non-volatile memory
consistency, Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA
2014, part of SPLASH 2014, Portland, OR, USA,
October 20-24, 2014, Black, A. P. and Millstein,
T. D.(eds.), ACM, 2014, pp. 433–452.
[13] Coburn, J., Caulﬁeld, A. M., Akel, A., Grupp,
L. M., Gupta, R. K., Jhala, R., and Swanson, S.:
NV-Heaps: making persistent objects fast and safewith next-generation, non-volatile memories, Proceedings of the 16th International Conference on
Architectural Support for Programming Languages
and Operating Systems, ASPLOS 2011, Newport
Beach, CA, USA, March 5-11, 2011, Gupta, R. andMowry, T. C.(eds.), ACM, 2011, pp. 105–118.
[14] Dijkstra, E. W., Lamport, L., Martin, A. J.,
Scholten, C. S., and Steﬀens, E. F. M.: On-the-Fly
Garbage Collection: An Exercise in Cooperation,
Commun. ACM, Vol. 21, No. 11(1978), pp. 966–975.
[15] Friedman, M., Petrank, E., and Ramalhete, P.:
Mirror: making lock-free data structures persistent,
PLDI ’21: 42nd ACM SIGPLAN International
Conference on Programming Language Design and
Implementation, Virtual Event, Canada, June 2025, 20211, Freund, S. N. and Yahav, E.(eds.), ACM,
2021, pp. 1218–1232.
[16] Genç, K., Bond, M. D., and Xu, G. H.: Crafty:
eﬃcient, HTM-compatible persistent transactions,
Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2020, London,
UK, June 15-20, 2020, Donaldson, A. F. and Torlak, E.(eds.), ACM, 2020, pp. 59–74.
[17] Hudson, R. L. and Moss, J. E. B.: Sapphire:copying garbage collection without stopping theworld, Concurr. Comput. Pract. Exp., Vol. 15,
No. 3-5(2003), pp. 223–261.
[18] Intel: Intel 64 and IA-32 Architectures Software
Developer’s Manual - Volume 2 (2A, 2B, 2C, &2D): Instruction Set Reference, A–Z, 2021.
[19] Kokolis, A., Shull, T., Huang, J., and Torrellas, J.: P-INSPECT: Architectural Support for Programmable Non-Volatile Memory Frameworks, 53rd
Annual IEEE/ACM International Symposium on
Microarchitecture, MICRO 2020, Athens, Greece,
October 17-21, 2020, IEEE, 2020, pp. 509–524.

[20] Kotselidis, C., Clarkson, J., Rodchenko, A., Nisbet, A., Mawer, J., and Luján, M.: Heterogeneous
Managed Runtime Systems: A Computer Vision
Case Study, Proceedings of the 13th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, VEE 2017, Xi’an,
China, April 8-9, 2017, ACM, 2017, pp. 74–82.
[21] Nettles, S. and Jr., J. W. O.: Real-Time Replication Garbage Collection, Proceedings of the ACM
SIGPLAN’93 Conference on Programming Language Design and Implementation (PLDI), Albuquerque, New Mexico, USA, June 23-25, 1993,
Cartwright, R.(ed.), ACM, 1993, pp. 217–226.
[22] Rudoﬀ, A.: Persistent Memory Programming,
login Usenix Mag., Vol. 42, No. 2(2017).
[23] Shull, T., Huang, J., and Torrellas, J.: Deﬁning a high-level programming model for emerging
NVRAM technologies, Proceedings of the 15th International Conference on Managed Languages &Runtimes, ManLang 2018, Linz, Austria, September 12-14, 2018, Tilevich, E. and Mössenböck,
H.(eds.), ACM, 2018, pp. 11:1–11:7.
[24] Shull, T., Huang, J., and Torrellas, J.: AutoPersist: an easy-to-use Java NVM framework basedon reachability, Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019, Phoenix,
AZ, USA, June 22-26, 2019, McKinley, K. S. andFisher, K.(eds.), ACM, 2019, pp. 316–332.
[25] Shull, T., Huang, J., and Torrellas, J.:
QuickCheck: using speculation to reduce the overhead of checks in NVM frameworks, Proceedings ofthe 15th ACM SIGPLAN/SIGOPS International
Conference on Virtual Execution Environments,
VEE 2019, Providence, RI, USA, April 14, 2019,
Sartor, J. B., Naik, M., and Rossbach, C.(eds.),
ACM, 2019, pp. 137–151.
[26] Ugawa, T., Iwasaki, H., and Yuasa, T.: Improved replication-based incremental garbage collection for embedded systems, Proceedings of the
9th International Symposium on Memory Management, ISMM 2010, Toronto, Ontario, Canada,
June 5-6, 2010, Vitek, J. and Lea, D.(eds.), ACM,
2010, pp. 73–82.
[27] Ugawa, T. and Jones, R.: Model Checking

Transactional Sapphire, March 2018.
https://kar.kent.ac.uk/67197/.
[28] Ugawa, T., Ritson, C. G., and Jones,
R. E.: Transactional Sapphire: Lessons in HighPerformance, On-the-ﬂy Garbage Collection, ACM
Trans. Program. Lang. Syst., Vol. 40, No. 4(2018),
pp. 15:1–15:56.
[29] Volos, H., Tack, A. J., and Swift, M. M.:
Mnemosyne: lightweight persistent memory, Proceedings of the 16th International Conference on
Architectural Support for Programming Languages
and Operating Systems, ASPLOS 2011, Newport
Beach, CA, USA, March 5-11, 2011, Gupta, R. andMowry, T. C.(eds.), ACM, 2011, pp. 91–104.
[30] Wang, C., Cao, T., Zigman, J., Lv, F., Zhang,Y., and Feng, X.: Eﬃcient Management for Hybrid Memory in Managed Language Runtime, Network and Parallel Computing - 13th IFIP WG
10.3 International Conference, NPC 2016, Xi’an,
China, October 28-29, 2016, Proceedings, Gao,
G. R., Qian, D., Gao, X., Chapman, B. M., andChen, W.(eds.), Lecture Notes in Computer Science, Vol. 9966, 2016, pp. 29–42.
[31] Wu, M., Chen, H., Zhu, H., Zang, B., and Guan,
H.: GCPersist: an eﬃcient GC-assisted lazy persistency framework for resilient Java applications on
NVM, VEE ’20: 16th ACM SIGPLAN/SIGOPS
International Conference on Virtual Execution Environments, virtual event [Lausanne, Switzerland],March 17, 2020, Nagarakatte, S., Baumann, A., andKasikci, B.(eds.), ACM, 2020, pp. 1–14.
[32] Wu, M., Zhao, Z., Li, H., Li, H., Chen, H.,
Zang, B., and Guan, H.: Espresso: Brewing JavaFor More Non-Volatility with Non-volatile Memory, Proceedings of the Twenty-Third International
Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS
2018, Williamsburg, VA, USA, March 24-28, 2018,
Shen, X., Tuck, J., Bianchini, R., and Sarkar,
V.(eds.), ACM, 2018, pp. 70–83.
[33] 松本康太郎, 高田喜朗, 鵜川始陽: 不揮発性メモリを用いた Java オブジェクト永続化のオーバヘッドの調査, コンピュータ ソフトウェア, Vol. 38, No. 2(2021),
pp. 2 14–2 19.