手写 Window TinyLFU 缓存

组合窗口 LRU、分段 LRU、Doorkeeper 与 Count-Min Sketch，实现基于频率估计的缓存准入。

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

一、学习目标

区分淘汰策略与准入策略
实现近似频率统计和周期衰减
理解 W-TinyLFU 的窗口与主区

二、前置条件

完成 LRU、LFU 与 ARC 篇，熟悉概率数据结构。

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

三、问题与设计选择

新项先进入小型 window LRU；窗口候选与主区 probation 受害者比较估计频率。主区使用 probation/protected SLRU；Doorkeeper 过滤首次访问，Count-Min Sketch 记录重复频率。

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

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

三个实际区总量不超过 capacity；键只存在一个区；计数器饱和且每个采样周期减半；准入比较使用同一估计器。

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

五、核心实现

bool admit(const Key& candidate, const Key& victim) const {
    return frequency_.estimate(candidate) >=
           frequency_.estimate(victim);
}

void age_if_needed() {
    if (++samples_ >= sample_limit_) {
        frequency_.halve();
        doorkeeper_.clear();
        samples_ = 0;
    }
}

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

六、完整教学实现

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

namespace oc::handmade {

template<class Key, class Value, class Hash = std::hash<Key>>
class window_tinylfu_cache {
    using item = std::pair<Key, Value>;
    std::size_t capacity_;
    std::size_t window_capacity_;
    std::size_t protected_capacity_;
    std::list<item> window_;
    std::list<item> probation_;
    std::list<item> protected_;
    std::unordered_map<Key, typename std::list<item>::iterator, Hash> window_index_;
    std::unordered_map<Key, typename std::list<item>::iterator, Hash> probation_index_;
    std::unordered_map<Key, typename std::list<item>::iterator, Hash> protected_index_;
    std::unordered_map<Key, std::uint16_t, Hash> frequency_;
    std::size_t samples_{};

    void record(const Key& key) {
        auto& counter = frequency_[key];
        if (counter != std::numeric_limits<std::uint16_t>::max()) ++counter;
        if (++samples_ >= std::max<std::size_t>(10, capacity_ * 10)) {
            for (auto& [unused, value] : frequency_) value /= 2;
            samples_ = 0;
        }
    }
    std::uint16_t estimate(const Key& key) const {
        if (auto found = frequency_.find(key); found != frequency_.end()) return found->second;
        return 0;
    }
    void demote_protected_if_needed() {
        while (protected_.size() > protected_capacity_) {
            auto value = std::move(protected_.back());
            protected_index_.erase(value.first);
            protected_.pop_back();
            probation_.push_front(std::move(value));
            probation_index_[probation_.front().first] = probation_.begin();
        }
    }
    void admit(item candidate) {
        const std::size_t main_capacity = capacity_ - window_capacity_;
        if (probation_.size() + protected_.size() < main_capacity) {
            probation_.push_front(std::move(candidate));
            probation_index_[probation_.front().first] = probation_.begin();
            return;
        }
        if (probation_.empty()) return;
        const Key victim = probation_.back().first;
        if (estimate(candidate.first) >= estimate(victim)) {
            probation_index_.erase(victim);
            probation_.pop_back();
            probation_.push_front(std::move(candidate));
            probation_index_[probation_.front().first] = probation_.begin();
        }
    }
    void trim_window() {
        while (window_.size() > window_capacity_) {
            item candidate = std::move(window_.back());
            window_index_.erase(candidate.first);
            window_.pop_back();
            admit(std::move(candidate));
        }
    }
public:
    explicit window_tinylfu_cache(std::size_t capacity)
        : capacity_(capacity),
          window_capacity_(capacity == 0 ? 0 : std::max<std::size_t>(1, capacity / 100)),
          protected_capacity_(
              capacity <= window_capacity_ ? 0 :
              (capacity - window_capacity_) * 4 / 5
          ) {}
    std::size_t size() const noexcept {
        return window_.size() + probation_.size() + protected_.size();
    }
    std::size_t capacity() const noexcept { return capacity_; }
    bool contains(const Key& key) const {
        return window_index_.contains(key) ||
               probation_index_.contains(key) ||
               protected_index_.contains(key);
    }
    std::optional<Value> get(const Key& key) {
        record(key);
        if (auto found = window_index_.find(key); found != window_index_.end()) {
            window_.splice(window_.begin(), window_, found->second);
            return found->second->second;
        }
        if (auto found = protected_index_.find(key); found != protected_index_.end()) {
            protected_.splice(protected_.begin(), protected_, found->second);
            return found->second->second;
        }
        if (auto found = probation_index_.find(key); found != probation_index_.end()) {
            item value = std::move(*found->second);
            probation_.erase(found->second);
            probation_index_.erase(found);
            protected_.push_front(std::move(value));
            protected_index_[protected_.front().first] = protected_.begin();
            demote_protected_if_needed();
            return protected_.front().second;
        }
        return std::nullopt;
    }
    bool erase(const Key& key) {
        if (auto found = window_index_.find(key); found != window_index_.end()) {
            window_.erase(found->second);
            window_index_.erase(found);
            return true;
        }
        if (auto found = probation_index_.find(key); found != probation_index_.end()) {
            probation_.erase(found->second);
            probation_index_.erase(found);
            return true;
        }
        if (auto found = protected_index_.find(key); found != protected_index_.end()) {
            protected_.erase(found->second);
            protected_index_.erase(found);
            return true;
        }
        return false;
    }
    void put(Key key, Value value) {
        if (capacity_ == 0) return;
        record(key);
        if (contains(key)) erase(key);
        window_.push_front({std::move(key), std::move(value)});
        window_index_[window_.front().first] = window_.begin();
        trim_window();
    }
};

}  // namespace oc::handmade

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

七、使用示例与输出

预期输出或状态：

一次性扫描项停留在窗口且通常不能替换高频主区项；新热点重复访问后获得准入。

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

八、复杂度与失效规则

操作	复杂度	说明
record/get/put	近似 O(1)	固定哈希行数
窗口淘汰	O(1)	候选参与准入
SLRU 提升	O(1)	probation 到 protected
aging	O(计数器数)	按采样周期摊还

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

九、异常安全与资源管理

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

十、常见错误

1. 把 TinyLFU 当作完整淘汰队列

把 TinyLFU 当作完整淘汰队列会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 计数器不衰减导致历史永久污染

计数器不衰减导致历史永久污染会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 测试中不固定哈希种子

测试中不固定哈希种子会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

十一、面试追问

准入与淘汰有什么区别？
Count-Min Sketch 为什么只会高估？
window 大小如何影响突发热点？

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

十二、练习与自测

实现四行 Count-Min Sketch
增加 4-bit 饱和计数器
比较纯 LRU 与 W-TinyLFU 的 Zipf 命中率

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

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

上一篇：手写 ARC 缓存｜下一篇：综合测试、性能基准与面试复盘