队列是现代计算中极其有用的工具，在 Web 应用中通常用于稍后执行可能较慢的计算。基本上，队列允许将一次计算拆分为两个时间点：安排计算的时间，以及执行计算的时间。“生产者”会将待执行的任务放入队列，而“消费者”或“工作进程”则从队列中获取任务并执行。例如，Web 应用中的新用户完成注册流程后，应用会向队列中添加一个新任务，以便发送包含激活链接的电子邮件。实际的邮件发送过程可能需要在出现临时网络故障或其他错误时进行重试，这由工作进程负责。

从技术上讲，我们可以将队列看作一种进程间消息传递原语(inter-process messaging primitive)，其中接收进程需要确认消息已被接收。消息不能采用 fire-and-forget(发送后不再关心结果)的方式，因为队列需要知道是否可以将消息从队列中移除，因此某种形式的确认是必需的。

当接收消息会触发任务执行时——正如我们所讨论的这类队列一样——确认消息接收的时机会改变队列的语义。如果工作进程在处理消息之前确认接收，那么工作进程发生故障时，消息可能会在任务实际执行之前就丢失。如果只在消息处理之后发送确认，那么当工作进程发生故障，或由于网络分区导致连接中断时，队列可能会再次投递该消息。无论队列具有什么一致性属性，都会发生这种情况。因此，即使队列使用提供强一致性的系统来建模，这种不确定性仍然存在：

• 如果在处理之前确认消息，队列将具有 at-most-once delivery(至多一次投递)属性。这意味着消息可能被处理零次或一次。
• 如果在处理之后确认消息，队列将具有 at-least-once delivery(至少一次投递)属性。这意味着消息可能被处理 1 次到无限次。

虽然这两种情况都不完美，但在现实世界中，第二种行为通常更受青睐，因为应对消息多次投递（从而触发任务多次执行）的情况，通常要比应对系统偶尔完全不执行某个任务简单得多。Amazon SQS (Simple Queue Service) 就是一个至少一次投递系统的例子。

之所以应该优先选择至少一次投递系统，还有一个根本原因，这与分布式系统有关：另一种语义（至多一次投递）要求队列具备强一致性：一旦消息得到确认，就不能再有其他工作进程确认同一条消息，这是一个很强的属性。

一旦我们将注意力转向至少一次投递系统，就会发现，使用 CP system(CP 系统)对队列进行建模是一种浪费，同时也是一种劣势：

• 无论如何，我们都无法保证超过至少一次投递。
• 我们的队列将失去在网络分区的少数派一侧继续工作的能力。
• 由于一致性要求，队列需要达成共识，因此我们平白消耗了性能并增加了延迟。

由于消息可能被多次投递，从概念上讲，我们需要的是一个 commutative data structure(可交换数据结构)和一个 eventually consistent system(最终一致性系统)。消息可以存储在一个复制到 N 个节点的集合数据结构中，合并函数则是各集合之间的并集。工作进程在执行消息后收到的确认，从概念上讲也属于集合中的元素，用于标记某个元素已被处理。这是一个并不特别适用于现实系统的简单例子，但它展示了某类队列如何通过分布式系统的一组特定属性得到良好建模。

从实际角度看，我们的队列还可以尝试提供其他有用的功能：

• 至少在一段时间窗口内保证投递给单个工作进程：虽然允许多次投递，但我们希望尽可能避免这种情况。
• 通过尽力而为的检查，避免在超时后重新投递已经处理过的消息。同样，我们无法保证这一属性，但可以尽力减少重新发出实际上已经处理过的消息。
• 拥有足够的内部状态，使消息在正常运行期间按 FIFO(先进先出)顺序处理，从而先到达的消息先得到处理。
• 自动清理内部数据结构。

除此之外，我们还需要在网络分区期间保留消息，因此从概念上讲（即使在实际实现中我们可以使用不同的数据结构），待投递的消息集合应当是所有节点上全部消息的并集。

遗憾的是，尽管存在许多基于 Redis 的队列实现，却没有人尝试使用 N 个相互独立的 Redis 节点及其提供的原语，将它们作为构建模块，构建出具备这些特性的分布式系统。结合 Redis 数据结构和性能，以及能够提供某些有用保证的算法，可以构建出一种非常实用、易于管理和扩展的队列系统，同时为每个节点提供出色的性能（messages / second）。

我觉得这个主题很有意思，而且这是 Redis 的一个绝佳用例，因此我正在非常缓慢地设计这样一个基于 Redis 的队列系统。如果时间允许，希望能在接下来的几周内展示一些成果。