Delayed/Scheduled Notifications with Timezone-Aware Delivery

🎯 Design delayed/scheduled notifications with timezone-aware delivery timing — schedule 100M notifications/day for future delivery at user-local optimal times with <1 second precision

Concepts Involved

Delayed Queue (Redis Sorted Set) Timezone-Aware Delivery Batch Scheduling Cron-like Recurrence Sharded Timer Wheels

Problem Statement

How do you schedule notifications for future delivery at the optimal time per user's timezone — "send at 9am user-local-time" means different UTC times for each user — with <1 second precision at fire time?

Scope: Delayed queue architecture, timezone offset calculation, batch scheduling (group by target minute), cron-like recurrence for repeating notifications. Not covering notification content rendering or channel delivery (handled by downstream notification service).

100M/day

scheduled notifications

timezone-aware delivery

timezone offsets

UTC-12 to UTC+14

<1s

delivery precision

fire at exact scheduled second

1157/sec

avg scheduling rate

100M / 86400s

Functional Requirements

What the scheduled notification system must do · core scheduling behaviours

Must Have (Core)

1. Accept notification with schedule_at time (absolute UTC or relative "in 2 hours")
2. Timezone-aware scheduling · "send at 9am user-local-time" converts to per-user UTC fire time
3. Delayed queue · Redis sorted set with fire-time as score, poll every 100ms
4. Batch scheduling · group notifications by target minute to amortize dispatch overhead
5. Cancel/reschedule · cancel a scheduled notification before fire time
6. Cron-like recurrence · repeating schedules (daily at 9am, weekly Monday 8am)

Out of Scope (this design)

✗ Notification content rendering (template engine)
✗ Channel delivery (push/email/SMS workers)
✗ Preference checking (opt-out, quiet hours)
✗ Analytics (delivery rates, timing effectiveness)
✗ DST edge cases beyond basic offset (e.g., skipped hours)

Non-Functional Requirements

Quality constraints shaping the delayed scheduling architecture

Property	Target	Why It Matters / Design Impact
Delivery Precision	<1 second	Notifications must fire within 1 second of scheduled time. Requires sub-second polling of delay queues.
Throughput	100M schedules/day	~1,157/sec avg, 10K/sec burst during peak scheduling hours. Sharded sorted sets handle this.
Durability	Zero lost schedules	Every scheduled notification must fire. Redis AOF + backup to persistent store (DynamoDB).
Availability	99.99%	Scheduling service is on the critical path. Multi-AZ Redis with automatic failover.
Timezone Accuracy	All IANA zones	Handle DST transitions, half-hour offsets (India UTC+5:30), and 45-minute offsets (Nepal UTC+5:45).
Cancel Latency	<100ms	Cancellation must propagate before fire time. ZREM from sorted set is O(log N).
Recurrence	Infinite series	Recurring notifications generate next occurrence after each fire. No pre-materialization of infinite series.

Key tension: Precision vs. Throughput. Polling every 100ms for sub-second precision means high Redis load. Solved by sharding sorted sets by minute-bucket (shard key = target_minute % 64) and distributing pollers across shards.

Scale Estimation

Derive infrastructure sizing from given constraints. Show this reasoning in an interview.

Given: 100M scheduled notifications/day · 24 timezones · <1s precision · avg schedule-ahead: 4 hours

Step	What to Derive	Calculation	Result	Design Decision
1	Avg schedules/sec	100M / 86,400s	~1,157/sec	Single Redis cluster handles ingestion easily
2	Avg fires/sec	100M / 86,400s (uniform distribution)	~1,157/sec	But 9am local = heavy burst. Peak at 10x = 11.5K/sec fire rate
3	Peak fire burst (9am across TZs)	~40% of daily volume concentrated in 8am-10am local = 40M in 2h × 1TZ	~5,500/sec per TZ peak	But spread across 24 TZs, so UTC 9am peaks are staggered
4	In-flight sorted set size	Avg 4h ahead × 1,157/sec = 16.6M entries in sorted set	~17M entries	Each entry ~200 bytes = 3.4GB. Fits in Redis cluster with room.
5	Sorted set shards needed	17M entries / 500K per shard (for O(log N) perf)	~34 shards	Use 64 shards (power of 2) for even distribution via hash
6	Poller instances	64 shards / 4 shards per poller	~16 poller pods	Each poller checks ZRANGEBYSCORE every 100ms on 4 sorted sets
7	Redis memory total	17M entries × 200B + overhead	~5GB	Redis cluster with 8 nodes, 1GB each (with replication headroom)
8	Recurrence metadata store	10M recurring schedules × 512B each	~5GB	DynamoDB table for recurrence rules. Generate next fire on each trigger.

Interview tip: The key insight is that "send at 9am" creates a thundering herd across each timezone. Since timezones are staggered by 1 hour, the actual UTC fire times spread naturally. The real challenge is when one timezone has 10x more users (e.g., US Eastern = largest single-TZ cohort).

APIs

Scheduling service endpoints · create, cancel, and query scheduled notifications

POST /v1/notifications/schedule

Schedule a notification for future delivery at a specific time or user-local time

{
  "user_id": "u_abc123",
  "template_id": "daily_digest",
  "schedule_type": "user_local_time",   // absolute_utc | relative | user_local_time
  "schedule_at": "09:00",               // for user_local_time: HH:MM
  "schedule_date": "2024-03-15",        // optional: specific date (null = today)
  "timezone": "America/New_York",       // IANA timezone (from user profile if not provided)
  "channels": ["push", "email"],
  "params": { "digest_count": 12 },
  "dedup_key": "daily_digest:u_abc123:2024-03-15",
  "recurrence": {                       // optional: for recurring schedules
    "pattern": "daily",                 // daily | weekly | monthly | cron
    "cron_expr": null,                  // "0 9 * * 1" for cron pattern
    "end_after": 90                     // stop after N occurrences (null = infinite)
  }
}

Response: 201 Created · { "schedule_id": "sch_xyz789", "fire_at_utc": "2024-03-15T14:00:00Z", "status": "scheduled" }

DELETE /v1/notifications/schedule/{schedule_id}

Cancel a scheduled notification before it fires

DELETE /v1/notifications/schedule/sch_xyz789

Response 200: { "schedule_id": "sch_xyz789", "status": "cancelled", "was_fired": false }

GET /v1/notifications/schedule/{user_id}/pending

List pending scheduled notifications for a user

GET /v1/notifications/schedule/u_abc123/pending?limit=20

Response 200:
{
  "schedules": [
    { "schedule_id": "sch_xyz789", "template_id": "daily_digest", "fire_at_utc": "2024-03-15T14:00:00Z", "recurrence": "daily" }
  ],
  "total_pending": 3
}

Data Model

Core tables and Redis structures for the scheduling pipeline

scheduled_notifications (DynamoDB — persistent store)

{
  "schedule_id":    "sch_xyz789",       // partition key
  "user_id":        "u_abc123",
  "template_id":    "daily_digest",
  "fire_at_utc":    "2024-03-15T14:00:00Z",
  "user_timezone":  "America/New_York",
  "user_local_time":"09:00",
  "channels":       ["push", "email"],
  "params":         { "digest_count": 12 },
  "dedup_key":      "daily_digest:u_abc123:2024-03-15",
  "status":         "scheduled",        // scheduled | fired | cancelled | failed
  "recurrence":     { "pattern": "daily", "next_fire": "2024-03-16T14:00:00Z" },
  "created_at":     "2024-03-14T10:00:00Z",
  "fired_at":       null
}

recurrence_rules (DynamoDB)

{
  "recurrence_id":  "rec_001",          // partition key
  "user_id":        "u_abc123",
  "template_id":    "daily_digest",
  "pattern":        "daily",            // daily | weekly | monthly | cron
  "cron_expr":      null,
  "user_timezone":  "America/New_York",
  "local_time":     "09:00",
  "channels":       ["push", "email"],
  "params":         { "digest_count": 12 },
  "next_fire_utc":  "2024-03-16T14:00:00Z",
  "occurrences":    45,
  "max_occurrences": 90,
  "active":         true
}

Redis Structures (Delayed Queue)

// Delayed queue — sorted set, score = fire_time_unix_ms
// Sharded by: schedule_id hash % 64
ZADD delayed_queue:{shard_id} {fire_time_unix_ms} "{schedule_id}:{user_id}:{template_id}"

// Cancel set — tombstones for cancelled schedules (checked before fire)
SADD cancelled_schedules "{schedule_id}"
EXPIRE cancelled_schedules:{schedule_id} 86400   // 24h TTL

// Timezone offset cache
HSET tz_offsets "America/New_York" "-18000"      // offset in seconds from UTC
HSET tz_offsets "Asia/Kolkata" "19800"

// Per-minute batch bucket (for batch dispatch optimization)
SADD fire_bucket:{minute_unix} "{schedule_id_1}" "{schedule_id_2}" ...
EXPIRE fire_bucket:{minute_unix} 120              // 2 min TTL after target minute

Architecture Overview

Schedule API → Timezone Resolver → Delayed Queue (Redis ZSET) → Poller → Dispatcher → Notification Service

Key Design Decisions

Tradeoffs made in this architecture and their rationale

Decision	Options Considered	Chosen	Why
Delayed Queue	Database polling, RabbitMQ delayed exchange, Redis sorted set	Redis Sorted Set	O(log N) insert/remove. ZRANGEBYSCORE fetches all ready items in one call. Sub-ms latency. Sharding handles scale.
Timezone Handling	Store UTC only, store local+offset, resolve at fire time	Resolve to UTC at schedule time	Convert to UTC fire_time immediately. Store original TZ for DST recalculation on recurring schedules. Pollers only compare UTC.
Polling Interval	1s polling, 100ms polling, event-driven (Redis keyspace notifications)	100ms polling per shard	Keyspace notifications are unreliable under load. 100ms gives <1s precision with acceptable Redis load (10 ops/sec/shard).
Cancellation	ZREM immediately, tombstone set, soft-delete in DB	Tombstone SET + lazy ZREM	ZREM requires knowing the shard. Tombstone is O(1) lookup at fire time. Cancelled entries cleaned up on next poll or by background sweep.
Recurrence	Pre-materialize all occurrences, generate next on fire, hybrid	Generate next on fire	Infinite recurrence can't be pre-materialized. After each fire, compute next UTC fire time (accounting for DST changes) and ZADD.
Durability	Redis only, Redis + DB, DB as source of truth with Redis as acceleration	DynamoDB source of truth + Redis for active window	Redis handles the hot path (next 4 hours). DynamoDB persists all schedules. Recovery: replay DynamoDB → Redis on failure.

Why Redis sorted set over database polling: Database polling at 100ms intervals across 100M pending records would crush the DB. Redis ZRANGEBYSCORE(0, now) on a sorted set returns only ready items in O(log N + M) where M is the result count. With sharding, each shard holds ~265K entries — sub-ms response.

DST transition handling: When clocks spring forward (2am → 3am), a notification scheduled for 2:30am local never fires that day — reschedule to 3:00am. When clocks fall back (2am → 1am), deduplicate to prevent double-fire. Recurrence engine recalculates UTC offset on each occurrence.

Thundering herd at popular times: "Send at 9am" is the most common schedule. US Eastern alone may have 10M notifications firing at UTC 14:00:00. Solution: jitter within a configurable window (±30s) to spread the burst. Users don't notice 30s variance but infrastructure avoids 10M/sec spike.

Atomic poll-and-dequeue: Use a Lua script: ZRANGEBYSCORE + ZREM in a single atomic operation. This prevents two pollers from both claiming the same entry. The Lua script returns removed entries to the caller — if ZREM returns 0, another poller already claimed it.

Resilience & Edge Cases

How the scheduling system handles failures gracefully

Scenario	Problem	Solution	Recovery
Redis Node Failure	Shard goes down, entries for that shard are inaccessible.	Redis Cluster with replicas. Automatic failover to replica (<5s). DynamoDB has all schedules for full rebuild if needed.	<5s automatic failover
Poller Crash	Poller dies, its assigned shards go unpolled.	Leader election (ZooKeeper/etcd). Surviving pollers detect failure via heartbeat and take over orphaned shards within 10s.	<10s re-assignment
Clock Skew	Poller's clock drifts, fires notifications early or late.	NTP sync enforced. Health check rejects pollers with >100ms drift. Use Redis server time (TIME command) as reference, not local clock.	Automatic via Redis TIME
Massive Cancel Storm	Campaign cancelled — 5M scheduled notifications need cancellation.	Bulk cancel API writes tombstones asynchronously. Entries remain in ZSET but are skipped at fire time. Background cleanup sweeps old tombstones.	<1s effective cancellation
DST Recurrence Bug	Recurring schedule crosses DST boundary, fires at wrong time.	Recurrence engine always recalculates from user_local_time + current UTC offset (not previous UTC fire time). IANA tz database updated monthly.	Correct after next fire
Redis Full Rebuild	Complete Redis cluster loss (catastrophic failure).	DynamoDB scan: all records with status=scheduled AND fire_at_utc within next 4 hours → ZADD to new Redis. Background job completes in ~10 minutes.	~10 min full rebuild

Interview Cheat Sheet

5 key points to nail a delayed scheduling system interview

1. Redis Sorted Set as Delayed Queue
Score = fire_time_unix_ms. ZRANGEBYSCORE(0, now) returns all ready entries. Atomic Lua script does ZRANGEBYSCORE + ZREM to prevent double-fire. Shard by schedule_id hash % 64 to distribute load. Each shard holds ~265K entries — sub-ms poll response.

2. Timezone Resolution at Schedule Time
Convert "9am America/New_York" to UTC immediately at schedule creation. Store both the UTC fire_time (for the sorted set) and the original timezone+local_time (for DST recalculation on recurring schedules). Pollers never deal with timezones — they only compare UTC milliseconds.

3. Recurrence: Generate Next on Fire
Never pre-materialize infinite recurring schedules. After each fire, compute the next occurrence from the recurrence rule + user timezone (accounting for DST). ZADD the next fire time back to the sorted set. This keeps the sorted set size bounded to one entry per active recurrence.

4. Cancellation via Tombstones
Don't ZREM on cancel (requires knowing exact shard and member value). Instead, write a tombstone: SET cancelled:{schedule_id} 1 EX 86400. At fire time, poller checks SISMEMBER before dispatching. Lazy cleanup removes cancelled entries from ZSET during regular polling sweeps.

5. Jitter for Thundering Herd
"Send at 9am" is the #1 scheduled time. Without jitter, one timezone cohort (10M+ users) all fire at the exact same second. Add ±30s configurable jitter on non-time-critical notifications. Users never notice 30s variance but the system avoids a 10M/sec spike that would overwhelm downstream notification workers.

System Design Case Study