内容简介:在撸代码时,利用局部性原理对数据做缓存是一种常用的性能优化手段。要做缓存,离不开的就是缓存组件。降低锁冲突的策略有
在撸代码时,利用局部性原理对数据做缓存是一种常用的性能优化手段。
要做缓存,离不开的就是缓存组件。 ccache 就是一个很优秀的lru缓存组件,其做了很多很巧妙的优化策略来降低锁冲突,实现高性能。
降低锁冲突的策略有
- 一个元素在累计被访问多次后才做提权(提权指将元素移动到lru链的头部)
- 将提权操作放到一个队列中,由一个单独的线程做处理
- 在同一个线程中做垃圾回收操作
下面看下具体是怎么实现的。
2. lru cache
在分析源代码前,先简单了解下lru cache是做什么的。
lru为least recently used的缩写,顾名思义,lru cache在缓存满后,再缓存新内容需先淘汰最久未访问的内容。
要实现lru策略,一般是用hashtable和list数据结构来实现,hashtable支持通过key快速检索到对应的value,list用来记录元素的访问时间序,支持淘汰最久未访问的内容。如下图
在hashtable中,key对应的内容包含两部分,第一部分为实际要存储的内容,这里定义为value,第二部分是一个指针,指向对应在list中的节点,将其定义为element。
在list中,每个节点也包含两个部分,第一个部分是一个指针,指向hashtable中对应的value,这里定义为node,第二部分是next指针,用来串起来整个链表。
若我们执行get(key2)操作,会先通过key2找到value2和element2,通过element2又能找到node2,然后将node2移动到list队首,所以执行完get(key2)后,上图会变为
这时假如又有一个set(key5, value5)操作,而我们的cache最多只能缓存4条数据,会怎么处理呢。首先会在hashtable中插入key5和value5,并且在list的队首插入node5,然后取出list队尾的元素,这里是node4,将其删除,同时删除node4对应的在hashtable中的数据。执行完上图会变成
通过上述流程,可以很好的实现lru策略。但是因hashtable和list这两种数据结构都不是线程安全的,若要在多线程环境下使用,无论set操作还是get操作都需要加锁,这样就会很影响性能,特别是现在的服务器cpu核心数量越来越多,加锁对性能的损耗是非常大的。
3. ccache优化策略
针对上面的问题,ccache采用了下面几种优化策略,都非常的巧妙。
3.1 对hashtable做分片
这是个很常见的策略。
将一个hashtable根据key拆分成多个hashtable,每个hashtable对应一个锁,锁粒度更细,冲突的概率也就更低了。
如图所示,一个hashtable根据key拆分成三个hashtable,锁也变成了三个。这样当并发访问hashtable1和hashtable2时,就不会冲突了。
3.2 累计访问多次才做提权
value中新增一个访问计数,每次get操作时,计数+1。当计数达到阈值时,才将其移动到list的队首,同时将计数重置为0。
如阈值是3,那么对list的写操作就会降低3倍,锁冲突的概率也会减少3倍。
这是一个有损的策略,会使list的顺序不完全等同于访问时间序。但考虑到lru cache的get操作频率很高,这种策略对命中率的损失应该是可以忽略的。
3.3 单开一个线程更新list
在get和set操作时,都需要更新记录访问时间序的list,但更新操作只需要在这个key的下次set操作前完成就可以,并不需要实时更新。基于这一点,可以单独开一个更新线程对list做更新。get和set时,提交更新任务到队列中,更新线程不停从队列中取任务做更新。
这样做有两个好处
- list不存在多线程访问,不需加锁
- 所有对list的操作都放在一个线程中,对cpu cache更友好
这样会带来一个问题,当cpu核心很多,get和set的qps很高时,这个更新线程可能成为瓶颈。不过考虑到list的操作是非常轻量的,再加上服务不可能全部资源都放到读写cache上,这点也是可以忽略的。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 理解高性能内存缓存对象缓存Memcached原理 (Memcached核心概念,部署)
- 高性能缓存服务器 nuster 1.7.9.9 添加缓存 stats 功能
- 设计实现高性能本地内存缓存
- Nuster:高性能缓存服务器
- 基于HAProxy的高性能HTTP缓存服务器和RESTful NoSQL缓存服务器
- 高性能编程:三级缓存(LLC)访问优化
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
嵌入式系统开发之道
2011-12 / 69.00元
《嵌入式系统开发之道:菜鸟成长日志与项目经理的私房菜》用平易朴实的语言,以一个完整的嵌入式系统的开发流程为架构,通过一位“菜鸟”工程师与项目经理的诙谐对话,故事性地带出嵌入式系统概念及开发要素,并点出要成为一名称职的嵌入式系统工程师,在实际工作中所必须具备的各项知识及技能。 《嵌入式系统开发之道:菜鸟成长日志与项目经理的私房菜》可以分为三大部分:第1、3、4、17、18、19章和附录D为嵌入......一起来看看 《嵌入式系统开发之道》 这本书的介绍吧!