ロック競合をなくすSafe Optimistic Lock Coupling、型システムで安全性を保証

CPUコア数の増加に伴い、並行データ構造のスケーラビリティが重要になっている。従来のlock couplingはルートノードのロック競合でスケールしないが、Optimistic Lock Couplingは読み取りを純粋な読み取り専用にし、バージョン番号で整合性を検証する。さらに、未検証の値を専用型でラップし、コンパイラに検証を強制させることで、競合状態を防ぎつつ高い性能を実現する。

コンパイラは、実行時に微妙な競合状態になるようなミスを検出してくれる。
  1. dichloromethane

    でも、このコードは壊れているように見える。この種のロックフリー並列アルゴリズムの大きな課題は、常にライフタイムをどう扱い、use-after-freeを防ぐかだ(このツリーから何も解放したくないのでなければ、だが、それはあまり現実的ではない)。

    根本的な問題は、ライターが free() したノードをリーダーが参照するのを防ぐものがないことだ。これを修正するには、RCU か Hazard pointers を追加する必要がある。

  2. PeterWhittaker

    素人質問で恐縮だが、これは私の専門分野ではないので、Rust には RwLock がある。なぜ単純に RwLock を使って多数のリーダーと単一のライターを許可しないのか?

    このアプローチはどのように RwLock を上回るのか(「上回る」の任意の解釈において)、そして RwLock はどのようにこのアプローチを上回るのか(同様に)?

  3. windenntw

    よく書かれていて、内容も良く、ランダムなジャンクを売り込もうとしない、+10 また読みたい :)

この日のほかの記事

2026-10-05