Migration load distribution among partially loaded servers

Question

I am working with clusters of servers that host users who each generate significant, but varying amounts of load. For each user, I have a load metric. Each server can host a number of users until it reaches a maximum load limit. For example:

User | Server | Load
--------------------
A    |     10 | 107
B    |     10 |  59
C    |     11 | 341
D    |     11 |  95
E    |     12 |  88
F    |     12 | 215

Server 10 load = 166, server 11 load = 436, and server 12 load = 303. I am working on a PHP script that would migrate clients from one cluster to another, and needs to distribute users among destination servers.

Preferably, users would be added to server 10 (least loaded) until it roughly equalled server 12 (second least loaded). Then users would be added to both 10 and 12 until they equalled 11. Once all servers were equal in load, migrating users would be evenly distributed.

As mentioned, I am using PHP. User and Server data comes from a database in the following form:

$users = Array ( [0] => Array ([user] => 'A', [server] => '10', [load] => 107), [1] => ... etc
$servers = Array ( [0] => Array ([server] => '10', [load] => 166), [1] => ... etc

I could use some help designing a function (even just conceptually) to distribute users among servers when migrated from one cluster to another. While my example is simple, I am working with tens of thousands of users on hundreds of servers in dozens of clusters.

Answer 1

I found a good solution. The complicating factor was actually due to the structure of the data. To distribute users evenly, I first converted the server data to a single array of key (server) => value (load) pairs.

//Input like: Array ([0]=>Array([server]=>'10',[load]=>166),[1]=>Array([server]=>'11',[load]=>'436'), ...) 
function rekey ($multiArray, $key, $value) {
    $newArray = Array();
    foreach ($multiArray as $array) {
        $newArray[$array[$key]] = $array[$value];
    }   
    return $newArray;
    //Output like: Array([10]=>'166', [11]=>'436', [12]=>'303')
}

Once that has been converted, I can use the PHP min built-in.

function loadDistribute ($users, $servers) {
    $len = sizeof($users); //Find the length of the users array
    for ($i = 0; $i < $len; $i++) { //Using traditional for loop to make index available
        $server = array_keys($servers, min($servers)); //Get the key (server-id) for the least loaded server
        $users[$i]['server'] = $server[0]; //Change the assigned server for the user
        $servers[$server[0]] += $users[$i]['load']; //Add the users load to the server
    }   
    return $users; 
}

Once implemented with my other code, output is something like this:

User Z (load 652) assigned to server 10
User Y (load 0) assigned to server 12
User X (load 35) assigned to server 12
User W (load 311) assigned to server 12
User V (load 98) assigned to server 11

You can see that it is working, because 3 users in a row are assigned to server 12--until server 12 had greater load than 11, it kept receiving users.