Chapter 29
A queue before storage
In the first minute of the new year, messages come at 10 times the usual rate, and storage can write only 20,000 a second. Does the sender have to wait for storage before getting the ACK?
This chapter is a first draft. The author is still checking it, and its text and numbers may change.
By chapter 28, each conversation is owned by one message server, which gives its messages their seqs. After the seq, the path is still v1’s: write the message to storage, send the ACKACKACK(确认)The receiver’s “got it” to the sender. In this series, the server’s ACK means the message is in the message log, not that anyone has received it.See the glossary once it is committed, then push (chapters 3 and 5).
Normally that is fine. v3 averages 4,630 messages a second and peaks at 13,900; storage was sharded in chapter 28 too, and suppose the shards holding messages can together write 20,000 a second, with room to spare. But in the first minute of the new year, or when a group suddenly takes off, messages come at several times the usual rate.
This chapter’s question: when messages come faster than storage can write them, should the sender wait for storage?
1. One minute of peak
Suppose the peak is 10 times the average, 46,300 messages a second, for one minute. Storage writes only 20,000 a second, so 26,300 more each second queue up in front of it.
At the end of that minute, about 1.58 million messages are queued. After the peak, messages fall back to the usual 4,630 a second, and storage writes only about 15,000 a second more than come in, so it takes about 103 seconds more to clear the queue.
2. Storage on the path: the ACK waits in the queue
The ACK waits for the commit, so time in the queue is time the sender waits for the ACK. The message sent in the last second of the peak waits 1.58 million ÷ 20,000 ≈ 79 seconds.
A phone cannot wait that long. Chapter 3 set it: with no ACK, resend at 1, 3, 7 and 15 seconds, and mark the message “failed” at 31 seconds. At the rates above:
- messages sent from about 24 seconds into the peak wait more than 31 seconds;
- not until about 62 seconds after the peak is the queue back under 31 seconds;
- the roughly 1.97 million messages sent in between all show “failed to send” on their senders’ phones.
Most of them will in fact be stored, just late. Ana sees a red exclamation mark and taps it to resend; the server got the message long ago, but she thinks it was lost. Even if the server recognises the duplicate at no cost (chapter 4), each message has been sent four extra times.
Push comes after the commit, so Ben is late too: the worst-hit message reaches him 79 seconds late.
3. Write a log first, then ACK
v3 adds a message logmessage log消息日志A durable, append-only queue: the hand-off between receiving and delivering. A message counts as received once it is in the log, and the server ACKs then. It usually runs on a message queue, such as a topic partitioned by conversation.See the glossary between the message servers and storage: a durable queue that can only be appended to, with everything written to it kept on 3 machines.
The send path becomes:
- The message server checks for duplicates (chapter 4) and takes a seq (chapter 28);
- it appends the message to the log partition that holds this conversation;
- once the log has stored it, the server sends the ACK, carrying the seq.
The log only appends at the end, and many messages go to disk in one write, much faster than storage’s random writes. Suppose it can take 200,000 messages a second: the 46,300 peak does not queue, the ACK comes back in a few milliseconds, and not one message “fails”.
A partition is one of the segments the log is split into, ordered within itself. A conversation’s messages always go into the same partition, so they are read out in seq order.
Behind the log, several consumers each read at their own pace:
- Push: sends each message to the devices online as it reads it (chapter 2).
- Conversation records: updates each member’s row and stamps the version (chapter 11). Who gets it is worked out from the member ranges in chapter 12: the member table keeps the seqs each person may see, from where to where, and message 4,823 goes to everyone whose range contains 4,823. If the consumer works this out a minute late and someone left the group in between, his row is still there and he is still counted: the same answer as working it out at once.
- Storage: writes the message into the message storemessage store消息存储The long-term history of messages, one timeline per conversation. Dispatch writes it after reading the log, so it lags the ACK a little.See the glossary, keyed by conversation + seq, so writing it twice still leaves one row.
Each consumer remembers where in the log it has read to, but not after every message; say once every 100. If it crashes at the 80th of those 100, it restarts from the place it last remembered and does those 80 again. So every consumer has to be safe to run twice: storage writes by “conversation + seq”, so writing twice still leaves one row; a push sent again lands on the same row on the phone, where (conversation, seq) is a unique key in the local database (chapter 7).
The 1.58 million messages of the peak still queue, but now it is “storage is behind” instead of “the sender waits”: at most 79 seconds behind, queued on the log’s disks rather than in anyone’s memory.
The furthest behind are the conversation records: each message updates a row for every recipient, about 310,000 small transactions a second at the peak (46,300 messages × 6.67 recipients on average). Suppose the records’ storage is sized for the usual peak: the record for the peak’s last message is written about 140 seconds late, and the records catch up about 3.5 minutes after the peak. Push does not wait for them, so messages still arrive at once; what is late is the order of the chat list and the unread counts.
Chapter 11’s to-do is this log. Back then, the message’s transaction wrote a row saying “hiking group 4,823: update every member’s conversation”, and a background job did the updates later. Now nothing extra is written: each message in the log is a to-do row, and the to-do is done up to wherever the conversation-records consumer has read. (Chapter 15’s to-do for one-to-one read receipts is different: it is written in the read transaction and is not a message, so it is still kept on its own.)
Chapter 3’s “stored” now means “in the log”. When the ACK comes back, the message is on 3 machines and cannot be lost; but it may not be in storage yet.
4. Three things to get right
One: make it fetchable before telling anyone. Push, conversation records and the latest seq all tell devices “4,823 is here”. A device that hears it may come to fetch at once: to fill a gap (chapter 5), or to get the newest message of a conversation it is behind on (chapter 6). If storage is still 79 seconds behind at that point, the fetch comes back empty.
The fix is to let one fast consumer go first: it writes the message into a cache of recent messages (in memory) and updates the latest seq, and only then are push and conversation records allowed to say “it’s here”. Reads check this cache first and go to storage only on a miss. The whole peak’s 1.58 million messages take about 316 MB in the cache. The open-source OpenIM uses exactly this order: write to Redis first, then hand off to the queue that writes MongoDB and the queue for push.
Two: late duplicates. v1 catches duplicates in two places: the recent message IDs in memory, and the (sender, message ID) unique key in storage (chapter 4). The second catches very late resends, say an app killed for an hour that resends from its outbox. Now that the ACK comes before storage, the unique key only takes effect once storage has written the message, which is too late: the server has already given the duplicate a new seq and ACKed it.
So:
- The window of recent IDs must be longer than storage can fall behind. The window is there for the burst, so size it for 5 minutes that include the burst minute: 46,300 × 60, plus the other 4 minutes at the usual peak, 13,900 × 240. That is about 6.11 million IDs and 196 MB, spread over the message servers.
- For later resends, the phone says “first sent this long ago” (worked out as a difference on the phone’s own clock, so it does not matter whether that clock agrees with the server’s); for anything older than the window, the message server first checks the unique key in storage before deciding whether to take a seq. Such resends are rare, so one lookup each is cheap.
Three: on a change of owner, don’t resume counting from storage. Chapter 28’s new owner carries on from the seq of the last message in storage. But storage may now be 79 seconds behind while the log already holds higher seqs, so counting on from storage would repeat seqs. The same goes for chapter 14’s two numbers on each message, the count so far and the sender’s running number (how many messages that sender has sent in the conversation); none of these may skip or repeat (one skipped or repeated number puts chapter 14’s unread count off by one). So the new owner first waits until the recent-message cache has read to the end of the log, takes the conversation’s last seq, count, running numbers and the last 5 minutes of message IDs from the cache, and only then starts serving. The cache is normally only milliseconds behind.
The unique key (conversation, seq) that chapter 28 relied on as the last guard also takes effect only once storage has written the message, long after the ACK. So the log itself has to keep out an old owner (chapter 28’s lease: an owner that cannot renew stops on its own, but it may stall for a few seconds before noticing): each append carries the lease number, and one older than any already seen is refused.
5. The numbers
- Peak: 46,300 messages a second for one minute; at most about 1.58 million queued, storage at most 79 seconds behind, caught up about 103 seconds after the peak.
- Senders: with storage on the path, about 1.97 million show “failed”; with the log first, 0.
- Log: 400,000,000 messages a day × 200 bytes = 80 GB; kept 3 days in 3 copies, 720 GB.
- Consumers at v3’s usual peak: storage 13,900 messages a second, about 70% of its capacity; push 139,000 a second (counted per device, 10 per message); conversation records about 93,000 small transactions and 185,000 rows a second (counted per person, one transaction each: 10 devices ÷ 1.5 devices per person = 6.67 people), which at 20,000 rows a second per storage node is 9.3 nodes (chapter 32 adds up the bill).
6. The cost
- One more system. The log cluster has to be deployed, scaled and watched: 3 replicas, 720 GB.
- An ACK does not mean it is in storage. Normally storage is only milliseconds behind; at the peak it is tens of seconds behind. Every consumer has to be safe to rerun and remember where it has read to, and someone has to watch how far behind each one is (chapters 33 and 36).
- A hot conversation is still a single lane. A group’s messages go into one partition and are read in order by one consumer; they cannot be split up to run in parallel. It is chapter 28’s “a hot conversation lives on one server” turning up again in the log.
- One more cache, and the order around it matters. A message must be fetchable before devices are told about it; on a change of owner, counting also carries on from the cache.
7. Other answers
- Write straight to storage. v1 and v2 do this; at low volume it is simplest, one system fewer.
- Buy storage for the peak. Prepare 3.3 times the usual peak’s write capacity for one minute of peak, idle for most of the year.
- Queue first, take the seq later. OpenIM’s send API returns as soon as the message is written to Kafka, and the ACK carries only the server’s message ID and a time (send.go); the consumers behind it take the seq, write the cache, and then hand off to storage and push. The upside is that the service accepting messages need not deal with seqs; the cost is that the ACK carries no seq, so the sender learns where its own message falls only from push or sync (chapter 5). Telegram’s API sits on the other side: send a message in a one-to-one chat and the
updateShortSentMessagethat comes back already holds the message’sidandpts(the account’s update sequence number), so the sender knows at once where it falls; whether the server queues first or stores first inside is not published. - DingTalk. A public article (阿里IM技术分享(九), in Chinese, by Yin Qixiu (尹启绣), a DingTalk technical expert) says: the application that receives messages only checks whether the message may be sent, puts it into RocketMQ and returns; the application behind it stores it, then hands it through a message queue to the sync service, which pushes it to those online. If writing to the queue fails there are two fallbacks: call the next application directly, and failing that, write a local redoLog that is replayed into the queue on a timer. If storing fails, the message is pushed anyway, and storing is retried from a separate queue.
8. This chapter’s decision
The server side of the path is clear now. But on the client side, every rule from chapter 3 to here has to be written again for iOS, Android, desktop and the web. Next: one SDK, many platforms.
Comments
Comments live in GitHub Discussions and need a GitHub account.