Extension:CentralNotice/Allocation system/Notes

Current algorithm (2014-11-13)

BannerChooser::__construct()

Gets everything ready for banner selection via a slot.

• Receives an AllocationContext and puts it in BannerChooser::allocContext.
• Uses project, language and country data to get an array of appropriate campaigns from Campaign::getCampaigns().
• Sends this array of campaigns to Banner::getCampaignBanners() to get the Cartesian product of known devices and the banners assigned to those campaigns.
• Calls BannerChooser::filterBanners().
• Calls BannerChooser::allocate().
• After these steps, BannerChooser::banners is fully prepared for the call to BannerChooser::chooseBanner(), which makes the final choice based a slot.

BannerChooser::filterBanners()

Works on BannerChooser::banners , removing banners that aren't available to the user, based on the device, logged-in status and bucket set out in BannerChooser::allocContext.

BannerChooser::allocate()

Prepares filtered BannerChooser::banners for the final banner selection by adding properties and re-ordering them (in call to BannerChooser::quantizeAllocationToSlots()).

• Calculates total the weights (cn_assignments.tmp_weight, set via the "Weight" control next to the banner assignment on the UI) of remaining banners for in campaign.
• Adds the max_allocation property to each banner. This is done by calculating the banner's weight relative weight in relation to the total weights for the campaign, then taking a fraction of that as determined by the campaign's throttle (cn_notices.not_throttle, set via the "Limit traffic" control in the UI). For example, if a banner's weight in this campaign is 25, and the total weights for the campaign is 75 (because there's another banner available in the same bucket with a weight of 50), the banner's relative weight will be 0.333333. If the campaign is not throttled, that will be the max_allocation. If the campaign is throttled to 50%, the banner's max_allocation will be 0.166666.
• Makes an index of banners by their campaigns' priority (cn_notices.not_preferred, which is referred to here as campaign_z_index and uses the values of constants in the CentralNotice class).
• Calculates the sum of the max_allocation s of all the banners at each priority level. Since priority levels are set per campaign, and all the max_allocation s of every campaign will add up to 1 for campaigns that are not throttled, and less for campaigns that are throttled, the sums per priority level will the number of campaigns at that priority level, or less, if one or more of them are throttled.
• Sorts, by priority in descending order, the index of banners by priority.
• Divvy up the allocation pie. Full allocation is 1, set in $remainingAllocation . Cycle through the index of banners by priority from highest to lowest priority.
  • At each level we will set all the banners' allocation to max_allocation , or, if there isn't enough allocation space left over, all the banners' allocations will be proportionately scaled down to take up whatever space there is.
  • The scaling down works like this: before setting allocations at each level, see if the sums for the max_allocation s for that level are greater than $remainingAllocation . If they are, consider allocation to be used up, and set a scaling variable to scale down the remaining allocations to use up exactly the remainder.
  • Once allocation is used up, all banners at lower levels are eclipsed, getting 0 allocation.
• In summary, this means that without throttling, the campaigns at a higher priority level will share allocation equally, and will eclipse all the campaigns at lower priority levels. Only with throttling can there be unequal allocation among campaigns at the same level, and trickle-down of some allocation to lower levels.
• Calls BannerChooser::quantizeAllocationToSlots().

BannerChooser::quantizeAllocationToSlots()

Prepares allocation data for actual banner selection using a limited number of slots.