我正在使用分布式系统的Birman-Schiper-Stephenson协议，目前假设任何节点的对等集都不会改变。正如协议规定的那样，从节点序列到节点的消息必须放入“延迟队列”中。我的问题是延迟队列的组织，我们必须在消息中实现某种顺序。在决定订单后，我们必须制定一个'唤醒'协议，在当前时间戳被修改后有效搜索队列，以确定是否有一个延迟的消息可以'唤醒'并被接受。高效实现Birman-Schiper-Stephenson（BSS）协议的延迟队列
我正在考虑根据它们的向量时间戳与此节点的时间戳的差异点将延迟的消息分隔成多个分区。但箱的数量可能非常大，维护它们效率不高。
请为此类队列推荐一些设计。
抱歉，延迟 - 直到现在才看到您的问题。总之，如果你看看Isis2.codeplex.com，你会发现在Isis2中，我有一个causalsend实现，它使用了我们在BSS论文中描述的相同的向量时间戳方案。我所做的是让我的消息按照部分顺序排列，按VT排序，然后当发生传递时，我可以查看延迟的队列并将队列送到队列的前端，直到找到不可交付的东西。背后的一切都将无法传递。
但实际上这里有一个更深刻的见解：你实际上从不想让延迟消息的队列变得很长。如果队列比几条消息（比如说50或100）长，你会遇到这样的问题：队列中的人可能持有相当多的字节数据，并可能开始分页或以其他方式缓慢运行。所以它变成了一个自我延续的循环，因为他有一个队列，他很可能会丢掉信息，因此排队越来越多。此外，从他的角度来看，紧急的事情是恢复导致其他人失灵的错过消息。
这个加起来就是你需要一个流量控制方案，在这个方案中，待处理异步数据量保持很小。但是一旦你知道队列很小，搜索每一个元素将不会很昂贵！因此，这种更深层次的观点认为流量控制无论如何都是必要的，然后由于流量控制（如果您的流量控制方案可行），队列很小，而且由于队列很小，因此搜索不会很昂贵！