分散分布アルゴリズム

Question

私は疎結合クラスターのいくつかのコードに取り組んでいます。ジョブ中に最適なパフォーマンスを達成するために、私は、子供が出入りするたびにクラスタにデータを再マップさせます。これは最終的にオプションになりますが、現在はデフォルトでデータのバランシングを実行します。私のバランスは基本的には、各子供がマシン1台あたりの平均ファイル数に1を加えた数を超えないようにすることです。除算がきれいでない場合は、残りの部分はプラスです。残りの部分はとなるので、常には子どもの数より少なくなるようにすることができますが、除外することができます。

私のアルゴリズムは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）ここで私はOを（！n）の導出方法を示すためにいくつかの擬似コードです。 Foreach n、n => n * n => n^2。私は今朝はコーヒーが足りないと思うよ！ ;）

将来的には、より柔軟で弾力のある配分方法[重み付けとhueristics]に移行したいと思いますが、今のところデータの一様な配分が機能しています。

Answer 1

@zvrba：リストをソートする必要はありません。リストをトラバースするときは、平均作業量が少ないすべてのアイテムをリストの末尾に移動するだけです（最初のトラバース時に最後のアイテムへのポインタを保持することができます）。順序は完全である必要はなく、イテレーターを最後のステップで増やしたり減らしたりする必要があるときに変更されます。

See previous answer

最後のステップは次のようになります。第二段階では

をダブルリンクリストを持っている必要性を防ぐために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

私はあなたの分析が間違っていると思います：

• が平均を見つけるためにリストを歩いてO（n）の
• が多すぎるか、または少なすぎデータチャンクと子供のリストを作るにもなっているOデータを移動
• （n）は、あなたがOに到着しましたかデータ

の量に比例している（N！）？

[子供の数でリストを並べ替えることができます]ので、正面には仕事が多すぎる子供が、最後には仕事が少なすぎる子供がいます。次に、リストの両端から同時にトラバースします。一方のイテレータは余分なデータを持つ子を指し、もう一方のイテレータはデータのない子を指します。データを転送し、一方のイテレータを前方に、または他方の後方に移動します。

Answer 3

投稿したコードの複雑さはO（n^2）です。それでもなお、悪意のある人が観察したように線形時間で行うことができます。ここで、nは子リスト内の項目の数です。

考えてみましょう：内側のループにはn回の反復があり、実行されるのはで、最大ではです。 n * n = n^2である。

Answer 4

一貫性のあるハッシングなど、全く異なるアプローチを試してみるとよいでしょう。

話題に比較的容易に導入するためにここを参照してください： http://www8.org/w8-papers/2a-webserver/caching/paper2.html

（利用できる深い論文がカーガーら始まる、同様にあります）

私は一貫性のあるハッシュの作業の実装を作成しました

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