4

So my exact case is that I have ~1400 domains on an ancient, self-hosted bind server and I'm looking to migrate them to a hosted service. The trouble is that the hosted service's API has a rate limit of 150 requests per 300 seconds and each domain will require at least 3 requests to migrate. [Note: This API does not provide any quota information, it simply stops working with a generic error message. :I]

If I were to simply hard-code a 2-second sleep between requests I'd end up with 6+ seconds of API calls, plus an additional ~2 seconds to retrieve/reformat records from the legacy server. This clocks me in at around 3.1 hours for the migration, which is a hefty ask.

Another alternative that I considered was adding a $last_call variable that I could use to calculate a sleep to add up to 2 seconds since the last call, but that still doesn't account for the time spent outside of the API client/calls.

Lastly I've tried keeping a list of millisecond timestamps representing each call, counting how many have occurred in the last 300 seconds, and dividing the window equally among them. However I've found that this tends to result in longer-than necessary sleeps at the beginning of the first window, frantically small sleeps at the end, and a call rate somewhat lower than the configured limit. This repeats in a cycle and does not seem to average itself out very much even over the course of a couple hours.

Is there a particular method or algorithm that would be well-suited to more evenly coordinating these requests within the given rate limit?

  • 4
    I know it's not a programming solution, but have you talked to the people running the hosted service? They may well be able to help :-) – Philip Kendall Oct 13 '16 at 18:55
  • Yes, but even so I don't expect them to fully remove the rate limit. Besides that I think that this would be a good bit of code to have in my pocket, in the general case. – Sammitch Oct 13 '16 at 20:13
  • 2
    Is there a requirement for the 150 calls to be equally spaced in the 300s window? If not then just record the start time, make the 150 calls (or less, probably better to not start a new domain migration if it would exceed the limit) as fast as you can (i.e. no sleeps) then just sleep until the next 300s window can start. – Dan Cornilescu Oct 14 '16 at 4:54
  • 2
    I assume you only have to do this once? If so, does it really matter that it will take three hours? – Robert Harvey Oct 14 '16 at 17:42
  • @RobertHarvey "All major maintenances need to happen in the middle of the day, in the middle of the week, because $reasons." ~Management #enterprise #bestdecisions – Sammitch Oct 14 '16 at 18:23
0

A producer consumer. Throttle the producer as that way you don't have to account for execution time in the consumer.

0

So after much floundering I used some math to figure out a function that would sleep for the correct sum of time over the given request, and allow me to ramp it up exponentially towards the end.

If we express the sleep as:

y = e^( (x-A)/B )

where A and B are arbitrary values, then the sum of all sleeps, M, from 0 to N requests would be:

M = 0∫N e^( (x-A)/B ) dx

This is equivalent to:

M = B * e^(-A/B) * ( e^(N/B) - 1 )

and can be solved with respect to A as:

A = B * ln( -1 * (B - B * e^(N/B)) / M )

While solving for B would be far more useful, since specifying A lets you define a what point the graph ramps up aggressively, the solution to that is mathematically complex, and I've not been able to solve it myself or find anyone else that can.

/**
 * @param int $period   M, window size in seconds
 * @param int $limit    N, number of requests permitted in the window
 * @param int $used x, current request number
 * @param int $bias B, "bias" value
 */
protected static function ratelimit($period, $limit, $used, $bias=20) {
    $period = $period * pow(10,6);
    $sleep = pow(M_E, ($used - self::biasCoeff($period, $limit, $bias))/$bias);
    usleep($sleep);
}

protected static function biasCoeff($period, $limit, $bias) {
    $key = sprintf('%s-%s-%s', $period, $limit, $bias);
    if( ! key_exists($key, self::$_bcache) ) {
        self::$_bcache[$key] = $bias * log( -1 * ( ($bias - $bias * pow(M_E, $limit/$bias)) / $period ) );
    }
    return self::$_bcache[$key];
}

With a bit of tinkering I've found that B = 20 seems to be a decent default, though I have no mathematical basis for it. Something something slope mumble mumble exponential bs bs.

Also, if anyone wants to solve that equation for B for me I've got a bounty up on math.stackexchange.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.