Design a Pub-Sub / Message Broker (In-Process)
"Design a pub-sub system" sounds like a high-level design question about Kafka clusters. In an LLD round it means something smaller and sharper. You build the broker inside one process: a class that accepts messages on named topics and hands them to subscribers, with the delivery rules that make real brokers useful. Those rules are ordering, retries, a dead-letter queue, and protection against a subscriber that can't keep up.
The problem is popular because it packs a lot of concurrency into very little domain. There are only five or six nouns. Almost every interesting decision is about who runs which code on which thread, while holding which lock. A candidate who can draw the classes but can't say what happens when a handler throws, or when one subscriber is ten times slower than the others, hasn't solved it.
This page builds the broker step by step. The final code is about 250 lines per language and runs as-is, with checks for every rule.
1. Clarifying questions and requirements
Start by pinning down the scope. These are the questions worth asking, with the answers we'll design for.
| Question | Answer we assume | Why it matters |
|---|---|---|
| In-process or networked? | In-process, one JVM / Python process / Node process | No serialisation, no sockets. The interesting part is threading. |
| Does each subscriber see every message (fan-out) or do subscribers compete? | Fan-out per subscription. Competing consumers come as an extension. | Decides whether cursors live per subscription or per group. |
| Do we need ordering? | Per key. Messages with the same key reach a subscriber in publish order. | Forces partitions and one in-flight message per partition per subscriber. |
| Push or pull? | Both. Push calls a handler on a worker thread. Pull lets the consumer poll and commit. | Two delivery paths over one storage model. |
| What if a handler fails? | Retry with exponential backoff, then move the message to a dead-letter topic. | Without a DLQ, one poison message blocks its partition forever. |
| What if a subscriber is slow? | Per subscription policy: block the publisher, reject the publish, or drop the oldest message for that subscriber. | Unbounded buffering is an out-of-memory crash waiting to happen. |
| Durability? | None. Memory only, lost on restart. | Keeps us out of HLD. Say it out loud. |
| Late subscribers? | Start at the end by default. Optionally start from the oldest retained message. | Decides retention. |
Functional requirements
- Create a topic with a fixed number of partitions.
- Publish a message (payload, optional key, optional headers) to a topic. Messages with the same key go to the same partition.
- Subscribe in push mode with a handler, or in pull mode with
pollandcommit. - Every subscription receives every message published after it subscribed (fan-out).
- Within a partition, a subscription receives messages in order, and a push handler sees at most one message from that partition at a time.
- A failing push handler is retried up to
maxAttemptstimes with exponential backoff. Then the message goes to<topic>.dlqwith headers describing the failure, and the partition moves on. - A pull message that isn't committed is delivered again on the next poll (at-least-once).
- Each subscription has a
maxLag. When a publish would push it past that, its overflow policy applies:BLOCK(with a timeout),REJECT, orDROP_OLDEST. - Unsubscribe at any time. Shut the broker down gracefully: refuse new publishes, let push lanes drain, stop the workers.
Non-functional requirements
- Thread-safe. Many publisher threads and many handler threads at once.
- Handlers never run under the broker lock. A slow handler must not stall publishers or other subscribers.
- Bounded memory. The log keeps only what the slowest subscription still needs.
- Testable. Every rule above has a check that runs in under a second.
Out of scope
Persistence, networking, exactly-once delivery, transactions across topics, schema registries and authentication. If the interviewer wants any of these, it's an HLD conversation, and Message Queues covers it.
2. Core entities and relationships
| Entity | Responsibility | Notes |
|---|---|---|
Broker | The facade. Owns topics, subscriptions, the lock and the worker pool. | The only class callers touch. |
Topic | A name plus an ordered list of partitions. Maps a key to a partition. | Hashing must be stable, so not Python's randomised hash(). |
Partition | An append-only log of messages with a moving base offset. | Trimmed from the front when every cursor has moved past. |
Message | Immutable: topic, partition, offset, key, payload, headers. | Immutability lets handlers read it without locks. |
Subscription | A name, a topic, a handler (or none for pull), options, and one cursor per partition. | Push subscriptions also have a "lane busy" flag per partition. |
SubscriptionOptions | maxLag, overflow, maxAttempts, backoff. | A value object. |
Overflow | BLOCK, REJECT, DROP_OLDEST. | An enum, not a class hierarchy. See the pattern section. |
The key modelling decision is this. Messages live once, in the partition log. Subscriptions are just cursors into it. The naive design gives every subscriber its own queue and copies each message into every queue. That works, but it makes "how far behind is this subscriber?" a queue-size question per copy. It also makes "start from the beginning" impossible, and pull mode becomes a separate code path. A log with cursors gives you lag (end - cursor), replay (move the cursor) and retention (trim below the minimum cursor) for free. This is the core idea behind Kafka, scaled down to a list and an integer.
Relationships:
- A
Brokerhas manyTopics. ATopichas one or morePartitions. APartitionholds manyMessages. - A
Topichas manySubscriptions. ASubscriptionbelongs to exactly one topic and has exactly one cursor per partition of that topic. - Every topic
tgets a companiont.dlqwith one partition that is never trimmed.
The invariants to protect:
- For every subscription and partition,
partition.base <= cursor <= partition.end. - A push subscription has at most one lane running per partition. That's what gives ordering.
partition.basenever exceeds the minimum cursor over that topic's subscriptions, so no one loses a message to trimming.
3. Class diagram
classDiagram
class Broker {
-topics: map of name to Topic
-subs: map of topic name to list of Subscription
-pool: worker pool
-lock: mutex plus condition
-closed: boolean
+createTopic(name, partitions) Topic
+subscribe(topic, name, handler, opts, fromBeginning) Subscription
+unsubscribe(sub)
+publish(topic, key, payload, headers, timeout) Message
+poll(sub, max, partitions) list of Message
+commit(sub, message)
+shutdown(timeout) boolean
-makeRoom(topic, partition, deadline)
-drain(sub, partition)
-deliver(sub, message)
-deadLetter(sub, message, error, attempts)
}
class Topic {
+name: String
+partitions: list of Partition
+retainAll: boolean
+partitionFor(key) int
}
class Partition {
+base: long
+log: list of Message
+end() long
+read(offset) Message
+trim(upto)
}
class Message {
<<immutable>>
+topic: String
+partition: int
+offset: long
+key: String
+payload: Object
+headers: map
}
class Subscription {
+name: String
+offsets: long array
+busy: boolean array
+active: boolean
+dropped: int
+deadLettered: int
+isPush() boolean
+lag(partition) long
}
class SubscriptionOptions {
+maxLag: int
+overflow: Overflow
+maxAttempts: int
+backoff: duration
}
class Overflow {
<<enumeration>>
BLOCK
REJECT
DROP_OLDEST
}
class Handler {
<<interface>>
+handle(message)
}
Broker "1" *-- "*" Topic
Broker "1" o-- "*" Subscription
Topic "1" *-- "1..*" Partition
Partition "1" o-- "*" Message
Subscription --> Topic
Subscription --> SubscriptionOptions
Subscription ..> Handler : push mode only
SubscriptionOptions --> Overflow
Notice what isn't here. There's no Publisher class, because a publisher is any caller of publish. There's no Subscriber interface with ten methods either. A push subscriber is a single function, Message -> void, which is the smallest contract that works. There's also no Queue per subscriber, for the reason given above.
4. Key flows
Publish with push delivery
sequenceDiagram
actor P as Publisher thread
participant B as Broker
participant T as Topic
participant L as Partition log
participant W as Worker pool
actor H as Handler
P->>B: publish("orders", key, payload)
B->>B: acquire lock
B->>T: partitionFor(key)
T-->>B: partition 2
B->>B: makeRoom(topic, 2) checks every subscription lag
B->>L: append message at offset 41
B->>W: submit drain(sub, 2) if that lane is idle
B->>B: notifyAll, release lock
B-->>P: Message(offset 41)
W->>B: lock, read message at sub cursor, unlock
W->>H: handle(message) with no lock held
H-->>W: returns normally
W->>B: lock, cursor becomes 42, trim log, notifyAll, unlock
W->>B: loop until lag is 0, then mark lane idle
Two things are worth saying while you draw it. The publisher returns as soon as the message is in the log. It doesn't wait for any handler. And the handler runs between two short critical sections, never inside one.
Retry and dead letter
sequenceDiagram
participant W as Lane worker
actor H as Handler
participant B as Broker
participant D as orders.dlq
W->>H: attempt 1
H-->>W: throws "gateway timeout"
W->>W: sleep backoff
W->>H: attempt 2
H-->>W: throws "gateway timeout"
W->>W: sleep 2 x backoff
W->>H: attempt 3
H-->>W: throws "gateway timeout"
Note over W: attempts exhausted
W->>B: deadLetter(sub, message, error, 3)
B->>D: append copy with dlq.error, dlq.attempts, dlq.source headers
W->>B: advance cursor past the message
Note over W,B: The partition is unblocked and the next message flows
A slow subscriber with the BLOCK policy
sequenceDiagram
actor P as Publisher
participant B as Broker
actor C as Slow pull consumer
P->>B: publish(m1)
B-->>P: ok, lag is now 1 of maxLag 1
P->>B: publish(m2, timeout 2s)
B->>B: lag at maxLag, wait on condition
C->>B: poll()
B-->>C: [m1]
C->>B: commit(m1)
B->>B: cursor moves, trim, notifyAll
B->>B: publisher wakes, lag is 0, append m2
B-->>P: ok
Message lifecycle, per subscription
A message has one copy in the log, but its state is per subscription. The same message can be acked by one subscription and dead-lettered by another.
stateDiagram-v2
[*] --> Pending: appended to partition
Pending --> InFlight: lane reads it, or poll returns it
Pending --> Dropped: DROP_OLDEST overflow
InFlight --> Acked: handler returns, or commit
InFlight --> Retrying: handler throws, attempts left
Retrying --> InFlight: after backoff
InFlight --> DeadLettered: handler throws, no attempts left
InFlight --> Pending: pull consumer polls again without committing
Acked --> [*]
DeadLettered --> [*]
Dropped --> [*]
Nobody stores this state in a field. It's implied by where the cursor is and whether a lane holds the message. That's a deliberate choice, explained next.
5. Patterns, why, and the alternatives rejected
Observer vs pub-sub: the distinction interviewers probe
Candidates often say "pub-sub is just the Observer pattern". It's related, but the differences are the whole point of a broker.
| Observer | Pub-sub broker | |
|---|---|---|
| Who knows whom | The subject holds references to its observers | Publishers and subscribers know only a topic name |
| Coupling in time | Synchronous: notify() calls every observer before it returns | Asynchronous: publish() returns once the message is stored |
| Thread | The observer runs on the subject's thread | Handlers run on broker workers |
| A failing receiver | Its exception propagates into the subject | The broker retries and dead-letters it, and the publisher never knows |
| A slow receiver | Slows the subject down directly | Builds lag, and the overflow policy decides what happens |
| Buffering, replay | None | The log buffers, and cursors allow replay |
| Ordering across receivers | Fixed by registration order | Each subscription progresses independently |
A short way to say it: Observer is a method call with a list. Pub-sub puts a buffer and a policy between the two sides. You can see the difference in a few lines:
"""Observer couples the subject to its observers' speed and failures. A broker does not."""
from broker import Broker, SubscriptionOptions
class Thermostat:
def __init__(self) -> None:
self._observers = []
self.temp = 20
def attach(self, fn) -> None:
self._observers.append(fn)
def set(self, temp: int) -> None:
self.temp = temp
for fn in self._observers: # runs on the caller's thread, in order
fn(temp)
def broken(_):
raise RuntimeError("display offline")
if __name__ == "__main__":
thermostat, log = Thermostat(), []
thermostat.attach(log.append)
thermostat.attach(broken)
try:
thermostat.set(25)
raise AssertionError("observer failure should reach the subject")
except RuntimeError:
pass # the subject has to deal with a display it shouldn't know about
broker = Broker()
broker.create_topic("temps")
got = []
broker.subscribe("temps", "display", broken, SubscriptionOptions(max_attempts=1))
broker.subscribe("temps", "log", lambda m: got.append(m.payload))
broker.publish("temps", 25) # returns at once, the failure is the broker's problem
assert broker.shutdown(timeout_s=2)
assert got == [25] and log == [25]
print("observer vs pub-sub checks passed")
Use Observer when the receivers are part of the same component, cheap, and must see the change before the call returns: UI bindings, domain events inside one aggregate. Use a broker when the receivers are other components that may be slow, fail, or come and go.
Patterns we used
| Pattern | Where | Why | Alternative rejected |
|---|---|---|---|
| Facade | Broker | One entry point protects the invariants. Callers can't move cursors directly. | Exposing Topic and Partition, which would spread the locking rules across callers |
| Strategy (as a function) | Handler | The only thing that varies per push subscriber is "what to do with a message" | A Subscriber base class with lifecycle hooks, which is inheritance for one method |
| Producer-consumer with a worker pool | Lanes submitted to an executor | Handlers run off the publisher's thread, with bounded threads | One thread per subscription, which means thousands of threads for thousands of subscribers. See concurrency patterns in LLD. |
| Log plus cursor | Partition and Subscription.offsets | Lag, replay, retention and pull mode from one structure | A copied queue per subscriber |
| Enum for policy | Overflow | Three fixed behaviours, each two or three lines, all inside makeRoom | A BackPressurePolicy interface. It would need access to cursors and the lock, which leaks broker internals. If policies multiply, revisit. |
| Decorator | Extensions: filters, TTL | Adding behaviour around a handler without touching the broker | Flags on subscribe() for every feature |
Patterns we deliberately did not use
- The State pattern for message state. The lifecycle diagram has six states, which looks like State pattern territory. But a message's state is per subscription, and storing a state object per (message, subscription) pair costs memory proportional to messages times subscribers. A cursor and a busy flag encode the same information in two fields per partition. Choose the representation that makes the invariant cheap to enforce.
- Singleton broker. Tests need fresh brokers, and two brokers in one process are perfectly reasonable. Pass the broker in.
- The Mediator pattern. A broker is a kind of mediator between publishers and subscribers. Calling it that adds nothing in an interview unless you're asked.
6. The code
All three versions implement the same design and finish with a main that checks every rule: per-partition ordering under concurrent publishers, retry, dead letter, all three overflow policies, pull redelivery and graceful shutdown.
- Java 24:
javac PubSub.java && java PubSubDemo. - Python 3.12: save as
broker.py, thenpython broker.py. The tests and extensions below import it. - TypeScript:
npx tsx pubsub.ts. It typechecks undertsc --strict --target es2022 --lib es2022,dom.
// PubSub.java -> javac PubSub.java && java PubSubDemo
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.BooleanSupplier;
import java.util.function.Consumer;
enum Overflow { BLOCK, REJECT, DROP_OLDEST }
class BrokerException extends RuntimeException {
BrokerException(String message) { super(message); }
}
class BackPressureException extends BrokerException {
BackPressureException(String message) { super(message); }
}
record Message(String topic, int partition, long offset, String key, Object payload, Map<String, String> headers) {}
/** An append-only log. Offsets below base have been trimmed. */
final class Partition {
long base = 0;
final ArrayList<Message> log = new ArrayList<>();
long end() { return base + log.size(); }
Message read(long offset) { return log.get((int) (offset - base)); }
void trim(long upto) {
if (upto > base) {
log.subList(0, (int) (upto - base)).clear(); // Simplification: O(n) shift, a ring buffer at high volume
base = upto;
}
}
}
final class Topic {
final String name;
final List<Partition> partitions = new ArrayList<>();
final boolean retainAll; // dead-letter topics keep everything
private int next = 0;
Topic(String name, int count, boolean retainAll) {
this.name = name;
this.retainAll = retainAll;
for (int i = 0; i < count; i++) partitions.add(new Partition());
}
int partitionFor(String key) {
if (key == null) { next = (next + 1) % partitions.size(); return next; } // no key, no ordering promise
return Math.floorMod(key.hashCode(), partitions.size()); // String.hashCode is stable
}
}
record SubscriptionOptions(int maxLag, Overflow overflow, int maxAttempts, long backoffMillis) {
SubscriptionOptions {
if (maxLag < 1 || maxAttempts < 1) throw new BrokerException("maxLag and maxAttempts must be at least 1");
}
static SubscriptionOptions defaults() { return new SubscriptionOptions(1000, Overflow.BLOCK, 3, 10); }
SubscriptionOptions withLag(int lag, Overflow policy) { return new SubscriptionOptions(lag, policy, maxAttempts, backoffMillis); }
SubscriptionOptions withRetries(int attempts, long backoff) { return new SubscriptionOptions(maxLag, overflow, attempts, backoff); }
}
final class Subscription {
final String name;
final Topic topic;
final Consumer<Message> handler; // null means pull mode
final SubscriptionOptions opts;
final long[] offsets; // next offset to deliver, per partition
final boolean[] busy; // push lane running, per partition
boolean active = true;
volatile int dropped, deadLettered; // written under the broker lock, read by anyone
Subscription(String name, Topic topic, Consumer<Message> handler, SubscriptionOptions opts, boolean fromBeginning) {
this.name = name; this.topic = topic; this.handler = handler; this.opts = opts;
int n = topic.partitions.size();
offsets = new long[n];
busy = new boolean[n];
for (int p = 0; p < n; p++) {
Partition part = topic.partitions.get(p);
offsets[p] = fromBeginning ? part.base : part.end();
}
}
boolean isPush() { return handler != null; }
long lag(int p) { return topic.partitions.get(p).end() - offsets[p]; }
}
final class Broker {
private final Object lock = new Object(); // guards everything below, and is the condition for waiters
private final Map<String, Topic> topics = new HashMap<>();
private final Map<String, List<Subscription>> subs = new HashMap<>();
private final ExecutorService pool;
private boolean closed;
Broker(int workers) { pool = Executors.newFixedThreadPool(workers); }
// ---- topics and subscriptions ----
Topic createTopic(String name, int partitions) {
synchronized (lock) {
Topic topic = addTopic(name, partitions, false);
addTopic(name + ".dlq", 1, true);
return topic;
}
}
Subscription subscribe(String topic, String name, Consumer<Message> handler, SubscriptionOptions opts, boolean fromBeginning) {
synchronized (lock) {
Topic t = topic(topic);
for (Subscription s : subs.get(topic))
if (s.name.equals(name)) throw new BrokerException("subscription " + name + " already exists on " + topic);
Subscription sub = new Subscription(name, t, handler, opts, fromBeginning);
subs.get(topic).add(sub);
for (int p = 0; p < t.partitions.size(); p++) schedule(sub, p); // from-beginning push starts on the backlog
return sub;
}
}
Subscription subscribe(String topic, String name, Consumer<Message> handler, SubscriptionOptions opts) {
return subscribe(topic, name, handler, opts, false);
}
void unsubscribe(Subscription sub) {
synchronized (lock) {
sub.active = false;
subs.get(sub.topic.name).remove(sub);
trim(sub.topic);
lock.notifyAll(); // a publisher may have been blocked on this subscriber
}
}
// ---- publishing ----
Message publish(String topic, String key, Object payload, Map<String, String> headers, long timeoutMillis) {
long deadline = System.nanoTime() + timeoutMillis * 1_000_000;
synchronized (lock) {
Topic t = topic(topic);
int p = t.partitionFor(key);
makeRoom(t, p, deadline);
return append(t, p, key, payload, headers);
}
}
Message publish(String topic, String key, Object payload) { return publish(topic, key, payload, Map.of(), 1000); }
private void makeRoom(Topic t, int p, long deadline) {
while (true) {
if (closed) throw new BrokerException("broker is shut down");
List<Subscription> full = new ArrayList<>();
for (Subscription s : subs.get(t.name)) if (s.lag(p) >= s.opts.maxLag()) full.add(s);
if (full.isEmpty()) return;
for (Subscription s : full) // validate before mutating: a reject must not drop anything
if (s.opts.overflow() == Overflow.REJECT)
throw new BackPressureException(s.name + " is " + s.lag(p) + " messages behind on " + t.name + "/" + p);
boolean mustWait = false;
for (Subscription s : full) {
if (s.opts.overflow() == Overflow.DROP_OLDEST) { s.offsets[p]++; s.dropped++; }
else mustWait = true;
}
trim(t);
if (!mustWait) return;
long waitMillis = (deadline - System.nanoTime()) / 1_000_000;
if (waitMillis <= 0) throw new BackPressureException("timed out waiting for a slow subscriber on " + t.name + "/" + p);
try { lock.wait(waitMillis); } // releases the lock while waiting
catch (InterruptedException e) { Thread.currentThread().interrupt(); throw new BrokerException("interrupted"); }
}
}
private Message append(Topic t, int p, String key, Object payload, Map<String, String> headers) { // lock held
Partition part = t.partitions.get(p);
Message m = new Message(t.name, p, part.end(), key, payload, Map.copyOf(headers));
part.log.add(m);
for (Subscription s : subs.get(t.name)) schedule(s, p);
lock.notifyAll();
return m;
}
// ---- push delivery ----
private void schedule(Subscription s, int p) { // lock held
if (s.isPush() && s.active && !s.busy[p] && s.lag(p) > 0) {
s.busy[p] = true;
pool.execute(() -> drain(s, p));
}
}
private void drain(Subscription s, int p) {
while (true) {
Message m;
synchronized (lock) {
if (!s.active || s.lag(p) == 0) { s.busy[p] = false; lock.notifyAll(); return; }
m = s.topic.partitions.get(p).read(s.offsets[p]);
}
deliver(s, m); // no lock held: handlers are slow and may publish
synchronized (lock) {
s.offsets[p] = Math.max(s.offsets[p], m.offset() + 1); // DROP_OLDEST may have moved it already
trim(s.topic);
lock.notifyAll();
}
}
}
private void deliver(Subscription s, Message m) {
for (int attempt = 1; ; attempt++) {
try { s.handler.accept(m); return; }
catch (RuntimeException e) { // a handler failure must never kill the lane
if (attempt >= s.opts.maxAttempts()) { deadLetter(s, m, e, attempt); return; }
// Simplification: sleeping holds a worker; schedule the retry instead if lanes far outnumber workers
sleep(s.opts.backoffMillis() << (attempt - 1));
}
}
}
private void deadLetter(Subscription s, Message m, RuntimeException e, int attempts) {
synchronized (lock) {
s.deadLettered++;
Topic dlq = topics.get(m.topic() + ".dlq");
if (dlq == null) return; // a dead-letter topic has no dead-letter topic of its own
Map<String, String> h = new HashMap<>(m.headers());
h.put("dlq.subscription", s.name);
h.put("dlq.error", String.valueOf(e.getMessage()));
h.put("dlq.attempts", String.valueOf(attempts));
h.put("dlq.source", m.topic() + "/" + m.partition() + "/" + m.offset());
append(dlq, 0, m.key(), m.payload(), h);
}
}
// ---- pull delivery ----
List<Message> poll(Subscription s, int max) {
synchronized (lock) {
if (s.isPush()) throw new BrokerException("poll() is for pull subscriptions");
List<Message> out = new ArrayList<>();
for (int p = 0; p < s.offsets.length && out.size() < max; p++) { // Simplification: low partitions first, rotate for fairness
Partition part = s.topic.partitions.get(p);
for (long o = s.offsets[p]; o < part.end() && out.size() < max; o++) out.add(part.read(o));
}
return out; // nothing is committed here, so unacked messages come back next poll
}
}
/** Acks m and everything before it on the same partition. */
void commit(Subscription s, Message m) {
synchronized (lock) {
if (!m.topic().equals(s.topic.name)) throw new BrokerException("message is from another topic");
s.offsets[m.partition()] = Math.max(s.offsets[m.partition()], m.offset() + 1);
trim(s.topic);
lock.notifyAll();
}
}
// ---- shutdown ----
boolean shutdown(long timeoutMillis) throws InterruptedException {
long deadline = System.nanoTime() + timeoutMillis * 1_000_000;
boolean drained;
synchronized (lock) {
closed = true;
lock.notifyAll(); // blocked publishers fail fast
while (!(drained = idle())) {
long left = (deadline - System.nanoTime()) / 1_000_000;
if (left <= 0) break;
lock.wait(left);
}
if (!drained) for (List<Subscription> list : subs.values()) for (Subscription s : list) s.active = false;
}
pool.shutdown();
pool.awaitTermination(timeoutMillis, TimeUnit.MILLISECONDS);
return drained;
}
private boolean idle() {
for (List<Subscription> list : subs.values())
for (Subscription s : list)
if (s.isPush())
for (int p = 0; p < s.offsets.length; p++) if (s.busy[p] || s.lag(p) > 0) return false;
return true;
}
// ---- helpers ----
private Topic topic(String name) {
Topic t = topics.get(name);
if (t == null) throw new BrokerException("unknown topic " + name);
return t;
}
private Topic addTopic(String name, int partitions, boolean retainAll) {
if (topics.containsKey(name)) throw new BrokerException("topic " + name + " already exists");
if (partitions < 1) throw new BrokerException("a topic needs at least one partition");
Topic t = new Topic(name, partitions, retainAll);
topics.put(name, t);
subs.put(name, new ArrayList<>());
return t;
}
private void trim(Topic t) { // lock held: keep what the slowest cursor still needs
if (t.retainAll) return;
for (int p = 0; p < t.partitions.size(); p++) {
Partition part = t.partitions.get(p);
long min = part.end();
for (Subscription s : subs.get(t.name)) min = Math.min(min, s.offsets[p]);
part.trim(min);
}
}
private static void sleep(long millis) {
try { Thread.sleep(millis); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
}
}
class PubSubDemo {
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
System.out.println("ok " + what);
}
static void waitUntil(BooleanSupplier cond, String what) throws InterruptedException {
long deadline = System.currentTimeMillis() + 5000;
while (!cond.getAsBoolean()) {
if (System.currentTimeMillis() > deadline) throw new AssertionError("timed out: " + what);
Thread.sleep(2);
}
}
static boolean throwsBackPressure(Runnable r) {
try { r.run(); return false; } catch (BackPressureException e) { return true; }
}
public static void main(String[] args) throws Exception {
Broker broker = new Broker(4);
SubscriptionOptions defaults = SubscriptionOptions.defaults();
// 1. Per-partition order with two concurrent publishers
broker.createTopic("orders", 4);
Map<Integer, List<Long>> seen = new ConcurrentHashMap<>();
AtomicInteger delivered = new AtomicInteger();
broker.subscribe("orders", "audit", m -> {
seen.computeIfAbsent(m.partition(), k -> Collections.synchronizedList(new ArrayList<>())).add(m.offset());
delivered.incrementAndGet();
}, defaults);
List<Thread> publishers = new ArrayList<>();
for (String tag : List.of("web", "mobile")) {
Thread t = new Thread(() -> {
for (int i = 0; i < 200; i++) broker.publish("orders", "customer-" + (i % 10), tag + "-" + i);
});
publishers.add(t);
t.start();
}
for (Thread t : publishers) t.join();
waitUntil(() -> delivered.get() == 400, "all 400 delivered");
boolean ordered = seen.values().stream().allMatch(list -> {
for (int i = 1; i < list.size(); i++) if (list.get(i) <= list.get(i - 1)) return false;
return true;
});
check(ordered, "per-partition order holds under two concurrent publishers");
// 2. Retry, then success
broker.createTopic("payments", 1);
AtomicInteger calls = new AtomicInteger();
Subscription flaky = broker.subscribe("payments", "flaky", m -> {
if (calls.incrementAndGet() < 3) throw new RuntimeException("gateway timeout");
}, defaults.withRetries(3, 1));
broker.publish("payments", "p1", "charge 500");
waitUntil(() -> calls.get() == 3, "three attempts");
broker.unsubscribe(flaky);
check(flaky.deadLettered == 0, "a handler that recovers within maxAttempts is not dead-lettered");
// 3. Dead letter
Subscription ops = broker.subscribe("payments.dlq", "ops", null, defaults, true);
Subscription broken = broker.subscribe("payments", "broken", m -> { throw new RuntimeException("schema mismatch"); },
defaults.withRetries(2, 1));
broker.publish("payments", "p2", "charge 900");
waitUntil(() -> broken.deadLettered == 1, "dead-lettered");
List<Message> dead = broker.poll(ops, 10);
check(dead.size() == 1 && dead.get(0).payload().equals("charge 900")
&& dead.get(0).headers().get("dlq.error").equals("schema mismatch")
&& dead.get(0).headers().get("dlq.attempts").equals("2"), "poison message lands in payments.dlq with failure headers");
// 4. Back-pressure: REJECT
broker.createTopic("metrics", 1);
Subscription strict = broker.subscribe("metrics", "strict", null, defaults.withLag(2, Overflow.REJECT));
broker.publish("metrics", null, 1);
broker.publish("metrics", null, 2);
check(throwsBackPressure(() -> broker.publish("metrics", null, 3)), "REJECT fails the third publish");
broker.unsubscribe(strict);
// 5. Back-pressure: DROP_OLDEST
Subscription lossy = broker.subscribe("metrics", "lossy", null, defaults.withLag(2, Overflow.DROP_OLDEST));
for (int i = 0; i < 5; i++) broker.publish("metrics", null, i);
List<Object> kept = broker.poll(lossy, 10).stream().map(Message::payload).toList();
check(kept.equals(List.of(3, 4)) && lossy.dropped == 3, "DROP_OLDEST keeps the newest two");
broker.unsubscribe(lossy);
// 6. Back-pressure: BLOCK, first timing out, then released by a commit
Subscription slow = broker.subscribe("metrics", "slow", null, defaults.withLag(1, Overflow.BLOCK));
broker.publish("metrics", null, "a");
check(throwsBackPressure(() -> broker.publish("metrics", null, "b", Map.of(), 50)), "BLOCK times out");
new Thread(() -> {
try { Thread.sleep(50); } catch (InterruptedException ignored) { }
broker.commit(slow, broker.poll(slow, 1).get(0));
}).start();
broker.publish("metrics", null, "c", Map.of(), 2000);
check(true, "BLOCK publisher resumes once the consumer commits");
// 7. Pull redelivery until commit
List<Message> first = broker.poll(slow, 10);
check(first.equals(broker.poll(slow, 10)) && first.get(0).payload().equals("c"), "uncommitted messages are redelivered");
broker.commit(slow, first.get(first.size() - 1));
check(broker.poll(slow, 10).isEmpty(), "committed messages are gone");
// 8. Graceful shutdown
check(broker.shutdown(2000), "shutdown drains push lanes");
try { broker.publish("metrics", null, "late"); check(false, "publish after shutdown"); }
catch (BrokerException e) { check(e.getMessage().contains("shut down"), "publish after shutdown is refused"); }
}
}
"""broker.py: an in-process pub-sub broker.
Topics are split into partitions (append-only logs). Each subscription keeps one
cursor per partition. Push subscriptions get one delivery lane per partition, so a
partition's messages reach a subscriber in order, one at a time. Pull subscriptions
poll and commit. Failed pushes are retried with exponential backoff and then copied
to the topic's dead-letter topic. A subscription more than max_lag messages behind
triggers its overflow policy on the publisher.
"""
from __future__ import annotations
import threading
import time
import zlib
from concurrent.futures import ThreadPoolExecutor
from dataclasses import dataclass, field
from enum import Enum
from typing import Any, Callable, Iterable
class Overflow(Enum):
BLOCK = "block" # publisher waits (with a timeout) for the subscriber to catch up
REJECT = "reject" # publisher gets BackPressureError
DROP_OLDEST = "drop_oldest" # the slow subscription skips its oldest undelivered message
class BrokerError(Exception):
pass
class BackPressureError(BrokerError):
pass
@dataclass(frozen=True)
class Message:
topic: str
partition: int
offset: int
key: str | None
payload: Any
headers: dict[str, str] = field(default_factory=dict)
class Partition:
"""An append-only log. Offsets below `base` have been trimmed."""
def __init__(self) -> None:
self.base = 0
self.log: list[Message] = []
@property
def end(self) -> int:
return self.base + len(self.log)
def read(self, offset: int) -> Message:
return self.log[offset - self.base]
def trim(self, upto: int) -> None:
if upto > self.base:
del self.log[: upto - self.base] # Simplification: O(n) shift, use a deque or ring buffer at high volume
self.base = upto
class Topic:
def __init__(self, name: str, partitions: int, retain_all: bool = False) -> None:
self.name = name
self.partitions = [Partition() for _ in range(partitions)]
self.retain_all = retain_all # dead-letter topics keep everything
self._next = 0
def partition_for(self, key: str | None) -> int:
if key is None: # no key, no ordering promise: spread round-robin
self._next = (self._next + 1) % len(self.partitions)
return self._next
return zlib.crc32(key.encode()) % len(self.partitions) # stable across runs, unlike hash()
Handler = Callable[[Message], None]
@dataclass(frozen=True)
class SubscriptionOptions:
max_lag: int = 1000
overflow: Overflow = Overflow.BLOCK
max_attempts: int = 3
backoff_s: float = 0.01 # first retry delay, doubled on each further attempt
def __post_init__(self) -> None:
if self.max_lag < 1 or self.max_attempts < 1:
raise BrokerError("max_lag and max_attempts must be at least 1")
class Subscription:
def __init__(self, name: str, topic: Topic, handler: Handler | None,
opts: SubscriptionOptions, from_beginning: bool) -> None:
self.name = name
self.topic = topic
self.handler = handler # None means pull mode
self.opts = opts
self.offsets = [p.base if from_beginning else p.end for p in topic.partitions]
self.busy = [False] * len(topic.partitions) # push lane running, per partition
self.active = True
self.dropped = 0
self.dead_lettered = 0
@property
def is_push(self) -> bool:
return self.handler is not None
def lag(self, partition: int) -> int:
return self.topic.partitions[partition].end - self.offsets[partition]
class Broker:
def __init__(self, workers: int = 4) -> None:
self._lock = threading.Lock()
self._changed = threading.Condition(self._lock)
self._topics: dict[str, Topic] = {}
self._subs: dict[str, list[Subscription]] = {}
self._pool = ThreadPoolExecutor(max_workers=workers, thread_name_prefix="broker")
self._closed = False
# ---- topics and subscriptions ----
def create_topic(self, name: str, partitions: int = 1) -> Topic:
with self._lock:
topic = self._add_topic(name, partitions, retain_all=False)
self._add_topic(name + ".dlq", 1, retain_all=True)
return topic
def topic_names(self) -> list[str]:
with self._lock:
return list(self._topics)
def subscribe(self, topic: str, name: str, handler: Handler | None = None,
opts: SubscriptionOptions | None = None, from_beginning: bool = False) -> Subscription:
with self._lock:
t = self._topic(topic)
if any(s.name == name for s in self._subs[topic]):
raise BrokerError(f"subscription {name} already exists on {topic}")
sub = Subscription(name, t, handler, opts or SubscriptionOptions(), from_beginning)
self._subs[topic].append(sub)
for p in range(len(t.partitions)):
self._schedule(sub, p) # a from-beginning push subscriber starts on the backlog
return sub
def unsubscribe(self, sub: Subscription) -> None:
with self._lock:
sub.active = False
self._subs[sub.topic.name].remove(sub)
self._trim(sub.topic)
self._changed.notify_all() # a publisher may have been blocked on this subscriber
# ---- publishing ----
def publish(self, topic: str, payload: Any, key: str | None = None,
headers: dict[str, str] | None = None, timeout_s: float = 1.0) -> Message:
deadline = time.monotonic() + timeout_s
with self._lock:
t = self._topic(topic)
p = t.partition_for(key)
self._make_room(t, p, deadline)
return self._append(t, p, key, payload, headers or {})
def _make_room(self, t: Topic, p: int, deadline: float) -> None:
while True:
if self._closed:
raise BrokerError("broker is shut down")
full = [s for s in self._subs[t.name] if s.lag(p) >= s.opts.max_lag]
if not full:
return
for s in full: # validate before mutating: a reject must not drop anything
if s.opts.overflow is Overflow.REJECT:
raise BackPressureError(f"{s.name} is {s.lag(p)} messages behind on {t.name}/{p}")
must_wait = False
for s in full:
if s.opts.overflow is Overflow.DROP_OLDEST:
s.offsets[p] += 1
s.dropped += 1
else:
must_wait = True
self._trim(t)
if not must_wait:
return
remaining = deadline - time.monotonic()
if remaining <= 0:
raise BackPressureError(f"timed out waiting for a slow subscriber on {t.name}/{p}")
self._changed.wait(remaining) # releases the lock while waiting
def _append(self, t: Topic, p: int, key: str | None, payload: Any,
headers: dict[str, str]) -> Message: # caller holds the lock
part = t.partitions[p]
msg = Message(t.name, p, part.end, key, payload, dict(headers))
part.log.append(msg)
for sub in self._subs[t.name]:
self._schedule(sub, p)
self._changed.notify_all()
return msg
# ---- push delivery ----
def _schedule(self, sub: Subscription, p: int) -> None: # caller holds the lock
if sub.is_push and sub.active and not sub.busy[p] and sub.lag(p) > 0:
sub.busy[p] = True
self._pool.submit(self._drain, sub, p)
def _drain(self, sub: Subscription, p: int) -> None:
while True:
with self._lock:
if not sub.active or sub.lag(p) == 0:
sub.busy[p] = False
self._changed.notify_all()
return
msg = sub.topic.partitions[p].read(sub.offsets[p])
self._deliver(sub, msg) # no lock held: handlers are slow and may publish
with self._lock:
# max(): DROP_OLDEST may already have moved the cursor past this message
sub.offsets[p] = max(sub.offsets[p], msg.offset + 1)
self._trim(sub.topic)
self._changed.notify_all()
def _deliver(self, sub: Subscription, msg: Message) -> None:
assert sub.handler is not None
for attempt in range(1, sub.opts.max_attempts + 1):
try:
sub.handler(msg)
return
except Exception as exc: # a handler failure must never kill the lane
if attempt == sub.opts.max_attempts:
self._dead_letter(sub, msg, exc, attempt)
return
# Simplification: sleeping holds a worker; schedule the retry instead if lanes far outnumber workers
time.sleep(sub.opts.backoff_s * 2 ** (attempt - 1))
def _dead_letter(self, sub: Subscription, msg: Message, exc: Exception, attempts: int) -> None:
with self._lock:
sub.dead_lettered += 1
dlq = self._topics.get(msg.topic + ".dlq")
if dlq is None: # a dead-letter topic has no dead-letter topic of its own
return
headers = {**msg.headers,
"dlq.subscription": sub.name,
"dlq.error": str(exc),
"dlq.attempts": str(attempts),
"dlq.source": f"{msg.topic}/{msg.partition}/{msg.offset}"}
self._append(dlq, 0, msg.key, msg.payload, headers)
# ---- pull delivery ----
def poll(self, sub: Subscription, max_messages: int = 100,
partitions: Iterable[int] | None = None) -> list[Message]:
with self._lock:
if sub.is_push:
raise BrokerError("poll() is for pull subscriptions")
out: list[Message] = []
for p in partitions if partitions is not None else range(len(sub.offsets)):
part = sub.topic.partitions[p]
offset = sub.offsets[p]
while offset < part.end and len(out) < max_messages:
out.append(part.read(offset))
offset += 1
return out # nothing is committed here, so unacked messages come back next poll
def commit(self, sub: Subscription, msg: Message) -> None:
"""Acks msg and everything before it on the same partition."""
with self._lock:
if msg.topic != sub.topic.name:
raise BrokerError("message is from another topic")
sub.offsets[msg.partition] = max(sub.offsets[msg.partition], msg.offset + 1)
self._trim(sub.topic)
self._changed.notify_all()
# ---- shutdown ----
def shutdown(self, timeout_s: float = 5.0) -> bool:
"""Refuse new publishes, let push lanes drain, then stop the workers."""
with self._lock:
self._closed = True
self._changed.notify_all() # blocked publishers fail fast
drained = self._changed.wait_for(self._idle, timeout=timeout_s)
if not drained:
for subs in self._subs.values():
for s in subs:
s.active = False # lanes stop after their current message
self._pool.shutdown(wait=True)
return drained
def _idle(self) -> bool:
return all(not s.busy[p] and s.lag(p) == 0
for subs in self._subs.values() for s in subs if s.is_push
for p in range(len(s.offsets)))
# ---- helpers ----
def _topic(self, name: str) -> Topic:
t = self._topics.get(name)
if t is None:
raise BrokerError(f"unknown topic {name}")
return t
def _add_topic(self, name: str, partitions: int, retain_all: bool) -> Topic:
if name in self._topics:
raise BrokerError(f"topic {name} already exists")
if partitions < 1:
raise BrokerError("a topic needs at least one partition")
t = self._topics[name] = Topic(name, partitions, retain_all)
self._subs[name] = []
return t
def _trim(self, t: Topic) -> None: # caller holds the lock: keep what the slowest cursor needs
if t.retain_all:
return
subs = self._subs[t.name]
for i, part in enumerate(t.partitions):
part.trim(min((s.offsets[i] for s in subs), default=part.end))
def wait_until(cond: Callable[[], bool], timeout_s: float = 5.0) -> None:
deadline = time.monotonic() + timeout_s
while not cond():
if time.monotonic() > deadline:
raise AssertionError("condition not met in time")
time.sleep(0.002)
def demo() -> None:
broker = Broker(workers=4)
# 1. Per-partition order with two concurrent publishers
broker.create_topic("orders", partitions=4)
seen: dict[int, list[int]] = {}
seen_lock = threading.Lock()
def audit(m: Message) -> None:
with seen_lock:
seen.setdefault(m.partition, []).append(m.offset)
broker.subscribe("orders", "audit", audit)
def publisher(tag: str) -> None:
for i in range(200):
broker.publish("orders", f"{tag}-{i}", key=f"customer-{i % 10}")
threads = [threading.Thread(target=publisher, args=(tag,)) for tag in ("web", "mobile")]
for t in threads:
t.start()
for t in threads:
t.join()
wait_until(lambda: sum(len(v) for v in list(seen.values())) == 400)
assert all(offs == sorted(set(offs)) for offs in seen.values())
print("ok per-partition order holds under two concurrent publishers")
# 2. Retry, then success
broker.create_topic("payments")
calls: list[int] = []
def flaky(m: Message) -> None:
calls.append(m.offset)
if len(calls) < 3:
raise RuntimeError("gateway timeout")
flaky_sub = broker.subscribe("payments", "flaky", flaky, SubscriptionOptions(max_attempts=3, backoff_s=0.001))
broker.publish("payments", "charge 500", key="p1")
wait_until(lambda: len(calls) == 3)
broker.unsubscribe(flaky_sub)
assert flaky_sub.dead_lettered == 0
print("ok a handler that recovers within max_attempts is not dead-lettered")
# 3. Dead letter
ops = broker.subscribe("payments.dlq", "ops", from_beginning=True)
def broken(_: Message) -> None:
raise ValueError("schema mismatch")
bad = broker.subscribe("payments", "broken", broken, SubscriptionOptions(max_attempts=2, backoff_s=0.001))
broker.publish("payments", "charge 900", key="p2")
wait_until(lambda: bad.dead_lettered == 1)
[dead] = broker.poll(ops)
assert dead.payload == "charge 900"
assert dead.headers["dlq.error"] == "schema mismatch" and dead.headers["dlq.attempts"] == "2"
print("ok poison message lands in payments.dlq with failure headers")
# 4. REJECT
broker.create_topic("metrics")
strict = broker.subscribe("metrics", "strict", opts=SubscriptionOptions(max_lag=2, overflow=Overflow.REJECT))
broker.publish("metrics", 1)
broker.publish("metrics", 2)
try:
broker.publish("metrics", 3)
raise AssertionError("expected back-pressure")
except BackPressureError:
pass
broker.unsubscribe(strict)
print("ok REJECT fails the third publish")
# 5. DROP_OLDEST
lossy = broker.subscribe("metrics", "lossy", opts=SubscriptionOptions(max_lag=2, overflow=Overflow.DROP_OLDEST))
for i in range(5):
broker.publish("metrics", i)
assert [m.payload for m in broker.poll(lossy)] == [3, 4] and lossy.dropped == 3
broker.unsubscribe(lossy)
print("ok DROP_OLDEST keeps the newest two")
# 6. BLOCK: times out, then is released by a commit
slow = broker.subscribe("metrics", "slow", opts=SubscriptionOptions(max_lag=1))
broker.publish("metrics", "a")
try:
broker.publish("metrics", "b", timeout_s=0.05)
raise AssertionError("expected a timeout")
except BackPressureError:
pass
def consume_later() -> None:
time.sleep(0.05)
broker.commit(slow, broker.poll(slow)[0])
threading.Thread(target=consume_later).start()
broker.publish("metrics", "c", timeout_s=2) # blocks until "a" is committed
print("ok BLOCK publisher resumes once the consumer commits")
# 7. Pull redelivery until commit
first = broker.poll(slow)
assert first == broker.poll(slow) and [m.payload for m in first] == ["c"]
broker.commit(slow, first[-1])
assert broker.poll(slow) == []
print("ok uncommitted messages are redelivered, committed ones are gone")
# 8. Graceful shutdown
assert broker.shutdown(timeout_s=2)
try:
broker.publish("metrics", "late")
raise AssertionError("publish after shutdown")
except BrokerError as e:
assert "shut down" in str(e)
print("all pub-sub checks passed")
if __name__ == "__main__":
demo()
// pubsub.ts -> npx tsx pubsub.ts
enum Overflow { Block = "BLOCK", Reject = "REJECT", DropOldest = "DROP_OLDEST" }
class BrokerError extends Error {}
class BackPressureError extends BrokerError {}
interface Message {
readonly topic: string;
readonly partition: number;
readonly offset: number;
readonly key: string | null;
readonly payload: unknown;
readonly headers: Readonly<Record<string, string>>;
}
/** An append-only log. Offsets below base have been trimmed. */
class Partition {
base = 0;
readonly log: Message[] = [];
get end(): number { return this.base + this.log.length; }
read(offset: number): Message { return this.log[offset - this.base]; }
trim(upto: number): void {
if (upto > this.base) { this.log.splice(0, upto - this.base); this.base = upto; }
}
}
class Topic {
readonly partitions: Partition[];
private next = 0;
constructor(readonly name: string, count: number, readonly retainAll: boolean) {
this.partitions = Array.from({ length: count }, () => new Partition());
}
partitionFor(key: string | null): number {
if (key === null) { this.next = (this.next + 1) % this.partitions.length; return this.next; }
let h = 0x811c9dc5; // FNV-1a: stable across runs and processes
for (let i = 0; i < key.length; i++) { h ^= key.charCodeAt(i); h = Math.imul(h, 0x01000193) >>> 0; }
return h % this.partitions.length;
}
}
type Handler = (m: Message) => void | Promise<void>;
interface SubscriptionOptions { maxLag: number; overflow: Overflow; maxAttempts: number; backoffMs: number }
const DEFAULTS: SubscriptionOptions = { maxLag: 1000, overflow: Overflow.Block, maxAttempts: 3, backoffMs: 10 };
class Subscription {
readonly offsets: number[];
readonly busy: boolean[];
active = true;
dropped = 0;
deadLettered = 0;
constructor(readonly name: string, readonly topic: Topic, readonly handler: Handler | null,
readonly opts: SubscriptionOptions, fromBeginning: boolean) {
this.offsets = topic.partitions.map((p) => (fromBeginning ? p.base : p.end));
this.busy = topic.partitions.map(() => false);
}
get isPush(): boolean { return this.handler !== null; }
lag(p: number): number { return this.topic.partitions[p].end - this.offsets[p]; }
}
const sleep = (ms: number) => new Promise<void>((resolve) => setTimeout(resolve, ms));
/** Caps how many handlers run at once: the event-loop version of a fixed thread pool. */
class Semaphore {
private readonly waiting: Array<() => void> = [];
constructor(private permits: number) {}
async acquire(): Promise<void> {
if (this.permits > 0) { this.permits--; return; }
await new Promise<void>((resolve) => this.waiting.push(resolve));
}
release(): void {
const next = this.waiting.shift();
if (next) next(); else this.permits++;
}
}
class Broker {
private readonly topics = new Map<string, Topic>();
private readonly subs = new Map<string, Subscription[]>();
private waiters: Array<() => void> = []; // blocked publishers and shutdown
private readonly workers: Semaphore;
private closed = false;
constructor(workers = 4) { this.workers = new Semaphore(workers); }
// ---- topics and subscriptions ----
createTopic(name: string, partitions = 1): Topic {
const topic = this.addTopic(name, partitions, false);
this.addTopic(`${name}.dlq`, 1, true);
return topic;
}
subscribe(topic: string, name: string, handler: Handler | null = null,
opts: Partial<SubscriptionOptions> = {}, fromBeginning = false): Subscription {
const t = this.topic(topic);
const list = this.subs.get(topic)!;
if (list.some((s) => s.name === name)) throw new BrokerError(`subscription ${name} already exists on ${topic}`);
const merged = { ...DEFAULTS, ...opts };
if (merged.maxLag < 1 || merged.maxAttempts < 1) throw new BrokerError("maxLag and maxAttempts must be at least 1");
const sub = new Subscription(name, t, handler, merged, fromBeginning);
list.push(sub);
t.partitions.forEach((_, p) => this.schedule(sub, p));
return sub;
}
unsubscribe(sub: Subscription): void {
sub.active = false;
const list = this.subs.get(sub.topic.name)!;
list.splice(list.indexOf(sub), 1);
this.trim(sub.topic);
this.notifyAll();
}
// ---- publishing ----
async publish(topic: string, payload: unknown, key: string | null = null,
headers: Record<string, string> = {}, timeoutMs = 1000): Promise<Message> {
const deadline = Date.now() + timeoutMs;
const t = this.topic(topic);
const p = t.partitionFor(key);
for (;;) {
if (this.closed) throw new BrokerError("broker is shut down");
// check and append in one synchronous step: an await between them would let another publish in
if (this.roomFor(t, p)) return this.append(t, p, key, payload, headers);
const left = deadline - Date.now();
if (left <= 0) throw new BackPressureError(`timed out waiting for a slow subscriber on ${t.name}/${p}`);
await this.changed(left);
}
}
private roomFor(t: Topic, p: number): boolean {
const full = this.subs.get(t.name)!.filter((s) => s.lag(p) >= s.opts.maxLag);
for (const s of full) { // validate before mutating: a reject must not drop anything
if (s.opts.overflow === Overflow.Reject) throw new BackPressureError(`${s.name} is ${s.lag(p)} messages behind on ${t.name}/${p}`);
}
let mustWait = false;
for (const s of full) {
if (s.opts.overflow === Overflow.DropOldest) { s.offsets[p]++; s.dropped++; } else mustWait = true;
}
this.trim(t);
return !mustWait;
}
private append(t: Topic, p: number, key: string | null, payload: unknown, headers: Record<string, string>): Message {
const part = t.partitions[p];
const msg: Message = { topic: t.name, partition: p, offset: part.end, key, payload, headers: { ...headers } };
part.log.push(msg);
for (const s of this.subs.get(t.name)!) this.schedule(s, p);
this.notifyAll();
return msg;
}
// ---- push delivery ----
private schedule(sub: Subscription, p: number): void {
if (sub.isPush && sub.active && !sub.busy[p] && sub.lag(p) > 0) {
sub.busy[p] = true;
void this.drain(sub, p);
}
}
private async drain(sub: Subscription, p: number): Promise<void> {
while (sub.active && sub.lag(p) > 0) {
const msg = sub.topic.partitions[p].read(sub.offsets[p]);
await this.workers.acquire();
try { await this.deliver(sub, msg); } finally { this.workers.release(); }
sub.offsets[p] = Math.max(sub.offsets[p], msg.offset + 1); // DROP_OLDEST may have moved it already
this.trim(sub.topic);
this.notifyAll();
}
sub.busy[p] = false;
this.notifyAll();
}
private async deliver(sub: Subscription, msg: Message): Promise<void> {
for (let attempt = 1; ; attempt++) {
try { await sub.handler!(msg); return; }
catch (e) { // a handler failure must never kill the lane
if (attempt >= sub.opts.maxAttempts) { this.deadLetter(sub, msg, e, attempt); return; }
await sleep(sub.opts.backoffMs * 2 ** (attempt - 1));
}
}
}
private deadLetter(sub: Subscription, msg: Message, error: unknown, attempts: number): void {
sub.deadLettered++;
const dlq = this.topics.get(`${msg.topic}.dlq`);
if (!dlq) return; // a dead-letter topic has no dead-letter topic of its own
this.append(dlq, 0, msg.key, msg.payload, {
...msg.headers,
"dlq.subscription": sub.name,
"dlq.error": error instanceof Error ? error.message : String(error),
"dlq.attempts": String(attempts),
"dlq.source": `${msg.topic}/${msg.partition}/${msg.offset}`,
});
}
// ---- pull delivery ----
poll(sub: Subscription, max = 100, partitions?: number[]): Message[] {
if (sub.isPush) throw new BrokerError("poll() is for pull subscriptions");
const out: Message[] = [];
for (const p of partitions ?? sub.offsets.map((_, i) => i)) {
const part = sub.topic.partitions[p];
for (let o = sub.offsets[p]; o < part.end && out.length < max; o++) out.push(part.read(o));
}
return out; // nothing is committed here, so unacked messages come back next poll
}
/** Acks msg and everything before it on the same partition. */
commit(sub: Subscription, msg: Message): void {
if (msg.topic !== sub.topic.name) throw new BrokerError("message is from another topic");
sub.offsets[msg.partition] = Math.max(sub.offsets[msg.partition], msg.offset + 1);
this.trim(sub.topic);
this.notifyAll();
}
// ---- shutdown ----
async shutdown(timeoutMs = 5000): Promise<boolean> {
this.closed = true;
this.notifyAll(); // blocked publishers fail fast
const deadline = Date.now() + timeoutMs;
while (!this.idle()) {
const left = deadline - Date.now();
if (left <= 0) {
for (const list of this.subs.values()) for (const s of list) s.active = false;
return false;
}
await this.changed(left);
}
return true;
}
private idle(): boolean {
for (const list of this.subs.values())
for (const s of list)
if (s.isPush && s.offsets.some((_, p) => s.busy[p] || s.lag(p) > 0)) return false;
return true;
}
// ---- helpers ----
private topic(name: string): Topic {
const t = this.topics.get(name);
if (!t) throw new BrokerError(`unknown topic ${name}`);
return t;
}
private addTopic(name: string, partitions: number, retainAll: boolean): Topic {
if (this.topics.has(name)) throw new BrokerError(`topic ${name} already exists`);
if (partitions < 1) throw new BrokerError("a topic needs at least one partition");
const t = new Topic(name, partitions, retainAll);
this.topics.set(name, t);
this.subs.set(name, []);
return t;
}
private trim(t: Topic): void {
if (t.retainAll) return;
const list = this.subs.get(t.name)!;
t.partitions.forEach((part, p) => part.trim(Math.min(part.end, ...list.map((s) => s.offsets[p]))));
}
/** Resolves on the next state change or after timeoutMs, like Condition.wait(timeout). */
private changed(timeoutMs: number): Promise<void> {
return new Promise((resolve) => {
const done = () => { clearTimeout(timer); resolve(); };
const timer = setTimeout(done, timeoutMs);
this.waiters.push(done);
});
}
private notifyAll(): void {
const waiting = this.waiters;
this.waiters = [];
waiting.forEach((wake) => wake());
}
}
// ---- checks ----
function check(ok: boolean, what: string): void {
if (!ok) throw new Error(`FAILED: ${what}`);
console.log(`ok ${what}`);
}
async function waitUntil(cond: () => boolean, what: string): Promise<void> {
const deadline = Date.now() + 5000;
while (!cond()) {
if (Date.now() > deadline) throw new Error(`timed out: ${what}`);
await sleep(2);
}
}
async function throwsBackPressure(fn: () => Promise<unknown>): Promise<boolean> {
try { await fn(); return false; } catch (e) { return e instanceof BackPressureError; }
}
async function main(): Promise<void> {
const broker = new Broker(4);
// 1. Per-partition order with two concurrent publishers
broker.createTopic("orders", 4);
const seen = new Map<number, number[]>();
let delivered = 0;
broker.subscribe("orders", "audit", async (m) => {
await sleep(0); // pretend to do I/O, so lanes interleave
const list = seen.get(m.partition) ?? [];
list.push(m.offset);
seen.set(m.partition, list);
delivered++;
});
const publisher = async (tag: string) => {
for (let i = 0; i < 200; i++) await broker.publish("orders", `${tag}-${i}`, `customer-${i % 10}`);
};
await Promise.all([publisher("web"), publisher("mobile")]);
await waitUntil(() => delivered === 400, "all 400 delivered");
check([...seen.values()].every((offs) => offs.every((o, i) => i === 0 || o > offs[i - 1])),
"per-partition order holds under two concurrent publishers");
// 2. Retry, then success
broker.createTopic("payments");
let calls = 0;
const flaky = broker.subscribe("payments", "flaky", () => {
if (++calls < 3) throw new Error("gateway timeout");
}, { maxAttempts: 3, backoffMs: 1 });
await broker.publish("payments", "charge 500", "p1");
await waitUntil(() => calls === 3, "three attempts");
broker.unsubscribe(flaky);
check(flaky.deadLettered === 0, "a handler that recovers within maxAttempts is not dead-lettered");
// 3. Dead letter
const ops = broker.subscribe("payments.dlq", "ops", null, {}, true);
const broken = broker.subscribe("payments", "broken", () => { throw new Error("schema mismatch"); },
{ maxAttempts: 2, backoffMs: 1 });
await broker.publish("payments", "charge 900", "p2");
await waitUntil(() => broken.deadLettered === 1, "dead-lettered");
const dead = broker.poll(ops);
check(dead.length === 1 && dead[0].payload === "charge 900" && dead[0].headers["dlq.error"] === "schema mismatch"
&& dead[0].headers["dlq.attempts"] === "2", "poison message lands in payments.dlq with failure headers");
// 4. REJECT
broker.createTopic("metrics");
const strict = broker.subscribe("metrics", "strict", null, { maxLag: 2, overflow: Overflow.Reject });
await broker.publish("metrics", 1);
await broker.publish("metrics", 2);
check(await throwsBackPressure(() => broker.publish("metrics", 3)), "REJECT fails the third publish");
broker.unsubscribe(strict);
// 5. DROP_OLDEST
const lossy = broker.subscribe("metrics", "lossy", null, { maxLag: 2, overflow: Overflow.DropOldest });
for (let i = 0; i < 5; i++) await broker.publish("metrics", i);
check(JSON.stringify(broker.poll(lossy).map((m) => m.payload)) === "[3,4]" && lossy.dropped === 3,
"DROP_OLDEST keeps the newest two");
broker.unsubscribe(lossy);
// 6. BLOCK: times out, then is released by a commit
const slow = broker.subscribe("metrics", "slow", null, { maxLag: 1 });
await broker.publish("metrics", "a");
check(await throwsBackPressure(() => broker.publish("metrics", "b", null, {}, 50)), "BLOCK times out");
setTimeout(() => broker.commit(slow, broker.poll(slow)[0]), 50);
await broker.publish("metrics", "c", null, {}, 2000);
check(true, "BLOCK publisher resumes once the consumer commits");
// 7. Pull redelivery until commit
const first = broker.poll(slow);
check(JSON.stringify(first) === JSON.stringify(broker.poll(slow)) && first[0].payload === "c",
"uncommitted messages are redelivered");
broker.commit(slow, first[first.length - 1]);
check(broker.poll(slow).length === 0, "committed messages are gone");
// 8. Graceful shutdown
check(await broker.shutdown(2000), "shutdown drains push lanes");
try { await broker.publish("metrics", "late"); check(false, "publish after shutdown"); }
catch (e) { check(e instanceof BrokerError && e.message.includes("shut down"), "publish after shutdown is refused"); }
}
main().then(() => console.log("all pub-sub checks passed"));
Walking through the important decisions
makeRoom validates before it mutates. It first looks for any REJECT subscription that is full and throws. Only then does it drop messages for DROP_OLDEST subscriptions. If it did those in the other order, a rejected publish would still have cost a lossy subscriber a message. It's the same "validate, then mutate" rule from the interview framework, applied to a policy loop.
The lane is the ordering mechanism. busy[p] says a worker is already draining partition p for this subscription. schedule starts a lane only if none is running. The lane keeps reading until the cursor reaches the end, then clears the flag under the lock. That last detail matters. If the lane cleared the flag after releasing the lock, a publish could land in between, see busy == true, skip scheduling, and leave a message stranded until the next publish.
Cursors move after delivery, not before. If the cursor moved first and the process were interrupted, or the handler kept failing, the message would be lost from that subscription's point of view. Moving it after gives at-least-once semantics. The other half of that bargain is that handlers must be idempotent. See idempotent consumers.
max() on cursor updates. A DROP_OLDEST publisher can push a cursor forward while a lane is delivering. When the lane finishes, it must not move the cursor backwards. max(current, offset + 1) handles both cases in one expression. One consequence is that a dropped message might also be the in-flight one, so the drop counter is approximate under contention. For a metrics feed that's fine. Say so if asked.
The dead-letter topic is just a topic. Operators consume it with an ordinary pull subscription starting from the beginning. They can inspect the headers, fix the bug, and republish to the original topic. No special API is needed. That uniformity is why it's modelled as a topic and not a list on the side.
TypeScript has no lock, but it has a gap. In publish, the room check and the append run in one synchronous block. If you wrote await this.makeRoom(...) followed by this.append(...), the await would yield to the event loop even when no waiting was needed. Another publisher could then fill the last slot in between. The Java and Python versions get the same atomicity from the lock. TypeScript gets it by never awaiting between check and act.
7. Concurrency
What's shared
| State | Written by | Protected by |
|---|---|---|
| Topic map, subscription lists | createTopic, subscribe, unsubscribe | Broker lock |
| Partition logs | Publishers (append), lanes and commits (trim) | Broker lock |
Cursors, busy flags, active | Publishers (drop), lanes, commits, shutdown | Broker lock |
dropped, deadLettered counters | Under the broker lock | Lock for writes, volatile in Java for lock-free reads |
| Messages | Nobody after creation | Immutability |
| Handler state | The handler | The handler's own problem, but a lane never runs two messages from one partition at once |
Why one lock is enough
Every critical section in this design is a handful of list operations. The only slow thing, the handler, runs outside the lock. A single lock is therefore not a throughput problem until you have millions of messages per second, which an in-process broker won't see. It also makes the cross-object invariants trivially safe. "Trim never removes what a cursor still needs" involves the log and every subscription's cursor, and holding one lock while reading all of them is the simplest correct way to check it. Finer locks (per topic, then per partition) are an easy upgrade later, because every critical section touches exactly one topic. That's worth saying in the interview. The thread-safe class design page covers the trade-off in general.
The condition variable
BLOCK publishers wait on the same lock's condition and are woken by notifyAll whenever a cursor moves, a subscription leaves, or the broker shuts down. Three details:
- Wait in a loop. A wake-up only means "something changed". The publisher re-checks every lag, because another publisher may have taken the slot first.
- Always wait with a timeout. A pull consumer that crashed without unsubscribing would otherwise block publishers forever. The timeout turns a hang into an error the publisher can act on.
notifyAll, notnotify. Publishers wait for different partitions and different subscriptions. Waking only one waiter can wake the wrong one, which then goes back to sleep while the right one never wakes.
Races we designed out
| Race | What would go wrong | How the design prevents it |
|---|---|---|
| Two workers drain the same partition for one subscription | Messages delivered out of order or twice | busy[p] is set and cleared under the lock, and schedule checks it |
| A lane exits just as a new message arrives | The message is stranded until the next publish | The lane decides to exit and clears busy in the same critical section where it sees lag == 0 |
| Trim removes a message a lane is about to read | Index error or wrong message | The lane's cursor hasn't moved yet, so trim keeps the message. A message already read is held by reference. |
| A publisher waits forever after a subscriber leaves | Hang | unsubscribe calls notifyAll |
| A handler publishes to another topic | Deadlock, if the handler ran under the lock | Handlers never run under the lock |
The deadlock you can still build
A push handler that publishes to its own topic with a BLOCK subscription that is full is waiting for itself. The lane can't advance until the handler returns, and the handler can't return until the lane advances. The timeout turns this into a BackPressureError rather than a hang, but it's still a design bug. If a handler must republish (for example, to delay a retry), it should publish to a different topic, or that topic's subscriptions should use REJECT or DROP_OLDEST.
Thread count and the worker pool
Lanes are tasks, not threads. A broker with 1,000 subscriptions and 8 partitions has up to 8,000 lanes, but only workers run at once. An idle lane costs nothing, because it doesn't exist until a message arrives. The cost of this design is head-of-line blocking between lanes. If all workers are busy with slow handlers, a fast subscriber waits for a free worker. Two standard fixes are a separate pool per subscription class (slow vs fast), or a dedicated pool for subscriptions marked as slow. Both are a constructor parameter away.
Retry backoff currently sleeps on the worker. That keeps the code short and is semantically correct, because the partition must wait for the message anyway. The cost is a worker held idle during the sleep. With many failing lanes, this can starve healthy ones. The fix is to hand the retry to a scheduled executor and release the worker. That is the trade-off comment in deliver. The task scheduler case study builds exactly that piece.
8. Extensibility: "the interviewer adds X"
Extension A: consumer groups (competing consumers)
"Now several instances of the same service should share the work on a topic, and each message should be processed by only one of them."
That's a consumer group. The broker already has the building block: a pull subscription with one cursor per partition. A group is one subscription shared by several members, where each partition is owned by exactly one member. Ordering per partition still holds, because only one member reads a given partition. The only broker change is the partitions parameter on poll, which the code above already has.
"""Extension: consumer groups on top of a pull subscription."""
import threading
from broker import Broker, BrokerError, Message
class ConsumerGroup:
"""Members share one subscription. Each partition belongs to exactly one member,
so a partition's messages are still processed in order, by one consumer at a time."""
def __init__(self, broker: Broker, topic: str, group: str) -> None:
self._broker = broker
self._sub = broker.subscribe(topic, group) # pull mode: one shared cursor per partition
self._lock = threading.Lock()
self._members: list[str] = []
self._owned: dict[str, list[int]] = {}
def join(self, member: str) -> None:
with self._lock:
self._members.append(member)
self._rebalance()
def leave(self, member: str) -> None:
with self._lock:
self._members.remove(member)
self._rebalance()
def assignment(self, member: str) -> list[int]:
with self._lock:
return list(self._owned.get(member, []))
def poll(self, member: str, max_messages: int = 100) -> list[Message]:
return self._broker.poll(self._sub, max_messages, partitions=self.assignment(member))
def commit(self, member: str, msg: Message) -> None:
with self._lock: # lock order is always group, then broker
if msg.partition not in self._owned.get(member, []):
raise BrokerError(f"{member} no longer owns partition {msg.partition}") # fencing
self._broker.commit(self._sub, msg)
def _rebalance(self) -> None: # Simplification: round-robin, moves many partitions; sticky assignment moves fewer
self._owned = {m: [] for m in self._members}
for p in range(len(self._sub.offsets)):
if self._members:
self._owned[self._members[p % len(self._members)]].append(p)
if __name__ == "__main__":
broker = Broker()
broker.create_topic("jobs", partitions=4)
group = ConsumerGroup(broker, "jobs", "workers")
group.join("w1")
group.join("w2")
assert group.assignment("w1") == [0, 2] and group.assignment("w2") == [1, 3]
for i in range(20):
broker.publish("jobs", i, key=f"k{i}")
w1, w2 = group.poll("w1"), group.poll("w2")
assert sorted(m.payload for m in w1 + w2) == list(range(20)) # each message to exactly one member
assert not {m.partition for m in w1} & {m.partition for m in w2}
for m in w1:
group.commit("w1", m)
group.leave("w2") # w2 crashes before committing anything
assert group.assignment("w1") == [0, 1, 2, 3]
redelivered = group.poll("w1")
assert sorted(m.payload for m in redelivered) == sorted(m.payload for m in w2) # at-least-once
try:
group.commit("w2", (w2 or w1)[0]) # w2 owns nothing now, so any commit is fenced off
raise AssertionError("a member that left must not commit")
except BrokerError:
pass
broker.shutdown()
print("consumer group checks passed")
What changed: one new class, and nothing in the broker. What to say: a member that crashes loses its partitions to the survivors, who re-read from the last committed offset. That's at-least-once delivery again. The commit check is fencing: a slow member that was rebalanced away must not commit offsets for a partition it no longer owns, or it could skip messages the new owner hasn't processed.
Extension B: wildcard topics and content filters
"A fraud service wants every
orders.*topic, including ones created later, but only orders above 1,000."
Two separate features hide in that sentence. The filter is a Decorator around the handler. The broker doesn't change, and a filtered-out message still moves the cursor, so it can't cause lag. The wildcard needs a hook on topic creation, which fits a subclass that overrides create_topic.
"""Extension: wildcard subscriptions with a content filter."""
import fnmatch
from broker import Broker, Handler, Message, SubscriptionOptions, wait_until
def filtered(predicate, handler: Handler) -> Handler:
"""Decorator: skip unwanted messages. Skipped messages still advance the cursor."""
def wrapper(msg: Message) -> None:
if predicate(msg):
handler(msg)
return wrapper
class WildcardBroker(Broker):
def __init__(self, workers: int = 4) -> None:
super().__init__(workers)
# Simplification: not synchronised with create_topic; share one lock if topics are created concurrently
self._patterns: list[tuple[str, str, Handler, SubscriptionOptions | None]] = []
def subscribe_pattern(self, pattern: str, name: str, handler: Handler,
opts: SubscriptionOptions | None = None) -> None:
self._patterns.append((pattern, name, handler, opts))
for topic in self.topic_names():
if self._matches(pattern, topic):
self.subscribe(topic, name, handler, opts)
def create_topic(self, name: str, partitions: int = 1):
topic = super().create_topic(name, partitions)
for pattern, sub_name, handler, opts in self._patterns:
if self._matches(pattern, name):
self.subscribe(name, sub_name, handler, opts)
return topic
@staticmethod
def _matches(pattern: str, topic: str) -> bool:
return fnmatch.fnmatchcase(topic, pattern) and not topic.endswith(".dlq")
if __name__ == "__main__":
broker = WildcardBroker()
broker.create_topic("orders.eu")
broker.create_topic("payments")
big: list[tuple[str, int]] = []
broker.subscribe_pattern("orders.*", "fraud",
filtered(lambda m: m.payload["amount"] >= 1000,
lambda m: big.append((m.topic, m.payload["amount"]))))
broker.create_topic("orders.us") # created after the pattern subscription
broker.publish("orders.eu", {"amount": 50})
broker.publish("orders.eu", {"amount": 1500})
broker.publish("orders.us", {"amount": 2500})
broker.publish("payments", {"amount": 9999})
wait_until(lambda: len(big) == 2)
assert broker.shutdown()
assert sorted(big) == [("orders.eu", 1500), ("orders.us", 2500)]
print("wildcard and filter checks passed")
A follow-up the interviewer may ask: should filtering happen in the broker instead? For an in-process broker, subscriber-side filtering is fine, because the "delivery" is a function call. In a networked broker, broker-side filtering saves bandwidth, which is why systems like Google Pub/Sub accept a filter expression at subscription time.
Extension C: message time-to-live
"Price updates older than five seconds are useless. Don't deliver them."
Put the expiry time in a header when publishing, and check it at delivery with an injected clock, so the test doesn't sleep for five seconds. Again a handler decorator does it, and again the broker doesn't change.
"""Extension: per-message time-to-live, checked at delivery with an injectable clock."""
import time
from typing import Callable
from broker import Broker, Handler, Message, wait_until
TTL_HEADER = "expires_at_ms"
def wall_clock_ms() -> int:
return int(time.time() * 1000)
def publish_with_ttl(broker: Broker, topic: str, payload, ttl_ms: int, key: str | None = None,
now_ms: Callable[[], int] = wall_clock_ms) -> Message:
return broker.publish(topic, payload, key=key, headers={TTL_HEADER: str(now_ms() + ttl_ms)})
class ExpiringHandler:
"""Decorator: ack and skip expired messages. A stale price is worse than none."""
def __init__(self, handler: Handler, now_ms: Callable[[], int] = wall_clock_ms) -> None:
self._handler = handler
self._now_ms = now_ms
self.expired = 0
def __call__(self, msg: Message) -> None:
expires = msg.headers.get(TTL_HEADER)
if expires is not None and self._now_ms() >= int(expires):
self.expired += 1
return
self._handler(msg)
if __name__ == "__main__":
broker = Broker()
broker.create_topic("prices")
got: list[str] = []
handler = ExpiringHandler(lambda m: got.append(m.payload), now_ms=lambda: 10_000) # consumer's "now"
broker.subscribe("prices", "ticker", handler)
publisher_clock = lambda: 4_000 # published 6 seconds before the consumer's "now"
publish_with_ttl(broker, "prices", "AAPL 190.10", ttl_ms=5_000, now_ms=publisher_clock) # expired at 9,000
publish_with_ttl(broker, "prices", "AAPL 190.25", ttl_ms=60_000, now_ms=publisher_clock) # valid
broker.publish("prices", "no ttl")
wait_until(lambda: len(got) + handler.expired == 3)
assert broker.shutdown()
assert got == ["AAPL 190.25", "no ttl"] and handler.expired == 1
print("ttl checks passed")
Notice the pattern across all three extensions. Two of them are decorators on a one-method Handler, and the third is a new class using an existing method. That's the payoff for keeping the subscriber contract to a single function.
9. Testing approach
Concurrency code needs two kinds of tests. Rule tests check one behaviour each, deterministically. Stress tests run many threads to shake out races. The rule tests below never sleep for a fixed time to "let things happen". They wait for a condition with a deadline. Fixed sleeps make tests slow when they pass and flaky when the machine is busy.
What to cover, and why:
- Same key, same partition, publish order. The core ordering promise.
- Fan-out. Two subscriptions each get every message.
- A late subscriber starts at the end.
- Retry then success doesn't dead-letter.
- A poison message is dead-lettered and doesn't block the partition. The messages after it still arrive.
REJECTraises and changes nothing. The "validate before mutate" check.DROP_OLDESTkeeps the newest.BLOCKtimes out, then succeeds after a commit.- Uncommitted pull messages are redelivered.
unsubscribereleases a blocked publisher. Catches a missingnotifyAll.- A handler can publish without deadlocking. Catches handlers run under the lock.
- Shutdown drains, then refuses publishes.
"""Run with: python -m unittest test_broker -v"""
import threading
import time
import unittest
from broker import BackPressureError, Broker, BrokerError, Overflow, SubscriptionOptions, wait_until
FAST = SubscriptionOptions(max_attempts=3, backoff_s=0.001)
class BrokerTest(unittest.TestCase):
def setUp(self) -> None:
self.broker = Broker(workers=4)
self.broker.create_topic("t", partitions=3)
def tearDown(self) -> None:
self.broker.shutdown(timeout_s=1)
def pull(self, name: str, max_lag: int, overflow: Overflow):
return self.broker.subscribe("t", name, opts=SubscriptionOptions(max_lag=max_lag, overflow=overflow))
def test_same_key_same_partition_in_publish_order(self):
got = []
self.broker.subscribe("t", "s", got.append)
for i in range(50):
self.broker.publish("t", i, key="k")
wait_until(lambda: len(got) == 50)
self.assertEqual([m.payload for m in got], list(range(50)))
self.assertEqual(len({m.partition for m in got}), 1)
def test_every_subscription_gets_every_message(self):
a, b = [], []
self.broker.subscribe("t", "a", a.append)
self.broker.subscribe("t", "b", b.append)
for i in range(10):
self.broker.publish("t", i)
wait_until(lambda: len(a) == 10 and len(b) == 10)
def test_late_subscriber_starts_at_the_end(self):
self.broker.publish("t", "old", key="k")
late = self.pull("late", 10, Overflow.BLOCK)
self.assertEqual(self.broker.poll(late), [])
def test_retry_then_success_is_not_dead_lettered(self):
calls = []
def flaky(m):
calls.append(m)
if len(calls) < 3:
raise RuntimeError("timeout")
sub = self.broker.subscribe("t", "s", flaky, FAST)
self.broker.publish("t", "x")
wait_until(lambda: len(calls) == 3)
self.assertEqual(sub.dead_lettered, 0)
def test_poison_message_is_dead_lettered_and_does_not_block_the_partition(self):
seen = []
def handler(m):
if m.payload == "poison":
raise ValueError("bad payload")
seen.append(m.payload)
dlq = self.broker.subscribe("t.dlq", "ops", from_beginning=True)
self.broker.subscribe("t", "s", handler, FAST)
for payload in ["a", "poison", "b"]:
self.broker.publish("t", payload, key="k")
wait_until(lambda: seen == ["a", "b"])
[dead] = self.broker.poll(dlq)
self.assertEqual(dead.payload, "poison")
self.assertEqual(dead.headers["dlq.attempts"], "3")
self.assertEqual(dead.headers["dlq.error"], "bad payload")
def test_reject_raises_and_changes_nothing(self):
sub = self.pull("s", 1, Overflow.REJECT)
self.broker.publish("t", "x", key="k")
with self.assertRaises(BackPressureError):
self.broker.publish("t", "y", key="k")
self.assertEqual([m.payload for m in self.broker.poll(sub)], ["x"])
def test_drop_oldest_keeps_the_newest(self):
sub = self.pull("s", 2, Overflow.DROP_OLDEST)
for i in range(6):
self.broker.publish("t", i, key="k")
self.assertEqual([m.payload for m in self.broker.poll(sub)], [4, 5])
self.assertEqual(sub.dropped, 4)
def test_block_times_out_then_succeeds_after_commit(self):
sub = self.pull("s", 1, Overflow.BLOCK)
self.broker.publish("t", "x", key="k")
with self.assertRaises(BackPressureError):
self.broker.publish("t", "y", key="k", timeout_s=0.02)
threading.Timer(0.03, lambda: self.broker.commit(sub, self.broker.poll(sub)[0])).start()
start = time.monotonic()
self.broker.publish("t", "z", key="k", timeout_s=2)
self.assertLess(time.monotonic() - start, 1.0)
def test_uncommitted_pull_messages_are_redelivered(self):
sub = self.pull("s", 10, Overflow.BLOCK)
self.broker.publish("t", "x", key="k")
first = self.broker.poll(sub)
self.assertEqual(first, self.broker.poll(sub))
self.broker.commit(sub, first[0])
self.assertEqual(self.broker.poll(sub), [])
def test_unsubscribe_releases_a_blocked_publisher(self):
slow = self.pull("slow", 1, Overflow.BLOCK)
self.broker.publish("t", 1, key="k")
threading.Timer(0.03, lambda: self.broker.unsubscribe(slow)).start()
self.broker.publish("t", 2, key="k", timeout_s=2) # would time out without notify_all
def test_handler_can_publish_without_deadlock(self):
self.broker.create_topic("audit")
out = []
self.broker.subscribe("audit", "sink", lambda m: out.append(m.payload))
self.broker.subscribe("t", "relay", lambda m: self.broker.publish("audit", m.payload))
self.broker.publish("t", "x")
wait_until(lambda: out == ["x"])
def test_shutdown_drains_then_refuses_publishes(self):
got = []
self.broker.subscribe("t", "s", lambda m: (time.sleep(0.01), got.append(m)))
for i in range(5):
self.broker.publish("t", i, key="k")
self.assertTrue(self.broker.shutdown(timeout_s=2))
self.assertEqual(len(got), 5)
with self.assertRaises(BrokerError):
self.broker.publish("t", "late")
if __name__ == "__main__":
unittest.main()
For stress testing, the main functions above already run two publishers against four partitions and check that offsets arrive strictly increasing per partition. Run that a few hundred times in a loop in CI, ideally with more threads than cores. For Java, jcstress is the serious tool when you need to prove a lock-free piece correct. For a lock-based broker like this one, repeated runs plus assertions on the invariants catch most mistakes.
10. Common mistakes
- Calling handlers while holding the broker lock. It looks tidy and it's the single most common bug. One slow handler stalls every publisher, and a handler that publishes deadlocks. Copy what you need under the lock, release it, then call out.
- A thread per subscriber, or a thread per message. The first doesn't scale past a few hundred subscribers. The second destroys ordering, because two threads may run two messages from the same partition at once. Use a bounded pool plus one logical lane per (subscription, partition).
- Unbounded queues. "Just use a
LinkedBlockingQueue" with no capacity is an out-of-memory error with extra steps. Every buffer needs a bound and a policy for when it's full. - Global ordering as a requirement. Total order across a topic forces one lane, which forces one worker. Ask whether ordering per key is enough. It almost always is.
- Acking before processing. Moving the cursor before the handler runs turns every crash into silent message loss. At-least-once plus idempotent handlers is the honest default.
- Retrying forever. One poison message then blocks its partition permanently, and everything behind it piles up until back-pressure stalls the publishers. Cap the attempts and dead-letter.
- Retrying without backoff. A tight retry loop hammers whatever is failing, often the very dependency that's overloaded. Backoff, ideally with jitter, gives it room to recover. See timeouts, retries and backoff.
- Swallowing handler exceptions silently. Catching and ignoring means failures vanish. Count them, dead-letter them with the error text, and make the DLQ observable.
- Using
hash()in Python, or identity hash codes, for partitioning. Python randomises string hashes per process, so the same key could land on different partitions after a restart. Use a stable hash such as CRC32 or FNV-1a. - Calling it the Observer pattern and stopping there. The interviewer wants to hear about the buffer, the threads and the failure isolation. Those are exactly what Observer lacks.
notifyinstead ofnotifyAllwith waiters that wait for different things. See the concurrency section.- No shutdown story. Without one, messages in flight vanish on exit, and the tests leak threads into each other.
11. Interview follow-ups
"Is delivery at-most-once, at-least-once or exactly-once?" At-least-once. The cursor moves only after the handler returns, so a crash or a failure leads to redelivery. Exactly-once isn't something the broker can provide on its own. It needs the handler's side effects and the cursor update to commit atomically, for example by storing the processed offset in the same database transaction as the result. In practice you get "effectively once" with idempotent handlers. Exactly-once semantics goes deeper.
"Why partitions at all? Why not one queue per topic?" Because ordering and parallelism pull against each other. One queue gives total order but only one message in flight per subscriber. Partitions give order per key and up to N messages in flight per subscriber, one per partition. Most business ordering is per entity (per order, per account), so per-key order is what's actually needed.
"What happens if I add partitions to an existing topic?"
hash(key) % N changes for most keys, so a key's new messages may land on a different partition than its old ones, and a subscriber could process them out of order during the transition. Real systems either forbid changing the count, accept the reordering window, or use consistent hashing to move fewer keys. Our broker fixes the count at creation, which is the honest answer for an LLD round.
"Push or pull: which would you choose?" Push gives the lowest latency and a simple programming model, but the broker decides the pace, so push needs back-pressure on the broker side. Pull lets the consumer decide its own pace and batch size, which makes it naturally back-pressured, at the cost of polling latency and a more complex consumer. Kafka is pull-based. RabbitMQ is push-based, with prefetch limits as back-pressure. Our broker offers both over the same log, which is a nice way to show that the storage model doesn't depend on the delivery model.
"How do you choose between BLOCK, REJECT and DROP_OLDEST?"
By asking what losing a message costs. Payments and orders can never be dropped, so use BLOCK (with a timeout that surfaces as an error) or REJECT (and let the caller retry or shed load at the edge). Telemetry, prices and presence updates lose value as they age, so dropping the oldest keeps the subscriber current. Backpressure patterns lists more options, such as sampling and conflation.
"Why is the DLQ per topic rather than per subscription?"
Either works. Per topic with a dlq.subscription header keeps the number of topics small, and one operator view covers everything. Per subscription isolates teams better, because one team's failures don't mix with another's. If the interviewer cares about ownership, switch to per-subscription naming. It's a one-line change in deadLetter. Dead-letter queues discusses replay strategies.
"How would you make it durable?" Make the partition log an append-only file with fsync policy (every write, every N ms, or never), and store each subscription's committed offsets in a small file or the same log. On restart, rebuild cursors from the offsets file. That's an HLD conversation, and Kafka's design (Kafka internals) is the canonical reference.
"How do I test that ordering holds under concurrency?" Record (partition, offset) in the handler and assert that offsets are strictly increasing per partition after many concurrent publishes. Run it repeatedly. Don't assert on wall-clock timing, and don't use fixed sleeps. Wait for a condition with a deadline.
"What's the memory bound?"
For each partition, the log holds end - min(cursor) messages. Each subscription's lag is at most maxLag under REJECT and DROP_OLDEST, and also under BLOCK, because publishers wait at that point. So the bound is partitions × max(maxLag) per topic, plus the dead-letter topic, which retains everything. In production you'd cap the DLQ too, or age it out.
"Where does this differ from Redis Pub/Sub?" Redis Pub/Sub is closer to fire-and-forget fan-out with no retention. A subscriber that's disconnected misses messages, and there are no acks. Redis Streams adds a log, consumer groups and acks, which makes it much closer to this design. See Redis Pub/Sub patterns.
Related
- Design a Task Scheduler builds the delayed-retry executor this broker would use.
- Design a Notification Service is a typical consumer of a broker like this.
- Concurrency Patterns in LLD covers producer-consumer and worker pools in general.
- Ordering guarantees and Backpressure in stream processing cover the distributed versions of these ideas.