具有更高速度remove()的DelayQueue？

Question

我有一个跟踪500,000个对象状态信息的项目，该程序每秒接收10,000次有关这些对象的新建、更新或删除操作。

作为程序的一部分，这些对象需要大约每五分钟执行一次清理工作，为此，我将它们放在了一个实现Delayed 接口的DelayQueue 中，利用DelayQueue 的阻塞功能来控制这些对象的清理工作。

• 在新建时，对象会被放置在DelayQueue 中。

• 在更新时，将从DelayQueue 中删除对象，对其进行更新并以更新的信息为准重新插入到新位置中。

• 在删除时，将从DelayQueue 中删除对象。

我面临的问题是，一旦队列中的对象超过约450,000个，remove() 方法就会变得非常耗时。

程序是多线程的，一个线程负责处理更新，另一个线程负责清理工作。由于remove() 延迟，我们遇到了一些令人讨厌的锁定性能问题，并且最终更新线程缓冲区消耗了所有堆空间。

我通过创建一个DelayedWeakReference (扩展弱引用并实现Delayed)来解决这个问题，它允许我在队列中留下“影子”对象，直到它们按照正常方式过期。

这可以解决性能问题，但会显著增加内存需求。这样做会导致每个实际需要放入队列中的对象约有5个DelayedWeakReference。

是否有人知道带有额外跟踪功能且允许快速执行remove()操作的DelayQueue？或者有没有更好的方法来处理这个问题而不会消耗太多内存？

- CuddlyDragon

---

只是好奇...除了技术问题，这是用来做什么的？ - Adam Gent

这是一个用于处理防火墙状态表内容的引擎，它接收防火墙的文本输出并在内存中重建状态表。这使您可以进行广泛的操作和分析，并更重要的是定期以其他格式导出信息，导出自上次更新以来的差异，正如NetFlow中所使用的那样。 - CuddlyDragon

Answer 1

我花了一些时间思考这个问题，
但是在阅读您有趣的问题几分钟后，这是我的想法：
A. 如果您的对象具有某种ID，请使用它进行哈希，并且实际上不要延迟一个队列，而是拥有N个延迟队列。
这将通过N减少锁定因素。
将有一个中央数据结构，
持有这些N个队列。由于N是预配置的，
您可以在系统启动时创建所有N个队列。

- Yair Zaslavsky

---

这是一个有趣的方法，我之前没有考虑过，即对“DelayQueue”进行分片。很容易使用模数将对象分配到不同的队列中，因为它们都有唯一的ID。这可能是一种扩展的方式。 - CuddlyDragon

确实，这正是我想表达的。如果您能测试一下并且有所帮助的话，我会很感激您的点赞 :) - Yair Zaslavsky

这是短期内我最好的选择，并且很可能能够在短到中期内扩展到满足我的需求。我可能会尝试为自己的需求设计一种更专业的队列，以提供所需的功能。--谢谢！ - CuddlyDragon

Answer 2

如果您只需要大约每五分钟执行一次清理工作，那么维护这个任务会很繁琐。

我的建议是设置一个任务，每分钟运行一次（或根据需要更频繁），以检查自上次更新以来是否已经过了五分钟。如果使用此方法，则无需额外的收集来维护，并且在更新时不会改变任何数据结构。扫描组件的开销会增加，但是是恒定的。执行更新的开销变得微不足道（仅需设置一个带有最后更新时间的字段）。

- Peter Lawrey

---

谢谢您的建议，我确实考虑过对HashMap进行定期的“全扫描”，而不是使用DelayQueue。然而，我很快意识到它需要针对特定对象的周年纪念日，即它们并不共享相同的限制。我将对每五分钟扫描一次和延迟方法之间的性能差异进行一些测试。 - CuddlyDragon

Answer 3

如果我正确理解了您的问题，您想对一个对象进行某些操作，如果它在5分钟内没有被触摸。

您可以拥有一个自定义的链接列表；尾部是最近被触摸的。删除节点很快。

簿记线程可以简单地每1秒钟唤醒一次，并删除5分钟前的头节点。但是，如果1秒延迟不可接受，请计算准确的暂停时间。

// book keeping thread

void run()

  synchronized(list) 

    while(true)

        if(head==null)
            wait();
        else if(  head.time + 5_min > now )
            wait( head.time + 5_min - now );
        else 
            remove head
            process it


// update thread

void add(node)
  synchronized(list) 
    append node
    if size==1
        notify()  

void remove(node)
  synchronized(list) 
    remove node    

- irreputable

---

我怀疑的问题是在DelayQueue中搜索要删除的对象，它内部使用PriorityQueue，而PriorityQueue又使用Object[]来存储。我想知道使用LL是否会更快速地进行搜索，或者区别在于可以在不锁定整个结构的情况下完成操作？ - CuddlyDragon