IM Systems in Depth

Chapter 28

Sharing out the conversations

At 13,900 messages a second, one message server and one counter table can no longer cope. Once the work is split over several servers, who hands out the hiking group’s next seq?

This chapter is a first draft. The author is still checking it, and its text and numbers may change.

By v3, 10,000,000 people use the app every day, and the evening peak is 13,900 messages a second. All of them pass through the message layer: dedup (chapter 4), take a seq (chapter 5), store, send the ACK.

Chapter 5 takes the seq by adding one to the conversation’s counter in the same transaction that writes the message. Add the to-do row that chapter 11 writes in that transaction too (chapter 11: first record one “to-do” row, then a background job works through it, updating each member’s conversation record), and each message writes three rows (the message, the counter, the to-do):

13,900 × 3 = 41,700 rows a second, 2.1 times one storage node’s 20,000 rows a second

The message servers are in the same position. Suppose one can handle 5,000 messages a second (this chapter’s assumption): the peak needs 3, plus 1 spare in case one fails, so 4 servers. Storage has to be split into shards too; this chapter leaves aside how.

Once there are 4 servers, who hands out the hiking group’s next seq? Chapter 5’s guarantee has to hold: within a conversation, seqs are contiguous, never repeat and never go backwards.

1. The first answer: any server will do, the lock stays in storage

The easiest split: message servers keep no state, a load balancer sits in front, and each message goes to whichever server is free. Storage is split into shards by conversation, and the hiking group’s counter and messages live on the same shard. Taking a seq is still chapter 5’s transaction: lock the counter row, add one, write the message, commit.

This is correct. There is only one counter and its lock is in storage, so whichever of the 4 servers writes has to queue for the lock, and seqs stay contiguous. While storage is healthy, this is entirely enough.

Its cost hides in “queue for the lock”: a conversation can have only one transaction at a time. At 5 milliseconds per storage write, a conversation can take at most 200 messages a second; when storage is sick and a write takes 500 milliseconds (chapter 36’s assumption), only 2 a second. Chapter 5 worked out both numbers.

Two smaller things: the “recent message IDs” that dedupdedup去重When a message ID arrives again, return the first result instead of storing another copy. The network can only deliver at least once; dedup makes each message show once.See the glossary needs (chapter 4) are not in any one server’s memory, so they go into a shared cache, one more round trip per message; and two messages of the same conversation pushed out by two servers can reach the phone out of order: the phone gets number 8 before number 7, so, as in chapter 5, it waits 0.5 seconds and, if 7 still has not come, fetches it.

2. Watch it break: 30 seconds of slow storage

Storage is sick for 30 seconds, and every write takes 500 milliseconds. The hiking group is busy, 5 messages a second (an assumption).

  • The lock in storage: a conversation can write only one message at a time, 2 a second. Of the 150 messages that arrive in those 30 seconds, only 60 are stored; 90 are still queued. The last one is number 150; it arrives at second 30 and only gets written at second 75, a wait of 45 seconds. Of the 150, 148 wait past chapter 3’s 1-second first timeout, the phones start resending, and storage gets even busier.
  • If all of this conversation’s messages are on one server: it can gather the queued messages into a batch and write them in one go. One batch per 500 milliseconds, about 2.5 messages a batch, the longest wait 0.9 seconds; none waits more than 1 second.

Batching needs every message of a conversation to reach the same server. A load balancer that spreads them at random scatters them over 4 servers, and they cannot be gathered.

3. One owner per conversation

So split the work another way: each conversation is assigned one message server as its owner, and only that server handles the conversation’s messages. This is sharding by conversationsharding by conversation按会话分片Each conversation is owned by one message service. Its seq is then assigned by a single owner, which is what keeps the order.See the glossary.

The owner keeps two things about the conversation in memory:

  • The counter: the next seq is the counter plus one, with no lock to take in storage.
  • The recent message IDs: dedup checks its own memory. As chapter 4 said, at the v3 peak, 32 seconds of messages means about 440,000 IDs, to be spread over several message servers: with 4, about 110,000 IDs and 3.5 MB each.

When a message reaches its owner: check for a duplicate, give it a seq, write it to storage together with the other messages of the conversation that are queued, send the ACK once written (chapter 3’s “ACK only once stored” stands), then push in seq order. A conversation has only one batch being written at a time, and the next batch is written only after this one commits, so seq order is still commit order (chapter 5).

The counter row is no longer written, so each message goes from three rows to two. To find a conversation’s latest seq (when chapter 6’s cache does not have it), look up its largest seq in the message table; the (conversation, seq) unique key serves as the index.

If the owner gives out a seq and the write then fails, that seq is left empty and never given to another message: the write may in fact have succeeded with only the reply lost. If it truly was not written, the phone comes to fetch the gap and the server answers “seq 6 does not exist”. Chapter 5 said this would come up.

4. Who is the owner: modulo or a hash ring

When the gateway receives Ana’s message to the hiking group, it has to work out the owner. The most direct way is modulo: hash the conversation ID and take the remainder after dividing by the number of servers. With 4 servers the remainder is 0 to 3, which fits exactly.

Users grow, and a 5th server is added. The divisor goes from 4 to 5, and almost every conversation’s remainder changes:

Modulo: from 4 servers to 5, 80% of conversations change owner

Why 80%: take hash values 20 at a time; only 4 of them (0, 1, 2, 3) leave the same remainder when divided by 4 and by 5, one fifth. The other four fifths change owner.

Changing owner is not free: the new owner has to read the conversation’s last seq once, and its in-memory message IDs have to build up again. With 80% of conversations moving at once, it is as if the whole message layer restarted. If one server fails and 4 become 3, 75% move too.

Consistent hashing (Karger et al., 1997) lays hash values out on a ring. Each server takes some points on the ring; a conversation’s hash lands on the ring, and the owner of the first point clockwise from it is the conversation’s owner. A new server takes over only the stretches that fall just before its own points:

Hash ring: from 4 servers to 5, in a simulation of 100,000 conversations, 18.1% moved (in theory 1/5); when one fails, only its own 24.7% move

With one point per server, the stretches on the ring vary in length, and the busiest server gets 1.43 times the average; with 100 points each, the busiest gets only 1.08 times.

The ring itself is kept in a coordination service (something like etcd or ZooKeeper); each gateway keeps a copy and works out the owner itself.

5. Hand-over: only one owner at any moment

The real danger is two owners at once. Say owner A stalls for a few seconds, everyone thinks it is dead, and the hiking group is handed to B. B reads the last seq as 4,823 and gives the next message 4,824; then A wakes up and gives 4,824 to a message it was still holding. One seq, two messages.

WeChat’s sequence-number service ran into the same problem. Its rule is that “at any moment, any uid is served by one and only one AllocSvr”, and it relies on leases (a grant with an expiry: if the holder does not renew it in time, it lapses on its own and someone else may take over; InfoQ, 2016): an AllocSvr that cannot get the latest allocation within N seconds stops serving on its own; a newly assigned range of users is served only after N seconds.

We use the same idea, with N = 10 seconds (an assumption). The owner renews its lease with the coordination service every few seconds; if it cannot renew within N seconds, it stops handing out seqs on its own. The coordination service hands its conversations to someone else only after N seconds without a renewal. The old owner’s N seconds count from when it sent the renewal, earlier than the coordination service’s. Say the old owner sends its last renewal at 10:00:00 and the coordination service receives it at 10:00:00.1; the old owner stops itself at 10:00:10, and the coordination service hands the conversations over only at 10:00:10.1. So by the time the new owner starts, the old one has already stopped.

There are two kinds of hand-over:

  • Planned (adding servers, a deploy): the old owner first stops taking new messages for the conversation, finishes writing what it holds, then lets go. The new owner reads the last seq once when the next message arrives, about 5 milliseconds. If a gateway’s copy of the ring is not yet updated and sends a message to the old owner, the old owner refuses it and the gateway checks the ring again.
  • Unplanned (a server dies): the only option is to wait for the lease to run out. If a server dies at peak, its quarter of the conversations stops for up to 10 seconds: 13,900 × 25% × 10 seconds, about 34,750 messages delayed. The phones resend as in chapter 3, and in the end all of them are stored.

Clocks drift, processes stall, and writes the old owner sent before it stopped may land very late. So there are two last guards, both unique keys in storage:

  • (conversation, seq) (chapter 5): if two messages are both written as 4,824, the second write is refused. The owner rereads the last seq; that message got no ACK, so the phone resends it and it gets a new seq.
  • (sender, message ID) (chapter 4): the new owner’s in-memory message IDs are empty, so it cannot recognise resends from around the hand-over; when a write hits this unique key, it looks up the original message and sends the same ACK.

6. The numbers

  • Storage writes: each message goes from three rows to two, 27,800 rows a second at peak, still 1.4 times one storage node. Storage has to be sharded too; this chapter does not avoid that, it only stops queuing for locks in storage.
  • Moves: adding one server moves 80% with modulo, about 20% with a hash ring.
  • Unplanned hand-over: when a server dies, about 34,750 messages arrive up to 10 seconds late.

7. The cost

  • The message layer now has state. Message servers used to restart freely; now a restart means a hand-over, and deploys go one server at a time (chapter 35).
  • One more coordination service. The ring and the leases live there, and it has to be highly available itself.
  • A busy conversation can only be on one server. A 500-member group is fine; for groups of tens of thousands and live rooms, when one server is not enough, there is another design (chapters 40 and 41).
  • Seqs can have gaps. A seq whose write failed is not reused, and the phone has to accept “this seq does not exist”.

8. Other answers

  • The lock stays in storage (section 1). No hand-over and no coordination service; enough while storage is healthy.
  • WeChat’s seqsvr (InfoQ, 2016). It hands out seqs per user, and “only requires them to increase, not to be contiguous”: it keeps the current seq cur_seq and a ceiling max_seq in memory, and only when it reaches the ceiling does it raise the ceiling by a step and write to disk once. With a step of 10,000, disk writes fall from about ten million a second to about a thousand; after a restart it carries on from the ceiling, so seqs jump a long way. Owners are not set by a hash ring; an arbitration service assigns ranges of users to each machine.
  • Slack’s channel servers: each channel server is assigned a share of the channels by consistent hashing, and when one fails a replacement takes over in “under 20 seconds” (Slack Engineering, 2023).
  • Discord: Discord describes itself as a distributed system built on consistent hashing, and uses a ring to look up which node an object lives on (Discord, 2017).
  • Telegram’s two numberings (chapter 6 touched on them): in Telegram’s public API, message IDs in private chats and basic groups are per account: all of one account’s private chats and basic groups share one sequence, so the same message has different IDs for different people. Each channel and supergroup has its own sequence, and everyone sees the same IDs (Telegram API: updates). The first is like WeChat’s seqsvr numbering per user, the second like this chapter numbering per conversation. Which server hands out the numbers, Telegram has not published.

9. This chapter’s decision

The owner still waits for storage to finish writing before it sends the ACK. In a real flood, such as the first minute of the new year at ten times the all-day average, storage still cannot keep up. Next: a queue before storage.

Comments

Comments live in GitHub Discussions and need a GitHub account.