个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
25
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章高吞吐、线程安全的LRU缓存详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
本文研究的主要是高吞吐、线程安全的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操作是按如下方式工作的:
|
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中多线程的移除操作.
这个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缓存详解的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！ 。
原文链接：http://blog.csdn.net/maoyeqiu/article/details/50502410 。
最后此篇关于高吞吐、线程安全的LRU缓存详解的文章就讲到这里了,如果你想了解更多关于高吞吐、线程安全的LRU缓存详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
25
4
0
题目地址：https://leetcode.com/problems/lru-cache/ 题目描述 Design and implement a data structure for Least
我使用 redis 作为数据存储而不是缓存，但是设置了 maxmemory 限制，据我了解，maxmemory 指定了 redis 可以使用的 RAM，如果达到内存限制，它不应该将数据交换回磁盘。 我
假设redis 实例中的所有键都设置了过期时间，volatile-lru 和allkeys-lru 是相似的。但是，当删除 key 时，两者之间是否存在显着的性能差异？ 奖励问题: 在配置了 allk
LRU-K 是一种缓存淘汰算法，旨在改进传统的LRU（Least Recently Used，最近最少使用）算法的性能。将其中高频的数据达到K次访问移入到另一个队列进行保护。 算法思想 LR
1.题目 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： ① LRUCache(int capacity) 以正整数作为容量 capacity
如果 memcached 中的某个项目设置为永不过期，它是否免于 LRU 驱逐？ 我见过的文档并没有清楚地描绘出哪个优先。在我看来，让 LRU 仅适用于过期 > 0 的项目是理想的(可能在内部非常复杂
当 memcache 中可用内存已满时，memcache 使用 LRU(最近使用的)算法来释放内存。 我的问题是 LRU 算法是否会删除在一段时间内(最近一次使用)未使用的条目而不是过期的条目？ 即将
我在java中使用LRU缓存并覆盖了removeEldest。 @Override protected boolean removeEldestEntry (Map.Entry eldest) {
我前段时间已经发帖询问LRU缓存的良好设计(C++)。您可以在此处找到问题、答案和一些代码: Better understanding the LRU algorithm 我现在尝试对这段代码进行多线
我正在尝试使用这个 youtube video 自学 LRU 算法.在下面的示例 ( taken from here ) 中，为什么 0 被 3 代替。不应该是 4 被 3 代替，因为 4 是最少使用
我正在尝试使用 Caffeine 作为 LRU 缓存，因此首先添加的条目将首先被逐出。运行这段代码: final Cache map = Caffeine.newBuilder()
我对算法LRU有一点疑问。如果您有一个包含四个 block 的缓存，您需要多少位来实现该算法？ 最佳答案 假设您指的是 4 路组相联缓存: “完美”的 LRU 本质上是按照使用顺序为每一行分配一个准确
我有两种类型的 Redis 键:post:{pid} 和 comment:{cid}。 我想存储最多 100 条记录的任一类型的缓存。 例如我有 100 条帖子记录和 50 条评论记录。当评论记录到来
我正在使用 Swift 构建一个应用程序，我想在我的应用程序中使用 LRU 缓存。我实现了一个简单的 LRUCache在 Swift 中，但后来我发现，由于它已经附带了 Dictionary 和 Ar
现在软件或者网页的并发量越来越大了，大量请求直接操作数据库会对数据库造成很大的压力，处理大量连接和请求就会需要很长时间，但是实际中百分之80的数据是很少更改的，这样就可以引入缓存来进行读取，减少数据
我有一些看起来像这样的代码: from functools import lru_cache @lru_cache() def get_cheese(type): print('{}? We\
我有一个规范，我试图定义一个 LRU 缓存系统，我遇到的一个问题是如何从结构键/值对(基本上是字典或哈希映射)中删除值其他语言)。 到目前为止，这是规范本身(不完整): EXTENDS Integer
如何使用 Erlang 实现 LRU 缓存？ LRU Cache Wiki 最受关注的 Github 项目是 fogfish/cache ，但分段表不太适合我的数据。 barrel-db/erlang
我正在制作一个 Android 应用程序，其中有带有缩略图的新闻文章。这些缩略图从网络加载并存储在 LruCache 中，其中 URL 作为键，位图作为值。 private LruCache tCac
这个问题已经有答案了: How would you implement an LRU cache in Java? (21 个回答) 已关闭 5 年前。 我想仅使用 Java 内置的数据结构在 Jav
我是一名优秀的程序员,十分优秀！