关于「非平稳请求:流行度漂移、冻结名单与冷启动」,《缓存命中率与车氏近似》给出的定量结论是什么?
结论:第五章说明流行度漂移时稳态近似只会高估,快速换人可使命中率从 0.4483 跌到 0.3488,冻结名单迅速老化,清空后的回填按特征时间计时。
数据口径:本书用标准库程序推翻这条直觉:在齐普夫请求下,最近最少使用(LRU)缓存的命中率随容量增长得很慢,示意参数下容量放大一百二十八倍,命中率只放大 6.80 倍;而车氏近似只凭请求概率与容量,就能事先算出 LRU 命中率,与逐条模拟的最大差距为 0.0013。 书中参数为示意;全部计算由书中程序生成;本书给出只读的容量建议,不访问任何服务器、不写任何配置;「排盘」仅作一种计算结果的名称,不做任何命理推断;属于非个人化经营建议。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.3488, 0.4483
| LRU under turnover, C = 2000, stationary Che = 0.4483 | |||
| turnover f | E = 50000 | E = 10000 | E = 2000 |
| 0.0 | 0.4496 | 0.4496 | 0.4496 |
| 0.1 | 0.4487 | 0.4457 | 0.4312 |
| 0.3 | 0.4474 | 0.4383 | 0.3965 |
| 0.6 | 0.4454 | 0.4281 | 0.3488 |
查看完整验算程序
# Chapter 5. p51: when popularity drifts, the stationary Che value lies.
# Model: request ranks follow Zipf (a = 0.8, N = 20000), but the key
# behind each rank is not fixed: every E requests each rank, with
# probability f, is handed to a brand-new key (a chart nobody asked for
# before). LRU (C = 2000) is replayed on 300000 requests with 50000
# warm-up; the same rank sequence is reused for every (E, f) cell, and
# each cell's turnover draws come from its own seeded generator. E and
# f are illustrative, not measurements of any real service.
import math
import random
from collections import OrderedDict
N, A, L, WARM, C = 20000, 0.8, 300000, 50000, 2000
def zipf(n, a):
w = [1.0 / (i ** a) for i in range(1, n + 1)]
s = math.fsum(w)
return [x / s for x in w]
def occupancy(p, t):
return math.fsum(-math.expm1(-x * t) for x in p)
def che_t(p, c, tol=1e-9):
lo, hi = 0.0, 1.0
while occupancy(p, hi) < c:
hi = 2.0 * hi
while hi - lo > tol * hi:
mid = 0.5 * (lo + hi)
if occupancy(p, mid) < c:
lo = mid
else:
hi = mid
return 0.5 * (lo + hi)
def che_hit(p, t):
return math.fsum(x * -math.expm1(-x * t) for x in p)
def churn_lru(ranks, c, warm, e, f, seed):
r = random.Random(seed)
key = list(range(N))
fresh = N
cache = OrderedDict()
hits = 0
for t, k in enumerate(ranks):
if t and t % e == 0 and f > 0:
for i in range(N):
if r.random() < f:
key[i] = fresh
fresh += 1
x = key[k]
if x in cache:
cache.move_to_end(x)
if t >= warm:
hits += 1
else:
cache[x] = None
if len(cache) > c:
cache.popitem(last=False)
return hits / (len(ranks) - warm)
if __name__ == "__main__":
p = zipf(N, A)
rng = random.Random(20261113)
ranks = rng.choices(range(N), weights=p, k=L)
che = che_hit(p, che_t(p, C))
print("LRU under turnover, C = {}, stationary Che = {:.4f}"
.format(C, che))
print(" turnover f E = 50000 E = 10000 E = 2000")
seed = 20261200
for f in (0.0, 0.1, 0.3, 0.6):
row = []
for e in (50000, 10000, 2000):
seed += 1
row.append(churn_lru(ranks, C, WARM, e, f, seed))
print(" {:.1f} {:.4f} {:.4f} {:.4f}".format(
f, row[0], row[1], row[2]))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《缓存命中率与车氏近似、排盘结果缓存容量的最优边界母典》第 5 章「非平稳请求:流行度漂移、冻结名单与冷启动」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-327 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026327,
author = {Fan, Yafu},
title = {Cache Hit Ratios and the Che Approximation: Optimal Capacity for Caching Computed Charts},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}