22

更新：这是我对 Hashed Timing Wheels 的实现。如果您有提高性能和并发性的想法，请告诉我。（2009 年 1 月 20 日）

// Sample usage:
public static void main(String[] args) throws Exception {
    Timer timer = new HashedWheelTimer();
    for (int i = 0; i < 100000; i ++) {
        timer.newTimeout(new TimerTask() {
            public void run(Timeout timeout) throws Exception {
                // Extend another second.
                timeout.extend();
            }
        }, 1000, TimeUnit.MILLISECONDS);
    }
}

更新：我通过使用Hierarchical 和 Hashed Timing Wheels解决了这个问题。（2009 年 1 月 19 日）

我正在尝试在 Java 中实现一个特殊用途的计时器，该计时器针对超时处理进行了优化。例如，用户可以注册一个带有截止期限的任务，并且计时器可以在截止期限结束时通知用户的回调方法。在大多数情况下，注册的任务会在很短的时间内完成，因此大多数任务将被取消（例如 task.cancel()）或重新安排到未来（例如 task.rescheduleToLater(1, TimeUnit.SECOND)） .

我想使用这个计时器来检测空闲的套接字连接（例如，在 10 秒内没有收到消息时关闭连接）和写入超时（例如，当写入操作在 30 秒内未完成时引发异常。）在大多数情况下，不会发生超时，客户端将发送一条消息并发送响应，除非存在奇怪的网络问题..

我不能使用 java.util.Timer 或 java.util.concurrent.ScheduledThreadPoolExecutor 因为他们认为大多数任务都应该超时。如果一个任务被取消，被取消的任务被存储在它的内部堆中，直到 ScheduledThreadPoolExecutor.purge() 被调用，这是一个非常昂贵的操作。（O（NlogN）也许？）

在我在 CS 课程中学到的传统堆或优先级队列中，在许多情况下更新元素的优先级是一项昂贵的操作 (O(logN)，因为它只能通过删除元素并重新插入它来实现新的优先级值。像斐波那契堆这样的堆有 O(1) 时间的 reductionKey() 和 min() 操作，但我至少需要快速 increaseKey() 和 min()（或 reductionKey() 和 max()） .

您是否知道针对此特定用例高度优化的任何数据结构？我正在考虑的一种策略是将所有任务存储在哈希表中并每秒左右迭代所有任务，但这并不是那么漂亮。

4

9 回答 9

13

尝试将事情快速完成的正常情况与错误情况分开处理怎么样？

同时使用哈希表和优先级队列。当一个任务开始时，它会被放入哈希表中，如果它很快完成，它会在 O(1) 时间内被删除。

每隔一秒，你就会扫描哈希表，任何已经很长时间的任务，比如 0.75 秒，都会被移动到优先级队列中。优先级队列应该总是很小并且易于处理。这假设一秒远小于您正在寻找的超时时间。

如果扫描哈希表太慢，您可以使用两个哈希表，基本上一个用于偶数秒，一个用于奇数秒。当一个任务开始时，它被放入当前的哈希表中。每秒将所有任务从非当前哈希表移动到优先级队列中并交换哈希表，以便当前哈希表现在为空，并且非当前表包含一到两秒前开始的任务。

有一些选项比仅使用优先级队列复杂得多，但很容易实现应该是稳定的。

于 2009-01-17T15:31:25.173 回答
11

据我所知（我写了一篇关于新优先级队列的论文，其中还回顾了过去的结果），没有一个优先级队列实现得到斐波那契堆的边界，以及恒定时间增加键。

从字面上理解有一个小问题。如果你可以在 O(1) 中得到增加键，那么你可以在 O(1) 中得到删除——只需将键增加到 +infinity（你可以使用一些标准的摊销技巧来处理充满大量 +infinity 的队列）。但是如果 find-min 也是 O(1)，这意味着 delete-min = find-min + delete 变成 O(1)。这在基于比较的优先级队列中是不可能的，因为排序界限意味着（插入所有内容，然后一个接一个地删除）

n * insert + n * delete-min > n log n。

这里的重点是，如果您希望优先级队列在 O(1) 中支持增加键，那么您必须接受以下惩罚之一：

  • 不是基于比较的。实际上，这是一种很好的解决问题的方法，例如vEB 树。
  • 接受 O(log n) 的插入和 O(n log n) 的 make-heap（给定 n 个起始值）。这很糟糕。
  • 接受 O(log n) 的 find-min。如果您从未真正执行find-min （没有伴随的删除），这是完全可以接受的。

但是，再一次，据我所知，没有人做过最后一个选择。我一直将其视为在数据结构的一个非常基本的领域取得新成果的机会。

于 2009-01-19T06:51:06.763 回答
6

使用Hashed Timing Wheel - Google 'Hashed Hierarchical Timing Wheels' 了解更多信息。这是人们在这里做出的答案的概括。我更喜欢带有大轮尺寸的散列计时轮，而不是分层计时轮。

于 2009-01-19T06:23:35.897 回答
5

哈希和 O(logN) 结构的某种组合应该可以满足您的要求。

我很想反驳你分析问题的方式。在你上面的评论中，你说

因为更新会非常频繁地发生。假设我们每个连接发送 M 条消息，那么总时间变成 O(MNlogN)，这是相当大的。– 信任李（6 小时前）

就目前而言，这是绝对正确的。但是我认识的大多数人都会关注每条消息的成本，因为你的应用程序有越来越多的工作要做，显然它需要更多的资源。

因此，如果您的应用程序同时打开了十亿个套接字 （这真的可能吗？），插入成本仅为每条消息大约 60 次比较。

我敢打赌这是过早的优化：您实际上还没有使用 CodeAnalyst 或 VTune 等性能分析工具测量系统中的瓶颈。

无论如何，可能有无数种方法可以满足您的要求，一旦您决定没有单一结构可以满足您的需求，并且您想要结合不同算法的优缺点。

一种可能性是将套接字域 N 划分为若干大小为 B 的桶，然后将每个套接字散列到其中一个 (N/B) 桶中。在那个桶中有一个堆（或其他），更新时间为 O(log B)。如果 N 的上限不是预先固定的，而是可以变化的，那么您可以动态创建更多的桶，这会增加一点复杂性，但肯定是可行的。

在最坏的情况下，看门狗定时器必须搜索（N / B）队列以寻找到期时间，但我认为看门狗定时器不需要以任何特定顺序杀死空闲套接字！ 也就是说，如果 10 个套接字在最后一个时间片中空闲，它不必在该域中搜索第一个超时的那个，处理它，然后找到第二个超时的那个，等等。它只是必须扫描（N / B）组桶并枚举所有超时。

如果您对存储桶的线性数组不满意，您可以使用队列的优先级队列，但您希望避免在每条消息上更新该队列，否则您又回到了开始的地方。相反，定义一些小于实际超时的时间。（比如说，其中的 3/4 或 7/8），如果最长的时间超过了，你只会将低级队列放入高级队列。

并且冒着说明显而易见的风险，您不希望您的队列以经过的时间为键。关键应该是开始时间。对于队列中的每条记录，经过的时间必须不断更新，但每条记录的开始时间不会改变。

于 2009-01-17T22:14:03.583 回答
3

有一种非常简单的方法可以在 O(1) 中执行所有插入和删除操作，利用以下事实：1) 优先级基于时间，以及 2) 您可能有少量固定数量的超时持续时间。

  1. 创建一个常规的 FIFO 队列来保存所有在 10 秒内超时的任务。因为所有任务都有相同的超时持续时间，您可以简单地插入到末尾并从开头移除以保持队列排序。
  2. 为具有 30 秒超时持续时间的任务创建另一个 FIFO 队列。为其他超时持续时间创建更多队列。
  3. 要取消，请从队列中删除该项目。如果队列被实现为链表，则这是 O(1)。
  4. 重新调度可以通过取消插入来完成，因为这两个操作都是 O(1)。请注意，任务可以重新安排到不同的队列。
  5. 最后，要将所有 FIFO 队列组合成一个整体优先级队列，让每个 FIFO 队列的头部参与一个常规堆。此堆的头部将是所有任务中超时时间最短的任务。

如果你有 m 个不同的超时持续时间，那么整个结构的每个操作的复杂度是 O(log m)。由于需要查找要插入的队列，因此插入是 O(log m)。Remove-min 是 O(log m) 用于恢复堆。取消是 O(1) 但最坏的情况是 O(log m) 如果您要取消队列的头部。因为 m 是一个很小的固定数，所以 O(log m) 本质上是 O(1)。它不随任务数量而扩展。

于 2012-03-22T03:23:54.557 回答
2

您的具体情况向我建议了一个循环缓冲区。如果最大。timeout 是 30 秒，我们希望至少每十分之一秒获取一次套接字，然后使用 300 个双向链表的缓冲区，在此期间每十分之一秒一个。要在条目上“增加时间”，请将其从其所在的列表中删除，并将其添加到新的第十秒周期（均为恒定时间操作）。当一个周期结束时，获取当前列表中剩余的任何东西（可能通过将其提供给一个收割线程）并推进当前列表指针。

于 2009-01-17T23:28:57.490 回答
0

您对队列中的项目数量有硬性限制 - TCP 套接字有限制。

因此问题是有界的。我怀疑任何聪明的数据结构都会比使用内置类型慢。

于 2009-01-16T13:25:26.473 回答
0

是否有充分的理由不使用 java.lang.PriorityQueue？remove() 不会在 log(N) 时间内处理您的取消操作吗？然后根据直到队列前面的项目的时间实现您自己的等待。

于 2009-01-16T15:14:18.940 回答
0

我认为将所有任务存储在一个列表中并遍历它们是最好的。

您必须（将要）在一些非常强大的机器上运行服务器才能达到这个成本很重要的极限？

于 2009-01-17T09:14:04.610 回答