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

プログラムを停止させない定期的な不揮発性メモリへのチェックポインティング
中田 昌輝

鵜川 始陽

佐藤 重幸

高い応答性が求められるサーバーアプリケーションでは，インメモリデータベースが広く利用されている．しかしイ
ンメモリデータベースは電源断が起きるとデータを消失してしまう．その解決策として不揮発性メモリへの定期的なチェックポインティングが有望である．既存研究の CpNvm は読み込みが多いワークロードにおいて高い性能を示す
反面，チェックポインティングの際にユーザプログラムを停止させるため，応答性を低下させてしまう．そこで本研
究は CpNvm に対し double buﬀering と Copy-on-Write を組み合わせ，チェックポインティングをユーザプログ
ラムと並行に実行する手法を提案する．提案手法がユーザプログラムの高い応答性を維持させることと，読み込みが多いワークロードで性能が良いことを確認した．

の不可分性（failure atomicity）を保証する永続化が

1 はじめに必要になる．

高い応答性を求められるサーバーアプリケーション

この永続化をデータ構造に対して効率的に実現すは，インメモリデータベースが広く利用されている．

るには，buﬀered durable linearizability [12] に基づ

インメモリデータベースは，全てのデータをメモリ

くアプローチが有望であることが知られている．これ（DRAM）上で管理するために，実行効率が良く，高は，トランザクションにおけるデータ構造への書き込

い応答性を維持できる．その反面，持続性のあるスト

みをロギングして，適当な時間間隔（エポック）で，レージ（SSD や HDD）にデータを置かないために，その書き込みログの内容を NVM 上のデータ構造に

電源断などの故障に対して脆弱である．

反映するものである．故障時に直近のエポックにおけ

そこで有望なのは，持続性を持ちながら，メモリとる書き込みが犠牲になる代わりに，NVM への書き込

して扱える不揮発性メモリ（NVM）である．NVM

みの反映をアプリケーションと独立に処理できるようは，DRAM に比べてやや低速ではあるが，大容量でになり，永続化の処理全体が効率化される．

あり，ストレージの代替利用が可能である．メモリ

この buﬀered durable linearizability に基づく永続上のデータ構造を，適切に NVM 上に配置して管理化について，既存の実装方針は，大きく二つに分けすれば，アプリケーションの耐故障性と実行効率をられる．一つは，データ構造全体と書き込みログを両立できる見込みがある．しかし，単に更新データ

NVM に配置するもの（Montage [18] [6] 方式と呼ぶ）．

を NVM へ書き出すだけでは，故障からの回復時に，

もう一つは，データ構造の最新版を DRAM に，永データ不整合が生じてしまう．意味的に不可分な一連続版を NVM に配置し，DRAM への書き込みログをのメモリ操作（トランザクション）に対して，故障時

NVM に配置するもの（CpNvm [2] [3] 方式と呼ぶ）．

∗

Periodic Checkpointing to Non-Volatile Memory
without suspending the programThis is an unrefereed paper. Copyrights belong to
the Authors.
Masaki Nakata, Tomoharu Ugawa, and Shigeyuki
Sato, 東京大学, The University of Tokyo.

両者には一長一短がある．

Montage 方式では，アプリケーションの書き込み
時に，Copy-on-Write（CoW）でエポック毎に新しいオブジェクトを生成し，書き込みログに記録する．
このログの追記は，書き込みを行うスレッドを止めずに処理することが可能である．また，アプリケーショ• 高 い 実 行 効 率 と 応 答 性 を 両 立 し た ，buﬀered

ン側の並行アクセスが正しく排他制御されていればdurable linearizability に基づくデータ構造の（すなわち data-race-free ならば），書き込みログの永続化手法を開発した（4 章）．これは，Cp-

反映は，アプリケーションと競合することはない．結Nvm [2] [3] におけるアプリケーションと永続化果としてアプリケーションを停止させずに，永続化処処理が干渉する問題を，Montage [18] [6] の手法

理を並行させることができる．一方，最新版が NVM

を CpNvm に適応させることで，解消したものにあることから，読み込みは常に NVM から行うことになり，DRAM に比べて低速になる．

である．

• 提案手法を利用したアプリケーションのスルー

CpNvm 方式では，最新版が DRAM 上にあるため，

プットと応答性を実験的に評価した（5 章）．マイ

アプリケーション側の読み込みにペナルティは生じ

クロベンチマークと YCSB ベンチマークの両方

ず，通常の DRAM 上のデータ構造と同等の性能にについて，提案手法は，スループットで Montage

なる．また，アプリケーションの書き込み時は，書を上回り，応答性で CpNvm と Montage の両方き込まれたアドレスを DRAM 上に記録するだけで，を上回った．

NVM に書き込むことはないので，オーバーヘッドが小さい．一方，書き込まれたデータをログに記録する

2 Periodic Persistence

際に，エポックを跨いだ最新版を参照すると，failure

Periodic Persistence [16] とは buﬀred durable lin-

atomicity が壊れてしまう．したがって，書き込みロ

earizability [12] に基づく手法である．アプリケーショ

グを追記する際は，アプリケーションを停止させる必ンの実行をエポックに分割し，故障後はデータ構造を要が生じる．結果として，アプリケーションの応答性

直近のエポック終了時点の状態に復元する．永続化はが低下してしまう．

failure atomicity を保証するために，定期的にアプリ

そこで本研究では，実行効率と応答性の両立を目

ケーションを停止させたり，NVM へ保存するべきオ

指して，CpNvm 方式におけるアプリケーションと永ブジェクト（永続化オブジェクトと呼ぶ）の書き込み

続化処理の干渉を解消する実装手法を提案する．基はアトミック命令に限定したりする．

本的な考え方は，Montage 方式における，1) CoWDRAM 上にデータ構造を構築する際，永続化におで NVM 上にコピーを生成すること，2) 書き込みロ

いて failure atomicity を保証するために，定期的にグをエポック毎に区別して管理することを，CpNvm

チェックポインティングを行う．チェックポインティ

方式に適応させるものである．具体的には，1) につ

ングでは，エポックの切り替わりで，書き込みログ

いては，最新版が DRAM 上に置かれているべきなのを NVM 上にまとめて反映させる．このチェックポイ

で，古いオブジェクトをコピーする方針を取る．2) にンティングは buﬀered durable linearizability が満た

ついては，書き込まれたアドレスを記録する DRAM

されるように，アプリケーションを停止させて実行上のビットマップを，現在エポックと一つ前のエポッ

する．

クで区別して管理する方針を取る．これによって，ア
プリケーションが data-race-free である仮定の下で，3 CpNvm

アプリケーションを永続化処理によって止めること

3. 1 概要

なく，CpNvm 方式の高い実行効率を享受できるよう

CpNvm は DRAM 上にデータ構造を配置し，Pe-になる．そして，提案手法を利用したアプリケーショ

riodic Persistence に基づく永続化を行う C++用ランのスループットと応答性を実験的に評価した．そ

イブラリである．チェックポインティングは failureの結果，Montage を上回るスループットと，CpNvm

atomicity が満たされるように，アプリケーションをだけでなく Montage をも上回る応答性を確認した．

停止させてから行われる．読み込みの際は DRAM 上

本研究の主な貢献は次の二つである．

のデータ構造を直接参照するため，高速にアクセスする領域（DRAM ヒープと呼ぶ），書き込んだアドレ
1void insert ( K key , V val ) {2

std :: lock_guard lk ( List . lock ) ;3

ListNode * new_node = PNEW ( ListNode , key , val ) ;4mark ( tail , sizeof ( ListNode ) ) ;5

List - > tail - > next = new_node ;6

List - > tail = new_node ;7checkpoint () ;8}スを記録するビットマップとアドレスリストがある．

NVM 上にはチェックポインティングの際に作成する
redo ログ，DRAM ヒープの複製である NVM ヒープがある．ビットマップとアドレスリストが記録するアドレスは DRAM ヒープを 64byte 単位で区切って管理する．ビットマップはグローバルに書き込んだアド

図1

永続化リストの insert 関数コード例

レスを記録し，アドレスリストはスレッドごとに書き込んだアドレスを記録する．

ることができる．

CpNvm ではアプリケーションを実行するスレッド（ユーザスレッドと呼ぶ）と並行して永続化処理を担

3. 2 API

うスレッド（永続化スレッドと呼ぶ）が動作する．永CpNvm はあらゆるデータ構造に対応できる永続化

続化スレッドは複数存在し，それぞれ複数のユーザス

ライブラリであり，表 1 で示すような API を用いてレッドと対応付けられて動いている．

データの永続化を行う．CpNvm はリカバリーのため

2 種類のスレッドによる CpNvm の永続化処理は 3の API も存在するが，本論文ではリカバリーについ種類によって構成され，書き込みバリアとチェックポて言及しないため割愛する．

インティングがある．書き込みバリアは図 2 中の 1

O

CpNvm ではトランザクションの最後やアプリケーに示す実行処理におけるマーキングである．ユーザ

ションが停止可能なタイミングに，checkpoint() をスレッドが書き込む際は mark 関数を記述し，書き込

記述することで，定期的にチェックポインティングをみ先のアドレスを記録する．このマーキングはビット実行する．また，NVM へ保存するべきデータ構造にマップの対象のビットが立っていない場合のみである

対しては，書き込み時に mark(addr, size) と記述（図 3 の 13–15 行目）．これにより，記録するアドレ

する．CpNvm がチェックポインティングを行う際にス数を最小限に抑え，同じアドレスに対する書き込み

は，checkpoint() の位置でユーザスレッドの実行をの高速化が図れる．

止める．これらの API を用いて，永続化リストにおける insert 関数の実装例を図 1 に示す．

チェックポインティングはまず，ユーザスレッドにO

よる 2 redo ログの作成を行う．ユーザスレッドがNVM へ保存するべきオブジェクトを作成する際は，スナップショットをとるべきと判断すると，この処理必ず専用のマクロである PNEW を用いる（3 行目）．こが始まる．ここで作成する redo ログは書き込み先のの PNEW マクロを用いることで NVM 上の複製を作成

アドレスと書き込みデータの組を記録する．ユーザ

することを可能としている．また永続化オブジェクト

スレッドはグローバルに停止することが可能な状況の中身を書き換える際はその箇所に mark 関数を挿入

下（トランザクション終了時など）で定期的に redo

する（4–5 行目）．最後に，この insert 関数は一つログの作成処理を行う．この際，全てのユーザスレッの transaction なので，トランザクションの終わりにドで同期を取り，アプリケーションを停止させてからcheckpoint 関数を挿入する．

この処理が始めることで，整合性の取れた状態を得る．ビットマップやアドレスリストには直近のエポッ

3. 3 永続化の流れ

ク内で書き込まれたアドレスしか記録されていない．

CpNvm の永続化の流れを図 2 に示す．また，表 1

そのため記録されたアドレスを元に redo ログに記録の API や図 2 の処理の疑似コードを図 3 に示す．図

すべきデータを DRAM ヒープから得る．

2 に示すように CpNvm は大きく分けて四つの要素でredo ロ グ の 作 成 処 理 は ユ ー ザ ス レッド の構成されている．DRAM 上にはデータ構造を格納す

checkpoint 関数を契機に行われる．この関数内のinit(filename)

永続化処理のための初期処理

finalize()

プログラム終了時の永続化完了処理

thread init()

ユーザスレッドにおける永続化処理のための初期処理

transaction start()

トランザクション開始時処理 (CpNvm では用いない)

transaction end()

トランザクション終了時処理 (CpNvm では用いない)

mark(addr, size)

書き込みバリアcheckpoint()

チェックポイント処理 (提案手法では用いない)

PNEW(type, ...)

永続化オブジェクトの new

PDELETE(type, ptr)

永続化オブジェクトの delete
表1

永続化処理のための API: ユーザスレッド

DRAM ヒープ: 永続化スレッド

O書き込み先アドレス

ビットマップvalue

O ログの作成

1

アドレスリスト

を記録

2

O

addr

addr

value

0x19...

0x00...

0x7f...

0x10...

3 ログの情報をNVM ヒープに更新

NVM ヒープ

redo ログ
図2

CpNvm の概要図

redo ログの作成では書き込み先のアドレスは主にア

チェックポインティングの二つ目の処理は永続化ス

ドレスリストを参照して得る．アドレスリストを参

レッドによる 3 バックグラウンドで redo ログの情照することで，ビットマップ全部を走査する必要が報を NVM ヒープに更新することである．ユーザス

ない，redo ログ作成の並行実行が可能，など高速化

レッドは redo ログの作成終了後，アプリケーションに寄与する．さらに，redo ログの作成の度にビットの実行を再開する．それと同時に永続化スレッドが起マップの対象となるビットを下ろす．すると，アドレ

動し，ユーザスレッドの実行と並行して（ 1 と並行

スリストとビットマップが記録するアドレス情報は同して），redo ログの情報を NVM ヒープにデータをじため，この処理が終わるとビットマップはクリアさ更新する（図 3 の persist 関数）．

れている．したがって，ビットマップは各エポックで同一のものが用いることができる．

O

O

以上の永続化の流れで，NVM ヒープと redo ログの情報から整合性の取れるデータ構造を復元するこ1

time_t l a s t _ c h e c k p o i n t _ t i m e ;32

2bool bitmap [ HEAP_SIZE / sizeof ( CacheLine ) ];

33
34

3
4

void checkpoint () {35

struct ThreadContext {5list < intptr_t > addr_list ;6list < pair < intptr_t , CacheLine > > log ; // on NVM

if ( current_time () - l a s t _ c h e c k p o i n t _ t i m e <=INTERVAL )

7

};

8

ThreadContext ctx [ NUM_THREADS ]; // indexed by thread

36

return ;

37
ID

9
10

# define PDELETE ( type , ptr ) pdelete < type >( ptr )void mark ( intptr_t addr , size_t size ) {38

thread_barrier () ;39

auto id = my_thread_id () ;40

for ( auto addr : ctx [ id ]. addr_list ) {41

bitmap [ addr / sizeof ( CacheLine ) ] = false ;
auto value = * static_cast < CacheLine * >( addr ) ;11

auto id = my_thread_id () ;42

12

for ( int i = 0; i < size ; i += sizeof ( CacheLine ) )43

13

if (! bitmap [( addr + i ) / sizeof ( CacheLine ) ]) {

44

}

14

ctx [ id ]. addr_list . push_back ( addr + i ) ;45

ctx [ id ]. addr_list . clear () ;15

bitmap [( addr + i ) / sizeof ( CacheLine ) ] = true ;46

thread_barrier () ;47

sfence () ;

16
17

}

ctx [ id ]. log . push_back ({ addr , value }) ;

48

}

18

49

19

template < typename T , typename ... Args >50

20

T * pnew ( Args ... args ) {51

r e n e w _ l a s t _ c h e c k p o i n t _ t i m e () ;}void persist () {21

auto ptr = new T ( args ...) ;52

22

mark ( static_cast < intptr_t >( ptr ) , sizeof ( T ) ) ;53

for ( auto & [ addr , value ] : ctx [ i ]. log ) {23

return addr ;54

auto nvm_addr = translate_to _nvm ( addr ) ;for ( int i = 0; i < NUM_THREADS ; i ++) {

24

}

55

memcpy ( nvm_addr , & value , sizeof ( CacheLine ) ) ;25# define PNEW ( type , ...) pnew < type >( __VA_ARGS__ )56

clwb ( nvm_addr ) ;

26

57

27

template < typename T >5828

void pdelete ( T * ptr ) {59

29mark ( static_cast < intptr_t >( ptr ) , sizeof ( T ) ) ;60

30

delete obj ;

61

31

}
ctx [ i ]. log . clear () ;}sfence () ;
}

}

図3

CpNvm の疑似コードとが可能となる．この整合性の取れるデータ構造は行うことでクラッシュ直前のエポック終了時点の状態

直近のエポック終了時点の状態であり，復元方法は 2を復元可能である．

パターン存在する．一つ目は NVM ヒープに整合性の取れた直近のエポック終了時点の状態が保存されて

3. 4 永続化スレッドの並列化いる場合である．永続化スレッドが永続化処理待機中

永続化スレッドの persist 関数における NVM ヒー

O Oの処理中）では NVM ヒープ内に一つ前のエプへの更新処理は並列実行が可能である（図 3 の 51–

ポック終了時点のデータ構造が保存されている．

56 行目）．CpNvm が作成する redo ログには，エポッ（1,2

二つ目は NVM ヒープと redo ログに整合性の取れクの終了時点のデータのみ保存されている．そのたた状態が保存されている場合である．永続化スレッド

め，各ユーザスレッドが作成するログには順序関係

が永続化処理を行っている最中（ 3 の処理中）ではが存在しない．したがって，どの順番でログを NVM

NVM ヒープ内に二つ前のエポック終了時点のデータ

ヒープに反映させても，最終的には整合性の取れる構造に redo ログのデータが一部反映された状態が保データが NVM ヒープ上に永続化される．このため，存されている．そのため，この時点で故障が起きた際

CpNvm の著者は永続化スレッドを二つ用意して実装

は redo ログから NVM ヒープにデータの更新作業を

している．

O

3. 5 CpNvm の問題点

チェックポイント3. 1 節で述べたように failure atomicity を満たす
スレッド 1

ために，CpNvm はアプリケーションを停止させてチェックポイントを取る．この停止は図 2 における

Oの redo ログの作成が完了するまで行われる．した

GET

PUT

PUT

スレッド 2

GET

.
.
.

2

がって，書き込みの割合が大きいワークロードの場

スレッド NPUT

PUT合，redo ログの作成に時間がかかり停止時間が長くなる．しかし，インメモリデータベースでは高い応答

図4

スライディングビューに基づくスナップショット性が要求されるため，CpNvm のチェックポインティ
ングによる停止はインメモリデータベースに適さなより，図 4 の点線のような，スレッド毎にタイミングいという問題がある．

がずれたスナップショットがとられることになる．
これを実現するために，提案手法では，チェックポ

4 提案手法

インティング開始時に実行中のトランザクションの完

4. 1 方針了を待ってからスナップショットをとり始める．しか提案手法は，3. 5 節の問題を解決し，アプリケー

し，待っている間に次のエポックのトランザクション

ションを停止させないようにチェックポインティングを実行することを許すので，スナップショットをとるする手法である．そのために提案手法では CpNvm をのに必要なデータが書き換えられる可能性がある．そ次の方針で変更する．

こで，double buﬀering（4. 6 節）と CoW（4. 7 節）

1. CpNvm ではユーザスレッドが行っていた redo ロを使ってこれを防ぐ．

グの作成も永続化スレッドが実行する．

2. 二つの隣接するエポックのトランザクションが同

4. 3 Data-race-freedom の仮定

時に実行することを許すが，チェックポインティ

チェックポインティング時に実行中のトランザク

ングではエポック境界のスナップショットをとる．

ション X がアクセスする範囲に，次のエポックのト
ランザクション Y もアクセスすると，トランザクショ

4. 2 スライディングビュー

ン X 完了時のビューに新しいエポックのトランザク

トランザクションの途中のメモリ状態を永続化しション Y の結果が混ざってしまう．その結果，他のス

ないようにするために，チェックポインティングはト

レッドのビューと統合したスライディングビューに新ランザクションが実行していないときに行う必要がしいエポックの実行結果が混ざってしまい，buﬀeredある．しかし，ユーザスレッドが複数あると，どのス

durable linearizability を満たさなくなる．

レッドもトランザクションを実行していない瞬間が定期的に訪れるとは限らない．
そこで，各スレッドのトランザクション完了時の本研究では，このようなことを避けるために，ユー
ザスレッドに data-race-freedom を要求する．より精確には，次の制約を課す．

ビューを結合したスライディングビュー [4] のスナッ

同時に実行される二つのトランザクションがプショットをとる．図 4 のようにスナップショットを同じメモリアドレスをアクセスするときは，開始する時点で，いくつかのユーザスレッドがトラ

どちらのトランザクションもそのメモリアド

ンザクションを実行中である場合，それらのトラン

レスに書き込んではならない．

ザクションに影響されない部分のメモリは，スナップ
ショット開始時の状態を保存する．一方，実行中のト

4. 4 API

ランザクションによって書き込まれるメモリは，トラ

3. 2 節 で 説 明 し た 表 1 の と お り で あ り，Cp-

ンザクション完了時のメモリ状態を保存する．これにNvm は ト ラ ン ザ ク ション 終 了 時 に checkpoint()

を書き込んだのに対し，トランザクション前後で前のエポックにおける redo ログを作成中に，ビットtransaction start(), transaction end() と記述

マップを書き換える可能性がある．この問題はエポッする．図 1 では，関数の開始時と終了時にこれらのクごとにビットマップを用意することで解決する．

API を呼び出すことで実行するトランザクションの図 6 に示すように，次のエポックでのビットマップ

エポックの管理を行う．

はアドレスの記録用，一つ前のエポックでのビットマップは redo ログ作成用，とビットマップに 2 種類

4. 5 エポック番号の役割をもたせた（double buﬀering と呼ぶ）．

提案手法では，隣接する二つのエポックのトラン

永続化対象のエポックは現在実行しているエポック

ザクションが同時に実行される．そこで，トランザクの一つ前のエポックである．次のエポックでのトランションの属するエポックを区別するために，エポック

ザクションは一つ前のエポックのビットマップに書き

番号を明示的に管理する．各トランザクションにエ込むことはない．そのため，永続化対象のビットマッ

ポック番号を付与し，どのエポック内で実行している

プは一つ前のエポックで書き込まれたアドレスの情報かが分かるようになる．これらの変更を加えた提案手のみを持つ．それゆえ，一つ前のエポック終了時のス法の疑似コードを図 5 に示す．

ライディングビューを得るために必要なアドレス情報

エポック番号はグローバルなエポック番号とユーザを正確に得ることが可能となる．

スレッドが個々に保持するエポック番号の 2 種類用意

このビットマップはエポックごとに用意する必要する．ユーザスレッドが保持するエポック番号は現在

はなく，二つのビットマップで十分である．3. 3 節で実行しているトランザクションのエポック番号であ述べたようにチェックポインティング終了後はビット

る．エポック番号が 0 のときはトランザクションを

マップは全てクリアされている．そのため，次のエ

実行していないことを表す．ユーザスレッドはトラン

ポックでのビットマップは二つ前のビットマップを再ザクションを始める時にグローバルなエポック番号を利用することが可能である．したがって，エポックがスレッドのエポック番号にコピーする（図 5 の 14 行切り替わる度に二つのビットマップの役割を変えて図目）．トランザクション終了時にはスレッドのエポッ

6 の処理を行う．

ク番号を 0 に戻す（図 5 の 20 行目）．
一方で，グローバルなエポック番号の管理は永続

4. 7 Copy on Write

化スレッドが担う．永続化スレッドはチェックポイン

CpNvm では，ユーザスレッドは書き込んだアドレ

ティングを開始する際はこのエポック番号をインクリスしか記録しない．書き込んだ値は DRAM ヒープかメントする（図 5 の 42 行目）．グローバルなエポッ

ら読み出せるからである．しかし，提案手法では次のク番号をインクリメントした後も，トランザクション

エポックのトランザクションによって DRAM ヒープを実行中のスレッドのエポック番号は変わらない．永が書き換えられる可能性がある．この問題は，新しい続化スレッドは古いエポックのトランザクションの終エポックのユーザスレッドが書き込み時に redo ログ

了を待ってから（図 5 の 46–47 行目）チェックポインの作成を手伝うことで解決する．

ティングを始める．

図 7 において，CpNvm と同じ処理を行った場合，
書き込みデータにオブジェクトの参照を切り替えた後

4. 6 Double Buﬀeringに永続化処理が行われると不整合が発生する．オブ

CpNvm では，ユーザスレッドが一つのビットマッ

ジェクトが保持するポインタは書き込みデータ（灰色プのみを用いて書き込みバリアを行っていた．これの丸）を指すことになるが，書き込みデータは永続化

は次のエポックになると，一つ前のエポックにおけるされないためダングリングポインタとなる．

redo ログの作成は完了しているからである．しかし，この解決のために，永続化が完了してない場合は提案手法では次のエポックのトランザクションが一つ

上書きの前にデータの redo ログを作成 (copy) して1

unsigned long global_epoch ;37

2

time_t l a s t _ c h e c k p o i n t _ t i m e ;38

3bool bitmap [2][ HEAP_SIZE / sizeof ( CacheLine ) ];void persist () {if ( current_time () - l a s t _ c h e c k p o i n t _ t i m e <=INTERVAL )

4

39

5

struct ThreadContext {40

6unsigned long epoch ;41

7list < intptr_t > addr_list [2];42list < pair < intptr_t , CacheLine > > log ; // on NVM

8return ;global_epoch ++;43// Corresponds to checkpoint() in CpNvm

9

};

44

list < pair < intptr_t , CacheLine > > log ; // on NVM

10ThreadContext ctx [ NUM_THREADS ]; // indexed by thread45

for ( int i = 0; i < NUM_THREADS ; i ++)ID

46

wait_until ([ i ]() { return ctx [ i ]. epoch !=11
12

global_epoch - 1; }) ;47

void tran sa ct i on_ s ta rt () {for ( int i = 0; i < NUM_THREADS ; i ++) {13

auto id = my_thread_id () ;48

auto old = ( global_epoch - 1) % 2;

14ctx [ id ]. epoch = global_epoch ;49

for ( auto addr : ctx [ i ]. addr_list [ old ]) {

15

}

16
17
19
20

log . push_back ({ addr , value }) ;bitmap [ old ][ addr / sizeof ( CacheLine ) ] = false ;

auto id = my_thread_id () ;53

ctx [ id ]. epoch = 0;

54

}

55

ctx [ id ]. addr_list [ old ]. clear () ;56

for ( int i = 0; i < NUM_THREADS ; i ++)

}

21
22

auto value = * static_cast < CacheLine * >( addr ) ;51
52

void transaction_end () {

18

50

}

57

void mark ( intptr_t addr , size_t size ) {wait_until ([ i ]() { return ctx [ i ]. epoch == 0; }) ;23

auto id = my_thread_id () ;58

24

auto cur = ctx [ id ]. epoch % 2;

5925

auto old = ( ctx [ id ]. epoch - 1) % 2;

60// Corresponds to persist() in CpNvm

26

for ( int i = 0; i < size ; i += sizeof ( CacheLine ) )61

for ( auto & [ addr , value ] : log ) {27

if (! bitmap [ cur ][( addr + i ) / sizeof ( CacheLine ) ])62{

sfence () ;auto nvm_addr = tran slate_to_nvm ( addr ) ;63

memcpy ( nvm_addr , & value , sizeof ( CacheLine ) ) ;64

clwb ( nvm_addr ) ;28

if ( bitmap [ old ][( addr + i ) / sizeof ( CacheLine )
]) {

65

}

29

auto value_old = * static_cast < CacheLine * >(66

for ( int i = 0; i < NUM_THREADS ; i ++) {addr + i ) ;30

ctx [ id ]. log . push_back ({ addr + i , value_old
}) ;

31

}

32

bitmap [ cur ][( addr + i ) / sizeof ( CacheLine ) ] =ctx [ id ]. addr_list [ cur ]. push_back ( addr + i ) ;34
35

for ( auto & [ addr , value ] : ctx [ i ]. log ) {68

auto nvm_addr = translate_to _nvm ( addr ) ;69

memcpy ( nvm_addr , & value , sizeof ( CacheLine ) ) ;70

clwb ( nvm_addr ) ;

71

}

72

true ;
33

67}

ctx [ i ]. log . clear () ;

73

}

74

sfence () ;

75

}

36

76

図5

r e n e w _ l a s t _ c h e c k p o i n t _ t i m e () ;}提案手法の疑似コード

から，書き込み (write) を行う．これにより，仮に永とで判別可能である．永続化が完了していないという続化スレッドが新しい書き込みデータを参照するオ

ことは一つ前のエポックで書き込みが行われている．

ブジェクトを永続化してしまったとしても，ユーザス

そのため，一つ前のエポックのビットマップを参照しレッドが作成した redo ログには整合性の取れている

た際に，対象のビットが立っていれば永続化が完了し一つ前のエポックでのデータが記録されている．

ていないことを判定できる．

書き込み先のデータが永続化が完了しているかどう

また，現在のエポックのビットマップを参照した際

かは，一つ前のエポックのビットマップを参照するこに対象のビットが立っていれば，そのデータに対する

4. 8 NVM ヒープへの更新
次のエポックでのビットマップ

永続化スレッドが redo ログを作成する処理が終わったあと，CpNvm と同様に NVM ヒープの更新処
理を始める．ここで, CpNvm の checkpoint() の最

書き込みデータ
一つ前のエポック
でのビットマップ

後に行われるバリア同期と同様の処理が提案手法でaddrも必要になる．それはユーザスレッドがまだ redo ログを作成している可能性があるためである．したがって，NVM ヒープの更新はユーザスレッドのトラン

図6

ザクションが終了してから行われる（図 5 の 56–58

Double Buﬀering行目）．
永続化が完了していない
ユーザスレッド用のredo ログオブジェクト

addr

value

0x19...

0xff...

書き込み前にデータをredo ログに移動

4. 9 永続化スレッドの並列化
CpNvm と同様，永続化スレッドは並列化して処理を行うことができる．提案手法の persist 関数では，redo ログの作成処理および redo ログのデータを

NVM ヒープへ更新する処理が並列化できる．redo ロ
書き込みデータ

図7

Copy on Write

グの作成処理に関しては CpNvm の checkpoint 関数と同様の処理で並列化出来る．

NVM ヒープへ更新する際は 4. 8 節で述べた永続化
redo ログは必ず作成されている．そのため，CoW のスレッドとユーザスレッドが作成した redo ログの反処理を行うか判断するのは，新しいエポックにおいて

映順序に気をつけなければならない．そのため，永続初めて対象のデータにアクセスしたときだけである

化スレッドが作成した redo ログを反映したのち，永（図 5 の 27–35 行目）．

続化スレッド同士で同期を取ってからユーザスレッド

NVM ヒープを更新する際は永続化スレッドが作成が作成した redo ログの反映処理を行う．

した redo ログとユーザスレッドが作成した redo ロ

永続化スレッドは，CpNvm では 2 スレッドを用い

グに同じアドレスのデータが記録されている場合がていたが，提案手法ではユーザスレッドと同数のスある．その際はユーザスレッドが作成する redo ログ

レッドを用いる．これは redo ログ作成を，少ないスを採用する．これは 4. 7 節で述べた，永続化スレッド

レッド数で処理すると，ユーザスレッドの CoW が多が作成する redo ログは不整合なデータが記録されてく発生することを防ぐためである．

いる可能性があるからである．一方でユーザスレッドが作成する redo ログは必ず一つ前のエポックの整合

5 評価

性の取れたデータを記録する．したがって，永続化ス

本章では，既存研究と比較して実験を行い，次の 2

レッドは永続化スレッドが作成した redo ログを先に点を実験的に確認した．

NVM ヒープに反映させてから，ユーザスレッドが作

1. 4. 6, 4. 7 節で説明した double buﬀering と CoW

成した redo ログを反映させる（図 5 の 61–77 行目）．

によって，プログラムを停止させないことを実現

これにより，永続化スレッドが作成した不整合なデーできているか（5. 2 節）

タが含まれている redo ログによる更新を消すことが出来る．

2. 提案手法は実際のワークロードにおいても，CpNvm の強みである読み込み性能が維持されているか（5. 3 節）

5. 1 実験設定
実験環境は以下のとおりである．

• CPU: Intel Xeon Gold 6354(3.00GHz)– 18 コア 36 スレッド

Montage に関しては ralloc [5] を用いている．
実験で用いたベンチマークは主に二つである．一つ目は既存研究 Montage で用いられた Hashmap へのアクセスを行うベンチマークである．get, insert, re-• DRAM: DDR4 3200MHz 192GB

move をクエリとして各クエリでは Hashmap のバケッ

• NVM: Intel Optane DC Persistence Memory

トごとにロックを保持していることで data-race-free
なプログラムである．また，get, insert, remove の割

256GB• C++ コンパイラ: g++ 9.3.0

合を変えて実験することができ，それを g:i:r=0:1:1 の• OS: Ubuntu 20.04.3LTS

ように書く．Hashmap のバケットの数は 1,000,000，

CPU はハイパースレッディングをオンにしており，書き込みする値のサイズは 1KB である．また定期的

turbo boost を切って 3.00GHz に固定している．まにチェックポインティング（や永続化処理）を行う手

た NUMA による NVM へのアクセス時のオーバー法に関しては，その間隔を 100ms とした．

ヘッドを避けるために，CPU は使用する NVM に直二つ目は YCSB ベンチマーク [9] であり，mem-

接つながっているもののみを使用している．提案手法

cached [1] 上に永続化ライブラリを挿入し，100ms おはユーザスレッドと永続化スレッドが同じキャッシュ

きにチェックポインティングを行う．メモリアクセスを共有するように CPU を固定して計測を行っている．

は zipﬁan 分布に従うワークロードを使用した．

また，比較実験に用いた既存研究は以下のとおりで

5. 2 応答性ある．

• CpNvm: 3 章で説明した手法を我々が実装したどの程度停止しているかを各時間におけるクエリのものである．永続化スレッドの個数は著者らの実数を計測することで確認した．データを永続化しない装に合わせて 2 個とした．

プログラムの実行 (DRAM の実行) における平均実• Montage [18] [6]: NVM 上にコンテナデータ構

行クエリ数の 10%, 30%, 50%を最低保証性能とする．

造を構築し，コンテナとその要素を永続化する．

この最低保証性能を下回った実行クエリ数の場合，そwait free なデータ構造に対しても永続化が適用の実行は停止と判断する．また，実行時間に対する停もの  を使用した．

止時間の割合を棒グラフで表現する．さらに 1 回あ可能な手法である．実装は著者らが公開している
1

たりに停止した時間を 0.5ms 未満，1ms 未満，5ms

実験結果において，データを永続化しないプログラム

未満，10ms 未満，50ms 未満，50ms 以上で区切ってを DRAM と表記し，提案手法のライブラリを用いた

表示し，その割合によって評価を行う．

データ構造を Proposed と表記する．

ユーザスレッド数は 1, 4, 16 スレッドで行った．

メモリアロケータについて，先行研究の CpNvm [2]5. 2. 1 HashMap へのアクセスにおける応答性[3] は InCLL [8] で用いられるフリーリストによるア

まず，書き込み中心なワークロード (g:i:r=0:1:1)

は jemalloc を使用している．また提案手法のアロにおける実行で，100µs ごとに実行されたクエリ数をケータも jemalloc がベースとなっているが，CoW 時

いるかを 1, 16 スレッドの結果をそれぞれ図 8, 9 にの redo ログ作成における data-race を避けるために示す．

ロケータを用いていたが，我々の CpNvm の実装で
2

出し，どのようにチェックポインティングが行われて64byte にアライメントするように変更を加えた．そ図 8, 9 でチェックポインティングが行われた位置にの他のプログラムについては，DRAM は jemalloc,⋆ 印を示す．CpNvm と提案手法のスナップショット

1 https://github.com/urcs-sync/Montage
2 https://github.com/jemalloc/jemalloc

は定期的に取られている．CpNvm は実行したクエリ数が 0 となる時間が数ミリ秒が存在している．一方で提案手法は 1 スレッドのときに，スナップショットをる停止割合の結果を図 10，読み込み中心なワークロー
ド (g:i:r=18:1:1) における停止割合の結果を図 11 に
100

DRAM
CpN vm

スループット (ops/100µs)

90

ProposedMontage示す．書き込み中心の場合，16 スレッド実行結果を示す図 10-(c) において，最低保証性能が DRAM の性能

80
70の 50%の際，提案手法と Montage が見切れている．

60
50

提案手法では 40%近くが停止とみなされ，Montage

40
30

⋆

20

⋆

⋆

⋆

⋆

⋆

⋆

⋆

⋆

⋆

10

に読み込み中心の場合である図 11-(c) でも Montage

0
0

100

200

300

400

500

時間 (ms)⋆ : CpN vm のチェックポイント⋆ : 提案手法のチェックポイント

図8については全ての実行が停止とみなされている．同様

Hashmap へのアクセスにおける応答性（1 スが見切れており，78%が停止とみなされている．
提案手法はスレッド数が多くなると停止の割合が増える．書き込みメインのワークロードの結果を示した図 10 において，最低保証性能が DRAM の性能の 50%の場合，スレッド数が増えると CpNvm に比レッド）

べ，停止時間が増える．これはユーザスレッドの 2 倍が CPU のコア数を超えるような実験では，永続化ス
レッドに CPU をとられてユーザスレッドの速度が低
1.1

DRAM
CpN vm

スループット (ops/100µs)

1

ProposedMontage

0.9

下しているためである．

5. 2. 2 YCSB ベンチマークにおける応答性

0.8
0.7

読み書きの割合が 1 : 1 であるワークロードの YCSB-

0.6
0.5

A における応答性に関する結果を図 12 に示す．

0.4
0.3

ユーザスレッド数が 1 スレッド時の停止割合の結

0.2

⋆

0.1

⋆

⋆

⋆

⋆

⋆

⋆

⋆

⋆

果である図 12-(a) において，Montage の性能が悪い

0
0

100

200

300

400

500

時間 (ms)⋆ : CpN vm のチェックポイント⋆ : 提案手法のチェックポイント

図9

Hashmap へのアクセスにおける応答性（16 ス
レッド）

ため，最低保証性能が DRAM の性能の 50%の際は，38%停止している．
提案手法に関して，図 12-(c) に示す，16 スレッドで最大保証性能が DRAM の性能の 50%である場合，
最も停止割合が多く，その割合は 0.31%である．し取るタイミングがほとんど判別付かないほど，安定しかし CpNvm は最大の場合に 6.5%停止し，Montage

たスループットである．16 スレッドの場合，チェックは 38%停止していることを考慮すると，停止時間はポインティングによりスループットが大きく低下した

わずかであるといえる．さらに提案手法の場合は，こ状態でも，Montage のスループットと同程度である．

のときの約 67%が，0.5ms 未満の停止である．

図 9 に お い て CpNvm の ス ル ー プット が 0

CpNvm と Montage はスレッド数や最低保証性能

ops/100ms, 600ops/100ms, 800 ops/100ms の 3 段によらず，一定時間停止している．最低でも CpNvm

階存在している．それぞれ redo ログの作成フェーズ，

は 3.4%停止，Montage は 7.5%停止している．さらバックグラウンドで NVM ヒープの更新フェーズ，書にその停止は 5ms から 10ms を要するものである．

き込みバリアのみ行っているフェーズである．

Montage に関してはチェックポイントの間隔の 2倍の頻度で停止しているが，その原因は今後調査する予定である．
書き込み中心なワークロード (g:i:r=0:1:1) におけ

5. 3 スループット評価
5. 3. 1 Hashmap
Hashmap へのアクセスを行うベンチマークでは書き込みメインなワークロード（g:i:r=0:1:1) と読み込

DRAM

CpNvm

10%

DRAM

30%

50%

(a) 1 スレッド

図 12

10%

30%

(b) 4 スレッド

DRAM

50%

(b) 4 スレッド

20
20

15
15

5
5
5

0

0

0

30%

10%

30%

Montage

10%

DRAM

50%

CpNvm

0
Montage

CpNvm

Proposed

DRAM

Montage30%

Proposed0Montage

15

DRAM

15

CpNvm

20

Proposed20DRAM(b) 4 スレッド

CpNvm

10%

Proposed50%

Montage0Montage

0

CpNvm

0
DRAM

Montage

CpNvm

Proposed

DRAM

Montage

CpNvm

Proposed

DRAM

Montage

CpNvm

Proposed

DRAM

Montage

CpNvm

Proposed

DRAM

Montage

CpNvm

Proposed

DRAM

Montage

CpNvm

Proposed

停止割合 (%)

停止割合 (%)
15

Proposed10

停止割合 (%)

CpNvm
Montage

10

DRAM

Montage

CpNvm

5

Proposed

DRAM

Montage

15

CpNvm

0
Proposed

DRAM

Montage

DRAM
CpNvm

20

Proposed10

停止割合 (%)

DRAM
CpNvm

5

Proposed

20

DRAM

Montage

30%

CpNvm

5

Proposed30%

Proposed20

Montage(a) 1 スレッド

DRAM

10%

CpNvm

50%
Montage10%

Proposed10DRAM(a) 1 スレッド

CpNvm

20

Proposed10

停止割合 (%)

50%

Montage

CpNvm〜0.5ms
〜1ms
〜5ms
〜10ms
〜50ms
50ms〜

DRAM

図 11
Montage

CpNvm
Montage

10

CpNvm

5

Proposed

DRAM

Montage

DRAM

5

Proposed

停止割合 (%)

〜0.5ms
〜1ms
〜5ms
〜10ms
〜50ms
50ms〜

Proposed〜0.5ms
〜1ms
〜5ms
〜10ms
〜50ms
50ms〜

停止割合 (%)

30%

CpNvm

DRAM
CpNvm

図 10

Montage5

Proposed30%

Proposed

DRAM

Montage

10%

CpNvm

CpNvm
Montage10%

Proposed

15

Montage

DRAM

15

Proposed

停止割合 (%)
15

Proposed

停止割合 (%)
20

10

50%

(c) 16 スレッド

Hashmap へのアクセス (g:i:r=0:1:1) における停止時間の割合

10

50%

(c) 16 スレッド

Hashmap へのアクセス (g:i:r=18:1:1) における停止時間の割合

10

50%

YCSB ベンチマークへのアクセスにおける停止時間の割合(c) 16 スレッド

みメインなワークロード (g:i:r=18:1:1) の測定を行っは 16 スレッドと 36 スレッドの間を境にスループット

た．結果を図 13 に示す．

が大きく落ちている．これはユーザスレッドは 18 ス

図 13-(a) に示す書き込み中心のワークロードでは，レッドで CPU を全て使うこと，36 スレッドでハイ

CpNvm が最も良い性能であることが分かる．CpNvm

パースレッディングを活用して CPU を全て使うこと

108

スループット (ops/s)

スループット (ops/s)

108

107

106

DRAM
CpN vm

105
0

20

40

60

ProposedMontage
80

107

106

DRAM
CpN vm

105
0

20

スレッド数

60

80

スレッド数

(a) 書き込み中心なワークロード（g:i:r=0:1:1)

図 13

40

ProposedMontage(b) 読み込み中心なワークロード (g:i:r=0:1:1)

Hashmap への読み書きにおけるスループットに起因している．また 90 スレッド実行のスループッドを用いて測定を行った．測定結果を図 14 に示す．

トは 80 スレッドの際と比べてスループットが大きく

図 14-(a) に示す YCSB-A におけるスループットで落ちる原因には，スレッド同期に時間がかかってしは，CpNvm と提案手法は高いスループットである．

まっていることが挙げられる．

DRAM と比較してそれぞれ最低でも 0.94 倍，0.89

一方で提案手法は 16 スレッドと 20 スレッドの間倍のスループットであり，実際のアプリケーションでを境にややスループットが落ちる結果になっている．

も高い性能を引き出せることがいえる．Montage は

これは永続化スレッドがユーザスレッドと同じ数だけ最低の場合，0.68 倍のスループットとなってしまう．

作られており，ユーザスレッドを 16 スレッド以上使

これは Montage がたとえ一つのフィールド変数を書う場合，18 個の CPU コアを全て利用しても 1 コア

き換えても，エポックが変わってしまうとオブジェクに 2 スレッド以上割り当てられるためである．スレッ

ト全体をコピーし直す必要があるためである．

ド数が増えてもスループットがあまり落ちないのは，

図 14-(b) に示す YCSB-B におけるスループットで

CpNvm と異なりユーザスレッド同士の同期をとらなは，全体的に高い性能を示している．CpNvm ，提案

いためである．

手法，Montage それぞれ最低でも 0.85 倍，0.89 倍，

Montage については 36 スレッドと 40 スレッドの0.86 倍のスループットである．これは，どの手法も間を境にややスループットが落ちる結果になってい

読み込み時は永続化のための特別な処理を行っていな

る．提案手法は Montage よりもスループットがよく，いことから高いスループットになるといえる．

最大で 2.2 倍スループットがよい．
図 13-(b) に示す読み込み中心のワークロードでは

6 関連研究DRAM 上にデータを置く CpNvm, 提案手法が高い

NVM を用いたデータやオブジェクトの永続化に関す性能を示している．提案手法と CpNvm は DRAM とる初期の仕事では，NV-Heaps [7] や Mnemosyne [17]比べて最低でもそれぞれ 0.43 倍，0.42 倍と読み込みなどの，トランザクション単位の永続化が主流であっ性能が高いことが確認できる．提案手法は CpNvm

た．永続性トランザクションを，計算の実行・redo ロに比べ，最低でも 0.83 倍のスループットであるため，

グへの記録・NVM 上のデータの更新の 3 ステップにMontage と比較して CpNvm の強みを維持できてい分離させる DudeTM [14] の技法は，CpNvm の原型

るいえる．

となっている．

5. 3. 2 YCSB ベンチマーク

NVM 上 に 並 行 デ ー タ 構 造 と し て ，lock-free キ

読み書きの割合が 1 : 1 である YCSB-A と読み書きュー [11] や lock-free Hashmap の SOFT [21] が開発の割合が 19 : 1 である YCSB-B の二つのワークロー

されてきた．これらは個々のデータ構造を，効率的

0

5

10

15

20

25

30

35

2500
1500

DRAM
CpN vm0

ProposedMontage500

スループット (kops/s)

2500
1500

スループット (kops/s)

500
0

DRAM
CpN vm

0

5

10

15

スレッド数

20

25

30

ProposedMontage35

スレッド数(a) YCSB-A

図 14(b) YCSB-B

YCSB ベンチマークにおけるスループットに NVM 上で永続化することが主眼である．NVTra-

グを，NVM 上の同一キャッシュラインに配置する技

verse [10] はこれらを一般化し，DRAM 上で動作す法である．これにより，キャッシュラインの書き戻しるリンク構造のデータ構造の走査コードを，failure（clwb）やフェンス（sﬂush）を発行せずに，フィール

atomicity が保証されるようにように変換する．

ドの値とログの一貫性を保証できる．これらの仕事

トランザクション単位で永続化を行うコストが大きいため，それを削減する技法が研究されている．例えは，永続化の対象となるデータ構造に，ある程度仮定を置く方針を取っている．

ば，clobber logging [20] は，トランザクション単位

一方，永続化対象のデータ構造に依存しない API にで，それを再実行するのに十分な変数の値だけをログ

よって，Periodic Persistence を実現する取り組みもに記録する技法である．障害時には，ログを元に変数ある．本研究で拡張を加えた CpNvm [2] [3] に加えて，の値を復元して，トランザクション再実行することでMontage [18] [6]，PMThreads [19]，ResPCT [13] も，

データを復元する．

それに分類される．これらのうち，ユーザスレッド

永続化の単位を，個々のトランザクションではなく，を停止させずにチェックポインティングを行うのは，エポックに拡張する考えが Periodic Persistence [16]Montage だけである．PMThreads は，エポックの区である．エポック長を調整することで，故障時に失わ切りとして，ユーザスレッド間の mutex lock の利用れる更新量を増やす代わりに，永続化のオーバーヘッを仮定している．ResPCT は，InCLL に基づく API

ドを抑えることができる．Periodic Persistence に基を与えることで，効率と汎用性を両立させた．

づく Hashmap である Dalı́ [16] が，先駆的な仕事で
ある．

7 まとめ

Periodic Persistence の下で，ロギングのオーバー本研究では，読み込み性能が高い永続化手法であるヘッドを削減する手法も数多く研究されている．Asyn-

CpNvm に対して double buﬀering と CoW を導入しchronous Semantic Logging [15] は ，DRAM 上 のてプログラムを停止させない手法を提案した．本手

データ構造への高水準操作（例えば insert）とその引法は data-race-free なアプリケーションでは failure

数だけを，専用のバックグランドスレッドがログに記

atomicity を保ちながらチェックポインティング時に録する技法である．このとき，高水準操作の DRAM

停止しないことを実現する．

上での実行が，高水準操作と引数を NVM に記録する本手法を YCSB ベンチマークで測定し，停止時間

ことよりも時間が掛かるとき，ロギングのレイテンシの割合はデータを永続化しない場合と比べて，2.3 倍は隠蔽される．In-Cache-Line-Log (InCLL) [8] は，に抑えることを確認した．さらに，CpNvm の強みで更新の記録対象のオブジェクトフィールドと，そのロある読み込み性能を維持することができ，スループットは最低の場合でも 0.89 倍に抑えることができた．
提案手法ではまだリカバリーの実装が終わっていな
い．そのため，リカバリーの実装をし，リカバリーにかかる時間を既存研究と比較することが今後の課題である．
謝辞
本研究の一部は，JSPS 科研費 JP19K11904 の助成を受けたものです．また，本研究の一部は，キオク
シア株式会社の支援をうけて実施したものです．

参 考 文 献[ 1 ] : Memcached, https://memcached.org/.
[ 2 ] Aksun, D. and Larus, J.: Durability Through
NVM Checkpointing, 12th Non-Volatile Memories
Workshop (Poster), 2021.
[ 3 ] Aksun, D. T.: Software Support for NonVolatile Memory (NVM) Programming, PhD Thesis, IINFCOM, EPFL, Lausanne, 2021.
[ 4 ] Azatchi, H., Levanoni, Y., Paz, H., and Petrank, E.: An On-the-Fly Mark and Sweep Garbage
Collector Based on Sliding Views, Proceedingsof the 18th Annual ACM SIGPLAN Conference
on Object-Oriented Programing, Systems, Languages, and Applications, OOPSLA ’03, ACM,
2003, pp. 269–281.
[ 5 ] Cai, W., Wen, H., Beadle, H. A., Kjellqvist,
C., Hedayati, M., and Scott, M. L.: Understanding and Optimizing Persistent Memory Allocation,
Proceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management, ISMM
’20, ACM, 2020, pp. 60–73.
[ 6 ] Cai, W., Wen, H., Maksimovski, V., Du, M.,
Sanna, R., Abdallah, S., and Scott, M. L.: Fast
Nonblocking Persistence for Concurrent Data Structures, 35th International Symposium on Distributed
Computing (DISC 2021), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 209, Schloss
Dagstuhl – Leibniz-Zentrum für Informatik, 2021,
pp. 14:1–14:20.
[ 7 ] Coburn, J., Caulﬁeld, A. M., Akel, A., Grupp,
L. M., Gupta, R. K., Jhala, R., and Swanson,
S.: NV-Heaps: Making Persistent Objects Fastand Safe with next-Generation, Non-Volatile Memories, Proceedings of the Sixteenth International
Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS
XVI, ACM, 2011, pp. 105–118.
[ 8 ] Cohen, N., Aksun, D. T., Avni, H., and Larus,
J. R.: Fine-Grain Checkpointing with In-CacheLine Logging, Proceedings of the Twenty-Fourth International Conference on Architectural Support for
Programming Languages and Operating Systems,
ASPLOS ’19, ACM, 2019, pp. 441–454.

[ 9 ] Cooper, B. F., Silberstein, A., Tam, E., Ramakrishnan, R., and Sears, R.: Benchmarking Cloud
Serving Systems with YCSB, Proceedings of the 1st
ACM Symposium on Cloud Computing, SoCC ’10,
ACM, 2010, pp. 143–154.
[10] Friedman, M., Ben-David, N., Wei, Y., Blelloch,
G. E., and Petrank, E.: NVTraverse: In NVRAM
Data Structures, the Destination is More Important than the Journey, Proceedings of the 41st ACM
SIGPLAN Conference on Programming Language
Design and Implementation, PLDI ’20, ACM, 2020,
pp. 377–392.
[11] Friedman, M., Herlihy, M., Marathe, V., andPetrank, E.: A Persistent Lock-Free Queue for
Non-Volatile Memory, Proceedings of the 23rd ACM
SIGPLAN Symposium on Principles and Practiceof Parallel Programming, ACM, 2018, pp. 28–40.
[12] Izraelevitz, J., Mendes, H., and Scott, M.: Linearizability of Persistent Memory Objects Undera Full-System-Crash Failure Model., Distributed
Computing, 30th International Symposium, DISC
2016, Lecture Notes in Computer Science, Vol. 9888,
Springer, 2016, pp. 313–327.
[13] Khorguani, A., Ropars, T., and De Palma, N.:
ResPCT: Fast Checkpointing in Non-Volatile Memory for Multi-Threaded Applications, Proceedings of
the Seventeenth European Conference on Computer
Systems, EuroSys ’22, ACM, 2022, pp. 525–540.
[14] Liu, M., Zhang, M., Chen, K., Qian, X., Wu,
Y., Zheng, W., and Ren, J.: DudeTM: Building
Durable Transactions with Decoupling for Persistent Memory, Proceedings of the Twenty-Second International Conference on Architectural Support for
Programming Languages and Operating Systems,
ASPLOS ’17, ACM, 2017, pp. 329–343.
[15] Memaripour, A., Izraelevitz, J., and Swanson,
S.: Pronto: Easy and Fast Persistence for Volatile
Data Structures, Proceedings of the Twenty-Fifth
International Conference on Architectural Support
for Programming Languages and Operating Systems, ASPLOS ’20, ACM, 2020, pp. 789–806.
[16] Nawab, F., Izraelevitz, J., Kelly, T., III, C.
B. M., Chakrabarti, D. R., and Scott, M. L.: Dalı́:
A Periodically Persistent Hash Map, Proceedings ofthe 31st International Symposium on Distributed
Computing (DISC 2017), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 91, Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017,
pp. 37:1–37:16.
[17] Volos, H., Tack, A. J., and Swift, M. M.:
Mnemosyne: Lightweight Persistent Memory, Proceedings of the Sixteenth International Conference on Architectural Support for Programming
Languages and Operating Systems, ASPLOS XVI,ACM, 2011, pp. 91–104.
[18] Wen, H., Cai, W., Du, M., Jenkins, L., Valpey,
B., and Scott, M. L.: A Fast, General System forBuﬀered Persistent Data Structures, Proceedings ofthe 50th International Conference on Parallel Processing, ICPP ’21, ACM, 2021, pp. 73:1–73:11.
[19] Wu, Z., Lu, K., Nisbet, A., Zhang, W.,
and Luján, M.: PMThreads: Persistent Memory
Threads Harnessing Versioned Shadow Copies, Proceedings of the 41st ACM SIGPLAN Conference
on Programming Language Design and Implementation, PLDI ’20, ACM, 2020, pp. 623–637.
[20] Xu, Y., Izraelevitz, J., and Swanson, S.:

Clobber-NVM: Log Less, Re-Execute More, Proceedings of the 26th ACM International Conferenceon Architectural Support for Programming Languages and Operating Systems, ASPLOS ’21, ACM,
2021, pp. 346–359.
[21] Zuriel, Y., Friedman, M., Sheﬃ, G., Cohen, N.,
and Petrank, E.: Eﬃcient Lock-Free Durable Sets,
Proc. ACM Program. Lang., No. OOPSLA(2019),
pp. 128:1–128:26.