ConcurrentCacheSystem

一个无第三方运行时依赖的 C++17 header-only 并发缓存实验项目。它实现了分片 LRU、LRU-K、带延迟老化的 LFU 与 ARC，并提供统一接口、线程安全访问、原子统计 和可复现的基准测试。

项目定位：用于学习并验证缓存淘汰策略、锁分片和并发工程实践。当前版本不是 经过生产环境长期验证的通用缓存组件。

特性

策略	实现	主要用途
LRU	Cache::HighConcurrencyCache	通用、访问局部性较强的负载
LRU-K	Cache::LruKCache	降低一次性扫描造成的缓存污染
LFU	Cache::ShardedLFUCache	热点访问频率相对稳定的负载
ARC	Cache::ShardedARCCache	在近期性与访问频率之间自适应

• 锁分片降低不同 key 之间的锁竞争。
• CachePolicy 提供统一的 put/get/peek/erase/contains 接口。
• 命中、未命中和淘汰计数使用 relaxed atomic，不占用分片锁。
• CMake、CTest、AddressSanitizer、UndefinedBehaviorSanitizer 和 GitHub Actions。
• 基准脚本包含热点读、混合读写、顺序扫描和写密集四类负载。

快速开始

#include "LRU.h"

#include <iostream>
#include <string>

int main()
{
    Cache::HighConcurrencyCache<int, std::string> cache(1024, 8);
    cache.put(42, "answer");

    std::string value;
    if (cache.get(42, value)) {
        std::cout << value << '\n';
    }

    const Cache::CacheStats stats = cache.stats();
    std::cout << "hit rate: " << stats.hitRate() << '\n';
}

直接使用时，将所需头文件和 CachePolicy.h 加入 include path 即可。

构建与测试

要求：CMake 3.16+，支持 C++17 的 Clang 或 GCC。

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel
ctest --test-dir build --output-on-failure

启用 Sanitizer：

cmake -S . -B build-sanitized \
  -DCMAKE_BUILD_TYPE=Debug \
  -DCONCURRENT_CACHE_ENABLE_SANITIZERS=ON
cmake --build build-sanitized --parallel
ctest --test-dir build-sanitized --output-on-failure

运行基准

./run_cache_benchmark.sh . 1000000 16384 8 8

参数依次为：头文件目录、每个场景的操作数、缓存容量、线程数、分片数。结果会输出 耗时、吞吐量、命中率、写入数、最终大小和已知淘汰数。

也可以使用 Docker：

docker compose up --build

基准结果与 CPU、编译器、线程数、数据分布密切相关。请在固定环境中多次运行，并 使用中位数比较；不要把单次微基准结果直接等同于生产性能。

设计概览

key
 └─ hash(key) % shard_count
     └─ shard mutex
         ├─ policy metadata
         └─ key/value storage

global stats
 └─ relaxed atomics (hits / misses / evictions)

每个 key 始终路由到固定分片。不同分片可以并行执行，同一分片内由互斥锁保护策略 元数据。size() 等跨分片操作是逐分片快照，不保证与并发写入构成全局线性一致的 瞬时视图。

复杂度

操作	LRU	LRU-K	LFU	ARC
get	平均 O(1)	平均 O(1)	O(log F)	平均 O(1)
put	平均 O(1)	平均 O(1)	O(log F)	平均 O(1)
空间	O(C)	O(C + H)	O(C)	O(C)

C 是缓存容量，H 是 LRU-K 历史区容量，F 是当前频率桶数量。

项目结构

.
├── CachePolicy.h
├── LRU.h
├── LFU.h
├── ARC.h
├── tests/cache_tests.cpp
├── run_cache_benchmark.sh
└── .github/workflows/ci.yml

后续计划

• 增加 ThreadSanitizer 独立任务和长时间并发压力测试。
• 增加固定硬件环境下的基准历史与性能回归阈值。
• 补充自定义 allocator、TTL 和容量动态调整实验。
• 对比 oneTBB、Folly 等成熟实现，明确适用边界。

License

MIT