トランザクション入門

トランザクション入門 2016 10/28 グランパーク田町 Tech Lunch @kumagi

並行処理難しい T本のスレッドがそれぞれNステップの処理を行う場合NTの状態を取りうる 。（状態爆発） 更にはシングルスレッド性能を上げるためにIntelではPentium Pro世代から Out-of-Order実行が行われる。（プログラムは書いた通りにすら動いてい ない） 同じプログラムを２度実行しても、全く同じ並行実行パターンをなぞる確 率は絶望的。（非決定的動作）

コンセプト：Atomic Object オブジェクト指向プログラミングが話題だった頃に提唱されたコンセプト ・操作を示すメッセージを受け取る「オブジェクト」が存在する。 ・個々のメッセージは「不可分」に実行される。 オブジェクトはQueueだったり配列だったり任意のクラスのインスタンスだった りする オブジェクト単位では何らかの論理的な逐次順序でメッセージを処理するだけ このオブジェクトでシステムの登場人物を整理すればシステムを作りやすくなる のでは？

Atomic Objectの実装：単一オブジェクトの場合 Lockされた期間中の一瞬で処理が行われたと想像すれば理解しやすい その（想像上の）一瞬で処理が行われた瞬間の事をLinearization Pointと呼ぶ T1 処理A 処理X T2 Object 処理B T1の処理A 青線は論理的な時間軸 T2の処理X T1の処理B

Linearizability(線形化可能性) 「ある操作の開始から完了までの間のどこかの一瞬で処理が終わった」と定義で きる性質の事をLinearizabilityと呼ぶ 普通の排他Lockを使っている場合、自然にこの性質を満たす。 で、そのLinearization Pointって具体的にいつ？→Lock期間内ならどこでもいい T1 Object この範囲内ならどこでもいい

Composability(合成可能性) 「ある性質を持った物を組み合わせた際、組み合わせた後も同一の性質を持つ」 という性質を「Composability」と言い、Lockから得られるLinearizabilityの Composabilityは確認されている。 複数のオブジェクトを触る場合であっても、全てのロックが取れてる期間内なら どこにでもLinearization Pointをマッピングして良い。 Object1&2に対する操作 T1 Object1 Object2 Object1&2 この範囲内ならどこでもいい

2 Phase Lock(2PL) LockのComposabilityを活用して行けば、いくつのオブジェクトであっても Linearization Pointが作れる期間が得られるはず。 そのために、ロック確保は「獲得を続ける成長相」と「解放を続ける縮退相」の 2つだけからなるようしようというプロトコルが 2 Phase Lock Object1&2&3,,,nに対する操作 T1 Object1 Object2 Object3 Objectn Object1&2,,,n 成長相 縮退相 この範囲内ならどこでもいい

ここまでのまとめ 並行世界におけるオブジェクトに対する「処理」は 論理的な時間軸のどこか一瞬にマッピングして整理する Lockを使っている場合、Lock期間のどこにでも処理をマッピングでき る 2 Phase Lockはそれを拡張したもの

トランザクションへの応用 2PLを使えばトランザクションにおける並行制御の問題は（論理的には）解決で きる 全部のロックを取った状態でディスクにログを書き出せば最低限のACIDは満たせ る T1 Object1 Object2 Object3 Objectn Disk Write Object1&2,,,n

トランザクションへの応用 2PLを使えばトランザクションにおける並行制御の問題は（論理的には）解決で きる 全部のロックを取った状態でディスクにログを書き出せば最低限のACIDは満たせ る だが遅い

トランザクションへの応用 ページの中身を更新する際、ページがディスクに書き戻されるより先にログが到 達していないと行けない && 1つのトランザクションが更新するデータ量が必ずし もメモリに収まるとは限らない → トランザクションは進行と同時にWALを書 くしかない と、状況は悪化する。ロック獲得期間は伸びるばかり T1 Object1 Object2 Object3 Objectn Disk Write Object1&2,,,n

トランザクションへの応用 ANSI「2PLを最強として、そこから緩めていく方向でIsolationを諦めて行けば性 能と実用性のバランスが取れるんじゃない？」 と、本気で言ったかは知らないがANSIの提唱する4つの分離レベルからはロックの使い方が透 けて見える SERIALIZABLE: 2PLとGap Lock(レコードの隙間に対するロック)を使う REPEATABLE READ: 2PLを使う READ COMMITTED: Read Lockを取らない READ UNCOMMITTED: Write Lockすら取らない もちろんANSI自体は実装の詳細を指定していないのでこれらの記述は仕様ではない

ちょっと脱線： SNAPSHOT ISOLATION 「全てのトランザクションは、開始した瞬間の一貫したスナップショットをトラ ンザクション中ずっと観測する。書き込み同士が衝突した場合はAbortする」 裏ではMulti Versioning Concurrency Control(MVCC)とTimestampで頑張っている 。 ❖ 値を書き込む際は別のバージョンを作成して脇に置く事で古いデータを読む 事になる他のトランザクションの邪魔をしない ❖ Read Lockを取る必要が無いので読み出しが大半を占めるワークロードで多 大な高速化を実現 ❖ 特定の値を読んで良いかどうかはトランザクション開始時に獲得したタイム スタンプで判断するのでPhantom Readは抑制できる

ちょっと脱線： SNAPSHOT ISOLATION 2つのAnomaly(Serialize不可能なHistory生成)が起きる OracleDBのSERIALIZABLE設定はこの問題が起きる事で有名 参考: https://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:3233191441609 Oracle「Phantom Readが起きなきゃSERIALIZABLEってANSIが言ってるし、うち の実装はPhantom Read起きないじゃん？」 Write Skew Anomaly x=y+1した い y=x+1した い x 0 y 0 T1 T2 y=0 x=0 Read Only Anomaly x←1 y←1 x+y==0ならy- T1 x=0 y=0 =10 T2 1 1 T1, T2どっちが先に終わったか不 明 y←-10 x=0 x←10 x+=10 y=0 x=10 T3 x+yが知りたい 10 x 0 -10 y 0 結果で見ればT2が最初に終わっている がT3はT1の方が早かったと主張して矛 盾

• https://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:3233191441609

ここまでのまとめ 2 Phase Lockでトランザクションは実装可能だが現実的な速度は出ない SNAPSHOT ISOLATIONのような「ACIDを一部諦めた」モデルが 一般に広く使われている OracleのSERIALIZABLEはSNAPSHOT ISOLATION

Atomic Snapshot 問題「ランダムなタイミングで増加する2つのカウンターのどこか一瞬の状態を 獲得せよ。ただし、一度に読めるカウンターは1つである」 1つ読んで、2つめを読むタイミングで1つめの値が変わってる可能性がある 2つを2回読んで、値が一致していればその期間ずっとその値だったと言える T1 A B 0 1 0 1 2 2 3 3 4 この範囲内ならずっとA=2, B=3と断言できる 4 5

Optimistic Concurrency Control(OCC) コミット時までロックを取らずに進行し、Commit時にValidationを行う戦略 コミット時にロックを取る→Readをやり直す という順序で操作を行う事によっ て、Read側のSnapshotの瞬間とWrite側の2PLのLinearization pointを重ねるのがポ イント ReadされるデータのSnapshotが取れるように、全てのオブジェクトに単調増加す T1 るバージョン番号を取り付ける必要がある Object1 Object2 Object3 Objectn Object1&2,,n この範囲内でトランザクションの全操作が起きた事にできる

マルチコアの時代到来 コア数が増える程にコヒーレンスが重くなる(Universal Scalability Law) 縦軸：性能 横軸：システム負荷(≒使用プロセッサ数) N: プロセッサ数 α: 衝突コスト係数 β: コヒーレントコスト係数 平たく言うと、N倍の資源を用意すればN倍速 になるかと思いきや、衝突のせいでそう速くな らないし、コヒーレントのコストが2乗で効い てくるので返って遅くなる事すらある http://www.perfdynamics.com/Manifesto/USLscalability.html

• http://www.perfdynamics.com/Manifesto/USLscalability.html

最近のDB研究での動向 メインメモリに全データが入るという前提が許されるなら、ページの書き戻し自 体が必要ないのでWAL(ページの書き戻しより先にUndo-Logを書く)という制約が 要らなくなる マルチコアを活かしてトランザクションを高速化させる場合、キャッシュコヒー レントに足を引っ張られにくいOCCが注目を集めている。(Snapshot Readはキャ ッシュを一切汚さない場合すらある) In-Memory + マルチコア + 楽観的並行制御 の組み合わせがスイートスポット

Group Commit 個々のトランザクションごとにCommit Logを書くのでは無く、複数のトランザクションから出てきたログを1つにまとめて 書き込む技法 各トランザクションは自分のCommit Logがまとめて書き込まれるのを見届けるまでクライアントに完了を報告しないの で、クライアントから見た振る舞いは一緒 ディスク書き込みはシーケンシャルアクセスの方が高速なので、少ないIO数の中に大量のコミット情報を投入すること は大きな高速化に寄与する SSDであっても結構意義があると手元のベンチマークは言ってる commit 最初にこれを実装したのはIBMのIMS FastPath。大抵の人気DBは実装してるはず。 Unlock commit Disk Write Unlock Logger Disk Write

Early Lock Release Group Commit等で、何をCommitするかという内容を決めてディスクに書き出す順序まで確定(precommit)した後なら、ロックを手放してしまってもトランザクションの性質は変わらないよという提案 仮に手放したロックを握った別のトランザクションがやってきても、手放した側のトランザクションを追い抜く事はな い（ディスクに書き出す順序は既に確定したので） ディスク動作を待つ間にデータのロックを手放して良いので、より多くのトランザクションがロックを握って進行でき るようになる 詳細な証明は結構ゴツいので論文参照 commit Unlock commit Unlock 実地でどの程度使われてるかは未調査。PostgreSQLは未実装らしい。 Disk Write Disk Write

Silo マルチコアの為に更にOCCを突き詰めて並列度を高めるコミットプロトコル 1. Epochという40ミリ秒ごとに増える数字を全トランザクションに与えてIDの上位ビットにする 2. 各トランザクションは自分が観測した値の全バージョンより1大きいIDをコミット時に算出する 3. メモリ更新と同時にUnlockして構わなくなった 4. 同一Epochなログが全て揃わないとユーザに完了を報告しない Unlock commit Unlock 5.commit リカバリの際は同一Epochのトランザクションが全て揃っていない限り無効なログとして棄却する Epoch単位でログ集合を緩く共有するので、ログの細かい順序も入れ替わっても問題なくなり並列化もで きる Disk Write Disk Write

OCCの偽陽性 OCCはコミット時まで衝突を検知しないのでAbort時に無駄になるCPU資源が多 い 更には本来AbortさせるべきでないトランザクションをAbortさせてしまう x+y==0ならy- T1 x=0 y=0 =10 T2 x+=10 x 0 0 y y←-10 x=10 x=0 x←10 Xが変わったのでAbort Commit成功 10 -10 本来これらのトランザクションは、T1→T2の順で実行した事にして 両方Commitしてよい

TicToc コミットするとき、読んだデータに対してRead-Timestampを振っていってコミッ ト時に無矛盾なCommit-Timestampを決めれば偽陽性を減らす事ができる ReadSet Rt:3 Wt:2 ReadWriteSet Rt:1 Wt:1 x+y==0ならy- T1 x=0 y=0 =10 T2 x+=10 x y Rt:3 0 Wt:2 Rt:1 0 Wt:1 y←-10 ts:2でOK x=0 x←10 ts:4でOK Rt:4 Wt:4 Commit成功 Commit成功 10 Rt:2 Wt:2 -10 コミットのタイムスタンプは「ReadSet内で最大のWTS」か「WriteSetの 最大のRTS+1」のうち大きい方を採用する。T1は「max(2, 1)」と「 max(1)+1」で比較して2を採用する。これでより多くのパターンでCommit を許す事ができる。 …ただしログの順序についてはFuture Workとして詳細は書いてない。

TicToc Siloを超える性能が出ているらしい TicToc Silo 出典: Xiangyao Yuら TicToc: Time Traveling Optimistic Concurrency Control

TicTocの問題点 ReadするだけのデータであってもReadTimeStampを更新しないといけない。 …キャッシュを汚さないのがOCCの利点じゃなかったっけ？ Read-Onlyなワークロードだと負けてるじゃないですか！ 出典: Xiangyao Yuら TicToc: Time Traveling Optimistic Concurrency Control

Mostly-Optimistic Concurrency Control(MOCC) 最近読んでる論文（まだ読みかけ） 基本的にはOCC Validation失敗でAbortするときに「ここの値は良く更新される」という情報を Temperatureとして書き込む 閾値よりTemperatureが高い値をReadする際はLockを取りながらトランザクシ ョンを続行する 自分がさっき触ったのにValidationが合わなかったデータもLockを取る そのまま走らせるとデッドロックしかねないのでロック順序を壊しそうなタイ ミングでアンロックして順に再獲得する

Mostly-Optimistic Concurrency Control(MOCC) OCCが苦手なWriteメインのワークロードでも性能が出ている。 出典： Tianzheng Wangら Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores

まとめ マルチコア＆インメモリ時代ではOCCが美味しいという認識はあるも のの アボートのコストが高くなりがちなOCCに対して程よいバランスで 並行制御できるアルゴリズムはまだ試行錯誤の段階