狠狠撸

狠狠撸Share a Scribd company logo

述語ロックの歴史 r2

?
?
S
Sho Nakazono

调べました

1 of 45
Download to read offline
nikezono (sho nakazono), 2022/1/21 述語ロックの歴史 The History of Predicate Locking
TL;DR; ? トランザクション処理における並?性制御（Concurrency Control）のモデル 化は ”The Page Model” として1970年代に?われた． ? The Page Model には述語（Predicate） やInsert/Deleteの概念が無かった ? Insert/Deleteに起因するファントム異常 （Phantom anomaly）が報告され た ? 対処法として述語ロック（Predicate Locking）という?法が提案された ? 今はあまり使われていないが，別の形で?きている
紹介する論? ? [1] K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. 1976. The notions of consistency and predicate locks in a database system. Commun. ACM 19, 11 (Nov. 1976), 624–633. ? [2] J. R. Jordan, J. Banerjee, and R. B. Batman. 1981. Precision locks. SIGMOD ’81. ? [3] Manuel Reimer. 1983. Solving the Phantom Problem by Predicative Optimistic Concurrency Control. VLDB ’83. ? [4] Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. 2015. Fast Serializable Multi- Version Concurrency Control for Main-Memory Database Systems. SIGMOD ’15. ? [5] Jinwei Guo, Peng Cai, Jiahao Wang, Weining Qian, Aoying Zhou: Adaptive Optimistic Concurrency Control for Heterogeneous Workloads. Proc. VLDB Endow. 12(5): 584-596 (2019)
まとめ ? [1] Predicate Locking: すべての術語をそのまま保存しロックする．計算量に問題がある． ? [2] Precision Locking: scanとinsert/delete のみを分けて保存する．2PLベースならではの 最適化？ ? [3] Optimistic Predicate Locking: Precision Locking に OCC のエッセンスを追加．つま り，insert/deleteのみ保存 ? [4] HyPer: Precision LockingをSnapshot IsolationをSerializableにする?法の?つとして採 ?．Phantomは関係ない ? [5] AOCC: HyPer?式をSingle-Version OCCにも採?．性能を評価．
The page model (a.k.a., read/write model, general model) トランザクション処理を形式的に記述するためのモデリングの?つ． あるページ x に対して， read(x) と write(x) のみを命令とするモデル. 現在まで使われている． Notation: ? データベースは，ページ (data item) の集合 ? として表現される． ? (Pros) 最もシンプルで，ストレージやメモリへのアクセス命令と対応している ? (Pros) readers-writer locking で簡単に実装できる ? (Cons) テーブル情報などのセマンティクスがなく，最適化の余地が失われる ? (Cons) ? が静的である．ページの追加/削除といった概念がない (すべて ? になる) t = r(x)w(x)r(y)w(z) D = {x, y, z . . . , } D w(x)
The page model (a.k.a., read/write model, general model) トランザクション処理を形式的に記述するためのモデリングの?つ． あるページ x に対して， read(x) と write(x) のみを命令とするモデル. 現在まで使われている． Notation: ? データベースは，ページ (data item) の集合 ? として表現される． ? (Pros) 最もシンプルで，ストレージやメモリへのアクセス命令と対応している ? (Pros) readers-writer locking で簡単に実装できる ? (Cons) テーブル情報などのセマンティクスがなく，最適化の余地が失われる ? (Cons) ? が静的である．ページの追加/削除といった概念がない (すべて ? になる) t = r(x)w(x)r(y)w(z) D = {x, y, z . . . , } D w(x) ? が静的であることによって，ロックベースの Concurrency Control実装特有の問題が発?する D
[1] Notion of Phantom Anomaly
[1] Notion of Phantom Anomaly ? ページの ”存在” を情報として扱うトランザクションは，ページモデル+ロックだと実装できない． ? 「存在する」ページはロックできるが，「存在しない」ページにはロックをかけられないため． ? SELECT * FROM Users WHERE …, といった?般的な Predicate を持つクエリ全てにこの問題は 存在する． ? 今はまだ ? に存在しないが，クエリの対象となっているページを phantoms と呼ぶ． D > A still more elementary example is the test for the existence of a tuple in a relation. If the tuple exists, it is to be locked to insure that no other transaction will delete it before the fi rst transaction terminates. If the tuple does not exist, "it" should be locked to insure that no other transaction will create such a tuple before the fi rst transaction terminates. In this case the "nonexistence" of the tuple is being locked. Such nonexistent tuples are called phantoms.
Phantom Anomaly on Graph Other Anomalies t1 ? r1(x) w2(x) w2(y) r1(y) t2 r-w (anti dependency) w-r ( fl ow dependency)
Phantom Anomaly on Graph Other Anomalies t1 ? r1(x) w2(x) w2(y) r1(y) t2 r-w (anti dependency) w-r ( fl ow dependency)
Phantom Anomaly on Graph Other Anomalies t1 ? r1(x) r1(y) w2(x) w2(y) t2 r-w (anti dependency)
Phantom Anomaly on Graph Other Anomalies Phantom Anomaly t1 ? r1(x) r1(y) w2(x) w2(y) t2 r-w (anti dependency) t1 SELECT * FROM User WHERE Age < 20 t2 r-w (anti dependency)? w-r ( fl ow dependency)? t1 = INSERT INTO User (Age=25) t2 = → when t1 reads Age =25 ← otherwise
Phantom Anomaly on Graph Other Anomalies Phantom Anomaly t1 ? r1(x) r1(y) w2(x) w2(y) t2 r-w (anti dependency) t1 SELECT * FROM User WHERE Age < 20 t2 r-w (anti dependency)? w-r ( fl ow dependency)? t1 = INSERT INTO User (Age=25) t2 = → when t1 reads Age =25 ← otherwise 向きが分からないエッジが?つでも存在しうるだけで， Serializableは達成できない． ページ単位の操作に関してはロックを使って?循環グラ フが描けても，Predicate/Insert/Delete によって?まれ たエッジを使えば循環がつくれてしまう．
既存のアプローチ # ナイーブな解決?法 ? テーブルロックをかける(簡単 & 遅い) # 発展的な解決?法 ? Predicate Locking(今?の話題) ? ファントム対処まで織り込んだConcurrency Control Algorithmを使う ? インデックスにロックをかける ? 例えば，B+treeのリーフノードの next pointer に readers-writer lock を使う，など． ? MySQL では “ギャップロック” とか． “ネクストキーロッキング”とも．
[1] Predicate Locking (Eswaran et al. 1976) トランザクションの述語をそのままロックとして扱うアプローチ． 別名「Logical locking」とも． 例えば，ACCOUNTS テーブルをSELECTする際にこのような形の論理的なロックを取る． ? これによって，Location=Napa のACCOUNTSをINSERT/DELETEできなくする． ロックベースのConcurrency Control と同じように 2-phase locking することで，?循環なグラフ を作ることができる．
Phantom Anomaly on Graph Other Anomalies Phantom Anomaly t1 ? r1(x) r1(y) w2(x) w2(y) t2 r-w (anti dependency) t1 SELECT * FROM User WHERE Age < 20 t2 r-w (anti dependency) t1 = INSERT INTO User (Age=15) t2 =
[1] Predicate Locking w/ Lock Table ? データベース内にLock Tableを?意する． ? Readers-writer lock に加えて predicate lockを?れる． ? {テーブル名, 述語, read/write fl ag} のtripleで構成． ? Read: SELECT ?などWHERE句がつくもの ? Write: INSERT/DELETE?など ? read/write, write/writeでそれぞれsatisfy checkを?う ? Lock table のいずれかのlockを?分がsatisfyしている 場合は，待つ． ? Readers-writer lockingと同じく，readersはロックを共有 できる
[1] Predicate Locking w/ Lock Table ? データベース内にLock Tableを?意する． ? Readers-writer lock に加えて predicate lockを?れる． ? {テーブル名, 述語, read/write fl ag} のtripleで構成． ? Read: SELECT ?などWHERE句がつくもの ? Write: INSERT/DELETE?など ? read/write, write/writeでそれぞれsatisfy checkを?う ? Lock table のいずれかのlockを?分がsatisfyしている 場合は，待つ． ? Readers-writer lockingと同じく，readersはロックを共有 できる 全トランザクションが共有しアクセスする 並?データ構造になって並列性が厳しい クエリを選?/積和標準形(DNF) に変換し，ロック テーブル内のすべてのpredicateとの compatibility(satisfiability) checkingを?う処理 は，?較演算?が等号でない場合， NP-hard[2][Rosenkrantz80]． (さらに後年の論?ではSATなのでNP-Completeとされる)． 要するに計算量的に使い物にならない． [Rosenkrantz80] Processing Conjunctive Predicates and Queries D. Rosenkrantz, H. Hunt Published in VLDB 1 October 1980
[2] Precision Locking (Jordan et al. 1981)
[2] Precision Locking (Jordan et al. 1981) ? Predicate Lockingをよりpreciselyにした?法． ? 「不必要なロックを取らない」ことが改善点． ? 計算量の問題も解決した． ? 証明がない．
[2] Predicates and Updates ? トランザクション ? は ? と ? として表現する． ? ? は ? の j番?のpredicate． ? は ? の k番?のupdate． ? Predicateは “title=‘programmer’ ∧ location=‘Roseville’” といった論理的な述語 ? Updateは insert/delete された 物理的なキー ? Predicate Locking[1] ではupdateも “write predicate” として同じ扱いだった． ? ここが明確な差分で，”insert/delete絡みでしか phantom は起こらない” という洞察による最適化とい える ? i.e., 「“2PLベースでは，phantom anomalyが起こるならば，insert/deleteとscanの，satis fi ed な pairが必ず存在する”」という定理が証明できるはず．でなければこの最適化は通らない Ti Pi = {pij} Ui = {uik} pij Ti uik Ti
[2] Predicate List ? データベースには Predicate List ? と Update List ? を?意する． ? トランザクションは，predicate read の際とinsert/deleteの際に以下を?う ? predicate read: ? にpredicateを追加する． ? の全件とsatis fi ability checkを?う． ? checkは ? ．つまり「predicateにマッチするins/delがない」 ? ↑のcheckがtrueであれば，wait/blockする． ? Insert/delete: ? にins/delを追加する． ? の全件とsatis fi ability checkを?う ? 以下同じ Lp = {pij} Lu = {uik} Lp Lu ?uk ∈ Lu, pij(uk) Lu Lp
[2] Predicate Locking vs Precision Locking Precision Lockingの改良点 ? Read vs Read，Write vs Writeの satis fi ability checkが不要 ? Writeも insert/delete に限定している ? updateされたtupleをpredicate readしたところでphantomにはならないため． ? Predicateの定義に関する制限が緩い ? Predicate lock [1]は 演算?が = なのか < なのかで計算量が激変した ? Precision lock [2] はあるtuple t に ? がbooleanを返せばどんな形でもよい．計算量も ? , ? で済む． pij(t) |Lp | |Lu |
[3] Optimistic Predicate Locking
[3] Optimistic Predicate Locking (Redner et al. 1983) ? Predicate Locking + Optimistic Concurrency Control (OCC) [Kung81] という?法． ? OCCなので，トランザクションは readset と writeset をもつ． ? OCCなので，トランザクションは3-phase に分けて実?される． 1. Read phase ? トランザクションを実?する．Read/Writeはwaitなしで実?し，predicateをread setに，writeをwrite setに保存してお く． 2. Validation phase 1. Serial validation/ parallel validation どちらにせよ，write setがcon fl ictしているトランザクション同?ではひとつのトラ ンザクションしか同時に validation phase に?れない ? グローバル領域に?意された concurrent transactions の writeset list と ?身のpredicateをcheckする． 3. Write phase ? Writeset の中身をグローバルに反映する．グローバル領域に writesetを書き出す． [Kung81] H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. VLDB 1979: 351
[3] Optimistic Predicate Locking ? この?法は Precision Locking (PL)にかなり近いが，以下の点で異なる． A. Writeset だけを他のトランザクションにglobalに公開する． ? i.e., PLにおける ? のうち後者のみしか必要としない． ? PLはreadがwriteを，writeがreadを待っていたが，OPLはreadもwriteも待ちなしで? い，writeを優先させてreaderをabortさせている． B. block/waitがない．他のトランザクションとintersectしているかどうかは validation phase で判定するので，predicate read/insert/deleteもread phaseですぐに実?できる． Lp, Lu
[3] Precision Locking vs Optimistic Predicate Locking Optimistic Predicate Locking (OPL)の改良点/変更点 ? OCCなので，predicate read のロックを実際に取らない => readが多いときキャッシュに優しい ? 特に，Predicate List L_p や Lock Tableはグローバルなデータ構造なので，極?何も書きたくない．shared lock を取ることで全ワーカスレッドのキャッシュをinvalidateする可能性?． ? Predicate lockingは phantom preventionだが，OPLは phantom avoidanceである ? OCCなので，deadlockが起こらない ? Predicate lockingは結局2PLなので，deadlockがある．回避アルゴリズムのコストが必要 ? Starvation-freeではない ? OCCはread-lock-freeだがreader abortするので，OPLにおいてもscanが?向に通らないということがありうる．
[4] HyPer (Neumann et al. 2015)
[4] HyPer (Neumann et al. 2015) ? ?い時を経て述語ロックが帰ってきた！ ? Snapshot Isolation + Optimistic Concurrency Control + Precision Locking + MVCC という全部盛りな感じの設計． ? Hybrid OLTP-OLAP (HTAP) なプロトコルが売り． ? MVCC + Snapshot Isolationなので OLAPには強い． ? OCCなので Read-mostlyなワークロードにも強い． ? Precision Lockingを使っているので Snapshot Isolationよりも?貫性が強い(Serializable)． ? 他にも，カラムストアだったり，delta-record versioningといった?夫があるか，今回の本題から外れるので割 愛． ? 評価実験もある．ありがたい．tableau にも実装されている．
[4] Protocol of HyPer ? Snapshot Isolationがベースになっており，トランザクションにタイムスタンプが与えられる． ? 開始時に transactionID, startTime が与えられる． ? 終了時に commitTime というタイムスタンプが与えられ，writeしたversionに記録される．これが書かれているversionは committedである． ? First-Writer-Wins: writeする際，uncommitted versionがあればabortする．これによって w-w con fl ict は発?しだいabortされ る． ? Readする際はlast committed versionを読む．これによって w-r con fl ict のエッジ は 必ずcommit済みのトランザクションから 伸びる． ? したがって循環があり，Serializableでないならば， commit済みのトランザクションに対して伸びる r-w con fl ict のエッジ がある．(ここまでSnapshot Isolation?般の知識) ? この r-w エッジによる循環を排除するために， precision lockingを使っている． ? Commit済みのトランザクションの write set を保存しておけば，r-w con fl ictのエッジが検出できる，というわけ．
CMU 15-721 SPRING 2020 Advanced Database Systems, Multi-Version Concurrency Control (Protocols), https://15721.courses.cs.cmu.edu/spring2020/slides/04-mvcc2.pdf
CMU 15-721 SPRING 2020 Advanced Database Systems, Multi-Version Concurrency Control (Protocols), https://15721.courses.cs.cmu.edu/spring2020/slides/04-mvcc2.pdf
[4] OPL vs HyPer HyPerの改良点 ? Snapshot Isolation (MVCC, Timestamp) をベースにしている ? これまでの?法は全てロックベースで，tuple-level lockingを2PLで?い，phantomを2-phase predicate lockingで処理する，というものだった ? もはやphantomの為ではなく，SIのSerializabilityの?を塞ぐためにPrecision Lockingを使っている ? キモは “write setをglobalに保存する” という部分で，これを使って r-w con fl ictを検出している ? Validation時に?分のRead setではなく predicate set を使うというのも良い．OLAPだとRSの サイズが?きいため．
[4] HyPer Performance
[4] HyPer Evaluation ? HyPerのパフォーマンスは[Wu17] でも?較実験されている． [Wu17] Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. 2017. An empirical evaluation of in-memory multi-version concurrency control. Proc. VLDB Endow. 10, 7 (March 2017), 781–792. DOI:https://doi.org/10.14778/3067421.3067427
[5] Adaptive OCC (Guo et al. 2019)
[5] Adaptive OCC (Guo et al. 2019) ? OCCのValidation Phaseの挙動を以下２つでadaptiveに切り替える?法． ? LRV: local read-set validation. RSのtuplesが更新されているかを判定 (popular) ? GWV: global write-set validation. グローバルに置かれたWSと?身のRSが intersectしているかを判定 (つまり optimistic predicate locking) ? ２つの?法はそれぞれpros/consがある．
Settings ? YCSB ? 10M Records ? Single table ? 5 queries per transaction ? Zipfian distribution ? Scan query accesses 800 tuples Results (a) ? RSのサイズが?さいことから，LRVのほうが? 速 ? GWVはcentral data structureがあるので遅い (b) ? Scanが?るとLRVは苦しい．
[5] Adaptive OCC Implementation ? Adaptiveに実装を切り替えるために以下を?う ? Point queryしかないトランザクションは，LRVを使う ? Range query(scan) があるトランザクションには，GWVを使う ? adaptiveにしようとすると実装が難しい ? LRV: 各トランザクションのread setと，各tuplesにversion number ? GWV: グローバルなupdate listと，各トランザクションにpredicate set ? 実?中に?分がどちらでvalidationをするかを決めたいので，↑の実装を両?やる必要がある ? トランザクションは writeset, readset, predicateset の３つを保存することになる． ? グローバルには，各tuplesにversion numberと，あと効率的なupdate list 実装として gList を作る．
[5] gList ? 要するにlock-free ring bu ff er. ? NextIndex をCASして timestampを得る．(ん？) ? CollectedIndex: GC?． ? CommittedIndex: Validation ?．
? Validation phase のアルゴリズムを valLR1, valLR2, valGW と３つ?意し てある． ? LR1: read setでvalidationする ? LR2: predicate set でvalidationする ? GW: gListでvalidationする この３つをもとにコストモデルを作り， adaptive strategyに基づいてvalidationし ていく．（今回は割愛)
? (a) クエリが?いほど GWVが有利で，LRVの性 能が落ちる． ? (b) RSのサイズが増える ぶんvalidation phase に 時間がかかっている，と いう図．逆に，RSのサ イズが少ないときは， LRVが有利．
? (a) RSのサイズが?さい ときは，LRVが有利． AOCCもLRVを使えてい る． ? (b) RSのサイズが?きい ときは，GWVが有利． 以下略．
[5] Adaptive OCC vs Predicate Locking ? AOCCはHyPerに影響を受けている ? Phantomのために作られたはずのPredicate LockingをCCに使っている ? AOCCはPhantom回避のためにインデックスに並?処理をしていて， Predicate Locking相当の処理があるのにphantomのためには使っていな い． ? HyPerもAOCCもPrecision LockingというよりもOPLに近いハズだが，OPLを referしておらず，”precision locking” という名前で紹介している
まとめ ? [1] Predicate Locking: すべての術語をそのまま保存しロックする．計算量に問題がある． ? [2] Precision Locking: scanとinsert/delete のみを分けて保存する．2PLベースならではの 最適化？ ? [3] Optimistic Predicate Locking: Precision Locking に OCC のエッセンスを追加．つま り，insert/deleteのみ保存 ? [4] HyPer: Precision LockingをSnapshot IsolationをSerializableにする?法の?つとして採 ?．Phantomのためだけよりも広い使い? ? [5] AOCC: HyPer?式をSingle-Version OCCにも採?．性能を評価．

More Related Content

述語ロックの歴史 r2

  • 1. nikezono (sho nakazono), 2022/1/21 述語ロックの歴史 The History of Predicate Locking
  • 2. TL;DR; ? トランザクション処理における並?性制御（Concurrency Control）のモデル 化は ”The Page Model” として1970年代に?われた． ? The Page Model には述語（Predicate） やInsert/Deleteの概念が無かった ? Insert/Deleteに起因するファントム異常 （Phantom anomaly）が報告され た ? 対処法として述語ロック（Predicate Locking）という?法が提案された ? 今はあまり使われていないが，別の形で?きている
  • 3. 紹介する論? ? [1] K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. 1976. The notions of consistency and predicate locks in a database system. Commun. ACM 19, 11 (Nov. 1976), 624–633. ? [2] J. R. Jordan, J. Banerjee, and R. B. Batman. 1981. Precision locks. SIGMOD ’81. ? [3] Manuel Reimer. 1983. Solving the Phantom Problem by Predicative Optimistic Concurrency Control. VLDB ’83. ? [4] Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. 2015. Fast Serializable Multi- Version Concurrency Control for Main-Memory Database Systems. SIGMOD ’15. ? [5] Jinwei Guo, Peng Cai, Jiahao Wang, Weining Qian, Aoying Zhou: Adaptive Optimistic Concurrency Control for Heterogeneous Workloads. Proc. VLDB Endow. 12(5): 584-596 (2019)
  • 4. まとめ ? [1] Predicate Locking: すべての術語をそのまま保存しロックする．計算量に問題がある． ? [2] Precision Locking: scanとinsert/delete のみを分けて保存する．2PLベースならではの 最適化？ ? [3] Optimistic Predicate Locking: Precision Locking に OCC のエッセンスを追加．つま り，insert/deleteのみ保存 ? [4] HyPer: Precision LockingをSnapshot IsolationをSerializableにする?法の?つとして採 ?．Phantomは関係ない ? [5] AOCC: HyPer?式をSingle-Version OCCにも採?．性能を評価．
  • 5. The page model (a.k.a., read/write model, general model) トランザクション処理を形式的に記述するためのモデリングの?つ． あるページ x に対して， read(x) と write(x) のみを命令とするモデル. 現在まで使われている． Notation: ? データベースは，ページ (data item) の集合 ? として表現される． ? (Pros) 最もシンプルで，ストレージやメモリへのアクセス命令と対応している ? (Pros) readers-writer locking で簡単に実装できる ? (Cons) テーブル情報などのセマンティクスがなく，最適化の余地が失われる ? (Cons) ? が静的である．ページの追加/削除といった概念がない (すべて ? になる) t = r(x)w(x)r(y)w(z) D = {x, y, z . . . , } D w(x)
  • 6. The page model (a.k.a., read/write model, general model) トランザクション処理を形式的に記述するためのモデリングの?つ． あるページ x に対して， read(x) と write(x) のみを命令とするモデル. 現在まで使われている． Notation: ? データベースは，ページ (data item) の集合 ? として表現される． ? (Pros) 最もシンプルで，ストレージやメモリへのアクセス命令と対応している ? (Pros) readers-writer locking で簡単に実装できる ? (Cons) テーブル情報などのセマンティクスがなく，最適化の余地が失われる ? (Cons) ? が静的である．ページの追加/削除といった概念がない (すべて ? になる) t = r(x)w(x)r(y)w(z) D = {x, y, z . . . , } D w(x) ? が静的であることによって，ロックベースの Concurrency Control実装特有の問題が発?する D
  • 7. [1] Notion of Phantom Anomaly
  • 8. [1] Notion of Phantom Anomaly ? ページの ”存在” を情報として扱うトランザクションは，ページモデル+ロックだと実装できない． ? 「存在する」ページはロックできるが，「存在しない」ページにはロックをかけられないため． ? SELECT * FROM Users WHERE …, といった?般的な Predicate を持つクエリ全てにこの問題は 存在する． ? 今はまだ ? に存在しないが，クエリの対象となっているページを phantoms と呼ぶ． D > A still more elementary example is the test for the existence of a tuple in a relation. If the tuple exists, it is to be locked to insure that no other transaction will delete it before the fi rst transaction terminates. If the tuple does not exist, "it" should be locked to insure that no other transaction will create such a tuple before the fi rst transaction terminates. In this case the "nonexistence" of the tuple is being locked. Such nonexistent tuples are called phantoms.
  • 9. Phantom Anomaly on Graph Other Anomalies t1 ? r1(x) w2(x) w2(y) r1(y) t2 r-w (anti dependency) w-r ( fl ow dependency)
  • 10. Phantom Anomaly on Graph Other Anomalies t1 ? r1(x) w2(x) w2(y) r1(y) t2 r-w (anti dependency) w-r ( fl ow dependency)
  • 11. Phantom Anomaly on Graph Other Anomalies t1 ? r1(x) r1(y) w2(x) w2(y) t2 r-w (anti dependency)
  • 12. Phantom Anomaly on Graph Other Anomalies Phantom Anomaly t1 ? r1(x) r1(y) w2(x) w2(y) t2 r-w (anti dependency) t1 SELECT * FROM User WHERE Age < 20 t2 r-w (anti dependency)? w-r ( fl ow dependency)? t1 = INSERT INTO User (Age=25) t2 = → when t1 reads Age =25 ← otherwise
  • 13. Phantom Anomaly on Graph Other Anomalies Phantom Anomaly t1 ? r1(x) r1(y) w2(x) w2(y) t2 r-w (anti dependency) t1 SELECT * FROM User WHERE Age < 20 t2 r-w (anti dependency)? w-r ( fl ow dependency)? t1 = INSERT INTO User (Age=25) t2 = → when t1 reads Age =25 ← otherwise 向きが分からないエッジが?つでも存在しうるだけで， Serializableは達成できない． ページ単位の操作に関してはロックを使って?循環グラ フが描けても，Predicate/Insert/Delete によって?まれ たエッジを使えば循環がつくれてしまう．
  • 14. 既存のアプローチ # ナイーブな解決?法 ? テーブルロックをかける(簡単 & 遅い) # 発展的な解決?法 ? Predicate Locking(今?の話題) ? ファントム対処まで織り込んだConcurrency Control Algorithmを使う ? インデックスにロックをかける ? 例えば，B+treeのリーフノードの next pointer に readers-writer lock を使う，など． ? MySQL では “ギャップロック” とか． “ネクストキーロッキング”とも．
  • 15. [1] Predicate Locking (Eswaran et al. 1976) トランザクションの述語をそのままロックとして扱うアプローチ． 別名「Logical locking」とも． 例えば，ACCOUNTS テーブルをSELECTする際にこのような形の論理的なロックを取る． ? これによって，Location=Napa のACCOUNTSをINSERT/DELETEできなくする． ロックベースのConcurrency Control と同じように 2-phase locking することで，?循環なグラフ を作ることができる．
  • 16. Phantom Anomaly on Graph Other Anomalies Phantom Anomaly t1 ? r1(x) r1(y) w2(x) w2(y) t2 r-w (anti dependency) t1 SELECT * FROM User WHERE Age < 20 t2 r-w (anti dependency) t1 = INSERT INTO User (Age=15) t2 =
  • 17. [1] Predicate Locking w/ Lock Table ? データベース内にLock Tableを?意する． ? Readers-writer lock に加えて predicate lockを?れる． ? {テーブル名, 述語, read/write fl ag} のtripleで構成． ? Read: SELECT ?などWHERE句がつくもの ? Write: INSERT/DELETE?など ? read/write, write/writeでそれぞれsatisfy checkを?う ? Lock table のいずれかのlockを?分がsatisfyしている 場合は，待つ． ? Readers-writer lockingと同じく，readersはロックを共有 できる
  • 18. [1] Predicate Locking w/ Lock Table ? データベース内にLock Tableを?意する． ? Readers-writer lock に加えて predicate lockを?れる． ? {テーブル名, 述語, read/write fl ag} のtripleで構成． ? Read: SELECT ?などWHERE句がつくもの ? Write: INSERT/DELETE?など ? read/write, write/writeでそれぞれsatisfy checkを?う ? Lock table のいずれかのlockを?分がsatisfyしている 場合は，待つ． ? Readers-writer lockingと同じく，readersはロックを共有 できる 全トランザクションが共有しアクセスする 並?データ構造になって並列性が厳しい クエリを選?/積和標準形(DNF) に変換し，ロック テーブル内のすべてのpredicateとの compatibility(satisfiability) checkingを?う処理 は，?較演算?が等号でない場合， NP-hard[2][Rosenkrantz80]． (さらに後年の論?ではSATなのでNP-Completeとされる)． 要するに計算量的に使い物にならない． [Rosenkrantz80] Processing Conjunctive Predicates and Queries D. Rosenkrantz, H. Hunt Published in VLDB 1 October 1980
  • 19. [2] Precision Locking (Jordan et al. 1981)
  • 20. [2] Precision Locking (Jordan et al. 1981) ? Predicate Lockingをよりpreciselyにした?法． ? 「不必要なロックを取らない」ことが改善点． ? 計算量の問題も解決した． ? 証明がない．
  • 21. [2] Predicates and Updates ? トランザクション ? は ? と ? として表現する． ? ? は ? の j番?のpredicate． ? は ? の k番?のupdate． ? Predicateは “title=‘programmer’ ∧ location=‘Roseville’” といった論理的な述語 ? Updateは insert/delete された 物理的なキー ? Predicate Locking[1] ではupdateも “write predicate” として同じ扱いだった． ? ここが明確な差分で，”insert/delete絡みでしか phantom は起こらない” という洞察による最適化とい える ? i.e., 「“2PLベースでは，phantom anomalyが起こるならば，insert/deleteとscanの，satis fi ed な pairが必ず存在する”」という定理が証明できるはず．でなければこの最適化は通らない Ti Pi = {pij} Ui = {uik} pij Ti uik Ti
  • 22. [2] Predicate List ? データベースには Predicate List ? と Update List ? を?意する． ? トランザクションは，predicate read の際とinsert/deleteの際に以下を?う ? predicate read: ? にpredicateを追加する． ? の全件とsatis fi ability checkを?う． ? checkは ? ．つまり「predicateにマッチするins/delがない」 ? ↑のcheckがtrueであれば，wait/blockする． ? Insert/delete: ? にins/delを追加する． ? の全件とsatis fi ability checkを?う ? 以下同じ Lp = {pij} Lu = {uik} Lp Lu ?uk ∈ Lu, pij(uk) Lu Lp
  • 23. [2] Predicate Locking vs Precision Locking Precision Lockingの改良点 ? Read vs Read，Write vs Writeの satis fi ability checkが不要 ? Writeも insert/delete に限定している ? updateされたtupleをpredicate readしたところでphantomにはならないため． ? Predicateの定義に関する制限が緩い ? Predicate lock [1]は 演算?が = なのか < なのかで計算量が激変した ? Precision lock [2] はあるtuple t に ? がbooleanを返せばどんな形でもよい．計算量も ? , ? で済む． pij(t) |Lp | |Lu |
  • 25. [3] Optimistic Predicate Locking (Redner et al. 1983) ? Predicate Locking + Optimistic Concurrency Control (OCC) [Kung81] という?法． ? OCCなので，トランザクションは readset と writeset をもつ． ? OCCなので，トランザクションは3-phase に分けて実?される． 1. Read phase ? トランザクションを実?する．Read/Writeはwaitなしで実?し，predicateをread setに，writeをwrite setに保存してお く． 2. Validation phase 1. Serial validation/ parallel validation どちらにせよ，write setがcon fl ictしているトランザクション同?ではひとつのトラ ンザクションしか同時に validation phase に?れない ? グローバル領域に?意された concurrent transactions の writeset list と ?身のpredicateをcheckする． 3. Write phase ? Writeset の中身をグローバルに反映する．グローバル領域に writesetを書き出す． [Kung81] H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. VLDB 1979: 351
  • 26. [3] Optimistic Predicate Locking ? この?法は Precision Locking (PL)にかなり近いが，以下の点で異なる． A. Writeset だけを他のトランザクションにglobalに公開する． ? i.e., PLにおける ? のうち後者のみしか必要としない． ? PLはreadがwriteを，writeがreadを待っていたが，OPLはreadもwriteも待ちなしで? い，writeを優先させてreaderをabortさせている． B. block/waitがない．他のトランザクションとintersectしているかどうかは validation phase で判定するので，predicate read/insert/deleteもread phaseですぐに実?できる． Lp, Lu
  • 27. [3] Precision Locking vs Optimistic Predicate Locking Optimistic Predicate Locking (OPL)の改良点/変更点 ? OCCなので，predicate read のロックを実際に取らない => readが多いときキャッシュに優しい ? 特に，Predicate List L_p や Lock Tableはグローバルなデータ構造なので，極?何も書きたくない．shared lock を取ることで全ワーカスレッドのキャッシュをinvalidateする可能性?． ? Predicate lockingは phantom preventionだが，OPLは phantom avoidanceである ? OCCなので，deadlockが起こらない ? Predicate lockingは結局2PLなので，deadlockがある．回避アルゴリズムのコストが必要 ? Starvation-freeではない ? OCCはread-lock-freeだがreader abortするので，OPLにおいてもscanが?向に通らないということがありうる．
  • 28. [4] HyPer (Neumann et al. 2015)
  • 29. [4] HyPer (Neumann et al. 2015) ? ?い時を経て述語ロックが帰ってきた！ ? Snapshot Isolation + Optimistic Concurrency Control + Precision Locking + MVCC という全部盛りな感じの設計． ? Hybrid OLTP-OLAP (HTAP) なプロトコルが売り． ? MVCC + Snapshot Isolationなので OLAPには強い． ? OCCなので Read-mostlyなワークロードにも強い． ? Precision Lockingを使っているので Snapshot Isolationよりも?貫性が強い(Serializable)． ? 他にも，カラムストアだったり，delta-record versioningといった?夫があるか，今回の本題から外れるので割 愛． ? 評価実験もある．ありがたい．tableau にも実装されている．
  • 30. [4] Protocol of HyPer ? Snapshot Isolationがベースになっており，トランザクションにタイムスタンプが与えられる． ? 開始時に transactionID, startTime が与えられる． ? 終了時に commitTime というタイムスタンプが与えられ，writeしたversionに記録される．これが書かれているversionは committedである． ? First-Writer-Wins: writeする際，uncommitted versionがあればabortする．これによって w-w con fl ict は発?しだいabortされ る． ? Readする際はlast committed versionを読む．これによって w-r con fl ict のエッジ は 必ずcommit済みのトランザクションから 伸びる． ? したがって循環があり，Serializableでないならば， commit済みのトランザクションに対して伸びる r-w con fl ict のエッジ がある．(ここまでSnapshot Isolation?般の知識) ? この r-w エッジによる循環を排除するために， precision lockingを使っている． ? Commit済みのトランザクションの write set を保存しておけば，r-w con fl ictのエッジが検出できる，というわけ．
  • 31. CMU 15-721 SPRING 2020 Advanced Database Systems, Multi-Version Concurrency Control (Protocols), https://15721.courses.cs.cmu.edu/spring2020/slides/04-mvcc2.pdf
  • 32. CMU 15-721 SPRING 2020 Advanced Database Systems, Multi-Version Concurrency Control (Protocols), https://15721.courses.cs.cmu.edu/spring2020/slides/04-mvcc2.pdf
  • 33. [4] OPL vs HyPer HyPerの改良点 ? Snapshot Isolation (MVCC, Timestamp) をベースにしている ? これまでの?法は全てロックベースで，tuple-level lockingを2PLで?い，phantomを2-phase predicate lockingで処理する，というものだった ? もはやphantomの為ではなく，SIのSerializabilityの?を塞ぐためにPrecision Lockingを使っている ? キモは “write setをglobalに保存する” という部分で，これを使って r-w con fl ictを検出している ? Validation時に?分のRead setではなく predicate set を使うというのも良い．OLAPだとRSの サイズが?きいため．
  • 35. [4] HyPer Evaluation ? HyPerのパフォーマンスは[Wu17] でも?較実験されている． [Wu17] Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. 2017. An empirical evaluation of in-memory multi-version concurrency control. Proc. VLDB Endow. 10, 7 (March 2017), 781–792. DOI:https://doi.org/10.14778/3067421.3067427
  • 36. [5] Adaptive OCC (Guo et al. 2019)
  • 37. [5] Adaptive OCC (Guo et al. 2019) ? OCCのValidation Phaseの挙動を以下２つでadaptiveに切り替える?法． ? LRV: local read-set validation. RSのtuplesが更新されているかを判定 (popular) ? GWV: global write-set validation. グローバルに置かれたWSと?身のRSが intersectしているかを判定 (つまり optimistic predicate locking) ? ２つの?法はそれぞれpros/consがある．
  • 38. Settings ? YCSB ? 10M Records ? Single table ? 5 queries per transaction ? Zipfian distribution ? Scan query accesses 800 tuples Results (a) ? RSのサイズが?さいことから，LRVのほうが? 速 ? GWVはcentral data structureがあるので遅い (b) ? Scanが?るとLRVは苦しい．
  • 39. [5] Adaptive OCC Implementation ? Adaptiveに実装を切り替えるために以下を?う ? Point queryしかないトランザクションは，LRVを使う ? Range query(scan) があるトランザクションには，GWVを使う ? adaptiveにしようとすると実装が難しい ? LRV: 各トランザクションのread setと，各tuplesにversion number ? GWV: グローバルなupdate listと，各トランザクションにpredicate set ? 実?中に?分がどちらでvalidationをするかを決めたいので，↑の実装を両?やる必要がある ? トランザクションは writeset, readset, predicateset の３つを保存することになる． ? グローバルには，各tuplesにversion numberと，あと効率的なupdate list 実装として gList を作る．
  • 40. [5] gList ? 要するにlock-free ring bu ff er. ? NextIndex をCASして timestampを得る．(ん？) ? CollectedIndex: GC?． ? CommittedIndex: Validation ?．
  • 41. ? Validation phase のアルゴリズムを valLR1, valLR2, valGW と３つ?意し てある． ? LR1: read setでvalidationする ? LR2: predicate set でvalidationする ? GW: gListでvalidationする この３つをもとにコストモデルを作り， adaptive strategyに基づいてvalidationし ていく．（今回は割愛)
  • 42. ? (a) クエリが?いほど GWVが有利で，LRVの性 能が落ちる． ? (b) RSのサイズが増える ぶんvalidation phase に 時間がかかっている，と いう図．逆に，RSのサ イズが少ないときは， LRVが有利．
  • 43. ? (a) RSのサイズが?さい ときは，LRVが有利． AOCCもLRVを使えてい る． ? (b) RSのサイズが?きい ときは，GWVが有利． 以下略．
  • 44. [5] Adaptive OCC vs Predicate Locking ? AOCCはHyPerに影響を受けている ? Phantomのために作られたはずのPredicate LockingをCCに使っている ? AOCCはPhantom回避のためにインデックスに並?処理をしていて， Predicate Locking相当の処理があるのにphantomのためには使っていな い． ? HyPerもAOCCもPrecision LockingというよりもOPLに近いハズだが，OPLを referしておらず，”precision locking” という名前で紹介している
  • 45. まとめ ? [1] Predicate Locking: すべての術語をそのまま保存しロックする．計算量に問題がある． ? [2] Precision Locking: scanとinsert/delete のみを分けて保存する．2PLベースならではの 最適化？ ? [3] Optimistic Predicate Locking: Precision Locking に OCC のエッセンスを追加．つま り，insert/deleteのみ保存 ? [4] HyPer: Precision LockingをSnapshot IsolationをSerializableにする?法の?つとして採 ?．Phantomのためだけよりも広い使い? ? [5] AOCC: HyPer?式をSingle-Version OCCにも採?．性能を評価．