Algorithme de distribution équilibrée

Question

Je travaille sur du code pour un cluster faiblement couplé. Pour obtenir des performances optimales pendant les tâches, le cluster remappe ses données chaque fois qu'un enfant entre ou sort. Cela sera éventuellement rendu optionnel, mais pour l'instant il effectue son équilibrage de données par défaut. Mon équilibrage consiste simplement à s'assurer que chaque enfant n'a jamais plus que le nombre moyen de fichiers par machine, plus un. Le plus un est pour le reste si la division n'est pas propre. Et puisque le reste sera toujours inférieur au nombre d'enfants [sauf 0 cas, mais nous pouvons exclure que], les enfants après un équilibrage auront au plus avg + 1.

Tout semble bien, jusqu'à ce que je réalise mon algorithme est O (n!). Descendez la liste des enfants, découvrez la moyenne, le reste, qui en a trop et qui en a trop peu. Pour chaque enfant dans la liste trop, passez par la liste, envoyez à chaque enfant qui a trop peu.

Y a-t-il une meilleure solution à cela? Je pense qu'il doit y avoir.

Edit: Voici quelques psuedocode pour montrer comment je tirais O (n!):

foreach (child in children) { 
    if (child.dataLoad > avg + 1) { 
     foreach (child2 in children) { 
      if (child != child2 && child2.dataLoad < avg) { 
       sendLoad(child, child2) 
      } 
     } 
    } 
} 

Edit: O (n^2). Foreach n, n => n * n => n^2. Je suppose que je n'ai pas eu assez de café ce matin! ;)

À l'avenir, je voudrais passer à une méthode de distribution plus flexible et résiliente [poids et hibernation], mais pour l'instant, une distribution uniforme des données fonctionne.

Answer 1

@zvrba: Vous n'avez même pas à trier la liste. Lorsque vous parcourez la liste la deuxième fois, déplacez simplement tous les éléments avec moins de charge de travail moyenne à la fin de la liste (vous pouvez garder un pointeur sur le dernier élément lors de votre première traversée). L'ordre ne doit pas être parfait, il change juste quand les itérateurs doivent être augmentés ou diminués dans votre dernière étape.

See previous answer

La dernière étape ressemblerait à quelque chose comme:

Dans la deuxième étape garder un pointeur vers le premier élément avec moins de charge de travail moyenne child2 (pour éviter la nécessité d'avoir une liste à double liaison).

for each child in list { 
    if child2 == nil then assert("Error in logic"); 
    while child.workload > avg + 1 { 
    sendwork(child, child2, min(avg + 1 - child2.workload, child.workload - (avg + 1))) 
    if child2.workload == avg + 1 then child2 = child2.next; 
    } 
} 

Answer 2

Je pense que votre analyse est incorrecte:

• marchant dans la liste pour trouver la moyenne est O (n)
• faire des listes d'enfants avec trop ou trop peu de blocs de données est également O (n)
• le déplacement des données est proportionnelle à la quantité de données

Comment êtes-vous arrivé à O (n!)?

Vous pouvez trier la liste [O (n lg n) dans le nombre d'enfants], de sorte qu'au premier plan vous avez des enfants avec trop de travail, et à la fin des enfants avec trop peu de travail. Traversez ensuite la liste des deux extrémités simultanément: un itérateur pointe vers un enfant avec des données excédentaires, l'autre vers un enfant avec un manque de données. Transférez des données et déplacez l'un des itérateurs vers l'avant ou vers l'arrière.

Answer 3

Le code que vous avez posté a une complexité O (n^2). Pourtant, il est possible de le faire en temps linéaire comme l'a observé malach, où n est le nombre d'éléments dans la liste des enfants.Considérons que la boucle interne a n itérations et qu'elle est exécutée au plus n fois. n * n = n^2.

Answer 4

Vous pouvez essayer une approche complètement différente, telle que le hachage cohérent.

Voir ici pour une introduction relativement facile au sujet: http://www8.org/w8-papers/2a-webserver/caching/paper2.html

(Il y a des papiers plus profonds disponibles aussi bien, en commençant par Karger et al)

J'ai créé une implémentation fonctionnelle de hachage cohérente Erlang que vous pouvez examiner si vous le souhaitez:

http://distributerl.googlecode.com/svn/trunk/chash.erl