这篇文章主要介绍高吞吐、线程安全之LRU缓存的示例分析，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
之前实现了一个LRU缓存用来为关键字来查找它的id。数据结构非常有意思，因为要求的吞吐很大足以消除大量使用locks和synchronized关键字带来的性能问题，应用是用java实现的。
我想到一连串的原子引用分配会在ConcurrentHashMap中保持LRU保持LRU顺序，开始的时候我把value包装到entry中去，entry在双链表的LRU链中有一个节点，链的尾部保持的是最近使用的entry，头节点中存放的是当缓存达到一定的大小的时候可能会清空的entry。每一个节点都指向用来查找的entry。
当你通过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 ,, have 我方表示歉意an entry e offer 才能;entry e try 才能purge some holes else load 才能value v for key k create 才能;entry e & lt;作用;(k、v), try 才能put entry e 最终获得; return value e。v
如果关键存在,我们在LRU链的尾部提供一个新的节点来表明,这是一个最近使用的值. get和提供的执行并不是原子操作(这里没有锁),所以我们不能说这个提供节点指向最近使用的实体,但是肯定是当我们并发执行时获得的最近使用的实体。我们没有强制获得和提供对在线程间执行的顺序,因为这可能会限制吞吐量。在提供一个节点之后,我们尝试着做一些清除和返回值的操作。下边我们详细看一下这提供和清洗操作。
如果缓存丢失发生了,我们将调用加载器为这个键加载值,创建一个新的实体并把它放入到地图中去,把操作如下:
正结束如你所见的一样,有两个或这两个以上的线程把一个实体放入地图的时候可能存在竞争,但是只允许一个成功并且会调用。在LRU链的尾部提供一个节点之后,我们需要检查是否缓存已经达到了它的阙值的大小,阙值是我们用来出发批量清空操作的标识。在这个特定的应用的场景下,阙值的设置要比容量的大小要小。清空操作小批量的发生而不是每一个实体加进来的时候都会发生,多线程或许会参与到清空操作中去,直到缓存的容量达到它的容量。上锁很容易但是线程却能是安全的。清空需要移除LRU链的头节点,这需要依赖细心的原子操作来避免在地图中多线程的移除操作。
