Mastering Ad Frequency: Strategies for High-Scale Capping

Frequency capping ensures that a single user does not see the same campaign (or brand) too many times within a fixed window—typically 3–5 impressions per day. From the user's perspective, frequency capping prevents ad fatigue and improves brand sentiment. From the advertiser's perspective, it allocates budget toward reaching new users rather than showing the same ad to the same person repeatedly, which has diminishing returns on conversion and ROI.

The technical challenge is enforcing per-user impression counts across a geographically distributed bidding fleet within tens of milliseconds, without incurring the latency cost of querying a central database for every auction. A typical exchange sees 100k–500k bid requests per second; adding a synchronous round-trip to a database for each bid request immediately becomes the critical path and can add 20–50ms of tail latency.

The business impact is substantial. Uncapped campaigns waste 10–20% of budget showing repeat impressions to the same users, and poor user experience erodes publisher trust. Major advertisers contractually require frequency capping: "No more than 5 impressions per user per day" is standard language in media buying contracts. Failure to enforce frequency caps can result in millions of dollars in wasted spend and publisher relationship damage.

Key challenges include: (1) distributed state—tracking user impression counts across multiple servers requires either centralized storage (latency spike) or distributed eventual consistency (reconciliation lag); (2) user identification—cookies are unreliable and privacy laws (GDPR, CCPA) restrict tracking; (3) storage at scale—tracking 1 billion users × 10 campaigns per day is 10 billion counters, roughly 80 GB of state; (4) TTL management—counters must expire (typically 24 hours) to avoid unbounded storage growth.

Scale considerations: 100k–500k bid requests per second, 86.4 billion bids per day, and audience sizes ranging from 100k (niche B2B) to 1 billion (mass-market consumer). A frequency cap of "5 per day" means managing 5 billion to 5 trillion impressions worth of counter state per day.

Key Requirements

Functional Requirements

• Per-user, per-campaign impression counting: Track how many times user_id has been shown campaign_id in a 24-hour window.
• Configurable cap thresholds: Support 1–100 impressions per user per day (typically 3–5).
• Multi-level capping: Some campaigns require frequency caps; others do not. Support per-campaign configuration.
• Lookback window flexibility: Allow 1-hour, 6-hour, 24-hour, or custom windows.
• Accurate reporting: Log each capped impression (suppressed bid) for auditing and campaign performance analysis.
• Safe defaults: If frequency capping service is unavailable, gracefully degrade to no capping rather than blocking all bids.

Non-Functional Requirements

• Decision latency: < 5ms for a frequency cap lookup + increment (including network round-trip if external).
• Throughput: Support 100k–500k 'check and increment' operations per second.
• Storage efficiency: Store impression counters using < 1 byte per user-campaign pair (e.g., Bloom filters, HyperLogLog, bitmaps).
• Memory footprint: Typical system should fit ~100 billion user-campaign pairs in < 1 TB (aggressive compression required).
• Consistency: Eventual consistency acceptable (a few seconds of lag before old impressions expire); strong consistency not required.
• Availability: 99.99% uptime for frequency capping checks (few suppressed impressions acceptable; false negatives < 0.1%).
• TTL/Expiry: Automatic expiration of counters after 24–48 hours to free memory.

Simplified Architecture

Architecture Proposals

Option 1: Centralized ElastiCache Redis Cluster with INCR+EXPIRE

Maintain an Amazon ElastiCache for Redis cluster (cluster mode enabled, Multi-AZ) where each key is campaign_id:user_id, and the value is an impression counter. On each bid request, atomically increment the counter and set a 24-hour TTL. If the counter exceeds the cap, suppress the bid.

How it works:

1. Bidder receives a bid request for campaign_123 from user_456.
2. Bidder sends a pipelined request to ElastiCache Redis: INCR("campaign_123:user_456") and EXPIRE("campaign_123:user_456", 86400) (using Redis Cluster with consistent hashing).
3. ElastiCache returns the new counter value (e.g., 3).
4. If 3 > cap_for_campaign_123 (e.g., 5), bidder rejects the bid and logs a suppressed impression.
5. If 3 <= cap, bidder participates in the auction.

To reduce latency, bidders use pipelined Redis commands: batch multiple INCR operations into a single TCP round-trip (e.g., 100 operations per pipeline).

Why it works:

• Redis is purpose-built for this use case: atomic operations, sub-millisecond latency, and integrated TTL.
• Pipelining reduces the latency cost: 100 operations in 1–2ms instead of 100 individual round-trips.
• ElastiCache Cluster Mode distributes keys across shards; replication (primary + replica in separate AZ) provides high availability.
• Route 53 latency-based routing directs bidders to the nearest regional cluster.

Pros:

• Simple to understand and operate: straightforward key-value store with atomic INCR.
• INCR is atomic, so no race conditions between concurrent bidders.
• Built-in TTL (EXPIRE) prevents unbounded memory growth.
• Easy to debug: you can query ElastiCache directly to check user impression counts.
• Multi-AZ redundancy: automatic failover if a node fails.
• Multi-region: span multiple regions for better geo-locality and resilience.

Cons:

• ElastiCache cluster cost: high-memory, high-throughput ElastiCache instances are expensive ($1k–$5k/month per cluster).
• Network round-trip latency: pipelined batches add 1–5ms to bid latency on average, p99 can be 50ms+ during traffic spikes.
• Thundering herd during high traffic: all bidders make simultaneous requests to ElastiCache, saturating the network or cluster connections.
• Memory pressure: at 100k QPS, storing all user-campaign pairs for 24 hours requires ~1–2 TB of ElastiCache memory (100k QPS × 86,400 seconds × 2 bytes per key-value ≈ 1.7 TB), which exceeds affordable single-cluster budgets.

Failure Modes & Mitigations:

• ElastiCache node failure: Replication ensures data survives; failover takes ~500ms. Mitigate by configuring bidders to retry failed INCR operations or use a local in-process cache of recent user impression counts (valid for ~1 second).
• Network partition between bidders and ElastiCache: Bidders cannot reach ElastiCache; they fall back to no capping (permissive mode) or use a local cache. Mitigate by deploying ElastiCache replicas in multiple regions and using CloudFront for request routing.
• ElastiCache memory exhaustion: Old keys are not expiring fast enough, or TTL is too long. Mitigate by using ElastiCache eviction policies (e.g., LRU) and reducing TTL to 12–18 hours if storage is tight.

When to Choose: Choose Option 1 for small to mid-scale systems (< 10k QPS, < 1M unique users per day) or when operational simplicity is critical. Early-stage ad exchanges and DSPs often start here.

Option 2: Probabilistic Counters with Redis HyperLogLog or MemoryDB

Instead of storing exact counts, use probabilistic data structures that estimate impression counts using a fraction of the memory. HyperLogLog provides cardinality estimation (count unique items) with ~2% error; Counting Bloom Filters track approximate counts with similar accuracy. Use Amazon ElastiCache for Memcached or Amazon MemoryDB for Redis (if durability is required).

How it works:

1. For each campaign_id:user_id, maintain a HyperLogLog or Counting Bloom Filter in ElastiCache Memcached or MemoryDB for Redis.
2. Instead of incrementing a counter, add the user to the HyperLogLog: PFADD("campaign_123", user_id).
3. To check the cap, query the cardinality: count = PFCOUNT("campaign_123") (returns approximate count).
4. If the approximate count exceeds the cap, reject the bid.
5. HyperLogLog has a small false positive rate (~1–5%), meaning occasionally a user will be incorrectly identified as having exceeded the cap and a valid bid will be rejected. This is acceptable.

Data structures:

• HyperLogLog: Uses ~1.5 KB to track ~100k unique users with 2% error. Redis provides built-in HyperLogLog: PFADD("campaign_123", user_456) and PFCOUNT("campaign_123").
• Counting Bloom Filter: Uses ~3–5 KB for the same cardinality with similar error. Libraries exist in Python (pybloom), Java (guava), Go (bloom).

Why it works:

• Probabilistic structures use 1,000x less memory than exact counters (1.5 KB vs. 1.5 MB for 100k users).
• Operations are still O(1) and sub-millisecond.
• No central database required: filters can be stored in ElastiCache Memcached (cheaper than Redis) or MemoryDB (for durability).

Pros:

• Extreme memory efficiency: track billions of user-campaign pairs in tens of GB rather than terabytes.
• No central bottleneck if using local filters: each bidder maintains local Bloom Filters for campaigns it bids on, no network round-trip.
• Fast: PFADD/PFCOUNT operations are O(1) and highly optimized (bitwise operations).
• Graceful degradation: false positives mean occasional suppressed bids (acceptable); false negatives are impossible.
• Cheaper than Option 1: ElastiCache Memcached is ~50% cheaper than Redis.

Cons:

• Approximate counts introduce false positives: ~1–5% of bids are incorrectly suppressed. For a $1B/day spend, this could mean $10M–$50M in suppressed valid bids (unacceptable for some advertisers).
• Requires understanding of probabilistic data structures; operators unfamiliar with HyperLogLog may struggle to tune parameters.
• Resetting filters daily is tricky: you cannot simply "clear" a HyperLogLog; you must create a new one. During the transition (old filter → new filter), there is a ~1-hour window where users' counts reset or double-count.
• Cross-bidder consistency is harder: if multiple bidders maintain local filters, one bidder doesn't see another's impressions until a batch reconciliation (e.g., via Kinesis stream).

Failure Modes & Mitigations:

• HyperLogLog size is too small: False positive rate spikes to 10%+, causing unacceptable bid suppression. Mitigate by over-provisioning filter size (use 10x the expected cardinality) or monitoring FPR in production and alerting if it exceeds 2%.
• Filter never resets (no daily expiry): Counts accumulate indefinitely; after a few days, every user exceeds the cap. Mitigate by implementing an explicit "daily reset" process: at midnight UTC, bidders clear old filters and instantiate new ones. Use a Kinesis topic with "reset" events to coordinate.
• Bidders disagree on caps: Some bidders suppress impressions for user_456 under campaign_123; others do not. Mitigate by storing cap thresholds in a central config service (Amazon Systems Manager Parameter Store) and broadcasting updates to all bidders hourly.

When to Choose: Choose Option 2 for hyperscale systems (100k+ QPS) where memory cost is a major constraint, or when a small false positive rate (< 5% suppressed valid bids) is acceptable. Large DSPs and exchanges with billions of daily impressions often use HyperLogLog for frequency capping.

Option 3: Edge-Local Caching with Kinesis Reconciliation

Each bidder (ECS Fargate task) maintains a local in-memory cache of user impression counts for frequently seen campaigns. Every 10–30 seconds, bidders flush their local counts to Amazon Kinesis Data Streams for reconciliation. A Lambda or ECS consumer processes the stream, merges counts from all bidders, and publishes summaries back to bidders for correction.

How it works:

1. Bidder receives a bid request for campaign_123 from user_456.
2. Bidder checks local cache: local_cache["campaign_123"]["user_456"].
3. If the count is < cap, increment locally and bid.
4. Every 10 seconds, bidder publishes its local cache to Kinesis: { campaign_123: { user_456: 5, user_789: 3, ... }, ... }.
5. A Lambda function or ECS consumer (Kinesis consumer) merges counts from all bidders, groups by campaign-user, and stores aggregates in Amazon DynamoDB or Amazon Timestream.
6. Aggregator periodically (every 30s) publishes a "corrections" message: "campaign_123 user_456 actually has 7 impressions; you logged 5."
7. Bidders incorporate corrections into their local cache via a second Kinesis topic.

Why it works:

• Local cache eliminates network latency: impression count check is just a hash lookup (~1 microsecond).
• Asynchronous reconciliation keeps central infrastructure lightweight: no real-time requirements.
• Natural fault tolerance: if the aggregator Lambda is down, bidders continue with their local caches and gradually drift apart; once aggregator recovers, corrections re-sync.

Pros:

• Extremely low latency: sub-microsecond local lookups, no network calls per bid.
• Minimal central infrastructure: aggregator is a stateless Lambda function or ECS task, not a database.
• Handles traffic spikes gracefully: local cache scales with each bidder, no central bottleneck.
• Cost-effective: local memory is cheap; only aggregate metadata (top-K user counts) is persisted in DynamoDB.
• Scales to billions of impressions: each bidder is independent, adding more bidders is linear cost.

Cons:

• Eventual consistency: a user can exceed the cap by a small amount (1–3 impressions) before reconciliation catches it. For strict caps (e.g., "exactly 1 impression"), this is unacceptable.
• Reconciliation complexity: merging counts across bidders requires careful handling of duplicates, clock skew, and out-of-order messages. Lambda must process Kinesis records idempotently.
• Memory usage per bidder can grow unchecked if not managed: a naive implementation caches counts for all users, which can be billions. Mitigate with an LRU cache (e.g., max 100k users per campaign per bidder).
• Stale corrections: a correction published at time T may arrive at a bidder at time T+5s, causing the bidder to suppress a bid that should not have been suppressed. Requires a strategy for handling out-of-order corrections (e.g., ignore corrections older than 10 seconds).

Failure Modes & Mitigations:

• Bidder crashes without flushing cache: Its local counts are lost; users appear to have lower impression counts in the next window. Mitigate by flushing cache to Kinesis every 5 seconds (more frequent than the standard 10s) and using an "ack" mechanism (Lambda acknowledges receipt, bidder then clears).
• Lambda aggregator falls behind: It cannot process Kinesis records fast enough; reconciliation lag exceeds 5 minutes. Mitigate by increasing Lambda parallelism (add reserved concurrency) or sharding the Kinesis topic by campaign (one topic per campaign, processed independently).
• LRU cache eviction causes lost counts: If a bidder's cache is full and a new user_id is added, an old user's count is evicted. The bidder later sees the same user again and starts counting from 0. Mitigate by increasing LRU cache size (trade memory for accuracy) or using a more sophisticated eviction policy (evict only expired entries, not frequently-accessed ones).

When to Choose: Choose Option 3 for large-scale, latency-sensitive systems (100k+ QPS) where cost and operational simplicity are balanced. It is particularly useful if you already have Kinesis and Lambda infrastructure for other streaming jobs (e.g., bid logging, spend aggregation).

Comparison Table

Recommendation

For startups and small DSPs (< 10k QPS, < 10M users/day): Use Option 1 (Centralized ElastiCache). It is easy to implement, reliable, and sufficient for early-stage volume. Start with a single ElastiCache Redis instance (cache.r7g.large, 16 GB RAM, ~$200/month) and scale to a cluster (3 nodes, ~$1.5k/month) only when you hit QPS limits around 50k.

For mid-market exchanges (10k–100k QPS, 10M–1B users/day): Prototype with Option 1, then transition to Option 2 (Probabilistic Counters) as memory becomes a cost constraint. False positive rates of 2–5% are typically acceptable in the ad tech industry; if your SLA requires < 1% false positives, stick with Option 1 and invest in ElastiCache cluster sharding across multiple regions.

For hyperscale exchanges (100k+ QPS, 1B+ users/day) or latency-critical systems (p99 < 2ms): Use Option 3 (Local Cache + Reconciliation). The complexity pays off in latency and cost. You will need a Kinesis cluster (often already present for bid logging) and a Lambda function for aggregation, but the local cache approach scales naturally: each bidder is independent, and the aggregator is stateless.

Hybrid approach: Many large exchanges use Option 1 (ElastiCache) for exact counts on high-value campaigns (where false positives are unacceptable) and Option 2 or 3 for long-tail campaigns (where approximation is acceptable). This gives you the best of both worlds: strong guarantees where they matter most, and cost efficiency for the bulk of the workload.

For all options, implement automated testing of the reconciliation logic (Option 3) or TTL expiry (Option 1–2) to ensure that daily resets work correctly and do not cause double-counting or dropped impressions.

Capacity & Performance Notes

Sizing for a hyperscale exchange:

• 500k bids per second
• 1 billion unique users per day
• 50k active campaigns per day
• Frequency cap: 5 impressions per user per day, per campaign

Option 1 (ElastiCache Redis INCR+EXPIRE):

• Key count: ~1B users × 50k campaigns = 50 trillion keys in the worst case, but realistically only ~10B keys (average 10 impressions / user × 1k campaigns tracked). ElastiCache stores each key-value pair at ~32 bytes (including overhead). 10B keys × 32 bytes = 320 GB RAM. Cost: ~$30k/month for high-memory ElastiCache (cache.r7g.16xlarge nodes).
• QPS to ElastiCache: 500k bids/sec with pipelined batches of 100 = 5k QPS. Achievable with a 3-node cluster (each node handles ~2k QPS).
• Latency: pipelined batches of 100 commands in a single round-trip add ~2ms p50, ~10ms p99.

Option 2 (Probabilistic Counters):

• HyperLogLog size per campaign: ~1.5 KB for 100k users with 2% error.
• Total memory: 50k campaigns × 1.5 KB = 75 MB in ElastiCache Memcached, or distributed across bidders (~4 MB per bidder × 20 bidders).
• FPR (false positive rate): ~2% means 10k bids/sec are incorrectly suppressed. Over a day, this is ~864M suppressed valid bids. For $1B/day spend, this is ~$10M. Acceptable for most advertisers (< 2% loss).
• Latency: < 0.5ms if stored in ElastiCache (1 PFADD/PFCOUNT per bid), < 0.001ms if local (in-memory HyperLogLog).

Option 3 (Local Cache + Reconciliation):

• Local cache size per bidder: LRU cache of 100k users × 50k campaigns. Assuming 20 bytes per entry (8 bytes user_id hash + 4 bytes count + 4 bytes timestamp + 4 bytes hash overhead): 100k × 20 bytes = 2 MB per campaign. At 50k active campaigns but only 1k "hot" (recently seen) per bidder: 2 MB × 1k = 2 GB per bidder. With 100 bidders, ~200 GB total (manageable).
• Kinesis stream throughput: 500k bids/sec × 20 bytes (campaign + user + count) = 10 MB/sec. Kinesis (4–8 shards, ~$100/month) handles this easily.
• Lambda aggregator: 500k input events/sec. With Lambda's throughput of ~1M events/sec per task, one task is sufficient (4 cores, ~$100/month on provisioned concurrency).
• P99 latency for impression check: < 1 microsecond (hash map lookup).

Example reconciliation window (Option 3):

• Bidders flush every 10 seconds: 500k QPS × 10 seconds = 5M bid events per flush.
• Lambda merges and publishes corrections every 30 seconds.
• Reconciliation lag: ~30 seconds. A user can exceed the cap by at most (500k QPS / 1B users) × 30 seconds = ~0.015 extra impressions on average, or ~1–2 in peak scenarios. Acceptable.