# Endurable Transient Inconsistency in Byte-Addressable Persistent B+Tree
https://www.usenix.org/node/210511
https://github.com/DICL/FAST_FAIR
Failure-Atomic ShifT(FAST) と Failure-Atomic In-place Rebalance (FAIR)でB+Treeを実装
* FAST：ノード無いのEndurableなIn place update
* FAIR：ノード分割が起きた時の話（こっちはまだちゃんと読めていないが、肝は多分FAST）
## Failure-Atomic ShifT(FAST)
### 不揮発メモリでB+treeのIn place update(※)を行う際に問題となること
1. メモリアクセスのリオーダリング
* load, store命令はreorderingされる
* 別スレッドから見たときにpartially updateな状態に見えてしまう
2. Cache line flush(永続化領域への書き出し)のタイミング
* 永続化順序がめちゃくちゃで電源断からのrecoveryなんてあったもんじゃない
3. 更新途中に電源落ちた後のrecovery
(※)apeend onlyの実装もあるが論文中ではread performanceが悪くなることを懸念して,In place updateにfocus
1.はmfench、2.はclflush(clwb)を逐一行うことで解決可能だが、そんなことをしているとNVDIMMの性能を全く生かすことが出来ない。1.,2.はしょうがないとして、3.のためにloggingなんてするのか？となる。
### FASTは以下のように上記課題を解決
* 多くのアーキテクチャに共通するreorder性質を使ってmfence削減
* 依存関係のあるload, storeはreorderされない。
* x86ではstore, storeはreorderされない。これをTotally Store Ordering(TSO)という
（Non-TSOの場合も書いてあるがmfenceがふえてるだけっぽい。ちなみにARMはNon-TSOを許してる）
⇒ 依存関係のあるload, storeとstore, storeを使って更新を行えばreorderingが防げる。
* 更新サイズがCache line sizeになったときに、mfence、clflushでclflush数削減
* storeとclflushはreorderされるのでmfenceが必要
* ptrが一意である前提を置き、更新過程でleaf nodeに同じptrが2つ存在する状態を作り、障害検出可能にする。
* ptrはメモリアドレスなどが一般的なのでこの前提はreasonable
* 詳しくは例で説明（回復までは整理できていない）
例を見てみる。
```
Lead nodeはkeyとptrの配列でできてると仮定
key, ptrともに8 byte, cache line size 64 byteとすると、
ちょうど以下の配列は1 cache lineにのる。
+-----------------------------------------------+
| | | | | | | | |
| key | ptr | key | ptr | key | ptr | key | ptr |
+-----------------------------------------------+
Insert (2, 0x2)を下のノードにすると、
+-----------------------------------------------+
| | | | | | | | |
| 1 | 0x01| 3 | 0x03| 0 | 0 | 0 | 0 |
+-----------------------------------------------+
+
|
v
こうなる
+-----------------------------------------------+
| | | | | | | | |
| 1 | 0x01| 2 | 0x02| 3 | 0x03| 0 | 0 |
+-----------------------------------------------+
leaf[0] [1] [2] [3] [4] [5] [6] [7]
```
この時(3, 0x3)を右にずらして(2, 0x2)を挿入するが、
その時の命令列は、以下の通り(operand順番はintel記法)。
```
# ノードのロック（githubのコードにはこれがないかも、、、）
# 更新系のみ排他する、これ自体はよくあるOptimisitc Lock Coupling.
i0: node.acquire_lock
# 0x3のシフト
i1: load r0, leaf[3]
i2: store leaf[5], r0
# 3のシフト
i3: load r1, leaf[2]
i4: store leaf[4], r1
※ TSO architectureではi2とi4はreorderされないので確実にptrのupdateが先に全コアに見える。
# あえて0x01をleaf[3]に置くことでduplicate ptr状態を作り、
# fault detectionを検出可能にする。
i5: load r2, leaf[1]
i6: store leaf[3], r2
# (2, 0x2)のinsert
i7: store leaf[2], 2 # 先にkeyを更新.まだduplicate ptrなので落ちても検出可能
i8: store leaf[3], 0x2 # ここでptrが変わり更新完了になる
i9: mfence
i10: clflush
i11: node.release_lock
```
各ポイントで障害が起きた時の検出方法はsearch中に前後のptrを比較し、同じ値があればupdate中に落ちたことがわかる。
ここではstore後すぐにメモリに書き込まれる前提で書く。
（update中のsearchでも同じことが起きるので結果の整合性は合わせて対処しているはず）
1. i1後: 更新全くなしなので問題にならない
2. i2後: leaf[5]とleaf[3]が0x3で同じなので、update中に落ちたことがわかる
3. i3後: 2と同じ
4. i4後: 2と同じ
5. i5後: 2と同じ
6. i6後: leaf[3]とleaf[1]が0x1で同じなので、update中に落ちたことがわかる
7. i7後: 6と同じ
8. i8後: ここで更新は完了
### Keyを8byte以上にするには、、、？
仮にkeyが24byte, ptrが8byteだとすると以下のようになるが、
ptrがatomicに更新できる限り、単にload, storeが増えるだけ。
```
下のleaf nodeは2 cache lineに跨る。
+-----------------------------------------------+
| | | | | | | | |
| 1 | 0x01| 3 | 0x03| 0 | 0 | 0 | 0 |
+-----------------------------------------------+
leaf[0][1][2][3][4][5][6][7][8][9][10][11]...
(2, 0x2)をノードに追加するときの命令列は
i0: node.acquire_lock
# 0x3のシフト
i1: load r0, leaf[7]
i2: store leaf[11], r0
・見にくいがkey 24byte, ptr 8byteなのでleaf[7]がptr(0x3)で、leaf[11]が移動先になる
・ここでptr
# 3のシフト
i3: load r1, leaf[6]
i4: store leaf[10], r1
i5: load r2, leaf[5]
i6: store leaf[9], r1
i7: load r3, leaf[4]
i8: store leaf[8], r1
i9: mfence
i10: clflush
※ 以降の更新は別キャッシュラインに対して行われるのでflushが必要
```
もっときれいな図（論文から引用）
Sign in with Wallet
Connect another wallet