面试官问我Redis内存满了怎么办？我用Go手撸LRU和LFU算法给他看

面试官问我Redis内存满了怎么办我用Go手撸LRU和LFU算法给他看当Redis内存达到上限时缓存淘汰策略的选择直接影响系统性能。作为后端工程师理解LRU和LFU算法的实现原理远比记住概念更重要。本文将带你用Go语言从零实现这两种经典算法并探讨它们在真实场景中的应用差异。1. 缓存淘汰策略的核心逻辑内存是有限的但数据是无限的——这是每个后端工程师必须面对的永恒矛盾。当缓存空间不足时我们需要一套公平且高效的规则来决定哪些数据应该被保留哪些可以被牺牲。缓存淘汰算法的本质是预测未来基于历史访问模式判断哪些数据最有可能被再次使用。LRU和LFU分别从时间和频率两个维度建立了不同的预测模型LRU最近最少使用认为最近被访问过的数据未来更可能被访问LFU最不经常使用认为历史访问次数多的数据未来更可能被访问在Go中实现这两种算法时我们需要考虑几个关键点// 公共数据结构定义 type CacheItem struct { Key string Value interface{} Freq int // LFU专用 Access time.Time // LRU专用 }2. LRU算法的Go实现细节LRU算法可以看作是一个有时间记忆功能的队列。当访问某个键时它会被移动到队列前端当需要淘汰数据时从队列尾部移除。2.1 数据结构设计高效的LRU实现需要结合哈希表和双向链表type LRUCache struct { capacity int cache map[string]*list.Element list *list.List // 双向链表维护访问顺序 } type entry struct { key string value interface{} }2.2 关键操作实现Get操作需要处理并发安全和访问时间更新func (l *LRUCache) Get(key string) (interface{}, bool) { l.lock.Lock() defer l.lock.Unlock() if elem, ok : l.cache[key]; ok { l.list.MoveToFront(elem) return elem.Value.(*entry).value, true } return nil, false }Put操作需要考虑缓存淘汰的边界条件func (l *LRUCache) Put(key string, value interface{}) { l.lock.Lock() defer l.lock.Unlock() // 已存在则更新 if elem, ok : l.cache[key]; ok { l.list.MoveToFront(elem) elem.Value.(*entry).value value return } // 需要淘汰最久未使用的 if len(l.cache) l.capacity { oldest : l.list.Back() if oldest ! nil { delete(l.cache, oldest.Value.(*entry).key) l.list.Remove(oldest) } } // 添加新元素 elem : l.list.PushFront(entry{key, value}) l.cache[key] elem }2.3 性能优化技巧在实际工程中我们可以通过以下方式优化LRU实现批量操作合并短时间内多次更新预分配内存根据capacity预先分配足够空间惰性删除标记删除而非立即释放内存3. LFU算法的Go实现方案LFU算法需要统计每个键的访问频率这使得它的实现比LRU更复杂。我们需要维护频率到键的映射关系。3.1 分层数据结构设计type LFUCache struct { capacity int minFreq int items map[string]*list.Element // 存储所有键值对 freqLists map[int]*list.List // 频率到键列表的映射 counters map[string]int // 键到频率的映射 }3.2 频率更新策略当键被访问时需要将其移动到更高频率的列表中func (l *LFUCache) increment(elem *list.Element) { key : elem.Value.(*entry).key oldFreq : l.counters[key] // 从旧频率列表移除 l.freqLists[oldFreq].Remove(elem) // 更新最小频率 if oldFreq l.minFreq l.freqLists[oldFreq].Len() 0 { l.minFreq } // 添加到新频率列表 newFreq : oldFreq 1 if _, exists : l.freqLists[newFreq]; !exists { l.freqLists[newFreq] list.New() } newElem : l.freqLists[newFreq].PushFront(elem.Value) l.items[key] newElem l.counters[key] newFreq }3.3 淘汰机制实现当缓存满时淘汰最低频率中最久未使用的键func (l *LFUCache) evict() { if list : l.freqLists[l.minFreq]; list ! nil { if elem : list.Back(); elem ! nil { key : elem.Value.(*entry).key list.Remove(elem) delete(l.items, key) delete(l.counters, key) } } }4. 实战场景下的选择策略在真实项目中LRU和LFU各有适用场景特性LRULFU实现复杂度简单复杂内存开销较低较高适用场景热点数据集中访问模式稳定突发流量表现良好可能误淘汰冷启动问题存在较严重Redis的近似LRU实现由于精确LRU成本高Redis采用随机采样方式近似实现。可以通过maxmemory-policy配置volatile-lru从设置了过期时间的键中淘汰allkeys-lru从所有键中淘汰Go实现中的工程考量并发安全使用sync.RWMutex保护共享数据内存效率预分配足够容量避免频繁扩容监控指标记录命中率、淘汰次数等运行指标// 监控指标示例 type CacheMetrics struct { Hits int64 Misses int64 Evictions int64 AvgLatency time.Duration }在面试中展示这些实现细节能体现你对缓存系统的深刻理解。记住优秀的工程师不仅要会调用API更要理解底层机制。