关于「边际收益:容量与命中率曲线的斜率和成本最优边界」,《缓存命中率与车氏近似》给出的定量结论是什么?

结论:第四章由斜率与成本求出最优容量,示意参数下为 4187 个槽位、占目录 0.2094,且最优点附近成本平坦。

数据口径:本书用标准库程序推翻这条直觉:在齐普夫请求下,最近最少使用(LRU)缓存的命中率随容量增长得很慢,示意参数下容量放大一百二十八倍,命中率只放大 6.80 倍;而车氏近似只凭请求概率与容量,就能事先算出 LRU 命中率,与逐条模拟的最大差距为 0.0013。 书中参数为示意;全部计算由书中程序生成;本书给出只读的容量建议,不访问任何服务器、不写任何配置;「排盘」仅作一种计算结果的名称,不做任何命理推断;属于非个人化经营建议。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.2094, 4187

Daily cost, R = 3000, m = 1.0, k = 0.15 (illustrative units)
CLRU hitrecomputestoragetotal
00.00003000.00.03000.0
10460.35111946.8156.92103.7
20930.45591632.3313.91946.3
41870.58621241.5628.01869.6
83740.7485754.61256.12010.7
167480.9469159.22512.22671.4
optimum C* = 4187 slots, 0.2094 of the catalogue
slot cost k = 0.075: C* = 11385
slot cost k = 0.3: C* =1521
查看完整验算程序
# Chapter 4. p42: where the next slot stops paying for itself.
# Model: daily cost = R m (1 - H(C)) + k C, with R requests per day,
# m the cost of recomputing one chart on a miss and k the cost of
# keeping one cached result for one day, all in the same illustrative
# cost unit. The optimum satisfies R m dH/dC = k; since dH/dC falls as
# T grows, the root in T is found by bisection and C* is read as the
# occupancy there. R = 3000, m = 1, k = 0.15, Zipf a = 0.8 and
# N = 20000 keys are illustrative, not measurements.
import math

N, A = 20000, 0.8
R, M, K = 3000, 1.0, 0.15


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_hit(p, t):
    return math.fsum(x * -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 slope(p, t):
    num = math.fsum(x * x * math.exp(-x * t) for x in p)
    den = math.fsum(x * math.exp(-x * t) for x in p)
    return num / den


def best_t(p, target, tol=1e-9):
    lo, hi = 0.0, 1.0
    while slope(p, hi) > target:
        hi = 2.0 * hi
    while hi - lo > tol * hi:
        mid = 0.5 * (lo + hi)
        if slope(p, mid) > target:
            lo = mid
        else:
            hi = mid
    return 0.5 * (lo + hi)


def cost(p, c, r, m, k):
    t = che_t(p, c)
    return r * m * (1.0 - che_hit(p, t)) + k * c, che_hit(p, t)


if __name__ == "__main__":
    p = zipf(N, A)
    t = best_t(p, K / (R * M))
    cs = round(occupancy(p, t))
    print("Daily cost, R = {}, m = {}, k = {} (illustrative units)"
          .format(R, M, K))
    print("      C     LRU hit   recompute   storage    total")
    for c in (0, cs // 4, cs // 2, cs, 2 * cs, 4 * cs):
        if c == 0:
            tot, h = R * M, 0.0
        else:
            tot, h = cost(p, c, R, M, K)
        print("  {:5d}     {:.4f}    {:8.1f}   {:7.1f}   {:7.1f}".format(
            c, h, R * M * (1 - h), K * c, tot))
    print("optimum C* = {} slots, {:.4f} of the catalogue".format(
        cs, cs / N))
    for k2 in (0.075, 0.3):
        c2 = round(occupancy(p, best_t(p, k2 / (R * M))))
        print("slot cost k = {:<5}: C* = {:5d}".format(k2, c2))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《缓存命中率与车氏近似、排盘结果缓存容量的最优边界母典》第 4 章「边际收益:容量与命中率曲线的斜率和成本最优边界」(版本 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}
}

本书其他章节结论