Extension:CentralNotice/Allocation system/Notes
Current algorithm (2014-11-13)[edit]
BannerChooser::__construct()
[edit]
Gets everything ready for banner selection via a slot.
- Receives an
AllocationContext
and puts it inBannerChooser::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 toBannerChooser::chooseBanner()
, which makes the final choice based a slot.
BannerChooser::filterBanners()
[edit]
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()
[edit]
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 themax_allocation
. If the campaign is throttled to 50%, the banner'smax_allocation
will be 0.166666. - Makes an index of banners by their campaigns' priority (
cn_notices.not_preferred
, which is referred to here ascampaign_z_index
and uses the values of constants in theCentralNotice
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 themax_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.
- At each level we will set all the banners' allocation to
- 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()
[edit]
Prepares allocation data for actual banner selection using a limited number of slots.