Design a scalable notification system. Discuss the data structures and algorithms involved.

Official answer

First define channels, peak volume, acceptable delay, ordering and user consent. A notification accepted by our service is not the same as one delivered by a provider or read by a recipient.

Persist an authorized notification intent with a stable ID. If it accompanies a business transaction, a transactional outbox can prevent the gap between committing the business change and enqueueing its notification. A relay feeds a durable queue; workers select the channel and call the provider.

Partition work by a meaningful key when ordering is required. Use a persistent delivery ledger with a unique (notification_id, recipient_id, channel) key to track attempts. A delayed queue or priority heap can schedule retries; token buckets can enforce recipient and provider rate limits. Priority handling needs fairness so low-priority work is not starved.

Retry transient failures with bounded backoff and jitter, honor provider limits, and route exhausted attempts to an inspectable failure queue. A timeout after provider acceptance can still produce duplicates unless the provider supports a suitable idempotency mechanism. Do not promise exactly-once delivery from an internal unique key alone.

Recheck current preferences and eligibility before sending, invalidate cached preferences appropriately, and protect device tokens. Monitor queue age, accepted/delivered/failed counts and duplicate reports. Rehearse outages and replay before claiming scale.