vishal maurya

LLD Series: Notification Service (Low-Level Design)

Overview

Part of the Interview Prep series. Dotted-underline words are glossary terms: hover for the meaning or open the Glossary. Track your progress on the Interview Prep tracker. Series index: Start here.

1. Problem statement and how it is asked

Prompt: "Design a notification service that can send Email, SMS and Push notifications using templates, honours priority (OTP before promos), retries on failure, and can easily add new channels."

Asked at: PayU, Amex, Visa and Mastercard (OTP / transaction alerts / fraud alerts), NPCI-ecosystem apps (UPI collect and debit alerts). Interviewers watch for: Strategy per channel, Observer for delivery status, priority and retry handled sanely, and no blocking of the caller.

2. Requirements clarification

Functional

  • Send to a user over EMAIL / SMS / PUSH, using a named template with {{placeholders}}.
  • Priority: HIGH (OTP, fraud) is served before MEDIUM before LOW (promos).
  • Retry transient failures with exponential backoff; after N attempts, dead-letter.
  • Respect per-user channel opt-out.
  • Idempotency: same idempotencyKey submitted twice is sent once.
  • Observers get SENT / RETRY / FAILED / SKIPPED events.

Non-functional: submit is non-blocking (async), thread-safe, new channel = new class only, one slow channel must not block others (production: separate queue/pool per channel).

Assumptions / out of scope: vendor SDKs are simulated; no real persistence; no rate limiting per user, scheduling for future time, or localisation (all mentioned in follow-ups).

3. Entities and class diagram

 +------------------+  submit()   +-----------------------------+   uses   +----------------+
 |  Client / API    |------------>|     NotificationService     |--------->| TemplateEngine |
 +------------------+             |-PriorityBlockingQueue<Notif>|          +----------------+
                                  |-Set<String> seenKeys        |   uses   +----------------+
                                  |-workers, retryScheduler     |--------->| UserPreferences|
                                  +--+---------+----------+-----+          +----------------+
                                     |         |          | notifies
                          1..* by    |         | uses     v
                           channel   |         v      <<interface>>
                                     v   <<interface>>  DeliveryListener (Observer)
                          <<interface>>   RetryPolicy    onSuccess/onRetry/onFailed/onSkipped
                       NotificationSender  (exponential)
                          ^    ^    ^
                          |    |    |
                  EmailSender SmsSender PushSender   (here: SimulatedSender)

 Notification(idempotencyKey,userId,Channel,templateId,params,Priority,attempts) implements Comparable

4. Design patterns and why

PatternWhereWhy / rejected alternative
Strategy (+Adapter)NotificationSender per channelAdding a channel = a new class. Rejected: switch(channel) in service (violates OCP).
ObserverDeliveryListenerMetrics, audit, webhooks decoupled from sending. Rejected: service writing to DB/log directly.
StrategyRetryPolicySwap fixed / exponential / jitter without touching the worker.
Template method-liteTemplateEngine.renderContent separated from channel and request.
Producer-consumerPriority queue and workersCaller returns immediately; priority ordering is the queue's compareTo.
Factory (optional)SenderRegistryMention if senders created from config.

Rejected: one thread per notification (unbounded), Thread.sleep in worker for backoff (starves workers; we use a scheduler that re-enqueues).

5. Code

All files below are in the default package, Java 11+. Compiled with javac *.java, run with java Main.

Models and enums

Channel.java

public enum Channel { EMAIL, SMS, PUSH }

Priority.java

/** Lower rank = served first. */
public enum Priority {
    HIGH(0), MEDIUM(1), LOW(2);
    final int rank;
    Priority(int rank) { this.rank = rank; }
}

Notification.java

import java.util.Map;
import java.util.concurrent.atomic.AtomicLong;

/** Immutable request, except attempt counter which is only touched by the one worker owning it. */
public final class Notification implements Comparable<Notification> {
    private static final AtomicLong SEQ = new AtomicLong();
    private final long seq = SEQ.incrementAndGet();      // FIFO tie-break inside a priority
    private final String idempotencyKey;
    private final String userId;
    private final Channel channel;
    private final String templateId;
    private final Map<String, String> params;
    private final Priority priority;
    private int attempts;

    public Notification(String idempotencyKey, String userId, Channel channel,
                        String templateId, Map<String, String> params, Priority priority) {
        this.idempotencyKey = idempotencyKey; this.userId = userId; this.channel = channel;
        this.templateId = templateId; this.params = Map.copyOf(params); this.priority = priority;
    }
    public String idempotencyKey() { return idempotencyKey; }
    public String userId() { return userId; }
    public Channel channel() { return channel; }
    public String templateId() { return templateId; }
    public Map<String, String> params() { return params; }
    public Priority priority() { return priority; }
    public int attempts() { return attempts; }
    public int incrementAttempts() { return ++attempts; }

    @Override public int compareTo(Notification o) {
        int c = Integer.compare(priority.rank, o.priority.rank);
        return c != 0 ? c : Long.compare(seq, o.seq);
    }
    @Override public String toString() { return idempotencyKey + "[" + channel + "/" + priority + "]"; }
}

Interfaces

NotificationSender.java

/** Strategy: one implementation per channel (adapter over a vendor SDK). */
public interface NotificationSender {
    Channel channel();
    /** @throws TransientDeliveryException for retryable failures */
    void send(String userId, String body) throws TransientDeliveryException;
}

TransientDeliveryException.java

public class TransientDeliveryException extends Exception {
    public TransientDeliveryException(String m) { super(m); }
}

DeliveryListener.java

/** Observer for delivery lifecycle (metrics, audit log, webhooks). */
public interface DeliveryListener {
    void onSuccess(Notification n, String body);
    void onRetry(Notification n, int attempt, long delayMs, String reason);
    void onFailed(Notification n, String reason);   // dead-letter
    void onSkipped(Notification n, String reason);  // opt-out / duplicate
}

RetryPolicy.java

public interface RetryPolicy {
    boolean shouldRetry(int attemptsSoFar);
    long delayMs(int attemptsSoFar);

    static RetryPolicy exponential(int maxAttempts, long baseMs) {
        return new RetryPolicy() {
            public boolean shouldRetry(int a) { return a < maxAttempts; }
            public long delayMs(int a) { return baseMs * (1L << (a - 1)); }
        };
    }
}

Supporting services

TemplateEngine.java

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class TemplateEngine {
    private final Map<String, String> templates = new ConcurrentHashMap<>();
    public void register(String id, String body) { templates.put(id, body); }
    /** Replaces {{key}} placeholders; unknown template is a permanent (non-retryable) error. */
    public String render(String id, Map<String, String> params) {
        String t = templates.get(id);
        if (t == null) throw new IllegalArgumentException("Unknown template " + id);
        for (Map.Entry<String, String> e : params.entrySet())
            t = t.replace("{{" + e.getKey() + "}}", e.getValue());
        return t;
    }
}

UserPreferences.java

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

public class UserPreferences {
    private final Map<String, Set<Channel>> optOut = new ConcurrentHashMap<>();
    public void optOut(String userId, Channel c) {
        optOut.computeIfAbsent(userId, k -> ConcurrentHashMap.newKeySet()).add(c);
    }
    public boolean allows(String userId, Channel c) {
        return !optOut.getOrDefault(userId, Set.of()).contains(c);
    }
}

SimulatedSender.java

import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

/** Fake vendor: fails the first N calls per user to demo retry. */
public class SimulatedSender implements NotificationSender {
    private final Channel channel;
    private final int failFirst;
    private final Map<String, AtomicInteger> calls = new ConcurrentHashMap<>();
    public SimulatedSender(Channel channel, int failFirst) { this.channel = channel; this.failFirst = failFirst; }
    @Override public Channel channel() { return channel; }
    @Override public void send(String userId, String body) throws TransientDeliveryException {
        int n = calls.computeIfAbsent(userId, k -> new AtomicInteger()).incrementAndGet();
        if (n <= failFirst) throw new TransientDeliveryException(channel + " vendor timeout #" + n);
    }
}

Core service

NotificationService.java

import java.util.*;
import java.util.concurrent.*;

public class NotificationService {
    private final PriorityBlockingQueue<Notification> queue = new PriorityBlockingQueue<>();
    private final Map<Channel, NotificationSender> senders = new EnumMap<>(Channel.class);
    private final TemplateEngine templates;
    private final UserPreferences prefs;
    private final RetryPolicy retryPolicy;
    private final List<DeliveryListener> listeners = new CopyOnWriteArrayList<>();
    private final Set<String> seenKeys = ConcurrentHashMap.newKeySet();   // idempotency
    private final ExecutorService workers;
    private final ScheduledExecutorService retryScheduler = Executors.newSingleThreadScheduledExecutor(r -> {
        Thread t = new Thread(r, "retry-scheduler"); t.setDaemon(true); return t; });
    private volatile boolean running = true;
    private final java.util.concurrent.atomic.AtomicInteger inFlight = new java.util.concurrent.atomic.AtomicInteger();

    public NotificationService(TemplateEngine t, UserPreferences p, RetryPolicy r,
                               List<NotificationSender> senderList, int workerCount) {
        this.templates = t; this.prefs = p; this.retryPolicy = r;
        senderList.forEach(s -> senders.put(s.channel(), s));
        workers = Executors.newFixedThreadPool(workerCount, run -> {
            Thread th = new Thread(run, "notif-worker"); th.setDaemon(true); return th; });
        for (int i = 0; i < workerCount; i++) workers.submit(this::workLoop);
    }

    public void addListener(DeliveryListener l) { listeners.add(l); }

    public boolean submit(Notification n) {
        if (!seenKeys.add(n.idempotencyKey())) { listeners.forEach(l -> l.onSkipped(n, "duplicate")); return false; }
        inFlight.incrementAndGet();
        queue.put(n);
        return true;
    }

    private void workLoop() {
        while (running) {
            try { process(queue.take()); }
            catch (InterruptedException e) { return; }
        }
    }

    private void process(Notification n) {
        try {
            if (!prefs.allows(n.userId(), n.channel())) {
                listeners.forEach(l -> l.onSkipped(n, "user opted out")); done(); return;
            }
            String body;
            try { body = templates.render(n.templateId(), n.params()); }
            catch (IllegalArgumentException e) { listeners.forEach(l -> l.onFailed(n, e.getMessage())); done(); return; }
            int attempt = n.incrementAttempts();
            try {
                senders.get(n.channel()).send(n.userId(), body);
                listeners.forEach(l -> l.onSuccess(n, body)); done();
            } catch (TransientDeliveryException e) {
                if (retryPolicy.shouldRetry(attempt)) {
                    long d = retryPolicy.delayMs(attempt);
                    listeners.forEach(l -> l.onRetry(n, attempt, d, e.getMessage()));
                    retryScheduler.schedule(() -> queue.put(n), d, TimeUnit.MILLISECONDS); // still in flight
                } else {
                    listeners.forEach(l -> l.onFailed(n, "retries exhausted: " + e.getMessage())); done();
                }
            }
        } catch (RuntimeException e) {                // never let a worker die
            listeners.forEach(l -> l.onFailed(n, "unexpected: " + e)); done();
        }
    }
    private void done() { inFlight.decrementAndGet(); }

    /** For demo/tests: wait until everything submitted reached a terminal state. */
    public void awaitIdle(long timeoutMs) throws InterruptedException {
        long end = System.currentTimeMillis() + timeoutMs;
        while (inFlight.get() > 0 && System.currentTimeMillis() < end) Thread.sleep(20);
    }
    public void shutdown() { running = false; workers.shutdownNow(); retryScheduler.shutdownNow(); }
}

Lock granularity: no explicit locks. PriorityBlockingQueue (internal lock, O(log n)), ConcurrentHashMap-backed sets for idempotency and opt-out, CopyOnWriteArrayList for listeners (reads far outnumber writes). Notification.attempts is mutated only by the single worker holding the item (hand-off through the queue gives happens-before), so it needs no sync.

Demo

Main.java

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        TemplateEngine te = new TemplateEngine();
        te.register("OTP", "Your OTP is {{otp}}. Valid 5 min.");
        te.register("PROMO", "Hi {{name}}, 20% off today!");
        UserPreferences prefs = new UserPreferences();
        prefs.optOut("u3", Channel.SMS);

        // 1 worker so priority ordering is observable; SMS fails first 2 calls per user
        NotificationService svc = new NotificationService(te, prefs, RetryPolicy.exponential(3, 50),
            List.of(new SimulatedSender(Channel.EMAIL, 0), new SimulatedSender(Channel.SMS, 2),
                    new SimulatedSender(Channel.PUSH, 99)), 1);
        svc.addListener(new DeliveryListener() {
            public void onSuccess(Notification n, String b) { System.out.println("SENT    " + n + " -> \"" + b + "\""); }
            public void onRetry(Notification n, int a, long d, String r) { System.out.println("RETRY   " + n + " attempt=" + a + " in " + d + "ms (" + r + ")"); }
            public void onFailed(Notification n, String r) { System.out.println("FAILED  " + n + " : " + r); }
            public void onSkipped(Notification n, String r) { System.out.println("SKIPPED " + n + " : " + r); }
        });

        // queue them before the single worker can drain: submit from main quickly
        svc.submit(new Notification("n1", "u1", Channel.EMAIL, "PROMO", Map.of("name", "Asha"), Priority.LOW));
        svc.submit(new Notification("n2", "u1", Channel.SMS, "OTP", Map.of("otp", "482913"), Priority.HIGH));
        svc.submit(new Notification("n2", "u1", Channel.SMS, "OTP", Map.of("otp", "482913"), Priority.HIGH)); // dup
        svc.submit(new Notification("n3", "u3", Channel.SMS, "OTP", Map.of("otp", "111"), Priority.HIGH));    // opted out
        svc.submit(new Notification("n4", "u2", Channel.PUSH, "PROMO", Map.of("name", "Ravi"), Priority.MEDIUM)); // always fails
        svc.submit(new Notification("n5", "u2", Channel.EMAIL, "NOPE", Map.of(), Priority.MEDIUM));           // bad template
        svc.awaitIdle(5000);
        svc.shutdown();
    }
}

Real output (single worker; exact interleaving of the first lines can vary run to run since the worker starts draining while main is still submitting, but the semantics are the same):

SKIPPED n2[SMS/HIGH] : duplicate
RETRY   n2[SMS/HIGH] attempt=1 in 50ms (SMS vendor timeout #1)
SKIPPED n3[SMS/HIGH] : user opted out
RETRY   n4[PUSH/MEDIUM] attempt=1 in 50ms (PUSH vendor timeout #1)
FAILED  n5[EMAIL/MEDIUM] : Unknown template NOPE
SENT    n1[EMAIL/LOW] -> "Hi Asha, 20% off today!"
RETRY   n2[SMS/HIGH] attempt=2 in 100ms (SMS vendor timeout #2)
RETRY   n4[PUSH/MEDIUM] attempt=2 in 100ms (PUSH vendor timeout #2)
SENT    n2[SMS/HIGH] -> "Your OTP is 482913. Valid 5 min."
FAILED  n4[PUSH/MEDIUM] : retries exhausted: PUSH vendor timeout #3

Reading it: n2 duplicate skipped; n3 skipped (opt-out); n4 retried with 50ms then 100ms backoff and dead-lettered after 3 attempts; n5 failed permanently (bad template, no retry); n2 succeeded on the 3rd attempt (SMS vendor failed twice).

6. Key flows

submit(n) -> seenKeys.add(key)? --no--> onSkipped(duplicate)
                 | yes
                 v
           queue.put(n)  (ordered by priority, then FIFO seq)
                 |
 worker: take() -> opted out? --yes--> onSkipped
                 | no
                 v
        render template --bad--> onFailed (permanent)
                 |
        sender[channel].send()
           | ok                    | TransientDeliveryException
           v                       v
       onSuccess        shouldRetry(attempt)?
                          yes: onRetry, scheduler.schedule(queue.put(n), delay)
                          no : onFailed (dead letter)

7. Extensibility (no modification of existing code)

  • New channel (WhatsApp): add Channel.WHATSAPP + a WhatsAppSender and pass it in the sender list. (Enum edit is the one touch point; use a string channel id/registry to avoid even that.)
  • New retry behaviour (jitter, circuit-breaker): new RetryPolicy.
  • New template syntax (Mustache/FreeMarker): extract TemplateEngine as an interface.
  • Audit/metrics: new DeliveryListener.
  • Scheduling / digest: decorate submit or add a DelayQueue stage in front.

8. Concurrency and edge cases

  • Duplicate submit race: Set.add is atomic, so exactly one winner. Caveat: the key is recorded before send; if the process crashes the notification is lost. Production: persist state (PENDING/SENT) in DB with a unique constraint on the key.
  • Retries keep the item "in flight" so awaitIdle is correct; the scheduler only re-enqueues (cheap), so workers never sleep.
  • A runtime exception in a listener or sender is caught so a worker never dies (listener exceptions should also be isolated individually in production).
  • Unknown template is permanent: do not retry non-transient errors.
  • Priority starvation: LOW can starve under constant HIGH load; fix with aging or weighted fair queues.
  • Opt-out must be checked at send time, not submit time (the user may opt out while queued). We do.
  • OTP expiry: HIGH items may carry a TTL; drop if stale before sending.

9. Follow-ups and model answers

  • Make it distributed / persistent? Replace the in-memory queue with Kafka (partition by userId for per-user ordering; separate topics per priority/channel). Workers are stateless consumers; an outbox table written in the same transaction as the business event guarantees no lost notifications; DLQ topic for exhausted retries; idempotency key in Redis/DB unique index; delivery status in a store and vendor callbacks (webhooks) update it.
  • Exactly once? Impossible end to end; do at-least-once plus idempotency (vendor idempotency key where supported).
  • Why separate pools per channel? Bulkhead: slow SMS vendor must not block email.
  • Rate limit per vendor/user? Wrap sender in a RateLimitedSender decorator (token bucket).
  • Fallback channel (push fails then SMS)? A FallbackPolicy consulted in onFailed, or chain of senders (Chain of Responsibility).
  • Ordering guarantees? Per-user ordering needs one partition/worker per user hash; trade-off with parallelism.
  • Complexity: submit O(log n); take O(log n); render O(template length x params); opt-out check O(1).

10. Common mistakes and rubric

Red flags: if/else on channel; sending synchronously in the request thread; Thread.sleep for backoff in worker; retrying permanent errors; no idempotency; template rendering hard-coded inside senders; plain PriorityQueue shared across threads; unbounded retries.

Rubric (10 pts): requirements and assumptions asked (2); Strategy for channels + Observer (2); priority + retry correct (2); thread-safety reasoning (2); extensibility and distributed discussion (2).