リーダーレスレプリケーションとクオラム
リーダーレスデータベースにおいて、仮に書き込みに失敗したノードがあってもクライアントは失敗を無視して処理を継続できると述べた。ただしこれは文面ほど無秩序ではない。極端な話、すべてのノードに書き込みが失敗したのにクライアントが成功したと思い込んで処理を継続するようなことは許容できない。
クオラムという概念による定式化が可能である。次のような擬似式で端的に定義することができる。
- 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 のように、複数人が同時に書き込みをおこなうことができるようなプロダクトも、複数リーダーレプリケーションの運用であるとみなすことができる。言うなれば、自分の書き込みがまず自分自身のローカルレプリカに保存され、追って非同期にサーバーへ同期されているわけである。こうしたプロダクトは書き込み時にロックを取得しているわけではない。ロックを取得すると言う発想は単一リーダー制の考え方で、複数リーダー制ではキーストローク単位の細かな変更を管理することでロックの必要性を排除するというイメージである。
技術領域として未開拓であり、実装も不十分で予期せぬ罠がそこらじゅうに散らばっているというのが、現状の複数リーダーレプリケーションのパラダイムである。こうした巨大なデメリットを合わせのんでもなお、この手法を採用する覚悟があるか？ ことによっては巨大な投資を要求し、とんでもなくハイリスクなプロジェクトになるかもしれない。そうした負の面を合わせ飲めるのであれば、複数リーダー制も検討に値するかもしれない。
レプリケーションラグと結果整合性
ひとつのリーダーが排他的に書き込みを管理する方式について検討してきた。この方式によって享受できるメリットはスケーラビリティとレイテンシの向上である。つまり、リードレプリカを追加すれば読み込みをスケールアウトさせられるし、ユーザーの近くにレプリカを配置すれば地理的制約によるレイテンシの問題も解消できる。
他方で、リードレプリカの数が増えるに伴って、非同期レプリケーション化は避けられなくなる。同期レプリケーションにおける障害点がリードレプリカの数に比例するためである。そして非同期レプリケーションを導入すると、整合性の問題に否応なく向き合う必要が生じる。
整合性の破綻とは、リーダーノードとリードレプリカの間でデータが一貫しなくなることである。同期が完了するまで一定の時間をおけば整合性が回復されることは保証される。また通常はコンマ数秒で同期が完了することも期待できる。しかしシステムの負荷が高まったり、ネットワーク全体が混雑するようになると、数秒から数分、あるいはそれ以上にわたって無制限に同期が遅延することは簡単に起こりうる。
最終的にデータは整合するが、時点によっては整合しないことをとって「結果整合性」と呼ばれる。結果整合性は NoSQL の文脈で使われることが多いタームとはいえ、リレーショナルデータベースにおいても分散データベースの文脈では起こりうる問題であるので見落とすことはできない。
結果整合性を前提に、不整合なデータがユーザーに提示されてしまいうるケースと、それに対する防止策を2パターンほど取り上げて検討してみることにしよう。
Read-after-write
書き込みリクエストの直後にリードレプリカに読み込みリクエストを投げるとする。運が悪いと、自分の書き込みが反映されていないレスポンスが返されることになる。しばらく待てば結果整合がもたらされるとはいえ、ユーザーの視点からは自分の書き込みが失われたように見えてしまうわけで、これは小さからざる問題であるといえよう。ここで要求されるデータの一貫性は、書き込み直後の読み込みについての一貫性ということで read-after-write consistency と呼ばれる。
最新の書き込み内容を見せるためには、リーダーノードに読み込みリクエストを投げるようにすればよい。また大切なのは自分自身の書き込み内容が見えることだけであって、他のユーザーにその書き込みを反映させるのが遅れてしまうのは問題にならない。こう考えると解消すべき問題のスコープはいくぶん小さく保てそうだ。ではどうやって、リクエストを転送する前に動的にリクエスト先を判定するか？ いくつかの方法がありそうだ。
例えば SNS のプロフィールページの更新が懸念になっているとする。「プロフィールを編集できるのは自分自身のみ」という前提に立つと、次のように整理することができそうだ。
- 自分のプロフィールページは常にリーダーから読み込む
- 他人のプロフィールページはレプリカから読み込む
あるいは最終書き込み時刻をクライアントに記憶させておき、これを利用してリクエスト先を決定するようなことも考えられる。システム時刻を直接利用すると、クロックラグが生じたりクライアントが時刻を偽装することが可能になってしまうから、何かしらの単調増加する値を利用するなどといったことも考えられる。
複数のクライアントをまたいで read-after-write consistency を実現するのは非常に困難である。具体的には、デスクトップクライアントで更新したデータをモバイルクライアントで閲覧したときにも最新のデータを取得させたい、というような要件のことである。
異なるクライアントに横断的な状態を持たせることは不可能なので、判断材料となる何かしらのメタデータをサーバー側で管理する必要がある。これだけでも管理は複雑になりうる。その上リクエストが複数のデータセンターに分散している状況では、すべてのリクエストをひとつのデータセンターに集約するか、そうでなければメタデータをさらにレプリケーションして分散管理しないといけないことになる。いずれも大変な難事業となるだろう。
Monotonic Reads
複数のリードレプリカ間に不整合が生じることもありうる。例えばまったく同じリクエストが二度繰り返されたとき、はじめにあるレプリカが最新のレコードを返した後で、異なるレプリカが少し古いレコードを返してしまうことがある。ユーザーからみると、まるで時間が巻き戻ったかのような見え方となり、好ましいものとはいえない。
これを防止するために導入される整合性の考え方を Monotonic Reads という。これが保証するのは、新しい状態を一度受け取ったら、それ以降の読み込みではそれより古い状態は取得されないということである。
具体的にいうと、あるユーザーのリクエスト先のレプリカを完全にランダムに振り分けるのではなく、例えばユーザーIDのハッシュ値などを使って常に同じレプリカから読み込むように設定すればこの整合性は保証できる。もちろん、リクエスト先のレプリカがダウンしたときのフォールバック先をどうするかをきちんと考慮するところまで検討しなければならない。
Consistent Prefix Reads
書き込み順序にまつわる因果関係を管理し、正しい順序で情報を提示する整合性についての描写が含まれるが、これについては書き手の咀嚼力が足りずにうまく説明し直すことができないため割愛する。
レプリケーションログの実装
リーダーノードからリードレプリカに変更差分を通知するのはレプリケーションログの転送によってであるとこれまで述べてきた。ではレプリケーションログとはなにか。どのような詳細を持っているのか。これにもいくぶんばらつきがあり、ここで整理することにする。次の4本立てになる。
クエリ単位でのレプリケーション
もっとも単純な連携手法として、リーダーは単に実行したクエリをログに落とし、リードレプリカにログを転送することが考えられる。リードレプリカ側では受け取ったログをパースして、厳密に同じ順序でひとつずつクエリを実行していけば、リーダーと同じデータを複製できるはずである。
うまくいくように見えるかもしれないが、これには本質的な欠陥があって、一般には推奨できない。例えば NOW() や RAND() といった関数がクエリに含まれるとき、同じ結果を再現することができなくなってしまう。また厳密に同じ順序で実行することを要請するにも限界があり、例えば並行トランザクションの扱いをどうするか？ といった振る舞いは定義不能に陥ってしまう。
MySQL はバージョン 5.1 以前でこの方式を採用していたが、いまでは使っていない。
ログ先行書き込み (WAL) を利用したレプリケーション
データベースへの書き込みに先立って、変更内容をあらかじめログに書き出すことで処理の永続性を保証するログ先行書き込み (Write-ahead log, or WAL) という仕組みがデータベースエンジンに備わっていることがある。本来的にはこのログは、書き込み中にダウンしたノードの再起動時に、どこまで処理が成功しているかを参照するためのものであるが、このログをレプリケーションログに転用して、書き込み結果を複製することが可能である。 PostgreSQL と Oracle はこの方式によりレプリケーションを備えている。
この方式にもデメリットがある。それは低レベルな実装の詳細である WAL にレプリケーションが依存してしまうことで、データベースのアップグレードの障害となりかねない点である。要するに、 WAL に互換性のない変更が導入されたときに、クラスタ内で異なるバージョンのデータベースを動かすことが不可能になってしまうのである。
ちなみにこの制約がなければ、データベースのバージョンアップは一般に次のような手順でダウンタイムなく実施することができる。
- リードレプリカを先にアップグレードする
- フェイルオーバーを実施しアップグレード済みのノードをリーダーに昇格させる
- 降格した元リーダーをアップグレードする
WAL の実装にレプリケーションを依存させてしまうと、クラスタに属するすべてのノードを一斉にアップグレードする必要が生じる。サービスを稼働させたままこのオペレーションを行うのは現実的に不可能で、サービスを停止させてアップグレード作業を実施する必要が生じてしまう。
列単位での論理的レプリケーション
前項の議論を踏まえると、実装の詳細である WAL をそのままレプリケーションログに転用するのではなく、なんらかのアルゴリズムによって WAL を抽象化したものをレプリケーションログとして利用すればよさそうである。例えば次のようなやり方が採用できそうである。
INSERTについてはすべての行の値をログするDELETEについては主キーをログする。主キーがないときはすべての行の値をログして完全一致する列を消す。UPDATEについては行を特定するのに最低限必要な数の行のデータと新しい値をログする。
これらの道具があれば事足りるはずだ。トランザクション処理については、これらの道具の組み合わせと、コミットを表すログでひとまとまりとみなしてログに落とせばよい。
この方式で作成されるレプリケーションログは WAL よりもパースしやすい構造となっているはずで、おのずと外部システム連携への道も開ける。例えばレプリケーションログをデータウェアハウスに送信して、異なるクラスタにデータを複製するようなことも可能になる。
トリガーを利用したレプリケーション
データベース層でなくアプリケーション層でレプリケーションを行いたいというケースもまれにあるだろう。ストアドプロシージャなどの仕組みを使って、データベースの変更をフックにアプリケーションコードを実行することも不可能ではない。不可能ではないが、データベース層で実行するレプリケーションよりも当然オーバーヘッドは大きくなるから、計算量その他に対する繊細な配慮は必要となるだろう。
ノードのダウンに対応する
個別のノードがダウンすること自体は防ぎようがない。よって個別のダウンが発生してもシステムが稼働し続けることを目指すのが健全である。言い換えると、ノードが不足する状況が発生したときにどれだけその影響を小さく止められるか、を対策するのである。
リードレプリカがダウンしたとき
リードレプリカがダウンし、一定時間後に再起動したとする。このレプリカがただちに読み取りリクエストの処理を再開してしまうと、古いデータをレスポンスしてしまいかねない。よってこのときの復旧手順としては、まずはリードレプリカの状態をリーダーノードに追いつかせることが最優先となる。
通常時のリードレプリカはリーダーからのレプリケーションログを絶え間なく受け取り続けている。つまり、ダウンから復旧したリードレプリカは、「ダウンした時点でどこまで処理済みだったか」を覚えている。復旧した時点で、ダウン期間のレプリケーションログをリーダーにリクエストし、キャッチアップすれば再稼働できる。
リードレプリカが再起不能のときは、ノードをクラスタから切り離して新しいリードレプリカを追加しよう。この時の手順は前項にて述べた。
リーダーがダウンしたとき
フェイルオーバーを実施しよう。フェイルオーバーとは、リーダーがダウンしたときの一連の手続きを総合した呼び名である。おおよそ総括すると次のような手順が含まれる。
- リードレプリカのうち1台をリーダーノードに昇格させる
- クライアントが新しいリーダーに書き込みリクエストを送信するように設定を更新する
- 残りのリードレプリカが新しいリーダーからレプリケーションを取得するよう設定を更新する
ここではフェイルオーバーを自動で実施するか、手動で実施するかというトレードオフが存在する。体系化された自動フェイルオーバーの設定事項は存在するが、配慮すべき障害点が多いことを踏まえると、フェイルオーバーの意思決定を自動化しないという選択肢も十分妥当である。例えば GitHub は自動フェイルオーバーの事故を踏まえて手動フェイルオーバーに切り替えている1。
そのうえで、自動フェイルオーバーは次のような流れで実施される。
リーダーがダウンしたことを検知する。
タイムアウトによって検出するのが一般的である。例えば30秒間疎通が確認できなければダウンしているとみなすなどと設定する。閾値の設定はプロジェクトによって異なるので、実際の運用ケースから経験主義的に導き出す必要がある。ただしネットワーク全体が遅延しているようなケースでは、閾値が低ければ低いほどフェイルオーバーが連鎖して暴走し、システム全体の負荷上昇に歯止めが効かなくなることも考えられる。十分な注意を払う必要があるし、最終的には人が介入して緊急脱出できるような仕組みも結局は必要になるだろう。
新しいリーダーを選出する
コンセンサスアルゴリズムによって決定されることもあるし、コントローラノードをあらかじめ用意しておいて意思決定を託すこともあるだろう。非同期レプリケーションが行われていた場合には、原則として、元リーダーのデータをもっとも最新分まで取得できていたレプリカが新しいリーダーとなるのが理想である。
新しいリーダーを利用するようにシステムを再設定する
クライアントが新しいリーダーに書き込みリクエストを送信するようにする。リードレプリカは新しいリーダーからレプリケーションログを取得するようにする。ダウンした旧リーダーノードがクラスタに復帰した場合には、もはやそれがリーダーでないと教えてレプリカに格下げする必要もある。リーダーノードがふたつ以上存在してしまうようになると、データの整合性は保証不能になる。
