project-tsurugi / yakushima Goto Github PK

Bug

空の木に対して並列でランダム書き込みを実行するとデッドロックが発生します．あるスレッドがノードのロックを専有したままになり，yakushima::node_version64::get_stable_version内のこのループから抜けられなくなるようです．

Execution Environment

• Branch or Commit: main (a3eeab)
• OS: Ubuntu 20.04
• Compiler: gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1)

To Reproduce

スレッド数2以上で，各スレッド100万レコードをランダムなキーに対して書き込むと発生します（予め各スレッドで書き込むキーをパーティションで分けておくと発生しないようです）．たまに通りますが，8スレッド程度使えばだいたい止まるようになります．

なお，index-benchmarkのtmp-yakuhsimaブランチに状況を再現するためのコードを用意しました．デフォルトで8スレッドが100万レコードずつ書き込む設定になっており，ビルド後にindex_benchを実行していただければおそらく状況を再現できます．-DCMAKE_BUILD_TYPE=Debugでビルドしても発生するため，デバッガで確認することも可能です．

Expected Behavior

ざっと関係しそうなコードを見ただけなので不確実ですが，おそらくinterface_put.hの160行目で獲得したロックの解放し忘れです．164行目および168行目でgotoする前に獲得したロックの解放が必要だと思います．試しに各gotoの前でロックを解放してみたところ112スレッドでランダム書き込みを実行しても通るようになりました．ただ，コード全体を見たわけではないため，別途確認をお願いします．

TODO: destroy 後にルートを空のボーダーノードとして残しておく。

現状: 残していないため、起動終了を跨いだ後の起動時に destroy 後のツリーが空の状態に対するスキャンが意図通りではなくなる懸念がある。

@thawk105
把握されているかもしれませんが，同様のissueが見当たらなかったため立てておきます．

発生している事象

remove命令をマルチスレッドで実行する際に，border_node.hのdelete_of関数の中で到達しないはずのコードが実行される可能性があるようです．cde60f（12/13の最後にテストが通ったコミット）では発生しなかったので，それ以降に加えたコードにバグが含まれていると思われます．

実行環境

• Commit ID: f833a80（12/14時点のmaster）
• OS: Ubuntu 20.04.5 LTS
• Compiler: g++ 9.4.0 (Ubuntu 9.4.0-1ubuntu1~20.04.1)
• スレッド数：8
  • 2～4スレッド程度だと起きないこともありますが，8スレッド以上使用すればほぼ再現します．
• レコード数：1億
  • 1億レコードを重複なしでputしたあとに全レコードを削除しています．

@thawk105
前回の索引打合せで依頼を受けたため，yakushimaのメモリ使用量について調査を行いました．調査結果の詳細はBoxにアップロードしましたが，1点気になる挙動が見られたためこちらで共有します．これがバグなのか仕様なのかまだ判別しきれていないため，お気づきの点があればお知らせください．

なお，メモリ使用量を確認している過程で，レコードおよび子ノードポインタの持ち方を修正すればおおよそ3～4割程度メモリの使用量を減らせそうなこともわかりました．今のところ明日以降は以下のメモリ資料量が急増する方を調査しようと思っていますが，この3～4割減らす方はやろうと思えば来週にはPRを出せるため，こちらの方を優先してほしいなどあればお知らせください．

実行環境

• Commit ID: ccafbb8（3/2時点のmaster）
• OS: Ubuntu 20.04.5 LTS
• Kernel: 5.4.0-132
• Compiler: g++ 9.4.0

発生している事象

yakushimaに対して挿入するキーの長さを64バイト（挿入するレコード数は約1億個，ペイロードの長さは8バイトで固定．ワークロードの詳細は後述）にすると，メモリの使用量が10倍になるという挙動が確認されました．こちらのスライドにあるとおり，{8, 16, 32} バイトに対しては微増しかしていないのに対し，64バイトに増やすとここで急に10倍になります．また，エクセルの詳細（yakushima detailシート）の方には載せてありますが，挿入するレコード数を10万に減らして128バイトのキーまで試したところ，64から128バイトにかけても更に10倍になりました．

こちらについて手続きレベルでの詳細はまだ確認していませんが，生成されているノード数を見る限り，おそらく1レコードに対して1 base_nodeが生成されているのが原因だと思われます．以下はエクセルからの抜粋で，Levelは根ノードの階層を0とした際の木の深さ，# of nodesはその階層のノード数，Actual usageは空レコードを除外した実際に使用されているメモリ使用量，Reserved usageはyakushimaのために使用されているメモリの総量になります．

ここで注目していただきたいのはlevel 13のノード数で，これは挿入したレコード数（112スレッドで892,857レコードずつ挿入）と一致しています．Actual/Reserved usageの差が大きいことからも各base_nodeが1つしかレコードを持っていないようなので，本来level 12でレコードを挿入すべきところでノードを挿入してしまっているような気配があります．

使用したワークロード

上記の問題が特定のエッジケースを引いただけの可能性もあるため，ワークロードの詳細も載せておきます．

使用した命令

Write（put）命令のみです．後述するように書き込むレコードのキーは重複なしのため，挙動としてはinsertのみになります．

パーティショニング・アクセスパターン

各スレッドが挿入するレコードのキーが重複しないようパーティショニングしています．パーティショニングはstripeで，スレッドの総数が $m$ のときスレッド $k$ は $m * i + k$ 番目のレコードの挿入を担当します．なお，アクセスパターンはrandomとしたため， $i$ の値は各スレッドの担当する挿入数 $n$ に対して $[0, n)$ の範囲から無作為＆重複なしで選ばれます．

使用したキー

キーは少し特殊で，直感的には4バイト非負整数を伸長することで {8, 16, 32, 64, 128} バイトに変換したものを使用しています．例えば16バイトの場合は，以下のように元の4バイト非負整数の各バイトをそれぞれ4バイトずつコピーすることで64バイトのデータとしています．

Original: 0xAB01
Extended: 0xAAAABBBB00001111

元となる値は上述したアクセスパターンのとおりで，全体で見れば挿入するレコード数 $N$ に対して $[0, N)$ の範囲で用意していることになります．

先日の打合せで報告したのですが，phone-billベンチマークにおけるYakushimaのメモリ使用量を調査する過程で改めてborder/interior nodesのメンバ変数を見たところ，いくらかの未使用領域を確認したため報告します．なお，全体のメモリ使用量に比べれば軽微な量であるため，優先度低めで確認していただければ大丈夫です．

詳細は上記リンク先の資料を参照していただきたいのですが，基本的にはノード用領域の先頭アドレスをキャッシュラインに揃えるためにborder nodeで16バイト，interior nodeで24バイトの未使用領域が発生しています．今回の実験で計測した限り索引全体の4～5%程度ではありますが，こちらはクラス宣言時のalignasを除くだけで解消できるため，アラインメントを外してしまってもよいのではないかと思います．手元で計測した限り，アラインメントの有無で性能はほとんど変化しませんでした（YCSB-A/B/Cで1 or 112スレッド使用して計測）．

また，こちらは未使用領域ではありませんが，クラスの継承機能（i.e., virtual function tableの利用）のために追加でメモリが使用されている面もあります．特にinterior nodeの場合，base node側からinterior node側のメンバ変数に切り替わる際に一旦8バイトでアラインメントが入るため，その分の未使用領域も発生しています．ただ，こちらは解消しようとするとコードの修正が非常に多くなる割にそれによって得られる効果が薄いため，積極的に実施する必要はないかと思います．

学会などがあり遅れてしまいましたが，格納値のinline化後にテストを行っていたところdelete命令を含むテストでたまに失敗が発生したため報告します．最初はこちらのコード修正によるものかと思いましたが，masterブランチでも再現したためメモリ使用量の削減などに関する変更とは無関係のバグと考えています．

なお，発生確率は低いです．ctestで100回も回せば1, 2回くらいは発生するのですが，たまに100回連続で発生しないこともあります．また，以下に挙げた2つのテスト以外はすべて成功したため，おそらくdelete命令に関するバグだろうと予想しています．

実行環境

• Commit ID: ccafbb8（3/2時点のmaster）
• OS: Ubuntu 20.04.5 LTS
• Kernel: 5.4.0-132
• Compiler: g++ 9.4.0

エラーログ（ctest）

yakushima_test-multi_thread_delete_200_key_test

53/63 Test #19: yakushima_test-multi_thread_delete_200_key_test ............................***Exception: SegFault  1.41 sec
Running main() from ../../third_party/googletest/googletest/src/gtest_main.cc
[==========] Running 2 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 2 tests from multi_thread_delete_200_key_test
[ RUN      ] multi_thread_delete_200_key_test.200_key
[       OK ] multi_thread_delete_200_key_test.200_key (869 ms)
[ RUN      ] multi_thread_delete_200_key_test.200_key_shuffle

yakushima_test-multi_thread_put_delete_scan_test

こちらはおそらく無限ループが発生しています．このログでは40秒ほどでテストをkillしましたが，最初に気づいた際はおそらく数分程度放置してそれでも終了していませんでした．

63/63 Test #44: yakushima_test-multi_thread_put_delete_scan_test ...........................Child terminated***Exception:  43.33 sec
Running main() from ../../third_party/googletest/googletest/src/gtest_main.cc
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from mtpdst
[ RUN      ] mtpdst.many_layer

[現状の仕様]
scan を実施するとき、要素が無ければ OK_ROOT_IS_NULL を返す。

[望ましい仕様]
この時、yakushima user がファントム問題検証のため後々の状態変化を観測できるように空のボーダーノードがルートとして存在していると、full scan 結果が null でも version 情報を獲得できて望ましい。

[必要な修正]
要素が空のときもルートとしてボーダーノードを存在させる。

[現状の問題]
現状 scan の仕様として、レンジの外の要素になったら処理を終了している。

レンジスキャンとして [2:100] の範囲を与えられたと仮定し、
リーフノード A, B, C が存在すると仮定し、
A: 1,
B: 51,
C: 102
が入っていると仮定する。
A, B を分岐させる内部ノードのキーは 3 であると仮定し、
B, C を分岐させる内部ノードのキーは 90 であると仮定する。
スキャンは左端点が 2 であるため A のノードに降り、A では要素を収集せず、 B で 51 を収集し、C で 102 がレンジ外であることを確認し、 51 という結果と B のノード情報を返す仕様である。
しかし、yakushima user (ex. shirakami) がファントム検証をする段階では A に 2, C に 91 が挿入されていたとして、ノード情報が B しか収拾されていないとファントムを検出できない。
このようなケースでは A, C のノード情報も必要である。

[IF の検討事項]
現状、スキャン結果に関する IF 引数の tuple_list, node_version_vec の要素は 1:1 対応関係となっている。

問題の事象

・https://github.com/project-tsurugi/yakushima/actions/runs/6376901833/job/17304616012#step:6:842
delete 操作において、期待されないコードパスを踏んでいる。
・確率的に発生している。

TBD

問題の観察：
943b1b7
上記にて、 1 bytes から 2 をかけていった数字それぞれに対して、 put, scan, delete を実施したとき、 256 bytes でエントリを削除しようとしたときに見つからなくなった。

inline 化 によって uint64_t を正常に格納できなくなっている。
64bit の型であっても、 int64_t のように正常に扱えるものもある。
(https://github.com/project-tsurugi/tsurugi-issues/issues/256 の調査中に発見)

原因:

• inline 可能かどうかを判定する yakushima::is_inlinable において、 ポインタ値のみを inlinable としようとしているようだが (根拠1 #24 (comment) , 根拠2 ソース中のコメント )、 std::is_same_v<ValueType, uintptr_t> のため、単なる 64bit非負整数の uint64_t も is_inlinable で true とされてしまう。
• inlinable とされた場合には、ポインタ値であるとみなされる。
• ポインタ値の上位数ビット(現実装では上位2ビット)は立っていないと仮定され、確認せずにフラグ領域として扱う。
• そのために、上位ビットまで埋まった uint64_t を格納すると必然的に値が破壊されるか不正メモリ参照となる。

バージョン

• 問題発生: 61cd9dd
• 正常動作: 008a9b2