Efficient lock-free durable sets – the morning paperを読んだメモ

メモリが不揮発性でも、キャッシュとレジスタが揮発性のままな場合がある。

キャッシュに存在するがメモリに書き込めなかったときに一貫性が崩れる。

本論文では、log-freeなデータ構造を検討する。

データプレーン: key-valueペアを格納するノード

コントロールプレーン: ノードに接続し、集合に対する操作をサポートする構造

データプレーンで永続的に格納、コントロールプレーンで一時的に保持。

クラッシュ後にコントロールプレーンの構造を回復する方法も必要。

回復時間と操作の高速化がトレードオフ。

高レイヤーから見ると、「データは永続的だが、ポインタは永続的ではない」

link-free sets

各ノードに2つのvalidity bitsを追加

リストに挿入されているノードを「invalid」としてマーク

論理削除マーカー

validかつ削除されていないノードが集合で考慮される。

containsを実行するときは、insertを保留にしているノードを永続的（valid）にする

→返り値が常にNVRAM viewの状態に一致する。

insert

1. 新しいノードはinvalidで初期化される

2. key-valueが新しいノードに書き込まれる

3. ノードがlinked-listに挿入され、validにbit反転

4. psyncでノードを永続的にする

クラッシュ後の回復

validityスキームでノードがリンクされていたかどうかを調べる

SOFT

更新系の操作をintentionとcompletionに分けて、psyncの回数を減らす

集合のエントリは、揮発性ノードと永続ノード（Pノード）で表現

揮発性ノード

Pノードへのポインタを持つ

Pノード

永続領域に格納

validity用の3ビット使用する

log-freeアルゴリズムを拡張

ノードの4状態

Inserted

Deleted

Intention to insert

挿入されるが、PノードがNVRAMにあることは保証されない

Inserted with intention to delete

削除されるが、削除状態がNVRAMにあることは保証されない

クラッシュ後の回復

クラッシュするとintent状態だったものは失われる

回復は、Pノードのbit情報のみに基づく

validStartとvalidEndの値が同じ、かつ、deletedが異なる場合はPノードはvalid

https://gyazo.com/6a9546a6b4676493b494808976f9d7d4

References