用于选择机器组的数据结构

Question

我有这个旧的批处理系统.调度程序将所有计算节点存储在一个大数组中.现在大多数情况下都可以,因为大多数查询都可以通过筛选满足查询的节点来解决.

我现在遇到的问题是,除了一些基本属性(cpus,内存,操作系统的数量)之外,还有这些奇怪的分组属性(城市,infiniband,网络划痕).

现在,这些问题是,当用户请求节点与InfiniBand的我不能只是给他的任何节点,但我得给他节点连接到一个InfiniBand交换机,所以节点可以使用InfiniBand实际通信.

这仍然没问题,当用户只请求一个这样的属性时(我可以为每个属性分区数组,然后尝试分别选择每个分区中的节点).

问题在于组合多个这样的属性,因为那时我将不得不生成子集的所有组合(主阵列的分区).

好处是大多数属性都处于子集或等价关系中(对于一个infiniband交换机上的计算机来说,它在一个城市中是有意义的).但遗憾的是,这并非严格属实.

是否有一些良好的数据结构用于存储这种半分层的大多数树状的东西？

编辑:例子

node1 : city=city1, infiniband=switch03, networkfs=server01
node2 : city=city1, infiniband=switch03, networkfs=server01
node3 : city=city1, infiniband=switch03
node4 : city=city1, infiniband=switch03
node5 : city=city2, infiniband=switch03, networkfs=server02
node6 : city=city2, infiniband=switch03, networkfs=server02
node7 : city=city2, infiniband=switch04, networkfs=server02
node8 : city=city2, infiniband=switch04, networkfs=server02

用户要求:

2x node with infiniband and networkfs

期望的输出是:(node1, node2)或(node5,node6)或(node7,node8).

在一个好的情况下,这个例子不会发生,但在某些情况下我们实际上有这些奇怪的跨站点连接.如果city2inin中的节点都在infiniband上switch04,那将很容易.不幸的是,现在我必须生成具有相同infiniband交换机和相同网络文件系统的节点组.

实际上,问题要复杂得多,因为用户不会请求整个节点,并且属性很多.

编辑:为查询添加了所需的输出.

Answer 1

假设您有 p 个分组属性和 n 个计算机，基于存储桶的解决方案最容易设置，并提供 O(2 ^p ·log(n)) 访问和更新。

• 您为每组属性创建一个桶堆（因此您将拥有一个“infiniband”的桶堆、一个“networkfs”的桶堆和一个“infiniband × networkfs”的桶堆）——这意味着 2 ^p桶堆。
• 每个桶堆包含一个用于每个值组合的桶（因此“infiniband”桶将包含一个用于键“switch04”的桶和一个用于键“switch03”的桶）——这意味着总共最多 n·2 p 个^桶分裂跨越所有桶堆。
• 每个桶都是一个服务器列表（可能分为可用和不可用）。桶堆是一个标准堆（请参阅 参考资料std::make_heap），其中每个桶的值是该桶中可用服务器的数量。
• 每个服务器都存储对包含它的所有存储桶的引用。
• 当您查找与特定属性组匹配的服务器时，您只需在该属性组的相应存储桶中查找，然后沿着堆向下查找足够大的存储桶以容纳所请求的服务器数量。这需要 O(log(p)·log(n))。
• 当服务器被标记为可用或不可用时，您必须更新包含这些服务器的所有存储桶，然后更新包含这些存储桶的存储桶堆。这是一个 O(2 ^p ·log(n)) 操作。

如果您发现自己拥有太多属性（并且 2 ^p增长失控），则该算法允许根据其他存储桶堆按需构建一些存储桶堆：如果用户请求“infiniband × networkfs”，但您只有一个可用于“infiniband”或“networkfs”的桶堆，您可以将“infiniband”桶堆中的每个桶变成自己的桶堆（使用惰性算法，这样您就不必处理所有存储桶（如果第一个有效）并使用惰性堆合并算法来查找合适的存储桶。然后，您可以使用 LRU 缓存来决定存储哪些属性组以及按需构建哪些属性组。