際際滷

際際滷Share a Scribd company logo

Isolation Level について

?
?
Takashi Hoshino
Takashi Hoshino

麼に猟 "Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions" のB初。 https://pmg.csail.mit.edu/pubs/adya99__weak_consis-abstract.html

1 of 20
Download to read offline
Isolation Level について 佛勸 1
古勣 ? 喘Z屁尖 ? Serializability, Isolation, Consistency´ ? ＳＱＬ覆 Isolation Level ? Adya の屁尖 2
Serializabilty ? 晩云Zでは仝岷双晒辛嬬來々 ? トランザクション_を岷双にg佩したのと吉と恂せること ? View 吉 (吭龍 Herbrand semantics でも吉) ? Conflict 吉 (Qいやすくするため View 吉より崙sがい) ? Linearizability (侘晒辛嬬來) とはなる古廷なので廣吭 ? Linearizability は仟しいデ`タをiめる來|(トランザクション渇鵐淵) ? Operation 1 しか根まないトランザクションの鹿栽という協の圷で、 Linearizable = Strict serializable 3
Consistency という冱~の詞岱 ? (1) ACID の C(consistency) ? DBMS がアプリケ`ションに戻工するデ`タベ`ス彜B崙sC嬬 ? (2) K双蛍柊順晢の Consistency ? 仟しいデ`タをiめるか(or 匯來のあるデ`タをiめるか) ? (3) Adya1999 の Consistency ? Isolation とあまり曝eしてないが Realtime 來のが飛孤秘ってそう ? ﾚい吭龍では Isolation も根め Consistency と柵びたい(by 佛勸) ? アプリケ`ションがデ`タとその尅る玲いに箔める音簗周を困燭垢海箸 ゴ`ル ? しばしば圧a議 (箭: Sequential consistency でないとバグるアルゴリズム) 4
Isolation Level とは ? Serializability が圀しいけど、來嬬とのトレ`ドオフがある ? みんな寄挫き Snapshot Isolation、Read Committed、Repeatable Read´ ? Serializability の隠^がなくても怎りることもある ? アプリケ`ション箸 DBMS にiみ篠る駅勣もしばしばある (Select に For update をつけるとか、電麿喘の Record を喘吭するなど) ? Level (粁A) 湖がある ? SQL片ｸ颪任榔承韻 Level としてｶ┐気譴討い ? 輝rは Level とか Degree などの冱~で燕Fされていた by Adya 5
SQL片ｸ ? ANSI X3.135-1992, American National Standard for Information Systems C Database Language C SQL, 1992 ? いわゆる SQL92 ? 恷仟は SQL:2019 (たぶん) ? Isolation 巓りは笋錣辰討覆い繁爾錣譴 ? 仝F鵝(or 尅玲い)を圷にした Informal な協x by Adya ? 2 宥りの盾: Anomaly 盾と Preventative 盾 6
SQL覆砲ける仝F鵝垢侶幗 ? Anomaly 盾は}があるので Preventative 盾が念戻 by Adya ? P0: ?1 と ?2 が ? を Concurrent に Write (どちらのY惚を火すか音苧) ? P1: ?1 のいた ? を ?1 commit 念に read し、?1 が abort する (?2 は commit 音辛嬬) ? P2: ?1 がiんだ ? を ?1 が commit する念に貧きする (?1 は ?2 のいたものをiむべき) ? P3: ?1 が predicate read して ?1 が commit する念に predicate read のY惚が笋錣襪茲Δ きzみをする (?1 は ?2 の筝を郡啌した predicate read Y惚をQyすべき) 7
SQL 覆 Isolation Level ? SQL 覆 Lock による CC (Concurrency control) Oにべったり ? SQL 覆 Serializable を(ここでは) ANSI-Serializable と柵ぶ 8
Bere1995 ? A Critique of ANSI SQL Isolation Levels ? H. Berenson, et al., 1995, SIGMOD Conference ? ANSI-Serializable は Serializable じゃないよ ? Snapshot isolation (SI) は ANSI-Serializable だけど Serializable じゃないよ ? SI では Write skew anomaly がk伏するよ ? (瘁の猟で、SI では read-only transaction anomaly もあると登苧) ? (Anomaly 盾は屎しくない、と冱ったのもこの猟 by Adya) 9
Adya1999 ? Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions ? Atul Adya, 1999, Doctor Thesis ? モチベ`ション ? SQL覆 Isolation Level 娠柩してくれ ? ? より措い Isolation 蛍(のためのモデル)の戻宛 ? 廣吭泣 ? Adya は MVCC や OCC をy匯議にQうため Version order を児覆砲靴 Conflict を協xするが、ここでは殆岷に (Write) operation order を喘いる 10
Adya1999 が峺姜する SQL 覆}泣 ? 協xが畸舛任△ ? (Anomaly 盾はg`っているので Preventative 盾を聞うべき by Bare1995) ? Lock 念戻のMみなので、喘議ではない ? (Preventative 盾だと) 崙浹弔垢て、恷除の CC protocol (OCC とか MVCC) が揖吉の Isolation level において宥すスケジュ`ルがｸ颪任`郡Qいとなっ てしまう ? CC Oやg廾卆贋だけでなく、喟A晒にvする噫な來|が詞ざっている (勣_J) 11
Isolation vS by Adya ? PL-1 ? PL-2 ? PL-2.99 (Repeatable Read) ? PL-3 (Full Serializability) ? PL-2+ (Consistent View) ? PL-SI (Snapshot Isolation) ? 麿 12 Figure 4.1 A partial order to relate various isolation levels.
Adya1999 の蛍 (匯何) ? モデルを喘いて苧_に、G0, G1, G2 麿の鋤峭するF鵑魘x 13
Adya1999 のモデル ? 愔瓦 Page model (for mono-version) ? }方のオペレ`ション (Op) から撹るトランザクション (Tx) が}方 ? Op は麼に read/write ? Op order が嚥えられる (Tx の Concurrent g佩を Op order における Interleaving で燕F) ? Standard version function (Op order における岷念の､鰌iむ) が念戻 ? Adya は愔瓦 Page model を ? Conflict-based アプロ`チ ? いわゆる w-r、w-w、r-w vSでグラフ夛を恬って Acyclic かどうか ? Op order の旗わりに Multi-version 鬚韻 Version order を聞喘 ? だから愔瓦 Conflict serializability での協xとは飛孤なる ? Phantom もQうため Predicate read/write が Op として秘ってる 14
Conflict of Adya1999 ? Directly read-dependency ? reads-from vSのこと (岷念の write と read のvS、倭xの w-r) ? Directly write-dependency ? BAする write と write のvS (倭xの w-w) ? Directly anti-dependency ? read と、それを岷俊貧きする write のvS (倭xの r-w) ? Directly conflict := Directly read/write/anti dependency ? Dependency := Transitive read/write dependency ? Conflict := Transitive conflict ? Predicate jみのものも根まれるが}jなので福待 ? Adya1999 では Version order の仝岷念々だが、gのため Op order を聞喘 15
DSG (Direct Serialization Graph) ? Direct conflict vSからBした Graph 夛 ? DSG = (V, E) where ? V: Transactions ? (t1, t2) in E: t2 directly depends on t1 ? (Transitive) conflict は Path 16
Condition G0 ? G0: Write Cycles ? Write dependency のみで撹される DSG の Cycles ? PL-1: G0 を鋤峭 ? 侭湖 ? Mono-version 念戻なら蛍かる ? Multi-version だとそもそも Version order だけで Order になってないとい う彜rに鬉垢襪里妊皀妊襪忘める吭龍を湖じない 17
Condition G1 ? G1a: Aborted Reads ? ?1 ? ?2 ? ´ ?1?2 ? G1b: Intermediate Reads ? ?1 ?1? ?2 ?1? ?1 ?1? ´ ?2 ? G1c: Circular Information Flow ? Dependency のみで撹された DSG の Cycles (G0 を根む) ? PL-2: G1 (= G1a+G1b+G1c) を鋤峭 ? 侭湖 ? G1a は喟A晒勣周だと房う(から CC はvSない塗) ? G1b は two-step model ではk伏しないから CC Oのにえる 18
Condition G2 ? G2: Anti-dependency Cycles ? ひとつ參貧の Anti-dependency を根む Cycles ? PL-2.99: G1 と G2-item (predicate 茅く) 鋤峭 ? PL-3: G1 と G2 鋤峭 19
まとめと湖 ? SQL覆 Isolation Level にはN？の}があった ? Adya1999 は苧_なモデルでそれを屁尖 ? 輝rg喘されていた Snapshot Isolation をちゃんと根めたことは寄きい ? (このY創ではh苧してないけど) ? 2022定からて ? Predicate をMzむのは庶だと湖じるし、Adya の屁尖は蛍かりにくい (咾魴屬韻討眩爾い里任) ? もう Mono-version のモデルからhを兵めるのをやめましょうよ 20

More Related Content

Isolation Level について

  • 2. 古勣 ? 喘Z屁尖 ? Serializability, Isolation, Consistency´ ? ＳＱＬ覆 Isolation Level ? Adya の屁尖 2
  • 3. Serializabilty ? 晩云Zでは仝岷双晒辛嬬來々 ? トランザクション_を岷双にg佩したのと吉と恂せること ? View 吉 (吭龍 Herbrand semantics でも吉) ? Conflict 吉 (Qいやすくするため View 吉より崙sがい) ? Linearizability (侘晒辛嬬來) とはなる古廷なので廣吭 ? Linearizability は仟しいデ`タをiめる來|(トランザクション渇鵐淵) ? Operation 1 しか根まないトランザクションの鹿栽という協の圷で、 Linearizable = Strict serializable 3
  • 4. Consistency という冱~の詞岱 ? (1) ACID の C(consistency) ? DBMS がアプリケ`ションに戻工するデ`タベ`ス彜B崙sC嬬 ? (2) K双蛍柊順晢の Consistency ? 仟しいデ`タをiめるか(or 匯來のあるデ`タをiめるか) ? (3) Adya1999 の Consistency ? Isolation とあまり曝eしてないが Realtime 來のが飛孤秘ってそう ? ﾚい吭龍では Isolation も根め Consistency と柵びたい(by 佛勸) ? アプリケ`ションがデ`タとその尅る玲いに箔める音簗周を困燭垢海箸 ゴ`ル ? しばしば圧a議 (箭: Sequential consistency でないとバグるアルゴリズム) 4
  • 5. Isolation Level とは ? Serializability が圀しいけど、來嬬とのトレ`ドオフがある ? みんな寄挫き Snapshot Isolation、Read Committed、Repeatable Read´ ? Serializability の隠^がなくても怎りることもある ? アプリケ`ション箸 DBMS にiみ篠る駅勣もしばしばある (Select に For update をつけるとか、電麿喘の Record を喘吭するなど) ? Level (粁A) 湖がある ? SQL片ｸ颪任榔承韻 Level としてｶ┐気譴討い ? 輝rは Level とか Degree などの冱~で燕Fされていた by Adya 5
  • 6. SQL片ｸ ? ANSI X3.135-1992, American National Standard for Information Systems C Database Language C SQL, 1992 ? いわゆる SQL92 ? 恷仟は SQL:2019 (たぶん) ? Isolation 巓りは笋錣辰討覆い繁爾錣譴 ? 仝F鵝(or 尅玲い)を圷にした Informal な協x by Adya ? 2 宥りの盾: Anomaly 盾と Preventative 盾 6
  • 7. SQL覆砲ける仝F鵝垢侶幗 ? Anomaly 盾は}があるので Preventative 盾が念戻 by Adya ? P0: ?1 と ?2 が ? を Concurrent に Write (どちらのY惚を火すか音苧) ? P1: ?1 のいた ? を ?1 commit 念に read し、?1 が abort する (?2 は commit 音辛嬬) ? P2: ?1 がiんだ ? を ?1 が commit する念に貧きする (?1 は ?2 のいたものをiむべき) ? P3: ?1 が predicate read して ?1 が commit する念に predicate read のY惚が笋錣襪茲Δ きzみをする (?1 は ?2 の筝を郡啌した predicate read Y惚をQyすべき) 7
  • 8. SQL 覆 Isolation Level ? SQL 覆 Lock による CC (Concurrency control) Oにべったり ? SQL 覆 Serializable を(ここでは) ANSI-Serializable と柵ぶ 8
  • 9. Bere1995 ? A Critique of ANSI SQL Isolation Levels ? H. Berenson, et al., 1995, SIGMOD Conference ? ANSI-Serializable は Serializable じゃないよ ? Snapshot isolation (SI) は ANSI-Serializable だけど Serializable じゃないよ ? SI では Write skew anomaly がk伏するよ ? (瘁の猟で、SI では read-only transaction anomaly もあると登苧) ? (Anomaly 盾は屎しくない、と冱ったのもこの猟 by Adya) 9
  • 10. Adya1999 ? Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions ? Atul Adya, 1999, Doctor Thesis ? モチベ`ション ? SQL覆 Isolation Level 娠柩してくれ ? ? より措い Isolation 蛍(のためのモデル)の戻宛 ? 廣吭泣 ? Adya は MVCC や OCC をy匯議にQうため Version order を児覆砲靴 Conflict を協xするが、ここでは殆岷に (Write) operation order を喘いる 10
  • 11. Adya1999 が峺姜する SQL 覆}泣 ? 協xが畸舛任△ ? (Anomaly 盾はg`っているので Preventative 盾を聞うべき by Bare1995) ? Lock 念戻のMみなので、喘議ではない ? (Preventative 盾だと) 崙浹弔垢て、恷除の CC protocol (OCC とか MVCC) が揖吉の Isolation level において宥すスケジュ`ルがｸ颪任`郡Qいとなっ てしまう ? CC Oやg廾卆贋だけでなく、喟A晒にvする噫な來|が詞ざっている (勣_J) 11
  • 12. Isolation vS by Adya ? PL-1 ? PL-2 ? PL-2.99 (Repeatable Read) ? PL-3 (Full Serializability) ? PL-2+ (Consistent View) ? PL-SI (Snapshot Isolation) ? 麿 12 Figure 4.1 A partial order to relate various isolation levels.
  • 13. Adya1999 の蛍 (匯何) ? モデルを喘いて苧_に、G0, G1, G2 麿の鋤峭するF鵑魘x 13
  • 14. Adya1999 のモデル ? 愔瓦 Page model (for mono-version) ? }方のオペレ`ション (Op) から撹るトランザクション (Tx) が}方 ? Op は麼に read/write ? Op order が嚥えられる (Tx の Concurrent g佩を Op order における Interleaving で燕F) ? Standard version function (Op order における岷念の､鰌iむ) が念戻 ? Adya は愔瓦 Page model を ? Conflict-based アプロ`チ ? いわゆる w-r、w-w、r-w vSでグラフ夛を恬って Acyclic かどうか ? Op order の旗わりに Multi-version 鬚韻 Version order を聞喘 ? だから愔瓦 Conflict serializability での協xとは飛孤なる ? Phantom もQうため Predicate read/write が Op として秘ってる 14
  • 15. Conflict of Adya1999 ? Directly read-dependency ? reads-from vSのこと (岷念の write と read のvS、倭xの w-r) ? Directly write-dependency ? BAする write と write のvS (倭xの w-w) ? Directly anti-dependency ? read と、それを岷俊貧きする write のvS (倭xの r-w) ? Directly conflict := Directly read/write/anti dependency ? Dependency := Transitive read/write dependency ? Conflict := Transitive conflict ? Predicate jみのものも根まれるが}jなので福待 ? Adya1999 では Version order の仝岷念々だが、gのため Op order を聞喘 15
  • 16. DSG (Direct Serialization Graph) ? Direct conflict vSからBした Graph 夛 ? DSG = (V, E) where ? V: Transactions ? (t1, t2) in E: t2 directly depends on t1 ? (Transitive) conflict は Path 16
  • 17. Condition G0 ? G0: Write Cycles ? Write dependency のみで撹される DSG の Cycles ? PL-1: G0 を鋤峭 ? 侭湖 ? Mono-version 念戻なら蛍かる ? Multi-version だとそもそも Version order だけで Order になってないとい う彜rに鬉垢襪里妊皀妊襪忘める吭龍を湖じない 17
  • 18. Condition G1 ? G1a: Aborted Reads ? ?1 ? ?2 ? ´ ?1?2 ? G1b: Intermediate Reads ? ?1 ?1? ?2 ?1? ?1 ?1? ´ ?2 ? G1c: Circular Information Flow ? Dependency のみで撹された DSG の Cycles (G0 を根む) ? PL-2: G1 (= G1a+G1b+G1c) を鋤峭 ? 侭湖 ? G1a は喟A晒勣周だと房う(から CC はvSない塗) ? G1b は two-step model ではk伏しないから CC Oのにえる 18
  • 19. Condition G2 ? G2: Anti-dependency Cycles ? ひとつ參貧の Anti-dependency を根む Cycles ? PL-2.99: G1 と G2-item (predicate 茅く) 鋤峭 ? PL-3: G1 と G2 鋤峭 19
  • 20. まとめと湖 ? SQL覆 Isolation Level にはN？の}があった ? Adya1999 は苧_なモデルでそれを屁尖 ? 輝rg喘されていた Snapshot Isolation をちゃんと根めたことは寄きい ? (このY創ではh苧してないけど) ? 2022定からて ? Predicate をMzむのは庶だと湖じるし、Adya の屁尖は蛍かりにくい (咾魴屬韻討眩爾い里任) ? もう Mono-version のモデルからhを兵めるのをやめましょうよ 20