Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?

Coordination-Avoiding Database Systems 解説

自己紹介

  • @kuenishi
  • Basho Japan, KK
  • WE ARE HIRING
  • Riak CSの開発してます
  • モチベーションは…

Coordination-Avoiding Database Systems

  • Authors - All Big Names

  • Peter Bailis - CAP定理とトランザクションがテーマ pubs @ UCB

  • Alan Fekete - 言わずとしれたRDB界の大物

  • Micheal J. Franklin - TelegraphCQとかSparkとか @ AMPLab

  • Ali Ghodsi @ UCB

  • Joseph M. Hellerstein - TelegraphCQとかCALMとか @ UCB

  • Ion Stoica - Chord DHT とか @ Co-dir of AMPLab

  • To appear, VLDB 2015

  • arXiv

High-level Background

CAP Theorem

  • CAP Theorem (Brewer 1998, Nancy Lynch 2002) で、高可用な分散トランザクションはムリだと証明された
  • "Atomic Object" vs Network Separation vs Availability
  • なので、トランザクションや、ConsistentなレプリカがなくてもDynamoやCassandraのようなデータベースが登場(もしくはMemcachedの分散したやつなど)した
  • つまり、データが一貫していて(=複製が必ず一致していて)、高可用で、ネットワークが切れても動く、データベースはつくれない
  • 2つを選んでつくることはできる

Optimistic Replication

  • Atomic Broadcast がなくても(=Linearizableな更新でなくても)よいデータの一貫性を再定義すればよい

  • 操作の順番を入れ替えてもよいようなデータ構造、データ型、操作体系

  • w2(w1(x)) -> x2 && w1(w2(x)) -> x2

  • Boom (Overlog, Bloom, CALM ~2010 by J Hellerstein)

  • CRDT (Mark Shapiro 2009, Riak 2012)

  • Operational Transformation (?)

  • Many Giants before

  • ○Partition Tolerance

  • ▲できることが限られる(Bank Accountingのようなことはできない)→Doesn't fit all size

Distributed Transaction

  • 2PCなどの技術は古代からあったが、Coordinator(TM)の故障やネットワーク分断に弱かった
  • いわゆるSerializableなやつ、だが、本当にアプリの全ての操作に必要なのか?

というわけで問題

CAP定理の壁を超えつつ
アプリケーションレベルのCorrectnessを保証しつつ
性能も出るデータベースを考えよう。

方法、考え方

  • いわゆるAtomic Broadcastに類するものデータ更新はPaxosやRaftのようなCoordinationが必須(論文では直接言及していないが)
  • Coordinationが必要なので当然CAP定理に抵触する
  • データベースのワークロードを分析して、Coordinationが必要ないものと必要なものに分類しよう
  • Coordinationが必要十分に行われるようにしたい

I-confluentな操作

「Coordinationが必要ないものを必要十分に選定するための条件として、 I-Confluence というのを考えてみた」

confluence: A社の有名CMS 合流、集合、集約

Definitions

  • DB: Replica

  • Transaction T: DB -> DB

  • Merge Operator ⊔: DB x DB -> DB (Square Cup, U+2294 )

  • Invariants I: DB -> {true, false}

  • "Database state D is I-valid iff I(D)=true"

  • Availability: トランザクションTがどんなときでもデータにアクセス可能で、Tのレプリカ状態によっては正しくアボートされる

"A system provides transactionally available execution iff, whenever a client executing a transaction T can access a server for each item in T , T eventually commits or otherwise aborts itself either due to an abort operation in T or if committing the transaction would violate a declared invariant over T ’s replica state."

  • Convergence: replicaがDivergeしてもものすごい遅延が起きても全てのレプリカが同じ状態に収束すること
  • Validity: a system is globally I-valid iff all replicas are I-valid
  • Coordination-free execution: 全てのレプリカが全く通信しなくても複数のトランザクションを順番に実行できること

I-confluence

  • S: transacation
  • D: database state
  • I: I-validity check output

Definition 6 (Valid Sequence). Given invariant I, a sequence Si of transactions in set T, and database state D, we say Si is an I-valid sequence from D if ∀k ∈ [1,n],tik(...ti1(D)) are I-valid.

Definition 7 (I-confluence). A set of transactions T is I-confluent with respect to invariant I if, for all I-valid database states Ds = S0(D0) where S0 is an I-valid sequence of transactions in T from D0, for all pairs of I-valid sequences S1,S2 of transactions in T from Ds, S1(Ds) ⊔ S2(Ds) is I-valid.

「どんなトランザクションS1とS2についても、それがI-valid sequenceなら、バラバラにレプリカを更新してMergeしても、その結果もI-validである」

記号的に解釈すると…(たぶん)

S1 & S2 => T, I(S1(S2(Ds)))=true and I(S1(Ds) ⊔ S2(Ds)) = true

See Figure 4

Theorem1. A globally I-valid system can execute a set of transactions T with coordination-freedom, transactional availability, convergence if and only if T is I-confluent with respect to I.

証明はAppendix B.

ひとことでいうと "I-confluence captures a simple (informal) rule: coordination can only be avoided if all local commit decisions are globally valid (i.e. merging all local states satisfies invariants)." 「I-confluenceはつまり簡単なルール、Coordinationを避けられるのは、ローカルでのそれぞれの更新が全てGlobally valid(=マージしてもInvariantが壊れない)ときだけ」

理論は分かった、実世界で使えるのか

  • ○Coordinationしなくても更新できるので速い、並列処理できる(かもしれない)
  • ○ネットワークが分断していても更新できることがある、その条件が判明している
  • ▲全ての操作がI-confluentかどうか知っていなければならない(=アプリケーションが教えてあげないといけない)
  • ▲まちがってI-confluentでないものをそうだと指定してしまったらデータが壊れることだってありうる

SQLのなかでの構造、操作

Relations, Data Types それぞれが守るべきInvariantsの典型の話をしている

See Table 2;

証明はAppendix-Cをみる

TPC-C

See Table 3;

TPC-Cでの性能測定

  • オンメモリ
  • JVMで、EC2で大きめのインスタンス
  • 2PLのふつうのDistributed TransactionするDBと比較

いくつかWorkaround

  • 3番 "New Order ID" はTPC-CではSequencial Auto Incrementになっているけど、とりあえずSeqじゃないIDを生成してRAMPで更新しておいて、Masterに変換テーブルを持たせておいた
  • Each New-Order transaction generates be- tween 13–33 reads and 13–33 writes, so switching to an event-based RPC layer with support for batching and connection pooling de- livered an approximate factor of two improvement in throughput,
  • while additional optimization (e.g., more efficient indexing, fewer object allocations) delivered another factor of two.

結果

  • 40K tps vs 600K tpsで、それなりにスケールアウトする

  • 200台のときは12M tps

  • Figure 5, 6

  • プロファイルもしてみたが、処理時間のほとんどはローカルのデータ更新でCPU boundだった(一方2PCだとロック待ちが長くなってくる)

まとめ (contribution)

  • coordination-free executionかどうか判断するのに必要十分なのがI-Confluence
  • replica同士が通信しなくてもうまくexecuteする方法を発見した
  • アプリ全体で必要なinvariantを知るだけで十分>プログラマーの負担が軽減

Questions

  • TPC-Cの実験でI-Cなのが分かったデータ、下回りのデータ構造は明らかにされていない(おそらくCRDTだと思うのだが…)
  • RPCでバッチにしたとかPiggy Backで頑張ったとかそのあたりよくわからない
  • 参考文献多すぎ
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment