STMの設計と進化 @kumagi 熊崎 宏樹 聴講者想定レベル：Java初級者

最初に このスライドは後で全部アップロードします その為、論文名などのメモ取りは不要です 120ページほどありますが25分で話せる気がしません 懇親会などで質問してください

Why STM? ロックを使ったプログラムは そもそもエンバグしがち 再利用が難しい マルチコアを生かしにくい それ、Software Transactional Memoryで解決できるよ！

トランザクションとは？ 複数の手続きをまとめて一つの不可分な手続きとして扱う事 データベースの世界ではACID特性という用語がよく一緒に用いられる Atomic: 手続き全体がAll-or-Nothingとなる Consistency: トランザクション前後でデータに整合性が取れている Isolation: コミットしていないトランザクションによる作用は外から観測できない Durability: コミットした結果は永続化される

基礎知識 Compare And Swap関数 sun.misc.Unsafe.compareAndSwapInt等で使える 指定したメモリ番地に対して 指定した値Aと等しいかを比較 比較した結果一致したら値Bをそのメモリ番地に書く 成功したらTrue、失敗したらFalseを返す の動作をアトミックに行うCPUの命令 x86アーキテクチャだとcmpxchgというニーモニック 以後断りなくCAS命令と呼びます

STMの歴史 CPUのキャッシュ制御プロトコルを拡張することでメモリ内でトランザクションが可能じゃん！プログラミングしやすくなっていいよ！ (Mauriceら Transactional Memory: Architectural Support for Lock-Free Data Structures 1993) ソフトウェアでも同じような事が可能だったよ！ (Nirら Software transactional memory 1997)

どう書けるのか？ synchronized { x += 100; y -= 100; } atomic { x += 100; y -= 100; } synchronizedをatomicに書き換えるだけ！ これでブロックに囲まれた処理全体が All-or-Nothingになる

どう嬉しいのか？ atomicで囲んだ部分は可能な限り並列して動作する　→　マルチコアの性能を生かせる atomic { x += 100; y -= 100; } atomic { z += 100; w -= 100; } synchronized { x += 100; y -= 100; } synchronized { z += 100; w -= 100; } 並列実行可能！ ロック競合…

どう嬉しいのか？ 操作を組み合わせ可能 トランザクション中で他のトランザクションを実行 STMを使ったコードを簡単に再利用可能 class BankAccount { ... atomic public void add(int diff) { credit += diff; } private int credit = 0; } 使う BankAccount x; BankAccount y; ... // xからyに100ドル送金 atomic { x.add(-100); y.add(100); }

どう嬉しいのか？（実験1） 書きやすい！ 学生12人を6チームに分けてサーチエンジンを作らせてみた。 普通のC++とIntelコンパイラのSTMを使うチームで分けたところSTMのチームの方が高速でシンプルなコードを書いた （Victorら Transactional Memory versus Locks - A comperative Case Study）

どう嬉しいのか？（実験2） 書きやすい！ 学生147人にJavaでゲームを作らせてみた 粗粒度ロック・細粒度ロック・STMの3つのスタイルでバグの量を比較 (Christopherら Is Transactional Programming Actually Easier?)

圧倒的に少ないバグ率！

余談：Cliff ClickとRich Hickeyの議論 当時Azul SystemsのCTOだったCliff Click氏と、Clojureの作者Rich Hickey氏の有名な議論 Cliff「デッドロックはJavaならスレッドのダンプが簡単に取れるから一番解決しやすいバグでしょ」 Cliff「その点、STM由来のライブロックのデバッグは辛い。発生しているかも気付けない」 Rich「それでもなおComposabilityの一点は評価する価値がある」 Cliff「ふむ…」 出典： http://www.azulsystems.com/blog/cliff/2008-05-27-clojure-stms-vs-locks

どう作るのか？ 非常に原始的なSTMからスタートし、近年の研究を追いかけながら改良していく順で説明 言語レイヤーでコンパイラがどうサポートするのかという話は今回のスコープ外 STM内部の設計の進化とは少し違う

スタート地点 オブジェクト毎にロックを取り付ける トランザクションはいい感じにロックを取って動いて欲しい class BankAccount { ... synchronized public void add(int diff) { credit += diff; } private int credit = 0; } Javaで普通のロックを使うコードの例

synchronizedではなぜダメか 内部で行われるロックを展開してみる synchronizedなメソッドは自動でロックを取る BankAccount x; BankAccount y; ... // xからyに100ドル送金 x.add(-100); y.add(100); BankAccount x; BankAccount y; ... // xからyに100ドル送金 x.lock(); x.add(-100); x.unlock(); ←アンロックしてる y.lock(); y.add(100); y.unlock();

synchronizedではなぜダメか アンロックを行うとなぜ不味いのか // xからyに100ドル送金 x.lock(); x.add(-100); x.unlock(); y.lock(); y.add(100); y.unlock(); この隙間にもし「銀行の全口座の残高の合計を算出する処理」が挟まったら？ 100ドル消失！

どんなロックの取り方がいいのか？ さっきの例だけで言えばこういう挙動になって欲しい // xからyに100ドル送金 x.lock(); x.add(-100); y.lock(); y.add(100); x.unlock(); // 最後にアンロック y.unlock(); 2口座間だけではなく、より一般的に言うと？ 複数のロックの正しい取り方は一般化できるのか？　→　できる

2 Phase Lock

2 Phase Lock 本日覚えて貰いたい用語No.1 2相ロックとも言う 「複数のロックを獲得する手続きは、2つのフェーズに分かれるべきだ」というロック利用の作法（プロトコル） 2つのフェーズ（相）とは 成長相：ロックを獲得し続ける 減退相：ロックを解放し続ける

2 Phase Lock 手続き全体が成長相と減退相の1つずつからなるべし 1 2 獲得しているロックの数 時間 成長相 減退相

2 Phase Lock つまりこれはだめ 成長相・減退相が2回以上ある

2 Phase Lock これを用いれば、複数のロックを取る操作が一つの不可分な操作として外部から見えるようになる 専門用語を使うと、競合等価直列化可能なスケジュールを作成できる、と言う なぜそうなのかという説明はデータベースの本などを（Concurrency Control and Recovery in Database Systems, Addison Wesley Publishing Company, ISBN 0-201-10715-5）

Serializability 2PLはSerializableな実行を動的に紡ぎ出すシンプルな技法 処理Aと処理Bを並行して実行する例 処理Aと処理Bの全ての非決定実行のパターン A→Bの実行順と 同じ結果に辿り付くパターン B→Aの実行順と 同じ結果に辿り付くパターン 2PLが許す実行パターン 2PLが許す実行パターン バグるパターン

2 Phase Lock 利点 競合等価直列化可能なスケジュールを動的に組み立てる事ができる 欠点 競合等価直列化可能よりも広いスケジュールは組み立てれない 競合等価直列化可能より広い直列化可能スケジュールとしてビュー等価直列化可能などがある デッドロックは回避してくれない

2 Phase Lockを用いたSTM オブジェクトにアクセスするときはそのデータのロックを獲得する 既にロックを取っているなら何もしない コミットするまでロックを手放さない ある程度の時間ロックを獲得できなかったらデッドロックと見なして作業内容を巻き戻す 作業を巻き戻せるように元のデータの複製をロック獲得時に作っておく

2 Phase Lockを用いたSTM STMから利用する全部のデータにロックを取り付ける X Y Z X Y Z

Y 2 Phase Lockを用いたSTM トランザクションはロックを獲得したらオブジェクトを手元に複製する(undo-logと言う) X Y Z Transaction1(以後T1) X X' Y'

Y 2 Phase Lockを用いたSTM トランザクションが無事コミットまで辿りついたらロックを開放してバックアップを消去する X Y Z Transaction1(以後T1) X X' Y'

Y 2 Phase Lockを用いたSTM デッドロックした場合にはランダム時間の待機後アボートする X Y Z T1 X X' Y' T2 y→xの順にアクセスしたい x→yの順にアクセスしたい

2 Phase Lockを用いたSTM デッドロックした場合にはランダム時間の待機後アボートする X Y Z T1 X X' Y' T2 Abort! x→yの順にアクセスしたい Y 続行できる！

2 Phase Lockを用いたSTM 今回のSTMの特性を書き並べると Pessimistic Concurrency Control(悲観的ロック) Eager Versioning (commitまで待たずに即書換え) Eager Conflict Detection (実行中のトランザクション同士も即座に衝突) 個々の用語は追って解説します 今は聞き流して頂ければ

2 Phase Lockを用いたSTM ACI特性を満たす事ができる Atomic: 全体を実行できなければアボートして書き戻すから大丈夫 Consistency: 2PLのお陰でSerializable Isolation: ロックのお陰で他のトランザクションからはアクセス不能 Durabilityはそもそも揮発性メモリなので考えない でも遅い。たくさん改良の余地がある これから改良の試みを追ってみる

データの読み出しについて トランザクション中で読み出しにしか使わないデータは複製しても無駄 無駄なデータは複製しない事でオーバーヘッドを削減 更に言うと、読み出すだけなら複数のスレッドで共有していても良い 複数のトランザクションが共有できるロックであるReader-Writer Lockの出番

Reader-Writer-Lock 複数のReaderが衝突しないロック Reader-WriterやWriter-Writerは衝突する 1word幅のメモリを用いた実装例は以下 0 0 Readerの数 Writer 1word read lock 1 0 write lock 0 1 read lock n 0 unlock unlock unlock read lock unlock ※状態遷移はすべてCompare And Swap命令で行う

Read-Write-Lockで本当にいいの？ トランザクションって本当に読むだけで終わる時と終わらない時がある 残高がマイナスの時に限り利息を取るとか つまりRead-LockからWrite-Lockへの昇格が必要 Read-Lockを取っているスレッドのうち一つがUpgrade可能となるようにプロトコルを設計しよう このUpgrade可能なロックを全部のオブジェクトに取り付ければSTMから便利に使えるはずだ

Upgrade-Lock 1word read lock write lock unlock Upgrade待ち upgrade unlock * n write lock read lock unlock upgrade UpgradeをしたくなったらUpgrade待ちビットを立てて他のすべてのReaderの離脱を待つ Upgrade待ちビットが立ったらそれ以上他のスレッドはLockを取れない unlock unlock ※状態遷移はすべてCompare And Swap命令で行う

Upgrade-Lockを用いたSTM 良さそうに見えるが実は凄く遅い 詳細は Bratinらの McRT-STM: A High Performance Software Transactional Memory System for a Multi-Core Runtime なぜならRead-WriteロックはCAS命令を酷使 普通のロックならunlockにCAS命令は不要 CAS命令は1回40クロック程度のコストが掛かる 競合時は更に遅くなる メモリの書き換えでキャッシュラインが汚れる

解決策：Versioned Lock STM進化の最初のブレークスルー オブジェクトにバージョンを付ければロック無しでも安全に読み出しができる。 しかもキャッシュラインも汚れない 読みだしたデータはRead-Setとしてバージョン番号と共にスレッドローカルな場所に保持する コミット時にバージョン番号を比較すれば良い

Versioned Lock バージョンのカウントとロックの両方ができる ついでにロック保持者のトランザクションディスクリプタへのポインタも保存できる(abortに使える) 更新に成功してアンロックするたびバージョンが増える 1wordでの実現例は以下 versionフラグ lock Pointer to desc unlock ポインタの下位1bitは必ず0 ※状態遷移はすべてCompare And Swap命令で行う

比較 比較 Versioned Lockで何ができるか？ Read Snapshotができる 値と一緒にバージョン番号を読み出しておく X Y Z v3: 120 v2: 42 v5: 459 v3: 120 v2: 42 v5: 459 単調増加するはずのバージョン番号が変動していないのでこの赤い期間の間にはデータは書き換えられていない t t t 比較

読み出し方に注意 ロック無しでデータを読むため読み出し方には注意が必要 int v1 = x.version(); if (v1 & 1 == 0) { abort(); // 既にWriteスレッドが保持している } Object result = x.value; int v2 = x.version(); if (v1 != v2) { abort(); // valueを読んでいる間にWriteされた } return result;

閑話休題：CPUのキャッシュ CPUは高速化のため、メモリの一部を手元に複製している（これをキャッシュと呼ぶ） 複製する単位をキャッシュラインと呼ぶ。大きさは64byteぐらい 最近のCPUはキャッシュをコア間で共有している 共有の際はキャッシュコヒーレントプロトコルを用いる Core1 Core2 L1キャッシュ L1キャッシュ L2キャッシュ コヒーレント

キャッシュコヒーレントプロトコル IntelならMESIF、AMDならMOESIというプロトコル キャッシュラインが取る状態名の頭文字が由来 Modified: メモリよりもキャッシュの方が新しい Exclusive: メモリとキャッシュが同一であり、他のコアはこのキャッシュラインを持っていない Shared: メモリとキャッシュが同一であり、他のコアもこのキャッシュラインを複製している Invalid: 正しいキャッシュを持っていないので読むな Owned: 俺がメモリだ(Shared可能なModified) Forward: Sharedのボス。アクセスする際にはこいつに伺え

共有した キャッシュコヒーレントプロトコル MESI(F)プロトコルはModifiedなデータを他のコアが読み出す際にメモリに書き戻す Sharedなデータを書き換える時にはInvalidation要求をブロードキャストするためトラフィックが混む Modified Shared Invalid Exclusive 共有を要求 （メモリアクセス発生） Invalidation要求が来た 新規に読み出した 書き換えた 他のコアから貰った

キャッシュを汚す事はギルティ 他のスレッドから繰り返し読む値を書き換え続けると、キャッシュラインのステートはModifiedとSharedの間を行ったりきたりすることになる。これは激しいトラフィックを起こす。 更にはModifiedからSharedになる度に下層のメモリに書き込まなくてはならない Core1 Core2 L1キャッシュ L1キャッシュ L2キャッシュ write read うぉー！ うぉー！ ぎゃー！！ write Invalidate

キャッシュを汚す事はギルティ http://www.1024cores.net/home/lock-free-algorithms/first-things-first から 共有データにWriteした場合の速度 localデータにWriteした場合の速度 共有/localデータからReadした場合の速度

http://www.1024cores.net/home/lock-free-algorithms/first-things-first から まったくスケールしない！！！！

話を戻してVersioned Lock Readする際にはバージョン番号と値のペアを読み出すだけ。書き込まない！ コミット時にもう一度バージョン番号と値のペアをすべて読み出し直す Read-Onlyなトランザクションであれば共有データには一切書き込みを行わない！ Invisible Readerと呼ばれるSTM設計パターン キャッシュラインのステートがSに固まる Readが多いトランザクションほど高速化する！

Versioned Lock Versioned-Lockに比べてRead-Lockがどれだけ遅いかを表したグラフ 出典：McRT-STM: A High Performance Software Transactional Memory System for a Multi-Core Runtime ワークロードによってはざっくり10000倍遅い

ここまでのおさらい 2 Phase Lockプロトコルに従えばSerializableなトランザクションが作れる でも愚直にやると遅い Readがデータを汚さない事に着目して、バージョン番号をRead Lock代わりに使えば高速化できる でも 2 Phase Lockの庇護を失ってしまった さあどんなデメリットが？

2 Phase Lockの外は危険がいっぱい Read時にロックを取らなくなったので、Readしたデータが他のトランザクションによっていつ書き換えらてもおかしくない でもコミット時にバージョン確認によって正しいかどうか確認するから何かあったときはアボートするだけでしょ？ 甘い！

ゾンビトランザクション問題 以下はRead Skewと呼ばれる異常パターン 発生する問題は Inconsistent Read問題 左のトランザクションは永久に衝突に気づけない コミット時まで値の正しさを検証できない atomic { // この時点でx==y==20 int tmp_x = ReadTx(x); int tmp_y = ReadTx(y); while (tmp_x != tmp_y) { // 無限ループ } } atomic { WriteTx(x, 10); WriteTx(y, 10); }

ゾンビトランザクション問題 トランザクションとしては既に致命傷を負ってるから死ぬしかないのに、検証するタイミングまで辿り付けないから死んだ事すら自覚できないゾンビ状態の事 無限ループの他にも0除算やSegFaultなどヤバい事をやらかすパターンは無限にある

ゾンビトランザクション回避策 ロックを取る（2 Phase Lockに戻る） キャッシュコヒーレントが重いから取りたくない Incremental Validation 値を1つReadTxで読むたびに過去に読んだ値を全て確認し直す 確認1回はN回のメモリアクセスを行うのでN箇所読むトランザクションはO(N^2)回読み出すことになる ← 超重い

ゾンビトランザクション回避策 Global Commit Counter コミットが成功するたびにインクリメントする共有カウンタを1つ用意する 前回のReadTx時と今回のReadTx時でカウンタの値が変わった場合に限り過去に読んだ値を確認 つまりカウンタを目印にIncremental Validationの検証回数を間引く 詳細は Michaelら: Conflict Detection and Validation Strategies for Software Transactional Memory(DISC 2006)

ゾンビトランザクション回避策 (Semi-)Visible Readerに変える Readerの存在を伝えることができればWriterを抑制できる 例えばSkySTMはSNZI(後述)を使ってReaderの存在をスケーラブルに残している Global Clockを使う（後述） 効率が良いお勧めのアルゴリズム

Opacity RachidらのOn the Correctness of Transactional Memory (2008)によって提唱された「トランザクショナルメモリの正しさの基準」であるOpacity SerializabilityやLinearizabilityなどの基準は「成功した」トランザクションのふるまいについてしか定義していなかった Opacityは「すべてのトランザクション（Abortする物も含む）は、一貫したメモリのみを観測しなくてはならない」という基準 更にLinearizableであること 更にAbortされるトランザクションによる作用は全てのトランザクションから見えない事

Why Opacity? データベースの世界で同様の問題はなかったの？ 無かった。保護対象がデータベースに閉じていたため「一貫性の無いデータを読んだトランザクションはそのうち死ぬ」という基準で解決している 「そもそも一貫性のないデータを読むトランザクションの発生を許さない」という基準はプログラムと密接にくっついたトランザクショナルメモリならではの問題

Global Clock STM進化の一つの大きなブレークスルー Opacityを保証する Transactional Locking II(TL2)がこれを利用した最初のSTM 詳細は(Diceら Transactional Lockng II (2006)) TL2はシンプルで高速なため、最新の論文でもよく比較対象に挙がる

Transactional Locking 2 個々のオブジェクトにVersionを付ける それに加えて全体で単調増加するカウンタを共有する コミットが成功するたびにカウンタを1増やす コミット成功時に個々のオブジェクトのバージョンにそのカウンタを使う

Global Clock in TL 各トランザクションは初めにGlobal Clockを読む X Y 5 2 3 2 < 5 => OK 6 5 < 5 => NG! Write! Read Commit! Abort...

ゾンビ化しない Global Clockのお陰で誤ったReadが起きない ロック無しでread/write conflictに対策できる atomic { // この時点でx==y==20 int tmp_x = ReadTx(x); int tmp_y = ReadTx(y); while (tmp_x != tmp_y) { // 無限ループ } } atomic { WriteTx(x, 10); WriteTx(y, 10); } Abort!

Lazy Versioning Eager Versioning(これまでの手法)だとWriteは悲観的にロックを取ってしまうのでロック期間が長くなりがち 各スレッドはコミットまでに「コミット時にやること」をローカルで整理して、コミット時だけロックを取って一気に書けばロック期間が短くなる！

Transactional Locking 2 コミット直前までロックは取らない Readはバージョン番号をSnapshotして読む 書き込むデータは変わりにredo-logに保存 Y' X Y Z X' redo-log 2 3 2 3 2

redo-log Transactional Locking 2 コミット時に各オブジェクトのロックを取る redo-logとバージョンを比較 問題なければGlobal Clockを添えて書き込み実行 X Y Z Y' X' 2 3 2 3 2 ロック！ 5 5

パフォーマンス Fast

ここまでのおさらい パフォーマンスを得るために2 Phase Lockから足を踏み外した するとゾンビトランザクション問題に襲われた しかしGlobal Clockを備えたTL2によって華麗に解決 TL2はまだ改良できるのではないか？ TL2の改良について追っていく

Bloom Filter Redo-Logの管理に使う Bloom Filterは集合にデータが含まれているかを高速に検知するデータ構造 あ い う え お あ か い ふ く あ か い ふ く ←あいうえお検知器 検知 検知 すっぽり覆われた物は「あいうえお」のどれかである"確率が高い"

Z Y redo-log Bloom Filter 既にredo-logに書いてる物に上書きしたい時はredo-log内で上書きする必要がある 値に書き込む度に「これってredo-logにもう入れたっけ？」と検索する必要がある 検索の前さばきにbloom filterが便利 X Y Z 2 3 2 Bloom Filter X Z 2 Y X' 2 3 X

TL2の改良（いっぱいある） Read Onlyトランザクションはコミット時にGlobal Clockに触らなくても良い トランザクション開始時とコミット開始時でGlobal Clockが等しければ他のトランザクションが書き込みをしていないのでValidation不要 複数のデータを読む時はバッチ化することでバージョン番号→メモリ→バージョン番号のsnapshootingのメモリフェンスを削減可能 A,Bのバージョンを読んでメモリフェンスしてA,Bを読んでメモリフェンスしてA,Bのバージョンを読む

TL2の改良（いっぱいある） TinySTM Pascal Felberら Dynamic Performance Tuning of Word-Based Software Transactional Memory(2008) バージョン番号をN回確認するの重い メモリアドレスを大雑把なセグメントに分けてそこにもバージョンつければ、バージョン番号のチェックを大幅にサボれる

Hierarchical Locking A 2 B 3 C 5 D 1 E 3 F 4 G 3 H 1 I 3 J 4 K 4 L 6 M 2 N 1 O 4 P 5 Q 6 R 7 S 8 T 9 U 6 V 3 W 2 X 4 Y 4 Z 6 5 6 7 9 6 コミット時にオブジェクト毎のバージョン番号に加えてセグメントのバージョン番号も上書きしておく Commit中のトランザクション のバージョンが変わってないかチェックしたいなー 比較3回でOK!

TL2の改良（まだまだある） Global Clockへの更新のキャッシュコヒーレントトラフィックがボトルネックになるかも？ 各メタデータのClockにスレッドIDを埋め込めばGlobal Clockを増やさなくてよいケースがある（TL2の論文内） 複数のトランザクションが同時に衝突なくコミットするなら同一のバージョン使ってもいいのでは（Ruiら Commit phase in timestamp-based STM（2008）） GV4: Global ClockへのCASの失敗は無視して良いのでは？（Yossiら Anatomy of scalable software transactional memory（2009））

TL2の改良（まだまだある） GV5: Global Clockを更新したつもりになって、増やした後のGlobal ClockをObjectのバージョンとして書きこんでいけばよいのでは？ それだとGlobal Clockより大きいバージョンのオブジェクトを読もうとするトランザクションが永久に完了できない そんなのは一部の不幸なスレッドだけだ GV6: 1/32の確率しかバージョンのIncrementを試みないというのでどうだ？（Yossiら Anatomy of scalable software transactional memory（2009））

出典：Yossiら Anatomy of scalable software transactional memory（2009） Fast

TL2の改良（まだまだある） TL2C: Global Clockの代わりにVector Clockを使えば大丈夫！ (Hillelら Maintaining Consistent Transactional States without a Global Clock(2008)) 各オブジェクトに[コミットしたスレッドID, その時のスレッドのClock]をバージョンとして付与 全スレッドが自分以外の全スレッドの「最後に観測したクロック」を記憶 そこと食い違ったらAbortしてクロックを上書きして再実行

出典： Hillelら Maintaining Consistent Transactional States　without a Global Clock(2008) Fast

ここまでのおさらい TL2は良いSTM そのためTL2をベースにした改良版がいくつも出てきて研究が進展した STMの実装を分類学的に見るとどうなるのだろうか？

STMの実装上の選択肢 直交する複数の軸がある（直交しない事もある） これらで実存する実装を（いくらか）分類する事ができる

Eager Versioning と Lazy Versioning X Y Z Read Z' Read lock! unlock! Write Y' lock! unlock! Write validation! Commit X Y Z Read Z' Read lock! unlock! Y' lock! unlock! Write validation! Z' Y' redo redo Write Eager Versioning Lazy Versioning TL2はこっち

Lazy Versioning 利点 ロック保持期間が短くなるのでスケールしやすい コミット中のスレッド同士しか競合しないのでLive-Lockが発生しえない 複数ロックがある場合でもロックを取りに行く時点で全ての欲しいロックが分かっているのでロックの獲得順序を全スレッドで統一できる つまりデッドロックを簡単に回避できる Abortするトランザクションが共有メモリを汚さない Abort時にはログを消去するだけで済むので高速

Lazy Versioning 欠点 コミットする際にredo-logの内容を全部本来の場所に書き込む必要がある redo-logを作成するコストを考えると二度手間 トランザクションが同じ場所に何度も書き込む手続きの場合、redo-log内を何度も検索する必要がある 遅い TinySTMはこれを避けるため、Eager Versioningを使っている

Eager? Lazy? どちらが良いかは場合による データベース界隈でもどちらかが決定的に良いという事はない様子？

STMの実装上の選択肢 直交する複数の軸がある（直交しない事もある） これらで実存する実装を（いくらか）分類する事ができる

Conflict Detection いつ書き換えるか（Versioning）の他に、いつ衝突を検知するか（Conflict Detection）にも直交する実装上の選択肢がある 最初にアクセスする時に検知する？(Eager) 実行中何度も検知する？(Incremental Validation) コミットする瞬間まで検知しない？(Lazy) TL2はLazy Conflict Detection 最初のTransactional MemoryはEager Conflict Detection

Lazy Conflict Detection コミット時まで衝突を検知しようとしない LazyなVersioningと組み合わせる事が多い 利点 チェックののべ回数が少ない 必要のないリトライを行わないのでスループットが出やすい 欠点 コミットまで走り切らないと間違いに気付けない

いつ衝突を検知するか？ Eagerな検知だと初めのWriteが衝突しあう 適切に片方のトランザクションだけ走るように調停する必要がある pが低い(滅多にアボートしない)の時に効率が良い atomic { WriteTx(x, 1); // 何かすごく重い処理 if (prob(p)) { Abort(); } } atomic { WriteTx(x, 1); // 何かすごく重い処理 if (prob(p)) { Abort(); } } 確率pでTrueになる

いつ衝突を検知するか？ Lazyな検知だとコミットまで衝突しない 重い処理　が複数のスレッドで走ってしまう pが高い(よくアボートする)時にどれかが早くコミットに辿り着ける見込みがある 下手な鉄砲数撃ちゃなんとやら atomic { WriteTx(x, 1); // 何かすごく重い処理 if (prob(p)) { Abort(); } } atomic { WriteTx(x, 1); // 何かすごく重い処理 if (prob(p)) { Abort(); } } 確率pでTrueになる

いつ衝突を検知するか？ つまりどちらかが常に良いという事はない この場合はp次第で最適解が変わる アボートが多い時だけLazyにしてはどうか？ AdamらTransactional Monitors for Concurrent Objects(2004) Write-Write衝突はEagerに、Read-Write衝突はLazyに検知してはどうか？ Michaelら A Comprehensive Strategy for Contention Management in Software Transactional Memory(2009) atomic { WriteTx(x, 1); // 何かすごく重い処理 if (prob(p)) { Abort(); } } atomic { WriteTx(x, 1); // 何かすごく重い処理 if (prob(p)) { Abort(); } } 確率pでTrueになる

STMの実装上の選択肢 直交する複数の軸がある（直交しない事もある） これらで実存する実装を（いくらか）分類する事ができる

Granularity トランザクションで保護するデータの粒度 これまでの説明では暗黙的にオブジェクト（C言語的には構造体）単位にメタデータを取り付けてきた 実際はメモリのワード単位で保護するタイプのSTMもある Word-based STMやObject-based STMなどと呼ぶ

Object-based STM 各オブジェクトに1つずつメタデータを取り付ける 利点 連続しているのでキャッシュに同時に載る オブジェクト全体が一気に保護できる プログラム言語の機能に取り込みやすい 欠点 例えば配列をオブジェクトにすると、配列の異なる場所へのアクセスも競合アクセスとなってしまう Object メタデータ Object メタデータ Object メタデータ

Word-based STM ワード単位でオブジェクトを保護する 利点 巨大なオブジェクト（配列）の一部のデータのみを書き換えるなどのパターンに強い 既存の実装に外付けで機械的にトランザクション化できる 欠点 メタデータが多くなりがち メタデータへのアクセスが遅くなりがち

Word-based STM メモリ番地に対するメタデータを離れた場所に持つが、トランザクションはその両方に触れる必要があるのでキャッシュのコストが2倍 メタデータ メモリ メタデータ メタデータ メタデータ メタデータ メタデータ メタデータ メタデータ

Word-based STM ハッシュ関数などでN:Mの対応にする事もある メタデータを減らし過ぎると偽共有の問題が発生する メタデータ メモリ メタデータ メタデータ メタデータ メタデータ

STMの実装上の選択肢 直交する複数の軸がある（直交しない事もある） これらで実存する実装を（いくらか）分類する事ができる

Nest トランザクション中でのトランザクションをどう扱うか？ Flatten: 外のトランザクションと結合する。どの時点で失敗しようと全体をロールバック Closed: 内側のトランザクションが失敗したときは内側だけロールバック Open: 内側だろうが外側だろうがコミットはコミットでメモリに書き込む

Flattened Nesting すべて最外周のトランザクションに合成される 利点：実装が楽 欠点：アボート時に高くつく atomic { WriteTx(x, 2); atomic { WriteTx(x, 3); ... AbortTx(); } ... }

Closed Nesting 内側は内側で処理される 利点：アボート時のペナルティが少ない 欠点：実装が複雑で遅くなりがち atomic { WriteTx(x, 2); atomic { WriteTx(x, 3); ... AbortTx(); } ... } デフォルトでFlattenで動作し、Abort時のリトライだけClosedにスイッチする等の戦略が考えられる

Open Nesting どのポイントでもトランザクションのコミットは常にメモリを更新する 利点：性能が高まりやすい 欠点：使いどころが難しい atomic { WriteTx(x, 2); atomic { WriteTx(x, 3); ... } AbortTx(); ... } // ← ここでは x == 3 Yangら Open Nesting in Software Transactional Memory (2007)

STMの実装上の選択肢 直交する複数の軸がある（直交しない事もある） これらで実存する実装を（いくらか）分類する事ができる

Isolation トランザクション中で触るデータに、トランザクション外から触ったらどうなるのか？ ロックの場合であっても迂闊に触ったら壊れるのは一緒 でもロックなら注意深く触れば大丈夫なパターンはいくつもある STMではどんなに注意深く触ってもダメなパターンがある（後述）

ここまでのおさらい TL2は良いSTM（大事なことなのでry 実装上の選択肢はまだいくつもあり、TL2はその中の効率的な組み合わせの一つ 改良はまだいくつも出てくるけれど、またどこかで罠にぶち当たるのでは？ Isolationの問題

TL2の改良（まだあるのかよ） 以下のトランザクションを救いたい atomic { // Clock=10 loacl_x = ReadTx(x); } atomic { // clock=10 WriteTx(x, 10); } // clock->11 ←バージョン番号不一致でAbort() トランザクション開始時のクロックより新しい物を読んだからと言って、必ずしもそれがアボートするほど致命的とは限らない

TL2の改良（まだあるのかよ） Timebase Extension（Lazy Snapshot Algorithm） Tovaldら Time-based Transactional Memory with Scalable Time Bases (2007) Read-Setの中に矛盾さえ無ければ良いから、トランザクション開始時のタイムスタンプで辻褄が合わない時だってRead-SetをValidationし直せば助かる場合もある 特にさっきの場合、Read-Setが空なのでValidationは必ず成功する

Timebase Extensionの罠 以下のケースでバグる atomic { int tmp = ReadTx(x); if (ReadTx(x_published)) { // Use tmp } } x_published = false; x = 42; atomic { WriteTx(x_published, true); } ←TL2ならここでAbort()してくれた ←ここでゾンビするかも… これを Racy Publication Idiomと呼ぶ

次なる怪物：Privatization Idiom atomicがsynchronizedだったら、どう実行しても x == 100 にしかならないはず 左のトランザクションが、xを「自分だけのもの」に変えたときに出現する問題 atomic { WriteTx(x_is_private, true); } x = 100; atomic { if (!ReadTx(x_is_private)) { x = 200; } }

Privatization Idiom(Eager) Eager Versioningだと★の行で右トランザクションがx_is_sharedの競合に気付いて、undo_logでxを42に書き戻してしまう(100は無かった事になる) 左のトランザクションはxを「自分しかアクセスできない物」にしたつもりが他のトランザクションに邪魔された事になる atomic { WriteTx(x_is_private, true); } x = 100; atomic { if (!ReadTx(x_is_private)) { x = 200; // ← 実行した } // undo_log(x) == 42 } // ★

Privatization Idiom(Lazy) Lazyであっても、右のトランザクションがvalidationを終えた直後(redo-log書き込み前)に左のトランザクションとx=100が一気に完走すると、右のトランザクションのRedo-Logの書き込みが最後になってしまい、x=200になる たぶんTL2もヤバい 2 Phase Lockならx_is_privateのロックが食い止めてくれた atomic { WriteTx(x_is_private, true); } x = 100; atomic { if (!ReadTx(x_is_private)) { x = 200; // ← Redo-Log } } // ★ Data Race

そもそもトランザクショナルメモリとは？ Privatization Idiom? Racy Publication? STM設計者：そんな無茶な使い方しないでよ！ STMユーザ：synchronizedの代わりに使えるって言いだしたのはSTM側じゃん！ どっちの言い分も筋は通る トランザクショナルメモリが真に備えるべき機能について、本当は合意できていない モデリングが不十分

モデリングとは 実装がどのように動くかについてユーザに期待して貰いたい挙動の抽象的表現 つまり「STMは何を約束するのか」 どういう挙動をすると思って使えばいいのか このモデリングがしっかりしていれば、STMを使ったコードが異なる同モデルのSTM実装上でも動くはず！ポータブル！

Single Lock Atomicity（SLA） STM初期の神話 atomicのブロックはまるでプロセス全体で共通している単一のロックだと思って使えば良いよ、というSTMの保障 STMの宣伝文句に使われた 非常に明快で直観的 synchronizedをatomicに変えれば良いだけだ！ 実はTM過激推進派の欺瞞（大げさ） ロックを機械的に置き換えると非常に困るケースがいくつもある

Data Race Lockだったらtmp_xは42か10のどちらかになるはず(少なくともJavaは) STMだと、実装にも依るけれど鼻から悪魔が飛び出す Single Lockだと思えって言ったのは誰だ！ x = 42; atomic { WriteTx(x, 10); } int tmp_x = x;

Victorの例 左のスレッドが先に走ったら、右のスレッドも10秒待たされないとおかしい！ でも実際は右のスレッドは即座に完了する Single Lockだと思えって言ったのは誰だ！ Victor：Against lock-based semantics for transactional memory(2008) atomic { sleep(10); } atomic { WriteTx(x, 10); }

Empty Publication ロックならここでatomic{}の所でseq_cstなメモリフェンスが行われたはず STMだと古いdataを読んだぞ！ Single Lockだと思えって言ったのは(ry data = 1; atomic { /* 空 */ } ready = true; atomic { int tmp = data; if (ready) { // use data } } Vijayら Single global lock semantics in a weakly atomic STM(2008)

Single Lock Atomicity... 結構批判が多い 本当に単一のロックだと思えるSTMは作れなくないが実装の選択肢が相当減る けれど「ロックだと思え」というのは多くのユーザーから見て直観的なのも事実 落とし所は無いものか？

Lock based Modeling（DLA） Disjoint Lock Atomicity（DLA） Vijayら Single global lock semantics in a weakly atomic STM(2008) アクセス対象のデータに個別にロックがあると考える。トランザクション開始時にアクセス対象のデータのみをすべてロックする（というモデリング） アクセス対象のデータが被ったトランザクションだけが衝突すると思え（というモデリング） Empty Publicationイディオムは明白にノー（データに触らないトランザクションは他のトランザクションとぶつかれない）

Disjoint Lock Atomicity(DLA) DLAはユーザーから見たらわかりやすいかも知れないけれどSTM側の制約が辛い 例えば左のassertが通るならDLA下では必ずval == 1になってくれないと困る（readyのロック取ってるんでしょ？） でもTL2はそうならない！（Read-Lockを取らないため） ready = false; data = 1; atomic { test = ready; } assert(test == false); data = 0 atomic { int tmp = data; // tmp == 0 ready = true; val = tmp; // val == 0 }

Disjoint Lock Atomicity(DLA) 「read-lockはトランザクション開始時にすべて確保されるけれど、write-lockの獲得は実際の書き込みまで遅延するよ」と考えると下の例が動かないのは納得がいく このモデリングを「Asynmetric Lock Atomicity」と呼ぶ ready = false; data = 1; atomic { test = ready; } assert(test == false); data = 0 atomic { int tmp = data; // tmp == 0 ready = true; val = tmp; // val == 0 }

Encounter-time Lock Atomicity(ELA) 「read-lockもwrite-lockも獲得は実際の読み込み・書き込みまで遅延する」というモデリング Racy Publication Idiomは明白にサポートされない つまり下のようなコードを書いたらプログラマが悪い atomic { int tmp = ReadTx(x); if (ReadTx(x_published)) { // Use tmp } } x_published = false; x = 42; atomic { WriteTx(x_published, true); }

SLA->DLA->ALA->ELA SLAはプログラマから理解しやすいし使いやすい一方でSTM側には制約が強い STMの制約が強いとパフォーマンスも出しにくい DLA、ALA、ELAと変わるにつれてプログラマへの制約がかかる一方でSTMの実装の選択肢が増える プログラマの制約が強いとエンバグしやすくデバッグも辛くなる

ここまでのまとめ Publication / Privatizationの事を考えると結構頭が痛い サポートしようとすると遅くなる サポートを諦めてプログラマに「こういう物だ」とロックに例えて抽象化したモデルを定義しようとするとEncounter-time Lock Atomicityのようになる（割とbrain-damaging） ロックに例えようとするから不味い 発想からしてロックから離れよう Transactional Sequential Consistencyへ