95%에서 99%로 가는 4%가 시스템 비용을 가른다
캐시 적중률이 95%에서 99%로 올랐다고 하면 4%포인트 개선처럼 보인다. 그러나 시스템 성능 관점에서 이 차이는 다섯 배에 가깝다. 핵심은 적중률이 아니라 미스율의 비율 차이다. 95% 적중은 5% 미스를 의미하고, 99% 적중은 1% 미스를 의미한다. 미스가 5분의 1로 줄어든 것이다. 이 차이를 사용자 관점에서 정리한 Cloudflare의 캐싱 학습 자료는 캐시 적중률이 1%포인트 오를 때마다 원본 서버 부하가 어떤 비율로 줄어드는지를 트래픽 단위로 계산해 보여준다.
미스 비용이 적중 비용보다 압도적으로 클 때 이 차이가 결정적이 된다. CPU 캐시 적중은 1나노초, 메모리 접근은 100나노초 수준이다. 100배 차이다. 95%의 적중률에서 평균 접근 시간은 0.95 곱하기 1 더하기 0.05 곱하기 100, 약 6 나노초다. 99% 적중률에서는 0.99 곱하기 1 더하기 0.01 곱하기 100, 약 2 나노초다. 적중률 4%포인트 차이가 평균 응답 시간을 세 배로 만든다.
웹 서비스에서는 비율이 더 극단적이다
웹 캐시에서는 이 비율이 더 극단적이다. CDN 적중은 수십 밀리초, 원본 서버까지 가는 미스는 수백 밀리초가 걸린다. 적중률 99%와 95% 사이의 평균 응답 시간 차이는 다섯 배에서 열 배까지 벌어질 수 있다. 사용자 입장에서 1초 안에 끝나는 페이지가 5초가 걸리는 페이지로 바뀐다.
이 때문에 캐시 시스템 설계에서 적중률은 단순한 지표가 아니라 비용 함수의 가장 큰 변수다. 적중률을 1%포인트 올리기 위해 캐시 메모리를 두 배 늘리는 게 합리적인지는, 그 1%포인트가 평균 응답 시간을 얼마나 줄이는지로 계산된다. 메모리 비용과 응답 시간 단축에서 오는 가치를 비교해 손익 분기점을 잡는다.
지역성이 캐시의 본질이다
캐시가 작동하는 이유는 데이터 접근에 지역성(Locality)이 존재하기 때문이다. 시간적 지역성은 한 번 접근한 데이터가 곧 다시 접근될 가능성이 높다는 패턴이고, 공간적 지역성은 한 위치에 접근하면 그 근처 위치에 접근할 가능성이 높다는 패턴이다. 두 지역성이 모두 약한 워크로드에서는 캐시 효율이 떨어진다. 1968년 피터 데닝(Peter Denning)이 워킹셋 모델을 제안하면서 처음 정량화한 이 개념은 이후 모든 메모리 계층 설계의 출발점이 되었다.
무엇을 캐시에서 내보낼 것인가가 더 어려운 문제다
캐시 크기가 무한하다면 적중률은 100%에 가까워진다. 그러나 캐시는 항상 유한하고, 캐시가 가득 차면 무언가를 내보내야 새로운 데이터를 넣을 수 있다. 이때 어떤 항목을 내보낼지 결정하는 알고리즘이 교체 정책(Replacement policy)이고 캐시 시스템 설계의 가장 어려운 부분이다.
LRU가 표준이 된 이유와 그 약점
가장 단순한 정책은 가장 오랫동안 사용되지 않은 항목을 내보내는 LRU(Least Recently Used)다. 시간적 지역성 가정 위에서 단순하고 효과적이라 가장 널리 쓰인다. 그러나 LRU도 약점이 있다. 한 번만 접근하는 데이터가 대량으로 들어오면 기존의 자주 쓰이는 데이터를 모두 밀어내는 캐시 오염(Cache pollution)이 발생한다.
이 문제를 해결하기 위해 IBM 연구소의 니마트로드 메기도(Nimrod Megiddo)와 단다파니 모드하(Dharmendra Modha)가 2003년에 제안한 ARC(Adaptive Replacement Cache) 알고리즘은 최근 접근 빈도와 최근 접근 시점을 동시에 추적하는 두 개의 LRU 리스트를 유지한다. 워크로드가 일시적이라 사라지는 데이터인지 자주 쓰이는 데이터인지를 알고리즘이 스스로 학습해 비율을 조정한다. ZFS와 PostgreSQL 일부 버전이 이 알고리즘을 채택했다.
일관성이 가장 비싼 문제
분산 시스템에서 캐시는 또 다른 문제를 만든다. 원본 데이터가 변경되었을 때 캐시된 사본을 어떻게 갱신할 것인가의 문제, 즉 캐시 일관성(Cache coherence) 문제다. 가장 간단한 방법은 원본 변경 시 캐시를 무효화하는 것이지만 분산 환경에서 이 무효화 메시지가 모든 캐시 노드에 도달하는 데 시간이 걸린다. 그 사이 사용자는 오래된 데이터를 본다. 이 지연 시간이 비즈니스 요구사항을 어디서 깨는지 정의하는 게 분산 캐시 설계의 본질이다.
접근 분포가 캐시 효율을 좌우한다
캐시 시스템의 성능 분석은 결국 확률 분포 위에서 이루어진다. 접근 패턴이 균등 분포라면 캐시 효율은 매우 낮다. 인기 콘텐츠가 소수에 집중되는 멱법칙 분포를 따른다면 적은 캐시 메모리로도 높은 적중률을 얻을 수 있다. 해시 충돌의 수학이 캐시의 해시 기반 자료구조 설계에 그대로 적용되고, 몬테카를로 시뮬레이션이 새로운 교체 정책을 평가할 때 표준 도구로 쓰인다.
적중률이라는 단일 지표가 캐시 효율을 대변하는 것처럼 보이지만, 실제로는 미스 비용, 워크로드 분포, 교체 정책, 일관성 정책이 모두 얽힌 다차원 문제다. 한 시스템에서 잘 작동하는 캐시 설계가 다른 시스템에서는 효율이 떨어지는 이유가 여기에 있다. 95%에서 99%로 가는 4%포인트의 이면에는 이 모든 변수가 들어가 있다.