Как мессенджер поддерживает последовательность сообщений во время чата и при повторном входе пользователя в систему?

Question

Мне задали этот вопрос в интервью, и я не смог на него ответить.

Как мессенджер FB упорядочивает сообщения на стороне пользователя, когда два сообщения являются одновременными, чтобы избежать различий в порядке отображения во время периода чата и при повторном посещении мессенджера пользователем . Я подумал, что мы можем хранить метку времени с каждым сообщением, то есть время, когда сообщение получено сервером. Однако это не гарантирует правильный порядок сообщений для клиентов.

Возьмем сценарий, в котором временная метка сервера не может определить точный порядок сообщений, будет выглядеть следующим образом:

1. Пользователь-1 отправляет сообщение M1 на сервер для пользователя-2.
2. Сервер получает M1 в T1.
3. Между тем, Пользователь-2 отправляет сообщение M2 на сервер для пользователя-1.
4. Сервер получает сообщение M2 в момент T2, так что T2> T1.
5. Сервер отправляет сообщение M1 пользователю-2 и сообщение M2 пользователю-1.
6. Таким образом, Пользователь-1 сначала увидит M1, а затем M2, тогда как Пользователь-2 сначала увидит M2, а затем M1.

Я прочитал, что решает эту проблему, мы можем использовать векторные часы, но не смог понять, как последовательность сообщений сохраняется для разных пользователей во время чата и при повторном входе в систему .

В приведенном выше сценарии пользователь 1 увидит M1, за которым следует M2, тогда как пользователь 2 увидит M2, за которым следует M1. Теперь, если каждый пользователь также генерирует порядковый номер или временную метку для каждого своего сообщения каждому клиенту (отдельно). Затем в сценарии выше user1 отправит сообщение M1 с последовательностью <1 (user1 seq), 0(user2 seq)>, а user2 отправит сообщение M2 с последовательностью <0 (user1 seq), 1(user2 seq)>. Итак, когда оба сообщения поступят на пользователя user1 и user2, они будут иметь:M1 <1, 0>M2 <0, 1>

Теперь предположим, что пользователь1 отправляет больше сообщений 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 при повторном входе в систему ?

Спасибо.

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>

Теперь, когда Алиса войдет в систему в следующий раз, сервер получит данные и отсортирует их:

      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>  

Для Боба это будет порядковый номер Алисы:

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

Как мы будем хранить последовательности сообщений в базе данных:

Как клиент узнает, какой у него порядковый номер?

В нашем примере мы решили, что первое число будет порядковым номером Алисы, а второе - номером Боба. Но в реальном времени, как это решение будет принято. Эту проблему легко решить, если мы условимся, что первый порядковый номер всегда будет порядковым номером отправителя, а второй - получателем. Поэтому, когда кто-то получает сообщение, он знает, что первый порядковый номер - это порядковый номер отправителя. и когда он готовит следующее сообщение, он увеличивает свой порядковый номер от последнего полученного сообщения и помещает его на первое место и берет порядковый номер отправителя из полученного сообщения и помещает его на второе место.

Как сервер узнает, какой порядковый номер и где должен храниться?

Теперь, поскольку мы определили вышеупомянутое соглашение, если сервер получает сообщение от Алисы, первое поле будет порядковым номером Алисы, а второе - порядковым номером Боба, поэтому он будет храниться таким образом. То же самое и с Бобом.

Примечание: я также искал решение вышеуказанной проблемы, но не нашел в сети ничего, что могло бы помочь, поэтому я сделал свое собственное решение. Пожалуйста, поправьте меня, если это нарушает какой-либо вариант использования, чтобы мы могли улучшить его или попробовать что-то еще.