Distribuição equilibrada Algorithm

Question

Eu estou trabalhando em algum código para um cluster de baixo acoplamento. Para obter um desempenho ideal durante os trabalhos, eu tenho o cluster remapear os dados cada vez que uma criança entra ou sai. Isto acabará por ser feita opcional, mas por enquanto ele executa seus dados de equilíbrio por padrão. Meu equilíbrio é basicamente apenas certificando-se de que cada criança nunca tem mais do que o número médio de arquivos por máquina, mais um. O mais um é para o resto se a divisão não é limpo. E uma vez que o restante irá sempre ser inferior ao número de crianças [excepto 0 caso, mas podemos excluir que], as crianças após um balanceamento terá, no máximo, avg + 1.

Tudo parece bem, até que eu percebi que meu algoritmo é O (n!). Desça a lista de crianças, descobrir o avg, restante, que tem demasiados e que tem muito poucos. Para cada criança na lista de muitos, passar por lista, envie a cada criança que tem muito poucos.

Existe uma solução melhor para isso? Eu sinto que deve ser.

Edit: Aqui estão algumas psuedocode para mostrar como eu derivado O (n!):

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

Editar: O (n ^ 2). Foreach n, n => n * n => n ^ 2. Eu acho que eu não tinha o suficiente café esta manhã! ;)

No futuro eu gostaria de passar para um método de distribuição mais flexível e resiliente [pesos e hueristics], mas por agora, uma distribuição uniforme das obras de dados.

Answer 1

@zvrba: Você não tem sequer para ordenar a lista. Ao percorrer a lista pela segunda vez apenas mover todos os itens com menor a carga de trabalho média para o fim da lista (você pode manter um ponteiro para o último item em sua primeira travessia). A ordem não tem que ser perfeito, ele apenas muda quando os iteradores tem que ser aumentada ou diminuída em sua última etapa.

Ver resposta anterior

O último passo seria algo parecido com:

Na segunda etapa manter um ponteiro para o primeiro item com menos de carga de trabalho média em child2 (para evitar a necessidade de ter uma lista de link duplo).

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

Eu acho que a sua análise é incorreto:

• caminhada através da lista para descobrir a média é de O (n)
• fazer listas de crianças com muitos ou alguns pedaços de dados também é O (n)
• movimentação de dados é proporcional à quantidade de dados

Como você chegou a O (n!)?

Você pode classificar a lista [O (n lg n) no número de crianças], de modo que na frente você tem filhos com muito trabalho, e as crianças acabam com muito pouco trabalho. Em seguida, percorrer a lista de ambos os lados ao mesmo tempo: um iterador aponta para uma criança com excesso de dados, o outro para uma criança com falta de dados. Transferência de dados, e mover qualquer uma iteração para a frente, ou o outro para trás.

Answer 3

Você pode querer tentar uma abordagem completamente diferente, como hashing consistente.

Veja aqui uma introdução relativamente fácil com o tema: http://www8.org/w8-papers/2a-webserver/ caching / paper2.html

(Há papéis disponíveis mais profundas, bem como, começando com Karger et ai)

Eu criei uma implementação de trabalho de hashing consistente em Erlang que você pode examinar se desejar:

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

Answer 4

O código que você postou tem complexidade O (n ^ 2). Ainda assim, é possível fazê-lo em tempo linear como malach observou, onde n é o número de itens na lista de crianças.

Considere: o loop interno tem n iterações, e ele é executado , no máximo n vezes. n * n = n ^ 2.