世界に
世界中を見てまわりたい。一年とすこし前まで、事実そういう生活をしていたことがすっかり遠い過去のことに思える。
ベルリンにいた僕は COVID-19 がヤバイと聞いて早めに撤退したのだった。あとになってこれは英断だったとよく褒められるし、事実これ以外ありえない決断だったと評価している。とはいえ、ここまでひどいことになるとは思っていなかった。しばらく落ち着いたらふたたび繰り出そうと思っていたところ、国外どころか狭い狭い家の外にすら出られない生活で息がつまりそうだ。
世界のほんの片隅しか知らない。そうと知りながら、その片隅でぼんやり暮らすのは苦しい。広い世界があると知っているのに、そんなものなどないというふりをして生きていきたくはないし、もっとアクティブに世界を飛び回りたい。それができる職業についているのは幸運である。世界が安全といえるようになったら、いつでもその生活に舵を切れるように準備だけはしておきたい。
そういう熱い気持ちのことを、このエッセイを読んで思い出したので、忘れないように書いておく。
プログラマが変わっていると思うのは、遠隔地や旅行中でも容易にできる仕事でありながらみんなそうしないということだ。もちろん例外はあるだろうけど、この旅行中に同じようなことをしているプログラマには一度も出会わなかった。残念なことだと思う。プログラマ仲間への僕のメッセージは、言い訳するのをやめて実行しようよ、ということだ。人生一度しかないんだから。素晴らしい体験になるだろうことだけは請け合える。
会社員は会議がおおい
新入社員になってきょうで丸3ヶ月となる。入社の折に書いたエントリを読み返すと、かなり肩に力がはいってしまっていたことがわかる。よほど自己肯定感が低かったとみえるが、実際働きはじめてみると、まったく問題なく戦力となれている実感があるし、自信を折られて萎縮することなどはまったくない。尊敬に値するチームメイトと一緒にいても、自分には自分の強みと特性があるからと、力強く振る舞えているように思う。
手を動かして開発をする時間は以前よりもすこし減っている。「すこし」とぼんやりと書いたところで、そういえば rescuetime で活動時間のログをとっていたのだと思い出し、集計してみた。
それがこれである。ざっくりいうとエディタとか GitHub を触っている時間が development で、ビデオ会議とか Slack をしている時間が communication である。開発時間が減少傾向にあるのは事実のようだが、それよりも目を引くのはコミュニケーションに割かれるようになった時間の急激な増加である。
すべての会議がただちに無駄とは言わない。以前の職場においてコミュニケーションが少なすぎた、ということも言えるだろう。設計を議論するなどの健全で生産的な会話は前の職場よりも増えているし、それは嬉しく思う。
ただ、一日の半分がミーティングで埋め尽くされているカレンダーを眺めたりすると「本当にこれがあるべき姿なのか？」とうなだれてしまうのもまた事実である。それが求められる職務であるといえばそれまでなのだが、さみしい気持ちにはなる。
この3ヶ月は手探りの期間だったので、よくわからない会議にとりあえず呼ばれて置き物になる、みたいなムーブもあったように思う。そしてそのために集中力が散漫になっている直感があったが、この直感は正しかったようだ。
会議に出るか出ないかは自分で決める、という線で振るまってみよう。それが波風をたてる職場であるとは思わないし、それによって仕事が進まなくなるというのなら、それはおかしくないか？ と問題提起しよう。実際、3ヶ月前まではいまの半分未満のコミュニケーション時間で済んでいたのだから、できないことはないはず。
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。ベストプラクティスといえるほど有効で定着するかどうかは時間の判断に委ねるほかないが、監視項目のひとつに含めておくことは損にはならないだろう。「結果整合性」というあいまいな言葉にどれだけの期待をしてよいか、チームの共通認識として言語化しておくことはなにより大切である。
