2

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

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

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

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

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

在上述场景中，user1 将看到 M1 后跟 M2，而 user2 将看到 M2 后跟 M1。现在，如果每个用户还为每个客户端（单独）生成每个消息的序列号或时间戳。然后在上面的场景中，user1 将发送序列为 <1 (user1 seq), 0(user2 seq) > 的消息 M1，而 user2 将发送序列为 <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。现在，我想知道再次登录时如何为用户 1 和用户 2 保留相同的顺序？

谢谢。

4

1 回答 1

3

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

让我们假设 Alice 和 Bob 之间的对话。

消息序列结构：

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

现在，从 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.

对于鲍勃也是如此

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.

所以对于爱丽丝来说，它将按照鲍勃的序列号顺序：

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。

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

于 2021-09-18T06:34:55.213 回答