Message Queues

The problem: slow work while the user waits

Say your photo app does everything inside the upload request: it saves the photo, makes 5 sizes of it, emails the user's followers, and only then answers. That takes about 4 seconds of spinner, though all the user needs to know is that the photo arrived.

Bursts make it worse. When a photo contest opens and 1,000 uploads a second arrive, each one holds an upload server for 4 seconds: about 4,000 uploads in progress at once. More upload servers let more uploads run side by side, but each user still waits 4 seconds.

How a message queue works

A message queue lets the request leave the slow part for later. The upload service, the producer, saves the original photo to storage, adds a small job to the queue ("make the sizes of photo p7, email the followers") and answers at once. Workers, the consumers, pull jobs off the queue whenever they're free. The job holds only the photo's id: the photo itself is in storage.

The rule that makes it safe is the ack (acknowledgment). When a worker takes a job, the queue hides it from the other workers but doesn't delete it. Only when the worker says the job is done does the queue delete it. If no ack comes within a timeout (often called a visibility timeout; say 30 seconds), the job becomes visible again for the next worker that asks.

Here is a run with five jobs and two workers. J1 takes 3 seconds, J2 and J3 4 each, J4 and J5 3 each, and the queue hands out the job that has waited longest. "W1" marks a job Worker 1 has, hidden from the other worker:

time   event                                         queue after
0 s    Worker 1 takes J1, Worker 2 takes J2          J1 (W1) J2 (W2) J3 J4 J5
3 s    Worker 1 acks J1, takes J3                    J2 (W2) J3 (W1) J4 J5
4 s    Worker 2 finishes J2, crashes before its ack  J2 (W2) J3 (W1) J4 J5
7 s    Worker 1 acks J3, takes J4                    J2 (W2) J4 (W1) J5
10 s   Worker 1 acks J4, takes J5                    J2 (W2) J5 (W1)
13 s   Worker 1 acks J5                              J2 (W2)
30 s   J2 times out, Worker 1 takes it               J2 (W1)
34 s   Worker 1 acks J2                              (empty)

The crash didn't lose J2: the queue kept it until its timeout ran out. But J2 ran twice, so every follower got the same email twice. And J3 to J5 finished before J2: with several workers, jobs don't finish in the order they arrived.

Bursts: the queue grows, then drains

Say the contest brings 1,000 uploads a second for 10 seconds, and your workers, all together, finish about 500 jobs a second. The upload service still answers every user at once; the jobs wait:

after   added    done    waiting
1 s     1,000    500     500
2 s     2,000    1,000   1,000
3 s     3,000    1,500   1,500
10 s    10,000   5,000   5,000

The queue grows by 500 a second, to 5,000 when the burst ends. When uploads fall back to, say, 250 a second, the workers gain 250 a second on it, and it's empty 20 seconds later. Nothing was lost and no server was overloaded: the last photo of the burst just gets its sizes about 10 seconds after it was uploaded. If the queue keeps growing, add workers.

At-least-once delivery

The queue sees acks, never the work. When no ack comes, it can't tell a worker that crashed before the work from one that crashed after it, so it has two choices:

• At-least-once: hand the job out again after the timeout. Every job gets done, but some get done twice. This is the usual choice.
• At-most-once: ack the job as soon as a worker takes it. Nothing runs twice, but a crash loses the job.

For work with effects outside the queue, like an email, the queue alone can't promise exactly once. You get the same result by making each job idempotent: safe to run twice.

Making jobs idempotent

• Safe as written: saving the small size of photo p7 as p7-small.jpg (the same bytes to the same name), setting order 81's status to "shipped", saving a like under the key (user 7, post 42).
• Not safe as written: adding 10 points to a score (twice adds 20), charging a card $20 (twice is $40), sending a welcome email.

For the others, keep a record of done job ids. The worker checks it first and only acks a job that's already there; right after the work, it adds the job's id. A crash between the work and the record can still repeat the work, so write the record as soon as the work is done; when the work is a database write, write both in one transaction. Or turn an add into a set: store the points under the job's id, so a second run saves the same row. Payments go further: payment services commonly take an idempotency key and won't charge one key twice.

Retries, backoff and dead-letter queues

Many failures pass: storage is busy for a moment, the email service is slow. But a job that can never succeed, such as a broken image file, would come back forever and take a worker every time. The usual policy:

1. Retry with growing waits (backing off): say 1 second, then 2, then 4. Storage that is busy for 2 seconds works on the third try.
2. After a few tries, say 4, move the job to a dead-letter queue that the normal workers don't read.
3. Alert someone, who fixes the cause and sends the job back if it can now succeed.

So the broken image is tried at 0, 1, 3 and 7 seconds, then set aside, and the other jobs never wait on it.

Choices and trade-offs

• Order: a plain queue with several workers doesn't keep order. When order matters per user or per account, use a log split by key, which keeps each key's messages in order (Pub/Sub and Streams, the next lesson).
• The timeout: too short, and a slow job is handed out again while it's still running; too long, and a crashed worker's job sits idle.
• Products: RabbitMQ and Amazon SQS are common examples of message queues.

Where it shows up in design interviews

Anything slow or bursty that the user needn't wait for goes through a queue: video formats, thumbnails, emails, reports, pushing a new post into followers' feeds. Draw the producer, the queue and a pool of workers, then say how retries are made safe: delivery is at-least-once, so jobs are idempotent (a done record by job id, or keys), and failures retry with backoff, then go to a dead-letter queue. What the user needs before they can go on, like checking a password, stays in the request.

Common interview questions

Why put a queue between two services?

The first one can answer without waiting for the slow work, and bursts wait in the queue instead of overloading the workers. A job also survives a worker's crash, because the queue deletes it only after the ack.

What does at-least-once delivery mean for your code?

Any job can run twice, when a worker crashes between doing the work and acking it. So jobs must be idempotent: check a record of done job ids first, or make the work set a value rather than add to one.

What happens to a message that keeps failing?

It's retried a few times with growing waits, then moved to a dead-letter queue for someone to look at. Without a limit it would come back forever.

Does a queue keep messages in order?

It hands out the oldest job first, but with several workers jobs finish out of order, and a retried job comes back late. When order matters, split the messages by key so each key's messages go to one consumer.

Summary

• A message queue lets a request add a job and answer; workers do the slow part later.
• It absorbs bursts: 1,000 jobs a second in and 500 out grow the queue to 5,000, which then drains.
• A job is deleted only after its worker's ack, so delivery is at-least-once: make every job idempotent.
• Retry failures with backoff, then send them to a dead-letter queue.