Pub Sub System

Publish-Subscribe Message Broker

Design an in-process publish-subscribe broker: topics, named subscriptions that each get every message, worker groups that share one subscription, acknowledgements with redelivery, and a dead-letter list.

Overview

A publish-subscribe broker sits between the code that produces events and the code that reacts to them. A publisher sends a message to a named topic and does not know who reads it. Each reader creates a subscription on the topic, and the broker gives every subscription its own copy of every message. The publisher and the readers never refer to each other, so a new reader is added without touching the publisher.

Interviewers use this problem to test four ideas. Fan-out and sharing: every subscription gets every message, but the workers behind one subscription split its messages between them. Delivery guarantees: what happens when a worker takes a message and crashes before finishing it. Isolation: a slow reader must not slow down the publisher or the other readers. Thread safety: many publishers and workers call the broker at once.

A strong answer separates the topic (where messages go in) from the subscription (where they wait to be read), makes delivery pull-based so the broker never runs reader code while holding a lock, and states the guarantee it gives (at least once) together with what the reader must do about duplicates.

Scoping the problem

Does every reader get every message, or do readers share the work? — Decides fan-out versus a work queue; most systems support both — Both: each subscription gets every message; workers on one subscription share them
Push (broker calls the reader) or pull (reader asks)? — Push runs reader code inside the broker; pull lets each reader go at its own pace — Pull; push can be a thread that polls and calls a callback
What guarantee: at most once, at least once, exactly once? — Decides whether acknowledgements and redelivery exist — At least once, with idempotent readers
Is order required? — A total order is cheap in one process; across partitions it is per partition only — Messages reach each subscription in publish order; redelivery can reorder
What happens to a message that keeps failing? — Without a limit it is retried forever and blocks others — Move it to a dead-letter list after N deliveries
Filters on a subscription? — Saves readers from discarding what they do not want — Yes, a predicate on the message headers
Durable across restarts? — Adds a log on disk and offsets — Follow-up, not the core

Core entities

There is no Publisher or Subscriber class. A publisher is any code that calls publish; a worker is any code that calls poll and ack with its own name. Adding classes for them would add nothing the methods do not already say.

Fan-out and groups

The two ways a message can be shared are the core of the problem, and one rule gives both: a message is copied once per subscription, and within a subscription it is handed to one worker at a time.

Two subscriptions, one worker each — Both workers see every message — Different jobs: billing and email both react to an order
One subscription, three workers — Each message goes to one of the three — The same job, spread across workers
Two subscriptions, one with a filter — The filtered one sees only matching messages — Email only cares about new orders

Kafka calls the second row a consumer group: each record is delivered to one consumer instance within each subscribing group. Google Cloud Pub/Sub uses the same shape: a topic has many subscriptions, and the subscribers on one subscription share its messages.

A message's life inside a subscription

The trace below is the demo in the implementation. The billing subscription has a 30 second timeout and allows 2 deliveries; the email subscription only accepts messages whose type is created.

1 — publish m1 (created), m2 (created), m3 (paid) — billing has 3, email has 2 — The filter drops m3 for email
2 — w1 polls, w2 polls billing — w1 gets m1, w2 gets m2 — One worker per message in a group
3 — ack m1 twice — true, then false — The second ack finds nothing in flight
4 — expire(now = 30) — m2 goes back before m3 — Late messages return to the front
5 — w1 polls 2; w2 acks m2 late — m2, m3; the late ack is refused — Second delivery of m2, which now belongs to w1
6 — expire(now = 60) — m2 dead-lettered — That was delivery 2 of 2
7 — email has not polled — backlog 2, billing unaffected — Each subscription has its own queue

Delivery guarantees

The guarantee is decided by when the broker forgets a message.

At most once — when it is handed out — a crash loses it — nothing; losing some is acceptable
At least once (the code) — when it is acknowledged — a crash after the work but before the ack gives a duplicate — be idempotent: skip ids it has already processed
Exactly once in effect — when it is acknowledged — none visible — record the message id and its result in one transaction

Exactly once is not a broker setting that removes the duplicate; it is at least once plus a reader that makes the duplicate harmless. Say that clearly, since it is what the interviewer is checking.

Thread safety

Two locks, one order. The broker lock guards the topic table, the id counter and the fan-out loop, so two concurrent publishes get ids and reach every subscription in the same order. Each subscription's lock guards its queue and in-flight table, so poll, ack and expire are atomic and two workers can never take the same message. publish takes the broker lock and then each subscription lock; nothing takes them the other way round, so there is no deadlock. offer only appends to a deque, so a publish never waits for a reader; the only reader code that runs under the broker lock is the subscription's filter, which must be a quick check.

The demo runs 4 publisher threads of 250 messages each against 3 worker threads in one group, and asserts that all 1,000 messages are acked exactly once and that a second subscription saw them in id order.

What you will be able to do

Separate topics from subscriptions and explain fan-out across subscriptions and sharing within one.
Draw a message's states in a subscription and implement ack, timeout, redelivery and dead-lettering.
State which guarantee your design gives and what the reader must do to make duplicates harmless.
Explain why pull delivery keeps a slow reader from blocking others, and where each lock lives.

Functional requirements

create_topic(name) and delete_topic(name)
subscribe(topic, name, filter, ack_timeout, max_deliveries) returns a named subscription; subscribing twice with the same name returns the same one
publish(topic, payload, headers) gives the message an id and copies it to every subscription whose filter accepts it
poll(member, now, max_messages) hands ready messages to one worker; workers on one subscription never get the same message at once
ack(message_id, member) finishes a message only for the worker that holds it; expire(now) returns late messages to the front of the queue, or to the dead letters after max_deliveries
Publishing to an unknown topic raises UnknownTopic

Non-functional requirements

Decoupling: publishers never know which subscriptions exist
Isolation: publish only appends to queues; a slow or stopped reader never blocks the publisher or other subscriptions
Order: every subscription receives messages in publish order; only redelivery can reorder
Thread safety: one broker lock and one lock per subscription, always taken in that order
At-least-once delivery with a bounded number of retries; time is injected so tests are exact

Interview questions

Your broker is at least once. How does a reader avoid charging a customer twice?
How would you keep order per customer while still using several workers?
Why pull instead of push? What does a slow subscriber do to your broker?
How would you make messages survive a restart and let a new subscription read old messages?
What should happen to a message that fails every time?