Model

Zipf: what the hottest items carry

The benefit is logarithmic in the cache size: the last slice of hit rate costs the most.

h (k) \approx \frac{ln k}{ln N} (α \approx 1), k = N^{h}

$k$: Hot items; the top k items (what you cache)
$N$: Items; all items
$h$: Share; the fraction of accesses that go to the top k
$α$: Exponent; the item ranked r is accessed in proportion to 1/r^α

Recurring principle: Power laws and skew

How it behaves

One input on the horizontal axis, the others held fixed.

N = 10⁶N = 10⁹

Data table

Share of accesses to the hottest items, by the fraction cached (α ≈ 1)
Fraction of items cached k/N	series	Accesses served
0	N = 10⁶	16.7%
0	N = 10⁶	17.7%
0	N = 10⁶	18.8%
0	N = 10⁶	19.8%
0	N = 10⁶	20.8%
0	N = 10⁶	21.9%
0	N = 10⁶	22.9%
0	N = 10⁶	24%
0	N = 10⁶	25%
0	N = 10⁶	26%
0	N = 10⁶	27.1%
0	N = 10⁶	28.1%
0	N = 10⁶	29.2%
0	N = 10⁶	30.2%
0	N = 10⁶	31.3%
0	N = 10⁶	32.3%
0	N = 10⁶	33.3%
0	N = 10⁶	34.4%
0	N = 10⁶	35.4%
0	N = 10⁶	36.5%
0	N = 10⁶	37.5%
0	N = 10⁶	38.5%
0	N = 10⁶	39.6%
0	N = 10⁶	40.6%
0	N = 10⁶	41.7%
0	N = 10⁶	42.7%
0	N = 10⁶	43.8%
0	N = 10⁶	44.8%
0.001	N = 10⁶	45.8%
0.001	N = 10⁶	46.9%
0.001	N = 10⁶	47.9%
0.001	N = 10⁶	49%
0.001	N = 10⁶	50%
0.001	N = 10⁶	51%
0.001	N = 10⁶	52.1%
0.002	N = 10⁶	53.1%
0.002	N = 10⁶	54.2%
0.002	N = 10⁶	55.2%
0.002	N = 10⁶	56.3%
0.003	N = 10⁶	57.3%
0.003	N = 10⁶	58.3%
0.004	N = 10⁶	59.4%
0.004	N = 10⁶	60.4%
0.005	N = 10⁶	61.5%
0.006	N = 10⁶	62.5%
0.006	N = 10⁶	63.5%
0.008	N = 10⁶	64.6%
0.009	N = 10⁶	65.6%
0.01	N = 10⁶	66.7%
0.012	N = 10⁶	67.7%
0.013	N = 10⁶	68.8%
0.015	N = 10⁶	69.8%
0.018	N = 10⁶	70.8%
0.021	N = 10⁶	71.9%
0.024	N = 10⁶	72.9%
0.027	N = 10⁶	74%
0.032	N = 10⁶	75%
0.037	N = 10⁶	76%
0.042	N = 10⁶	77.1%
0.049	N = 10⁶	78.1%
0.056	N = 10⁶	79.2%
0.065	N = 10⁶	80.2%
0.075	N = 10⁶	81.3%
0.087	N = 10⁶	82.3%
0.1	N = 10⁶	83.3%
0.115	N = 10⁶	84.4%
0.133	N = 10⁶	85.4%
0.154	N = 10⁶	86.5%
0.178	N = 10⁶	87.5%
0.205	N = 10⁶	88.5%
0.237	N = 10⁶	89.6%
0.274	N = 10⁶	90.6%
0.316	N = 10⁶	91.7%
0.365	N = 10⁶	92.7%
0.422	N = 10⁶	93.8%
0.487	N = 10⁶	94.8%
0.562	N = 10⁶	95.8%
0.649	N = 10⁶	96.9%
0.75	N = 10⁶	97.9%
0.866	N = 10⁶	99%
1	N = 10⁶	100%
0	N = 10⁹	44.4%
0	N = 10⁹	45.1%
0	N = 10⁹	45.8%
0	N = 10⁹	46.5%
0	N = 10⁹	47.2%
0	N = 10⁹	47.9%
0	N = 10⁹	48.6%
0	N = 10⁹	49.3%
0	N = 10⁹	50%
0	N = 10⁹	50.7%
0	N = 10⁹	51.4%
0	N = 10⁹	52.1%
0	N = 10⁹	52.8%
0	N = 10⁹	53.5%
0	N = 10⁹	54.2%
0	N = 10⁹	54.9%
0	N = 10⁹	55.6%
0	N = 10⁹	56.3%
0	N = 10⁹	56.9%
0	N = 10⁹	57.6%
0	N = 10⁹	58.3%
0	N = 10⁹	59%
0	N = 10⁹	59.7%
0	N = 10⁹	60.4%
0	N = 10⁹	61.1%
0	N = 10⁹	61.8%
0	N = 10⁹	62.5%
0	N = 10⁹	63.2%
0.001	N = 10⁹	63.9%
0.001	N = 10⁹	64.6%
0.001	N = 10⁹	65.3%
0.001	N = 10⁹	66%
0.001	N = 10⁹	66.7%
0.001	N = 10⁹	67.4%
0.001	N = 10⁹	68.1%
0.002	N = 10⁹	68.8%
0.002	N = 10⁹	69.4%
0.002	N = 10⁹	70.1%
0.002	N = 10⁹	70.8%
0.003	N = 10⁹	71.5%
0.003	N = 10⁹	72.2%
0.004	N = 10⁹	72.9%
0.004	N = 10⁹	73.6%
0.005	N = 10⁹	74.3%
0.006	N = 10⁹	75%
0.006	N = 10⁹	75.7%
0.008	N = 10⁹	76.4%
0.009	N = 10⁹	77.1%
0.01	N = 10⁹	77.8%
0.012	N = 10⁹	78.5%
0.013	N = 10⁹	79.2%
0.015	N = 10⁹	79.9%
0.018	N = 10⁹	80.6%
0.021	N = 10⁹	81.3%
0.024	N = 10⁹	81.9%
0.027	N = 10⁹	82.6%
0.032	N = 10⁹	83.3%
0.037	N = 10⁹	84%
0.042	N = 10⁹	84.7%
0.049	N = 10⁹	85.4%
0.056	N = 10⁹	86.1%
0.065	N = 10⁹	86.8%
0.075	N = 10⁹	87.5%
0.087	N = 10⁹	88.2%
0.1	N = 10⁹	88.9%
0.115	N = 10⁹	89.6%
0.133	N = 10⁹	90.3%
0.154	N = 10⁹	91%
0.178	N = 10⁹	91.7%
0.205	N = 10⁹	92.4%
0.237	N = 10⁹	93.1%
0.274	N = 10⁹	93.8%
0.316	N = 10⁹	94.4%
0.365	N = 10⁹	95.1%
0.422	N = 10⁹	95.8%
0.487	N = 10⁹	96.5%
0.562	N = 10⁹	97.2%
0.649	N = 10⁹	97.9%
0.75	N = 10⁹	98.6%
0.866	N = 10⁹	99.3%
1	N = 10⁹	100%

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Caching
What happens when we deliberately keep a second copy of data that no protocol forces to be correct?
$h \approx ln C / ln N, C \approx N^{h}$
C (cache size) = $k$
Read it in place →
Caching
What happens when we deliberately keep a second copy of data that no protocol forces to be correct?
$h \approx (C / N)^{1 - α} (α < 1)$
C (cache size) = $k$
Read it in place →
Caching
What happens when we deliberately keep a second copy of data that no protocol forces to be correct?
$Δ h = ln k / ln N$
k (nodes pooling one keyspace) = $k$
Read it in place →