複数リーダーレプリケーションのユースケース
複数リーダーレプリケーションが行われるユースケースを考えてみよう。「データベース」という言葉からくる先入観に必ずしも対応しないものも含めて、いくつものユースケースがある。
まずは複数のデータセンターについて、各データセンターにひとつずつリーダーノードを立てることで、単一リーダーレプリケーションとは異なり書き込みリクエストが単一のデータセンターに集中することを防ぐことを企図できる。ネットワーク障害時にも個別のデータセンター内に閉じて処理を継続できるので、耐障害性は相対的には高くなる。巨大なデメリットとして、個別のリーダーが許可した書き込み内容が後になってコンフリクトを引き起こすことを許容しなければならず、コンフリクト解消の手段を提供する必要が生じる。しかし大規模なデータセンター間で複数リーダーを運用するのは未知の領域があまりに広く、事例も充実していないことから、できる限り避けることが推奨される。
それから、クライアントがオフライン処理をおこなうようなアプリケーションも複数リーダーレプリケーションを行なっていると見立てることができる。例えばカレンダーアプリのように、複数のデバイス上でオフラインで実施した操作を後になって同期するようなケースを考える。この場合、各デバイスはいわばリーダーノードであり、それぞれが受け付けた書き込みを非同期にレプリケートしているわけだ。しかもレプリケーションラグはデバイスのオフライン期間に比例して、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秒間疎通が確認できなければダウンしているとみなすなどと設定する。閾値の設定はプロジェクトによって異なるので、実際の運用ケースから経験主義的に導き出す必要がある。ただしネットワーク全体が遅延しているようなケースでは、閾値が低ければ低いほどフェイルオーバーが連鎖して暴走し、システム全体の負荷上昇に歯止めが効かなくなることも考えられる。十分な注意を払う必要があるし、最終的には人が介入して緊急脱出できるような仕組みも結局は必要になるだろう。
新しいリーダーを選出する
コンセンサスアルゴリズムによって決定されることもあるし、コントローラノードをあらかじめ用意しておいて意思決定を託すこともあるだろう。非同期レプリケーションが行われていた場合には、原則として、元リーダーのデータをもっとも最新分まで取得できていたレプリカが新しいリーダーとなるのが理想である。
新しいリーダーを利用するようにシステムを再設定する
クライアントが新しいリーダーに書き込みリクエストを送信するようにする。リードレプリカは新しいリーダーからレプリケーションログを取得するようにする。ダウンした旧リーダーノードがクラスタに復帰した場合には、もはやそれがリーダーでないと教えてレプリカに格下げする必要もある。リーダーノードがふたつ以上存在してしまうようになると、データの整合性は保証不能になる。
新しいリードレプリカをクラスタに追加する
サービスが成長するに従って、既存のクラスタにリードレプリカを追加する必要性は必ず生じる。そのときどうやって新しいリードレプリカにリーダーのデータを複製するか？
単にデータファイルをコピーするだけでは、コピー中に生じる差分を吸収できない。かといってコピー中に書き込みをブロックするのは、可用性を犠牲とすることとなるのでスマートな解決策とはいいがたい。
これについてはこうあるべきという合意された答えがある。それをそのまま紹介する。こういうことになる。
同期レプリケーションか、非同期レプリケーションか
書き込みログをネットワーク越しにリードレプリカに転送するジョブは、基本的には軽量で高速動作する。ただしネットワークの不調やリードレプリカの予期せぬ故障など外部要因によって無制限の遅延が発生する可能性は常に存在する。
同期レプリケーション
リーダーノードとリードレプリカの間のレプリケーションを常に同期的に実行するとする。ノード間のネットワークが遅延していても、リードレプリカに正しく疎通がとれるまでリーダーノードは書き込みリクエストに対して ok を返さない。
このときクラスタ全体が常に最新のデータを持つことを保証できる。またリーダーがダウンしてもリードレプリカが読み取りリクエストを処理しつづけることができる。他方で、リードレプリカが一台でも落ちてしまうと、リーダーノードは疎通が取れるようになるまで書き込みリクエストをブロックせざるを得ない状況に陥ってしまう。
つまり、クラスタ全体にわたって同期レプリケーションを実施するというのは、一台でもノードが落ちるとシステム全体が落ちてしまうということにほかならない。分散データベースが要請される前提条件が崩れることになるので、これは許容できない選択となるだろう。
非同期レプリケーション
他方でレプリケーションを非同期で行うとすると、原理的にデータの損失が発生しうる。とはいえ多少のデータ損失を許容できるのであれば、これは有効な選択肢となろう。データ損失など多少なりとも許容できない！ と息巻く気持ちはわかるが、100%の安全性を要件とするのはそもそも不健全だし保証不可能なので、どの程度の損失を許容できるかを明確化し、運用コストとの落とし所を探るのが賢明だろう。その意味で、データ損失を覚悟のうえ非同期レプリケーションを検討するのは有効であるはずと繰り返し述べておく。
どういうときにデータの損失が起こりうるか？ それはリーダーノードが受け付けた書き込みをリードレプリカに転送する前に不意にダウンしてしまうときである。リードレプリカのうち任意の一台が新しいリーダーノードに昇格することで、全体としての可用性は守られるが、クライアントから見ると成功したはずの書き込みが消失してしまうケースが生じうることは避けられない。
実際、データ損失のリスクというトレードオフを飲んでも非同期レプリケーションを採用する事例は多い。特に書き込みクライアントが世界中に散らばっていて、リーダーノードが一台しか存在しない場合であれば、レスポンスタイムの最短化を最優先に考慮してレプリケーションは非同期で行うという選択肢は少なからず有効だろう。
半同期レプリケーション
それでもデータ損失のリスクは受け入れがたいというのであれば、 Facebook 社にて採用されている半同期（ semi-synchronous ）パターンこそがもっとも中庸の落としどころといえるかもしれない。
これはリードレプリカのうち任意の一台について同期レプリケーションを行い、残りのリードレプリカに対しては非同期でレプリケーションを行う方式である。つまり最新のデータが最低でもリーダーのほかにもう一台に存在することが保証されるので、リーダーノードがダウンしてもデータの損失なしにフェイルオーバーできるといえることとなる。
この方式の出典はマツノブ・ヨシノリ氏の公開記事に記載があるので、詳細についてはこれをよく読むのが良い。
データベースを支えるデータ構造: Designing Data-Intensive Applications 第3章より
Designing Data-Intensive Applicationsより、インデックスにまつわる箇所の読書ノートをまとめた。いくつか重要なデータ構造が登場しているが、個別の語彙やアルゴリズムについて深く検討まではしていない。概念を把握する前に、概念の存在をまずは認識した形である。詳細は詳細として、いつか必要が出たときに再訪する。
インデックスとは
n件のレコードから任意のレコードを検索するとき、基本的には O(n) の計算量が想定される。インデックスとは、その計算量を改善するに導入される補助的なデータ構造である。書き込みのたびにインデックスの更新も行わなければならないためインデックスを持つことは必然的に書き込みオーバーヘッドを伴う。
つまり次のようなシンプルなトレードオフとして整理できる。
- 優れたインデックスは読み取りを高速化する
- あらゆるインデックスは書き込みを低速化する
B-tree と LSM-tree
PostgreSQL や MySQL (InnoDB) においてインデックスというと、基本的には B-tree のことを指す。他方でトランザクションログのように大量に書き込まれるデータの扱いに長けた、 LSM-tree というデータ構造もある。
B-tree と LSM-tree はおおむね対照的な特性を持つ。簡単に列挙すると、次のようになる。
LSM-tree
pro
- 高い書き込みスループットを持つ
- 圧縮効率がよく、ディスクを効率的に利用できる
con
- ログをマージするバックグラウンド処理がパフォーマンスに影響を与える
- 平均的にはある程度均等なレスポンスタイムであるが
- 高いパーセンタイルほどレスポンスタイムが悪くなる
- データベースが大きくなるほどリソース効率が下がるリスクが高まる
-書き込み流入量がバックグラウンド処理の速度を超えるとみるみるうちにディスクが溢れてしまう
- 書き込み量がボトルネックになる場合何らかの方法で外部から書き込みをスロットルする必要がある
B-Tree
pro
- トランザクションのための強力なロック性能を持つ
- 任意のキーはインデックス上で常にひとつしか存在しないことが保証されているため
- 時の審判を経ていくつもの改良も行われているからデータ構造としての信頼性はとても高い
con
- ページへの書き込み、ページ分割時の、変更ログの書き込みなどとかく書き込みコストが高い
- フラグメンテーションの問題がつきまとう
マルチカラムインデックスと R-tree
B-Tree と LSM-tree はいずれも単一のキーを値にマッピングするデータ構造であり、複数カラムを効率的にインデックスすることは苦手である。複数カラムを結合して単一のキーとして扱うことはできるが、結合順序に依存することは避けられない。これはつまり、電話帳の索引が姓→名の順で検索しやすくても、名→姓で引くことはできないようなものである。
経緯度データに代表される多次元データを効率よくインデックスするには R-tree のようなまた異なるデータ構造が利用される。
全文検索とあいまい検索
同意語、ミススペル、コロケーションなどを含めたファジーなインデックスを実現するには、また別のテクニックが要求される。 Elasticsearch のエンジンである Lucene は検索語句を入力として受け取り、 レーベンシュタイン距離 に基づいて検索を行う。 Lucene 自体が 有限オートマトン として動作するよう設計されているのである。
すべてをメモリに記憶する
ここまで扱ったトピックは、いずれもディスクに永続化されたデータを効率的に検索するためのものであった。メモリの生産コストが下がったことで、メモリ上で動作するストレージも登場してきている。
インメモリデータベースは伝統的なデータベースよりも速く動作するとされる。よくある誤謬であるが、これはディスクシークやI/Oが省略できるぶん高速であるというよりもむしろ、メモリとディスクの間でデータのエンコード/デコードが不要であるため高速化できているのである。
例えば redis は優先度付きキューやセットを実装しているように、インメモリデータベースはディスクデータベースでは不可能だったデータ構造も実現できる。またデータの読み書きはメモリ上で行いつつも、データの永続化のためにディスクへの書き出しもサポートするプロダクトも存在している。
今後、不揮発性メモリが一般化すれば大きくパラダイムが変わるから、それも見据えてアンテナを張り、思考することが要請される。
