Software Engineer, Ads L4

I was asked Ads Frequency Capping problem for system design.

Requirements

• On ad request, check if the candidate ad can be shown
• The system should allow configurable cap rules (per user per ad, per user per campaign, etc)
• After the ad is served, the system should record the ad impression
• The system should support multiple time windows (1h, 1d, 7d, 30d)

The interviewer let me answer the question and stayed silent throughout. He interrupted once to ask what counting algorithm/strategy would you use to update the ad counter. I gave them 3 algorithms:
Counting algorithm:

1. Fixed window buckets
   Key = {userId}:{entityId}:{window}:{bucket}
   Value = count of times when the ad was served to the user

   Con : Since it is a fixed window bucket, the cap service can overserve during boundaries
   For example : 1hr buckets => 9:59 5 ads shown to the user => 10:01 5 ads shown again =>
   Instead of 5 ads per hour, we showed the user 10 ads in 3 minutes.

2. Sliding Window Sorted Set
   Instead of storing the count, we can store the timestamps of the actual impression.
   Key = {userId}:{entityId}:{window}:{bucket}
   Value = set(timestamp) when the ad was shown
   To check the cap, remove all timestamps older than now - windowSize, then count the remaining entries

   Memory : Each user x entity x window combination stores 1 entry per impression
   For 7 day window => 7 * 10 = 70 impressions per day.
   For a 30 days window across 50M users and thousands of entities, this would not scale.
   This would be ideal for short windows (1h, 1d) where accuracy matters most

3. Sliding window counter (bucketed approximation)
   Key = {userId}:{entityId}:{window}:{bucket}
   Value = count of times when the ad was served to the user

   When checking the cap, sum the buckets that fall within the rolling window.
   For example : at 9:30, look at the current hour + 50* count of previous hour
   Error : cap * (bucketSize/windowSize)

   Memory : For 7 day window with 1 hour buckets : 7*24 = 168 keys per user per entity
   This would work for longer windows (7d, 30d) because the error would be negligible