41.5 淘汰策略与 TTL

一句话

淘汰策略回答“内存满了先扔谁”，TTL 回答“谁到点必须走”——两者是两个维度，必须一起配：只靠淘汰会留下“再也没人访问但一直占内存”的 key，只靠 TTL 会在过期瞬间把压力全打回数据库。

六种淘汰策略

策略	留下谁	实现成本	适合的访问分布	主要缺点
LRU（最近最少使用）	最近被访问过的	中（哈希 + 双向链表）	有局部性、访问模式会变	一次全表扫描会把热数据冲掉
LFU（最不经常使用）	历史访问次数最多的	中高（计数 + 频次桶）	稳定的热点（Zipf）	新 key 冷启动难（需要“新key加分”机制）
CLOCK（时钟）	LRU 的近似	低（引用位 + 环形扫描）	同 LRU，内存受限时	精度略差
FIFO	最早进来的	最低	几乎不适合缓存	会把还在热的 key 按进入顺序扔掉
随机	随机	最低	无明显分布	命中率明显低于 LRU/LFU
TTL-only（不淘汰，靠过期）	谁到点谁走	低	数据有明确生命周期	未过期就会把内存撑爆

🔑 淘汰策略的效果完全取决于访问分布。在均匀分布下，所有策略命中率都接近 容量/总数；在 Zipf 分布下，LFU 跑到 72.8%、LRU 67.3%，而 FIFO 与随机只有 62.8% / 63.0%——下面实测。

代码：Zipf 请求流下的四种策略

package main

import (
	"container/list"
	"fmt"
	"math"
	"math/rand"
	"sort"
)

const (
	nKeys    = 10000
	nReqs    = 200000
	capacity = 1000
	alpha    = 1.0 // Zipf 指数
)

// zipf 请求流：key 0 最热，概率 ∝ 1/(k+1)^alpha
func makeRequests() []int {
	cum := make([]float64, nKeys)
	sum := 0.0
	for k := 0; k < nKeys; k++ {
		sum += 1 / math.Pow(float64(k+1), alpha)
		cum[k] = sum
	}
	r := rand.New(rand.NewSource(42))
	out := make([]int, nReqs)
	for i := range out {
		u := r.Float64() * sum
		idx := sort.SearchFloat64s(cum, u)
		if idx >= nKeys {
			idx = nKeys - 1
		}
		out[i] = idx
	}
	return out
}

type cache interface {
	get(k int) bool
	put(k int)
	evictions() int
}

// ---------- LRU ----------
type lru struct {
	cap  int
	ll   *list.List
	m    map[int]*list.Element
	evic int
}

func newLRU(c int) *lru { return &lru{cap: c, ll: list.New(), m: map[int]*list.Element{}} }

func (c *lru) get(k int) bool {
	if e, ok := c.m[k]; ok {
		c.ll.MoveToFront(e)
		return true
	}
	return false
}

func (c *lru) put(k int) {
	if e, ok := c.m[k]; ok {
		c.ll.MoveToFront(e)
		return
	}
	if c.ll.Len() >= c.cap {
		back := c.ll.Back()
		c.ll.Remove(back)
		delete(c.m, back.Value.(int))
		c.evic++
	}
	c.m[k] = c.ll.PushFront(k)
}

func (c *lru) evictions() int { return c.evic }

// ---------- FIFO ----------
type fifo struct {
	cap  int
	q    []int
	m    map[int]bool
	evic int
}

func newFIFO(c int) *fifo { return &fifo{cap: c, m: map[int]bool{}} }
func (c *fifo) get(k int) bool { return c.m[k] }
func (c *fifo) put(k int) {
	if c.m[k] {
		return
	}
	if len(c.q) >= c.cap {
		old := c.q[0]
		c.q = c.q[1:]
		delete(c.m, old)
		c.evic++
	}
	c.q = append(c.q, k)
	c.m[k] = true
}
func (c *fifo) evictions() int { return c.evic }

// ---------- 随机 ----------
type rnd struct {
	cap  int
	keys []int
	m    map[int]bool
	r    *rand.Rand
	evic int
}

func newRand(c int) *rnd {
	return &rnd{cap: c, m: map[int]bool{}, r: rand.New(rand.NewSource(7))}
}
func (c *rnd) get(k int) bool { return c.m[k] }
func (c *rnd) put(k int) {
	if c.m[k] {
		return
	}
	if len(c.keys) >= c.cap {
		i := c.r.Intn(len(c.keys))
		delete(c.m, c.keys[i])
		c.keys[i] = c.keys[len(c.keys)-1]
		c.keys = c.keys[:len(c.keys)-1]
		c.evic++
	}
	c.keys = append(c.keys, k)
	c.m[k] = true
}
func (c *rnd) evictions() int { return c.evic }

// ---------- LFU（每次淘汰扫描计数最小的，容量小时可接受） ----------
type lfu struct {
	cap  int
	cnt  map[int]int
	evic int
}

func newLFU(c int) *lfu { return &lfu{cap: c, cnt: map[int]int{}} }
func (c *lfu) get(k int) bool {
	if _, ok := c.cnt[k]; ok {
		c.cnt[k]++
		return true
	}
	return false
}
func (c *lfu) put(k int) {
	if _, ok := c.cnt[k]; ok {
		c.cnt[k]++
		return
	}
	if len(c.cnt) >= c.cap {
		minK, minV := -1, math.MaxInt
		for kk, vv := range c.cnt {
			if vv < minV {
				minK, minV = kk, vv
			}
		}
		delete(c.cnt, minK)
		c.evic++
	}
	c.cnt[k] = 1
}
func (c *lfu) evictions() int { return c.evic }

func main() {
	reqs := makeRequests()
	fmt.Printf("=== Zipf(α=%.1f)：%d 个 key，%d 次请求，容量 %d ===\n\n", alpha, nKeys, nReqs, capacity)
	fmt.Printf("%-8s %-10s %-10s\n", "策略", "命中率", "淘汰次数")

	for _, tc := range []struct {
		name string
		mk   func() cache
	}{
		{"LRU", func() cache { return newLRU(capacity) }},
		{"LFU", func() cache { return newLFU(capacity) }},
		{"FIFO", func() cache { return newFIFO(capacity) }},
		{"随机", func() cache { return newRand(capacity) }},
	} {
		c := tc.mk()
		hits := 0
		for _, k := range reqs {
			if c.get(k) {
				hits++
			} else {
				c.put(k)
			}
		}
		fmt.Printf("%-8s %-10s %-10d\n", tc.name,
			fmt.Sprintf("%.1f%%", float64(hits)*100/nReqs), c.evictions())
	}

	// 容量翻倍后的收益（判断“加内存”值不值）
	for _, cap2 := range []int{2000, 4000} {
		c := newLRU(cap2)
		hits := 0
		for _, k := range reqs {
			if c.get(k) {
				hits++
			} else {
				c.put(k)
			}
		}
		fmt.Printf("容量 %-6d 时 LRU 命中率 %.1f%%\n", cap2, float64(hits)*100/nReqs)
	}
}

本机实测（macOS，Apple M1，Go 1.27）：

=== Zipf(α=1.0)：10000 个 key，200000 次请求，容量 1000 ===

策略       命中率        淘汰次数      
LRU      67.3%      64450     
LFU      72.8%      53459     
FIFO     62.8%      73304     
随机       63.0%      73066     
容量 2000   时 LRU 命中率 76.4%
容量 4000   时 LRU 命中率 85.7%

读数：

策略	结论
LFU vs LRU	72.8% vs 67.3%，差 5.5 个百分点；差值来自“历史频次”对稳定热点的预测能力
FIFO / 随机	62.8% / 63.0%，比 LFU 低约 10 个百分点——换策略是零成本的收益
容量 1000 → 4000	命中率 67.3% → 85.7%，回源比例 32.7% → 14.3%；4 倍内存换回源减半，值不值看数据库压力

🔑 选型顺序：先用 LFU（或 LRU + 频次保护）吃 Zipf 红利，再用 TTL 控制陈旧，最后才考虑加内存。换策略是改一行配置，加内存是 4 倍账单——顺序别反。

TTL 的四个数

参数	定得太小	定得太大
TTL	回源放大、命中率下降、库压力上升（41.3）	数据陈旧，用户看到过期信息
TTL 抖动（jitter）	不加抖动 → 同批 key 同时过期 → 雪崩	抖动过大 → 过期时间不可预测，难排查
过期字典开销	—	每条 TTL 约 36 字节（本机 Redis 实测，见 41.9），1 亿 key 就是 3.6 GB
最大内存	太小 → 频繁淘汰，热数据被误杀	太大 → OOM 时连日志都写不进去

TTL 建议值：按“业务能容忍多旧”定，再按“回源能否承受”校验；两者冲突时，优先保证回源能承受（缓存首先是保护数据库的）。

maxmemory-policy 怎么选

策略	行为	适用
noeviction	内存满时写操作报错	不希望丢任何数据（此时缓存不该这么用）
allkeys-lru	所有 key 里按 LRU 淘汰	通用缓存默认值
allkeys-lfu	所有 key 里按频次淘汰	热点稳定的业务（商品详情、配置）
volatile-lru	只淘汰设了 TTL 的 key	缓存与“不能丢的数据”混布同一实例
volatile-ttl	优先淘汰即将过期的	临时数据为主

⚠️ volatile-* 的风险：如果所有 key 都没设 TTL，内存满时行为退化成 noeviction（写失败）。混布“缓存 + 队列/会话”的实例要特别小心这一点。

反模式

反模式	后果
不设 maxmemory，靠机器内存兜	OOM 时 Redis 被内核杀掉，缓存整层消失（41.3）
用 FIFO 当缓存策略	命中率低十几个百分点，等于白买内存
全量 key 同一时刻过期	雪崩，回源打穿数据库
TTL 只有 1–2 秒的“防脏”用法	命中率极低，缓存退化成限流器
缓存与不可丢数据混布，用 allkeys-*	淘汰把队列/会话数据删掉，业务异常
只看命中率，不看回源 QPS	命中率 95% 但基数大时，回源仍可能打穿库

自检

Q1 为什么在 Zipf 分布下，LFU 通常略优于 LRU，但在“突发新热点”时反而更差？

▸ 答案：Zipf 是稳定的长尾分布，历史频次能预测未来，LFU 因此占优。但 LFU 的计数是历史累积的：一个新的热点（如突发新闻、秒杀商品）刚出现时计数为 1，会被已经积累了几万次的老 key 挤掉，导致新热点频繁被淘汰（cache pollution）。工程上的解法是“新 key 加权/定期衰减/窗口计数”（如 TinyLFU 的准入机制），而不是纯 LFU。

Q2 TTL 与淘汰策略解决的是同一个问题吗？

▸ 答案：不是。TTL 解决正确性（数据不能无限陈旧），淘汰解决容量（内存有限时留谁）。只配 TTL 不配淘汰：容量满且没有 key 过期时写入失败或 OOM；只配淘汰不配 TTL：已经没人访问但“看起来还热”（历史计数高）的 key 会长期占内存，且数据可能无限陈旧。两者必须一起配，且 TTL 要加抖动避免雪崩。

Q3 缓存命中率从 90% 提到 95%，回源压力降了多少？为什么这个数字比“命中率”本身更重要？

▸ 答案：回源比例从 10% 降到 5%，回源 QPS 降一半（不是降 5 个百分点）。命中率是“比例”，回源压力是“绝对值”，后者才决定数据库会不会被打穿。同样，命中率从 99% 降到 98% 看起来只差 1 个点，但回源压力翻倍——所以监控要看“回源 QPS 与 P99”，而不是只看命中率。

Q4 一个实例同时存缓存与延迟队列（不可丢），该选哪个 maxmemory-policy？

▸ 答案：volatile-lru（或 volatile-lfu）——只淘汰设了 TTL 的 key（缓存），没设 TTL 的队列数据不会被淘汰；同时要保证所有缓存 key 都设 TTL，否则内存满时退化成 noeviction，写缓存开始报错。更稳的做法是物理隔离：缓存与队列用不同实例/不同集群，从根上避免“淘汰策略要同时满足两种语义”。

关联

• 前置：41.1 缓存模式 (旁路 / 读穿 / 写穿 / 写回)、41.2 本地缓存与分布式缓存
• 并列：41.3 缓存穿透 / 击穿 / 雪崩、41.6 热点 key 与分片
• 下游：41.9 产品 (Redis / Memcached) 与内部结构、41.7 多级缓存
• 待补：39.2 容量规划（未写，无链接）