WIP【備忘録】DBの論文を読む : 弱い分離と配布

そろそろデータベースに関するちゃんとした基礎知識をつけたいという思いがあるので、Readings in Database Systems, 5th Edition を読んでいこうと思う。
URL: http://www.redbook.io/index.html

この本は、DBに関する古典的な論文から、近年の特に重要な論文まで、章ごとに短い解説とともに紹介されている。

今回は Ch6 Weak Isolation and Distribution を読む。

紹介された論文

  1. Generalized Isolation Level Definitions. ICDE, 2000.

    • あああ
  2. Dynamo: Amazon's Highly Available Key-Value Store. SOSP, 2007.

    • いいい
  3. CAP Twelve Years Later: How the "Rules" Have Changed. IEEE Computer, 45, 2 (2012).

    • ううう

解説を読んだ

この章では、以下のことを説明している。

  • 実際のDBではトランザクション(以下, txn)の分離レベルとしてSerializableよりも「弱い分離レベル」を使用する場合が多いこと、そしてその理由
  • 「弱い分離レベル」が実際に何をしているのか
  • それらについての推論が難しい理由

著者は弱い分離が一般的である理由として、「(必要な?)調整が少ない」「パフォーマンスが高い」「可用性が高い」等を挙げた上で、以下のように述べている。

  • 直列化不可能な分離は、並行性に関して利点があるため(従来のRDBMSと最近のNoSQLの新興企業の両方で)普及している
  • しかし、直列化不可能な分離に関する多くの既存の定式化は、十分に規定されておらず、使用するのが困難
  • 弱い分離の研究は、意味のあるセマンティクスを維持し、直列化可能性を犠牲にすることなくプログラム可能性を改善する方法を示している

「アプリケーション開発者の中には直列化できない分離レベルのもとで実行されている事に気が付かない人がいる」と言われて耳が痛かった...。

なんでこの章でNoSQLの論文が出てくるんだろう?と疑問だったけど、以下のような解説があった。

NoSQLは分散環境向けに最適化された一連の新しいデータストアとして登場したが、その重要な特徴として、NoSQLはフォールトトレランスに明確に焦点を当てて、より弱いモデルを介して操作の可用性を向上させることに焦点を当てていることが多い。

なるほど。

論文1について

Abstruct

  • 現在のANSI規格では分離レベルが定義されているが、それは以下のような問題がある
    • 定義が曖昧
    • ロックに基づいており、「実装に依存しない」というANSISQLの目標を満たしていない
      • これにより、マルチバージョンを含む楽観的アルゴリズムによる分離レベルをカバーしていない
  • この論文では以下の貢献をしている
    • 実装に依存しない方法で既存のANSI分離レベルを規定する
    • さらに、その方法は述語(WHERE)を正しく処理することができる
    • その定義では、コミットされたtxnと実行中のtxnに対して異なる分離保証を行うことができる

要約とメモ

ロックに基づく分離レベルの復習

分離レベルはPhenomenaと呼ばれる良くない動作をどの程度禁止するかという観点で作られていた。
phonomenaとしては以下のP0~P4があった。記法の確認も一緒にして欲しい。

# wn[x]: n番目のtxnにおいてxに対して書き込みを行う
# wn[x in P]: n番目のtxnにおいて述語Pのxに対して書き込みを行う
# rn[x]: n番目のtxnにおいてxに対して読み出しを行う
# rn[P]: n番目のtxnにおいて述語Pのレコードの読み出しを行う
# cn   : n番目のtxnをcommit
# an   : n番目のtxnをabort


P0: w1[x] ... w2[x] ... (c1 or a1)
P1: w1[x] ... r2[x] ... (c1 or a1)
P2: r1[x] ... w2[x] ... (c1 or a1)
P3: r1[P] ... w2[y in P] ... (c1 or a1)

また、ロックに基づく分離レベルを以下のように表としてまとめることができる。

f:id:sereronnrot:20210831235012p:plain
出典 [1]

用語: Long lock ... ロックをかけたtxnがcommitされるまで保持される Short lock ... ロックをかけるキッカケとなった読み取り/書き込み処理が完了した直後に解放される

因みに、ロックは特定の状況(例えば、2つのtxnが同時に同じオブジェクトを変更する)を防ぐことでtxnを直列化するため、このアプローチを予防的アプローチと呼ぶ。

しかし、この予防的アプローチは以下のような問題点がある。 - このアプローチは制限的すぎる。事実、楽観的なマルチバージョン実装を排除している。
- バージョンではなくオブジェクトの観点から記述されているため、マルチバージョンシステムには適用できない - phenomenaが単一オブジェクトの履歴で表現されている - 関心のある特性は、多くの場合複数オブジェクトの制約(ex x+y=10)

例を考える。 x+y=10という制約がある場合において、以下のようなtxnの履歴(history)を考える。

H1: r1(x, 5) w1(x, 1) r2(x, 1) r2(y, 5) c2 r1(y, 5) w1(y, 9) c1
H2: r2(x, 5) r1(x, 5) w1(x, 1) r1(y, 5) w1(y, 9) c1 r2(y, 9) c2

分離レベルはSERIALIZABLE 両方ともT2からは制約が満たされない状態である。(H1はP1に該当, H2はP2に該当)

TODO: 追記

道具の用意1

database model - DBはtxnによって読み書きができるオブジェクトで構成される
- オブジェクトは1つ以上のバージョンを持つ。txnはDBとオブジェクトに関してのみ影響し合う - txnがオブジェクトxを書き込んだとき、xの新しいバージョンが作成されるtxn Tiはあるオブジェクトxiを複数回修正でき、xi:1, xi:2, ...と表記される。 - txnがcommitされた時、xiの各バージョンがcommitされた状態の一部になり、Tiがxiをinstallするという。

transaction hisotires DBのtxn履歴を txn historyと呼び、それは2つの要素で構成される。 - イベントの半順序 E: - Eはtxn内のイベントの順序を保存する。イベントはread/commit等の操作を表す。 - いくつかの制約を持つ。例えば「txnがxを修正した後にxを読み込んだ場合、xの最終更新版が得られる」など。
- バージョン順序 <<: - commitされたtxnによって作成された各オブジェクトのバージョンの全順序 - バージョンxi, xjがあった時、xiがxjより前にあれば、 xi << xj

数学の半順序とは関係ない。たぶん。

historyに関しては、更にいくつかの制約がある。
例えば、もしwi(xi:m), ..., ri(xj)という履歴があり、間にwi(xi:n)がなかった場合、xjxi:mでなければならない。 この条件は「もしtxnがオブジェクトxを修正した後にxを読み込んだら、xの最終更新版が得られること」を保証している。 その他の制約は論文を参照してほしい。

因みに、historyのバージョン順序はHのcommitされたイベントの順序とは異なっており、この柔軟性が楽観的なマルチバージョンに対応するために必要ならしい。
事実、マルチバージョンでは、「xjxiより先にinstallされるが、xi << xj」という状況があり得る。

f:id:sereronnrot:20210831235155p:plain
出典: [1]

predicates txnが述語Pに基づいてread/writeを実行するとき、システムはPのテーブルにある各タプルに対してバージョンを選択する。選択されたバージョンのセットは、この述語ベースの操作のバージョン・セットと呼ばれ、Vset(P)で表現される。

道具の用意2: Conflicts and serialization graphs

まず、txn間のコンフリクトをタイプ別に定義した後、それによってserialization graphを定義する。

まずはコンフリクトの定義。

directory Read-Depends 以下のいずれかの条件を満たすとき、txn Tjがtxn Tiにdirectory read-dependsである。 - directly item-read-depends... Tiがxiの何かのバージョンを install し、Tjがxiを読み込む - directly predicate-read-depends... Tjが rj(P: Vset(P)), xk ∈ Vset(P), i=k or xi << xkを実行し、xi >???

f:id:sereronnrot:20210831235227p:plain
出典: [1]

directly anti-depends 以下のいずれかの条件を満たすとき、txn Tjがtxn Tiにdirectly anti-dependsである。 - Directly item-anti-depends ... Tiがxiの何かのバージョンを読み取り、Tjがxの(xiより)後のバージョンをinstallする - Directly predicate-anti-depends ... TjがTiによるri(P: Vset(P))をoverwriteしてしまう(マッチの結果を変えてしまう)

read, anti depend共に、述語に関しては同じような扱いをしており、述語のマッチ(結果)が変化する時に依存が発生するとしている。

directly write-depends Tiがxiをinstallし、Tjがxの(xiより)後のバージョンをinstallする場合、txn Tjがtxn Tiにdirectly write-dependsである。

Direct Serialization Grpah(DSG) histroy Hから生じるDSGをDSG(H)とする。 DSGはDAGであり、ノードとエッジの定義は以下。
ノード Ti : commited txn エッジ Ti -> Tj : Ti からTjに存在する何かのdirect depends

f:id:sereronnrot:20210831235312p:plain
出典: [1]

注意: DSGはcommitされたtxnの情報しか含まないため、history Hの全ての情報をエンコードしているわけではない。

DSGの例 f:id:sereronnrot:20210831235329p:plain
出典: [1]

f:id:sereronnrot:20210831235336p:plain
出典: [1]

DSGによる分離レベル

ANSI分離レベルに対するDSGを用いた仕様も、これまでのアプローチと同様に、各分離レベルで回避すべきphenomenaの観点から各分離レベルを定義するが、このphenomenaがDSGの形によって定義されているのが大きな違いだ。
以下、DSGによるphonomenaをG0~G2で定義していく。

G0: Write Cycles DSG(H) が write-dependency edgeによる有向閉路を持つ。

f:id:sereronnrot:20210831235352p:plain
出典: [1]

f:id:sereronnrot:20210831235409p:plain
出典: [1]

G1は以下のG1-a~cで構成される。
G1-a: Aborted Reads
abortされたtxn T1とcommitされたtxn T2を含み、T2がT1によって更新されたオブジェクトを読み出している。

例)

w1(x1:i) ... r2(x1:i) ... (a1, c2が発生)
w1(x1:i) ... r2(P: x1:i, ... ) ... (a1, c2が発生)

DSGはcommitしたtxnの情報しか含まないから、abortが絡むと表現が難しくなるのかな?

G1-b: Intermediate Reads commitされたT2が、T1の最終的な書き込みバージョン以外のバージョンのxを読み出している。 例)

w1(x1:i) ... r2(x1:i) ... w1(x1:j ) ... c2

w1(x1:i) ... r2(P: x1:i, ...) ... w1(x1:j ) ... c2

G1-c: Circular Information Flow DSG(H)がread/write-dependencyによる有向閉路を持つ。

G2: Anti-dependency Cycles
DSG(H)がanti-dependency edgeを一つでも含む有効閉路を持つ。

G2-item: Item Anti-dependency DSG(H)がitem-anti-dependency edgeを一つでも含む有効閉路を持つ。

G2-itemはG1より若干ゆるい。 実際、以下のようなhistoryはG2-itemに該当するがG2には該当しない。

f:id:sereronnrot:20210831235421p:plain 出典: [1]

f:id:sereronnrot:20210831235449p:plain 出典: [1]

ここまで定義してきたphenomenaを用いて分離レベルPL-1~PL-3を定義する。

f:id:sereronnrot:20210831235428p:plain
出典: [1]

これで、実装に依存しない分離レベルの仕様を定義することができた。

出典:
[1] Generalized Isolation Level Definitions. ICDE, 2000.

論文2について

Dynamoについては、素晴らしいまとめがたくさんあるので、そちらを参照してほしい。
まずはDynamoDBの公式で概要を把握してから、下記リンクを当たると良いと思う。

論文3について

この論文は日本語訳が出ているので読むときはをそれを参照するのがおすすめ。
https://www.infoq.com/jp/articles/cap-twelve-years-later-how-the-rules-have-changed/

今更なんだけど、この論文を書いたEric Brewer氏はCAP定理を提案した本人のよう。

CAP定理とは、ざっくりいうと以下のことを示している。
「分散システムは、一貫性, 可用性, (通信の)分断耐性のうち、いずれか2つしか提供できない」

ここで、CAP定理における一貫性と可用性の定義について補足する。

  • 一貫性... 線形化可能性という非常に強い一貫性モデル。線形可能性の定義については、このスライドwikipediaを参照。
  • 可用性... 1つ以上のノードに障害が起きてもクライアントに応答を返す

CAP定理の詳しい話はIBMのサイトが分かりやすい。

CAP定理の意味を図でかんたんに説明する。

以下の図のような2つのnodeがネットワークで繋がれた分散システムを考える。
この2つのnodeはネットワークで同期が取れているとする。
また、node1の変更内容が瞬時にnode2にネットワークを伝って反映されるとしよう。
ここで、ユーザがA=1という書き込みをnode1にしたとする。(ユーザ自身はどのnodeに書き込んだかは分からない)
次にユーザがnode2からAの値を読み込むと、A=1が返ってくる。(ここでも、ユーザ自身はどのnodeから読み込んだかは分からない)

f:id:sereronnrot:20210915030328j:plain

ここで、node1とnode2を繋ぐネットワークに障害が発生したとしよう。
この状況でユーザがnode1にA=2という書き込みをしようとした場合、システムの対応として2つ考えられる。
1つ目は、node1に書き込みを許可するパターン。この場合、その後にnode2から読み込んだ場合A=1が返ってくるので、node1とnode2どちらから読み込むかで値が異なる。

f:id:sereronnrot:20210915030339j:plain

これはある意味、可用性を優先し、(node1,2の)一貫性を放棄している。

2つ目は、node1への書き込みを許可しないパターン。この場合も、その後にnode2から読み込んだ場合A=1が返ってくるので、node1とnode2どちらから読み込んでも値は同じ。

f:id:sereronnrot:20210915030349j:plain

これはある意味、可用性を放棄し、(node1,2の)一貫性を優先している。

ざっくり

  • 設計者は一貫性と可用性を最適化し、3つの性質すべての釣り合いを取ることができる
  • 一方で、CAP定理の"3つに2つという表現は誤解を生み、3属性の関係を過度に単純化してしまう
    • ある性質を満たすかどうかの2値判定は極端
    • ネットワーク分断(分割)はめったに怒らず、分断のない状態ではAもCも失われない
    • CAPは遅延を無視している
    • 同じシステムにおいて、様々な粒度・軸でCとAの選択を行える (サブシステム, 操作, 関係するユーザ, ...)
    • 一貫性を失う場合のコストを把握するのは難しい
  • 現在のCAP定理の目的は、特定のアプリに必要な一貫性と可用性を最適化すること
  • 分断が派生した場合のために、分断を検知し明示的に対処する仕組みを作る必要がある
    • 分断の検知-> 動作が制限される分割モードへ明示的に移行 -> 分断中に発生した動作不良を保証(下図参照)

f:id:sereronnrot:20210915030409j:plain

引用: 12年後のCAP定理: "法則"はどのように変わったか

本文で出てくるACID, BASEの説明については、RDSとDynamoDBをCAP定理、ACID、BASEを使って整理するが分かりやすい。

また、CAP定理に関する意見として以下の記事はとても勉強になった。
データーベースをCPだのAPだのと分類するのはやめて下さい