分散データベースのレプリケーション: Designing Data-Intensive Applications 第5章より
ネットワーク越しにつながった複数のマシンに、同じデータのレプリカを作成して保存する。「ネットワーク越しに」というのが難しいところで、ネットワーク障害が起きたり、コピー先のマシンが死んでしまったり（ネットワーク越しに生死を確認するというのもまた難しい問題になる）、データセンターが核攻撃されて消滅してしまうまで、あらゆる問題は現実に起こりうる。もし明日、太陽が急膨張して地球を飲み込んで人類の遺産が根こそぎ蒸発するのであればデータの行方がどうなろうと知ったことではない。しかしそうでもなければ有事に備えてデータの完全なレプリカを保持することが要請されるだろう。
これは分散データベースの問題である。レプリケーションにまつわる議論は70年代から存在していたものの、現実に分散データベースが構築されるようになったのは比較的近年のこととなる。主流の考え方は次の三つといえよう。
これらの分類に加えて、さらに考慮すべきトレードオフが存在する。「結果整合性」というコンセプトも関わってくる。そうした最低限の知識のイントロダクションとして、数回にわたって一連のノートを書く。個別のトピックは独立した記事にまとめることにして、以下のセクションにはインデックスとしてリンクをおいていくことにする。
ノートの参照元は DDIA である。完全な翻訳を掲載する権利も意思ももとよりなく、あくまで個人による要約である。同書を読んでいるひとはこれらを読む必要はないし、そうでない人にとっても、正確な情報としては正式な翻訳を参照いただくのが好ましい。
単一リーダーレプリケーション
複数のノードのうち任意の一台をリーダーとして選出して、リーダーノードがすべての書き込みを受け付ける。残りのノードはリードレプリカとして、読み込みリクエストのみを受け付ける。フォロワーはリーダーからレプリケーションログを介して変更差分の通知を受け取る。レプリケーションログに沿って、リーダーログの書き込み履歴を完全に再現して実行し直すことで、データの複製を構築する。
任意の一台が排他的に書き込みを受け付け、書き込みログをリードレプリカに伝播させる。この方式はもっともシンプルで代表的なレプリケーション方式である。主要な RDBMS はこのレプリケーション方式をサポートしているし、 MongoDB や RethinkDB といった NoSQL 製品から Apache Kafka や Rabbit MQ といったメッセージブローカーまで、採用例は多い。
- 同期レプリケーションか、非同期レプリケーションか - ﾕﾕﾕﾕﾕ
- 新しいリードレプリカをクラスタに追加する - ﾕﾕﾕﾕﾕ
- ノードのダウンに対応する - ﾕﾕﾕﾕﾕ
- レプリケーションログの実装 - ﾕﾕﾕﾕﾕ
- レプリケーションラグと結果整合性 - ﾕﾕﾕﾕﾕ
複数リーダーレプリケーション
基本的には単一リーダーレプリケーションのボトルネックを解消する目的で提案されるレプリケーション方式であると言える。この設定下においては、クラスタ内の複数のノードがリーダーとして書き込みを受け付けることが可能であり、それと同時にリーダー間で非同期にレプリケーションを行うこととなる。
結論として、複数リーダーレプリケーションは発展途上のパラダイムであり、安直な技術選択によって導入できる類のものではない。実用としては避けるのが望ましい。
リーダーレスレプリケーション
リーダーだけが書き込みを受け付けるという点において、単一リーダーレプリケーションと複数リーダーレプリケーションは同じパラダイムに属しているといえよう。対して、リーダーという地位を廃止してレプリカが自身の裁量で自由に書き込みを実行するリーダーレスモデルというものがある。分散ストレージ研究の歴史においては根強い伝統を伴ったコンセプトであるものの、リレーショナルデータベースの時代には忘れられかけた技術であった。
Amazon の DynamoDB がその状況を突破し、新しい風を吹き込んだ。 Riak, Cassandra, Voldemort といった製品が後に続いたことで、リーダレスレプリケーションというモデルが再び日の目を浴びるようになった。というと素晴らしい話のように聞こえるが、もちろん新しい毒も伴うことになる。設計の違いはデータベースの使われ方にも本質的な転換をもたらした。
並行書き込みを検知する
リーダーレスデータベースは書き込み時コンフリクトに対してひどく脆弱である。クオラムが満たされていても並行書き込みによるコンフリクトは起こりうるし、リードリペアの際にもコンフリクトしうる。さらには書き込み可用性を高めるためにクオラムをぞんざいに扱うというオプションも存在し、こうなると書き込み結果の不整合はどうしようもなく拡大する。
なにをもって並行とするかは認識論的にしか定義しえない
並行とはそもそもなにか。任意のふたつのリクエストについて、客観的な立場からそれらが並行しているか直列であるかを言い当てることは原理的に不可能である。リクエストを発する主体が、異なる処理の結果を知った上で書き込みをおこなえばそれは直列であるし、知らずに書き込みをおこなえばそれは並行することになる。つまり認識の位相の問題であるわけである。
こう言い換えることもできる。すなわち並行性とは時間によって定義されるものではない。物理的思考においてこれは正しいが、計算機的思考においてこれは成立しない。なぜならネットワークは無制限に遅延するものであるため、リクエストが送信した時刻やリクエストが処理された時刻を点として観察することにはなんの意味もないためである。
その上で、並行関係を補足するためのアルゴリズムを考えてみよう。
並行関係を補足するためのアルゴリズム
簡単のためにレプリカがひとつしかないとする。例えば、リクエストとレスポンスにバージョン番号を含めることで、「クライアントはどこまで知っているか？」を追跡することができるようにできる。
これにより、書き込みリクエストとして送信されたデータを消失させてしまうことは常に避けられるようになる。その一方で、ひとつのバージョンに複数の値が含まれることが起こりえ、それをマージする必要も生じる。競合する値を union して返すのがもっともシンプルな実装になるが、その場合でも削除操作をどう記録するかを考慮する必要はある。削除フラグ（ tombstone ）を含めて union できるようなアルゴリズムを用意するのがよいだろう。
この考え方を複数レプリカ間でのコンフリクト解消に拡張してみよう。同じようにデータのバージョン番号をリクエストとレスポンスに含めてやりとりする方針は有効である。ただしバージョン番号はレプリカごとに割り振られるものとして管理しなければならない。言い換えると、レプリカごとにバージョン管理ができていれば、あるノードから読み込んだ値を別のノードに書き込んだとしても、データの損失は発生しないということになる。この仕組みのことをバージョンベクターという1。
Sloppy Quorums and Hinted Handoff
クオラムが適切に設定されていれば、システム全体の可用性は確かに高まる。とはいえクライアント側のネットワーク障害など、クオラムが満たせなくなる状況は容易に生じうる。システムとして問題があるわけではないのだが、クライアントの視点からはシステムがダウンしているように見えてしまうケースがあるわけである。
とりわけ、ノードの総数 n がおおきくなるほどにこれはボトルネックになる。 n = 101 のクオラムにおいてクライアントが書き込みを成功させるには少なくとも w = 51 に対してリクエストを送信しなければ先に進めないことになる。
このときトレードオフがせまられる。クオラムを遵守し、クライアントのネットワーク環境が改善するまでエラーを返し続けるか、とりあえず到達可能なノードに書き込みを行うだけで処理を続行させてしまうかの択である。後者の「とりあえず書き込んで処理を続ける」という方針を sloppy quorum とよぶ。「ぞんざいなクオラム」とでも訳せるか。
とりあえずの書き込み先のノードはクオラムを構成する n 件に含まれていなくてすらよい。手近で適当なストレージに一時的に書き込んでおくだけでも成立する。ただしこれはあくまで一時的な措置であり、状況が改善し次第、書き込みを受け入れたノードはデータをあるべき正しいストレージに転送しなければならない。これを hinted handoff とよぶ。「やっかいばらい」とでも意訳しようか。
これらの戦略によって、書き込み時の可用性を向上させることが可能になる。引き換えに犠牲となるのはデータの整合性である。クオラムをぞんざいに扱うわけであるから、たとえ外目には w + r > n が成立していても、不整合が発生する蓋然性は通常以上に高まる。
リーダーレスレプリケーションとクオラム
リーダーレスデータベースにおいて、仮に書き込みに失敗したノードがあってもクライアントは失敗を無視して処理を継続できると述べた。ただしこれは文面ほど無秩序ではない。極端な話、すべてのノードに書き込みが失敗したのにクライアントが成功したと思い込んで処理を継続するようなことは許容できない。
クオラムという概念による定式化が可能である。次のような擬似式で端的に定義することができる。
- n: ノードの総数
- w: 書き込み成功に必要なノードの数
- r: 読み込み成功に必要なノードの数
- w + r > n
例えば3台のノードがあるとき（ n = 3 ）、書き込み成功の承認には二台のノードが必要で（ w = 2 ）読み込み成功の承認にも二台のノードが必要であれば（ r = 2 ）、クオラムが成立する（ r + w > n ）。
一般には n を奇数として、 w, r をそれぞれ過半数に設定する構成が採られる。データベースがクオラムを構成するとき、クライアントは n 個のノードに同時にリクエストを行うが、必ずしもすべてのレスポンスを待つ必要はない。書き込み時には w 個、読み込み時には r 個の成功レスポンスが集まれば、その時点でリクエストが成功したとみなすことができる。
クオラムにも限界がある
w + r > n とは要するに、最低でもひとつのノードが w と r の両方の集合に属していることを表している。少なくともひとつのノードが最新の書き込み結果を読み取らせてくれるので、古いデータがレスポンスされることはないように見える。
実際には、 w + r > n が成立している状況でも古いデータがレスポンスされてしまう余地はある。例えば並行して書き込みが行われるような場合、書き込み結果はよくてコンフリクト、悪ければ一方の書き込み結果が失われてしまう。あるいは書き込みと同時に読み込みが行われる場合には、最新の書き込み結果を反映しないレスポンスが返されることもある。さらに、 w 未満の数のノードにしか書き込みが成功しなかったときには、書き込み結果はロールバックされずに残ってしまう。
具体的な例をいくつか述べたが、要はクオラムがあっても完全な整合性を保証できるということにはなりえないということである。単一リーダーレプリケーションでは追加で実現することもできた read-after-write consistency のような制約もリーダーレスデータベースでは実現できない。より高い整合性を求めるのであれば、もとよりトランザクションの採用を検討するべきである。
データの不整合を監視する
古く不整合なデータが残ってしまうことを要件として許容できるとしても、古さの程度に限度はあるだろう。どれだけ古いデータが取り残されているか、監視することはできないだろうか？
リーダー型レプリケーションではレプリケーションログを利用して容易にラグを特定できたものだが、リーダーレスデータベースにおいてデータの古さを監視するのはそう簡単ではない。
まだ一般的ではないが有効たりえるプラクティスとして、古いデータが読み込まれる可能性を定量化する研究は進められている1。ベストプラクティスといえるほど有効で定着するかどうかは時間の判断に委ねるほかないが、監視項目のひとつに含めておくことは損にはならないだろう。「結果整合性」というあいまいな言葉にどれだけの期待をしてよいか、チームの共通認識として言語化しておくことはなにより大切である。
ノードが落ちていても書き込みをおこない続ける
リーダーレスデータベースにおいて、クライアントはすべてのノードに同時に書き込みリクエストを発出し、仮にひとつのノードがダウンしていたとしても気にせずに処理を続行する。読み込みリクエストについても同じである。任意のノードに読み込みリクエストを投げるのではなく、すべてのノードにリクエストをおこない、メタデータによってもっとも新しいデータを識別し、それを最終的な結果とする。
リードリペアとアンチエントロピー
ダウンしたノードに書き込むことはできないのは当然である。そうにもかかわらずリーダーレスデータベースは書き込み失敗を無視して処理を続行する。ここでは明らかに整合性が失われており、なんらかの形で結果整合性がもたらされなければならない。
リードリペア
クライアントは読み込みリクエストを複数のノードに対しておこなう。このうち最新のデータを最終的な値として扱う。言い換えると、このときに古い値をレスポンスするノードは最新の値を知らないことになる。リードリペアとは、古いデータが検知されたときに新しい値に更新することを指す。読み込み頻度が高いほど検出率は上がるので、よく読み込まれるデータほど高い確率で整合する。
アンチエントロピー
リードリペアがクライアントのリクエストを起点に非整合の検出をおこなうのに対して、バックグラウンドで自動的にレプリカ間の差分を探索して同期させる仕組みのことをアンチエントロピーとよぶ。ただしこのアプローチは、どの順序で書き込みが行われたかを正確に識別できないし、非整合が検出され修正されるまでに要するラグが無制限に発生しうる。結果整合性とはいうものの、反映が遅れるデータが常に存在しうるという点で注意が必要となる。
書き込みコンフリクトを制御する
複数リーダーレプリケーションは書き込みコンフリクトの発生を防ぐことができない。またその解消を非同期的に実施する必要がある。「同期的にコンフリクトを検出したい」というのは本質的に単一リーダーがトランザクションで実現すべきことがらであるから、前提として成立しない。コンフリクトが発生することをできるだけ避けるように設定することが可能であっても、可能性をゼロにすることは複数リーダーの性質上不可能である。
複数の書き込み結果が存在してしまうとき、何らかのアルゴリズムによって、それらを最終的な値に解決しなければならない。具体的にはこんなやり方がありうる。
- 書き込みログにユニークな値を付与し、より大きい値を持つ書き込みを優先する
- レプリカごとにユニークな値を付与し、より大きい値を持つレプリカを優先する
- コンフリクトした値を連結（ concatenate ）してしまう
- コンフリクトそのものをデータ構造として保存し、後続の読み込み時にユーザー自身に修正させる
例えば CouchDB はコンフリクト状態を一時的に保存し、読み込みリクエストに対して複数のレコードを返すような実装になっている。コンフリクトの解消はアプリケーション開発者に委ねられており、任意のアルゴリズムで最終的な値を自動的に決定することもできるし、コンフリクトをそのまま表示し、エンドユーザーに修正をせまることもできる。
コンフリクトの解消は得てしてエラーを招きいれやすい。 Amazon のショッピングカートのバグは有名な事例である。カートへの書き込みでコンフリクトが生じた場合は、商品の追加を商品の削除に優先するというロジックにバグが存在し、「カートから商品を削除してもいつのまにか商品が復活する」という奇妙な動作を発生させていたのである1。自動的かつ穏当なやり方でコンフリクトを解消するための方法論はいまだ研究の途上にある。技術として発展途上であるから、一般のデータベース製品においてもほとんど対応されていないというのが正直なところである。
複数リーダーレプリケーションのユースケース
複数リーダーレプリケーションが行われるユースケースを考えてみよう。「データベース」という言葉からくる先入観に必ずしも対応しないものも含めて、いくつものユースケースがある。
まずは複数のデータセンターについて、各データセンターにひとつずつリーダーノードを立てることで、単一リーダーレプリケーションとは異なり書き込みリクエストが単一のデータセンターに集中することを防ぐことを企図できる。ネットワーク障害時にも個別のデータセンター内に閉じて処理を継続できるので、耐障害性は相対的には高くなる。巨大なデメリットとして、個別のリーダーが許可した書き込み内容が後になってコンフリクトを引き起こすことを許容しなければならず、コンフリクト解消の手段を提供する必要が生じる。しかし大規模なデータセンター間で複数リーダーを運用するのは未知の領域があまりに広く、事例も充実していないことから、できる限り避けることが推奨される。
それから、クライアントがオフライン処理をおこなうようなアプリケーションも複数リーダーレプリケーションを行なっていると見立てることができる。例えばカレンダーアプリのように、複数のデバイス上でオフラインで実施した操作を後になって同期するようなケースを考える。この場合、各デバイスはいわばリーダーノードであり、それぞれが受け付けた書き込みを非同期にレプリケートしているわけだ。しかもレプリケーションラグはデバイスのオフライン期間に比例して、1週間や1ヶ月あるいはそれ以上にわたり無制限に長くなりうる。このようなユースケースを目的とした製品としては CounchDB が代表的である。
あるいは Google Docs のように、複数人が同時に書き込みをおこなうことができるようなプロダクトも、複数リーダーレプリケーションの運用であるとみなすことができる。言うなれば、自分の書き込みがまず自分自身のローカルレプリカに保存され、追って非同期にサーバーへ同期されているわけである。こうしたプロダクトは書き込み時にロックを取得しているわけではない。ロックを取得すると言う発想は単一リーダー制の考え方で、複数リーダー制ではキーストローク単位の細かな変更を管理することでロックの必要性を排除するというイメージである。
技術領域として未開拓であり、実装も不十分で予期せぬ罠がそこらじゅうに散らばっているというのが、現状の複数リーダーレプリケーションのパラダイムである。こうした巨大なデメリットを合わせのんでもなお、この手法を採用する覚悟があるか？ ことによっては巨大な投資を要求し、とんでもなくハイリスクなプロジェクトになるかもしれない。そうした負の面を合わせ飲めるのであれば、複数リーダー制も検討に値するかもしれない。
