javascript - 基于属性的动态限制队列的数据结构/算法

Question

我有一个堆栈(作为数组实现)，其中包含当套接字可用时发出的 HTTP 请求，并且事件套接字的数量受到限制。我想扩展它，以便每个主机有最大数量的套接字(以及最大总套接字数量，但这并不是特别涉及我的问题)。

因此队列应该继续按照接收顺序进行处理。但是，当然，如果队列中下一个请求的主机已达到最大套接字数，则将无法为其提供服务，因此应采用队列中未达到最大套接字数的下一个主机.

我查看了使用 Priority Queue ，用一个比较器来检查主机上可用的最大套接字，但这并不能真正完成工作。我想获取队列中可以服务的下一个，而不是根据套接字可用性作为优先级指标重新排序队列。

我考虑过每个主机都有一个队列，但是很难维持原来的顺序。

我正在考虑有一个队列，每个项目上的主机的属性，以及一个遍历队列的例程，直到找到第一个具有可用套接字的队列，然后通过拼接将其出队。这保持了原始顺序，但似乎效率低下。

所以我正在考虑将这些方法与类似的方法结合起来(使用“order”属性维护整个队列):

const queues = [
  {
    host: 'www.example.org',
    queue: [
      { order: 1 },
      { order: 3 }
    ]
  },
  {
    host: 'www.example.com',
    queue: [
      { order: 2 },
      { order: 4 },
      { order: 5 }
    ]
  }
];

通过上述方法，当每个请求被添加到其主机的适当队列中时，都会将顺序属性添加到每个请求中。然后，每次需要新项目时，可以根据其第一个项目的顺序值对主机队列集进行排序。那么对下一项的检查只需要在每个主机上运行一次，而不是每次扫描整个队列。

Answer 1

我过去为网络爬虫做过类似的事情。

我有一个 Host 类，其中包含有关主机的信息:名称、最大并发请求数、当前事件请求数、其 robots.txt 文件的副本、有关其历史记录的统计信息(我向它发出的请求数量、平均响应速度、错误率等)以及其他特定于主机的信息。

我还有一个请求优先级队列。每个请求结构都有要访问的 URL 以及对相应 Host 实例的引用。优先级键是基于 URL 值(由此处并不真正相关的机器学习算法计算)的优先级值和时间的组合。

当我从队列中删除请求时，我要做的第一件事就是检查主机以查看是否有可用的套接字。如果没有，我将使用现在的时间值 + 主机的平均请求时间重新排队请求。

这很有效，尽管一些非常繁忙的主机的 URL 往往会经常被回收。

我尝试了主机优先级队列。每个主机都有一个队列或 URL。还有一个超时列表:当前由于各种原因而处于“超时”状态的主机字典，但主要是因为没有可用的套接字，或其 URL 队列为空。其工作原理如下:

主机将从优先级队列中删除，并发出请求。如果主机仍然有可用的套接字，那么我会将其添加回队列。如果没有，它将进入超时队列。无论哪种情况，当请求完成时，主机的可用套接字数量都会增加，主机从超时列表中删除并重新插入优先级队列。

这种方法看起来很有希望。当项目由于其他原因被取消时，我们正在对其进行测试。