読者です 読者をやめる 読者になる 読者になる

Software Transactional Memo

STM関係のことをメモっていこうと思います。

STMにまつわる用語メモ(すごく自信ない)

  • Strongly/Weakly Atomic

トランザクション中で読み書きしている値が非トランザクションから読みだしても同じ値を読めるかどうか、という物。HTM(Hardware Transactional Memory)はキャッシュラインの拡張なだけあって、非トランザクションからでも普通に読み出せる。こういうのはStrongly Atomicと呼ぶ。STMは大半がWeakly Atomicのはずなんだけど時々例外があるのでよく分からない。

  • Opacity

ゾンビトランザクションを発生させない工夫。STMはデータベースのトランザクションと異なりアトミックブロック内には原理上いくらでも好きなコードが書けてしまうので無限ループやゼロ除算やひょっとしたらIOだって起こりうる。これらに対してアトミックブロックを監視付きのサンドボックス化することなく、そもそも非一貫な値を読まないように制御する仕組みが有る事。STMそのものがSerializableな一貫性を保障していても、読み出しは逐次に行っていくので、時間軸のズレた値を読んでからアボートされるまでの間という、データベースを使ってる際にはたぶん気にする必要の無かった物をSTMは気にする必要があるという点に注意。不透明性という言葉が日本語としてしっくりくる気がする。

  • Privatization safe

辞書を引いたら「民営化」って出た…。アトミックブロックが外部から見ても順序的にセーフかどうかの定義らしい。Strongly/Weakly Atomicの項とどういう関係があるのかは謎だけど、これのセーフさにも段階があって、厳密な程直感に即して動くしパフォーマンスを出しにくい一方で、緩いほどパフォーマンスが出るしバグりやすい。というコンピュータ工学にありがちな感じっぽい。実装時に選択の余地があるものらしい。現時点で僕が一番意味がわかっていない用語。

  • Visible/Invisible Reader

値に対して読み出し者が居るよという事を何らかの方法で表明するのがVisible Reader。Invisible Readerは何も言わずにただ読むのみ。Visibleの方が、書き込み側が読み出し者の存在を見て書き込みを遅延したり、書き換える際に読み出し側をまとめてabortできたりするので読み出し側の正当性チェックを省いたりして便利そうに見えるけれど、実際にそれを実装したRSTMではその表明にかかるコスト(アトミック命令使うだのキャッシュコヒーレンスが走るだの)のせいで足を引っ張られてあまりスケーラビリティが出なかったらしいとかdisられてる。リードロックを取る場合もVisible Readerに分類される。

Invisible ReaderはマルチリーダーでノンブロッキングなSTM(DSTM, OSTM, ASTMあたり?)で人気の手法で、コミット前にもう一度読み出し直す事でSnapshotして、read lockすら無しに一貫的な読み出しを実現している。一方で読み書きプロトコルとしてはSnap shot読み出しは読み出し側が最弱な部類なので、公平性は怪しくなる。

たぶんそういう前提があるから、TLRWはSNZI-Rによってキャッシュコヒーレンス操作を最小限にしたReadWrite Lockを実装することで公平性とスケーラビリティとを両立する、という方針になったのだと思われる。

  • Nest

トランザクショントランザクションの扱い。一番簡単なのは全部外側のトランザクションの一部として融合させること、Composabilityそのものですね。最適な部分ロールバックを行うために真面目にネストをサポートする試みもあるんだけど、具体的にどうやってるかは調べてない。HTMだとサポートしてるものをよく見る気がする。