Design an In-Memory Message Queue
Topics, producers, consumers, offsets, and delivery guarantees — Kafka's object model in miniature.
Problem Statement
Design an in-memory message queue / pub-sub broker where producers publish messages to named topics and subscribers consume each topic independently. Every subscriber tracks its own offset, so one slow consumer never moves or blocks another consumer's progress.
The design must support publish, subscribe, per-subscriber acknowledgement, redelivery of unacknowledged messages, and safe concurrent access from many producer and subscriber threads. The core learning goal is the Observer-style fan-out model plus offset tracking per subscriber.
Business context
Message queues and pub-sub brokers sit between services that produce events and services that react to them: order created, payment captured, email sent, index document, refresh cache. They decouple availability and throughput, but they also introduce delivery semantics that a candidate must state clearly.
For LLD interviews, this problem tests whether you can model a topic log, consumer offsets, acknowledgement, duplicate-safe at-least-once delivery, and thread-safety without jumping straight to a distributed Kafka clone.
Functional Requirements
Create or reuse named topics on demand.
Allow producers to publish payloads to a topic and receive the assigned message offset.
Allow many subscribers to subscribe to the same topic.
Fan out every topic message to every subscriber registered on that topic.
Track an independent next offset for each subscriber, per topic.
Advance a subscriber's offset only when that subscriber acknowledges the message.
Redeliver an unacknowledged message to the same subscriber without losing ordering.
Make publish, subscribe, acknowledgement, offset inspection, and redelivery safe under concurrent access.
Non-Functional Requirements
Thread-safe correctness
The topic log, subscriber map, in-flight flag, and offsets are shared mutable state. Mutations must be protected so two publishers cannot assign the same offset and two acknowledgements cannot corrupt progress.
Per-subscriber ordering
A subscriber should observe messages in topic offset order. If offset 5 is unacknowledged, offset 6 waits for that subscriber even if other subscribers move ahead.
At-least-once delivery
The broker may deliver a message more than once, but it must not mark the message consumed for a subscriber until the subscriber explicitly acknowledges it.
In-memory simplicity
The base design stores topic logs and offsets in process memory. Durability, replay after restart, and cross-node replication are production extensions.
Extensible retry policy
Delivery and redelivery decisions should sit behind a strategy so fixed retry, backoff, and dead-letter behavior can be added without rewriting topic state management.
Requirement Clarification
QIs this a work queue where one consumer gets a message, or pub-sub where every subscriber gets it?
Use pub-sub for the base problem: every subscriber registered to a topic should receive every message, each at its own offset.
QDo we need durable storage or recovery after process restart?
No. Keep the implementation in memory. We still design clean seams where a durable append-only log and offset repository could replace the in-memory collections.
QWhat does acknowledgement mean?
Acknowledgement is subscriber-specific. When subscriber billing acknowledges offset 10, only billing's next offset advances to 11; other subscribers are unaffected.
QCan duplicates happen?
Yes. At-least-once delivery means a subscriber may see the same message again if it processed the message but crashed before acknowledging. Consumers should be idempotent.
QShould delivery be synchronous or asynchronous?
The reference implementation invokes subscriber callbacks synchronously to keep the LLD focused. A production broker would place delivery work on executors and use timers for retry.
UML Class Diagram
Sequence Diagram
Entity Identification
Broker
Singleton facade and topic registry. It exposes publish, subscribe, redelivery, and offset inspection while delegating topic-level state to Topic objects.
Topic
Owns the ordered message log for one topic and all subscriptions on that topic. It assigns offsets, snapshots deliveries, records in-flight messages, and applies acknowledgements.
Message
Immutable event stored in a topic log. The offset is assigned by the topic and becomes the ordering and acknowledgement handle for subscribers.
Subscriber
Observer callback interface. A subscriber receives a topic name, a message, and an acknowledgement function it must call only after successful processing.
Subscription
Topic-owned per-subscriber state: subscriber identity, next offset to deliver, whether that offset is in flight, and delivery attempts for redelivery policy.
DeliveryStrategy
Policy seam for whether a delivery attempt should happen. The default always allows redelivery for at-least-once behavior; later strategies can add backoff or dead letters.
Producer
Small client wrapper that publishes payloads through the broker. It keeps producer code independent from topic lookup and fan-out details.
Design Patterns Used
Subscribers register interest in a topic and are notified when the topic has a message for their offset. The topic is the subject; each Subscriber is an observer with its own cursor and acknowledgement callback.
Producers append work to topics while subscribers consume it later through callbacks. The broker decouples production from consumption and supports slow consumers through independent offsets.
Broker.getInstance provides one in-memory topic registry for the process. In real systems this would usually be dependency-injected, but Singleton is useful here to make the shared broker boundary explicit.
DeliveryStrategy isolates the redelivery decision from topic bookkeeping. Retry limits, exponential backoff, and dead-letter routing become new strategy implementations rather than edits to Topic.
Step-by-Step Design
1Represent a topic as an ordered log
Publishing appends an immutable Message to a topic. The array index becomes the message offset, and subscribers acknowledge that offset when processing succeeds.
public final class Message { private final long offset; private final String payload; Message(long offset, String payload) { this.offset = offset; this.payload = payload; } }2Track offsets per subscriber, not per topic
A pub-sub broker cannot keep one global consumed offset. Each subscriber needs a Subscription record with its own next offset, in-flight flag, and attempt counts.
private static final class Subscription { final String subscriberId; final Subscriber subscriber; long nextOffset; boolean inFlight; final Map<Long, Integer> attempts = new HashMap<>(); }3Advance only after acknowledgement
Delivery passes a callback to the subscriber. The callback is idempotent for old offsets and advances only when the acknowledged offset equals that subscriber's current next offset.
private void acknowledge(String subscriberId, long offset) { Subscription subscription = subscriptions.get(subscriberId); if (subscription != null && subscription.nextOffset == offset) { subscription.nextOffset++; subscription.inFlight = false; } }4Guard shared state inside Topic
Topic protects the message list and subscription map with synchronized blocks. It snapshots delivery work under the lock, then invokes subscriber callbacks outside the lock so user code cannot freeze the broker.
5Use a thread-safe singleton broker registry
Broker keeps topics in a ConcurrentHashMap and creates missing topics atomically with computeIfAbsent. Topic-level correctness remains inside each Topic.
private Topic topic(String topicName) { return topics.computeIfAbsent( topicName, name -> new Topic(name, deliveryStrategy) ); }6Make redelivery policy pluggable
The default strategy always permits another attempt, which gives at-least-once delivery. Production strategies can add maximum attempts, delay, jitter, or dead-letter routing.
Complete Java Implementation
Explanation of Every Class
Message
Immutable value object for one log entry. Topic assigns the offset, records the payload, and timestamps publication so subscribers can reason about order and age.
Subscriber
Observer interface. Implementations return a stable id and process messages through onMessage. They call the supplied acknowledgement function only after successful work.
DeliveryStrategy
Strategy interface for delivery attempts. The bundled AlwaysRedeliverStrategy returns true for every attempt, which implements at-least-once semantics for the in-memory broker.
Topic
Core aggregate. It stores the ordered message list, per-subscriber Subscription state, and delivery attempt counts. It synchronizes shared state, snapshots deliveries, and invokes callbacks outside the lock.
Broker
Singleton facade over a thread-safe topic registry. It creates topics atomically and routes publish, subscribe, redelivery, and offset inspection calls to the right Topic.
Producer
Client-side helper that depends only on Broker. It keeps producer code small and makes the producer role explicit in the Producer-Consumer pattern.
Main
Demonstrates two subscribers on the same topic. audit acknowledges immediately; billing skips its first acknowledgement, then receives the same offset again during redelivery.
Dry Run
Sample input
Topic orders with subscribers audit and billing. audit acknowledges immediately. billing fails before acknowledging the first delivery, then succeeds on redelivery.
| Step | Action | audit next offset | billing next offset | Result |
|---|---|---|---|---|
| 1 | subscribe audit and billing | 0 | 0 | Both subscribers start at offset 0. |
| 2 | publish M0 | 1 | 0 | audit acks M0; billing receives M0 but does not ack. |
| 3 | redeliver unacked | 1 | 1 | billing receives M0 again and acknowledges it. |
| 4 | publish M1 | 2 | 2 | Both subscribers receive and ack the next message. |
| 5 | inspect offsets | 2 | 2 | Offsets show each subscriber's next message to read. |
The key observation is that audit and billing move independently. billing stays at offset 0 until its own acknowledgement, so the broker safely redelivers M0 without rewinding audit.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| publish | O(S) | O(1) plus message storage | Appending is O(1); collecting immediate deliveries scans S subscribers for the topic. |
| subscribe | O(S) after registration | O(1) | Registration is O(1) average; the implementation then scans subscribers to deliver any available message. |
| acknowledge | O(S) | O(1) | Updating one subscriber is O(1); triggering the next delivery scans subscribers in this simple design. |
| redeliverUnacked | O(S) | O(S) | The topic scans subscribers and builds a delivery snapshot for those with in-flight messages. |
| offsets | O(S) | O(S) | Returns a snapshot of each subscriber's next offset. |
S is the number of subscribers on a topic. Message storage is O(M) per topic, where M is the number of retained messages. A production broker would add retention windows, partitioning, async dispatch queues, and more granular locks.
Extensibility
Durable topic log
Replace the in-memory messages list with an append-only file, database table, or replicated log. Offsets can be restored from a SubscriptionRepository on restart.
Consumer groups
Add a group id to Subscription and assign each message partition to one member of a group while still fanning out across different groups.
Retry and dead-letter policy
Implement new DeliveryStrategy classes for maximum attempts, exponential backoff, jitter, and routing exhausted messages to a dead-letter topic.
Asynchronous delivery
Move callback invocation to an executor per topic or per subscriber. The topic state machine stays the same, but delivery snapshots become tasks.
Filtering and routing
Add subscription predicates so a subscriber receives only matching messages, or add routing keys that map producers to topics without changing acknowledgement semantics.
Alternative Designs
Competing-consumer work queue
Store one queue per topic and let each message be claimed by exactly one consumer. This is useful for background jobs where work should not be duplicated.
Tradeoffs
Simpler offset state, but it is not pub-sub. Multiple downstream systems cannot independently replay every event.
Per-subscriber physical queues
On publish, copy the message reference into each subscriber's queue. Each subscriber then consumes from its own simple queue.
Tradeoffs
Delivery is easy and slow subscribers are isolated, but subscribe and publish need more memory and fan-out bookkeeping.
Partitioned append-only log
Hash messages into partitions and track offsets per subscriber per partition, similar to large-scale brokers.
Tradeoffs
Higher throughput and parallelism, but ordering is only guaranteed within a partition and the LLD becomes significantly larger.
Common Mistakes
- ×
Using one global consumed offset for the whole topic, which breaks pub-sub because one subscriber's acknowledgement hides messages from others.
- ×
Advancing the offset before the subscriber finishes processing, which silently loses messages on failure.
- ×
Claiming exactly-once delivery from an in-memory callback design. At-least-once permits duplicates and requires idempotent consumers.
- ×
Invoking arbitrary subscriber code while holding the topic lock, causing deadlocks or blocking all producers behind one slow consumer.
- ×
Using unsynchronized ArrayList and HashMap mutations from multiple threads without a clear lock boundary.
- ×
Forgetting to define the starting offset for a new subscriber: beginning of log, latest offset, or a caller-provided replay point.
- ×
Letting a failed subscriber receive later offsets before it acknowledges the current one, which breaks per-subscriber ordering.
Follow-up Interview Questions
QHow would you add consumer groups?
Introduce groupId and partitions. A message is delivered once within a group but once per group overall. Offsets become keyed by topic, partition, group, and subscriber assignment.
QHow do you prevent a slow subscriber from keeping messages forever?
Add retention and backpressure policies: max retained messages, max subscriber lag, pause producers, drop or dead-letter for specific subscribers, and alert on lag.
QCan this design provide exactly-once delivery?
Not by itself. Exactly-once needs coordinated durable offset commits plus idempotent or transactional consumers. In interviews, state that this design is intentionally at-least-once.
QWhere would retries be scheduled?
A retry scheduler or executor would periodically ask each topic for eligible in-flight messages, using DeliveryStrategy to decide delay and maximum attempts.
QHow would you scale beyond one process?
Persist the log, partition topics, elect partition leaders, replicate messages, store offsets durably, and route producers and subscribers through a cluster-aware broker facade.
Production Considerations
Durability and recovery
Persist messages before acknowledging publish success, and persist subscriber offsets after processing. On restart, rebuild topic state from the log and offset store.
Retry, timeout, and dead letters
An in-flight message needs a timeout. Repeated failures should move to a dead-letter topic with error metadata so poison messages do not block the subscriber forever.
Backpressure and retention
Bound memory by topic retention, max message size, max subscriber lag, and producer throttling. Without bounds, one offline subscriber can grow the in-memory log indefinitely.
Observability
Track publish rate, delivery rate, acknowledgement latency, subscriber lag, redelivery count, in-flight count, and dead-letter count per topic and subscriber.
Security and tenancy
Authorize publish and subscribe per topic, isolate tenants with quotas, and validate payload size before accepting messages into memory.
What Interviewers Look For
Did you explicitly choose pub-sub fan-out rather than competing consumers?
Did you track offsets per subscriber and advance them only after acknowledgement?
Did you call out at-least-once duplicates and the need for idempotent consumers?
Did you make the broker and topic state thread-safe without overcomplicating the model?
Did you avoid mixing retry policy with core topic state by using a strategy seam?
Quiz
0/5 answered
1.Why does each subscriber need its own offset?
2.When should a subscriber's offset advance?
3.What does at-least-once delivery imply?
4.Which state must be protected for thread safety inside a topic?
5.Which pattern best describes subscribers registering with a topic and being notified of messages?
Practice Variants
Add consumer groups
AdvancedExtend subscriptions with a group id so each message is delivered once per group, not once per subscriber, while preserving pub-sub across groups.
Add retry backoff and dead letters
IntermediateImplement a DeliveryStrategy that delays redelivery, stops after N attempts, and publishes exhausted messages to a dead-letter topic.
Add durable replay
AdvancedPersist messages and offsets so subscribers can restart and continue from their last acknowledged offset.
Flashcards
Cheat Sheet
Entities: Broker, Topic, Message, Subscriber, Subscription, DeliveryStrategy, Producer.
Core invariant: each topic has one ordered log; each subscriber has its own next offset into that log.
Publish: append message at next offset, snapshot eligible subscribers, notify them outside the lock.
Ack: if ack offset equals the subscriber's next offset, advance it and clear in-flight state.
Delivery: at-least-once means unacknowledged messages are redelivered; duplicates are possible and consumers should be idempotent.
Thread safety: broker uses a concurrent topic registry; topic protects log and subscription state with synchronization.
Patterns: Observer, Producer-Consumer, Singleton, Strategy.
References
- BookEnterprise Integration Patterns — Gregor Hohpe and Bobby Woolf
- BookDesigning Data-Intensive Applications — Martin Kleppmann
- DocsApache Kafka Documentation