1

我最近在一次采访中被问到这个问题。假设我有 2000 台服务器。我想将一个 5GB 的文件从中央服务器传输到所有这些服务器。想出一个有效的算法。

我的回应：我将使用 perl/python 将文件从集中式服务器传送到第一台服务器。同时，我还将开始向其他服务器发送文件。我觉得一个接一个地做效率很低，因此并行做会加快速度。

有一个更好的方法吗 ？

4

5 回答 5

14

当然，您会使用某种脚本，因为您不想手动执行此操作。但是，不是将所有文件从一台服务器发送到所有其他服务器，而是开始将文件发送到 k 个服务器。一旦这些 k 个服务器收到文件（假设在时间 t），它们也可以开始分发文件，所以大约在 t 之后。时间 2*t 已经 k^2 服务器拥有该文件，而不是原始解决方案中的 2*k。在时间 3*t 之后 k^3 服务器已经获得了文件...您继续使用该算法，直到每个服务器都获得它的文件。

为了使整个过程更快一点，您还可以将文件分成块，以便服务器可以在收到整个文件之前开始重新分发它（您最终会得到类似 torrent 的东西）

于 2012-07-04T18:32:53.453 回答
7

在这种情况下，绝对“洪流”是负载平衡的最佳且经过验证的策略。但我认为，当面试向我提出这样的假设性问题时，她可能也在寻找你的假设并期待反问。

  1. 服务器的上传/下载能力。
  2. 网络本地化，即不同机器有多少跳。
  3. 文件可以存档和发送吗
  4. 如何验证完整性（md5 哈希）

感谢@Misch，现在我的计划仍然是相同的“洪流”。但是，如果所有服务器都在相同的 n/w 上并且具有相同的容量，那么；

  1. 将文件分成 2000 个部分，每个服务器获得 5GB/2000 ~ 2.5 MB（文件段）来托管，中央作为信标服务器告诉其他服务器文件在哪里。

  2. 每台服务器都会以随机顺序从其他服务器下载这些块，如果我们按顺序下载，则会导致一台机器出现瓶颈。

根据机器，我们可以拥有最大的活动上传/下载线程，每个线程向上/向下单独的文件段。当服务器为最大主机提供服务时，它可以拒绝文件下载请求。请求主机将简单地拾取另一个随机段进行下载。

  1. 我们可以对单个文件段和所有文件组合使用一些校验和，以验证文件完整性。

这确保所有服务器都在接近其上行/下行带宽的情况下上传/下载。但很明显，在现实世界中，我可以拥有一个安全的种子，然后直接使用它。

于 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

我被问到一个类似的问题，其中不接受洪流的做事方式。问题是“如果微软必须将软件更新推送到它在美国拥有的 2000 台服务器，那么它将如何做到这一点”——因此这些服务器无法进行基于种子的文件传输。

我的回答是：从具有 2000 个节点列表的主服务器有一个批处理过程，批处理的容量将取决于您跨这些节点的网络速度。

  1. 因此，首先选择 100 个节点的样本并在这些节点上进行速度测试。速度测试将指示这 100 个节点的可用速度中值是多少，并且可能作为整个网络的样本。

  2. 因此，现在您的值 X Mbps 是您可以跨这些节点进行传输的速度。

  3. 查看您自己的传出数据速度的容量。因此，如果中央服务器的上传速度为 YGbps

然后批处理大小=您的上传容量（Y）/ X（speedtest找到的速度）。

根据这个批处理大小，您可以分批并行传输到 2000 个服务器。

任何输入？

于 2012-07-12T16:08:10.573 回答
0

我想您可以将文件放在 NFS 服务器上并让您的主机安装该 NFS 分区。

于 2020-09-26T16:34:47.940 回答