More Related Content
What's hot (20)
Viewers also liked (12)
Similar to トランザクション入門 (6)
トランザクション入門
- 1. トランザクション入門 2016 10/28 グランパーク田町 Tech Lunch @kumagi
- 4. Atomic Objectの実装：単一オブジェクトの場合 Lockされた期間中の一瞬で処理が行われたと想像すれば理解しやすい その（想像上の）一瞬で処理が行われた瞬間の事をLinearization Pointと呼ぶ T1 T2 Object T1の処理A T2の処理X T1の処理B 処理A 処理X 処理B 青線は論理的な時間軸
- 7. 2 Phase Lock(2PL) LockのComposabilityを活用して行けば、いくつのオブジェクトであっても Linearization Pointが作れる期間が得られるはず。 そのために、ロック確保は「獲得を続ける成長相」と「解放を続ける縮退相」の 2つだけからなるようしようというプロトコルが 2 Phase Lock T1 Object1 Object1&2&3,,,nに対する操作 Object2 Object1&2,,,n この範囲内ならどこでもいい Object3 Objectn 成長相 縮退相
- 10. トランザクションへの応用 2PLを使えばトランザクションにおける並行制御の問題は（論理的には）解決で きる 全部のロックを取った状態でディスクにログを書き出せば最低限のACIDは満たせ る だが遅い
- 11. T1 Object1 Object2 Object1&2,,,n Object3 Objectn トランザクションへの応用 ページの中身を更新する際、ページがディスクに書き戻されるより先にログが到 達していないと行けない && 1つのトランザクションが更新するデータ量が必ずし もメモリに収まるとは限らない → トランザクションは進行と同時にWALを書 くしかない と、状況は悪化する。ロック獲得期間は伸びるばかり Disk Write
- 12. トランザクションへの応用 ANSI「2PLを最強として、そこから緩めていく方向でIsolationを諦めて行けば性 能と実用性のバランスが取れるんじゃない？」 と、本気で言ったかは知らないがANSIの提唱する4つの分離レベルからはロックの使い方が透 けて見える SERIALIZABLE: 2PLとGap Lock(レコードの隙間に対するロック)を使う REPEATABLE READ: 2PLを使う READ COMMITTED: Read Lockを取らない READ UNCOMMITTED: Write Lockすら取らない もちろんANSI自体は実装の詳細を指定していないのでこれらの記述は仕様ではない
- 13. ちょっと脱線： SNAPSHOT ISOLATION 「全てのトランザクションは、開始した瞬間の一貫したスナップショットをトラ ンザクション中ずっと観測する。書き込み同士が衝突した場合はAbortする」 裏ではMulti Versioning Concurrency Control(MVCC)とTimestampで頑張っている 。 ❖値を書き込む際は別のバージョンを作成して脇に置く事で古いデータを読む 事になる他のトランザクションの邪魔をしない ❖Read Lockを取る必要が無いので読み出しが大半を占めるワークロードで多 大な高速化を実現 ❖特定の値を読んで良いかどうかはトランザクション開始時に獲得したタイム スタンプで判断するのでPhantom Readは抑制できる
- 14. ちょっと脱線： 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起きないじゃん？」 x=y+1した いy=x+1した い y x 0 0 y←1 y=0 x=0 x←1 1 1 Write Skew Anomaly x+y==0ならy- =10 x+=10 y x 0 x←10 0 x=0 x=0 y←-10 10 -10 Read Only Anomaly x+yが知りたい y=0 y=0 x=10 T1 T2 T1 T2 T3 T1, T2どっちが先に終わったか不 明 結果で見ればT2が最初に終わっている がT3はT1の方が早かったと主張して矛 盾
- 15. ここまでのまとめ 2 Phase Lockでトランザクションは実装可能だが現実的な速度は出ない SNAPSHOT ISOLATIONのような「ACIDを一部諦めた」モデルが 一般に広く使われている OracleのSERIALIZABLEはSNAPSHOT ISOLATION
- 17. Optimistic Concurrency Control(OCC) コミット時までロックを取らずに進行し、Commit時にValidationを行う戦略 コミット時にロックを取る→Readをやり直す という順序で操作を行う事によっ て、Read側のSnapshotの瞬間とWrite側の2PLのLinearization pointを重ねるのがポ イント ReadされるデータのSnapshotが取れるように、全てのオブジェクトに単調増加す るバージョン番号を取り付ける必要があるT1 Object1 Object2 Object1&2,,n Object3 Objectn この範囲内でトランザクションの全操作が起きた事にできる
- 18. マルチコアの時代到来 コア数が増える程にコヒーレンスが重くなる(Universal Scalability Law) 縦軸：性能 横軸：システム負荷(≒使用プロセッサ数) N: プロセッサ数 α: 衝突コスト係数 β: コヒーレントコスト係数 平たく言うと、N倍の資源を用意すればN倍速 になるかと思いきや、衝突のせいでそう速くな らないし、コヒーレントのコストが2乗で効い てくるので返って遅くなる事すらある http://www.perfdynamics.com/Manifesto/USLscalability.html
- 19. 最近のDB研究での動向 メインメモリに全データが入るという前提が許されるなら、ページの書き戻し自 体が必要ないのでWAL(ページの書き戻しより先にUndo-Logを書く)という制約が 要らなくなる マルチコアを活かしてトランザクションを高速化させる場合、キャッシュコヒー レントに足を引っ張られにくいOCCが注目を集めている。(Snapshot Readはキャ ッシュを一切汚さない場合すらある) In-Memory + マルチコア + 楽観的並行制御 の組み合わせがスイートスポット
- 20. Group Commit 個々のトランザクションごとにCommit Logを書くのでは無く、複数のトランザクションから出てきたログを1つにまとめて 書き込む技法 各トランザクションは自分のCommit Logがまとめて書き込まれるのを見届けるまでクライアントに完了を報告しないの で、クライアントから見た振る舞いは一緒 ディスク書き込みはシーケンシャルアクセスの方が高速なので、少ないIO数の中に大量のコミット情報を投入すること は大きな高速化に寄与する SSDであっても結構意義があると手元のベンチマークは言ってる 最初にこれを実装したのはIBMのIMS FastPath。大抵の人気DBは実装してるはず。 Unlockcommit Disk Write Unlockcommit Disk Write Logger
- 21. Early Lock Release Group Commit等で、何をCommitするかという内容を決めてディスクに書き出す順序まで確定(pre- commit)した後なら、ロックを手放してしまってもトランザクションの性質は変わらないよという提案 仮に手放したロックを握った別のトランザクションがやってきても、手放した側のトランザクションを追い抜く事はな い（ディスクに書き出す順序は既に確定したので） ディスク動作を待つ間にデータのロックを手放して良いので、より多くのトランザクションがロックを握って進行でき るようになる 詳細な証明は結構ゴツいので論文参照 実地でどの程度使われてるかは未調査。PostgreSQLは未実装らしい。 Unlockcommit Disk Write Unlockcommit Disk Write
- 22. Silo マルチコアの為に更にOCCを突き詰めて並列度を高めるコミットプロトコル 1. Epochという40ミリ秒ごとに増える数字を全トランザクションに与えてIDの上位ビットにする 2. 各トランザクションは自分が観測した値の全バージョンより1大きいIDをコミット時に算出する 3. メモリ更新と同時にUnlockして構わなくなった 4. 同一Epochなログが全て揃わないとユーザに完了を報告しない 5. リカバリの際は同一Epochのトランザクションが全て揃っていない限り無効なログとして棄却する Epoch単位でログ集合を緩く共有するので、ログの細かい順序も入れ替わっても問題なくなり並列化もで きる Unlockcommit Disk Write Unlockcommit Disk Write
- 24. TicToc コミットするとき、読んだデータに対してRead-Timestampを振っていってコミッ ト時に無矛盾なCommit-Timestampを決めれば偽陽性を減らす事ができる x+y==0ならy- =10 x+=10 y x 0 x←10 0 x=0 x=0 y←-10 10 -10 y=0T1 T2 Commit成功 Commit成功 Rt:3 Wt:2 Rt:4 Wt:4 Rt:2 Wt:2 Rt:1 Wt:1 ts:2でOK Rt:3 Wt:2 コミットのタイムスタンプは「ReadSet内で最大のWTS」か「WriteSetの 最大のRTS+1」のうち大きい方を採用する。T1は「max(2, 1)」と「 max(1)+1」で比較して2を採用する。これでより多くのパターンでCommit を許す事ができる。 …ただしログの順序についてはFuture Workとして詳細は書いてない。 Rt:1 Wt:1 ts:4でOK ReadWriteSetReadSet
- 25. TicToc Siloを超える性能が出ているらしい Silo TicToc 出典: Xiangyao Yuら TicToc: Time Traveling Optimistic Concurrency Control
- 26. TicTocの問題点 ReadするだけのデータであってもReadTimeStampを更新しないといけない。 …キャッシュを汚さないのがOCCの利点じゃなかったっけ？ Read-Onlyなワークロードだと負けてるじゃないですか！ 出典: Xiangyao Yuら TicToc: Time Traveling Optimistic Concurrency Control
- 28. Mostly-Optimistic Concurrency Control(MOCC) OCCが苦手なWriteメインのワークロードでも性能が出ている。 出典： Tianzheng Wangら Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores