fast-cache-deduplicator 是一个为高并发场景设计的线程安全缓存库，专门用于处理整数类型 ID 的去重。它采用 C++17 标准实现，通过结合哈希表、双向链表和时间轮算法，提供高效的 O(1) 时间复杂度的插入、查找和淘汰操作，确保在高负载下依然保持出色的、可预测的性能。

• 线程安全：使用读写锁 (std::shared_mutex) 优化并发访问，允许多线程并发读取，并在写入时保证数据一致性。
• 高效去重：利用哈希表 (std::unordered_map) 实现 O(1) 平均时间复杂度的去重判断。
• O(1) 淘汰策略：当缓存达到容量上限时，通过 std::list 实现的 LRU (最近最少使用) 策略可在 O(1) 时间内淘汰最旧的数据。
• 自动过期：基于时间轮算法，在后台线程中自动清理过期 ID，有效管理内存，避免了在高负载下扫描整个缓存的开销。
• 灵活配置：提供丰富的配置选项，如最大容量、过期时间、清理间隔等，以适应不同业务场景。
• 易于集成：作为头文件库 (header-only) 提供，只需包含 concurrent_id_cache.h 即可轻松集成到任何 CMake 项目中。

本缓存库的核心设计思想是在保证高并发性能和可预测性的前提下，实现高效的内存管理。其关键组成部分如下：

1. 核心数据结构：

   • std::unordered_map：用于存储 ID 及其对应的缓存条目。这保证了平均 O(1) 时间复杂度的查找、插入和删除操作。
   • std::list：作为一个双向链表，用于实现 LRU 策略。所有缓存条目按访问顺序排列，最新访问的位于链表头部。当需要淘汰数据时，只需从链表尾部移除即可，此操作时间复杂度为 O(1)。

2. 并发控制：

   • 采用 std::shared_mutex (读写锁) 来管理并发访问。读操作（如查找）可以并发进行，而写操作（如插入、更新、删除）则需要获取独占锁。insert 方法经过特别优化，采用“先读后写”的检查模式，以最大程度地减少写锁的持有时间，降低锁竞争。

3. 过期机制：

   • 时间轮 (Time Wheel)：为了避免定期扫描整个缓存来查找过期条目，本库实现了一个时间轮。新条目根据其过期时间被放入时间轮的特定“槽”中。一个后台清理线程只需定时检查并处理当前到期的槽位，极大地降低了过期处理的成本。

该设计在性能可预测性和资源开销之间做出了权衡。通过引入 std::list 和时间轮，我们确保了即使在缓存已满或需要清理大量过期数据等最坏情况下，关键操作的性能依然稳定。虽然这会带来轻微的内存开销和实现复杂度的增加，但它避免了在高负载下可能出现的性能悬崖，为系统提供了更强的稳健性。

• C++17 或更高版本
• CMake 3.10 或更高版本
• Google Test (用于测试)
• Google Benchmark (用于性能基准测试)

# 克隆仓库
git clone <repository_url>
cd fast-cache-deduplicator

# 创建构建目录
mkdir build
cd build

# 配置并构建项目
cmake ..
make

# 运行单元测试
./test_concurrent_id_cache

# 运行性能基准测试
./benchmark_cache

#include "concurrent_id_cache.h"
#include <iostream>

int main() {
    // 使用默认配置创建缓存实例
    fast_cache_deduplicator::ConcurrentDeduplicationCache<int> cache;

    // 插入新 ID
    if (cache.insert(123)) {
        std::cout << "ID 123 是新的，已插入。" << std::endl;
    } else {
        std::cout << "ID 123 已存在。" << std::endl;
    }

    // 再次插入相同的 ID
    if (!cache.insert(123)) {
        std::cout << "ID 123 已存在，未插入。" << std::endl;
    }

    // 查询当前缓存大小
    std::cout << "当前缓存大小: " << cache.size() << std::endl;

    return 0;
}

以下是在配备 12 核 2.4 GHz CPU 的设备上运行的基准测试结果。请注意，性能数据可能因硬件和编译配置而异。