Laravel Weighted Distribution

Hand things out in a fixed ratio, one at a time, and stay within a fraction of an item of that ratio after every pick.

composer require keaton-php/laravel-weighted-distribution

Laravel discovers the service provider and the facade on its own, and the core also works in plain PHP. At the end of this README, two queue workers route a full day of sales leads to three teams by weight, with daily caps, and every lead comes back with the reason it went where it did.

Splitting traffic by hand

Say you are trying out a new homepage. Half your visitors should see it, three in ten the old page, and two in ten an experiment: a ratio of 5 : 3 : 2. The obvious way is a weighted random pick. Roll a number from 1 to 10, then walk down the list, subtracting each weight, until the roll runs out:

<?php

$pages = ['new-home' => 5, 'old-home' => 3, 'experiment' => 2];

// Seeded, so this README shows the same ten rolls every time it runs.
$random = new Random\Randomizer(new Random\Engine\Mt19937(30));
$visits = [];

for ($visitor = 1; $visitor <= 10; $visitor++) {
    $roll = $random->getInt(1, array_sum($pages));

    foreach ($pages as $page => $weight) {
        $roll -= $weight;

        if ($roll <= 0) {
            $visits[] = $page;
            break;
        }
    }
}

foreach (array_keys($pages) as $page) {
    echo $page, ': ', array_count_values($visits)[$page] ?? 0, PHP_EOL;
}

new-home: 3
old-home: 6
experiment: 1

Over a long run that comes out right on average. Over these ten visitors it gave the old page twice its share and the experiment half of its share.

The same split with the package

<?php

use Keaton\WeightedDistribution\WeightedDistribution;

$pages = WeightedDistribution::make('homepage')
    ->target('new-home', 5)
    ->target('old-home', 3)
    ->target('experiment', 2);

$visits = [];

for ($visitor = 1; $visitor <= 10; $visitor++) {
    $visits[] = $pages->allocate()->target;
}

foreach (['new-home', 'old-home', 'experiment'] as $page) {
    echo $page, ': ', array_count_values($visits)[$page] ?? 0, PHP_EOL;
}

echo PHP_EOL, implode(' ', $visits), PHP_EOL;

new-home: 5
old-home: 3
experiment: 2

new-home old-home new-home experiment new-home old-home new-home experiment old-home new-home

Exactly 5, 3 and 2. make() creates a distribution, target() adds a target with its weight, and allocate() picks the next target and records the pick. There is no dice roll: the split is exact, not right on average. The last line is the order the visitors went in, with the new page spread through the run rather than bunched at the start.

Why that's better

It is right at every step, not only at the end

Ten visitors is a short run. Here are 1,000 visitors each way, checked after every single visitor for the furthest any page had drifted from its exact share:

<?php

use Keaton\WeightedDistribution\WeightedDistribution;

$pages = ['new-home' => 5, 'old-home' => 3, 'experiment' => 2];

// The furthest any page ever got from its exact share, checked after every visitor.
$worstDrift = function (array $visits) use ($pages): float {
    $seen = array_fill_keys(array_keys($pages), 0);
    $worst = 0.0;

    foreach ($visits as $index => $page) {
        $seen[$page]++;

        foreach ($pages as $name => $weight) {
            $exact = ($index + 1) * $weight / array_sum($pages);
            $worst = max($worst, abs($seen[$name] - $exact));
        }
    }

    return $worst;
};

// 1,000 visitors the hand-written way...
$random = new Random\Randomizer(new Random\Engine\Mt19937(30));
$byHand = [];

for ($visitor = 1; $visitor <= 1000; $visitor++) {
    $roll = $random->getInt(1, array_sum($pages));

    foreach ($pages as $page => $weight) {
        $roll -= $weight;

        if ($roll <= 0) {
            $byHand[] = $page;
            break;
        }
    }
}

// ...and with the package.
$distribution = WeightedDistribution::make('homepage')
    ->target('new-home', 5)
    ->target('old-home', 3)
    ->target('experiment', 2);

$withPackage = [];

for ($visitor = 1; $visitor <= 1000; $visitor++) {
    $withPackage[] = $distribution->allocate()->target;
}

printf("By hand:      off by up to %.1f visitors\n", $worstDrift($byHand));
printf("The package:  off by up to %.1f visitors\n", $worstDrift($withPackage));

By hand:      off by up to 14.0 visitors
The package:  off by up to 0.6 visitors

With three targets the package is never more than three quarters of an item away from any target's exact share, after any number of picks. With two targets the bound is half an item, and however many targets there are, it stays below one. That holds while the same targets are in play; caps change the set, as the hard parts explain. The random pick wandered fourteen visitors off. How it works has the rule and where the bound comes from.

Every pick explains itself

allocate() returns a Decision. Its target is the name that was picked, and explain() says why:

<?php

use Keaton\WeightedDistribution\WeightedDistribution;

$pages = WeightedDistribution::make('homepage')
    ->target('new-home', 5)
    ->target('old-home', 3)
    ->target('experiment', 2);

$decision = $pages->allocate();

echo $decision->target, PHP_EOL;
echo $decision->explain(), PHP_EOL;

new-home
Allocation #1: 'new-home' was chosen. It was owed 0.50 of an allocation (slot 1 of 10 in this cycle) and had the earliest deadline of the 2 targets due one. Not due one yet: experiment.

"Owed" is how far behind its exact share a target is, counting this pick: on the first visitor, new-home is owed half a visitor, old-home 0.3 and experiment 0.2. A target is only due a pick once it is owed enough (with three targets, a quarter of an item), which is what stops anyone running ahead of their share. Here two were due, and new-home won on the earliest deadline, which is how the package chooses between targets that are due.