# al_cache **Repository Path**: diabio/al_cache ## Basic Information - **Project Name**: al_cache - **Description**: 这是用cpp实现的线程安全的缓存系统 - **Primary Language**: Unknown - **License**: MulanPSL-2.0 - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2025-04-15 - **Last Updated**: 2025-06-06 ## Categories & Tags **Categories**: Uncategorized **Tags**: Cpp, cmake ## README # 缓存系统项目 ## 概念和目的 ### 什么是缓存？ 缓存（Cache）是一种用于**临时存储高频访问数据**的技术，旨在**加速数据检索、减少计算或I/O开销**，从而提升系统性能。其核心思想是：**用空间换时间**，通过存储副本或中间结果，避免重复处理相同请求。 **存储位置**： - **内存缓存**（如 Redis、Memcached）：速度快，但容量有限，断电后数据丢失。 - **磁盘缓存**：速度较慢，但容量大，适合持久化存储。 - **CPU缓存**（L1/L2/L3）：硬件级缓存，减少CPU访问内存的延迟。 ### 为什么要实现缓存系统？ - **降低延迟**：从缓存读取比从数据库/磁盘快几个数量级（如内存纳秒级 vs 磁盘毫秒级）。 - **减轻负载**：减少对数据库、API等后端服务的压力。 - **提升吞吐量**：避免重复计算（如渲染页面、复杂查询）。 ### 缓存会应用到哪些地方？ - **Web缓存**：浏览器缓存静态资源（如图片、CSS），CDN缓存网站内容。 - **数据库缓存**：如MySQL的查询缓存、Redis缓存热点数据。 - **CPU/GPU缓存**：存储频繁使用的指令或数据。 - **应用层缓存**：缓存计算结果（如API响应、页面片段）。 ## 缓存策略对比 | 算法策略 | 原理 | 优点 | 缺点 | 实现复杂度 | 空间开销 | 缓存命中率 | 对新数据适应性 | 适用场景 | | ---------- | --------------------------------- | ------------------------------ | ------------------------- | ----- | ---- | ----- | ------- | ------------------------------- | | FIFO | 按数据进入缓存的先后顺序，缓存满时淘汰最早进入的数据 | 实现简单，开销小，无需额外记录访问信息 | 不考虑数据访问频率和时效性，可能淘汰频繁访问的数据 | 低 | 低 | 一般 | 好 | 日志缓存 | | LIFO | 后进先出，缓存满时淘汰最后进入的数据 | 实现简单 | 未考虑数据访问频率和重要性，可能频繁淘汰常用数据 | 低 | 低 | 一般 | 差 | 适合一次性处理大量数据且只需保留最新数据的场景，如临时文件缓存 | | LRU | 基于局部性原理，缓存满时淘汰最久未被访问的数据 | 适应数据局部性特征，减少缓存缺失率 | 实现较复杂，对突发批量访问处理不佳 | 中 | 中 | 较高 | 一般 | 数据库查询缓存、Web 服务器缓存 | | LRU - K | 记录数据前 K 次访问信息，缓存满时淘汰 K 次访问时间最早的数据 | 处理周期性和局部性数据表现优，可调整 K 值平衡性能和复杂度 | 实现复杂度高，K 值选择困难 | 高 | 高 | 高 | 一般 | 多媒体数据缓存 | | Hash - LRU | 在 LRU 基础上用哈希表加速数据查找和插入 | 结合哈希表快速查找与 LRU 淘汰策略，提高查找性能 | 存在哈希冲突问题，空间利用率可能低 | 中 | 中 | 较高 | 一般 | 分布式缓存系统 | | LFU | 根据数据访问频率，缓存满时淘汰访问频率最低的数据 | 保留访问频率高的数据，适应访问模式变化 | 实现复杂度高，对新数据不友好 | 高 | 高 | 高 | 差 | 热门商品推荐缓存 | | Hash - LFU | 在 LFU 基础上用哈希表加速数据查找和插入 | 结合哈希表快速查找与 LFU 淘汰策略，提高查找性能 | 存在哈希冲突问题，对新数据不友好 | 高 | 高 | 高 | 差 | 搜索引擎缓存 | | ARC | 结合 LRU 和 LFU 思想，动态调整两部分大小适应不同访问模式 | 自适应调整缓存策略，通用性强 | 实现复杂度高，内存使用要求高 | 高 | 高 | 高 | 一般 | 数据库系统缓存 | ## 开发环境 #### 硬件 - **服务器**：阿里云服务器，具体规格按需配置。 #### 软件 - **操作系统**：Ubuntu 24 - **文本编辑器**：Vim - **构建工具**：CMake - **编译器**：GCC（版本随 Ubuntu 24 系统默认） ## 如何运行测试？ ```bash mkdir build cd build cmake .. make ./main ``` ## 测试结果 单线程且不开模拟数据源取数（不然时间太久了）缓存容量：50 ARC：25（LRU和LFU部分各25） ```cpp +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | Algorithm | Threads | Test Case | Runtime(s) | Throughput(ops/sec) | Avg Latency(μs/op) | Min Latency(μs/op) | Max Latency(μs/op) | Hit Rate(%) | Memory Usage(KB) | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | FIFO | 1 | hot | 0.95 | 1048198.11 | 0.36 | 0.00 | 68.00 | 79.76 | 74452 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LRU | 1 | hot | 1.71 | 585126.39 | 0.36 | 0.00 | 86.00 | 83.37 | 74452 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LRU-K | 1 | hot | 3.79 | 264195.77 | 2.59 | 0.00 | 717.00 | 83.37 | 74452 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LFU | 1 | hot | 107.82 | 9274.88 | 106.63 | 1.00 | 1086.00 | 83.30 | 74452 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LRU | 1 | hot | 1.70 | 588570.34 | 0.36 | 0.00 | 48.00 | 83.29 | 74452 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LRU-K | 1 | hot | 3.90 | 256273.96 | 2.63 | 0.00 | 2099.00 | 83.35 | 74452 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LFU | 1 | hot | 16.89 | 59191.49 | 15.77 | 1.00 | 1063.00 | 83.34 | 74500 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | ARC | 1 | hot | 7.00 | 142752.46 | 5.61 | 1.00 | 135.00 | 78.80 | 74628 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | Algorithm | Threads | Test Case | Runtime(s) | Throughput(ops/sec) | Avg Latency(μs/op) | Min Latency(μs/op) | Max Latency(μs/op) | Hit Rate(%) | Memory Usage(KB) | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | FIFO | 1 | loop_scan | 2.67 | 748502.99 | 0.93 | 0.00 | 170.00 | 4.63 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LRU | 1 | loop_scan | 3.70 | 541125.54 | 1.00 | 0.00 | 592.00 | 4.61 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LRU-K | 1 | loop_scan | 4.96 | 403388.46 | 1.61 | 0.00 | 212.00 | 6.27 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LFU | 1 | loop_scan | 139.06 | 14382.80 | 68.73 | 4.00 | 1258.00 | 5.25 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LRU | 1 | loop_scan | 3.64 | 549601.54 | 0.99 | 0.00 | 127.00 | 4.68 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LRU-K | 1 | loop_scan | 5.13 | 389559.80 | 1.70 | 0.00 | 93.00 | 6.77 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LFU | 1 | loop_scan | 20.21 | 98960.91 | 9.30 | 1.00 | 565.00 | 7.90 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | ARC | 1 | loop_scan | 14.54 | 137551.58 | 6.54 | 0.00 | 2048.00 | 5.62 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | Algorithm | Threads | Test Case | Runtime(s) | Throughput(ops/sec) | Avg Latency(μs/op) | Min Latency(μs/op) | Max Latency(μs/op) | Hit Rate(%) | Memory Usage(KB) | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | FIFO | 1 | workload_change | 1.81 | 1104362.23 | 0.50 | 0.00 | 115.00 | 46.86 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LRU | 1 | workload_change | 2.82 | 708968.45 | 0.57 | 0.00 | 189.00 | 47.88 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LRU-K | 1 | workload_change | 4.09 | 489476.26 | 1.20 | 0.00 | 116.00 | 49.29 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LFU | 1 | workload_change | 139.22 | 14365.65 | 68.81 | 5.00 | 2192.00 | 9.27 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LRU | 1 | workload_change | 2.77 | 722021.66 | 0.55 | 0.00 | 367.00 | 47.78 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LRU-K | 1 | workload_change | 4.24 | 471586.89 | 1.24 | 0.00 | 134.00 | 49.63 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LFU | 1 | workload_change | 19.60 | 102061.65 | 8.92 | 1.00 | 88.00 | 41.24 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | ARC | 1 | workload_change | 11.60 | 172413.79 | 4.99 | 0.00 | 77.00 | 40.38 | 125684 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ ``` 多线程情况 启用模拟从数据源取数（未命中时，会去数据源取数据，这个一般耗时较长）操作数：2000000 缓存容量：50 线程数：256 ``` +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | Algorithm | Threads | Test Case | Runtime(s) | Throughput(ops/sec) | Avg Latency(μs/op) | Min Latency(μs/op) | Max Latency(μs/op) | Hit Rate(%) | Memory Usage(KB) | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | FIFO | 256 | hot | 3.93 | 254208.19 | 848.93 | 0.00 | 32100.00 | 78.42 | 77268 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LRU | 256 | hot | 7.54 | 132598.12 | 1862.43 | 0.00 | 41289.00 | 83.33 | 77396 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LRU-K | 256 | hot | 12.33 | 81107.46 | 3042.33 | 0.00 | 66000.00 | 83.31 | 77396 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LRU | 256 | hot | 3.10 | 322598.39 | 752.27 | 0.00 | 37206.00 | 83.23 | 77396 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LRU | 256 | hot | 4.76 | 209919.19 | 1127.06 | 0.00 | 63547.00 | 83.34 | 77396 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | LFU | 256 | hot | 123.87 | 8073.49 | 30806.56 | 1.00 | 2290088.00 | 83.33 | 77396 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | HASH-LFU | 256 | hot | 15.12 | 66123.71 | 3744.44 | 1.00 | 116198.00 | 83.31 | 77396 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ | ARC | 256 | hot | 15.79 | 63350.75 | 3974.77 | 0.00 | 76395.00 | 79.41 | 77396 | +------------+----------+-----------------+------------+---------------------+--------------------+--------------------+--------------------+-------------+------------------+ ```