聊天期间以及用户再次登录时，Messenger 如何保持消息的顺序？

Question

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

\n

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

\n

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

\n

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

\n

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

\n

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

\n

现在让\xe2\x80\x99s 假设用户1 发送了更多消息M3 <2, 1> 和M4 <3, 1> 那么每个客户端都会有以下消息。\nM1 <1, 0>\nM2 <0, 1>\ nM3 <2, 1>\nM4 <3, 1>

\n

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

\n

谢谢。

\n

Answer 1

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

让我们假设爱丽丝和鲍勃之间的对话。

消息序列结构：

message<Alice seq number,  Bob sequence number>

需要注意的是，M1、M2、M3...中的数字仅用于区分消息，与实际消息序列没有任何关系。

从爱丽丝一侧看：

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>.

现在，从鲍勃一侧查看：

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.

对于鲍勃来说也是如此

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 的序列号，因此它将以这种方式存储。同样，它也为鲍勃做这件事。

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