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

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

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

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

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

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

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

データベース授業あるある . ＿＿＿_ ／ ＼ ／ ＼ ｷﾘｯ ／ （ー） （ー）＼ ／ ⌒（__人__）⌒ ＼ | |r┬-| | ＼ `ー'´ ／ ノ ＼ トランザクションはACIDを守ります。 AはAtomicity CはConsistency IはIsolation DはDurability を意味します。 ／´ ヽ | ｌ ＼ ヽ -一''''''"~~｀`'ー--､ -一'''''''ー-､. ヽ ＿＿＿＿(⌒)(⌒)⌒) ) (⌒＿(⌒)⌒)⌒))

データベース授業あるある だっておｗｗｗｗｗｗｗｗ ＿＿＿_ 守ってないおｗｗｗｗ ／_ノ ヽ､_＼ 遅くてやってられないおｗｗｗｗ ﾐ ﾐ ﾐ oﾟ(（●）) (（●）)ﾟo ﾐ ﾐ ﾐ /⌒)⌒)⌒. ::::::⌒（__人__）⌒:::＼ /⌒)⌒)⌒) | / / / |r┬-| | (⌒)/ / / /／ | :::::::::::(⌒) | | | ／ ゝ:::::::::::/ | ノ | | | ＼ / ） / ヽ / `ー'´ ヽ / ／ | | l||l 从人 l||l l||l 从人 l||l ヽ -一''''''"~~｀`'ー--､ -一'''''''ー-､ ヽ ＿＿＿＿(⌒)(⌒)⌒) ) (⌒＿(⌒)⌒)⌒)) バンバン

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

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

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

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

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

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の順序は同時に実現できない

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

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

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

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

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

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

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

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

トランザクション分離レベル • 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

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

基本アイデア • 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]

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

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→円環できた

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

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

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

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

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

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

永続性の話 • 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

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

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

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

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

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

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

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

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

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

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

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

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

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