Not waiting sufficient time

[udf2457]

$throttle = new Stiphle\Throttle\LeakyBucket;
for ($i = 1; $i <= 100; $i++) {
$throttle->throttle('x', 2, 20000).PHP_EOL;
echo time().PHP_EOL;
}

Gives an output of:

1552774090
1552774090
1552774100
1552774110
1552774120
1552774130

1552774100-1552774090=10, so we're doing more than 2 in a 20 second period ?
Same goes fo the rest, they go up in to second increments 00,10,20,30....

(PHP PHP 7.2.16 on Linux)

[davedevelopment]

I think that's just an artefact of the leaky bucket method, the first one almost doesn't really count, as it's the only one to have happened in the previous 20 seconds? If you ignore the first couple, I would expect to see one every ten seconds, which is what is happening?

[villermen]

I think that's just an artefact of the leaky bucket method

@davedevelopment Isn't the whole analogy that drops should leave at a fixed rate? In this implementation if I want to enforce a limit of 100/s I have to set the limit to 50/s. An initial burst of 50 will be accepted without delay every time the bucket is empty. Remaining drops will then leave the bucket at the rate of 50/s, totalling 100/s which is very counterintuitive in my opinion.

[davedevelopment]

@villermen the analogy is yes, but if you take a look at the wikipedia page, there are two ways of using it, as a meter and as a queue. The way we use it here is a meter. Or at least I think so, it seems like forever since I looked at this stuff 😊

[villermen]

@davedevelopment The article mentions nothing about bursts allowed to go out, only bursts coming in. That is a side effect of discarding excess drops, which also doesn't happen here.

• A fixed capacity bucket, associated with each virtual connection or user, leaks at a fixed rate.
• If the bucket is empty, it stops leaking.
• For a packet to conform, it has to be possible to add a specific amount of water to the bucket: The specific amount added by a conforming packet can be the same for all packets, or can be proportional to the length of the packet.
• If this amount of water would cause the bucket to exceed its capacity then the packet does not conform and the water in the bucket is left unchanged.

[davedevelopment]

@villermen I don't understand. As far as I recall, the leaky bucket implementation here leaks at a fixed rate as described. The burstiness has nothing to do with leaking at a fixed rate, the burstiness is about the size of the threshold. For the example above, the threshold is 2, and the leak rate is 1 every 10 seconds. So we can burst 2 packets instantaneously, but then would have to wait 10 seconds for the first packet to leak out, at which point another 1 packet could pass.

[villermen]

@davedevelopment Yes, but in this case there is no distinction between burst limit and limit per interval. The effective limit is therefore always double the limit specified:

$throttle = new \Stiphle\Throttle\LeakyBucket();

$i = 1;
for ($j = 0; $j < 10; $j++) {
    $waitMs = $throttle->throttle('niceKeyThanks', 5, 10000);

    if ($waitMs) {
        echo $waitMs . 'ms | ';
    }

    echo $i++ . ' | ';
}

1 | 2 | 3 | 4 | 5 | 2000ms | 6 | 2000ms | 7 | 2000ms | 8 | 2000ms | 9 | 1999ms | 10 | 

So even though I specify a limit of 5/10s, 10 packets get through in 10 seconds. This feels a lot like the token bucket algorithm where tokens are saved up and replenished at the given rate only when there is space for them.

[davedevelopment]

@davedevelopment Yes, but in this case there is no distinction between burst limit and limit per interval. The effective limit is therefore always double the limit specified:

Agreed that a distinction is not clearly made in the parameters, but the effect can still be achieved it's only for the initial burst were the rate is "doubled", but thereafter the average is steady.

Regarding the token bucket algorithm, that's correct, the wikipedia page says of the leaky bucket as a meter and the token bucket algorithm:

As can be seen, these two descriptions are essentially mirror images of one another

[villermen]

@davedevelopment I see. I think I had my mind set too much on my own use case and assumed the limit could not be breached for any given timeframe. Either way it might be useful to add a sidenote to the first code example to prevent confusion for people like me ~~.