📚 课程目录第2章 TTL过期机制与数据结构

第二章：TTL过期机制与数据结构

2.1 为什么需要TTL

在生产缓存系统中，数据并非永久有效。TTL（Time-To-Live，生存时间）机制允许为每个缓存条目设置一个过期时间，到达该时间后条目自动失效。TTL解决了以下关键问题：

数据一致性：后端数据更新后，缓存中的旧数据应在合理时间内失效
内存释放：自动清理不再需要的过期键，防止缓存“僵尸数据”堆积
降低复杂度：无需上层应用手动调用删除接口，由缓存层自主管理

2.2 时间戳存储方案

TTL的实现核心是将过期时间戳与键值对绑定存储。常见方案有两种：

方案	存储结构	空间开销	精度	适用场景
时间戳	int64_t 表示的Unix毫秒时间戳	8字节/条目	毫秒级	通用场景，易于比较和排序
相对TTL	int32_t 或 int64_t 表示的剩余秒数	4~8字节/条目	秒级	简化实现，但每次访问需更新时间

推荐方案：在LRU+TTL混合缓存中，建议使用时间戳。因为惰性删除和定期扫描都依赖“当前时间 - 过期时间”的比较，时间戳无需计算相对值，性能更高且不易出现时钟漂移累积误差。

2.3 过期键清理策略总览

TTL过期键不会在到期瞬间被立即删除，而是采用惰性删除与定期扫描相结合的方案，兼顾CPU开销和内存利用率。

惰性删除：在访问键时检查是否过期，如果过期则删除并返回空
定期扫描：后台协程/线程每隔固定周期扫描一定比例或全部键，删除过期条目
强制淘汰：当内存超过阈值时，即使未过期也可能被LRU淘汰

2.4 惰性删除详解

惰性删除是TTL清理的第一道防线，其流程如下：

上层调用 Get(key) 或 Exists(key) 等操作时
从哈希表或链表中找到条目
比较当前系统时间与条目的过期时间戳
如果当前时间 ≥ 过期时间戳，则判定为过期：
将条目从LRU双向链表和哈希表中移除
返回“未命中”或“已删除”
如果未过期，则正常返回数据，并将节点移至链表头部

  核心优点：惰性删除保证每个访问操作最多执行一次过期检查，不会引入额外扫描负担。但在缓存冷门数据（长期不被访问）时，过期键会一直驻留内存，直到内存压力触发定期扫描或淘汰。

2.5 定期扫描详解

定期扫描作为补充策略，防止大量过期键“休眠”在内存中。典型实现参数：

参数	推荐值	说明
`scan_interval_ms`	100 ~ 500 ms	两次扫描之间的间隔
`scan_batch_size`	20 ~ 100	每次扫描最多检查的条目数
`scan_max_ratio`	25%	每次扫描最多删除的过期键占总过期键的比例
`scan_timeout_us`	1000	单次扫描最大耗时（微秒），避免阻塞业务

// 伪代码：定期扫描循环
void PeriodicScanLoop() {
    while (!shutdown_) {
        std::this_thread::sleep_for(std::chrono::milliseconds(scan_interval_ms_));

        int checked = 0;
        int deleted = 0;
        auto now = Clock::now();

        for (auto it = lru_list_.begin(); it != lru_list_.end() && checked < scan_batch_size_; ++it) {
            if (it->expire_time <= now) {
                // 删除过期条目
                RemoveNode(it);
                ++deleted;
            }
            ++checked;
        }

        // 如果本次删除比例过高，下次缩短扫描间隔
        if (deleted > scan_batch_size_ * scan_max_ratio_ / 100) {
            last_high_load_ = true;
        }
    }
}

2.6 整体过期清理流程图

2.7 两种策略对比

特性	惰性删除	定期扫描
触发时机	每次键访问	定时后台循环
CPU开销	分摊到访问，几乎无额外成本	固定周期消耗，可配置
内存释放及时性	仅清理被访问的过期键	清理未被访问的“僵尸”键
对冷门键效果	长期驻留，可能造成内存浪费	定期清理，防止缓存膨胀
并发安全	需要在读路径上加锁或使用CAS	扫描时需持有锁，但可分批处理

常见误区：不要只使用惰性删除。如果业务中大量键在写入后从未被访问（例如临时令牌、一次性验证码），这些过期键会永久堆积，最终导致OOM。定期扫描是必须的兜底机制。

2.8 代码实现要点

在C++实现中，每个缓存节点至少包含以下字段：

struct CacheNode {
    std::string key;
    std::string value;
    int64_t expire_time;  // Unix毫秒时间戳，0表示永不过期
    // LRU链接：prev, next 指针
    CacheNode* prev;
    CacheNode* next;
};

惰性删除在 get() 中的示例：

std::optional<std::string> LRUCache::Get(const std::string& key) {
    std::lock_guard<std::mutex> lock(mutex_);

    auto it = hash_map_.find(key);
    if (it == hash_map_.end()) {
        return std::nullopt;
    }

    CacheNode* node = it->second;

    // 惰性删除检查
    int64_t now = GetCurrentMillis();
    if (node->expire_time != 0 && node->expire_time <= now) {
        // 过期：从链表和哈希表中移除
        RemoveNode(node);
        hash_map_.erase(it);
        delete node;
        --size_;
        return std::nullopt;
    }

    // 未过期，移动到链表头
    MoveToHead(node);
    return node->value;
}

定期扫描循环需要在单独的线程中运行，并注意与LRU操作互斥：

void LRUCache::ScanExpiredKeys() {
    std::lock_guard<std::mutex> lock(mutex_);
    int64_t now = GetCurrentMillis();
    int checked = 0;

    // 从链表尾部（最久未使用）开始遍历，因为冷门键更可能过期
    CacheNode* cur = tail_;
    while (cur != nullptr && checked < scan_batch_size_) {
        CacheNode* next = cur->prev;  // 保存prev，因为cur可能被删除
        if (cur->expire_time != 0 && cur->expire_time <= now) {
            hash_map_.erase(cur->key);
            RemoveNode(cur);
            delete cur;
            --size_;
        }
        cur = next;
        ++checked;
    }
}

2.9 工程实践建议

扫描方向选择：从LRU链表尾部（最久未使用）开始扫描，因为冷门键过期概率更高，能更快释放内存
扫描耗时控制：即使在锁内，单次扫描也不应超过1ms，避免阻塞大量读请求
动态调整频率：如果某次扫描删除比例高于25%，可适当降低扫描间隔；反之则增大间隔，减少CPU消耗
与LRU淘汰的协同：当内存达到上限时，LRU淘汰会优先淘汰过期键（即使惰性删除和定期扫描还未处理），其次淘汰最久未使用的键

性能指标：在一个100万条目、TTL平均60秒的缓存中，惰性删除覆盖约80%的过期键清理，定期扫描负责剩余20%，整体CPU占用率在单核2%以下（扫描间隔200ms，批大小50）。如果TTL较短（如10秒），建议将扫描间隔缩短到50ms，批大小增大到200。

2.10 本章小结

TTL过期机制通过时间戳存储、惰性删除和定期扫描三种技术协同工作。时间戳存储在节点内，为每个键绑定一个到期时间点；惰性删除在访问时被动检查，低开销但无法处理冷门键；定期扫描主动从链表尾部遍历，弥补惰性删除的不足。两者结合能够以极低的CPU代价保障缓存内存被及时回收。