Алгоритм сбалансированного распределения

Question

Я работаю над кодом для слабосвязанного кластера. Для достижения оптимальной производительности во время работы кластер перераспределяет свои данные каждый раз, когда ребенок входит или выходит. В конечном итоге это станет необязательным, но пока он выполняет балансировку данных по умолчанию. Мой баланс в основном сводится к тому, чтобы у каждого ребенка не было больше, чем среднее количество файлов на машину плюс один. Плюс для остальных, если деление не чистое. И поскольку остаток будет всегда меньше числа детей [кроме случая 0, но мы можем исключить это], дети после балансировки будут иметь максимум avg + 1.

Все выглядит нормально, пока я не понял, что мой алгоритм O (n!). Спуститесь по списку детей, найдите среднее число, остаток, у которого слишком много, а у кого слишком мало. Для каждого ребенка в списке слишком много, просмотрите список, отправьте каждому ребенку, у которого слишком мало.

Есть ли лучшее решение для этого? Я чувствую, что должно быть.

Edit: Вот некоторый psuedocode, чтобы показать, как я получил O (n!):

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

Редактировать: O (n ^ 2). Foreach n, n => n * n => n ^ 2. Я думаю, мне не хватило кофе сегодня утром! ;)

В будущем я хотел бы перейти к более гибкому и устойчивому методу распределения [весам и иерархиям], но сейчас работает равномерное распределение данных.

Answer 1

@ zvrba: Вам даже не нужно сортировать список. При обходе списка во второй раз просто переместите все элементы с меньшей средней рабочей нагрузкой в ​​конец списка (вы можете сохранить указатель на последний элемент при первом прохождении). Порядок не обязательно должен быть идеальным, он просто изменяется, когда итераторы должны быть увеличены или уменьшены на последнем шаге.

См. Предыдущий ответ

Последний шаг будет выглядеть примерно так:

На втором шаге сохраните указатель на первый элемент с меньшей средней нагрузкой в ​​child2 (чтобы избежать необходимости иметь список двойных ссылок).

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

Возможно, вы захотите попробовать совершенно другой подход, например, последовательное хеширование.

Смотрите здесь для относительно простого введения в тему: http://www8.org/w8-papers/2a-webserver/caching/paper2.html

(также доступны более глубокие статьи, начиная с Каргера и др.)

Я создал работающую реализацию согласованного хеширования в Erlang, которую вы можете проверить, если хотите:

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

Answer 3

Я думаю, что ваш анализ неверен:

• , пройдя по списку, чтобы определить среднее значение O (n)
• создание списков детей со слишком большим или слишком малым количеством фрагментов данных также O (n)
• движущиеся данные пропорциональны объему данных

Как вы попали в O (n!)?

Вы можете отсортировать список [O (n lg n) по количеству детей], чтобы спереди у вас были дети с слишком большой работой, а в конце дети с слишком маленькой работой. Затем просмотрите список с обоих концов одновременно: один итератор указывает на ребенка с избыточными данными, другой - на ребенка с недостатком данных. Передайте данные и переместите один итератор вперед или другой назад.

Answer 4

Код, который вы опубликовали, имеет сложность O (n ^ 2). Тем не менее, это можно сделать за линейное время, как заметил Малах, где n - количество элементов в списке детей.

Учтите: внутренний цикл имеет n итераций и выполняется не более n раз. n * n = n ^ 2.