太原网站建设费用,抚顺市+网站建设,wordpress删除文章div,开网页死机文章目录 本地缓存概览golang-lru标准lrulru的操作PutGet 2q#xff1a;冷热分离lruPutGet expirable_lru#xff1a;支持过期时间的lruPutGet过期 总结 本地缓存概览
在业务中#xff0c;一般会将极高频访问的数据缓存到本地。以减少网络IO的开销#xff0c;下游服务的压… 文章目录 本地缓存概览golang-lru标准lrulru的操作PutGet 2q冷热分离lruPutGet expirable_lru支持过期时间的lruPutGet过期 总结 本地缓存概览
在业务中一般会将极高频访问的数据缓存到本地。以减少网络IO的开销下游服务的压力提高性能
一般来说能放到本地的数据需要满足下面两个限制
数据量不是非常大数据量大了本地内存撑不住一致性时效性要求不是非常高毕竟多个服务的本地缓存很难做到同步更新及时更新 如果用go自带的map实现本地缓存大概有两种实现方式
sync.Mapmap mutex.RWLock
但有以下缺点
锁竞争严重大量缓存写入导致gc标记阶段占用cpu多内存占用不可控不支持缓存按时效性淘汰不支持缓存过期缓存数据可以被污染如果缓存的V是指针那么业务修改了V的某个值为当前请求用户自己的值在缓存中的V就被污染了 本系列要介绍的开源缓存库如何解决上述问题 将大map拆分成多个小map每个小map使用各自的锁 零GC 使用堆外内存不把对象放到堆上自然不会被gc扫描。但要注意手动管理需要及时释放内存 map的非指针优化 如果kv都没有指针不会扫描map。注意常用作key的string类型含有指针会被gc扫描将hash值作为keyvalue在底层数组中的offset作为value这样KV都是int就不会被GC扫描了 内存占用可控 初始化时制定好底层数组的容量数据写满时会覆写这样永远不会超过容量或者指定好最多能放多少KV对但如果V大小不一极端情况下内存占用会很大 支持缓存按时效性淘汰例如使用LRU算法 支持数据过期 某些库在后台启定时任务定时清理过期的KV某些库会在Get时惰性检查KV是否过期 避免缓存污染存储Value序列化后的字节数组而不是指针 但cpu开销会增大每次写入缓存都要经过序列化每次从缓存读都要经过反序列化。内存开销也变大每次读都相当于拷贝一份出来也就是用性能换取安全性
golang-lru 本文阅读源码https://github.com/hashicorp/golang-lru版本v2.0.7 该库提供了3种LRU的实现 lru标准lru 2q类似mysql的buffer pool分为冷数据和热数据两部分。如果某对KV只被添加到缓存中而没有被查询那么只会待在冷数据区域直到被淘汰而不会占用热数据的空间 为啥要冷热分离考虑这样一种场景假设缓存中有10条热点数据突然有用户往缓存中写10条冷数据因为容量不够要淘汰掉所有的热数据。如果之后也不查这些冷数据而是继续查之前的热数据。产生的后果是所有热数据都会cacheMiss如果应用了冷热分离机制这些冷数据只会写到冷数据区然后在冷数据区被淘汰而不会占用热数据的空间避免了大量热数据的cacheMiss expirable_lru支持过期时间的lru 标准lru
数据结构包含一个双向链表和hash表
type LRU[K comparable, V any] struct {// 容量size int// entry越靠近头部越新evictList *internal.LruList[K, V]// hash表items map[K]*internal.Entry[K, V]onEvict EvictCallback[K, V]
}LruList就是个带哨兵头节点root的双向链表每个节点是Entry结构。哈希表items的value也是Entry机构
那么真正的头节点是root.Next
尾节点是root.Prev
type LruList[K comparable, V any] struct {// 哨兵entryroot Entry[K, V]// 已经放了多少entrylen int
}entry结构如下
type Entry[K comparable, V any] struct {// 前后指针next, prev *Entry[K, V]// 属于哪个list主要用于遍历链表时在lru算法中没啥用list *LruList[K, V]Key KValue V
}初始化时root自己先形成一个环
func (l *LruList[K, V]) Init() *LruList[K, V] {l.root.next l.rootl.root.prev l.rootl.len 0return l
}下面介绍一些在LRU算法中会用到的小方法
获取最后一个节点
func (l *LruList[K, V]) Back() *Entry[K, V] {if l.len 0 {return nil}return l.root.prev
}将entry添加到头部
func (l *LruList[K, V]) PushFront(k K, v V) *Entry[K, V] {l.lazyInit()return l.insertValue(k, v, time.Time{}, l.root)
}func (l *LruList[K, V]) insertValue(k K, v V, expiresAt time.Time, at *Entry[K, V]) *Entry[K, V] {return l.insert(Entry[K, V]{Value: v, Key: k, ExpiresAt: expiresAt}, at)
}就是普通的双链表操作将e插到at的后面
func (l *LruList[K, V]) insert(e, at *Entry[K, V]) *Entry[K, V] {e.prev ate.next at.nexte.prev.next ee.next.prev ee.list ll.lenreturn e
}将entry移动到头部
func (l *LruList[K, V]) MoveToFront(e *Entry[K, V]) {if e.list ! l || l.root.next e {return}l.move(e, l.root)
}move方法
func (l *LruList[K, V]) move(e, at *Entry[K, V]) {if e at {return}// 先将e从list删除e.prev.next e.nexte.next.prev e.prev// 再将e插到at后面e.prev ate.next at.nexte.prev.next ee.next.prev e
}lru的操作
主要看看Get和Put这两大流程
原则每次操作完都要将KV所在的entry移动到list头部表示该entry实效性最好最不应该过期 Put
func (c *LRU[K, V]) Add(key K, value V) (evicted bool) {// 如果已存在将entry移到链表头部更新valueif ent, ok : c.items[key]; ok {c.evictList.MoveToFront(ent)ent.Value valuereturn false}// 新元素加入头部ent : c.evictList.PushFront(key, value)c.items[key] entevict : c.evictList.Length() c.size// 如果容量超了需要移除最老的if evict {c.removeOldest()}return evict
}removeOldest删除最老的entry
func (c *LRU[K, V]) removeOldest() {// 找到列表末尾的entryif ent : c.evictList.Back(); ent ! nil {c.removeElement(ent)}
}// 把entry从链表和map中删除
func (c *LRU[K, V]) removeElement(e *internal.Entry[K, V]) {c.evictList.Remove(e)delete(c.items, e.Key)if c.onEvict ! nil {c.onEvict(e.Key, e.Value)}
}Get
如果key存在将key所在的entry移动到list头部
func (c *LRU[K, V]) Get(key K) (value V, ok bool) {if ent, ok : c.items[key]; ok {c.evictList.MoveToFront(ent)return ent.Value, true}return
}2q冷热分离lru
2q在用了3个lru
recent保存冷数据默认容量为size的1/4frequent保存热数据默认容量为size的3/4recentEvict保存最近从冷数据中被删除的key默认容量为size的1/2
数据加到缓存时首先被添加到冷数据区如果后续没有操作就会在冷数据区被淘汰。如果在还没被淘汰时执行了Put或Get就会提升到热数据区
在Put时如果某个key在冷热数据都没有但在recentEvict中有说明是最近被删除的也当做热数据处理加到冷数据区 type TwoQueueCache[K comparable, V any] struct {size int// size * 0.25recentSize int// 0.25recentRatio float64// 0.5ghostRatio float64// 保存冷数据recent simplelru.LRUCache[K, V]// 正常热数据frequent simplelru.LRUCache[K, V]// 最近从冷数据删除的keyrecentEvict simplelru.LRUCache[K, struct{}]lock sync.RWMutex
}构造方法就是初始化3个lru以及每个lru的容量 const (// 默认冷数据的容量 size * 0.25Default2QRecentRatio 0.25// 默认被删除数据的容量 size * 0.5Default2QGhostEntries 0.50
)func New2Q[K comparable, V any](size int) (*TwoQueueCache[K, V], error) {return New2QParams[K, V](size, Default2QRecentRatio, Default2QGhostEntries)
}func New2QParams[K comparable, V any](size int, recentRatio, ghostRatio float64) (*TwoQueueCache[K, V], error) {recentSize : int(float64(size) * recentRatio)evictSize : int(float64(size) * ghostRatio)// 初始化3个lrurecent, err : simplelru.NewLRU[K, V](size, nil)if err ! nil {return nil, err}frequent, err : simplelru.NewLRU[K, V](size, nil)if err ! nil {return nil, err}recentEvict, err : simplelru.NewLRU[K, struct{}](evictSize, nil)if err ! nil {return nil, err}c : TwoQueueCache[K, V]{size: size,recentSize: recentSize,recentRatio: recentRatio,ghostRatio: ghostRatio,recent: recent,frequent: frequent,recentEvict: recentEvict,}return c, nil
}重点还是看Put和Get Put
流程为
如果key在热数据中有那就在热数据的lru中执行Put更新其value返回如果在冷数据中有那么本次不是第一次操作说明该key不再是冷数据了将其移动到热数据的lru中返回到这一步说明在冷热两个lru中都没有再看看recentEvict中有没有如果有说明是最近才从冷数据被删除的那么也算作是热数据在热数据lru中新增否则就在冷数据lru中新增
func (c *TwoQueueCache[K, V]) Add(key K, value V) {c.lock.Lock()defer c.lock.Unlock()// 如果在热数据中有在热数据的lru中执行Putif c.frequent.Contains(key) {c.frequent.Add(key, value)return}// 如果在冷数据中有移动到frequent中if c.recent.Contains(key) {c.recent.Remove(key)c.frequent.Add(key, value)return}// 在两个lru中都没有但最近移除过这个key加到frequent中if c.recentEvict.Contains(key) {c.ensureSpace(true)c.recentEvict.Remove(key)c.frequent.Add(key, value)return}// 否则加到recent中c.ensureSpace(false)c.recent.Add(key, value)
}当需要新增时需要确保容量足够如果容量超了需要淘汰老数据给新数据腾位置
ensureSpace方法干这个活淘汰规则为 如果recent和frequent的len加起来不够size判定为还有容量不淘汰 也就是说在容量没满时冷热数据区分别都可以用到size个空间有很大的灵活性 否则看冷数据区frequent有没有超过容量限制超过了就从frequent中淘汰一个 否则从热数据区中淘汰一个
func (c *TwoQueueCache[K, V]) ensureSpace(recentEvict bool) {// 如果还有空间返回recentLen : c.recent.Len()freqLen : c.frequent.Len()if recentLenfreqLen c.size {return}/**recent超过了限制, 从recent移除最老的entry将key加到recentEvict中*/if recentLen 0 (recentLen c.recentSize || (recentLen c.recentSize !recentEvict)) {k, _, _ : c.recent.RemoveOldest()c.recentEvict.Add(k, struct{}{})return}// 否则就是frequent超过限制了从frequent中移除最老的entryc.frequent.RemoveOldest()
}Get
先看热数据有没有该key如果有返回对应的value再看冷数据有没有如果有说明本次不是第一次操作该key将其提升到热数据中否则在冷热数据中都没有返回空
func (c *TwoQueueCache[K, V]) Get(key K) (value V, ok bool) {c.lock.Lock()defer c.lock.Unlock()// 先看热数据有没有if val, ok : c.frequent.Get(key); ok {return val, ok}// 在看冷数据有没有if val, ok : c.recent.Peek(key); ok {c.recent.Remove(key)c.frequent.Add(key, val)return val, ok}// No hitreturn
}expirable_lru支持过期时间的lru
其结构就是在标准LRU的基础上增加过期时间ttl和过期桶固定为100个 所有KV都应用相同的过期时间ttl
每次Put后会把key加到最新的过期桶中 后台有定时任务每ttl/100时间执行一次把即将过期的桶nextCleanupBucket 中的数据清空 type LRU[K comparable, V any] struct {// 标准LRU结构size intevictList *internal.LruList[K, V]items map[K]*internal.Entry[K, V]onEvict EvictCallback[K, V]mu sync.Mutex// LRU中的所有kv都用这个过期时间ttl time.Durationdone chan struct{}// 存储所有过期的keybuckets []bucket[K, V]// 下次要清除的bucket索引nextCleanupBucket uint8
}bucket定义如下
type bucket[K comparable, V any] struct {// 所有过期的keyentries map[K]*internal.Entry[K, V]// enteied中的所有key最晚在啥时候过期newestEntry time.Time
}Put
在标准LRU的基础上新增了对过期桶的操作
func (c *LRU[K, V]) Add(key K, value V) (evicted bool) {c.mu.Lock()defer c.mu.Unlock()now : time.Now()// key存在if ent, ok : c.items[key]; ok {c.evictList.MoveToFront(ent)// 将entry从过期桶移除c.removeFromBucket(ent)ent.Value valueent.ExpiresAt now.Add(c.ttl)// 加入最新的过期桶c.addToBucket(ent)return false}// key不存在ent : c.evictList.PushFrontExpirable(key, value, now.Add(c.ttl))c.items[key] entc.addToBucket(ent)// 容量超了移除最老的元素evict : c.size 0 c.evictList.Length() c.sizeif evict {c.removeOldest()}return evict
}看看怎么将entry加入过期桶
func (c *LRU[K, V]) addToBucket(e *internal.Entry[K, V]) {// 加到nextCleanupBucket-1对应的bucket里也就是最新的bucketbucketID : (numBuckets c.nextCleanupBucket - 1) % numBucketse.ExpireBucket bucketIDc.buckets[bucketID].entries[e.Key] e// 更新桶中最新的entry过期时间if c.buckets[bucketID].newestEntry.Before(e.ExpiresAt) {c.buckets[bucketID].newestEntry e.ExpiresAt}
}解释下为啥加到下标为nextCleanupBucket-1的桶里nextCleanupBucket为即将失效的桶那么nextCleanupBucket-1就是在当前时刻来说最晚失效的桶 Get
在标准LRU的Get流程上多了一步校验key是否过期
func (c *LRU[K, V]) Get(key K) (value V, ok bool) {c.mu.Lock()defer c.mu.Unlock()var ent *internal.Entry[K, V]if ent, ok c.items[key]; ok {// 校验是否过期if time.Now().After(ent.ExpiresAt) {return value, false}c.evictList.MoveToFront(ent)return ent.Value, true}return
}过期
缓存数据怎么实现过期呢在初始化LRU时起了后台任务
go func(done -chan struct{}) {ticker : time.NewTicker(res.ttl / numBuckets)defer ticker.Stop()for {select {case -done:returncase -ticker.C:res.deleteExpired()}}
}(res.done)每隔一段时间执行deleteExpired方法
准备将下标为nextCleanupBucket的中的所有KV过期sleep直到时间到newestEntry因为桶中最晚过期的key在这个时候不能提前过期将该桶中所有KV删除推进nextCleanupBucket让nextCleanupBucket
func (c *LRU[K, V]) deleteExpired() {c.mu.Lock()// bucketIdx : c.nextCleanupBuckettimeToExpire : time.Until(c.buckets[bucketIdx].newestEntry)// sleep直到newestEntry到来if timeToExpire 0 {c.mu.Unlock()time.Sleep(timeToExpire)c.mu.Lock()}// 将里面所有kv删除for _, ent : range c.buckets[bucketIdx].entries {c.removeElement(ent)}// 推进nextCleanupBucketc.nextCleanupBucket (c.nextCleanupBucket 1) % numBucketsc.mu.Unlock()
}总结
最后看看golang-lru解决了哪些原生缓存的问题
问题解决锁竞争严重没有解决只有一把大锁锁竞争依然严重大量缓存写入导致gc标记阶段占用cpu多没有解决内存占用不可控有改善在KV个数的层面可用在总内存占用量的层面依然不可用不支持缓存按时效性淘汰解决了支持按LRU算法淘汰不支持缓存过期解决了expirable_lru支持缓存数据可以被污染没有解决还是存指针
