distributed-computing - Messenger 如何在聊天期间和用户再次登录时保持消息的顺序？

Question

我在面试中被问到这个问题，但无法回答。

当两条消息并发时，FB Messenger 如何对用户端的消息进行排序，以避免在聊天期间和用户再次访问 Messenger 时显示顺序不同。我想我们可以为每条消息存储一个时间戳，这是服务器收到消息的时间。但是，这不能确保为客户正确排序消息。

假设服务器时间戳无法确定消息的确切顺序，如下所示:

1. 用户 1 向用户 2 的服务器发送消息 M1。
2. 服务器在 T1 收到 M1。
3. 与此同时，用户 2 向用户 1 的服务器发送消息 M2。
4. 服务器在T2收到消息M2，使得T2 > T1。
5. 服务器将消息 M1 发送给用户 2，将消息 M2 发送给用户 1。
6. 因此用户 1 将首先看到 M1，然后是 M2，而用户 2 将首先看到 M2，然后是 M1。

我读到解决这个问题，我们可以使用矢量时钟，但无法理解如何在聊天期间和用户再次登录时为不同用户保留消息顺序。

在上述场景中，用户 1 将看到 M1 后跟 M2，而用户 2 将看到 M2 后跟 M1。现在，如果每个用户还为每个发送给每个客户端的消息生成一个序列号或时间戳(分别)。然后在上面的场景中，用户 1 将发送序列为 <1 (user1 seq), 0(user2 seq) > 的消息 M1，用户 2 将发送序列为 <0 (user1 seq), 1(user2 seq) > 的消息 M2。因此，当消息同时到达 user1 和 user2 时，它们将具有: M1 <1, 0> M2 <0, 1>

现在假设 user1 发送更多消息 M3 <2, 1> 和 M4 <3, 1> 那么每个客户端都会有以下消息。 M1 <1, 0> M2 <0, 1> M3 <2, 1> M4 <3, 1>

因此在这种情况下，当用户登录时，用户 1 和用户 2 在聊天期间的显示顺序分别为 M1、M2、M3、M4 和 M2、M1、M3、M4。 现在，我想知道当再次登录时，user-1 和 user-2 将如何保留相同的顺序结束？

谢谢。

Answer 1

这里的问题是我们如何根据这些序列号为每个用户生成一致的聊天对话。

让我们假设 Alice 和 Bob 之间有一段对话。

消息序列结构:

message<Alice seq number,  Bob sequence number>

需要注意的是，M1,M2,M3,...中的数字只是用来区分消息，与实际的消息顺序没有任何关系。

Alice 端的 View :

1) Alice sends M1<1,0>
2) Bob sends M2<1,1>
3) Alice sends M3<2,1>
Now, Bob sends one message(M5) but before Alice gets that, Alice sends one more message.
4) Alice sends M4<3,1>
And now, she received a message from Bob.
5) Bob sends M5<2,2> 
Since Bob didn't get M4 before sending M5 the Alice sequence number in M5 is 2. 
If he would have got that, the M5 would look like M5<3,2>.

现在，从 Bob 的角度看:

1) Alice sends M1<1,0>
2) Bob sends M2<1,1>
3) Alice sends M3<2,1>
Now, Bob sends message M5 before getting M4 from Alice
4) Bob sends M5<2,2>
5) Alice sends M4<3,1>

现在，当 Alice 下次登录时，服务器将获取数据并对其进行排序:

1) First sort with Bob sequence number. 
2) if two or more messages have the same Bob's sequence number then sort it in Alice's sequence number within them.

Bob 同样如此

1. First sort the message-ids with respect to Alice sequence number.
2. if two or more messages have the same Alice's sequence number then sort it in Bob's sequence number within them.

所以对于 Alice，它将按照 Bob 的序列号的顺序:

M1<1,0>  
M2<1,1>  
M3<2,1>  
M4<3,1>  
M5<2,2>  

对于 Bob，它将按照 Alice 的序列号的顺序:

M1<1,0>  
M2<1,1>  
M3<2,1>  
M5<2,2>  
M4<3,1>

我们将如何在数据库中存储消息序列:

客户如何知道哪个是他/她的序列号？

在我们的示例中，我们决定第一个数字是 Alice 的序列号，第二个是 Bob 的。但是实时如何做出这个决定。如果我们约定第一个序列号始终是发送者的序列号，第二个是接收者的序列号，那么这很容易解决。所以当有人收到一条消息时，他就知道第一个序列号是发送者的序列号。当他准备下一条消息时，他从最后收到的消息中增加他的序列号并将其放在第一位，并从收到的消息中获取发送者的序列号并将其放在第二位。

服务器如何知道哪个序列号必须存储在哪里？

既然我们定义了上述约定，如果服务器从 Alice 那里收到消息，第一个字段将是 Alice 的序列号，第二个字段将是 Bob 的序列号，因此它将以这种方式存储。同样，它也为 Bob 做这件事。

注意:我也在寻找上述问题的解决方案，但没有在网上找到任何可以提供帮助的信息，所以我自己制定了解决方案。如果它破坏了任何用例，请纠正我，以便我们可以改进它或尝试其他方法。