Ad Pacing Unpacked: Architecting Guaranteed Delivery

Direct deals between advertisers and publishers guarantee a fixed volume of impressions (or spend commitment) over a contract term. A fashion brand might sign a $5M quarterly deal with a publisher: "guaranteed 100M impressions on homepage and category pages, 80% viewable, target audience = women 18–45, all brand-safe content." Publishers must deliver 100M impressions—if they deliver only 95M, they owe a refund or make-goods (free impressions); advertisers expect priority queue access (direct impressions are served before open-auction inventory).

The delivery challenge is pacing: starting January 1 with 100M impressions over 90 days means ~1.1M impressions/day. Actual traffic is lumpy (weekends have 20% lower inventory; viral events spike 2–3x). Naive serving (first-come-first-served) risks under-delivery early and over-delivery late or missing target audience segments. Sophisticated pacing algorithms predict supply and allocate inventory optimally: hold back audience inventory to match demand, release surplus to auction when confident inventory will clear.

This case explores three architectures:

• deterministic priority decision-tree (guaranteed → preferred → open auction)
• linear-programming optimizer (SHALE-style, solve nightly for optimal allocation)
• forecast-driven pacing controller (predict supply hourly, adjust priorities in real-time based on pacing health).

Key Requirements

Functional Requirements

• Priority serving: Guaranteed deals are served first; open auction only gets residual inventory.
• Pacing control: Deliver guaranteed impressions uniformly over contract term (±5% variance).
• Audience targeting: Respect advertiser targeting (geography, device, audience cohort) while pacing.
• Make-goods tracking: Track under-delivery; enable make-good offer (free impressions to fulfill contract).
• Forecasting: Predict supply by hour (device type, geography, audience) to inform pacing decisions; store forecasts in S3 for Athena queries.
• Flexibility: Support different deal types: guaranteed (fixed volume), preferred (priority to auction but no guarantee), sponsorship (fixed CPM, all eligible inventory).
• Reporting: Daily/hourly delivery reports to advertiser; visibility into pacing health via CloudWatch dashboards and SNS alerts.

Non-Functional Requirements

• Latency: Pacing decision <10 ms at serve time; no RTB bottleneck.
• Throughput: 1M–10M impressions/sec across all deals; decisions per request are lightweight.
• Availability: 99.99% uptime; pacing logic must be resilient (failed pacing = mis-serving).
• Consistency: Deterministic decisions; same impression scored the same way across requests.
• Cost: Pacing orchestration ~$50–200K/month (ECS, forecast infrastructure, DynamoDB).
• Scalability: Support 1000–10000 concurrent deals; each deal has different requirements.

Simplified Architecture

Architecture Proposals

Option 1: Priority Decision-Tree at Ad Selection

Description:
Ad selection logic (ECS Fargate bidder service) evaluates eligible deals in a prioritized waterfall. At request time, the serving system checks:

1. Guaranteed deals: Query DynamoDB table for eligible guaranteed deals (targeting matches, not yet delivered). Score by pacing health. Serve one.
2. Preferred deals: If no guaranteed, check preferred deals in DynamoDB priority order.
3. Open auction: If no preferred, run second-price auction.

Within each tier, deals are scored by: remaining impressions needed (stored in DynamoDB counter), days remaining (computed from deal start/end stored in DynamoDB), and advertiser priority weight. Pacing is implemented as a simple heuristic: if a deal has N days remaining and K impressions left, target daily_quota = K / N. If today's served_count < daily_quota * 0.8, boost priority; if > daily_quota * 1.2, suppress priority. Served counts are tracked in DynamoDB with hourly aggregation via Lambda for reporting.

Pros:

• Simple logic: waterfall is transparent and easy to audit; all logic fits in ECS Fargate service <500 lines.
• Fast: O(n) decision per request where n = number of eligible deals (usually <20); DynamoDB DAX for sub-millisecond lookups.
• Deterministic: same request always gets same decision (if deals are static); audit-friendly.
• Easy integration: fits naturally into existing ad selection pipeline.
• Graceful degradation: if pacing service fails, waterfall still works (defaults to safe priorities).
• DynamoDB scales: handles 1000+ deals, millions of RPS.

Cons:

• Naive pacing: heuristic (0.8× to 1.2× boost based on pace health) is crude; no guarantee of optimal delivery.
• No inventory prediction: decision is myopic (current hour only); doesn't anticipate future supply/demand.
• Double-booking risk: concurrent requests all see same "under-paced" deal; serve 10x quota in a minute.
• Audience conflicts: if deal targets "women 18–45" and request is male user, deal is skipped; remaining inventory for men might be unused.
• Inflexible: can't adjust pacing mid-day based on real-time traffic; must wait until next hourly recalculation.
• Difficult scaling: adding a new deal requires recalibrating all boost weights.

Failure Modes & Mitigations:

• Concurrent under-pacing: Multiple threads see deal X is under-paced by 10%, all boost it; serve 100K impressions in 1 min instead of 5K. Mitigation: use DynamoDB atomic updates (conditional write) on served_count to serialize pacing decisions; implement rate limiter in ECS (serve max 10K/min per deal via in-process counter + periodic flush to DynamoDB).
• Audience skew: Deal targets "premium users" (5% of traffic); while general traffic is high, premium audience is low; deal under-delivers 20%. Mitigation: forecast supply by segment (store in DynamoDB table keyed by deal_id, segment); adjust pacing boost per segment.
• Make-good accumulation: Multiple under-paced deals trigger make-goods; publisher owes 20M impressions; audience is exhausted. Mitigation: DynamoDB table tracks outstanding make-goods per deal; cap total at 10% of monthly inventory (enforcement in Lambda validation).

When to Choose:

• Starting point for guaranteed deals; low complexity, acceptable pacing variance (±10–15%).
• Small publisher (<1000 deals) where coordination overhead is manageable.
• Deals with loose SLA (±10% delivery variance acceptable).

Option 2: Linear-Programming Optimizer (SHALE-style)

Description:
Formulate deal allocation as a linear program (LP) solving nightly via AWS Step Functions: maximize total revenue subject to constraints. Variables are: impressions allocated to each deal per hour (stored in S3 Parquet, loaded into ElastiCache for serving). Objective: sum(allocated[deal] * CPM[deal]) + sum(unallocated * reserve_CPM). Constraints:

• For guaranteed deals: sum(allocated[deal]) >= guarantee[deal] / num_days
• For preferred deals: allocated[deal] <= preference_cap[deal] (flexible cap)
• Total: sum(allocated[all_deals]) <= supply_forecast[hour] (forecasted via SageMaker, stored in S3)
• Audience: allocated[deal] respects audience_reach[deal] (can't allocate more "women 18–45" than available, from S3 forecast)

Solve via AWS Step Functions + SageMaker Processing (uses open-source solver like SCIP or OR-Tools) daily (nightly at 11 PM UTC). Deployment: write allocation plan to S3 Parquet, load into ElastiCache Redis for hot lookup at serve time (O(1) hash map: deal_id + hour → remaining_impressions). Similar to Google's HWM (High-Water-Mark) algorithm and Yahoo's SHALE (Scheduled Allocation Engine).

Pros:

• Provably optimal: LP solver finds globally optimal allocation (within solver precision, typically 99%+ optimality gap <1%).
• Handles constraints: respects guaranteed volumes, audience segments, and supply forecasts simultaneously.
• Flexible CPM handling: automatically trades off between guaranteed (lower CPM) and open auction (higher CPM).
• Audience-aware: allocates "women 18–45" inventory to deals targeting that segment only; avoids wasting supply.
• Scalable logic at serve time: serve-time decision is just budget check via Redis DECR (atomic, <1 ms).
• Learning feedback: daily re-solve incorporates latest supply/demand data from S3 forecasts and DynamoDB actuals.
• Multi-objective: can optimize for revenue, delivery coverage, or hybrid metric.

Cons:

• Optimization complexity: LP formulation requires expertise; solver choice (SCIP, OR-Tools, Gurobi) affects cost ($0 open-source to $100K/year commercial).
• Computation time: solve time is 10 min–1 h even for medium instances (1000 deals, 24 hours, 10 audience segments); can't solve too frequently.
• Forecast dependency: quality of allocation depends entirely on supply forecast; bad forecast (from SageMaker) → bad allocation.
• Reoptimization risk: if forecast is wrong (viral content, DDoS, outage), can't replan mid-day (re-solve takes 30 min); must accept suboptimal serving.
• Explainability challenge: LP solution is opaque ("allocate 1.2M to deal X"); hard to explain why to advertiser (use SageMaker Clarify for post-hoc SHAP explanations).
• Cold-start: new deal appears mid-day; can't wait for nightly solve; must use heuristic from Option 1 (breaks optimality).

Failure Modes & Mitigations:

• Forecast miss: Predicted 1M impressions via SageMaker, actual is 500K (network issue, traffic drop). Allocation is too aggressive, inventory exhausted by 3 PM. Mitigation: use conservative forecast (e.g., 20th percentile of supply from SageMaker); reallocate unused budget to auction in real time (mid-day re-solve, fast heuristic).
• Solver timeout: LP with 10K deals takes 2 hours to solve; window closes before deployment. Mitigation: decompose problem (solve per publisher, per hour independently); use warm-start (initialize solver with previous day's solution, stored in S3).
• Audience segment mismatch: SageMaker forecast says 1M "women 18–45" available; actual is 500K. Deal targeting that segment under-delivers. Mitigation: segment forecast more granularly (geography + device + age cohort); store in S3; monitor segment predictions weekly vs. actuals (Athena query).

When to Choose:

• Large publishers (>10M impr/sec) with 1000+ deals where coordination is complex.
• High-value deals where 2–3% revenue lift from optimality is material ($100K+/month).
• Sophisticated demand (mix of guaranteed, preferred, auction with different CPMs); heterogeneous audience segments.

Option 3: Forecast-Driven Pacing Controller

Description:
Predict supply hour-by-hour, by segment (device type, geography, audience cohort) via SageMaker time-series forecast model (Prophet, ARIMA, or gradient boosting). Store forecasts in S3 hourly, loaded into DynamoDB for fast lookup. For each guaranteed deal, compute target pacing curve: if deal has 100M impressions over 90 days and is currently 45 days through, target is 50M served (50% delivered). Actual served is 48M (tracked in DynamoDB counters, aggregated hourly). Pacing controller tracks: served_pct vs. target_pct. If behind (e.g., 40% served, 50% target), boost deal priority aggressively. If ahead, suppress priority and release inventory to auction.

For audience-specific deals (e.g., "guaranteed 10M to women 18–45"), SageMaker forecast supply of "women 18–45" impressions and adjust pacing per segment. If women traffic is lower than expected, extend deadline or reduce guarantee (negotiated via SNS alerts to sales). Pacing health metrics (% delivered vs. target) are visualized in CloudWatch dashboards and Managed Grafana.

Pros:

• Real-time responsiveness: SageMaker forecast is updated 4–6 times daily; pacing adjusts to actual trends within hours.
• Segment-aware: handles audience-specific guarantees by forecasting supply per segment (stored in DynamoDB or S3).
• Graceful degradation: if forecast is wrong, detection is fast (within hours, not days); can adjust next forecast cycle; Lambda recalculates pacing health every hour.
• Interpretable: pacing health (% delivered vs. target) is easy to explain to advertiser via dashboards; SNS alerts for under-delivery risk.
• Cost-effective: no LP solver needed; just simple heuristic logic (weighted priorities based on pacing health, <100 lines Python in Lambda).
• Flexibility: can extend deadline or adjust guarantee mid-term based on supply trends; DynamoDB table tracks deal adjustments for audit.
• CloudWatch Dashboards: real-time visibility into delivery progress, forecast accuracy, pacing health per deal.

Cons:

• Not provably optimal: pacing controller is heuristic; may under-utilize high-CPM auction inventory (15–20% revenue loss vs. LP).
• Forecast quality is critical: bad forecast → bad pacing; no error recovery (conservative fallback is safe but suboptimal).
• Segment granularity: if forecast is too coarse (all "women" together, not "women 18–25" vs "women 26–45"), pacing may skew within segment.
• Coordination complexity: multiple controllers (forecast model in SageMaker, pacing Lambda, inventory tracking in DynamoDB) must stay in sync.
• Cascading failures: if SageMaker forecast service is down, pacing logic can't adapt; defaults to conservative (hold inventory, reduce priority).

Failure Modes & Mitigations:

• Forecast drift: SageMaker model predicts traffic based on 2 years historical data; new trend (e.g., iOS privacy change) shifts traffic patterns. Forecast becomes consistently 10% low. Mitigation: CloudWatch monitors actual vs. predicted (Athena compares actuals to S3 forecasts daily); retrain SageMaker forecast model weekly; use conservative multiplier (predicted * 0.9) as target, accept 10% under-estimate to stay safe.
• Segment exhaustion: "Women 18–25" segment inventory depleted early; deal targeting that segment can't deliver. Mitigation: SageMaker forecast breaks segment forecast into finer cohorts (18–21, 22–25, etc.); reallocate guarantee to other segments if one exhausted; alert advertiser via SNS 3 days before end-of-contract.
• Mid-day traffic collapse: Forecast expected 50M impressions; at 6 PM only 20M served so far; can't catch up. Mitigation: Lambda job at 6 PM alerts advertiser via SNS (SQS message to sales team); offer extended deadline (re-solve pacing with new end date in DynamoDB) or reduced guarantee (update DynamoDB deal record, log adjustment to CloudTrail).

When to Choose:

• Medium-to-large publishers (1M–10M impr/sec) with 100–1000 deals.
• Inventory with predictable patterns (weekday/weekend, seasonal); SageMaker handles seasonality via Prophet.
• Deals where real-time pacing adjustment is preferred to upfront optimization (more agile, less compute).

Comparison Table

Recommendation

For most publishers, adopt Option 3 (Forecast-Driven Pacing) as the production architecture, with Option 2 (LP Optimizer) as a premium tier for complex multi-objective deals.

Option 3 offers the best practical balance: real-time SageMaker supply forecasting (updated 4–6 times daily) enables responsive pacing without the computational complexity of LP solving. Segment-aware forecasting handles audience-specific guarantees via DynamoDB segment tables; pacing health metrics (% delivered vs. target) provide transparency to advertisers via CloudWatch dashboards and SNS alerts. Cost is moderate ($50–100K/month for SageMaker forecast infrastructure + Lambda controller) and scales to 1000+ concurrent deals.

For publishers with highly complex deal portfolios (e.g., programmatic guaranteed at scale, thousands of preferred-tier deals, diverse CPM structures), consider Option 2: the LP optimizer finds globally optimal allocations, maximizing publisher revenue while respecting all constraints. The upfront solver cost (SCIP is free, Gurobi ~$20–100K/year) is justified if the revenue lift is >2% ($10M+ on $500M annual revenue). Use SageMaker Clarify to provide SHAP-based explanations of LP decisions for audit.

Start with Option 1 (decision-tree) if you are pre-scale (<100 deals, <100M impr/day) or new to guaranteed inventory. Rules are simple and transparent; advertiser expectations are easy to set via CloudWatch dashboards. Migrate to Option 3 as deal count grows (>500 deals) and supply patterns become volatile.

Make-Goods & Clawback:
All options must track under-delivery and trigger make-good offers automatically. If a deal is projected to under-deliver >5% by final day, Lambda job notifies advertiser via SNS and offers 1.1x make-goods (pay for 100M, get make-good offer of 5M+ free impressions, stored in DynamoDB make-goods table). Log all make-good commitments in DynamoDB; cap total outstanding make-goods at 10% of monthly inventory (prevent make-good spiral, enforced via Lambda validation).

AWS Integration Notes:

• SageMaker Forecast: Time-series models (Prophet, ARIMA, AutoML) pre-trained on 2+ years data; retrain weekly to capture trends.
• DynamoDB: Stores deal metadata, served counts (updated hourly via Lambda aggregation), pacing health (computed every hour), make-goods.
• ElastiCache Redis: Cache allocation plan (from S3) for serve-time O(1) lookups; multi-AZ cluster with auto-failover.
• Step Functions: Orchestrates nightly LP solve (formulation → solver → result storage → cache update).
• CloudWatch Dashboards: Real-time metrics per deal (served %, target %, hours remaining, forecast accuracy, make-goods).
• Kinesis: Stream impression events for real-time aggregation and pacing health computation.
• Athena / S3: Query actuals vs. forecasts for post-hoc analysis; S3 Parquet format for efficient storage and querying.

Capacity & Performance Notes

Decision-Tree (Option 1):

• Eligible deals per request: O(n) where n = number of deals with matching targeting. Typical n = 10–50 out of 1000 total deals.
• DynamoDB queries: targeting index (device, geo, audience) scans ~10–50 deals; DAX cache covers 80%+ of queries.
• Scoring per deal: compute pacing_boost = (target_pct - served_pct) * weight; O(1) per deal.
• Total latency: 50 deals * 1 μs/deal = 50 μs + DynamoDB query 5 ms via DAX << RTB budget (100 ms).
• Served-count tracking: DynamoDB atomic increment per deal per hour (UpdateItem with atomic counter); batch sync to S3 every 5 min for analytics.

LP Optimizer (Option 2):

• Problem size: 1000 deals * 24 hours * 10 audience segments = 240K variables; ~1M constraints.
• Solver time: SCIP typically solves in 10–30 min (depends on sparsity, constraint tightness, gap tolerance).
• Solve schedule: nightly Step Functions at 11 PM UTC; deploy allocation plan (S3 Parquet) by midnight.
• Allocation lookup at serve time: O(1) hash lookup in ElastiCache (deal_id, hour) -> remaining_impressions; atomic DECR per request.
• Solution warmth: use previous day's solution as warm start to reduce solve time.

Forecast-Driven Pacing (Option 3):

• Supply forecast model: SageMaker time-series (Prophet, ARIMA, or AutoML) trained on 2+ years historical impression data.
• Forecast features: day-of-week, hour-of-day, seasonality (holidays, events), device mix, geography, user cohorts; stored in S3 hourly.
• Forecast update: SageMaker retraining 1x weekly, inference 6x daily (6 AM, 10 AM, 2 PM, 6 PM, 10 PM, 2 AM UTC); each run ~5 min on m5.2xlarge (20 CPU).
• Forecast accuracy: MAPE (Mean Absolute Percentage Error) target <10% (±10% variance); CloudWatch dashboard monitors MAPE by segment.
• Pacing controller: Lambda runs every hour (e.g., at HH:00:30); computes pacing_health for all 1000 deals; updates DynamoDB priority table (sorted set of (deal_id, boost_factor)); execution time <30 sec.
• Hourly Lambda invocation: 1000 deals * 1 ms per deal = 1 sec compute; CloudWatch Logs track execution.

Storage:

• Deals table (DynamoDB): ~10 KB per deal (metadata, targeting, CPM, history, make-goods); 1000 deals = 10 MB (in-memory via DAX).
• Served-count log (S3 Parquet): 1000 deals * 24 hours * 30 days = 720K rows; ~100 MB (partitioned by date/hour for Athena queries).
• Forecast history (S3): daily S3 files (10–50 MB each, compressed); 1 year = ~5 TB; queryable via Athena.
• Make-goods table (DynamoDB): ~100 rows per month (10 per day on average); <10 MB.
• Allocation plan cache (ElastiCache): 1000 deals * 24 hours * 50 bytes = 1.2 MB; multiple cache instances for redundancy.

Monitoring:

• Delivery rate by deal (hourly, DynamoDB): alert if <90% of target pace (pacing_health < 0.9) for 2 consecutive hours; SNS alert to sales/ops.
• Make-good accumulation: daily total outstanding; CloudWatch dashboard; alert if >$5M worth (cap enforcement).
• Forecast accuracy (daily, Athena): compare predicted vs. actual supply by segment; retrain SageMaker if MAPE >12% on rolling 7-day window.
• Under-delivery projections: Lambda job at 6 PM UTC compares projected end-of-contract delivery vs. guarantee; alert advertiser 3 days before if projected under-delivery >2%.
• Pacing health distribution: CloudWatch percentile metrics (p50, p95) of pacing_health across all deals; alert if p50 < 0.95 (median deals behind schedule).