Neunomizuの日記

俺だけが俺だけじゃない

# CMU DB 23. Distributed OLTP Database Systems

CMU DB
tags: CMU DB

授業

OLTP vs OLAP

  • On-line Transaction Processing(OLTP)
    • 短命な読み書きtxn
    • 小さなfootprint(稼働時に占有，消費する資源)
    • 繰り返し処理
  • On-line Analytical Processing(OLAP)
    • 長寿な読み込み専用クエリ
    • 複雑な結合
    • 探索的なクエリ

重要な仮定．分散DBMS内の全てのノードはwell-behaved(性質が規則的で，直感に反さない)で，同じ管理ドメインの下にある．つまり，txnを完了するようにノードに命令したら，失敗せずにtxnを完了するということ．

atomic commit protocols

複数ノードのtxnが終了した際に，DBMSのノードは全ての関連ノードに完了しても安全かどうかを尋ねる必要がある．

  • 2pc optimizations
    • early prepare voting
    • early acknowledgement after prepare
  • two-phase commit(2pc)
    • それぞれのノードが不揮発性のストレージのlogにそれぞれの段階の結果を記録する
    • coordinatorがクラッシュしたら，participantが何をするべきかを決めなければならない
    • partitipantがクラッシュしたら，coordinatorはもし了承が返ってこないときは中断と反応したと仮定する
  • PAXOS
    • 同意のプロトコル
    • coordinatorは結果を提案し，participantsはその結果が成功したかを投票する
  • multi-paxos
    • システムがある期間の間の変化を提案する席にある単一のリーダーを選択するとしたら，Propose phaseを飛ばすことが可能．
    • システムは定期的に誰かリーダーになるかを再び改める必要がある．

replication

DBMSは可用性(availability，システムが安定稼働出来る能力)を増すために，余ったノードに渡ってデータを複製することが可能．

設計指針は

  • replica configuration
    • master-replica
      • 全ての更新はそれぞれのオブジェクトごとに指定されたmasterへ行く．
      • masterは不可分な完了プロトコルなしで，その複製に更新を伝える．
      • 読み込み専用のtxnは複製にアクセスすることを許されるのが当然
      • もしmasterが落ちたら，新しいmasterを選ぶ選挙を開く．
    • multi-master
      • txnはどんな複製のデータオブジェクトを更新する．
      • 複製は不可分な完了プロトコルを使うそれぞれと同期しなければならない．
    • K-safety
      • K-safetyは複製されたDBの耐障害性を決める閾値．
      • $K$はいつも使えないといけないデータオブジェクト1つ当たりの複製の数を表す
      • 複製の数がこの閾値を超えたとき，DBMSは実行を泊めて，それをオフラインに持っていく．
  • propagation scheme
    • 複製されたDB上でのtxnが完了した際に，DBMSはアプリケーションへ承諾を送れる前にtxnの変化が他のノードに伝わるのを待つかどうかを決める
    • synchronous(strong consistency)
      • masterは更新を複製に伝え，それらが変化を完全に適用したという承諾を返すのを待つ．
    • asynchronous(eventual conssitency)
      • masterは複製が変化を適用したことを待たずにクライアントへ承諾をすぐに返す．
  • propagation timing
    • continuous
      • DBMSはlogメッセージを生成したらすぐに送る
      • commit/abortメッセージも送る必要がある
    • on commit
      • DBMSはtxnが完了したらすぐにtxnのためのlogメッセージを複製に送る
      • log recordsを中断したtxnのために送る時間を浪費しない
  • update method
    • active-active
      • 各複製で独立にtxnは実行される
    • active-passive
      • それぞれのtxnは単一の場所で実行され，変化を複製に伝える

consistency issues(CAP)

Consistent + Always Available + Networdk Partitioin Tolerantうちどれか2つしか選べないという理論．

失敗をどう取り組むかが，CAP理論のどの要素に対応しているかを決める．

  • tradiditional/NewSQL DBMSs
    • ノードの過半数が再接続されるまで更新を許すことを止める
  • NoSQL DBMSs
    • ノードが再接続された後に衝突を解決する仕組みを与える．

federated databases

複数のDBMSを繋げて単一の論理システムにする分散アーキテクチャ．

これは難しくて，誰も上手くはやれていない．

  • モデル，クエリ言語，限界が違う
  • クエリの最適化が難しい
  • 多くのデータコピーがある(よくない)

結論

我々の分散DBMSのノードは友好的だと仮定した．

ブロックチェーンDBはノードは対抗的だと仮定している．これはtxnを完了するために複数のプロトコルを使わなければならないことを意味する．

感想

ブロックチェーンまで登場．DBMSは本当に色んな分野の知識が使えて面白そうに思えます．