지프 분포 캐시 히트율 계산기
항목 수와 지프 지수, 캐시 크기를 넣으면 인기 상위 K개를 담았을 때의 히트율을 조화수 비 H(K,s)/H(N,s)로 계산합니다. 캐시를 10배씩 키울 때 히트율이 얼마나 오르는지 표로 보이고, 목표 히트율에 필요한 캐시 크기도 거꾸로 찾습니다.
캐시에 들어갈 수 있는 후보 전체입니다. 상품·문서·키의 가짓수.
클수록 인기가 몇 개에 쏠립니다. 0이면 모두 똑같이 불리고, 1이 흔히 말하는 지프 법칙입니다.
인기 상위 K개를 담았다고 봅니다.
상위 1,000개를 담았을 때 히트율
52.01%
전체 1,000,000개 가운데 0.1%만 담고 접근의 52%를 막습니다. 인기가 고르게 흩어져 있었다면(s = 0) 0.1%에 그쳤을 자리입니다.
캐시를 10배씩 키우면
| 캐시 크기 | 항목 비율 | 히트율 | 오른 폭 |
|---|---|---|---|
| 1개 | 0% | 6.9% | +6.9%p |
| 10개 | 0.001% | 20.4% | +13.4%p |
| 100개 | 0.01% | 36% | +15.7%p |
| 1,000개 | 0.1% | 52% | +16%p |
| 10,000개 | 1% | 68% | +16%p |
| 100,000개 | 10% | 84% | +16%p |
| 1,000,000개 | 100% | 100% | +16%p |
s가 1 근처면 「오른 폭」이 줄마다 거의 같습니다. H(n, 1)이 ln n + γ에 붙으므로 히트율이 대략 ln K ÷ ln N이 되고, 열 배 키울 때마다 ln 10 ÷ ln N만큼 일정하게 오르기 때문입니다. 캐시를 키울수록 수확이 늘기는커녕 늘 같은 폭이라, 「캐시를 열 배 늘렸는데 히트율은 조금밖에 안 올랐다」는 말이 나오는 자리가 여기입니다. s를 0으로 내리면 오른 폭이 뒤로 갈수록 커지고, 1.3으로 올리면 앞줄에서 이미 다 끝납니다.
그 히트율을 채우는 가장 작은 캐시 크기를 거꾸로 찾습니다.
사용 방법
- 1전체 항목 수 N을 넣습니다. 캐시에 들어갈 수 있는 후보 전체입니다.
- 2지프 지수 s를 고릅니다. 1이 흔히 말하는 지프 법칙이고, 0이면 모두 똑같이 불리는 균등 분포입니다.
- 3캐시 크기 K를 넣으면 인기 상위 K개를 담았을 때의 히트율이 나옵니다.
- 410배씩 키운 표에서 「오른 폭」 열을 봅니다. s가 1 근처면 줄마다 거의 같은 폭입니다.
- 5목표 히트율을 고르면 그것을 채우는 가장 작은 캐시 크기가 거꾸로 나옵니다.
자주 묻는 질문
인기 상위 K개를 담았을 때의 히트율은 H(K, s) ÷ H(N, s)입니다. H(n, s) = 1/1^s + 1/2^s + … + 1/n^s인 일반화 조화수이고, 순위 i번 항목이 불릴 확률이 i^(−s) ÷ H(N, s)이므로 앞쪽 K개를 더하면 분모가 그대로 남아 이렇게 짧아집니다. 예를 들어 항목 100만 개에 s = 1이면 상위 1000개(0.1%)만 담아도 접근의 52%를 막습니다.
s가 1이면 항목 수와 무관하게 ln 10 ÷ ln N만큼만 오릅니다. 항목 100만 개라면 캐시가 1000개든 1만 개든 10배 키울 때마다 16%포인트씩 일정하게 오를 뿐입니다. H(n, 1)이 ln n + γ에 붙어 히트율이 대략 ln K ÷ ln N이 되기 때문이고, 캐시를 키울수록 수확이 늘기는커녕 늘 같은 폭이라는 뜻입니다. 「캐시를 늘렸는데 히트율이 안 오른다」는 말이 나오는 자리가 여기입니다.
쓰던 캐시의 실측 히트율에 맞추는 것이 가장 정확합니다. 항목 수와 캐시 크기를 넣고 s를 움직여 지금 나오는 히트율과 맞춘 뒤, 그 s로 「캐시를 키우면 얼마나 오를지」를 가늠하는 방식입니다. 문헌에서는 웹 요청·CDN 접근이 s = 0.6~1.0, 검색어와 단어 빈도가 s = 1 근처로 보고되지만 서비스마다 크게 다릅니다.
항목 수에 따라 다르며 s = 0.87~0.95 근처입니다. 항목 1만 개면 s = 0.95, 100만 개면 0.89, 10억 개면 0.87에서 딱 80대 20이 됩니다. 파레토 분포와 달리 지프는 스케일 불변이 아니라서, 항목이 많아질수록 꼬리가 길어져 같은 80대 20을 만드는 s가 작아집니다. s = 1이고 항목이 100만 개면 상위 20%가 88.8%를 가져가 80대 20보다 더 쏠립니다.
실제로는 이보다 낮게 나오며, 이 값은 상한에 가깝습니다. 「인기 상위 K개가 정확히 캐시에 들어 있다」고 본 결과라 교체 정책이 완벽하다는 뜻인데, LRU·LFU 같은 실제 정책은 인기 순위를 뒤늦게 따라갑니다. 접근 분포가 지프를 따른다는 것 자체도 가정이고, 실제 로그에서는 인기 순위가 시간에 따라 흔들리며 상위 몇 개는 지프보다 완만한 경우가 많습니다.
H(N, s)가 N을 아무리 키워도 ζ(s)로 수렴합니다. 꼬리가 길어져도 총량이 늘지 않는다는 뜻이라, 항목이 몇 개든 상위 몇 개만 담으면 히트율이 금세 1에 가까워집니다. 반대로 s가 1 이하면 꼬리의 총량이 계속 자라기 때문에 항목이 늘어날수록 같은 캐시 크기의 히트율이 떨어집니다. s = 0이면 모두 똑같이 불려서 히트율이 그냥 K/N이 되고, 캐시가 가장 안 듣는 경우입니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 조화수 H(n, s)는 앞의 1000항을 그대로 더하고 나머지를 오일러–매클로린 공식으로 이어 계산합니다. 항목이 10억 개여도 상수 시간에 가깝게 답하며, 남는 오차는 배정밀도 한계 아래입니다.
- 검증은 n = 1001~20000 구간에서 s를 0.5·0.8·1·1.2·2로 바꿔 가며 항을 하나씩 더한 값과 소수점 10자리까지 대조해 했습니다. 근사가 시작되는 경계(1001, 1002)를 특히 포함시켰습니다.
- s > 1에서 H(∞, s)가 리만 제타 함수 ζ(s)로 수렴하는 것을 ζ(2) = π²/6, ζ(3), ζ(4) = π⁴/90, ζ(1.5)와 대조했습니다. s = 1.5처럼 꼬리가 늦게 죽는 경우 유한한 N에서는 ζ(s)에 못 미치는 몫(2/√N)까지 계산에 넣어 맞췄습니다.
- s = 1은 적분이 로그가 되어 식이 갈라지므로 따로 처리했습니다. 이 분기를 빠뜨리면 가장 많이 쓰는 s = 1에서 0으로 나누게 됩니다. s가 1에 아주 가까운 값(1±10⁻⁹)에서도 이어지는 것을 확인했습니다.
- 히트율이 K와 s 모두에 대해 단조증가하는 것, 상위 K개 확률의 합과 정확히 같은 것, s = 1에서 10배마다 오르는 폭이 ln 10 ÷ ln N으로 일정한 것을 테스트로 고정했습니다.
- 「인기 상위 K개가 정확히 캐시에 들어 있다」고 본 값이라 실제 교체 정책(LRU·LFU)의 히트율보다 높게 나옵니다. 상한으로 보는 것이 안전합니다.
- 접근 분포가 지프를 따른다는 가정 자체가 근사입니다. 실제 로그에서는 인기 순위가 시간에 따라 흔들리고 상위 몇 개가 지프보다 완만한 경우가 많아, 실측 히트율은 여기서 나온 값보다 낮기 쉽습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.