缓存系统

缓存系统

基于 LRUCache 的缓存系统，其结构包括哈希表和 LRU 双向链表。

LRUHandle

• 哈希表相关: next_hash 用于链接哈希表中的条目。
• 链表相关: next 和 prev 用于在 LRU 链表和使用中的链表（in_use）中形成双向链表。

哈希表

• 结构: 哈希表由多个存储桶组成，每个存储桶包含一个链接链表，用于存储散列到该存储桶中的缓存条目。

• 插入逻辑：

  • 先找到对应的存储桶。
  • 比较哈希值和键值，如果找到则替换条目，否则将新条目插入到链表末尾。
  • 当条目数量超过容量时，重新调整哈希表的大小。

LRUCache

由哈希表、LRU 链表头和 in_use 链表头构成。

1. 插入过程:
   • 加锁。
   • 根据键创建 handle，引用计数加 1，并插入到 in_use_ 链表。
   • 将 handle 添加到哈希表中。
   • 如果键已存在，则返回旧的 handle，并从缓存和链表中删除旧条目，引用计数减 1。
   • 当缓存容量超出限制且 LRU 链表不为空时，从 LRU 链表中移除第一个条目，并从缓存和链表中删除。
2. 查找过程:
   • 加锁。
   • 在哈希表中查找 handle 并返回，引用计数加 1。
3. 释放过程:
   • 使用完 handle 后需要手动释放。
   • 加锁，引用计数减 1。
4. 擦除过程:
   • 加锁，从缓存中移除条目，引用计数减 1。

SharedLRUCache

对 LRUCache 进行进一步封装，通过取哈希值的高 4 位来决定分片位置。

• 分片优势: 通过分片将缓存操作分散到多个 LRUCache 实例中，提升了访问效率，降低了锁的竞争，改善了并发性能。