Algorithme de distribution équilibrée

Question

Je travaille sur du code pour un cluster faiblement couplé. Pour obtenir des performances optimales pendant les travaux, le cluster doit remapper ses données chaque fois qu'un enfant entre ou sort. Cela deviendra éventuellement facultatif, mais pour l'instant, il effectue son équilibrage des données par défaut. Mon équilibre consiste essentiellement à m'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 toujours inférieur au nombre d'enfants [sauf 0 cas, mais nous pouvons l'exclure], les enfants après un équilibrage auront au plus avg + 1.

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

Existe-t-il une meilleure solution à cela? Je pense qu’il doit y en avoir.

Éditer: Voici quelques psuedocodes pour montrer comment j'ai dérivé O (n!):

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

Modifiez: 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, j'aimerais passer à une méthode de distribution [poids et hueristique] plus souple et plus résiliente, 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 pour la deuxième fois, déplacez simplement tous les éléments dont la charge de travail moyenne est inférieure à la fin de la liste (vous pouvez conserver un pointeur sur le dernier élément lors de votre premier parcours). La commande ne doit pas nécessairement être parfaite, elle change simplement lorsque les itérateurs doivent être augmentés ou diminués lors de votre dernière étape.

Voir la réponse précédente

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

Dans la deuxième étape, gardez un pointeur sur le premier élément avec une charge de travail inférieure à la moyenne dans enfant2 (pour éviter la nécessité de disposer d’une double liste de liens).

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:

• parcourant la liste pour trouver la moyenne est O (n)
• dresser des listes d’enfants avec trop ou trop peu d’éléments de données est également O (n)
• les données en mouvement sont proportionnelles à la quantité de données

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

Vous pouvez trier la liste [O (n lg n) en 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. Parcourez ensuite la liste des deux côtés simultanément: un itérateur pointe vers un enfant avec un excès de données, 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

Vous pouvez essayer une approche complètement différente, telle qu'un hachage cohérent.

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

(Il existe également des documents plus détaillés, à commencer 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

Answer 4

Le code que vous avez posté a une complexité O (n ^ 2). Néanmoins, il est possible de le faire en temps linéaire, comme l'a observé malach, où n est le nombre d'éléments de la liste des enfants.

Considérez: la boucle interne a n itérations et elle est exécutée au plus n fois. n * n = n ^ 2.