maedamaのブログ

アプリケーションエンジニアです。最近は主に設計を担当しています。

When to use distributed database system?

背景

DDBSについてあまりきちんと知らなかったので、各DDBSがどのような経緯でうまれているのか、その前提条件をしらべるために以下の記事を読んだのでそれについて。

http://cs-www.cs.yale.edu/homes/dna/papers/abadi-pacelc.pdf http://www.cs.berkeley.edu/~rxin/db-papers/CAP.pdf

下記は文献から得た知識を自分の意見も交えてまとめたものです。以下メモみたいなものなので、間違いもあるかもしれませんし、きちんとcitationできてないですがご了承ください。

CAP定理

RDBSやDDBSの文脈でよく登場するのがCAP定理です。 まず、CAP 定理 自体は Node partition が発生したタイミングで ACID を実装する データベースがとりうる選択を示しています。以下の三つ

  • (Perfect) Consistency
  • (Perfect) Availability
  • (Perfect) Partition tolerance

CAP定理について、よく勘違いされがちがな点がここにあります。一つ目があくまで Node partition が発生した際の挙動に関する言及であるという事(そうでない場合はConsistency + Availabityを両立することは可能)。二点目が 全ての要素についている Perfect です。

CAP定理自体は数学的にも証明されてますが、データを分散してもってる Nodeが完全に分断された状態で、それぞれにConflictするデータ更新Requestを送った際の挙動をどう扱いうるのかというのが本質的な問題状況です。

それぞれの更新処理がConflictしており、かつお互いに通信ができない状態で Partition tolerance (システムとして稼働することろ) を実現すると、

  • ACIDを満たす Consisitency を犠牲にして、双方の 要求をうけつけて、Partition 復活時に 何らかの復旧処理をする(Last writeが勝つとか)
  • Availability を犠牲にして、一方ないしは双方の要求を棄却する

のいずれかの二択しかとれないという事を示しています。

例えば私が所属している会社では MySQL + MHA でハッピーライフをおくってます(AWSのRDS+自動Fail overもだいたい同じような構成だと思います)が MHA時には瞬間的に更新処理ができなくなるので、AvailabilityはCAP的な意味では犠牲になっています。 でも実運用としてそれでほとんど困ってません。

それは以下のような理由からです。

  • Node partition がMySQLが利用される環境だとかなりのレアケースであることが多い
  • Availabilityは完璧ではないがかなり高いので、実運用として困るレベルにない

ちなみに、Partitionが頻繁に発生するような環境で動くデータベースももちろん存在します。google spread sheetとかgitとかその良い例です。gitは Availabilityを重視していて、offlineだろうが、localのデータベースにいくらでもcommitできます。が復旧して、masterにmergeしようとすると場合によってはconflictしたりして、merge不可能な状況が発生します。

Why not RDBS?

僕RDBS大好きです。でも、RDBSに適さない要件がいくつか発生したからDDBSが生まれたはずでそれは何なのか？

多分、多くはCAPではないでしょう。CAP的な意味では実運用上はほとんど困らない事が多いと思います(もちろん、要件にもよりますが)。ではなにか？

もともと、RBDSの多くは ConsistencyとLatencyを 重視したシステムでした。それにMHAのような技法が加わり、ほとんどのユーザーケースにおいては十二分なシステム要件だったと思います。特に ACIDを満たす Consistency は非常に魅力的で それに恩恵をえているシステムはとても多いです。

でも、ある日 RBDS では満たせないけど、満たしたくてたまらない要求が生まれます。

  • Scalability
  • Cross region write latency

まず、Scalbilityについてはいわずもがな 多くのRDBSは中央集権的にデータを管理する設計で動いてました。これは ACIDで定義されるConsistency を担保する要求を満たす上での自然な設計です。

同等のレベルの事をやろうとすると 何らかの投票システムのようなものをつかって全員で Transacitonについて合意をとるようなプロセスが要求されるはずです。

この方法は、Write(+ それに付随するデータ量)に関して Scalabilityを担保するのが困難で、Application側でのShardingをしないとScaleしない仕組みになり、LINEやFacebookのような大規模なサービスの登場と主に、既存のRDBSをこえるScalabilityが要求されるケースが多くなりました。

次に重要なのが Cross region Latencyです。MySQLのように中央集権的なRDBSはデータの更新処理や、最新のデータを読み取る処理がある特定のNodeに要求されなければならないという制約が有り、これがGlobalでサービスを展開する上での一つの大きな制約となったでしょう。Readはreplicationの遅延をある程度許容しつつ、Web server等の近くにデータベースをおけばいいですが、更新のRequestが 特定の拠点のマスターのサーバーにむかなければいけないというのは相当つらいです。

地球の反対側にサーバーがあるとすると光の早さでデータが1往復したとしても 130msecくらいかかります。これが理論上の最速の値で、Protocolをどれだけ簡素にしようが、回線をどれだけ高速にしようがこれを上回る実測値はだせません。実際はこれより数段遅くなるはずなので、TCPでconnectionはるためにround tripを繰り返すとかなるとちょっと恐ろしい思いです。

このような事情から、特定のマスターサーバーでデータを管理するのではなく分散システムとしてデータを管理する需要が高まったと想像されます。

Latency Consistency Trade off

さて、上記の点で面白い点が、DDBSにすると、RDBSが抱えていたScalabilityの問題は解決されますが、結局 ACID の consistencyを満たそうとすると、本質的に Cross region write latencyの問題は DDBSにしても問題が解決されません。

距離が離れてるNodeをもつDDBSで Latency (write) を低くするという事はmaster のReplicaを多くのNodeでもつという事と本質的には同じです。

Round tripの時間がボトルネックになる以上、近くにデータがないと Low latency でデータ更新は実現できません。

( 近くにデータをおく手法としてapplication側の性質やhuerisistics を利用する事で高速にする事はできるでしょう。 例えば、Masterデータのshardingのlogicに頻繁に更新される場所を考慮すれば良いわけですから。それは Application側で担保してもいいし、場合によってはデータベース側でそういった仕様をもつというのも面白いかもしれません。更新 Requestのipの分布等を考慮して、masterデータの置き場所を動的にかえていくとか )

しかし、コピー = consistentencyの低下です。

ACIDが定義するようなレベルでのConsistencyを得るためには、中央集権的なシステムまたは何らかの投票システムを利用して、データの更新処理に合意をとる必要が有ります。 一方で World wideなサービスでは合意する上での通信がボトルネックになるわけですから、ここに DDBSのジレンマがあります。

実際、DDBSの多くは ACID を緩和したconsistencyのレベルの BASE を実装しています。BASEはtransaction完了時に、データが更新されて未来永劫変わらないという事を担保しなくてよいので、近くのNodeに対して更新Requestを送った場合、そのNodeが投票をせずして transactionの結果について自ら判断できます。

もちろん BASE になることにより、システムの実装は難しくなる部分はあります。例えば

  • Atomicな処理を DDBSがサポートしてくれない
  • Commit成功しても、場合によっては rollback相当の事が行われる

もちろんこのへんは使ってるデータベースに依存しますし、transactionを発行するタイミングでユーザー側がconsistencyのレベルをcontrollする事もできるでしょう。でも、一般的にはこのへんが RDBS にたいするデメリットになるはずです。

なので、RDBSを離れるべきかどうかは

  • Scalabilityに問題が有る？
  • World wideに展開するサービスで low write latencyを実現したい

あたりがキーになると想像します。前者は Aurora DBがMySQLの５倍速いとうたってますし、SNSでSOA化されたサービスであれば相当大規模にならないと問題にはならないかもしれません。一方で、後者は どちらかというと ACID にまつわる問題なので解決が大変そうです。