キューは現代のコンピューティングにおいて非常に有用なツールであり、Webアプリケーションで時間のかかる可能性のある処理を後で実行するためによく使われる。基本的にキューは、ひとつの計算を2つの時点、すなわち計算がスケジュールされる時点と、計算が実行される時点に分割することを可能にする。「プロデューサー」が実行すべきタスクをキューに入れ、「コンシューマー」あるいは「ワーカー」がキューからタスクを取り出して実行する。例えば、Webアプリケーションで新規ユーザーが登録を完了すると、アプリケーションはアクティベーションリンク付きのメールを送信するための新しいタスクをキューに追加する。一時的なネットワーク障害などでリトライが必要になることもある、実際にメールを送信するという処理はワーカーに委ねられる。

技術的に言えば、キューはプロセス間メッセージングのプリミティブの一種と考えることができ、そこでは受信側のプロセスがメッセージの受信を確認する必要がある。メッセージを送りっぱなし（fire-and-forget）にすることはできない。キューがそのメッセージを削除してよいかどうかを判断する必要があるため、何らかの形での確認応答が不可欠だからだ。

ここで話題にしているようなタイプのキューで、メッセージの受信がタスクの実行をトリガーする場合、メッセージ受信の確認をいつ行うかがキューのセマンティクスを変える。ワーカーがメッセージを処理する前に受信を確認した場合、ワーカーが障害を起こすとタスクが実行される前にメッセージが失われる可能性がある。確認がメッセージの処理後にのみ送られる場合、ワーカーの障害やネットワーク分断によってキューが同じメッセージを再配送することがある。これはキューの一貫性特性がどうであれ起こり得ることであり、強い一貫性を提供するシステムでキューをモデル化したとしても、この不確定性は依然として残る。

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

どちらのケースも完全ではないが、現実の世界では後者の挙動が好まれることが多い。メッセージが複数回配送されること（タスクが複数回実行されること）に対処する方が、時々タスクがまったく実行されないシステムに対処するよりも、通常ははるかに簡単だからだ。at-least-once配送システムの例として、Amazon SQS（Simple Queue Service）がある。

at-least-once配送システムが好まれるべき根本的な理由もあり、それは分散システムに関わるものだ。もう一方のセマンティクス（at-most-once配送）では、キューに強い一貫性が求められる。いったんメッセージが確認されれば、他のどのワーカーも同じメッセージを確認できてはならないというのは、強い特性だからである。

at-least-once配送システムに焦点を移すと、キューをCPシステムでモデル化することが無駄であり、むしろ不利であることに気づく。

• いずれにせよ、at-least-once以上の保証はできない。
• キューはネットワーク分断時に少数派側で動作する能力を失う。
• 一貫性の要件のためにキューは合意を必要とするため、正当な理由もなくパフォーマンスを犠牲にし、レイテンシを増大させることになる。

メッセージは複数回配送され得るため、概念的に求められるのは可換なデータ構造と結果整合的なシステムである。メッセージはN台のノードにレプリケートされた集合（セット）というデータ構造に格納でき、マージ関数は集合間の和集合となる。メッセージの実行後にワーカーから受け取る確認応答も、概念的には集合の要素であり、特定の要素が処理済みであることを示すマークとなる。これは実世界のシステムとしては特に実用的ではない自明な例だが、ある種のキューが分散システムのある種の特性の集合によってうまくモデル化され得ることを示している。

実用的には、キューが提供しようとし得る他にも有用なことがある。

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

さらに、ネットワーク分断の間もメッセージを保持する必要がある。概念的には（実際には異なるデータ構造を用いるとしても）配送すべきメッセージの集合が、すべてのノードのメッセージの和集合となるようにするためだ。

残念ながら、Redisベースのキュー実装は数多く存在するものの、N台の独立したRedisノードとそこで提供されるプリミティブを、そのような特性を持つ分散システムの building block として使おうとするものは一つもない。Redisのデータ構造とパフォーマンス、そして一定の有用な保証を提供するアルゴリズムを用いれば、非常に実用的で、管理やスケールが容易でありながら、ノードあたり優れたパフォーマンス（メッセージ数/秒）を提供するキューシステムを実現できる可能性がある。

このトピックは興味深く、Redisにとって絶好のユースケースだと考えているため、そうしたRedisベースのキューシステムの設計に、非常にゆっくりではあるが取り組んでいるところだ。時間が許せば、今後数週間のうちに何かお見せできればと思っている。