競合する並行なscan, upsert txで、並置にならないはずのシナリオが並置になる（non serializable)

[thawk105]

起票のきっかけ：
tsurugi-issue への取り組みの仮定で下記のような問題を観測した。

https://github.com/project-tsurugi/tsurugi-issues/issues/665#issuecomment-2005786859

調査実態：
再現性は高い。
ステップ実行で再現できるバグではなく、現状並行系テストプログラムでしか起こせないため、デバッグログの分析が難しい。
通過するパスに多くのデバッグログを仕込んだだけでは、現状原因の理解に至れなかった。
本件に関連する情報量が増えたり、並行でないテストプログラムでの再現シナリオが作成できたときにデバッグに取り組む予定である。

[ban-nobuhiro]

現状確認

TEST_P(tsurugi_issue665_test, simple) に渡す系列とテスト結果

• 起票時
  • true → success
  • false → fail
  • false, false → fail
  • true, false → fail
  • false, true → fail
  • true, true → success
• c72f2e9
  • true → success
  • false → success
  • false, false → success
  • true, false → success
  • false, true → success
  • true, true → success

c72f2e9 で修正されたように見える

[ban-nobuhiro]

しかし、私の手元の非力マシン 2C4T CPU では一部テストが通らない
true, false → fail

[ban-nobuhiro]

問題となっているときには、UPSERT が INSERT でなく UPDATE になっていた。

私の理解:
このテストコードの処理(full-scan count によって書く先が決まり、それは scan で見つけたどれとも重ならない位置になる)では、
(full-scan, 1 record upsert) → (full-scan, 1 record upsert) の順にシリアライズされると、
必ず後ろ側の full-scan で前のものより 1 レコード多く読めるのだから、後ろの upsert によって同じ位置に書かれるはずはない。
commit 時 verify で read scan した対象が変更されていることで気づいて ERR_CC となる はず/べき?

[ban-nobuhiro]

OCC の range scan で range read をどのように管理しているのか?

open_scan のコードを見ると、l_key を yakushima scan に渡すのに使っているだけで、どこかに覚えこんでいるように見えない
(LTX のコードでは range_read_set_for_ltx に追加したり long_tx::update_local_read_range に渡したりしている)

[thawk105]

commit 時 verify で read scan した対象が変更されていることで気づいて ERR_CC となる はず/べき?

こちら、仰る通りだと思います。

OCC の range scan で range read をどのように管理しているのか?
open_scan のコードを見ると、l_key を yakushima scan に渡すのに使っているだけで、どこかに覚えこんでいるように見えない
(LTX のコードでは range_read_set_for_ltx に追加したり long_tx::update_local_read_range に渡したりしている)

OCC の range scan では、エントリを読んだ場所の yakushima border node の version timestamp を控えています。コミット時にそのタイムスタンプの差分比較で phantom 問題（挿入を見落とした問題）を避けます。覚えることはそれだけであり、キー範囲を覚えたりはしていません。LTX 向けに範囲読み込みがあったよっていう情報はテーブルレベルに最大エポック情報一つだけです。

LTX は書いた範囲と読んだ範囲を突合処理していたり、LTX x LTX phantom 問題の検知に書き込み範囲を扱うため、手元に記録されています。

[thawk105]

こちら、仰る通りだと思います。

それでしたら、テストコードの誤りである確率が高いでしょうか。。。？

[ban-nobuhiro]

テストコードは別に問題ないと思います。
(問題調査用には味気ないので、いろいろ別情報も取れるように追加調整して使っていますが)

OCC の range scan では、エントリを読んだ場所の yakushima border node の version timestamp を控えています。コミット時にそのタイムスタンプの差分比較で phantom 問題（挿入を見落とした問題）を避けます。覚えることはそれだけであり、キー範囲を覚えたりはしていません。

すると yakushima 情報の更新チェックのみで検出できるはず、という前提なのですね。

今疑っているのは、以下のようになってしまうのではないかということです

1. 前提: 100 node が storage に存在する
2. txA: full scan (100 node 見つかる, 100 node が通常の生きた Record を指す)
3. txA: (左端でも右端でもない)途中の位置に upsert で inserting Record を新規作成
4. txB: full scan (101 node 見つかる, 100 node が通常の生きた Record, 1 node が txA が作った inserting record を指す)
5. txA: commit → OK
   • full scan の範囲内で yakushima node および shirakami Record を変更したのは自分だけ
   • expose: inserting Record を普通の Record にする
6. txB: txA と同じ 位置に upsert
7. txB: commit → OK
   • full scan の範囲内で、 yakushima node に変更なし
   • expose: txA が書いた Record を上書き、あるいは epoch 的に負けたとみなして R上書きせず何もしない

あるいはこれの 5. 6. が逆順のもの

[ban-nobuhiro]

今疑っているのは、以下のようになってしまうのではないかということです

shirakami scan loop が通過したレコードは session . read_set_for_stx に記録され、記録されたものは commit 時の read verify で shirakami Record の変化を検査されるので、そこまで単純ではない。
ただ、 scan loop 時において next() 内で inserting record を指したとき かつ その次の read_from_scan で対象が tid lock 状態だった場合には、記録されないことがある。これが怪しい。

[ban-nobuhiro]

このパスで問題となっているようです

1. 前提: N node (0 - N-1) が storage1 に存在する
2. txA: storage1 を full scan
   • N node の通常の生きた Record (0 - N-1)
   • read_set_for_stx に 0 - N-1 を登録
3. txA: storage1, storage2 に upsert N
   • yakushima に inserting Record を新規作成
   • write set に追加
4. txA: commit (続く)
   • write set の lock 待ち
     • この例では storage2 側に upsert した Record の lock で待っていた
5. txB: full scan
   • N node が通常の生きた Record と txA が作った 1 inserting record Record
   • read_set_for_stx に 0 - N を登録
6. txB: txA と同じ 位置に upsert N
   • write set に追加
7. txB: commit
   • write set の lock 待ち
   • 先に待ち始めた txA より先に lock を取得
   • read_verify OK
     • 0 - N の shirakami Record に txB の scan loop 時から変化なし
   • node verify OK
     • yakushima に txB の yakushima::scan 時から変化なし
   • expose
     • "N": inserting->normal, unlock
8. (4の続き) txA: commit
   • lock を取得
   • read_verify OK
     • 0 - N-1 の shirakami Record に txA の scan loop 時から変化なし
     • ("N" は確認しない)
   • node verify OK
     • yakushima に txA の yakushima::scan 時から、自分で加えた以外の変化なし
   • expose
     • try update, unlock

[ban-nobuhiro]

次のシングルスレッドテストを作成しました:

• Storage に ["a", "c"] が存在する
• OCC1: full-scan してから upsert "b" to Storage
• OCC2: full-scan してから upsert "b" to Storage
• OCC2: commit
• OCC1: commit
• どちらかの commit は失敗する

[ban-nobuhiro]

このパスで問題となっているようです

この場合は txA の commit でロック取得に時間がかかっていたが、
(txA が ロック取得に時間がかかった理由はほかの多数のスレッドで取り合いになっていたからだと思われる)
別にtxA の commit は後で始めてもよかったため、シングルスレッドで再現可能でした。

この例、もしくは #141 (comment) の単純ケースでは
OCC1(txA) が upsert したあとには yakushima ノードに変更がなく、
OCC2(txB) が変更した Record は OCC1(txA) の read_set_for_stx にも入っていないので、
両者の read verify, node verify を通過してしまうということのようです。

range read のチェックを強化する必要がありそうです。

[ban-nobuhiro]

#141 (comment)

この例、もしくは #141 (comment) の単純ケースでは OCC1(txA) が upsert したあとには yakushima ノードに変更がなく、 OCC2(txB) が変更した Record は OCC1(txA) の read_set_for_stx にも入っていないので、 両者の read verify, node verify を通過してしまうということのようです。

range read のチェックを強化する必要がありそうです。

• Storage に ["a", "c"] が存在する
  • yakushima に root, border の node (以下、N) があり、そこに "a", "c" がある。 ver=2
• OCC1: full-scan
  • ("a" → N, "c" → N で N しか出てこないので) node set に <N の位置, N の値> を記憶
  • read set に "a", "c" が追加される
• OCC1: upsert "b" to Storage
  • placeholder Record{key="b"} が作成される
  • N に "b" の位置に作成された placeholder ptr が置かれる。 N の versionが +1 されて 3になる
    • N には "a", "b", "c" がある
  • node set の N を <N の位置, 新しい N の値(ver=3)> で更新
    • ver=2→ 3 で 1 しか変更されていないので更新するが、それ以上離れていたら ERR_CC
  • write set に {"b": UPSERT "bval" }
• OCC2: full-scan
  • ("a" → N, "b" → N, "c" → N で N しか出てこないので) node set に <N の位置, N の値(ver=3) > を記憶
  • read set に "a", "b", "c" が追加される
• OCC2: upsert "b" to Storage
  • write set に {"b": UPSERT "bval" }
  • node set の N を <N の位置, N の値(ver=3)> で更新
• OCC2: commit
  • read verify { "a", "b", "c" } → どれ一つ Record が変更されていないので OK
  • node verify: N が 覚えている ver=3 の N から変更されていないので OK
  • write expose: "b" の Record を normal Record にする
• OCC1: commit
  • read verify { "a", "c" } → どれ一つ Record が変更されていないので OK
  • node verify: N が 覚えている ver=3 の N から変更されていないので OK
• どちらかの commit は失敗しなければならないが、両方通る

[ban-nobuhiro]

range read のチェックを強化する必要がありそうです。

問題: 今まで読んだ範囲に自分で placeholder を置き、その placeholder を他Tx によって更新されてしまうと、node verify で検出できないし、 placeholder は read set に入っていないので read verify でも検出できない。

解決案:
今まで読んだ範囲に自分で placeholder を置いた場合には、それを read set に加えるようにする。
read verify 時に placeholder から変わっていたら PHANTOM で abort するようになる。

「今まで読んだ範囲」そのものを OCC は保存していないので、 node set で代用する。
node set は範囲の近傍も含んでしまうので、誤判定による偽陽性 PHANTOM abort は起き得る。例えば ["b":"c"] の範囲で scan した後に "a" の位置に placeholder を作ったら同じ border node に配置された場合。