1

最近インタビューでこんな質問をされました。2000 台のサーバーがあるとします。集中型サーバーからこれらすべてのサーバーに 5 GB のファイルを転送したいと考えています。効率的なアルゴリズムを考えてみましょう。

私の回答: perl/python を使用して、中央サーバーから最初のサーバーにファイルを scp します。並行して、他のサーバーへのファイルの送信も開始します。1つずつ行うのは非常に非効率的であると感じているため、並行して行うと速度が上がります。

これを行うより良い方法はありますか？

4

5 に答える 5

14

確かに、手動で実行したくないので、ある種のスクリプトを使用します。ただし、1つのサーバーから他のすべてのサーバーにすべてのファイルを送信する代わりに、k台のサーバーにファイルを送信し始めます。これらのk台のサーバーがファイルを受信するとすぐに（たとえば、時刻tに）、ファイルの配布も開始できるようになります。時間2*tすでにk^2サーバーには、元のソリューションの2*kではなくファイルがあります。時間の経過後、3*tはすでにk^3サーバーがファイルを取得しています...すべてのサーバーがファイルを取得するまで、そのアルゴリズムを続行します。

プロセス全体をさらに高速化するために、ファイルをチャンクに分割して、サーバーがファイル全体を受信する前にファイルの再配布を開始できるようにすることもできます（トレントのようなものになります）

于 2012-07-04T18:32:53.453 に答える
7

このシナリオでの負荷分散には、間違いなく「トレント」が最適で実証済みの戦略です。しかし、インタビューで私にそのような仮説的な質問をするとき、彼女はおそらくあなたの仮定を探しており、反対の質問を期待していると思います.

  1. サーバーのアップロード/ダウンロード容量。
  2. ネットワークのローカリゼーション、つまり、異なるマシンのホップ数。
  3. ファイルをアーカイブして送信できますか
  4. 整合性を検証する方法 (md5 ハッシュ)

@Mischのおかげで、私のスキームは同じ「トレント」のままです。ただし、すべてのサーバーが同じネットワーク上にあり、容量が同じである場合。

  1. ファイルを 2000 の部分に分割し、各サーバーは 5GB/2000 ～ 2.5 MB (ファイル セグメント) をホストに割り当て、セントラルはビーコン サーバーとして機能し、他のサーバーにファイルの場所を伝えます。

  2. 各サーバーはこれらのチャンクを他のサーバーからランダムな順序でダウンロードします。順番にダウンロードすると、1 台のマシンでボトルネックが発生します。

マシンによっては、アクティブなアップロード/ダウンロード スレッドを最大にすることができ、各スレッドは個別のファイル セグメントを上下します。サーバーが最大数のホストにサービスを提供している場合、サーバーはファイルのダウンロード要求を拒否できます。ホストを要求すると、ダウンロードする別のランダムなセグメントが単純にピックアップされます。

  1. ファイルの整合性を検証するために、個々のファイル セグメントとすべてのファイルを組み合わせたチェックサムを使用できます。

これにより、すべてのサーバーがアップ/ダウン ストリーム帯域幅の近くでアップロード/ダウンロードすることが保証されます。しかし、明らかに現実の世界では、安全な torrent を代わりに使用することができます。

于 2012-07-05T13:06:08.237 に答える
1

ファイルを小さなチャンクに分割すると、ファイル全体がダウンロードされる前に、各サーバーが受信したチャンクの転送を開始できます。これは基本的に bittorrent が使用するアルゴリズムであり、サーバーがすべてを受信した後にのみファイルを送信するよりもはるかに (つまり、漸近的に) 高速です。

実際、チャンク サイズが非常に小さい場合 (つまり、純粋に理論的なケース)、あるサイズのファイルmをnサーバーに配布するのにかかる時間は、 の値には依存しませんn-- 配布されるファイルのサイズだけに依存します (すなわち O( m))。もちろん、実際のケースでは、考慮すべきいくつかのオーバーヘッド/詳細 ( d1valがうまくまとめたもの) があり、実際には少し時間がかかります。

逆に、各サーバーがファイル全体を受信した後にのみファイルを別のサーバーにアップロードする場合、実行時間は O( mlog( n)) になります。これは、bittorrent アプローチよりも漸近的に長くなります。

また、追加するために、通常、インタビューでこの種の質問をするとき、彼/彼女は実装の詳細ではなく、アルゴリズムについて尋ねています。

于 2012-07-06T01:46:47.260 に答える
1

急流のやり方では受け入れられない、同様の種類の質問がありました。質問は、「Microsoft がソフトウェアの更新を米国全体にある 2000 台のサーバーにプッシュする必要がある場合、どのように行うか」でした。したがって、これらのサーバーはトレント ベースのファイル転送を行うことができません。

私の答えは次のとおりです。2000ノードのリストを持つメインサーバーから、バッチ処理が行われます。バッチの容量は、これらのノードまでのネットワーク速度によって決まります。

  1. したがって、最初に 100 個のノードのサンプルを選択し、これらのノード全体で速度テストを行います。速度テストは、これらの 100 個のノードで使用可能な中央速度を示し、ネットワーク全体のサンプルとして機能する可能性があります。

  2. これで、X Mbps の値が、これらのノードに転送できる速度になります。

  3. 自分の発信データ速度の容量を見てください。したがって、中央サーバーのアップロード速度として YGbps の容量がある場合

次に、バッチ サイズ = アップロード容量 (Y)/X (スピード テストで検出された速度)。

このバッチ サイズに従って、バッチで 2000 サーバーに並行して転送を進めます。

入力はありますか?

于 2012-07-12T16:08:10.573 に答える