www.slideboom.com

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をatomicに書き換えるだけ！
synchronized {
x += 100;
y -= 100;
}
atomic {
x += 100;
y -= 100;
}
• これでブロックに囲まれた処理全体が
All-or-Nothingになる
どう嬉しいのか？
• atomicで囲んだ部分は可能な限り並列して動
作する → マルチコアの性能を生かせる
atomic { atomic {
x += 100; z += 100;
y -= 100; w -= 100;
}
}
並列実行可能！
synchronized { synchronized {
x += 100;
z += 100;
y -= 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内部の設計の進化とは少し違う
スタート地点
• オブジェクト毎にロックを取り付ける
• トランザクションはいい感じにロックを取って
動いて欲しい
Javaで普通のロックを使うコードの例
class BankAccount {
...
synchronized public void add(int diff) {
credit += diff;
}
private int credit = 0;
}
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();
この隙間にもし「銀行の全
口座の残高の合計を算出
する処理」が挟まったら？
どんなロックの取り方がいいのか？
• さっきの例だけで言えばこういう挙動になって
欲しい
// 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の実行順と
同じ結果に辿り付くパターン
2PLが許す実行パターン
B→Aの実行順と
同じ結果に辿り付くパターン
2PLが許す実行パターン
2 Phase Lock
• 利点
– 競合等価直列化可能なスケジュールを動的に組
み立てる事ができる
• 欠点
– 競合等価直列化可能よりも広いスケジュールは
組み立てれない
• 競合等価直列化可能より広い直列化可能スケジュー
ルとしてビュー等価直列化可能などがある
– デッドロックは回避してくれない
2 Phase Lockを用いたSTM
• オブジェクトにアクセスするときはそのデータ
のロックを獲得する
– 既にロックを取っているなら何もしない
• コミットするまでロックを手放さない
• ある程度の時間ロックを獲得できなかったら
デッドロックと見なして作業内容を巻き戻す
– 作業を巻き戻せるように元のデータの複製をロッ
ク獲得時に作っておく
2 Phase Lockを用いたSTM
• STMから利用する全部のデータにロックを取
り付ける
X
X
Y
Y
Z
Z
2 Phase Lockを用いたSTM
• トランザクションはロックを獲得したらオブジェ
クトを手元に複製する(undo-logと言う)
X'
X
Y
X
Transaction1(以後T1)
Y'
Y
Z
2 Phase Lockを用いたSTM
• トランザクションが無事コミットまで辿りついた
らロックを開放してバックアップを消去する
X'
X
Y
X
Transaction1(以後T1)
Y'
Y
Z
2 Phase Lockを用いたSTM
• デッドロックした場合にはランダム時間の待
機後アボートする
X'
X
うぐぐ・・・
Y'
Y
X
Y
Z
x→yの順にア
クセスしたい
T1
y→xの順にア
クセスしたい
T2
2 Phase Lockを用いたSTM
• デッドロックした場合にはランダム時間の待
機後アボートする
X'
X
続行できる！
X
Y'
Y
Y
Z
x→yの順にア
クセスしたい
T1
Abort!
T2
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幅のメモリを用いた実装例は以下
unlock
Readerの数 Writer
1 0 read lock
n 0
unlock
0 0
1word
read lock
0 1
※状態遷移はすべてCompare And Swap命令で行う
Read-Write-Lockで本当にいいの？
• トランザクションって本当に読むだけで終わる
時と終わらない時がある
– 残高がマイナスの時に限り利息を取るとか
– つまりRead-LockからWrite-Lockへの昇格が必要
– Read-Lockを取っているスレッドのうち一つが
Upgrade可能となるようにプロトコルを設計しよう
– このUpgrade可能なロックを全部のオブジェクトに
取り付ければSTMから便利に使えるはずだ
Upgrade-Lock
• UpgradeをしたくなったらUpgrade待ちビットを立てて
他のすべてのReaderの離脱を待つ
• Upgrade待ちビットが立ったらそれ以上他のスレッド
はLockを取れない
read lock
unlock
1 0 0
n 0 0
upgrade
Upgrade待ち
0 0 0
1word
0 1 0
write lock
unlock
n 1 0
unlock * n
0 0 1
※状態遷移はすべて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フラグ
n 1
lock
ポインタの下位
1bitは必ず0
Pointer to desc
unlock
n+1 1
※状態遷移はすべてCompare And Swap命令で行う
Versioned Lockで何ができるか？
• Read Snapshotができる
• 値と一緒にバージョン番号を読み出しておく
X
Y
Z
v3: 120
v3: 120
比較
t
v2: 42
v5: 459
比較
比較
v2: 42
v5: 459
単調増加するはずのバージョン番号が変動していないので
この赤い期間の間にはデータは書き換えられていない
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キャッシュ
コヒーレント
L2キャッシュ
L1キャッシュ
キャッシュコヒーレントプロトコル
• IntelならMESIF、AMDならMOESIというプロトコル
• キャッシュラインが取る状態名の頭文字が由来
– Modified: メモリよりもキャッシュの方が新しい
– Exclusive: メモリとキャッシュが同一であり、他のコアはこの
キャッシュラインを持っていない
– Shared: メモリとキャッシュが同一であり、他のコアもこの
キャッシュラインを複製している
– Invalid: 正しいキャッシュを持っていないので読むな
– Owned: 俺がメモリだ(Shared可能なModified)
– Forward: Sharedのボス。アクセスする際にはこいつに伺え
キャッシュコヒーレントプロトコル
• MESI(F)プロトコルはModifiedなデータを他のコアが読み出す際
にメモリに書き戻す
• Sharedなデータを書き換える時にはInvalidation要求をブロード
キャストするためトラフィックが混む
書き換えた
Modified
共有を要求
（メモリアクセス発生）
Exclusive
新規に読み出した
Shared Invalidation要求が来た
他のコアから貰った
Invalid
キャッシュを汚す事はギルティ
• 他のスレッドから繰り返し読む値を書き換え続けると、キャッ
シュラインのステートはModifiedとSharedの間を行ったりき
たりすることになる。これは激しいトラフィックを起こす。
• 更にはModifiedからSharedになる度に下層のメモリに書き
込まなくてはならない
うぉー！
うぉー！
Core1
write
ぎゃー！！
L1キャッシュ
Invalidate
Core2
read
L1キャッシュ
write
L2キャッシュ
キャッシュを汚す事はギルティ
共有/localデータから
Readした場合の速度
localデータにWrite
した場合の速度
共有データにWrite
した場合の速度
http://www.1024cores.net/home/lock-free-algorithms/first-things-first から
まったくスケール
しない！！！！
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がどれだけ
遅いかを表したグラフ
ワークロードによってはざっくり10000倍遅い
出典：McRT-STM: A High Performance Software Transactional Memory System for a Multi-Core Runtime
ここまでのおさらい
• 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);
atomic {
WriteTx(x, 10);
WriteTx(y, 10);
}
int tmp_y = ReadTx(y);
while (tmp_x != tmp_y) {
// 無限ループ
}
}
ゾンビトランザクション問題
• トランザクションとしては既に致命傷を負って
るから死ぬしかないのに、検証するタイミング
まで辿り付けないから死んだ事すら自覚でき
ないゾンビ状態の事
• 無限ループの他にも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を読む
5
6
2
5
Global Clock
X'
X
Read
Abort...
5
3
5
Y'
Y
Write!
2 < 5 => OK
5 < 5 => NG!
最後にここに書き込
んだ時のGlobal Clock
Commit!
ゾンビ化しない
• 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) {
// 無限ループ
}
}
Abort!
atomic {
WriteTx(x, 10);
WriteTx(y, 10);
}
Lazy Versioning
• Eager Versioning(これまでの手法)だとWriteは
悲観的にロックを取ってしまうのでロック期間
が長くなりがち
• 各スレッドはコミットまでに「コミット時にやるこ
と」をローカルで整理して、コミット時だけロッ
クを取って一気に書けばロック期間が短くな
る！
Transactional Locking 2
• コミット直前までロックは取らない
– Readはバージョン番号をSnapshotして読む
• 書き込むデータは変わりにredo-logに保存
2
redo-log
3
Y'
2
X'
3
2
X
Y
Z
Transactional Locking 2
• コミット時に各オブジェクトのロックを取る
• redo-logとバージョンを比較
• 問題なければGlobal Clockを添えて書き込み実行
2
5
redo-log
3
Y' ロック！
2
X'
3
5
2
X
Y
Z
パフォーマンス
Fast
ここまでのおさらい
• パフォーマンスを得るために2 Phase Lockから
足を踏み外した
• するとゾンビトランザクション問題に襲われた
• しかしGlobal Clockを備えたTL2によって華麗
に解決
• TL2はまだ改良できるのではないか？
– TL2の改良について追っていく
Bloom Filter
• Redo-Logの管理に使う
• Bloom Filterは集合にデータが含まれている
かを高速に検知するデータ構造
あ
い
う
え
お
お
い
あ
え
う ←あいうえお検知器
あ
か
い
ふ
く
い
お
あ
え
う
か
い
お
あ
え
う
い
お
あ
え
う
ふ
い
お
あ
え
う
い
お
あ
え
う
く
すっぽり覆われた物は
「あいうえお」のどれか
である"確率が高い"
Bloom Filter
• 既にredo-logに書いてる物に上書きしたい時はredo-log内で
上書きする必要がある
– 値に書き込む度に「これってredo-logにもう入れたっけ？」と検索する
必要がある
– 検索の前さばきにbloom filterが便利
2
redo-log
2
Bloom Filter
X
YZ
Z
3
Y
2
X'
3
2
X
Y
Z
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
• コミット時にオブジェクト毎のバージョン番号
に加えてセグメントのバージョン番号も上書き
しておく
2 3 5 1 3 4 3 1 3 4 4 6 2 1 4 5 6 7 8 9 6 3 2 4 4 6
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
5
6
7
3 5 1 3 4 1 4 5 6
B C H I J N O P Q
のバージョンが変わってないか
チェックしたいなー
Commit中のトランザクション
9
6
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））
Fast
出典：Yossiら Anatomy of scalable software transactional memory（2009）
TL2の改良（まだまだある）
• TL2C: Global Clockの代わりにVector Clockを
使えば大丈夫！
(Hillelら Maintaining Consistent Transactional
States without a Global Clock(2008))
• 各オブジェクトに[コミットしたスレッドID, その
時のスレッドのClock]をバージョンとして付与
• 全スレッドが自分以外の全スレッドの「最後に
観測したクロック」を記憶
– そこと食い違ったらAbortしてクロックを上書きして
再実行
Fast
出典： Hillelら Maintaining Consistent Transactional States without a Global Clock(2008)
ここまでのおさらい
• TL2は良いSTM
• そのためTL2をベースにした改良版がいくつも
出てきて研究が進展した
• STMの実装を分類学的に見るとどうなるのだ
ろうか？
STMの実装上の選択肢
• 直交する複数の軸がある（直交しない事もある）
• これらで実存する実装を（いくらか）分類する事ができる
Concurrency
Control
Pessimistic
Optimistic
Vesioning
Eager
Lazy
Conflict
Detection
Eager
Lazy
Granularity
Object
Word
Nest
Isolation
Flatten / Closed / Open
Weak
Strong
Eager Versioning と Lazy Versioning
Read
X
Read
Write
Eager Versioning Y
Y'
Z
TL2はこっち
Lazy Versioning
X
Y
Z
Write
Z'
Read
Commit
Read
Write
Y'
Z'
Y'Write
Z'
Lazy Versioning
• 利点
– ロック保持期間が短くなるのでスケールしやすい
– コミット中のスレッド同士しか競合しないのでLiveLockが発生しえない
– 複数ロックがある場合でもロックを取りに行く時点
で全ての欲しいロックが分かっているのでロック
の獲得順序を全スレッドで統一できる
• つまりデッドロックを簡単に回避できる
– Abortするトランザクションが共有メモリを汚さない
– Abort時にはログを消去するだけで済むので高速
Lazy Versioning
• 欠点
– コミットする際にredo-logの内容を全部本来の場所
に書き込む必要がある
• redo-logを作成するコストを考えると二度手間
– トランザクションが同じ場所に何度も書き込む手続
きの場合、redo-log内を何度も検索する必要がある
• 遅い
– TinySTMはこれを避けるため、Eager Versioningを
使っている
Eager? Lazy?
• どちらが良いかは場合による
• データベース界隈でもどちらかが決定的に良
いという事はない様子？
STMの実装上の選択肢
• 直交する複数の軸がある（直交しない事もある）
• これらで実存する実装を（いくらか）分類する事ができる
Concurrency
Control
Pessimistic
Optimistic
Vesioning
Eager
Lazy
Conflict
Detection
Eager
Lazy
Granularity
Object
Word
Nest
Isolation
Flatten / Closed / Open
Weak
Strong
Conflict Detection
• いつ書き換えるか（Versioning）の他に、いつ
衝突を検知するか（Conflict Detection）にも直
交する実装上の選択肢がある
– 最初にアクセスする時に検知する？(Eager)
– 実行中何度も検知する？(Incremental Validation)
– コミットする瞬間まで検知しない？(Lazy)
• TL2はLazy Conflict Detection
• 最初のTransactional MemoryはEager Conflict
Detection
Lazy Conflict Detection
• コミット時まで衝突を検知しようとしない
– LazyなVersioningと組み合わせる事が多い
• 利点
– チェックののべ回数が少ない
– 必要のないリトライを行わないのでスループット
が出やすい
• 欠点
– コミットまで走り切らないと間違いに気付けない
いつ衝突を検知するか？
atomic {
atomic {
WriteTx(x, 1);
WriteTx(x, 1);
// 何かすごく重い処理
// 何かすごく重い処理
if (prob(p)) {
if (prob(p)) {
Abort();
Abort();
}
}
}
}
確率pでTrueになる
• Eagerな検知だと初めのWriteが衝突しあう
– 適切に片方のトランザクションだけ走るように調停
する必要がある
– pが低い(滅多にアボートしない)の時に効率が良い
いつ衝突を検知するか？
atomic {
atomic {
WriteTx(x, 1);
WriteTx(x, 1);
// 何かすごく重い処理
// 何かすごく重い処理
if (prob(p)) {
if (prob(p)) {
Abort();
Abort();
}
}
}
}
確率pでTrueになる
• Lazyな検知だとコミットまで衝突しない
– 重い処理が複数のスレッドで走ってしまう
– pが高い(よくアボートする)時にどれかが早くコミット
に辿り着ける見込みがある
• 下手な鉄砲数撃ちゃなんとやら
いつ衝突を検知するか？
atomic {
atomic {
WriteTx(x, 1);
WriteTx(x, 1);
// 何かすごく重い処理
// 何かすごく重い処理
if (prob(p)) {
if (prob(p)) {
Abort();
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)
STMの実装上の選択肢
• 直交する複数の軸がある（直交しない事もある）
• これらで実存する実装を（いくらか）分類する事ができる
Concurrency
Control
Pessimistic
Optimistic
Vesioning
Eager
Lazy
Conflict
Detection
Eager
Lazy
Granularity
Object
Word
Nest
Isolation
Flatten / Closed / Open
Weak
Strong
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の実装上の選択肢
• 直交する複数の軸がある（直交しない事もある）
• これらで実存する実装を（いくらか）分類する事ができる
Concurrency
Control
Pessimistic
Optimistic
Vesioning
Eager
Lazy
Conflict
Detection
Eager
Lazy
Granularity
Object
Word
Nest
Isolation
Flatten / Closed / Open
Weak
Strong
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の実装上の選択肢
• 直交する複数の軸がある（直交しない事もある）
• これらで実存する実装を（いくらか）分類する事ができる
Concurrency
Control
Pessimistic
Optimistic
Vesioning
Eager
Lazy
Conflict
Detection
Eager
Lazy
Granularity
Object
Word
Nest
Isolation
Flatten / Closed / Open
Weak
Strong
Isolation
• トランザクション中で触るデータに、トランザク
ション外から触ったらどうなるのか？
– ロックの場合であっても迂闊に触ったら壊れるの
は一緒
– でもロックなら注意深く触れば大丈夫なパターン
はいくつもある
– STMではどんなに注意深く触ってもダメなパター
ンがある（後述）
ここまでのおさらい
• TL2は良いSTM（大事なことなのでry
• 実装上の選択肢はまだいくつもあり、TL2はそ
の中の効率的な組み合わせの一つ
• 改良はまだいくつも出てくるけれど、またどこ
かで罠にぶち当たるのでは？
– Isolationの問題
TL2の改良（まだあるのかよ）
• 以下のトランザクションを救いたい
atomic { // Clock=10
atomic { // clock=10
WriteTx(x, 10);
} // clock->11
loacl_x = ReadTx(x); ←バージョン番号不一致で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);
x_published = false;
x = 42;
atomic {
WriteTx(x_published, true);
}
if (ReadTx(x_published)) { ←TL2ならここでAbort()してくれた
// Use tmp ←ここでゾンビするかも…
}
}
これを Racy Publication Idiomと呼ぶ
次なる怪物：Privatization Idiom
atomic {
WriteTx(x_is_private, true);
}
x = 100;
atomic {
if (!ReadTx(x_is_private)) {
x = 200;
}
}
• atomicがsynchronizedだったら、どう実行して
も x == 100 にしかならないはず
• 左のトランザクションが、xを「自分だけのも
の」に変えたときに出現する問題
Privatization Idiom(Eager)
atomic {
if (!ReadTx(x_is_private)) {
x = 200; // ← 実行した
} // undo_log(x) == 42
atomic {
WriteTx(x_is_private, true);
}
x = 100;
} // ★
• Eager Versioningだと★の行で右トランザクションが
x_is_sharedの競合に気付いて、undo_logでxを42に
書き戻してしまう(100は無かった事になる)
• 左のトランザクションはxを「自分しかアクセスできな
い物」にしたつもりが他のトランザクションに邪魔さ
れた事になる
Privatization Idiom(Lazy)
atomic {
WriteTx(x_is_private, true);
}
x = 100;
atomic {
if (!ReadTx(x_is_private)) {
x = 200; // ← Redo-Log
}
} // ★
• Lazyであっても、右のトランザクションがvalidationを
終えた直後(redo-log書き込み前)に左のトランザク
ションとx=100が一気に完走すると、右のトランザク
ションのRedo-Logの書き込みが最後になってしまい、
x=200になる
– たぶんTL2もヤバい
– 2 Phase Lockならx_is_privateのロックが食い止めてくれた
そもそもトランザクショナルメモリとは？
• Privatization Idiom? Racy Publication?
– STM設計者：そんな無茶な使い方しないでよ！
– STMユーザ：synchronizedの代わりに使えるって言
いだしたのはSTM側じゃん！
– どっちの言い分も筋は通る
• トランザクショナルメモリが真に備えるべき機能
について、本当は合意できていない
– モデリングが不十分
モデリングとは
• 実装がどのように動くかについてユーザに
期待して貰いたい挙動の抽象的表現
– つまり「STMは何を約束するのか」
– どういう挙動をすると思って使えばいいのか
• このモデリングがしっかりしていれば、STMを
使ったコードが異なる同モデルのSTM実装
上でも動くはず！ポータブル！
Single Lock Atomicity（SLA）
• STM初期の神話
• atomicのブロックはまるでプロセス全体で共
通している単一のロックだと思って使えば良
いよ、というSTMの保障
• STMの宣伝文句に使われた
• 非常に明快で直観的
– synchronizedをatomicに変えれば良いだけだ！
• 実はTM過激推進派の欺瞞（大げさ）
– ロックを機械的に置き換えると非常に困るケース
がいくつもある
Data Race
x = 42;
atomic {
WriteTx(x, 10);
}
int tmp_x = x;
• Lockだったらtmp_xは42か10のどちらかにな
るはず(少なくともJavaは)
• STMだと、実装にも依るけれど鼻から悪魔が
飛び出す
– Single Lockだと思えって言ったのは誰だ！
Victorの例
atomic {
sleep(10);
}
atomic {
WriteTx(x, 10);
}
• 左のスレッドが先に走ったら、右のスレッドも
10秒待たされないとおかしい！
– でも実際は右のスレッドは即座に完了する
– Single Lockだと思えって言ったのは誰だ！
Victor：Against lock-based semantics for transactional memory(2008)
Empty Publication
atomic {
int tmp = data;
data = 1;
atomic { /* 空 */ }
ready = true;
if (ready) {
// use data
}
}
• ロックならここでatomic{}の所でseq_cstなメモ
リフェンスが行われたはず
• STMだと古いdataを読んだぞ！
– Single Lockだと思えって言ったのは(ry
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 = 0
atomic {
int tmp = data; // tmp == 0
data = 1;
atomic {
test = ready;
}
assert(test == false);
ready = true;
val = tmp; // val == 0
}
Disjoint Lock Atomicity(DLA)
• 「read-lockはトランザクション開始時にすべて確保されるけれ
ど、write-lockの獲得は実際の書き込みまで遅延するよ」と考
えると下の例が動かないのは納得がいく
• このモデリングを「Asynmetric Lock Atomicity」と呼ぶ
ready = false;
data = 0
atomic {
int tmp = data; // tmp == 0
data = 1;
atomic {
test = ready;
}
assert(test == false);
ready = true;
val = tmp; // val == 0
}
Encounter-time Lock Atomicity(ELA)
• 「read-lockもwrite-lockも獲得は実際の読み込み・書
き込みまで遅延する」というモデリング
• Racy Publication Idiomは明白にサポートされない
– つまり下のようなコードを書いたらプログラマが悪い
atomic {
int tmp = ReadTx(x);
x_published = false;
x = 42;
atomic {
WriteTx(x_published, true);
}
if (ReadTx(x_published)) {
// Use tmp
}
}
SLA->DLA->ALA->ELA
• SLAはプログラマから理解しやすいし使いや
すい一方でSTM側には制約が強い
– STMの制約が強いとパフォーマンスも出しにくい
• DLA、ALA、ELAと変わるにつれてプログラマへ
の制約がかかる一方でSTMの実装の選択肢
が増える
– プログラマの制約が強いとエンバグしやすくデ
バッグも辛くなる
ここまでのまとめ
• Publication / Privatizationの事を考えると結構頭が
痛い
• サポートしようとすると遅くなる
• サポートを諦めてプログラマに「こういう物だ」とロッ
クに例えて抽象化したモデルを定義しようとすると
Encounter-time Lock Atomicityのようになる（割と
brain-damaging）
• ロックに例えようとするから不味い
– 発想からしてロックから離れよう
– Transactional Sequential Consistencyへ

Download Report