手写 2Q 缓存

手写 2Q 缓存

使用 A1in、A1out 和 Am 三个队列抵抗一次性扫描，理解幽灵记录的价值。

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

---

一、学习目标

• 实现冷队列、热队列和幽灵队列
• 识别重复进入的真正热点
• 解释 2Q 如何改善扫描污染

---

二、前置条件

完成 FIFO 与 LRU 缓存篇。

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

---

三、问题与设计选择

首次访问进入 A1in FIFO；从 A1in 淘汰的键进入仅存键的 A1out；再次命中幽灵键时进入 Am LRU。容量在冷、热队列间分配。

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

---

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

实际值只存在于 A1in 或 Am；A1out 只存幽灵键；三个集合互斥且大小受各自预算限制。

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

---

五、核心实现

if (ghost_.contains(key)) {
    ghost_.erase(key);
    ensure_room_for_hot();
    hot_.push_front({key, std::move(value)});
    hot_index_[key] = hot_.begin();
} else {
    cold_.push_back({key, std::move(value)});
    cold_index_[key] = std::prev(cold_.end());
    trim_cold();
}

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

---

六、完整教学实现

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

namespace oc::handmade {

template<class Key, class Value, class Hash = std::hash<Key>>
class two_q_cache {
    using item = std::pair<Key, Value>;
    std::size_t capacity_;
    std::size_t cold_capacity_;
    std::list<item> cold_;
    std::list<item> hot_;
    std::list<Key> ghost_;
    std::unordered_map<Key, typename std::list<item>::iterator, Hash> cold_index_;
    std::unordered_map<Key, typename std::list<item>::iterator, Hash> hot_index_;
    std::unordered_map<Key, typename std::list<Key>::iterator, Hash> ghost_index_;

    void trim_ghost() {
        while (ghost_.size() > capacity_) {
            ghost_index_.erase(ghost_.front());
            ghost_.pop_front();
        }
    }
    void evict_cold() {
        Key key = cold_.front().first;
        cold_index_.erase(key);
        cold_.pop_front();
        ghost_.push_back(key);
        ghost_index_[key] = std::prev(ghost_.end());
        trim_ghost();
    }
    void ensure_room() {
        while (cold_.size() + hot_.size() >= capacity_) {
            if (!cold_.empty() && (cold_.size() > cold_capacity_ || hot_.empty()))
                evict_cold();
            else {
                hot_index_.erase(hot_.back().first);
                hot_.pop_back();
            }
        }
    }
public:
    explicit two_q_cache(std::size_t capacity)
        : capacity_(capacity),
          cold_capacity_(capacity == 0 ? 0 : std::max<std::size_t>(1, capacity / 4)) {}
    std::size_t size() const noexcept { return cold_.size() + hot_.size(); }
    std::size_t capacity() const noexcept { return capacity_; }
    bool contains(const Key& key) const {
        return cold_index_.contains(key) || hot_index_.contains(key);
    }
    std::optional<Value> get(const Key& key) {
        if (auto hot = hot_index_.find(key); hot != hot_index_.end()) {
            hot_.splice(hot_.begin(), hot_, hot->second);
            return hot->second->second;
        }
        if (auto cold = cold_index_.find(key); cold != cold_index_.end())
            return cold->second->second;
        return std::nullopt;
    }
    bool erase(const Key& key) {
        if (auto cold = cold_index_.find(key); cold != cold_index_.end()) {
            cold_.erase(cold->second);
            cold_index_.erase(cold);
            return true;
        }
        if (auto hot = hot_index_.find(key); hot != hot_index_.end()) {
            hot_.erase(hot->second);
            hot_index_.erase(hot);
            return true;
        }
        return false;
    }
    void put(Key key, Value value) {
        if (capacity_ == 0) return;
        if (auto hot = hot_index_.find(key); hot != hot_index_.end()) {
            hot->second->second = std::move(value);
            hot_.splice(hot_.begin(), hot_, hot->second);
            return;
        }
        if (auto cold = cold_index_.find(key); cold != cold_index_.end()) {
            cold->second->second = std::move(value);
            return;
        }
        if (auto ghost = ghost_index_.find(key); ghost != ghost_index_.end()) {
            ghost_.erase(ghost->second);
            ghost_index_.erase(ghost);
            ensure_room();
            hot_.push_front({std::move(key), std::move(value)});
            hot_index_[hot_.front().first] = hot_.begin();
            return;
        }
        ensure_room();
        cold_.push_back({std::move(key), std::move(value)});
        cold_index_[cold_.back().first] = std::prev(cold_.end());
        if (cold_.size() > cold_capacity_) evict_cold();
    }
};

}  // namespace oc::handmade

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

---

七、使用示例与输出

预期输出或状态：

顺序扫描 A B C D 不会把再次访问的热点 X 从 Am 中挤出；第二次出现 A 时从幽灵队列晋升。

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

---

八、复杂度与失效规则

操作	复杂度	说明
get/put	平均 O(1)	可能跨队列移动
A1in 淘汰	O(1)	键进入 A1out
Am 淘汰	O(1)	LRU 尾
幽灵命中	O(1)	直接晋升 Am

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

---

九、异常安全与资源管理

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

---

十、常见错误

1. 幽灵队列继续保存 value

幽灵队列继续保存 value会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 同一键同时出现在冷热队列

同一键同时出现在冷热队列会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 容量比例写死却不在文档说明

容量比例写死却不在文档说明会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

---

十一、面试追问

1. 幽灵条目为什么有用？
2. 2Q 与 LRU-K 的思想有何相似？
3. 冷区预算如何影响扫描抵抗？

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

---

十二、练习与自测

1. 画出键跨三个队列的状态机
2. 实现可配置冷区比例
3. 用扫描加热点轨迹比较 LRU

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

---

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

• C++20 工作草案 N4861
• C++ Core Guidelines
• 2Q 原始论文

---

上一篇：手写 TTL 缓存 ｜ 下一篇：手写 ARC 缓存