後追いBz木の実装に関する助言のお願い

[shu-nkym]

後追いBz木に関して，自分なりに実装してみましたが上手くいかない状態です．既存のマルチスレッド用テストの1つを用いて動作検証しているのですが，TraceTargetNode() で存在しない Node にアクセスして Segmentation fault が起きてしまったり，どこかで無限ループに陥り MwCAS() が失敗し続けるといった状況です．何か気づく点があれば教えていただけると助かります．

アイデアは杉浦先生にアドバイス頂いた通りで，下記のようなイメージです． 1.対象ノードがフリーズされていても SMO を開始 2.MwCAS実行前に，まだ対象ノードが存在しているか TraceTargetNode()で確認 3.存在していなければ操作を終了，書込み操作に戻る 4.存在しているならMwCASを実行 5.確認後に他スレッドにより SMO が行われていた場合は old_node が異なり MwCAS が失敗．でなければ MwCAS が成功し操作が完了．

[baycedar]

中山君の方でいくらか作業が進められそうなので，一旦割当を外しておきます．

なお，PRについては自分はreviewerの方に設定してください．Assigneeは省略することも多いですが，割り当てるとしたら中山君自身ですね．

[shu-nkym]

1点相談させて頂きたいです． SMOの対象ノードがマージの右ノード対象だった際に，先にそのマージを後追いする処理がうまくいっていなかったようで現在修正中です． 成功するはずのInsertが失敗するなど，明らかに左ノードのマージの後追い処理がうまく行っていない印象を受けています． bztree.hppの751--787行目における，マージ対象の右ノードまでのtraceを受け取り，左ノードのマージを後追いする関数FollowLeftNodeMerge()に関して，何か気づく点などございましたらご指摘いただけると助かります． お忙しいところ恐縮ですが，よろしくお願いします．

[baycedar]

まず原因の切り分けのために状況の確認をさせてもらえますか？コードをざっと見た感じ，中間ノードでの後追い処理は一切行わず，葉ノードでだけ後追い処理を実行している感じだと思います．で，後追い処理の対象になるのはconsolidate/split/mergeの3種だと思いますが，このうちconsolidate/splitは葉ノードのみなら後追い処理が上手くいっていて，そこにmergeの後追い処理も追加しようとするとバグが発生するという状況でしょうか？

[shu-nkym]

説明が不足してしまい申し訳ありません． 指摘していただいた通りです． 現状，以下の通りとなります． ・中間ノードの後追いは行っていない． ・consolidate/splitは葉ノードのみなら後追い処理を有効にしてもテストは通る． ・マージの後追いの前に，SMO対象ノードがマージの右ノードだった場合における，左ノードのマージの後追いの実装を試みているが上手くいかない．

[baycedar]

了解です．ちなみに，consolidate/splitのテストは全ての型で通っていますか？たまに8byte長のキーバリューなら通るけど他の型だと通らないパターンもあるので，念のため．

[shu-nkym]

いくつか型についてはテストが通ることは確認していましたが，全てではありません． 今から確認させて頂きます．

[shu-nkym]

左マージの後追いを有効にした場合は，キーやノードサイズによって，FollowLeftNodeMerge()が呼ばれるときだけ通らず，それ以外は通ります．

[shu-nkym]

consolidate/splitの後追いのみの場合では，全ての型でテストが通ることが確認できました．