Case study: Notification system

Every app sends messages: a one-time password (OTP), "your order has shipped", a sale offer. The interviewer says: "Design one notification system for the whole company. A campaign must reach 50 million users, and OTPs must still arrive in 5 seconds."

A weak answer draws one queue and a sender, and says "retry on failure". A strong answer keeps urgent messages apart from bulk messages. It counts how long a campaign takes. It says how a message is never sent twice, and how one user is not flooded.

At SDE-1 level you should draw the path of one message. At SDE-2 level you should add retries, duplicate protection and the numbers. At SDE-3 level you should add separate lanes, provider limits and what happens when a provider fails.

Quick recap (lessons 54, 56, 60, 61 and 62). A retry waits longer each time (backoff) and adds a random part (jitter). A token bucket lets requests pass at a steady rate. A queue can deliver a message twice, so work must be safe to repeat: an idempotency key or a unique constraint skips repeats. A message that fails too many times goes to a dead-letter queue, where a person looks at it. A permanent error is not retried. Wait for the last message = backlog / work rate.

Think about a school office that sends a notice to 5,000 parents. The clerk checks a list of parents who asked not to get notices. The clerk writes each notice and gives it to a post boy, a courier or a phone caller. Each of them can carry only so many a day. The head says that no parent gets more than 3 notices a week. A notice that says "your child is ill" goes with a separate runner, so it never waits behind the big bundle.

A notification system works the same way. In this lesson, a provider is an outside company that delivers a message for you: one for push, one for SMS, one for email. A push notification is a short message sent to a phone app. We use these ideas from earlier lessons: queues (lesson 58), retries (54) and rate limits (56).

Three lanes

Messages have different needs, so each kind gets its own queue and its own workers (a lane).

If all kinds share one queue, an OTP waits behind a campaign. So the OTP lane has its own workers, and marketing workers never take OTP work. Each channel (push, SMS, email) also has its own queue, because each provider has its own limit.

The path of one message

1. A service calls the API with the kind, the user, the data and an idempotency key (lesson 61). The API answers 202 Accepted (lesson 58) and saves a row in the log with the state NEW.
2. The preference check: does this user accept this kind on this channel? In our design, legal and security messages ignore marketing opt-outs.
3. The per-user limit (marketing only): a counter for each user and day, raised with INCR in Redis (lesson 37). Assumption: at most 3 marketing messages a day. If the counter passes 3, skip the message. OTP and transactional messages do not count.
4. A template plus the data makes the text, in the user's language.
5. The message goes to the queue of its lane and channel.
6. A sender worker takes the message and calls the provider with a timeout (lesson 54). It sends the notification ID as a key, if the provider accepts one.
7. The worker marks the row SENT. Later the provider tells us the result by a webhook (lesson 69), and a conditional update (lesson 66) marks it DELIVERED or FAILED.

Fan-out for a campaign

Fan-out means that one request spreads into many messages. A campaign is one request that becomes 50 million messages. Do not make them in the request.

1. The API saves the campaign and answers 202.
2. A fan-out job cuts the user list into batches of 1,000 user IDs and puts one message for each batch on a queue.
3. A batch worker handles one batch. It reads the preferences of all 1,000 users in one query. It checks the limits, makes the rows with a unique constraint on (campaign, user, channel), and queues the send messages. If the batch runs twice, the constraint stops the repeat rows.
4. A batch worker makes the next batch only when the send queue holds fewer than a set number of messages. This is back-pressure (lesson 63): the fast part waits for the slow part, so the queue does not grow without end.

If a batch worker crashes after it saves the rows and before it queues the messages, the rows stay in the state NEW. A timer job re-queues rows that are still NEW after 10 minutes (the idea of lesson 64: the memory of "still to send" lives in the database).

Provider limits and retries

A provider accepts only so many calls per second. Use one token bucket (lesson 56) for each provider, and keep your rate below the limit. When the provider answers 429, wait for the Retry-After time.

When a call fails:

• A permanent error, such as a phone token that is no longer valid: do not retry. Mark the row FAILED and remove the token.
• A short error, such as a timeout: retry with backoff and jitter (lesson 54), up to 5 tries.
• Tries used up: move the message to the dead-letter queue (lesson 62), with the reason. Alarm when it is not empty. Replay after the fix, at a chosen speed.
• Most calls fail: the provider is probably down. Pause all senders for 30 seconds (Assumption), so that the tries of every message are not used up for nothing.
• OTP only: keep a second SMS provider. If the first one times out, try the second one at once.

Three ways a user gets a message twice

1. The batch runs twice. The unique constraint on (campaign, user, channel) stops it.
2. A timeout after the provider accepted. The provider sent the push, but the reply was lost. A retry sends it again. Send the notification ID as a key, if the provider drops repeated keys. If it does not, accept a rare repeat for marketing.
3. A worker crashes after the call and before the mark. The row stays NEW, and the timer job queues it again. This gives at-least-once delivery (lesson 60), which is right here: a lost OTP is worse than a repeat.

Assumptions (made up to teach with, not real data):

• One campaign to 50,000,000 users by push. The goal is to finish in 30 minutes.
• The push provider accepts at most 50,000 calls per second from us. A call takes 20 ms.
• OTP: at most 500 per second, by SMS. The SMS provider accepts 1,000 calls per second, and a call takes 100 ms. Each OTP must arrive in 5 seconds.
• A batch has 1,000 users. A log row is 500 bytes. A queue message is 200 bytes. A Redis key is 100 bytes. One Redis server does 100,000 commands per second, and we plan for 70% (lesson 57).
• 0.1% of calls time out after the provider accepted. 0.5% of phone tokens are no longer valid.
• A weak design for comparison: one queue and one set of workers for all kinds and channels. It sends 35,000 messages per second, like the campaign.

Step 1: the campaign time. We send at 70% of 50,000: 0.7 x 50,000 = 35,000 per second. Time = 50,000,000 / 35,000 = 1,429 seconds, which is 23.8 minutes. This is inside 30 minutes. Workers needed = 35,000 x 0.02 = 700. This is the first answer to the predict box.

Step 2: the fan-out. 50,000,000 / 1,000 = 50,000 batches. One preference query for each batch means 50,000 queries, not 50,000,000. That is 1,000 times fewer. The log: 50,000,000 x 500 bytes = 25 GB for one campaign.

Step 3: the user limit. 50,000,000 INCR commands at 35,000 per second use 35,000 / 70,000 = 50% of one Redis server. The keys: 50,000,000 x 100 bytes = 5 GB, and they expire after one day.

Step 4: back-pressure. Suppose the batch workers make 100,000 messages per second, but the senders send 35,000. The queue grows by 65,000 per second. Making all rows takes 50,000,000 / 100,000 = 500 seconds. The queue then holds 65,000 x 500 = 32,500,000 messages. That is 32,500,000 x 200 bytes = 6.5 GB. With a cap of 200,000 messages, the queue holds at most 200,000 x 200 bytes = 40 MB. That is 200,000 / 35,000 = 5.7 seconds of sending.

Step 5: the OTP lane. In the weak design with one shared queue, an OTP behind 1,000,000 messages waits 1,000,000 / 35,000 = 28.6 seconds. This is the second answer to the predict box. It is far above the limit of 5 seconds. In its own lane, 500 OTPs per second use 50% of the SMS limit. The workers needed are 500 x 0.1 = 50. If SMS provider A fails after a 1-second timeout, we try provider B, which takes 0.1 seconds. Our part is 1 + 0.1 = 1.1 seconds. If B also fails after 1 second, our part is 2 seconds. Both are inside 5 seconds. The phone network adds its own time, which we do not count.

Step 6: permanent errors. 0.5% x 50,000,000 = 250,000 messages have an invalid token. With 5 tries each, the 4 extra tries make 1,000,000 wasted calls. That is 1,000,000 / 35,000 = 28.6 seconds of provider capacity. Skipping the tries saves all of it.

Step 7: duplicates. 0.1% x 50,000,000 = 50,000 calls time out after the provider accepted. With no key, 50,000 users get a second push. With the key, the number is 0 (Assumption: the provider drops repeated keys). Assumption: a server has 100 workers. If it crashes, at most 100 messages are in progress. Five crashes give at most 500 repeats. That is 500 / 50,000,000 = 0.001%.

Step 8: the provider is down for 10 minutes. The senders pause. 35,000 x 600 = 21,000,000 messages are not sent in that time. The campaign ends 600 seconds later: 1,429 + 600 = 2,029 seconds, which is 33.8 minutes. That is over the goal of 30 minutes. OTPs are not affected, because they use another provider and another lane.

• Separate lanes solve an OTP that waits behind a campaign (28.6 seconds against 5). They cost more queues and workers to run. I would use a lane for each kind that has its own deadline.
• A provider rate limit solves calls that the provider refuses. It costs time: the campaign takes 23.8 minutes, not 17 (at the full 50,000 per second). I would raise the rate only after I check how the provider counts.
• At-least-once delivery solves lost messages. It costs a rare repeat. I would use it for all lanes, and add the key for transactional messages.
• Back-pressure solves a huge queue (6.5 GB against 40 MB). It costs a slightly slower fan-out job.
• A per-user limit solves a flood for one user. It costs a counter for each user (5 GB) and the risk that a sale message is skipped. I would make the limit a setting for each kind.
• A dead-letter queue solves messages that fail for ever. It costs an owner and an alarm.

"One queue is enough, because workers take messages in order." An OTP behind a campaign waits 28.6 seconds. Give each kind its own lane.

"When a send fails, retry until it works." A bad token fails every time. In the example, retries wasted 28.6 seconds of provider capacity. Skip permanent errors, and use a dead-letter queue for the rest.

"The idempotency key from the caller stops all duplicates." It stops the same API call from creating two rows. It does not stop a retry to the provider after a timeout, or a crash after the call. Those need the notification ID as a key and the NEW state.

1. Name three ways a user can get the same notification twice. Give one fix for each.
2. A campaign goes to 20,000,000 users. The provider accepts 40,000 calls per second, and we plan for 70%. A call takes 25 ms. (a) How long does the campaign take? (b) How many workers? (c) An OTP waits behind 500,000 messages in the same queue. How long does it wait?
3. A user has already received 3 marketing messages today. The user now asks for an OTP, and the shop also sends an order update. Does the per-user limit block them? Why?