NoSQLの整合性担保 -AmazonとGoogleの思想の違い(Part2)
どうも、ITコンサルタントのShoheiです。
今日は僕の前回記事の続きで、NoSQLの主要2種について解説をしていきましょう。
少しだけ前回のおさらい
前回、NoSQLのアーキテクチャには２タイプあるという話をしましたね。
GoogleのBigtableはマスタ型を取っており、AmazonのDynamoはP2P型です。
またCAPの定理により、Consistency(整合性), Availability(可用性), Partitions(分断体制)の3つを同時に満たすことはできない、という説明をしました。
複数ノードでの稼働を前提とすることが多いNoSQLではPを譲らないものが大半という話もしました。
下の図のように、Dynamo系はAP,Bigtable系はCPを担保するDBと言えます。
ではここからは、Dynamo系とBigtable系の違いについて、もう少し突っ込んで説明していきましょう。
整合性担保の仕方の違い
異なる点の一つとして、整合性の担保の仕方が違います。
その前に整合性の解説ですが、整合性とは、読み出したデータが矛盾を生まないこと、でしたね。
下の図は、整合性が担保されていない例です。
データが複数ノードで読み書きされるケースを想定していますが、同時に犬さん口座からの引き落とし作業と振り込み作業が行われた際、両方が両方のリクエストをそのまま受け付けているために、データが一致しなくなっています。
これでは、システムの何を信じたらいいかわからない致命的な状況になっています。
RDBの場合の整合性担保方法
では、従来型RDBでどのようにこの整合性を担保してきたかについて、一例を挙げて説明します。
下の例では、書き込みの受付をノードAに絞っています。もし同じレコード(この場合"犬さん残高")への書き込みが同時にあった場合、一方をブロックしています。
少し正確に言うと、"5千円の引き落とし"というクエリが走っている間、"犬さん残高"のレコードへの書き込み(または読み書き)はロックされています。
ロックはいつ解除するかというと、書き込みに関連する作業が全て終わったタイミングです。諸々設定やポリシーによりますが、例えば、更新があった箇所をノードAのディスクに書き込み、ノードBにその変更を伝えたタイミング、などとなります。
ノードBは何のために存在するかというと、データを失わないためのバックアップであったり、読み専用のノードだったりします。あくまで書き込みはノードAですべて受け付けよう、というものです。
ただ御察しの通り、書き込みの受付が一つのノードに限定されるということがネックになり、大量の書き込みが行われるWebシステムなどでは限界がある、というのが難点です(複数ノード書き込みを許容するRDBは少ないのです)。
Bigtableの場合の整合性担保方法
Bigtableの場合、書き込み自体はどのノードでも受け付けます。
ただし、どのノードがどのレコードに関する書き込みを受け付けるかが、決まっています。
例えば以下のように、ユーザIDが偶数の場合はノードAで書き込みを受け付け、奇数はBで、というもの。そして書き込まれた変更点は同期的に複数ノードに伝えられ、そこまで完了してから書き込み完了とします。
こうすることで、書き込み対象のノードを分散させつつ、同時書き込みによる不整合を防ぐことができます。
またもっというと、ノードをさらに追加しても、自動で担当を振り直してくれます。「じゃぁ僕はユーザIDの末尾が1,4,7のものを担当するよ、君は2,5,8ね、君は3,6,9をよろしく」といった具合にです。また「ユーザID末尾が1のものが書き込み多くてノードAが辛いから、4,7の書き込みはノードBとCに担当してもらおう」という負荷分散も行われます。
Dynamoの場合の整合性担保方法
さらっと書きましたが、上記の例では変更内容は複数ノードに同期的に伝えられるため、不整合が生じることはほとんどありません。これは「強い整合性」と言われており、ノードによって異なる値をもつというのを禁じるのがポリシーです。CAPのCが強く守られているのがこのパターンです。
一方Dynamoの場合は「弱い整合性担保」がポリシーです。
これは一体何かというと、「いや、たとえ全てのデータベースで同じ値を持ってなくても、結果的に正しいものがどれかわかればよくね？」という考え方です。
そのための考え方の一つであるQuorumについて簡単に説明します。
Quorum(クォーラム)とは
Quorumは、元々「(議決に必要な)定足数」というい意味です。Quorumによる整合性保証は、以下のように表されます。
R+W>Nの場合、整合性が保証できる
N:レプリカの数
R:ノードから読み出す数
W:ノードに書き込む数
意味がわからないと思うので、まずはこの原則が満たされていない例から説明しましょう。
以下のように、読み込みたいデータが３つのノードに格納されているとします（N=3)。
最新情報は１つのノードだけに書き込まれました(W=1)。
この状態で一つだけのノードからデータを読みだした場合(W=1)、残念ながら正しいデータ(書き込みが反映されたノードが持っているデータ)を読みだせる確率は1/3ですね。2/3の確率で間違ったデータを引いてしまいます。これは、R+W(=2)<N(=3) であることからわかるように、Quorumの原則が満たされていません。
確率が低ければいい、という話でもなく、間違ったものを引いてしまう可能性がある時点で、データベースとして使えなくなってしまいます。
では、上記の原則が満たされている場合はどうでしょうか。
以下の例をご覧ください。
ここでは N=3, R=2, W=2です。
R+W(=4)>N(=3)となっており、Quorumの原則を満たしていますね。
そのため、たとえ読み込んだ2つのノードのうち、一方の情報が古かったとしても、もう一方の情報を採用することで正しいデータを引いてくることができます。
ただし、お察しのように、WとRの数を増やしているので、その分処理時間は長引いてしまいます。
上記の例では、書き込み時刻(Timestamp)が新しいものが勝つというシンプルなルールでした。ただサーバ間で完全に時刻を一致させることが難しいなどの壁もあります。
他の整合性担保方法として、ベクタークロックなどの技術もあるので、もし興味があれば調べてみてください。
まとめ
今日は、BigtableとDynamoの整合性担保の方法の違いについて説明しました。
次回はそれぞれでどのようにデータ書き込み先を判断しているか、もう少し詳細にお話ししたいと思います。
