6

疎結合クラスターのコードに取り組んでいます。ジョブ中に最適なパフォーマンスを実現するために、子が出入りするたびにクラスターにデータを再マッピングさせます。これは最終的にはオプションになりますが、現時点ではデフォルトでデータ バランシングを実行します。私のバランス調整は基本的に、各子がマシンごとの平均ファイル数に 1 を加えた数を超えないようにすることです。除算がきれいでない場合、プラス 1 は残りの部分です。そして、残りは常に子の数よりも少ないため [0 の場合を除きますが、それを除外できます]、バランス調整後の子は最大で avg + 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 => n*n => n^2。今朝はコーヒーが足りなかったみたい！;)

将来的には、より柔軟で回復力のある分散方法 [重みとヒューリスティックス] に移行したいと考えていますが、今のところ、データの均一な分散が機能しています。

4

4 に答える 4

4

@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;
  }
}
于 2008-09-26T14:21:28.367 に答える
2

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

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

O(n!)にたどり着いた経緯は？

リスト [O(n lg n) in the number of children] を並べ替えて、前に仕事が多すぎる子供がいて、最後に仕事が少なすぎる子供がいるようにすることができます。次に、両端からリストを同時にトラバースします。一方の反復子は過剰なデータを持つ子を指し、もう一方はデータのない子を指します。データを転送し、一方の反復子を前方または後方に移動します。

于 2008-09-26T13:57:34.210 に答える
2

コンシステント ハッシュなど、まったく異なるアプローチを試すこともできます。

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

(Kargerらから始まる、より深い論文も利用可能です)

必要に応じて調べることができる、Erlang で一貫したハッシュの実用的な実装を作成しました。

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

于 2008-09-26T14:42:55.880 に答える
1

投稿したコードの複雑さは O(n^2) です。それでも、malach が観察したように線形時間で実行することは可能です。ここで、n は子リスト内のアイテムの数です。

考慮してください: 内側のループには n 回の反復があり、最大でn 回実行されます。n*n = n^2。

于 2008-09-26T14:34:56.163 に答える