均衡分布アルゴリズム

StackOverflow https://stackoverflow.com/questions/139580

質問

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

アルゴリズムがO（n！）であることに気付くまで、すべてがうまくいくようです。子供のリストを下って、平均、残り、多すぎる人と少なすぎる人を見つけます。多すぎるリストの各子について、リストを調べ、少なすぎる各子に送信します。

これに対するより良い解決策はありますか？あるに違いないと思います。

編集：ここでは、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 =＆gt; n * n =＆gt; n ^ 2。今朝はコーヒーが足りなかったと思います！ ;）

将来は、より柔軟で回復力のある分散方法[重みと色相]に移行したいのですが、現時点では、データの均一な分散が機能します。

役に立ちましたか？

解決

@zvrba：リストをソートする必要さえありません。 2回目にリストを走査するときは、平均ワークロードが少ないすべてのアイテムをリストの最後に移動するだけです（最初の走査で最後のアイテムへのポインターを保持できます）。順序は完全である必要はなく、最後のステップでイテレーターを増加または減少させる必要がある場合にのみ変更されます。

以前の回答を見る

最後のステップは次のようになります：

2番目のステップでは、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;
  }
}

他のヒント

分析が間違っていると思う：

  • リストを調べて平均がO（n）であることを確認します
  • データチャンクが多すぎる、または少なすぎる子のリストを作成することもO（n）
  • データの移動はデータ量に比例します

どうやってO（n！）に到着しましたか？

リスト[O（n lg n）in childrenの数]を並べ替えることができます。これにより、前面に作業が多すぎる子があり、最後に作業が少なすぎる子がいます。次に、両方の端から同時にリストを走査します。一方のイテレータは過剰なデータを持つ子を指し、もう一方はデータのない子を指します。データを転送し、一方のイテレータを前方に移動するか、もう一方のイテレータを後方に移動します。

一貫性のあるハッシュなど、まったく異なるアプローチを試してください。

トピックの比較的簡単な紹介については、こちらをご覧ください。 http://www8.org/w8-papers/2a-webserver/ cacheing / paper2.html

（Karger et alから始まる、より深い論文も利用可能です）

Erlangで一貫したハッシュの実用的な実装を作成しました。必要に応じて確認できます。

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

投稿したコードの複雑さはO（n ^ 2）です。それでも、malachが観測したように線形時間でそれを行うことができます。ここで、nは子リスト内のアイテムの数です。

検討：内側のループにはn回の繰り返しがあり、最大で n回実行されます。 n * n = n ^ 2。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top