分布式系统中的消息排序

Question

我想构建一个分布式系统，其中我有分布在许多服务器上的“线程”（具有自己 ID 的消息集合，而不是系统进程）。这些线程必须具有两个关键属性：

1. 线程中的每条消息都必须有一个订单号，以反映它基于时间在线程中的位置。例如，通过说“thread1/message10”，我可以在线程 #1 中找到消息 #10
2. 一旦新消息被添加到线程中，系统必须能够为其分配一个订单号，该订单号对于所有服务器上的所有线程实例都是一致的，并且该编号绝不能更改。

我想知道是否有任何已知的解决方案、库或算法可以帮助我实现第二个选项，因为现在我认为这是一个大问题，因为由于许多因素，不同的服务器可以在不同的时间收到相同的消息，这可能会影响它订单号。

只是为了概述我目前对一个问题的想法，说我有 3 个服务器，我的分布式线程已经包含 5 条消息，每个服务器向它自己的线程和其余两个发送一条新消息。

• 幼稚的订购。每个服务器都认为它自己的消息编号是 6，而来自其他服务器的其余两条消息将根据网络延迟和许多其他随机因素在到达时获得它们的编号，因此服务器之间的订单号不一致。这立即是不可接受的。

• 基于 UTC 时间戳的排序。当每个线程收到一条新消息时，我假设 10 条前面的消息已经具有正确的订单号，提取它们的时间戳并通过在最近 10 个时间戳的列表中找到它的时间戳位置来确定新消息的订单号。我猜这可能有效，但它确实需要可以分配某些消息的订单号，然后在某些时候进行更改，这是不可接受的。另外，当传入的消息数量很大时，我不确定这是否会正常工作。

感谢所有的帮助。

Answer 1

这是被称为Atomic Broadcast 的分布式系统中的一个基本问题，许多解决方案提供了不同的性能和适用性权衡（请参阅维基百科页面引用的调查）。在实践中，最常用的是基于Paxos（例如libpaxos）或基于 Totem（例如Corosync或Spread）。选择其中之一时的一个关键问题是，如果网络分区，您预计会发生什么：它应该停止对消息（块）进行排序还是应该为每个分区生成独立的订单？