Queues: what they solve, and what must stay in the request

Many features do more work than the user needs to wait for. A food app, after you pay, sends an SMS, sends an email, adds points and tells the restaurant. The interviewer asks: "Checkout takes three seconds. How do you make it fast?"

A weak answer says "do it in the background" and moves every step there. A strong answer says which step must stay in the request and why. It also says what moving work costs. The work happens afterwards. A job can run twice. The pile of waiting jobs can grow.

At SDE-1 level you should explain how a line of waiting jobs works and name two jobs that can move. At SDE-2 level you should decide what stays, and do the arithmetic for the pile of waiting jobs. At SDE-3 level you should also keep urgent jobs apart from slow ones.

Think about a tea stall with one person who takes orders and two who make tea. The order-taker writes each order on a paper slip and puts the slip in a box. The tea makers take slips from the box one by one. The customer pays, gets a token and leaves. The customer does not wait while the tea is made. If ten customers come at once, the slips wait in the box. Nobody is turned away.

Synchronous and asynchronous

In synchronous work, the caller waits until the work is finished. In asynchronous (async) work, the caller hands the work over and continues at once. The work finishes afterwards.

A request takes the sum of its synchronous steps. If a request has steps of 200 ms and 1,200 ms, the user waits 1,400 ms. From lesson 54, every waiting request holds a worker, and requests in progress = requests per second x seconds each takes. So slow steps also use up your capacity.

The queue

A queue is a line of messages that wait for programs to handle them. A message is a small piece of data that describes one job, for example "send the SMS for order 42". These words are used:

• The producer adds messages to the queue. In our example, it is the checkout code.
• A queue worker (also called a consumer) takes a message and does the job.
• The backlog is the number of messages that are waiting.

The producer adds a message in a few milliseconds and does not wait for the job. You can run many queue workers. Each message goes to one of them.

The queue does not throw a message away when a worker takes it. The worker finishes the job and tells the queue "done". This reply is an acknowledgement (ack). Only then does the queue remove the message. If the worker crashes, no ack comes. The queue then gives the message to another worker, after a time limit or when it sees the connection close. (Amazon SQS calls this limit the visibility timeout. Its default is 30 seconds.) So no job is lost.

But one job can run twice. A worker may finish the job and crash just before the ack. Because of this, a job must be safe to repeat (idempotent, lesson 9). When a job fails, the worker follows the retry rules of lesson 54.

With several workers, jobs can finish in a different order than they arrived. Do not depend on the order. In this lesson we also assume that adding a message to the queue always works.

Queue and pub/sub

A queue shares work. Each message goes to one worker. Use it when a job must be done once by someone, such as "send this SMS".

Publish and subscribe (pub/sub) shares news. A sender publishes a message to a named channel, called a topic. Every program that has subscribed to the topic gets its own copy. It works like a notice in a WhatsApp group. Everyone in the group sees it, and the sender does not know who reads it. Use it when one thing happened and several parts must react. For example, "order placed" reaches the SMS part, the email part and the loyalty part.

What must stay in the request

Move a step out of the request only when all of these are true:

1. The user does not need the result in the response.
2. The next step does not need the work to be finished.
3. A late result does no harm. It is fine if it comes seconds or minutes afterwards.
4. The work is safe to retry and safe to repeat.

Keep a step in the request in any of these cases:

• The user needs its result, such as an order number.
• The next step depends on it. The payment must be accepted before you confirm the order.
• Its failure must stop the request, such as a wrong card.

A step that makes a promise to the user stays. When the screen says "Order placed", the order must be saved.

The response can say honestly that work is still going on. The status 202 Accepted means "I received your request, and the work is not finished" (RFC 9110). Give the user a job number, so the app can ask for the status afterwards.

Why a queue helps

1. A faster response. The user waits only for the steps that stay.
2. Peaks are spread out. When work arrives faster than workers can do it, messages wait in the queue.
3. A broken dependency does not break checkout. If the SMS provider is down, the messages wait. The order still works.
4. Separate scaling. You add queue workers without adding web servers.

The arithmetic for a queue is simple:

• work rate = number of workers / seconds of work per job
• backlog growth per second = arrival rate - work rate
• wait for the last message = backlog / work rate
• time to empty the backlog = backlog / (work rate - arrival rate)

A food app at 8 pm. When a customer pays, the checkout does five steps.

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

• Save the order: 200 ms. Send an SMS: 1,200 ms. Send an email: 800 ms. Add loyalty points: 250 ms. Tell the restaurant: 250 ms.
• Peak: 100 orders per second for 10 minutes (600 seconds). Normal: 20 orders per second.
• The API server has 200 workers (lesson 54).
• Adding a message to a queue takes 5 ms.

Step 1: all synchronous. The request takes 200 + 1,200 + 800 + 250 + 250 = 2,700 ms. Requests in progress = 100 x 2.7 = 270. The server has only 200 workers, so it needs 270 / 200 = 135% of its capacity. It cannot handle the load. This answers the predict box. Orders wait or fail, and a user who succeeds waits 2.7 seconds.

Step 2: decide what stays. Apply the four tests. "Order placed" is a promise, so the save stays. The SMS, the email and the points can wait. The restaurant message can also wait, but a late one is costly. So we give it a queue of its own.

Step 3: the new request. The request saves the order and adds 4 messages. That takes 200 + 4 x 5 = 220 ms. Requests in progress = 100 x 0.22 = 22. That is 22 / 200 = 11% of capacity. The user waits 220 ms, not 2,700 ms.

Step 4: the restaurant queue. The job takes 0.25 s. We run 30 queue workers. Work rate = 30 / 0.25 = 120 orders per second. That is above the peak of 100, so there is no backlog.

Step 5: the slow queue. Each order puts 3 messages here: the SMS, the email and the points. Together they need 1.2 + 0.8 + 0.25 = 2.25 s of worker time. Assume 90 queue workers. Work rate = 90 / 2.25 = 40 orders per second.

• Backlog growth = 100 - 40 = 60 orders per second. After 600 seconds: 60 x 600 = 36,000 orders.
• The last order waits 36,000 / 40 = 900 seconds, which is 15 minutes, for its SMS.
• After the peak, the load is 20 per second. The queue empties in 36,000 / (40 - 20) = 1,800 seconds, which is 30 minutes.

Step 6: more workers. With 180 workers, work rate = 180 / 2.25 = 80 per second. Backlog after the peak = (100 - 80) x 600 = 12,000. The last order waits 12,000 / 80 = 150 seconds. The queue empties in 12,000 / (80 - 20) = 200 seconds. Extra workers help only while the SMS provider can take the extra calls. If the provider is the limit, more workers only move the wait.

Nobody lost an order. The cost is delay: at the peak, the SMS can be minutes late. For this reason, watch the age of the oldest message, and not only the backlog. A short backlog with an old message means that the queue is stuck.

• A queue solves slow steps in the request, peaks, and a dependency that is down. It costs delay (15 minutes in our example), repeated jobs, and one more part to watch. I would use a queue for work that can wait, and keep the promise in the request.
• Separate queues solve the problem that urgent jobs wait behind slow ones. They cost more parts to run. I would split a queue when one kind of job must never wait.
• A queue or pub/sub: a queue fits "one worker does this job". Pub/sub fits "several parts react to one event". I would change to pub/sub when a new reader should not need a change in the checkout code.
• More workers solve a growing backlog. They cost money and more load on the dependency. I would add workers only after I check that the dependency can take the load.

"Put every step in the queue, so the API is as fast as possible." The save of the order is a promise. If you queue it, the screen says "Order placed" and the order may be lost or fail afterwards. Queue only work that can wait.

"A queue makes the system faster." It makes the response faster. The total work is the same, and it finishes afterwards. In our example the SMS arrives up to 15 minutes late.

"A queue runs each job once, in order." A crash before the ack makes the queue send the job again. So a job can run twice. With several workers, jobs can finish out of order. Design for both.

1. Give the four tests for moving a step out of the request. What is the difference between a queue and pub/sub?
2. A queue gets 50 messages per second. It has 10 workers, and each message takes 0.5 s. What is the backlog after 5 minutes, and how long does the last message wait?
3. A ticket app has a confirmed payment. The app must mark the seat as sold (50 ms), make a PDF ticket (3 s) and email it (1 s). What stays in the request, and what does the user see?