追記：見逃した方のために、Disqueのソースコードは現在 http://github.com/antirez/disque で公開されている。

数ヶ月前から、自分の時間の15〜20％ほどを、主に夜や週末から捻出した時間を使って、新しいシステムの開発に充てている。それはメッセージブローカーで、Disqueという名前だ。元の仕様の80％ほどはすでに実装できたが、まだリリースできる状態だとは思えない。リリースできない以上、せめてブログに書こう。そんなわけで、どう始まったのか、そしてそれが何なのかについて少し詳しく書いてみたい。

～ はじめの一歩 ～

多くの開発者がRedisをメッセージキューとして使っている。多くの場合はRedisの低レベルなプリミティブを抽象化したライブラリを介して、またあるときはRedisの生のAPIを使ってシンプルでアドホックなキューを直接作っている。このユースケースは主に、リストへのpush操作と、ブロッキングlist操作を使って実現されている。Redisは、こうした用途においては一見すると最良であると同時に最悪のシステムでもある。高速で、状態の確認やデプロイ、利用も容易であり、多くの環境ではすでにインフラの一部になっているという点では優れている。しかし欠点もある。Redisの可変データ構造は、不変であるメッセージとは根本的に異なるからだ。RedisのHAやClusterにおけるトレードオフは、大きく可変な値の扱いに完全に偏っているが、同じトレードオフはメッセージを扱う上では最適とは言えない。

メッセージブローカーにとって重要な保証の一つは、メッセージが「少なくとも一度」あるいは「多くとも一度」配信されることだ。端的に言えば、（ここで言う配信とは、メッセージがワーカーによって受信され、かつ処理されたことを意味する）メッセージが厳密に一度だけ配信されることを保証することは現実的に不可能なので、選択肢はメッセージブローカーが「0回または1回」の配信を保証するか、「1回から無限回」の配信を保証するかのどちらかになる。これはしばしばat-most-onceセマンティクス、at-least-onceセマンティクスと呼ばれる。前者のユースケースも存在するが、より興味深く実用的なのは後者であり、つまりメッセージが少なくとも一度は配信されることを保証し、障害があれば複数回配信するというものだ。

そこで数ヶ月前、こうした保証を提供する形で、複数のRedisマスター（レプリケーションもクラスタリングも一切なし）を扱うためのクライアントサイドのプロトコルについて考え始めた。Redisの使い方を少し変えるだけで、より良いシステムになることもある。例えば分散ロックについては、単一インスタンス＋フェイルオーバーによる実装よりも堅牢で、かつ実装がごく簡単なアルゴリズムをドキュメントにまとめてみた（http://redis.io/topics/distlock）。

しかし数日作業してみると、設計のドラフトは、専用のシステムを設計した方が得策であることを示していた。クライアントサイドのアルゴリズムは結局複雑で最適とは言えず、私がどうしても実現したかったことのいくつかは、不可能か、あるいは非常に困難だったからだ。Redisにさらに機能を追加するのも悪手に思えた。Redisはすでに多くのことを担っており、メッセージングをきちんとカバーするにはRedisの動作とは大きく異なるものが必要だったからだ。だが、世の中にメッセージブローカーが溢れているのに、なぜ新しいシステムを設計するのか？ それは、驚くほど多くのユーザーが、この目的のために特別に設計されたシステムではなくRedisを使っていたからだ。そしてそれは奇妙なことだった。少数の人が間違えることはあっても、これほど多くの人がそうするのには何か理由があるはずだ。おそらくRedisの参入障壁の低さ、シンプルなAPI、速度といったものは、メッセージブローカーの世界を見渡したときに多くの人が慣れ親しんできたものではなかったのだろう。そこにあるのは、シンプルすぎてアプリケーション側にやりすぎを要求するソリューションか、あるいは複雑すぎるが超高機能なソリューションかのどちらかだ。もしかすると「メッセージングにおけるRedis」のための余地があるのかもしれない？

～ Redisを力ずくでフォークする ～

人生で初めて、すぐにコードを書き始めなかった。何週間も時々設計を眺め、それをRedisのクライアントライブラリではなく新しいシステムへと変換し、ユーザーとしてメッセージブローカーに何があれば心から嬉しいかを考えようとした。当初のユースケースは変わらないままだった。遅延ジョブだ。Disqueは汎用的なシステムだが、設計において90％の場面で「リファレンス」となっていたのは、処理すべきジョブである可能性の高いメッセージを送るという問題を解決しなければならないユーザーだった。このユースケースに反するものがあれば、それは取り除かれた。

設計が固まったとき、ようやくコーディングを始めた。だがどこから始めるか？「vi main.c」からか？ 幸いなことに、Redisは部分的にはCで分散システムを書くためのフレームワークだ。プロトコル、ネットワークライブラリ、クライアント処理、ノード間メッセージバスがすでにあった。これらすべてを一から書き直すのは大きな無駄に思えた。同時に、もし必要ならDisqueがRedisとはあらゆる細部において完全に分岐できるようにしたかったし、Redis自体に影響を与えないサイドプロジェクトにしたかった。そこで、Redisを実際に独立したフレームワーク部分とRedisの実装部分に分割するという大掛かりな試みをする代わりに、より実務的なアプローチを取った。コードをフォークし、ソースコードからRedis固有のものをすべて取り除いて、スケルトンだけを残したのだ。その時点で、私は仕様の実装を始める準備ができていた。

～ Disqueとは何か ～

非常にゆるいペースで数ヶ月、わずか200コミットを経て、ようやく玩具には見えなくなったシステムができた。何週間もの間ずっと玩具のように見えていたので、ソースツリーを丸ごと削除してしまう確率も高く、話すことさえ怖かったのだ。今ではアイデアの大部分がテストを伴う動くコードになったので、将来的にこれがリリースされることは確信しているし、設計でどのようなトレードオフを選んだのかを語ることもできる。

Disqueはデフォルトで分散システムだ。APシステムである以上、Redisのようにシングルノードモードと分散モードを分ける意味はない。単一のDisqueノードは、ノードが一つだけのクラスタという特殊なケースに過ぎない。だからこれは設計における重要なポイントの一つだった。フォールトトレラントで、パーティションに強く、どれだけのノードが生き残っていても利用可能であること、すなわちAPであることだ。また、多くのプロデューサやコンシューマ、多くのキューを抱える場合でも、逆にそれらすべてのプロデューサやコンシューマが単一のキューに集中し、複数のノードに分散される場合でも、本質的にスケールできるシステムにしたかった。

要件は一つのことを声高に物語っていた……Disqueは大きな設計上の犠牲を払うことになる、と。メッセージの順序だ。Disqueが提供するのはベストエフォートの順序付けだけだ。しかしこの犠牲によって得られるものは大きい……トレードオフというのはときに、設計空間を完全に切り拓くものなのだ。

この調子でDisqueが何であるかを語り続けることもできるが、数ヶ月前にHacker NewsでJacques Chesterのコメントを見かけた。https://news.ycombinator.com/item?id=8709146 ［編集：Adrianの名前をコピペで間違えました（Adrian、誤って引用してごめんなさい！）］。たまたま私と同じくPivotalで働いているJacquesは、メッセージングシステムがいかに多様な機能や特性のセットを持っているか、そして詳細がなければ異なる選択肢を評価することも、一方が他方より速いのが実装が優れているからなのか、単に保証がずっと少ないからなのかを評価することもほぼ不可能だとコメントしていた。そこで彼は、メッセージングシステムを評価する際に問うべき一連の質問を書いた。私は彼の質問にいくつかを加えて、Disqueが何であるかを説明するために使おうと思う。そうすれば、ただ漠然と語るのではなく、実際に何らかの情報を提供できるはずだ。

Q: メッセージは少なくとも一度配信されるか？

Disqueでは、メッセージごとにat-least-once配信（デフォルト）かat-most-once配信かを選択できる。at-most-onceは、メッセージの「retry」パラメータを0に設定し、単一ノードにのみ複製することで実現される、at-least-onceの特殊なケースに過ぎない。

Q: メッセージはコンシューマによって確認応答（acknowledge）されるか？

はい。コンシューマがメッセージを正しく受信・処理できたことをシステムに伝える唯一の方法は、それをacknowledgeすることだ。

Q: acknowledgeされなかった場合、メッセージは複数回配信されるか？

はい。Disqueは「retry」で指定された時間が経過すると、メッセージを自動的に再配信する。これはメッセージの最大TTLに達するまで永遠に続く。メッセージがacknowledgeされると、そのacknowledgeはメッセージのコピーを持つノードへ伝播する。システムが全員に届いたと判断すれば、メッセージは最終的にガーベジコレクトされ削除される。acknowledgeされたメッセージはメモリ逼迫時にも退避される。

ノードは同じメッセージを何度もキューに入れないようにするベストエフォートなアルゴリズムを実行しており、より単一配信に近づけようとしている。しかし障害時には、複数のノードが同じメッセージを同時に複数回再配信してしまうことがある。

Q: キューイングは永続的か、それとも一時的か。

永続的だ。

Q: 永続性は、すべてのメッセージをまずディスクに書き込むことで実現されるのか、それともサーバ間でメッセージを複製することで実現されるのか？

デフォルトではDisqueはインメモリのみで動作し、同期レプリケーションによって耐久性を実現している（ただし、メッセージごとに非同期レプリケーションを指定することも可能だ）。大量再起動のような事態が想定される場合には、Redisと同様にAOFを有効にすることもできる。システムをアップグレードする際には、通常はディスク永続化を使っていなくても、再起動後に状態を失わないよう、一時的にAOFをディスクに書き出すことが可能だ。

Q: キューイングはサーバグループ間で部分的／全体的に一貫性があるのか、それとも最大のスループットのために分割されているのか？

スループットのために分割されている。ただしメッセージの順序はベストエフォートで保持される。各メッセージは不変の「ctime」を持っており、これは壁時計のミリ秒タイムスタンプに、同一ミリ秒内に生成されたメッセージ用のインクリメンタルなIDを加えたものだ。ノードはこのctimeを使って配信順にメッセージをソートする。

Q: 負荷がかかった際にメッセージが完全に破棄されることはあるか？（いわゆるベストエフォート）

いいえ。ただしメモリに空きがなければ新しいメッセージは拒否されることがある。メモリ使用率が75％に達すると、メッセージを受信したノードはコピーを保持せず、外部のノードへ複製を試みるが、他のノードもメモリ不足の状態であればうまくいかないこともある。

Q: コンシューマやプロデューサはキューを覗き見ることができるか、それとも完全に不透明か？

キューを覗き見るための「PEEK」コマンドが用意されている。

Q: キューイングは順序なし、FIFO、優先度付きのいずれか？

前述のとおり、ベストエフォートなFIFOに近い挙動だ。

Q: ブローカーは存在するか？

ブローカーはマスターの集合として存在する。クライアントはどのノードとでも通信できる。

Q: ブローカーは独立した名前付きキュー（トピック、ルートなど）を持つのか、それともプロデューサとコンシューマが接続を調整する必要があるのか？

名前付きキューだ。プロデューサとコンシューマが接続を調整する必要はない。ノードはフェデレーションを使ってクラスタ内でルートを発見し、コンシューマが必要とするメッセージを必要に応じて転送する。ただし、より多くのコンシューマがいる場所へ移動したい場合に備えて、クライアントにはヒントが提供される。

Q: メッセージの投稿はトランザクショナルか？

はい。メッセージを追加するコマンドが返った時点で、クラスタ内に所望の数のコピーが存在することがシステムによって保証される。

Q: メッセージの受信はトランザクショナルか？

おそらく違う。Disqueはacknowledgeされなければ同じメッセージを再配信しようとするからだ。

Q: コンシューマは受信時にブロックするか、それとも新しいメッセージがあるか確認できるか？

どちらの動作もサポートしており、デフォルトではブロックする。

Q: プロデューサは送信時にブロックするか、それともキューの満杯状態を確認できるか？

プロデューサは、自分がメッセージをpushしているローカルノードで、キューの長さがすでに指定した値を超えている場合に、新しいメッセージの追加時にエラーを返すよう要求できる。

さらに、プロデューサはメッセージのレプリケーションを非同期で行うよう要求でき、すぐに処理を抜けてクラスタにベストエフォートでレプリケーションを任せることもできる。

キューにメッセージが多すぎる場合にコンシューマをブロックし、メッセージが減ったらアンブロックするような方法は用意されていない。

Q: 遅延ジョブはサポートされているか？

はい。秒単位の粒度で、数年先までサポートしている。ただしメモリは消費する。

Q: コンシューマとプロデューサは異なるノードに接続できるか？

はい。

この投稿で、Disqueが少しはベイパーウェアでなくなったことを願っている。もちろんコードを見なければ何とも言えないが、もし優れた機能がすでに表に出ているなら、せめて文句を言うことはできるだろう。上記のうち、どれくらいがすでに実装され、きちんと動いているのか？ AOFによるディスク永続化と、APIで磨きをかけたい細かい部分を除けばすべてだ。なので最初のリリースはそう遠くないはずだが、これほど稀にしか作業していないと、超高速で進めるのは難しい。