实现带TTL的平均O(1)复杂度Map时看门狗线程效率低如何优化

现有实现的核心问题 #

现有方案的性能损耗主要来自两个方面：

• 每次清理都要全量遍历Map中所有Entry，当数据规模较大时遍历开销会线性上升
• 当无带TTL的条目时，checkExpiredKeys返回0，看门狗线程会进入无意义的空转循环，持续占用CPU资源

可行优化方案 #

1. 新增带TTL条目的有序存储结构 #

额外维护一个按过期时间升序排列的有序结构，可选实现：

• 用TreeMap<Long, Set<String>>：key为过期时间戳，value为该时间点过期的所有键集合
• 用JDK自带的DelayQueue：存储封装了过期时间和键的延迟对象
  优势：无需全量遍历即可快速拿到最小过期时间，清理时只需要处理已到期的小部分条目，不需要扫全表，put/remove操作只要同步更新该结构即可，依然能保持平均O(1)的复杂度（TreeMap的单操作复杂度是O(logn)，如果业务允许极小的性能损耗可以接受，也可以用跳表实现的有序集合进一步优化）

2. 解决无过期条目时的空转问题 #

引入wait/notify机制控制看门狗线程的状态：

• 当有序结构为空（无待过期的条目）时，让看门狗线程调用wait()进入阻塞状态，不占用CPU资源
• 当执行put操作新增了带TTL的条目时，调用notify()唤醒阻塞的看门狗线程，重新计算睡眠时间

3. 增加惰性删除兜底 #

在get、containsKey等用户主动调用的接口中，额外检查当前访问的键是否已过期，如果过期则当场删除并返回不存在/空结果。
优势：可以分摊清理压力，即使看门狗线程还没到唤醒时间，也能及时清理用户访问到的过期键，避免无效内存占用。

4. 调整清理逻辑 #

清理时直接从有序结构的头部开始，取出所有过期时间<=当前时间戳的条目批量删除，直到遇到第一个未过期的条目为止，将该条目的过期时间作为下一次唤醒的时间，直接返回给线程sleep即可，不需要遍历全量Entry。

调整后的看门狗核心逻辑示例 #

class TtlWatchdog extends Thread {
    @SneakyThrows
    @Override
    public void run() {
        System.out.println("Initiating Cleaner Thread..");
        while (true) {
            synchronized (lock) {
                // 无待过期条目时阻塞等待
                while (sortedExpireStructure.isEmpty()) {
                    lock.wait();
                }
                long nextExpireTime = sortedExpireStructure.firstKey();
                long currentTime = System.currentTimeMillis();
                if (nextExpireTime <= currentTime) {
                    // 清理所有已到期的条目
                    clearExpiredKeys();
                } else {
                    // 睡到下一个过期时间点
                    lock.wait(nextExpireTime - currentTime);
                }
            }
        }
    }
}

内容的提问来源于stack exchange，提问作者Shmuel