Many businesses need to consider the sequential nature of message delivery:

  • Single-chat message delivery ensures that the order of sending by sender is consistent with the order of presenting by receiver

  • Group chat message delivery, to ensure that all recipients show the same order

  • Top – up payment message to ensure that the same user initiated requests in the server execution sequence consistent

Message ordering is a very difficult problem in distributed system architecture design. What are the common optimization practices?

Compromise 1: Use the timing of the client or server

In either case, a ruler is needed to measure the order of the sequence, depending on the business scenario, on the client or server side of the time, for example:

  • The order of mail display is based on the sending time of the client

Voiceover: The sender simply changes the date in the email protocol to 1970 or 2970, and the sender can remain “top” or “bottom” after the recipient receives the email.

  • It is impossible for the client to modify the local time so that it can be seconds killed in advance

Compromise two: the server generates monotonically increasing ids for timing purposes

For strictly sequential business scenarios, singleton db seq/ auto_INC_id can be used to generate monotonically increasing ids to ensure sequence.

Voice-over: This single point of id generation can easily become a bottleneck.

Tradeoff three: if the business can accept a small error trend increasing ID

The timing of messages, posts, or even seconds is not so precise:

  • The timing of the chat messages released within 1s is out of order, it’s ok

  • The same as the post within 1s is not in order, nothing

  • The second kill initiated within 1s. Due to the time error between multiple servers, the second kill on server A is successful, while the second kill on server B has not started yet, which is acceptable in business (users can not perceive).

Therefore, for most businesses, the business needs can be satisfied with long time trend increasing timing, and very short time timing errors are acceptable to some extent.

Thus, the ID generation algorithm can always be distributed to generate ids for timing purposes.

Compromise 4: single point serialization can ensure the same timing of multiple machines

Data redundancy is required to ensure high availability. The same data is stored in multiple places. How do I ensure that the modification messages of these data are consistent?

“Single point serialization” is possible:

  • First serialize the operation on a machine

  • Then the operation sequence is distributed to all machines to ensure that the operation sequence of multiple machines is consistent, and the final data is consistent

Typical scenario 1: Primary/secondary database synchronization



Op1, OP2 and OP3 are initiated in the upstream of the master database respectively. The master database serializes all SQL write operations OP3, OP1 and OP2, and then sends the same sequence to the slave database to ensure the consistency of all database data. Is to use the idea of “single point serialization”.

Typical scenario 2: File consistency in GFS



The Google File System (GFS) stores multiple copies of a File to ensure File availability. When multiple upstream streams perform write operations on the same File, the primary chunk-server serializes the write operations first and then sends the serialized operations to other chunk-servers. To ensure data consistency of redundant files.

One-to-one chat, how to ensure that the order of sending and receiving is the same?

According to the requirement of single person chat, sender A successively sends msG1, MSG2 and MSG3 messages to receiver B. Can the consistency of display time sequence of these three messages be guaranteed (sending and displaying in the same order)?

The design idea is as follows:

(1) If the server single point serialization time sequence is used, it may appear that the time sequence of the message received by the server is MSG3, MSG1, MSG2, which will be inconsistent with the sending sequence.

(2) In business, there is no need for global message consistency, but only for the same sender A, the time sequence of the message sent from TA to B is consistent. In common optimization schemes, the absolute time sequence of the local sender A is added to the message sent from A to B to represent the display time sequence of the receiver B.

msg1{sender:A, seq:10, receiver:B, msg:content1}

msg2{sender:A, seq:20, receiver:B, msg:content2}

msg3{sender:A, seq:30, receiver:B, msg:content3}



The possible problem is that if the receiver B receives MSG3 first, MSG3 will be displayed first. After receiving MSG1 and MSG2, msG3 will be displayed before MSG3.

Group chat messages, how to ensure that the recipients receive the same order?

Group chat message requirements, N group members chat in a group, how to ensure that all group members receive the same message display time sequence?

The design idea is as follows:

(1) It is assumed that the seQ of the sender is used to ensure timing, just like the single-chat message. Since the sender is not clicking, SEQ cannot be uniformly generated and there may be inconsistency.

(2) Thus, a single point of the server can be used for serialization.



As shown in the figure above, the sending process of group chat is as follows:

(1) Sender1 emits MSg1, sender2 emits MSG2;

(2) MsG1 and MSG2 pass through the access cluster and service cluster;

(3) The Service layer takes a unique SEQ from the bottom layer to determine the display sequence of the receiver;

(4) Service gets SEQ 20 for MSG2 and 30 for MSg1;

(5) Deliver messages to multiple groups of friends through delivery service. Even if the group members receive MSG1 and MSG2 at different times, they can be presented uniformly according to SEQ;

This method can be implemented, all group members of the message display time is the same.

The downside is that a service that generates a globally increasing sequence number can easily become a system bottleneck.

Is there any further optimization method?

In fact, the group message does not need to ensure the global message sequence is ordered, but only to ensure that the message within a group is ordered, so “ID serialization” becomes a good idea.



In this scheme, the service layer no longer needs to go to a unified backend to get the global SEQ, but to make a small change in the service connection pool level, to ensure that a group of messages fall on the same service, the service can serialize all the messages of the same group with the local SEQ. Ensure that all group members see messages in the same time sequence.

At this point, using the local clock to generate SEQ works, isn’t it clever?

conclusion

(1) To be “orderly”, there must be a scale to measure “orderly”, which can be a client scale or a service scale;

(2) Most businesses can accept a large range of ordered trends and a small range of errors; Absolutely ordered business, can take advantage of the server absolute timing ability;

(3) Single point serialization is a common method to ensure the sequence unification of multiple machines. Typical scenarios include db master-slave consistency and GFS multi-file consistency;

(4) One-to-one chat, as long as the timing sequence of sending and receiving is consistent, client SEQ can be used;

(5) For group chat, the server SEQ is needed to ensure the consistency of message timing of all receivers. There are two methods: one is single point absolute timing, and the other is ID serial;

Thinking is more important than conclusion, I hope you have a harvest.

The Architect’s Path – Share practical technical articles