高吞吐、线程安全的LRU缓存

淩亂°似流年 2022-08-19 11:22 18阅读 0赞

几年以前，我实现了一个LRU缓存用来为关键字来查找它的id。数据结构非常有意思，因为要求的吞吐很大足以消除大量使用locks和synchronized关键字带来的性能问题，应用是用java实现的。

我想到一连串的原子引用分配会在ConcurrentHashMap中保持LRU保持LRU顺序，开始的时候我把value包装到entry中去，entry在双链表的LRU链中有一个节点，链的尾部保持的是最近使用的entry，头节点中存放的是当缓存达到一定的大小的时候可能会清空的entry。每一个节点都指向用来查找的entry。

![Center][]

有三个实体和三个节点的LRU缓存

当你通过key查找值的时候，缓存首先要查找map看看是否有这个value存在，如果不存在的话，它将依赖于加载器将value从数据源中以read-through的方式读出来并且以“如果缺失则添加”的方式添加的map中去。确保高吞吐的挑战是有效的维护LRU链。这个并发的哈希map是分段的而且在线程的水平在一定水平（当你构建map的时候你可以指定并发的水平）情况下的时候不会经历太多的线程竞争。但是LRU链不能以同样的方式被划分吗，为了解决这个问题，我引入了辅助的队列用来清除操作。

在cache中有六个基本的方法。对于缓存命中，查找包含两个基本操作：get和offer，对于换粗丢失包含四个基本的方法get、load、put和offer。在put方法上，我们也许需要追踪清空操作，在缓存命中的情况下get，我们在LRU链上被动的做一些清空叫做净化操作。

get  : lookup entry in the map by key
    load : load value from a data source
    put  : create entry and map it to key
    offer: append a node at the tail of the LRU list that refers to a recently accessed entry
    evict: remove nodes at the head of the list and associated entries from the map (after the cache reaches a certain size)
    purge: delete unused nodes in the LRU list -- we refer to these nodes as holes, and the cleanup queue keeps track of these

清空操作和净化操作都是大批量的处理数据，我们来看一下每个操作的细节

get操作是按如下方式工作的：

get(K) -> V
    
    lookup entry by key k
    if cache hit, we have an entry e
        offer entry e
        try purge some holes
    else
        load value v for key k
        create entry e <- (k,v)
        try put entry e
    end
    return value e.v

如果key存在，我们在LRU链的尾部提供一个新的节点来表明，这是一个最近使用的值。get和offer的执行并不是原子操作（这里没有lock），所以我们不能说这个offered 节点指向最近使用的实体，但是肯定是当我们并发执行时获得的最近使用的实体。我们没有强制get和offer对在线程间执行的顺序，因为这可能会限制吞吐量。在offer一个节点之后，我们尝试着做一些清除和返回value的操作。下边我们详细看一下这offer和purge操作。

如果缓存丢失发生了，我们将调用加载器为这个key加载value，创建一个新的实体并把它放入到map中去，put操作如下：

put(E) -> E
    
    existing entry ex <- map.putIfAbsent(e.k, e)
    if absent
        offer entry e;
        if size reaches evict-threshold
            evict some entries
        end
        return entry e
    else, we have an existing entry ex
        return entry ex
    end

正如你所见的一样，有两个或这两个以上的线程把一个实体放入map的时候可能存在竞争，但是只允许一个成功并且会调用offer。在LRU链的尾部提供一个节点之后，我们需要检查是否缓存已经达到了它的阙值的大小，阙值是我们用来出发批量清空操作的标识。在这个特定的应用的场景下，阙值的设置要比容量的大小要小。清空操作小批量的发生而不是每一个实体加进来的时候都会发生，多线程或许会参与到清空操作中去，直到缓存的容量达到它的容量。上锁很容易但是线程却能是安全的。清空需要移除LRU链的头节点，这需要依赖细心的原子操作来避免在map中多线程的移除操作。

![Center 1][]

这个offer操作非常有意思，它总是尝试着创建一个节点但是并不试图在LRU中立即移除和删除那些不再使用的节点。

offer(E)
    
    if tail node doesn't refer to entry e
        assign current node c <- e.n
        create a new node n(e), new node refers to entry e
        if atomic compare-and-set node e.n, expect c, assign n
            add node n to tail of LRU list
            if node c not null
                set entry c.e to null, c now has a hole
                add node c to cleanup queue
            end
        end
    end

首先它会检查，链中尾部的节点没有指向已经访问的实体，这并没有什么不同除非所有的线程频繁的访问同样的键值对，它将会链部的尾的实体创建一个新的节点当这个实体不同的时候，在提供新的节点之前，它尝试为实体进一个比较和设置的操作，这将阻止多线程做同样的事情。

成功的分配节点的线程在LRU链的尾部提供了一个新的节点，这个操作和ConcurrentLinkedQueue中的find一样，依赖的算法在下边的文章中有描述 [Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms][Simple_ Fast_ and Practical Non-Blocking and Blocking Concurrent Queue Algorithms]。线程然后会检查实体之前是否和其他的节点有相关连，如果是这样的话，老的节点不会立即删除，但是会被标记为一个hole（它的实体的引用会被设置为空）

![Center 2][]

原文地址：http://www.ebaytechblog.com/2011/08/30/high-throughput-thread-safe-lru-caching/

**关注我，获取400个的赚钱金点子，轻松开启程序员的副业生涯**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb3llcWl1_size_16_color_FFFFFF_t_70][]

[Center]: /images/20220731/2aed42fd67304535be4149d56b69e141.png
[Center 1]: /images/20220731/f441d55198dc424db6382387c46336bf.png
[Simple_ Fast_ and Practical Non-Blocking and Blocking Concurrent Queue Algorithms]: http://www.cs.rochester.edu/u/michael/PODC96.html
[Center 2]: /images/20220731/10d696957c244794b2d1c36797d71fe4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb3llcWl1_size_16_color_FFFFFF_t_70]: /images/20220731/ec54be626c22444d8e72ebfc5773e314.png