关于「分片与分层:同样的槽位,不同的摆法」,《缓存命中率与车氏近似》给出的定量结论是什么?
结论:再看车氏近似一栏。前一级的命中率 0.1931、0.2613、0.3450、0.4027,与单一缓存在同样容量下的值完全一致,这一级没有问题。问题出在后一级:两级合计的近似值是 0.4319、0.4190、0.4177 与 0.4309,比模拟值系统地偏高,对半分时偏高约六个百分点。原因在于,第一级的缺失流并不是独立引用:一个对象刚刚在第一级缺失,它就被放进了第一级,接下来一段时间里它的请求都会在第一级命中,不会再到达第二级;也就是说,到达第二级的请求在时间上是「打散」过的,同一对象的请求被拉开了间隔。车氏近似把它当作独立引用,就高估了第二级的命中机会。
数据口径:本书用标准库程序推翻这条直觉:在齐普夫请求下,最近最少使用(LRU)缓存的命中率随容量增长得很慢,示意参数下容量放大一百二十八倍,命中率只放大 6.80 倍;而车氏近似只凭请求概率与容量,就能事先算出 LRU 命中率,与逐条模拟的最大差距为 0.0013。 书中参数为示意;全部计算由书中程序生成;本书给出只读的容量建议,不访问任何服务器、不写任何配置;「排盘」仅作一种计算结果的名称,不做任何命理推断;属于非个人化经营建议。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.1931, 0.2613, 0.3450, 0.4027, 0.4177, 0.4190
| Two LRU levels with 2000 slots in all; one cache: 0.4483 | |||||
| C1 | C2 | Che L1 | Che L2 | Che all | sim all |
| 250 | 1750 | 0.1931 | 0.2388 | 0.4319 | 0.4277 |
| 500 | 1500 | 0.2613 | 0.1577 | 0.4190 | 0.3968 |
| 1000 | 1000 | 0.3450 | 0.0727 | 0.4177 | 0.3562 |
| 1500 | 500 | 0.4027 | 0.0281 | 0.4309 | 0.4048 |
查看完整验算程序
# Chapter 6. p62: two LRU levels in tandem, the setting of Che (2002).
# Model: level 1 has C1 slots and sees all requests; its misses go to
# level 2 with C2 slots. Following Che, Tung and Wang, the miss stream
# of level 1 is treated as independent references with rates
# q_i = p_i (1 - h1_i); level 2 is solved by the same Che equation on
# q normalised. Overall hit = H1 + sum q_i h2_i. A single LRU of
# C1 + C2 slots is the yardstick. Seeded trace of 250000 Zipf requests
# (a = 0.8, N = 20000, illustrative), 50000 warm-up.
import math
import random
from collections import OrderedDict
N, A, L, WARM, TOTAL = 20000, 0.8, 250000, 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_two(p, c1, c2):
t1 = che_t(p, c1)
h1 = [-math.expm1(-x * t1) for x in p]
q = [x * (1.0 - h) for x, h in zip(p, h1)]
m = math.fsum(q)
qn = [x / m for x in q]
t2 = che_t(qn, c2)
l1 = math.fsum(x * h for x, h in zip(p, h1))
l2 = math.fsum(x * -math.expm1(-y * t2) for x, y in zip(q, qn))
return l1, l2
def sim_two(trace, c1, c2):
a, b = OrderedDict(), OrderedDict()
h1 = h2 = 0
for t, x in enumerate(trace):
if x in a:
a.move_to_end(x)
if t >= WARM:
h1 += 1
continue
a[x] = None
if len(a) > c1:
a.popitem(last=False)
if x in b:
b.move_to_end(x)
if t >= WARM:
h2 += 1
else:
b[x] = None
if len(b) > c2:
b.popitem(last=False)
n = len(trace) - WARM
return h1 / n, h2 / n
if __name__ == "__main__":
p = zipf(N, A)
rng = random.Random(20261113)
trace = rng.choices(range(N), weights=p, k=L)
t0 = che_t(p, TOTAL)
single = math.fsum(x * -math.expm1(-x * t0) for x in p)
print("Two LRU levels with {} slots in all; one cache: {:.4f}"
.format(TOTAL, single))
print(" C1 C2 Che L1 Che L2 Che all sim all")
for c1 in (250, 500, 1000, 1500):
c2 = TOTAL - c1
l1, l2 = che_two(p, c1, c2)
s1, s2 = sim_two(trace, c1, c2)
print(" {:4d} {:4d} {:.4f} {:.4f} {:.4f} {:.4f}".format(
c1, c2, l1, l2, l1 + l2, s1 + s2))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《缓存命中率与车氏近似、排盘结果缓存容量的最优边界母典》第 6 章「分片与分层:同样的槽位,不同的摆法」(版本 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}
}