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