algorithm - 算法 - 根据两个标准平等地填充不同大小的容器

Question

我正试图围绕一个算法。我以前从未编写过算法，也不知道如何解决这个问题。这是它的要点：

我可以有 n 个容器，每个容器都有两组对我很重要的数字：内存量 (x) 和逻辑处理器的数量 (y) 每个容器可以有不同的值。

每个虚拟机都有一定数量的内存 (x) 和一定数量的逻辑处理器 (y)。我正在尝试创建一种算法，该算法将平均平衡集群中所有主机的内存负载（x）和逻辑处理器数量（y）。它不会在所有主机之间真正相等，但所有主机将在每台主机的 10% +/- 范围内。

我将如何解决这个问题，我会在数学上假设。

Answer 1

如果我正确理解了您的问题，您希望最小化主机的相对负载，以便每个主机的负载与其他主机的偏差不超过 10%。所以我们想通过找到一个最小值来优化主机之间的“相对负载”。

为此，您可以使用某种组合优化来达到可接受或最优的解决方案。像模拟退火或禁忌搜索这样的经典元启发式算法就可以完成这项工作。

您的问题的示例通用步骤：

• 通过将每个 VM 随机分配给主机来定义初始状态
• 通过在主机之间迭代交换 VM 来查找新状态，直到：
  • 找到了一些可接受的解决方案，或
  • 迭代次数已用尽，或
  • 满足其他一些条件（如模拟退火的“温度”）
• 开发一个比较函数来决定何时在每次迭代中切换状态（解决方案）
  • 在您的情况下，您应该测量所有主机之间的相对负载，并且仅当新状态的相对负载低于当前状态时才交换状态。

这当然假设您将使用某种形式的逻辑表示而不是实际的 VM 来执行此算法。一旦您找到模拟您的真实条件的解决方案，您就可以将它们物理地应用到您的虚拟机/主机配置中。

希望这可以帮助！

Answer 2

您现在可能已经继续前进，但是如果您回到这个问题，这个答案可能会很有用。如果任何部分令人困惑，请告诉我，我会尽力澄清。

您的问题是没有旋转的 2D 可变尺寸箱包装的情况。您的尺寸是内存和 CPU，而不是长度和宽度（因此没有旋转）。

我会使用一个简单的离线打包算法。（离线意味着你的虚拟机和主机都是事先知道的）我使用的简单打包是：

1. 按所需内存对未分配的虚拟机进行排序
2. 按可用内存对您的主机集进行排序
3. 找到可容纳 VM 的可用内存最多的主机并将其分配给该主机（请务必检查 CPU 容量。可用内存最多的主机可能没有足够的 CPU 资源）
4. 从列表中删除虚拟机
5. 减少主机的可用内存和 CPU 容量
6. 如果您仍有虚拟机，请转到 2

以下是我定义虚拟机和主机的方式：

[DebuggerDisplay("{Name}: {MemoryUsage} | {ProcessorUsage}")]
class VirtualMachine
{
    public int MemoryUsage;
    public string Name;
    public int ProcessorUsage;

    public VirtualMachine(string name, int memoryUsage, int processorUsage)
    {
        MemoryUsage = memoryUsage;
        ProcessorUsage = processorUsage;
        Name = name;
    }
}

[DebuggerDisplay("{Name}: {Memory} | {Processor}")]
class Host
{
    public readonly string Name;
    public int Memory;
    public Host Parent;
    public int Processor;

    public Host(string name, int memory, int processor, Host parent = null)
    {
        Name = name;
        Memory = memory;
        Processor = processor;
        Parent = parent;
    }

    public bool Fits(VirtualMachine vm) { return vm.MemoryUsage <= Memory && vm.ProcessorUsage <= Processor; }
    public Host Assign(VirtualMachine vm) { return new Host(Name + "_", Memory - vm.MemoryUsage, Processor - vm.ProcessorUsage, this); }
}

主机Fits和Assign方法对于检查 VM 是否适合，并减少主机可用内存/CPU 非常重要。我创建了一个“Host-Prime”来表示资源减少的主机，删除原始主机并将 Host-Prime 插入到主机列表中。这是bin pack求解算法。如果您针对大型数据集运行，应该有很多机会加快执行速度，但这对于小型数据集来说已经足够了。

class Allocator
{
    readonly List<Host> Bins;
    readonly List<VirtualMachine> Items;

    public Allocator(List<Host> bins, List<VirtualMachine> items)
    {
        Bins = bins;
        Items = items;
    }

    public Dictionary<Host, List<VirtualMachine>> Solve()
    {
        var bins = new HashSet<Host>(Bins);
        var items = Items.OrderByDescending(item => item.MemoryUsage).ToList();

        var result = new Dictionary<Host, List<VirtualMachine>>();

        while (items.Count > 0)
        {
            var item = items.First();
            items.RemoveAt(0);
            var suitableBin = bins.OrderByDescending(b => b.Memory).FirstOrDefault(b => b.Fits(item));
            if (suitableBin == null)
                return null;

            bins.Remove(suitableBin);

            var remainder = suitableBin.Assign(item);
            bins.Add(remainder);

            var rootBin = suitableBin;
            while (rootBin.Parent != null)
                rootBin = rootBin.Parent;
            if (!result.ContainsKey(rootBin))
                result[rootBin] = new List<VirtualMachine>();
            result[rootBin].Add(item);
        }
        return result;
    }
}

所以你现在有一个打包算法，但你仍然没有一个负载平衡解决方案。由于该算法会将虚拟机打包到主机上，而不用担心内存使用的平衡，因此我们需要另一个级别的解决方案。为了达到一些粗略的记忆平衡，我采取了蛮力的方法。减少每个主机上的初始内存以表示目标使用目标。然后解决以查看您的虚拟机是否适合减少的可用内存。如果没有找到解决方案，请放宽内存限制。重复此操作，直到找到解决方案，或者没有可能（使用给定的算法）。这应该给出最佳内存负载的粗略近似值。

class Program
{
    static void Main(string[] args)
    {
        //available hosts, probably loaded from a file or database
        var hosts = new List<Host> {new Host("A", 4096, 4), new Host("B", 8192, 8), new Host("C", 3072, 8), new Host("D", 3072, 8)};
        var hostLookup = hosts.ToDictionary(h => h.Name);

        //VMs required to run, probably loaded from a file or database
        var vms = new List<VirtualMachine>
                      {
                          new VirtualMachine("1", 512, 1),
                          new VirtualMachine("2", 1024, 2),
                          new VirtualMachine("3", 1536, 5),
                          new VirtualMachine("4", 1024, 8),
                          new VirtualMachine("5", 1024, 1),
                          new VirtualMachine("6", 2048, 1),
                          new VirtualMachine("7", 2048, 2)
                      };

        var solution = FindMinumumApproximateSolution(hosts, vms);
        if (solution == null)
            Console.WriteLine("No solution found.");
        else
            foreach (var hostAssigment in solution)
            {
                var host = hostLookup[hostAssigment.Key.Name];
                var vmsOnHost = hostAssigment.Value;

                var xUsage = vmsOnHost.Sum(itm => itm.MemoryUsage);
                var yUsage = vmsOnHost.Sum(itm => itm.ProcessorUsage);
                var pctUsage = (xUsage / (double)host.Memory);
                Console.WriteLine("{0} used {1} of {2} MB {5:P2} | {3} of {4} CPU", host.Name, xUsage, host.Memory, yUsage, host.Processor, pctUsage);
                Console.WriteLine("\t VMs: " + String.Join(" ", vmsOnHost.Select(vm => vm.Name)));
            }
        Console.ReadKey();
    }

    static Dictionary<Host, List<VirtualMachine>> FindMinumumApproximateSolution(List<Host> hosts, List<VirtualMachine> vms)
    {
        for (var targetLoad = 0; targetLoad <= 100; targetLoad += 1)
        {
            var solution = GetTargetLoadSolution(hosts, vms, targetLoad / 100.0);
            if (solution == null)
                continue;
            return solution;
        }
        return null;
    }

    static Dictionary<Host, List<VirtualMachine>> GetTargetLoadSolution(List<Host> hosts, List<VirtualMachine> vms, double targetMemoryLoad)
    {
        //create an alternate host list that reduces memory availability to the desired target
        var hostsAtTargetLoad = hosts.Select(h => new Host(h.Name, (int) (h.Memory * targetMemoryLoad), h.Processor)).ToList();

        var allocator = new Allocator(hostsAtTargetLoad, vms);
        return allocator.Solve();
    }
}