Concurrent LRU Cache¶

实际上并发 LRU Cache 是由多个 LRU Cache 组成的，每个 LRU Cache 和一把 lock 组成一个 Bucket，Concurrent LRU Cache 实际上就是 Bucket 数组。每个 LRU Cache 由自己的锁保护，使用 hash 来实现 bucket 并发，锁只在 bucket 这个粒度上。

LRU Cache¶

相较于标准的 map + 链表实现，nebula 用 std::unordered_map<K, std::pair<V, typename std::list<K>::iterator>> 替代std::map，通过一个指向在链表中对应键的迭代器实现 O(1)时间复杂度更新。std::unordered_map 替换了 std::map，意味着查找、插入、删除的平均时间复杂度从 O(log N)提升到了 O(1)，但牺牲了键的有序性（LRU 缓存通常不需要）。