Skip to content

Instantly share code, notes, and snippets.

@kasperkamperman
Created October 18, 2018 11:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kasperkamperman/d9df2fab6e061242c90ed2182c914246 to your computer and use it in GitHub Desktop.
Save kasperkamperman/d9df2fab6e061242c90ed2182c914246 to your computer and use it in GitHub Desktop.
This algorithm spreads out reoccurring (every n minutes) api calls over time, so server load is balanced. It's only the spreading out part.
<pre>
<?php
ini_set('display_errors', '1');
ini_set('error_reporting', E_ALL);
/* This algorithm spreads out reoccurring (every n minutes) api calls over time, so server load
is balanced. It's only the spreading out part.
The whole system uses a database with 60 columns. Each croncall (if we assume one a minute) we read out the
specific column and execute calls that are flagged with 1 (true).
Our callBucket array is the sum of each column.
Each minute we only execute the api calls that are flagged in the time that corrosponds to the column in the database.
Let say we need to do a lot api calls every 30 minutes.
We can make a cronjob and call it every 1st minute and every 30th minute of the hour.
However with 10000 calls we overload our server on those moments, it's better to spread them.
So we make a cronjob that calls our script every minute and then only do several calls.
In my case I need to call a service sometimes every 30, other every 2 minutes etc. I want to spread the load evely.
To simplyfy the numbers I call with cron 6 times an hour to my script (so every 10 minutes).
For each cronCall I make a bucket, so I have 6 callBuckets
x x x x x x
I need to do an api call every 30 minutes. I have the following start possibilities:
1. s - - s - -
2. - s - - s -
3. - - s - - s
Let's say I go for option 1. Then I put a 1 in my callBuckets.
The next time I need to add an api call, I see that the 1st and 4th bucket already are filled.
So it might be better to pick another start time for my other API call, so the algorithm picks
option 2. Etc. Etc.
In the callBuckets I store the amount of api calls that happen at that cron time frame.
*/
// in this case every minute.
// however we could also change this to every 2 minutes
// idea is that it's called in a cron
$cronCallsInAnHour = 60;
// we init the callBuckets array empty.
// for every call there is a bucket that can be filled
$callBuckets = array_fill ( 0 , $cronCallsInAnHour , 0 );
// fill the buckets
$every_n_Calls = 15;
// test with random calls
// in this example every 30 minutes, 15 minutes, 10 minutes, 6 minutes, 2 minutes
// the code will try to spread this in the most even way
$randomCalls = array(30,15,10,6,4,2);
// just add 100000 different call patterns
for ($z=0; $z < 10000; $z++) {
$every_n_Calls = $randomCalls[rand(0,count($randomCalls)-1)];
// -------------------------------------
// init startIndex = 0
$startIndex = 0;
// we make lastSum negative to give it a 'non-configured' flag
$lastSum = -1;
// Walkthrough all possible start positions
// For the selected every_n_Calls
for ($i = 0; $i < $every_n_Calls; $i++) {
$sumOfBuckets = 0; // reset the sum for each start
// so $i is the new startIndex to check
for ($j = $i; $j < $cronCallsInAnHour; $j=$j+$every_n_Calls) {
$sumOfBuckets = $sumOfBuckets + $callBuckets[$j];
}
// if the currentSum is smaller then the last sum, then
// that startIndex is the best to start.
// we use lastSum -1 to fill in the first found sumOfBuckets
if($sumOfBuckets < $lastSum) {
$lastSum = $sumOfBuckets;
$startIndex = $i;
}
else if($lastSum == -1) {
$lastSum = $sumOfBuckets;
}
$lastSum = $sumOfBuckets;
}
// add the api call pattern to the buckets.
// of course we also need to store this call pattern somewhere
// init the callPattern with 0
$callPattern = array_fill ( 0 , $cronCallsInAnHour , 0 );
//echo 'best startIndex for this callPattern: '.$startIndex.'<br/>';
for ($i = $startIndex; $i < $cronCallsInAnHour; $i=$i+$every_n_Calls) {
// so we place a 1 in which call in the 'column' when the api will be called
$callPattern[$i] = 1;
// also update our call buckets
$callBuckets[$i] = $callBuckets[$i] + 1;
};
// show the call pattern
// bring down the amount of calls in the for-loop
// echo join('', $callPattern).'<br/>';
// --------------------------------------
}
echo 'This is how the buckets are filled after spreading out 10000 api call patterns.<br/><br/>';
print_r($callBuckets);
?>
</pre>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment