Design and Algorithms of an Online Advertising System: Architecture, Coarse Ranking, Budget Control, and Pricing

The advertising system is divided into two major parts: ad placement (including interfaces such as approval, CRM, ad slot management, and operational data analysis) and ad playback (including the ad database, ad delivery stream, retrieval, coarse ranking, and fine ranking). Coarse and fine ranking are key strategy modules.

Figure 7‑3 shows the overall ad system architecture. The AD Mixer acts as an online data integration module that calls the AD Retrieval subsystem to obtain a Top‑N ad list. Coarse ranking is embedded as a plugin in AD Retrieval, scoring and filtering ads after directional retrieval, while fine ranking is embedded as a plugin in AD Mixer for further refinement of the Top‑N list.

Figure 7‑4 illustrates the coarse‑ranking and fine‑ranking processes. During indexing, local indexes are built for O(1) access to ad metadata, a HitIterator provides token‑hit information, and a double‑buffer channel enables incremental updates such as ad de‑activation.

The coarse‑ranking module consumes several data sources: the full‑ad file (containing all ad assets, targeting, bidding, and budget policies), offline CTR (smoothed click‑through rate), offline CVR (conversion rate used for eCPM calculation), and advertiser tier information (used for quality scoring).

In the indexing phase, offline CTR and CVR are used to compute an offline eCPM score, which orders the retrieval results. Retrieval clusters are split by ad ID parity, and newly added or modified ads are routed to a fast‑retrieval cluster. After all clusters finish, results are merged, preferring the regular retrieval path when duplicates occur.

Figure 7‑6 depicts the coarse‑ranking trigger flow. If the candidate list returned by retrieval is too large, it may be truncated and passed to the coarse‑ranking plugin as a local index.

The budget control system (Pacing) allocates an advertiser’s budget over the campaign lifetime, using historical PV/UV data to generate interval targets and a pacing factor to adjust bids. It creates filters based on PV/UV goals, historical bidding performance, and randomization to decide whether an ad enters the auction.

The pricing algorithm adjusts bids to keep ROI stable or improving while increasing GMV. ROI per click is defined as the expected GMV divided by the cost, where expected GMV = p(c|u,a) × â (estimated order value). Overall ROI depends on expected conversion rate, estimated order value, and the adjustable bid.

Constraints ensure that after bid adjustments the eCPM‑based ranking does not change undesirably. The algorithm (shown in code listing 7‑1) sorts ads by the upper bound of the bid range, finds the first ad whose score exceeds the remaining ads, and updates the rest to keep the maximum eCPM.

In summary, advertising strategy is the core module of an ad system; continuous optimization based on real data is required to maximize ROI and maintain a healthy ad ecosystem.