AtCoder のレートが緑色になった
週末の ABC199 で緑コーダーになれた。29回目のコンテストでの昇格である。
茶色に昇級したときのエントリを読み返した。これが去年の9月半ばのことであるから、緑色に到達するまでに要したのは7ヶ月ということになる。
正直に告白すると、この期間アルゴリズムの学習はほとんどしていない。過去問を解くこともほとんどできていない。それに割くだけの時間が作れないのである。ただコンテストにだけは愚直に参加し続けている。毎週末の2時間に集中して解く。解けなかったものはその場で復習して寝る。そういうルーティン化された毎週を送っていただけであるので、昇級したという感慨は思いのほか小さい。
週末のコンテストにしても、解ける問題を速解きした結果、たまたま高いパフォーマンスが出てしまっただけであって、どうも棚ぼた感はある。たまたま転がり込んできた結果でしかないので、またすぐに陥落するのではないかと思うと無邪気に喜ぶことはできない。
まあ、およそこのあたりのレーティング帯で長く推移しているので、これが正しく自分の実力というものを表しているのだろう。きちんと勉強と精進を積めばもうすこし成長できると思いつつ、緑色並の実力という自画像に納得してしまっているところもある。もっと高いレベルに立つとなにが見えてくるのかに興味はあるが、あいにくもっと興味のあることが他にある、ともいえる。
よって、次の目標として水色を目指すと言うことはできない。レーティング1000を目指すともあまり表明する気にならない。いま持てる実力より高い目標を立てても、それに邁進するだけのリソースがないのである。できない目標を掲げることになってしまえば、 atcoder と言うゲームそのものがつまらなくなってしまう。
そこで僕は目標として、次回からも変わらずコンテストに参加し続けることを目標にしたい。あるいはふたたび茶色に陥落することも十分にありえるが、それでもめげずに毎週2時間だけはこれに集中しきりたい。運動の習慣と同じようなもので、週に1度だけでもしっかり集中してセットをこなすことで、すこしずつ成長できるはず。すくなくとも衰微を遅らせることだけはできるだろう。
自分が特別な才能の持ち主ではないということを教えてくれたことについて、 AtCoder には感謝しきれない。正直にいって、もっとチョロいゲームだと思っていた。しかし茶色レーティングではやくも足踏みを食らわされたことで、自分がいかに凡庸であるかを知ることができた。もちろんその事実と向き合い、受け入れることには痛みを伴ったし、おおきな時間もかかった。でも最終的にはこの試練を通して、僕はつまらない自尊心を克服して、小さな人間として一皮むけることができたと思っている。そしてそれはプログラミングスキルよりもずっとおおきな収穫だ。
いまからトップティアを目指すわけでもあるまいし、競争的結果に一喜一憂するよりも、生涯のアマチュアとして、楽しく参加すること。そうして人生を豊かにすること。それくらいの気持ちで細々と付き合っていくことができればじゅうぶん幸せといえるだろう。将棋や囲碁の愛好者がいるように、僕は競技プログラミングの愛好者として楽しむ。いまはそれでいいと思っている。
分散データベースのレプリケーション: 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。自動的かつ穏当なやり方でコンフリクトを解消するための方法論はいまだ研究の途上にある。技術として発展途上であるから、一般のデータベース製品においてもほとんど対応されていないというのが正直なところである。
