Design an ad frequency capping system

Design a **frequency capping** system for an ads platform. An ad server must decide, for each ad impression opportunity, whether showing an ad would violate frequency caps such as: - Per-user per-campaign cap (e.g., max 3 impressions per user per 24 hours) - Per-user per-ad cap (creative-level) - Optional: per-user per-advertiser cap - Optional: cross-device identity (multiple device IDs map to one user) ### Requirements 1. **Online decisioning**: At serve time, given `(user_id, candidate_campaign_ids, now)`, filter out campaigns that would exceed caps. 2. **Event ingestion**: After an ad is shown, an impression event must update the counters used for future decisions. 3. **Time windows**: Support rolling windows (e.g., last 1 hour, 24 hours, 7 days). 4. **Scale** (assume): 100K–1M QPS serving; similar order impression events. 5. **Latency**: p99 decisioning latency budget ~10–20 ms at the ad server. 6. **Correctness**: Prefer not to exceed cap; small under-delivery is acceptable. Handle duplicates and late events. ### Deliverables - APIs and data flow - Storage/data model for counters - How you enforce rolling time windows - Consistency strategy (exact vs approximate) - Failure modes, edge cases, and monitoring