均衡分布アルゴリズム
-
02-07-2019 - |
質問
私は、疎結合クラスターのいくつかのコードに取り組んでいます。ジョブ中に最適なパフォーマンスを達成するために、子供が出入りするたびにクラスターにデータを再マッピングさせます。これは最終的にオプションになりますが、現時点ではデフォルトでデータバランシングを実行します。私のバランスは基本的に、各子供がマシンあたりの平均ファイル数に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で一貫したハッシュの実用的な実装を作成しました。必要に応じて確認できます。
投稿したコードの複雑さはO(n ^ 2)です。それでも、malachが観測したように線形時間でそれを行うことができます。ここで、nは子リスト内のアイテムの数です。
検討:内側のループにはn回の繰り返しがあり、最大で n回実行されます。 n * n = n ^ 2。