By Sanjay Agarwal, Engineering
I am the engineering lead on building the Adserving platform at Drawbridge, and would like to share some insights on building an efficient campaign targeting engine for Adservers.
Our Adservers receive requests from a variety of supply partners and often have strict SLA requirements governing the response we return, which can be as aggressive as 75 milliseconds. Our Adserver is built using open source java frameworks, augmented by proprietary technologies. One of the main problems we needed to solve when processing Ad requests was to find the campaigns eligible to run on a given Ad request based on targeting criteria specified by Advertisers.
At a high level, each request needs to process the following before returning a response:
- Extract a set of attributes related to the ad impression, such as device type, location, ad size, user attributes, etc
- Find the campaigns that qualify to serve on this impression. This is also known as applying the campaign targeting.
- Filter out campaigns that don’t have enough budget
- Filter out campaigns that have reached daily frequency cap set by Advertisers
- Predict revenue for these campaigns using prediction models
- Choose a campaign and return an ad response.
We are going to focus on the in-house technology we built for applying campaign targeting for an Ad request.
What is Campaign Targeting?
Given Ad request level attributes (for example, device_type = iphone, and country = US), we need to find the campaigns that are eligible to run on this impression. In this example, campaigns that are targeting device type as iphone OR did not specify device_type targeting are eligible for device_type = iphone. The eligible campaigns must also target US OR not use country targeting at all. When a campaign doesn’t specify targeting for an attribute, we call it “Don’t Care” or DNTC for short.
For a request with:
- device_type = iphone
- country = US
Campaigns that satisfy each of the following criteria are eligible too on this request:
- device_type = iphone OR device_type = DNTC
- country = US OR country = DNTC
We allow targeting on many attributes, some of which are:
- device_type (iphone, ipod, android_phone, etc)
- country, state, city
- platform (app, mobile_web, pc_web)
- make, model of device (such as Samsung, Galaxy)
- User attributes, such as demo_age, demo_gender etc.
- And many others ..
Mapping Campaign Targeting to a Search Problem
We mapped the targeting problem to a search problem, where each campaign is treated as a “Document” and each request is treated as a “Query”. Each request can be translated as a query, having a set of key-value pairs where key is attribute-name and value is its value. Over time, new targeting attributes can be added to the system, which will just translate to a new key-value pair.
We evaluated open source frameworks such as SOLR for executing this kind of search, but found it to be too CPU intensive for our needs. The reasons for this are:
- SOLR is designed for full text search, and is not optimized for exact match queries
- There is ranking function built into the index, which is not necessary for our needs. For Ad serving, we need to rank the campaigns after search using revenue or profit models.
- The query is represented in String form, which needs to be parsed before execution, which adds to CPU consumption
To solve this search problem in an efficient way, we wrote an in-memory reverse index based search framework. It works as follows:
- On a server startup, build a reverse index of attribute values to docId (campaignId in our case)
- Expose an API to pass in the query attributes in form of key-value pairs, creating a more efficient way to process the query parameters.
- The index is maintained in-memory. If the campaign targeting is changed when the server is running, the server can incrementally load the changes and update the index online.
- The index returns all documents that match the query. Documents are not ranked and any document that is returned is guaranteed to satisfy the search criteria.
Search Framework Internals
Let’s dive into the internals with an example.
For campaign_id = 1
For campaign_id = 2
||iphone, ipod, ipad
For campaign_id = 3
The search index will be built like the following on initialization, where for each attribute, we build a mapping of distinct attribute values pointing to a list of campaign_ids.
iphone -> 1,2
ipod -> 2
ipad -> 2
DNTC -> 3
US -> 2
DNTC -> 1,3
app -> 1,2
mobile_web -> 2,3
DNTC -> NULL
ATT -> 1,3
DNTC -> 2
male -> 1
DNTC -> 2,3
Let’s say an Ad request maps to the following query
device_type = iphone
country = US
platform_code = mobile_web
carrier = ATT
demo_gender = male
We start with all active campaign_ids and the following algorithm is executed:
- Start with all active campaignIds in the system
- For each request.attribute_type, take the union of request.attribute value and DNTC. This finds the campaignIds that either match directly with request or have not specified targeting for this attribute_type
- Take the intersection of campaignIds from step 2 against step 1.
- Repeat Step 2,3 for all request attribute types.
In this example, this is how we will find the eligible campaigns
Start with eligible_campaign_ids = 1,2,3
For device_type=iphone OR DNTC, matching campaignIds = 1,2. eligible_campaign_ids = 1,2,3
For country = US OR DNTC, matching campaignIds = 1,2. eligible_campaign_ids = 1,2,3
For platform_code = mobile_web OR DNTC, matching campaignIds = 2. eligible_campaign_ids = 2,3
For carrier = ATT OR DNTC, matching campaignIds = 1. eligible_campaign_ids = 2,3
For demo_gender = male OR DNTC, matching campaignIds = 1,2. eligible_campaign_ids = 2,3
So, campaign_ids 2,3 are eligible to serve on this request. They will be further evaluated for budget and predicted revenue and a winner will be chosen based on a ranking function.
Using an efficient in-memory search index, we built a generic campaign targeting search index. The framework itself is generic and can be used in other applications also. The framework exposes java APIs for indexing new documents and performing search using key-value pairs. We already use the framework for multiple applications in our systems.
Checkout our jobs page: http://drawbrid.ge/jobs