[jpollock]

I had a lot of trouble reading that code. I kept getting distracted by the comments and missed the code. The code seems pretty self-explanatory. I have some changes I would make, but they really depend on performance vs depth (modulo the burst vs budget bug).

  // Hit the bucket bottom, let's auto-replenish and try again.
  self.auto_replenish();

Is ugly. Why repeat in English exactly what the code says? I don't even know what language this is, but I know it's replenishing the tokens in the bucket.

All of the comments in reduce are redundant, this is what I would write at the top, so that anyone using the method doesn't have to page through to figure out what it does, it also makes the "smells" more obvious:

  // reduce: attempt to consume tokens from bucket, 
  // starting with one_time_burst, overflowing to 
  // budget. 
  // (keep comment only if _expensive_):Performs
  // auto-replenish when
  // burst is emptied, and budget has insufficient
  // tokens.
  // Asserts size, but only on replenishment.
  // On OverConsumption, entire bucket is emptied. 
  // On Failure, only one_time_burst is emptied.
  // In all cases, tokens is reduced by amount 
  // fulfilled.

I don't understand why OverConsumption is different to Failure. Both will result in throttling by the caller. The reason for the difference should be documented.

I'm also curious why burst is consumed, then budget. I would expect _budget_ to be consumed first (with refill) with overflow into burst? My expectation is for burst and budget to have different refill schedules in auto_replenish, so using burst first would result in more failures by missing refill opportunities.

I'm also curious why the size assertion is only on requests that result in refills. Is it guaranteed that size = max(one_time_burst + budget)? Why care about the difference? Is hogging the tokens "bad"?

Then, I'd work to remove the need for those comments - particularly the need to explain what happens on error - which should be "nothing", or that the bucket is emptied of whatever is available, not something in between.

Finally I'd remove the mutation of tokens, returning either unfulfilled or fulfilled in the return value.

[jpollock]

If we change the code, getting rid of if statements, it's easier to see what happens by removing if's.

I've changed BucketReduction to be a pair, and fixed the strange behavior on error. Swapping "fromBurst" and "auto_replenish" would reduce the number of throttling events. This solution does have more branches than the original, hence readability vs performance. It's still not exception safe, auto_replenish could throw and leave the state undefined.

    BucketReduction reduce(long tokens) {
        long fromBurst = min(tokens, burst);
        burst -= fromBurst;
        tokens -= fromBurst;

        if (tokens > budget) {
            auto_replenish();
        }

        long fromBudget = min(tokens, budget);
        budget -= fromBudget;
        tokens -= fromBudget;

        long totalConsumed = fromBurst + fromBudget;
        if (tokens == 0) {
            return new BucketReduction(Success, totalConsumed);
        }

        if (totalConsumed + tokens > size) {
            return new BucketReduction(OverConsumption, totalConsumed);
        }

        return new BucketReduction(Failure, totalConsumed);
    }

[ainzzorl]

This is a great comment: instead of making generic arguments, you actually tried to show how to do it better. Thank you.

I don't find the comments in the original code distracting, but I do like your version better.

> I'm also curious why burst is consumed, then budget. I would expect _budget_ to be consumed first (with refill) with overflow into burst? My expectation is for burst and budget to have different refill schedules in auto_replenish, so using burst first would result in more failures by missing refill opportunities.

This behavior is documented in the public API [0], so whatever is the reason why it was chosen, I don't think it can ever be changed.

> I don't understand why OverConsumption is different to Failure. Both will result in throttling by the caller. The reason for the difference should be documented.

My understanding is this. If the number of tokens requested is greater than the remaining budget but less than the size of the bucket, the call is rejected and the caller is blocked until it has enough tokens. But if the number of requested tokens is greater than the size of the bucket, the caller will never have enough tokens. Instead of blocking the caller forever, the rate limiter lets the call go through, but then blocks the caller for a while to compensate for the over-consumption. Here's the handling [1]. I wish it was documented better.

[0] https://github.com/firecracker-microvm/firecracker/blob/fc2e...

[1] https://github.com/firecracker-microvm/firecracker/blob/2f92...