服务器之家

服务器之家 > 正文

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

时间:2021-03-30 14:40     来源/作者:txxs

本文研究的主要是高吞吐线程安全的lru缓存的相关内容,具体介绍如下。

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

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

高吞吐、线程安全的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操作是按如下方式工作的:

?
1
2
3
4
5
6
7
8
9
10
11
12
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操作如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
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中多线程的移除操作。

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
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。线程然后会检查实体之前是否和其他的节点有相关连,如果是这样的话,老的节点不会立即删除,但是会被标记为一个hole(它的实体的引用会被设置为空)

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

总结

以上就是本文关于高吞吐、线程安全的lru缓存详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://blog.csdn.net/maoyeqiu/article/details/50502410

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部