如何实现一个高性能LRU

请设置文章作者

发布于：Apr 25, 2023

次浏览

如何实现一个高性能LRU

本质是分桶降低map锁的影响范围，然后使用单独的一个worker线程逐一处理链表的更新操作。

一个基本的实现就是一个lru链表，然后元素访问的时候移动到链表头，超出容量就淘汰链尾元素。

然后再看看怎么从链表中找到目标元素，方便我们移动。一个办法就是使用map做索引。这样就实现了O(1)的整删改查。

1
2
3
4
5
6
7
8
9

---      Item1
           |
           V
         Item2
map ->     |
           V
         Item3
           |
---        v

整流程就是

• Get
  1. 查map
  2. 移动链表中的元素
• Put
  1. 查map
  2. 插入map和链表
  3. 必要时执行淘汰

高并发场景

然后考虑高并发的场景，我们首先能想到的想法就是直接加锁。然后发现增删改查都需要访问map，对整个map加锁性能感觉就很差。然后又是修改链表，乍一看链表操作涉及多个元素不加大锁又不行。

于是我们对LRU进行反思，缓存的本质是什么，缓存的本质就是一个map，而链表只是用来方便维护LRU关系的数据结构。对于单纯的map我们解决冲突的方法很多，其中一个就是分桶。简单的说就是先通过一个map找到缓存map的位置，即桶，然后只需要对桶内的访问进行加锁即可，而不用对整个缓存数据加锁。

1
2
3
4
5
6
7
8
9
10
11

---     ---
        map
        ---
        
bucket  ---
map     map
        ---
        
        ---
        map
---     ---

然后就遇到了一个新的问题，如果需要加入新的桶怎么办，只要有需要加新桶的需求那在通过bucket map获取桶时就又得持有锁来以防万一。一个办法就是设置固定数量的桶，这样永远不会出现扩容的问题，就不需要锁。另一个办法是加读写锁。

ok, 我们使用分桶加锁的方式优化了对map使用大锁的问题。那链表该怎么办，链表元素的移动涉及范围很广好像非加大锁不成。我们做缓存要用的只是map的数据，链表只是辅助lru的结构，我们之所以要更新它是为了下次用到时希望能有即使的情况反馈。但是对于缓存来说，我们在map中更新了就行了，多数情况下我们对缓存的删除和淘汰并不敏感。所以就可以为链表元素的移动专门开一个且仅一个线程来处理。map修改完后通过消息队列的方式，告诉链表怎么操作元素就可以返回了，而不需要等待链表操作的执行完成。而且通过单线程的方式处理就不会阻塞了。

1
2
3
4
5
6
7
8
9
10
11
12

                   single thread
---     ---           Item1
        map             |
        ---             V
                      Item2
bucket  ---  events     |
map     map   ===>      V
        ---           Item3
                        |
        ---             V
        map
---     ---