キューは現代のコンピューティングにおいて非常に便利なツールです。Webアプリケーションでは、時間がかかる可能性のある処理を後で実行するためによく使われます。基本的にキューを使うと、処理を2つのタイミングに分けられます。処理を登録するタイミングと、実際に処理を実行するタイミングです。「プロデューサー」は実行すべきタスクをキューに入れ、「コンシューマー」または「ワーカー」がキューからタスクを取り出して実行します。たとえば、Webアプリケーションで新しいユーザーが登録手続きを完了したら、Webアプリケーションはアクティベーションリンク付きのメールを送信するための新しいタスクをキューに追加します。実際のメール送信処理はワーカーが担当します。ネットワーク障害などの一時的なエラーが発生した場合には、再試行が必要になることもあります。

技術的には、キューはプロセス間メッセージングのためのプリミティブの一種と考えられます。メッセージを受信したプロセスは、受信したことを確認応答する必要があります。メッセージを単純な fire-and-forget にすることはできません。キューは、そのメッセージを削除してよいかどうかを把握する必要があるため、何らかの確認応答が必ず必要になります。

メッセージを受信するとタスクの実行が始まる場合、つまりここで扱っている種類のキューでは、メッセージ受信の確認応答を送るタイミングによってキューの意味が変わります。ワーカープロセスがメッセージを処理する前に受信を確認した場合、ワーカーが失敗すると、タスクがまったく実行されないままメッセージが失われる可能性があります。確認応答をメッセージの処理後にだけ送る場合は、ワーカーの障害やネットワーク分断によって、キューがメッセージを再配信する可能性があります。これはキューの一貫性の性質にかかわらず起こります。つまり、キューを強い一貫性を提供するシステムでモデル化したとしても、この不確定性は残ります。

• メッセージを処理前に確認した場合、キューの配信特性は最大1回（at-most-once）になります。これは、メッセージが0回または1回処理されることを意味します。
• メッセージを処理後に確認した場合、キューの配信特性は少なくとも1回（at-least-once）になります。これは、メッセージが1回から無限回まで処理される可能性があることを意味します。

どちらのケースも完璧ではありません。しかし現実の世界では、2つ目の挙動が好まれることが多いでしょう。メッセージが複数回配信されてタスクが複数回実行されるケースに対処するほうが、あるタスクが時々まったく実行されないシステムに対処するより、通常ははるかに簡単だからです。少なくとも1回の配信を行うシステムの例として、Amazon SQS（Simple Queue Service）があります。

少なくとも1回の配信を行うシステムを選ぶべき根本的な理由は、分散システムにも関係しています。もう一方の意味論、つまり最大1回の配信では、キューに強い一貫性が必要になります。メッセージが確認された後は、別のワーカーが同じメッセージを確認できてはなりません。これは強い性質です。

少なくとも1回の配信を行うシステムに焦点を移すと、キューをCPシステムでモデル化するのは無駄であり、デメリットにもなることに気づきます。

• いずれにせよ、少なくとも1回の配信を超える保証はできません。
• ネットワーク分断が起きたとき、キューは少数側で動作する能力を失います。
• 一貫性の要件があるため、キューには合意形成が必要です。その結果、特別な理由もなく性能を消費し、レイテンシーを増やすことになります。

メッセージは複数回配信される可能性があるため、概念的に必要なのは可換なデータ構造と、結果整合性を持つシステムです。メッセージはN個のノードにレプリケーションされた集合データ構造に格納でき、マージ関数には集合の和集合を使います。メッセージの実行後にワーカーから届く確認応答も、概念的には集合の要素です。これは、ある要素が処理済みであることを示します。これは実際のシステムとしては特に実用的ではない単純な例ですが、分散システムが持つ特定の性質によって、ある種のキューをどのようにうまくモデル化できるかを示しています。

実際には、キューには次のような便利な機能も求められるでしょう。

• 一定の時間枠内では、少なくとも単一のワーカーへの配信を保証すること。複数回の配信は許容するとしても、可能な限り避けたいものです。
• タイムアウト後、メッセージがすでに処理済みであれば再配信を避けるためのベストエフォートのチェック。これも保証はできませんが、実際には処理済みのメッセージを再発行することを、できる限り減らすことはできます。
• 通常の運用中は、メッセージをFIFOとして扱えるだけの内部状態を持つこと。つまり、先に到着したメッセージを先に処理します。
• 内部データ構造を自動的にクリーンアップすること。

さらに、ネットワーク分断中もメッセージを保持する必要があります。したがって概念的には、配信すべきメッセージの集合は、すべてのノードが持つすべてのメッセージの和集合になります。実際には別のデータ構造を使うこともできます。

残念ながら、Redisをベースにしたキューの実装は数多く存在するものの、N個の独立したRedisノードと、Redisが提供するプリミティブを組み合わせて、このような特性を持つ分散システムの構成要素として利用しようとするものはありません。Redisのデータ構造と性能に、一定の有用な保証を提供するアルゴリズムを組み合わせれば、非常に実用的で、管理やスケールも容易なキューシステムを実現できるかもしれません。それでいて、ノードごとの性能（メッセージ／秒）にも優れたものになります。

このテーマは興味深く、Redisの優れたユースケースでもあるので、私はそのようなRedisベースのキューシステムの設計に、非常にゆっくりと取り組んでいます。時間が許せば、今後数週間のうちに何かお見せできればと思っています。