トランザクションをSerializableにする4つの方法

8.8K Views

April 12, 23

スライド概要

profile-image

分散システムとかデータベースとかロックフリーとかが好きです。

シェア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

トランザクションをSerializable にする4つの方法 2015年12月18日 熊崎 宏樹@kumagi

2.

Serializableとは? • ユーザの一連の操作(お金を口座AからBへ1000円 移動する、等)が「時系列上のどこかの瞬間に実行 された」と解釈できる事が保証された一貫性モデル – 実際に一瞬で実行されたかはどうでもいい – どこかの瞬間であれば、1年前でも1億年後でも(定義上) 構わない • 並行システムにおいてはSequential Consistency(逐 次一貫性)と呼ばれる特性であり、DBのトランザク ションの文脈ではSerializableと呼ぶ

3.

Serializableとは? • 複数のユーザの動作をどこかの瞬間に論 理的にプロットした時に矛盾が起きない組 み合わせが一つでも存在するならOK – 順番が狂うなどもどうでも良い User1 User2 User3 A C B E D 時間 上記トランザクション群の結果はB→A→C→E→Dの順で実行された 事にすれば何らかの「順」にはなったのでSerializableである。

4.

Serializableとは? • 自分で書いた値が読めなくても一応 Serializable – 下の図ではUser1はトランザクションAで書いた 値をトランザクションBで読めない User1 A B 時間 上記トランザクション群の結果はB→Aの順で実行された事にすれ ば何らかの「順」にはなったのでSerializableである。

5.

脱線:Linearizableとは? • Serializableかつ、実行された瞬間が「操作の開始 時」以後、「操作の終了時」以前という条件を満た す場合にLinearizable – オレンジの線と緑の線が鈍角を描かなければOKとも 言える User1 User2 User3 A C B E D 時間 B→A→C→D→Eの順で実行されたとすれば、各トランザクションの 実行時間中に実行が行われたと言えるのでLinearizable

6.

実際のDBはどうなのか • 有名どころのDBのデフォルト設定は、パフォーマン ス上の問題から基本的にSerializableより緩い一貫 性モデルを採用している MySQL「大抵のユーザはデフォルトのREPEATABLE READで充分やで」 Oracle「READ COMMITEDが一番良く使われるだろうしデフォルトにしといたで」 PostgreSQL「READ COMMITEDがデフォルトやで」 DB2「CUSOR STABILITYがデフォルトやで」

7.

データベース授業あるある . ____ / \ / \ キリッ / (ー) (ー)\ / ⌒(__人__)⌒ \ | |r┬-| | \ `ー'´ / ノ \ トランザクションはACIDを守ります。 AはAtomicity CはConsistency IはIsolation DはDurability を意味します。 /´ ヽ | l \ ヽ -一''''''"~~``'ー--、 -一'''''''ー-、. ヽ ____(⌒)(⌒)⌒) ) (⌒_(⌒)⌒)⌒))

8.

データベース授業あるある だっておwwwwwwww ____ 守ってないおwwww /_ノ ヽ、_\ 遅くてやってられないおwwww ミ ミ ミ o゚((●)) ((●))゚o ミ ミ ミ /⌒)⌒)⌒. ::::::⌒(__人__)⌒:::\ /⌒)⌒)⌒) | / / / |r┬-| | (⌒)/ / / // | :::::::::::(⌒) | | | / ゝ:::::::::::/ | ノ | | | \ / ) / ヽ / `ー'´ ヽ / / | | l||l 从人 l||l l||l 从人 l||l ヽ -一''''''"~~``'ー--、 -一'''''''ー-、 ヽ ____(⌒)(⌒)⌒) ) (⌒_(⌒)⌒)⌒)) バンバン

9.

実用上大丈夫なのか • パフォーマンスは出るしSQLの書き方次第で 何とかなる(SELECT FOR UPDATEうんぬん) • それで話が終わるとよくないので、ここでおも むろにSerializable以外の分離レベルの落とし 穴を紹介

10.

アプリ例:病院予約アプリ • 医師が複数居る – 全ての医師は初めみんな「診察可能」 • 患者がやってきて医師の一覧を見て一人選 んで治療の予約を入れる – 選ばれた医師の状態は「予約済み」になる • 急患に備え、非常時以外では医師は最低1人 は「診察可能」状態でなければならない – その条件を満たせないなら予約を断る • どう実装するか?

11.

ロジック例 • 以下のロジックで良さそうに見える – なお発表者はストアドプロシージャの文法に詳しくないので以下は フィーリングでお読みください SET @avail SELECT COUNT(*) FROM doctors WHERE state == “診察可能”; IF @avail <= 1 BEGIN -- 医師が一人以下なら RAISEERROR(“診察可能な医師が居なくなります”); ELSE -- 医師が二人以上いるなら UPDATE doctors SET state == “予約済み” WHERE state ==“診察可能”AND name == “田中医者丸”; COMMIT; END

12.

ロジック例 • トランザクション内で行われる個々の動作を 青い線で表記 User 時間 医師何人? 2人居るで じゃあ佐藤さんヨロ ええで コミット頼む OK この3ステップの完了をひとまとまりのトランザクションとして実行す る。All or Nothingで実行されるのできっと上手く行くように思える。 なお、MVCCの実装上、コミット前のwriteはローカルなwrite setに 閉じる事が多いが、細かい事は考えないようにする。

13.

Write Skew • 実際にはうまく行かない – 一覧の取得は命じたが書き換えを禁じてないからcommitがそのまま通る User1 User2 時間 医師何人? じゃあ佐藤さんヨロ 医師何人? 2人居るで 2人居るで じゃあ田中さんヨロ ええで ええで コミット頼む コミット頼む OK OK 上記トランザクション群の結果として、診察可能な医師が0人にな る。これはUser1とUser2のどちらが先に実行した事にもできない。 良さそうなロジックなのにバグってる有名な一例。

14.

Read Only • 詳細はA Read-Only Transaction Anomaly Under Snapshot Isolation(Alanら2004)を参照 • 以下の実行はSerializeできない X Y 口座Aを確認 口座Aに20万預ける コミット 口座Aを確認 口座Bを確認 口座Bから10万引き出す(A+Bが負になるので金利込の11万を減らす) Z 時間 X→Yと仮定すると、最終状態が{A:20, B:-10}にならないとおかしい つまりYは必ずXの前に来ないとダメ Y→X→Zと仮定すると、Zは{A: 20, B: -11} を読まないとおかしい つまりZはYより前でXより後じゃないとダメ Y→Xの順序と、X→Z→Yの順序は同時に実現できない

15.

さあどうする? • 診察可能医師をSELECTする際にSELECT FOR UPDATEを 利用する(アプリロジックへの侵入) • “急患待ち”という新たな状態を定義して医師を先にそこ に割り当ててしまう(業務ロジックへの侵入) • “急患待ち”の医師が4人以上になるシステムにしておけ ばWrite Skewが3回起きる可能性はかなり低いでしょ(運 用でカバーする例) • “急患待ち”状態の医師なんて別に要らんかったんや。 緊急なら診察中の他の医師が何とかするでしょ(解決を 諦める例) • 分離レベルにSERIALIZABLEを指定 DBの問題は DBで解決

16.

解決策 • • • • 2 Phase Lockを行う Read-Trackingを行う(SSI) Read-Validationを行う(SILOその他) SQLのレイヤで先にSerializableにしてしまう

17.

解決策 • • • • 2 Phase Lockを行う Read-Trackingを行う(SSI) Read-Validationを行う(SILOその他) SQLのレイヤで先にSerializableにしてしまう

18.

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

19.

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

20.

Strict 2 Phase Lock(S2PL) • 2 Phase Lockに加えて「コミットが済むまで一切ロック解放するべからず」 という条件を加えた物 – カスケードロールバックを回避できるので実用上2PLと言ったらこれの事を指 す事が多い[要出典] 獲得しているロックの数 コミットのタイミングはこれより右に 行ってはいけない 成長相 減退相 1 2 時間

21.

2 Phase Lock • なんでこの方法ならSerializableになるのかは Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987): Concurrency Control and Recovery in Database Systems を参照

22.

解決策 • • • • 2 Phase Lockを行う Read-Trackingを行う(SSI) Read-Validationを行う(SILOその他) SQLのレイヤで先にSerializableにしてしまう

23.

トランザクション分離レベル • Serializableという安全地帯から出ると様々な 魔物(Anomaly)が襲い掛かってくる Serializalbe Write Skew Anomaly Read Only Anomaly Snapshot Isolation Phantom Read Anomaly Repeatable Read Non-Repeatable Read Anomaly Read Commited Dirty Read Anomaly Read Uncommited

24.

Snapshot Isolation • Write Skew AnomalyとRead Only Anomaly以外の Anomalyが起きないとされているトランザクション分離 レベル • 全てのトランザクションは、トランザクション開始時の データベースのスナップショットのみを見ながら走る、 という分離レベル – Read Repeatableと違ってファントムリード等も起きない • 実装上はMVCC(Multi-Version Concurrency Control)が 用いられる事が多いが、厳密にはそれだけではSIにで きない – 理由を説明するにはこの余白は狭すぎる

25.

基本アイデア • Snapshot Isolationで問題になるのはWrite Skew AnomalyとRead Only Anomaly[AlanらSIGMOD04]だから、それ らが起きなくなる仕組みを用意すればSerializableと呼ん で良いんじゃね? – 1999年ごろからそのアイデアはあった – ユーザのSQL文を検査してAnomalyが起きそうかどうか静的チェックする 方法なども検討された • その結果、TPC-Cの実行はSnapshot IsolationでもAnomalyが起きないパターンである事 が証明されたりなどした • Snapshot Isolationで発生するAnomalyを検出する方法 考えました!Dependency Cyclic Graph(DSG)を書けばい けます! – paper: Making Snapshot Isolation Serializable [Alanら2005]

26.

Dependency Serialization Graph • 「読んだものを書いた」「書いた物を読んだ」「書いた後に書 いた」のいずれかの順序関係がある場合に依存辺を追加し ていく A 医師何人? 医師何人? B 時間 じゃあ佐藤さんヨロ じゃあ田中さんヨロ ええで あかんで 2人居るで 2人居るで A A B コミット頼む A B Bが読んだ値にAが書き込むので Anti-Dependency(問題ない) A OK B Aが読んだ値にBが書き込むので Anti-Dependency→円環できた

27.

Dependency Serialization Graph • ついでにRead Only Anomalyも対処できる A B 口座Aを確認 口座Aに20万預ける コミット 口座Aを確認 口座Bを確認 口座Bから10万引き出す(A+Bが負になるので金利込の11万を減らす C あかんで 時間 A A B A Bが読んだ値にAが書き込むので Anti-Dependency(問題ない) C C B A B Aがコミットした値をCが 読むのでDependency A B Cが読んだ値に Bが書き込んだので Anti-Dependency→円環できた

28.

パフォーマンス測定 • SIと比べてほとんどパフォーマンス低下なし 出典: Making Snapshot Isolation Serializable

29.

DSGについて • 円環ができたらabortという割とすっきりしたア ルゴリズム • 速度もそれなりに出る • False Positive(必要のないabort)が起きる – 詳細は論文に • マルチコアにスケールしようと思ったら複数の readerがDSGの更新のためにキャッシュライン を取り合うのでスケールしにくい

30.

解決策 • • • • 2 Phase Lockを行う Read-Trackingを行う(SSI) Read-Validationを行う(SILOその他) SQLのレイヤで先にSerializableにしてしまう

31.

Read Validation • コミットのタイミングで自分が読んだものと同じ物を 読んだと確認すれば良い – いわゆるOptimistic Concurrency Control • 全てのデータに単調増加するバージョンをつける • Read Lockを取る代わりにバージョンを記録する • トランザクションをコミットする際に必要なWrite Lock を獲得してからRead Setのバージョンを比較する • すべて一致したらコミットを認める

32.

Write Skew • Readのバージョン比較で簡単に解決する User1 User2 医師何人? じゃあ佐藤さんヨロ 医師何人? じゃあ田中さんヨロ コミット頼む コミット頼む ここでバージョンあがる 時間 2人居るで 2人居るで ええで ええで OK あかんで それぞれのトランザクションは医師2人のデータのバージョンを取 得している。

33.

Read Only • バージョン比較強い X Y 口座Aを確認 口座Aに20万預ける コミット 口座Aを確認 口座Bを確認 口座Bから10万引き出す(金利込の11万を減らす) コミット Z ここでAのバージョンがあがる 時間 Aのバージョン不一致でabort

34.

永続性の話 • Read-Lockを取らないのはややこしい問題を ひき起こす – 具体的にはS2PLと同様にならない T1: Yを読んでXに上書きする(Y=0だったのでX==0へ) T2: YとZに書きこむ(Y=Z=10と書き込む) X Y Z Log T1 WL WL Log T2 validation WL トランザクション的にはT1→T2の順に滞りなくシリアライズさ れたといえるがログに書き込まれる順序はT2→T1

35.

永続性の話 • もし後に来たはずのT2しか書き込めなかった らT1リカバリはどうなるの? – もっとややこしいストーリーはまだまだ出てくる X Y Z Log T1 WL WL validation WL Log T2 Crash!

36.

バージョン比較の話 • 単調に増えるバージョンをデータ毎に個々に 管理するとまずい(特にARIES的な意味でLSN はリカバリに不可欠) – グローバルなカウンタでLSNを管理するのが普通 • LSNは全トランザクションが増やし続けるので パフォーマンスボトルネックになる – キャッシュコヒーレントトラフィックがヤバい

37.

Silo • LSNの代わりにEpochというグローバルカウン タを共有 • 40msごとにEpochの数字を増やす専用のス レッドが居る – 他のスレッドは読むだけなのでロックは要らない • 各トランザクションはコミットできる瞬間になっ たら自分のTransactionID(TID)を取得する – コミット前のEpoch確認の瞬間がSerialization Pointとなる。

38.

Silo • TID(64bits)は以下の構成 – 上位ビット(32bits?)はepoch – 中位ビット(余り)は他と被らない値 – 下位ビット(3bit)はフラグ(lock/latest-version/absent)を保持 • 決定する際は以下のプロトコルで決める – – – – Read/Write-Setの全てのレコードより大きくて 自分の過去のトランザクションより大きくて 現在のEpochを利用した 最小の値

39.

Siloのログ • ログは各ワーカーがローカルにEpochごとに ディスクに吐き出す – 全部のワーカーの同一Epochのログをかき集め ればそのEpoch内の全ての更新が出来上がる • 同一Epoch内でのログの全順序性は問わない – 半順序性はTID決定プロトコルで保障される – 永続化のタイミングは全てのワーカーの同一 Epochが書き出された時にGroup Commitされる – リカバリの際は同一Epoch内の全てのログが集ま らないと永続化されているとみなさない

40.

永続性の話 • Epochが全トランザクションの有効性を保障す る T1, T2が同一Epochの場合 X Y Z Log T1 WL WL Log T2 Crash! validation WL T2のログは同一EpochであるT1のログが残っていない場合 無効になる

41.

永続性の話 • Epochが全トランザクションの有効性を保障す る T1とT2のSerialization Pointの間にEpochの境界がある場 合 X Y Z Log T1 WL WL Log T2 Crash! validation WL T2のEpochのほうがT1のEpochより進んでいるので無効化 される

42.

Siloまとめ • 他にもいくつも技術が詰め込まれてて話したいこ といっぱいあるけど力不足で説明しきれない • 32コアでTPC-Cが70万トランザクション/秒とかす ごい – ただしクエリはC++でローカル直書きなのでTPC-Cスコアそ のものではない • これをさらに改良したという「FOEDUS」がHPEから OSSで出てる – こっちもいろいろ語りたいけど時間がない

43.

解決策 • • • • 2 Phase Lockを行う Read-Trackingを行う(SSI) Read-Validationを行う(SILOその他) 先にSerializableにしてしまう

44.

いつSerializeするか? • クライアントからのリクエストにOne Shotモデ ルを採用してよいなら届いた瞬間にキューに 放り込んでその順に実行された事にしてしま えばいい • Rethinking serializable multiversion concurrency control(JoseらVLDB2015)などで 説明されてる。 • 発表資料作る時間なかったのでごめんなさい

45.

User1 BOHM: 大まかな概観図 A C User2 B E D User3 master 受け付けた順に処理する 行ごとに分割統治する Shared Nothingアーキテクチャ worker1 worker2 D E C A B Master worker3 worker4

46.

BOHMベンチマーク(YCSB) • パフォーマンスは出てるが圧倒的でもない • Hekatonと2PLがいい勝負してる…!?

47.

他になかったの? • 4つしかないとは誰も言ってない • いくつ思いつくかでトランザクションの知識量 を測れるかも