手写 TTL 缓存

组合可注入单调时钟、最小堆惰性删除和 LRU 容量控制，实现可确定测试的过期缓存。

本系列代码使用 C++20 和 oc::handmade 命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。

一、学习目标

使用 steady_clock 表达期限
处理重复更新产生的陈旧堆项
让测试不依赖真实 sleep

二、前置条件

完成 priority_queue 与 LRU 缓存篇，熟悉 chrono。

Linux/macOS：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure

Windows PowerShell：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

三、问题与设计选择

哈希表保存值、到期时间、代号与 LRU 节点；最小堆保存 (expires,generation,key)。清理时只有代号仍匹配的堆项有效。

这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。

四、内存布局与核心不变量

任何可命中条目的 expires 晚于当前时钟；generation 唯一标识一次写入；容量超限时先清过期再淘汰 LRU。

每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。

五、核心实现

void purge_expired(time_point now) {
    while (!expiry_.empty() && expiry_.top().expires <= now) {
        auto item = expiry_.top();
        expiry_.pop();
        auto found = entries_.find(item.key);
        if (found != entries_.end() &&
            found->second.generation == item.generation)
            erase(found);
    }
}

上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。

六、完整教学实现

下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。

namespace oc::handmade {

template<
    class Key,
    class Value,
    class Clock = std::chrono::steady_clock,
    class Hash = std::hash<Key>
>
class ttl_cache {
public:
    using time_point = typename Clock::time_point;
    using duration = typename Clock::duration;
private:
    struct record {
        Value value;
        time_point expires;
        std::uint64_t generation;
        typename std::list<Key>::iterator recency;
    };
    struct deadline {
        time_point expires;
        std::uint64_t generation;
        Key key;
        bool operator>(const deadline& other) const { return expires > other.expires; }
    };
    std::size_t capacity_;
    std::uint64_t generation_{};
    std::unordered_map<Key, record, Hash> entries_;
    std::list<Key> recency_;
    std::priority_queue<deadline, std::vector<deadline>, std::greater<deadline>> expiry_;

    void erase(typename std::unordered_map<Key, record, Hash>::iterator found) {
        recency_.erase(found->second.recency);
        entries_.erase(found);
    }
public:
    explicit ttl_cache(std::size_t capacity) : capacity_(capacity) {}
    void purge_expired(time_point now = Clock::now()) {
        while (!expiry_.empty() && expiry_.top().expires <= now) {
            deadline item = expiry_.top();
            expiry_.pop();
            auto found = entries_.find(item.key);
            if (found != entries_.end() &&
                found->second.generation == item.generation)
                erase(found);
        }
    }
    void put(Key key, Value value, duration ttl, time_point now = Clock::now()) {
        if (capacity_ == 0) return;
        purge_expired(now);
        if (auto found = entries_.find(key); found != entries_.end()) erase(found);
        const auto expires = now + ttl;
        const auto token = ++generation_;
        recency_.push_front(key);
        entries_.emplace(
            key, record{std::move(value), expires, token, recency_.begin()});
        expiry_.push({expires, token, std::move(key)});
        if (entries_.size() > capacity_) {
            auto found = entries_.find(recency_.back());
            erase(found);
        }
    }
    std::optional<Value> get(const Key& key, time_point now = Clock::now()) {
        purge_expired(now);
        auto found = entries_.find(key);
        if (found == entries_.end()) return std::nullopt;
        recency_.splice(recency_.begin(), recency_, found->second.recency);
        return found->second.value;
    }
    bool contains(const Key& key, time_point now = Clock::now()) {
        return get(key, now).has_value();
    }
    bool erase(const Key& key) {
        auto found = entries_.find(key);
        if (found == entries_.end()) return false;
        erase(found);
        return true;
    }
    std::size_t size() const noexcept { return entries_.size(); }
    std::size_t capacity() const noexcept { return capacity_; }
};

}  // namespace oc::handmade

生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。

七、使用示例与输出

预期输出或状态：

假时钟推进 99ms 时键仍命中，推进到 100ms 后未命中；更新后的旧堆项不会误删新值。

示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。

八、复杂度与失效规则

操作	复杂度	说明
get	平均 O(1)+清理	过期视为未命中
put	O(log n)	压入期限堆
purge	O(k log n)	k 个到期项
容量淘汰	O(1)	LRU 尾

复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。

九、异常安全与资源管理

获取资源后立即交给 RAII 对象或明确记录已构造数量。
用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
只有在所有后续步骤不会失败时才修改不可回滚的链接。
析构、释放和关闭路径不得抛异常。
并发包装通过回调在锁内访问，避免返回保护对象的裸引用。

十、常见错误

1. 使用 system_clock 导致时间回拨

使用 system_clock 导致时间回拨会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 更新键后旧到期项删除新值

更新键后旧到期项删除新值会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 在测试中真实 sleep 造成不稳定

在测试中真实 sleep 造成不稳定会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

十一、面试追问

惰性删除为什么需要 generation？
主动清理线程与访问时清理如何取舍？
TTL 与容量淘汰谁先执行？

回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。

十二、练习与自测

实现 fake_clock
增加 refresh-on-access 模式
测量大量陈旧堆项的开销

自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。

十三、官方资料与延伸阅读

上一篇：手写 LFU 缓存｜下一篇：手写 2Q 缓存