1

请帮助解决以下问题。

给出了以下实体：

  1. 应用。应用程序驻留在存储上，它们通过服务节点生成流量。
  2. 服务。服务分为几个节点。每个节点都可以访问本地或/和共享存储。
  3. 贮存。这是应用程序所在的位置。它可以是本地的（仅连接到一个服务节点）或由多个节点共享。

规则：

  1. 每个应用程序都放置在某个特定的存储上。并且无法更改存储。
  2. 只要新的服务节点可以访问应用程序的存储，就可以将应用程序的服务节点更改为另一个服务节点。

例如，如果 App 驻留在 Node0 的本地存储上，则它只能由 Node0 提供服务。但如果 App 驻留在存储 shared0 上，它可以由 Node0、Node1 或 Node2 提供服务。

考虑到所有应用程序都已放置在它们的数据存储中，问题在于找到在服务节点之间重新平衡应用程序的算法。并尽可能公平地进行这种重新平衡。

如果我们以 shared2 存储为例，解决方案似乎很简单：我们计算 Node3 和 Node4 的应用程序数量，并在它们之间平均分配所有应用程序。但是当涉及到 shared1 时，它变得更加复杂，因为 Node2 也可以访问 shared0 存储。因此，在重新平衡组 [Node2, Node5] 中的应用程序时，我们还必须考虑组 [Node0, Node1, Node2] 中的应用程序。组 [Node2, Node5] 和 [Node0, Node1, Node2] 相交，应立即对所有组执行重新平衡。

我怀疑这个问题应该有众所周知的工作算法，但仍然找不到。 在此处输入图像描述

4

1 回答 1

1

我认为匈牙利匹配算法会满足您的需求。但是，尝试自己的方法可能是一个足够简单的问题。

如果您将所有未连接的图表分开，则每个图表都会有一组共享存储单元，每个集合都与一组应用程序相关联。如果您将这些应用程序中的每一个均匀分布在每个存储的关联节点上，您将拥有一些节点的应用程序比其他节点多。这些节点将连接到多个共享存储单元。

如果所有空节点都被填满，则连通图中的任何两个节点之间应该始终存在传递关系，这样一个 App 可以减少，另一个 App 可以增加，即使需要一些中间位移。因此，如果您沿着从最重节点到最轻节点的路径迭代地移动应用程序，如果您到达一个空节点，则使用快捷方式，并根据需要在任何中间节点交换应用程序以继续沿着该路径通过一个或多个共享存储单元，当最重和最轻节点的数量相差不超过一个时，您应该保持平衡。

于 2022-02-03T19:19:15.467 回答