Skip to content

Instantly share code, notes, and snippets.

@ngugijames
Created May 16, 2016 13:44
Show Gist options
  • Save ngugijames/b2dfd5de651d793850bad2d695a60667 to your computer and use it in GitHub Desktop.
Save ngugijames/b2dfd5de651d793850bad2d695a60667 to your computer and use it in GitHub Desktop.
A simple implementation of the Weighted Round-Robin Scheduling in PHP ( PHP >= 5.3 )
<?php
/**
* @author Alexis Gruet
*
* A simple implementation of the Weighted Round-Robin Scheduling in PHP 5.3+
*
* The weighted round-robin scheduling is designed to better handle servers with different
* processing capacities. Each server can be assigned a weight, an integer value that
* indicates the processing capacity. Servers with higher weights receive new connections
* first than those with less weights, and servers with higher weights get more connections
* than those with less weights and servers with equal weights get equal connections.
*
* Note :
* composer is required
* array_column is required - use ./composer.phar require rhumsaa/array_column:~1.1
* predis is required - use ./composer.phar require predis/predis:~0.7.3
*
*
* $aProvider represents an array of partners with their associated weights.
*
* For example, the partners, 1, 2 and 3, have the weights, 4, 3, 2
* respectively, a scheduling sequence will be 1 1 2 1 2 3 1 2 3 in a scheduling
* period (mod sum(w(provider))).
*
* Useful when you want to send smartly balanced traffic to a remote api or something else
*
* @see http://kb.linuxvirtualserver.org/wiki/Weighted_Round-Robin_Scheduling
*/
const __I__ = 'round-robin-dispatch-i';
const __CW__ = 'round-robin-dispatch-cw';
require __DIR__ . '/../vendor/autoload.php';
$c = new \Pimple;
/**
* Registering predis
*/
$c[ 'predis' ] = (function () {
return new Predis\Client( array(
'scheme' => 'tcp',
'host' => '127.0.0.1',
'port' => '6379'
));
});
/**
* A list of partners with their associated weights
*/
$aProvider = array(
0 => array(
'provider' => 'partner1',
'weight' => 4 ),
1 => array(
'provider' => 'partner2',
'weight' => 3 ),
2 => array(
'provider' => 'partner3',
'weight' => 2 )
);
/**
* A simple array used for stats
*/
$aStats = array(
'partner1' => 0,
'partner2' => 0,
'partner3' => 0,
);
/**
* Weighted round robin algorithm
*/
$wrr = function() use( $c, $aProvider ) {
$n = count( $aProvider );
$i = $c[ 'predis' ]->exists( __I__ ) ? $c[ 'predis' ]->get( __I__ ) : -1;
$cw = $c[ 'predis' ]->exists( __CW__ ) ? $c[ 'predis' ]->get( __CW__ ) : 0;
/**
* greatest common divisor of all provider weights;
*/
$gcd = function() use ( $aProvider ) {
$gcd = function ( $a, $b ) use ( &$gcd ) {
return $b ? $gcd( $b, $a % $b ) : $a;
};
return array_reduce( array_column( $aProvider, 'weight' ), $gcd );
};
/**
* get the max weight across the whole providers
*/
$max = array_reduce( $aProvider, function( $v, $w ) {
return max( $v, $w[ 'weight' ] );
}, -9999999 );
/**
* get the weight of a specific provider
*/
$w = function( $provider ) use ( $aProvider ) {
return $aProvider[ $provider ][ 'weight' ];
};
while( 1 ) {
$i = ( $i + 1 ) % $n; $c[ 'predis' ]->set( __I__, $i );
if ( $i == 0 ) {
$cw = $cw - $gcd(); $c[ 'predis' ]->set( __CW__, $cw );
if ( $cw <= 0 ) {
$cw = $max; $c[ 'predis' ]->set( __CW__, $cw );
if ( $cw == 0 ) {
return NULL;
}
}
}
if ( $w( $i ) >= $cw ) {
return $aProvider[ $i ];
}
}
};
for ( $k=1;$k<=100;$k++ ) {
$current = $wrr();
echo '----------------------' . PHP_EOL;
echo 'Iteration :: ' . $k . PHP_EOL;
echo 'Will be sent to :: ' . $current[ 'provider' ] . PHP_EOL;
$aStats[ $current[ 'provider' ] ]++;
//sleep( 1 );
}
echo PHP_EOL;
echo PHP_EOL;
echo 'Statistics' . PHP_EOL;
echo '---------------------------------------' . PHP_EOL;
print_r( $aStats );
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment