How often have you thought of a joke minutes or hours too late? Advertisements work the same way. To be relevant to customers, ads must be pertinent to the moment, to the topics of interest right now.
Our business depends on us being relevant hundreds of millions of times per day. If you’re interested in how highly scalable systems work, this post will describe some of the challenges and the systems we’ve evolved to tackle them.
Finding relevance in a stream of bid opportunities
The ability to bid on a massive volume of inventory in real-time requires a highly available, fault tolerant, distributed system. Any bid opportunity could be the perfect needle in the haystack, thus the system needs to analyze every single opportunity to make sure we don’t miss out on relevant ad placements. To find all those needles, Quantcast’s systems take on average only about 10 milliseconds to evaluate and respond to each of the millions of bidding opportunities flowing through the system every second.
A key part of making real-time decisions to purchase ad inventory is evaluating the user’s expected interest in a particular advertising product. Think of this as identifying a relevant audience for an advertising campaign. Determining such an audience for each campaign can be done offline or in real-time. In this post we will take a trip through the evolution of Quantcast’s audience targeting system and give a brief overview of the underlying infrastructure that makes our current real-time approach possible.
Real-time bidding architecture
Let’s start by framing the real-time bidding problem within a basic structure, shown in the following diagram. In yellow, we have external components, real-time systems are blue, and we show parts of the control system in purple. We’ll continue to use this color coding as we expand upon the details below.
- Advertising Exchanges – send bid opportunities to Quantcast’s bidding system containing information on the advertisement up for auction, like the cookie ID, and the website on which the ad will show
- Bidding System – receives bid opportunities from advertising exchanges, looks up additional cookie data, evaluates bid opportunities across thousands of advertisers and sends bids back to the advertising exchanges
- Control System – optimizes spend across all active advertiser campaigns at a variety of time scales
The life of a bid opportunity
The bidding system is made up of several integral parts, which are outlined in the diagram below.
Looking at the path a bid opportunity takes, there are some serious challenges to bidding in real-time. When an advertising exchange offers a bid opportunity for a cookie, our system needs to respond with a bid in tens of milliseconds, or risk the exchange rejecting our bid due to lag. In this timeframe a lot needs to happen.
- Bid opportunity parsing – Translates raw bid opportunities into a Quantcast-internal format that is understood by all other parts of the bidding system. This is useful because every ad exchange behaves differently and provides different metadata along with their bid opportunities.
- Filtering – Blocks fraudulent behavior and ensures brand safety. We analyze each bid opportunity because we care deeply about delivering high-quality ads on websites that are safe for our users and our advertisers.
- Scoring – Estimates how relevant particular ads are for this bid opportunity. In our distributed scoring system, many different scorers work in parallel to determine which ad would be most interesting to the user.
- Bid calculation – Converts scores into dollar amounts. How much Quantcast bids on a particular bid opportunity depends on a number of factors, like how competitive the market is, the size of the campaign’s budget, and how many impressions a campaign should serve. Choosing an optimal bid price involves a feedback loop with the control system.
- Internal auction – Selects a winning bid from all campaigns.
- Bid formatting – Sends a finalized bid to the advertising exchange in the proper format.
Given that this complex process is occurring for each bid opportunity, we turn to examining designs for scoring bid opportunities and their inherent tradeoffs in efficiency, complexity, and quality of targeting.
Cookie lists in real-time bidding
Several years back, our bidding system consumed pre-determined lists of cookies that were relevant to each advertising campaign, and used those cookie lists to make bid decisions. Cookie lists define an audience: they represent a set of users that meet some criteria and are still used frequently in the industry.
The creation of such cookie lists for all advertising campaigns requires two additional systems:
- Model training – uses machine learning algorithms, domain-specific knowledge, and a massive amount of online behavioral data to train models of user behavior. These models describe which audiences are most relevant for each of the campaigns we run.
- Offline scoring – scores the billions of cookies Quantcast can access against each of the models. For each campaign, this tells us which users would be most likely to engage with ads for that campaign. Once all cookies are scored we pick the top N cookies as the most relevant audience for that campaign, and then ship the list of scored cookies for each campaign from our MapReduce cluster into the bidding data centers.
In the bidding system, we retrieve the scores via a simple lookup for a user ID as bid opportunities become available.
Benefits of offline cookie scoring
This approach, which we will refer to as offline cookie scoring, is simple because we offload the difficult task of determining the set of relevant cookies to a MapReduce-based batch job. In the real-time bidding system, this makes responding to bid opportunities computationally cheaper. Only bid opportunities for cookies contained in at least one cookie list need to be bid upon externally. Scoring each bid opportunity boils down to a simple lookup operation for each cookie that maps to campaign-specific lists, and is very efficient compared to the alternative of evaluating thousands of complex models in the bidding system rather than offline.
Drawbacks of offline cookie scoring
However, this system also has significant drawbacks. Quantcast’s core value proposition is to serve highly engaging ads to relevant audiences. This system comes with an inherent lag between scoring a set of cookies in offline jobs and actually using the computed data when responding to a bid opportunity. Before bidders can take action on this new data set, large-scale cookie lists have to be shipped across the internet from our MapReduce cluster to the data centers that house our real-time bidding infrastructure. This lag can cause cookie scores to be stale – consumers that were in-market at the time of scoring may no longer be interested in a particular product. In other words, by the time the list is available for bidding, some cookies have already stopped exhibiting in-market behavior.
One interesting impact here is on modeling targeted behavior such as conversions. There is little value in building responsive models that can evaluate short term behaviors for an in-market audience if there is a fundamental delay in delivering user data to bidders. Knowing in advance that we can’t act upon a behavioral cue for many hours limits us to longer time-scale behaviors, which may be less targeted. Using conventional offline cookie scoring, showing ads at appropriate times for short-term in-market behaviors is difficult, so modeling must incorporate known time lags and look for the longer time-scale signals rather than real-time signals.
Operationally, as the number of advertisers grows, the size of these cookie lists becomes less manageable. Furthermore, cookies on a list may disappear and not be seen again; if lists grow older, it may become difficult to deliver ads as the available cookie pool shrinks.
Real-time scoring
Compare this offline scoring design with scoring bid opportunities for cookies in real-time.
This real-time evaluation better achieves Quantcast’s value proposition of showing the most relevant ads to users, but comes at the cost of additional infrastructure.
Consider a cookie that only seconds ago exhibited in-market behavior for a particular product and now has bid opportunities offered on an ad exchange. If we can take the recent behavior into account, we can get an even better estimate of the true value of showing a relevant ad to this user.
In the offline scoring framework, the computation of bid-quality scores is a simple lookup for each cookie. Scoring cookies in real-time is a bit more complex: our bidders must apply machine learning algorithms for all advertising campaigns to each bid opportunity within milliseconds. This requires additional components to the real-time infrastructure:
- Model store – stores over 50,000 models built in offline training, accessible in real-time.
- Real-time featurizer – collects behavioral user data from Quantcast Measure in real-time and emits feature vectors. These features are used by the models and describe the user’s behavior in a machine-readable way that is very compact and can be processed very efficiently.
- Keebler – provides fast access to essential cookie data. At peak, Keebler handles over 2 million reads and over 4 million writes per second.
Operationally, real-time scoring changes the storage and computational requirements. Scoring each bid opportunity across all advertisers requires significantly more computation: instead of doing a single lookup, the bidder now needs to process hundreds or thousands of features. The complexity of scoring thousands of models scales with the number of features and the algorithmic complexity of the model.
Real-time scoring requires creating and accessing real-time features for billions of cookies, all within milliseconds. We must make choices about the amount of data to store per cookie and about the prioritization of features when we reach our storage limits.
When Quantcast introduced real-time scoring for performance targeting campaigns, we ran a series of A/B tests. We saw significant improvements: an average of 23% improvement in cost per acquisition. The system was able to capitalize on real-time signals and show advertisements at the most relevant times to the benefit of consumers, publishers, and advertisers.
This is only the beginning
At Quantcast, we’ve transitioned many processes to our real-time systems to remain responsive to the markets and able to better deliver value to our customers. This not only includes bidding, delivery control systems, and bid opportunity scoring, but also other essential components such as fraud detection, retargeting bookkeeping, frequency capping, and more.
Summary
Quantcast delivers the most relevant ads to the most engaged audience. We use massive amounts of data to train complex models that can predict user behavior with incredible precision.
We’ve shown that one way of scoring such complex models is an offline approach using large clusters of dedicated machines. MapReduce jobs are able to capitalize on the complexity of our models and can easily analyze billions of cookies to find the very best match for our customers.
However, offline model scoring introduces a significant delay between when we observe user behavior and when we are able to act upon that data. Real-time scoring addresses those shortcomings. At Quantcast, we score models in real-time, because it allows us to deliver a relevant ad just seconds after observing important user behavior.
Real-time scoring comes at a price, though. Quantcast bidders score billions of features every second, instead of relying on pre-generated cookie lists. Our real-time scoring systems are more complex than setups that rely on offline scoring, and we need to constantly adjust and refine our scoring to react to fluctuations in the market.
Interested in engineering at Quantcast? Check out our current openings.