最近看了Dyno-queues分布式延迟队列的源码，发现了一些不错的技巧，而本文是对Dyno-queues架构精华的总结。
本文是根据 https://medium.com/netflix-techblog/distributed-delay-queues-based-on-dynomite-6b31eca37fbc 翻译而来，如果有不准之处请大家多包含。

在Netflix的平台上运行着许多的业务流程，这些流程的任务是通过异步编排进行驱动，现在我们要实现一个分布式延迟队列，这个延迟队列具有如下特点：

• 分布式
• 不用外部的锁机制
• 高并发
• 至少一次语义交付
• 不遵循严格的FIFO
• 延迟队列（消息在将来某个时间之前不会从队列中取出）
• 优先级

一、使用Dynomite和Redis构建队列

Dynomite是一种通用的实现，可以与许多不同的key-value存储引擎一起使用。目前它提供了对Redis序列化协议（RESP）和Memcached写协议的支持。我们选择Dynomite，是因为其具有性能，多数据中心复制和高可用性的特点。此外，Dynomite提供分片和可插拔的数据存储引擎，允许我们在数据需求增加垂直和水平扩展。

1、为什么选择Redis？

我们选择Redis作为构建队列的存储引擎：

• Redis架构通过提供构建队列所需的数据结构很好地支持了队列设计，同时Redis的性能也非常优秀，具备低延迟的特性
• Dynomite在Redis之上提供了高可用性、对等复制以及一致性等特性，用于构建分布式集群队列。

一个队列被存储为Redis的有序集合（ZADD和ZRANGE等操作），Redis使用分数对有序集合中的成员进行排序，当往队列中存储数据时，根据优先级和超时时间计算分数。

2、使用Redis实现数据的push和pop

对于每个队列，维护三组Redis数据结构：

• 包含队列元素和分数的有序集合
• 包含消息内容的Hash集合，其中key为消息ID。
• 包含客户端已经消费但尚未确认的消息有序集合，Un-ack集合。

PUSH

• 根据消息超时（延迟队列）和优先级计算得分
• 添加到队列的有序集合
• 将Message对象到Hash集合中，key是messageId。

POP

• 计算当前时间为最大分数。
• 获取分数在0和最大分数之间的消息。
• 将messageID添加到unack集合中，并从队列的有序集中删除这个messageID。
• 如果上一步成功，则根据messageID从Redis集合中检索消息。

ACK

• 从unack集合中删除messageID。
• 从Message有效集合中删除messageID。
  客户端未进行确认的消息，会被再度推回到队列中（这是一个定时任务负责检测）。

3、可用分区和机架意识

我们的队列是在Dynomite的JAVA客户端Dyno之上建立的，Dyno为持久连接提供连接池，并且可以配置为拓扑感知，此外，Dyno为应用程序提供特定的本地机架（在AWS中，机架是一个区域，例如 us-east-1a、us-east-1b等）,us-east-1a的客户端将连接到相同区域的Dynomite/Redis节点，除非该节点不可用，在这种情况下该客户端将进行故障转移。这个属性被用于通过区域划分队列。

分片
队列根据可用区域进行分片，将数据推送到队列时，通过轮训机制确定分片，这种机制可以确保所有分片的数据是平衡的，每个分片都代表Redis中的有序集合，有序集中的key是queueName和AVAILABILITY _ZONE的组合。

避免全局锁

• 每个节点（上图中的N1...Nn）与可用性区域具有关联性，并且与该区域中的redis服务器进行通信。
• Dynomite / Redis节点一次只能提供一个请求，Dynomite可以允许数千个并发连接，但是请求是由Redis中的单个线程处理，这确保了当发出两个并发调用从队列轮询元素时，是由Redis服务器顺序执行，从而避免任何本地或分布式锁。
• 在发生故障转移的情况下，确保没有两个客户端连接从队列中获取相同的消息。

处理Un-ACK的消息
后台进程监视UNACK集合中的消息，这些消息在给定时间内未被客户端确认（每个队列可配置）。这些消息将移回到队列中。

Dyno-queues分布式延迟队列的github地址是：
https://github.com/Netflix/dyno-queues