캐시 미스

찾는 것이 캐시에 없어서 원본까지 가야 하는 조회 결과입니다. 캐시를 먼저 들여다보는 자리에서 조회는 언제나 둘 중 하나로 끝납니다. 있으면 캐시 히트이고, 없으면 캐시 미스입니다.

상세

책상 위에 자주 보는 책 몇 권을 꺼내 둡니다. 필요한 책이 그 자리에 없으면 서가까지 걸어가야 합니다. 그 걸음이 캐시 미스입니다.

캐시 미스는 캐시를 먼저 조회했을 때 찾는 항목이 거기 없는 결과입니다. 그러면 원본까지 가서 가져와야 합니다. 가져오는 것은 복사본이라 원본은 제자리에 그대로 남습니다. 반대쪽이 캐시 히트입니다. 미스가 났다고 조회가 실패한 것은 아닙니다. 캐시가 비어 있을 때 미스가 나는 것은 설계대로 도는 것입니다. 전체 조회 가운데 미스가 차지하는 비율을 미스율이라고 부릅니다. 한 번 빗나갔을 때 더 드는 비용은 미스 페널티라고 부릅니다.

미스는 조회의 끝이 아니라 중간입니다. Hill 과 Smith 는 1989년 논문에서 이 갈림을 조회 절차로 적습니다. 블록 하나를 참조하면 집합을 골라 그 안의 자리를 뒤집니다. 찾으면 캐시 히트입니다. 집합을 다 뒤지고도 못 찾으면 캐시 미스입니다. 미스가 나면 그 집합의 블록 하나를 메모리에서 가져온 것으로 바꿔 넣습니다. 그러고 나서 요청받은 값을 돌려줍니다. 미스는 값을 돌려주는 것으로 끝나지 않습니다. 캐시의 자리 하나를 바꿔 놓고 지나갑니다.

flowchart TD
    A[조회] --> B{캐시에 있나}
    B -->|있다| C[캐시 히트]
    B -->|없다| D[캐시 미스]
    D --> E[원본에서 가져온다]
    E --> F[캐시의 자리 하나를 채운다]
    F --> G[요청한 쪽에 돌려준다]

같은 말이 자리를 가리지 않고 쓰입니다. CPU(Central Processing Unit, 중앙처리장치) 캐시에서도, 운영체제의 페이지 캐시에서도, 데이터베이스 버퍼에서도, CDN(Content Delivery Network, 콘텐츠 전송 네트워크)의 응답 캐시에서도 뜻이 갈리지 않습니다. 어디서나 찾았는데 없었다는 한 가지를 가리킵니다. HTTP(HyperText Transfer Protocol) 캐시를 정하는 RFC(Request for Comments) 9111 도 이 말을 그대로 씁니다. 그 문서는 캐시가 미스에서 원본으로 내보내는 요청 하나에 들어온 요청 여럿을 합칠 수 있다고 적습니다. 그렇게 요청을 합치면 오리진 서버와 네트워크의 부하가 줄어든다고 덧붙입니다.

배경

캐시를 두면 조회가 히트와 미스 둘로 갈립니다. 그러면 이 캐시가 값을 하는지 물어볼 수 있게 됩니다. 답을 세려면 빗나간 쪽을 세야 합니다. 미스율이 캐시를 재는 잣대가 된 것이 여기서 나옵니다.

미스율을 내리는 손잡이는 하나가 아닙니다. 캐시를 키울 수도 있고, 블록이 한 자리에 몰리지 않도록 연관도를 올릴 수도 있습니다. Hill 과 Smith 는 연관도를 올리면 최근에 참조한 블록이 같은 자리에 너무 많이 사상될 확률이 내려간다고 적습니다. 교체 후보로 볼 블록도 늘어난다고 덧붙입니다. 그래서 블록이 캐시에 남아 있을 가능성이 올라갑니다. 다만 연관도가 미스율에 미치는 영향은 그때까지 따로 떼어 재어진 적이 없었습니다. 두 사람은 그것을 논문의 주요 목표 가운데 하나로 삼았습니다.

여기서 분류가 필요해집니다. 미스를 한 덩어리로 세면 어느 손잡이를 돌려야 하는지 알 수 없습니다. 캐시를 키워야 하는 미스와 배치를 고쳐야 하는 미스가 섞여 있기 때문입니다. 무엇을 해도 안 없어지는 미스까지 거기에 함께 셉니다. 두 사람은 관찰한 미스를 conflict · capacity · compulsory 세 갈래로 나눴습니다.

갈래

무엇 때문에 빗나갔나가 축입니다. Hill 과 Smith 는 갈래마다 원인을 붙였습니다. 각 갈래가 차지하는 몫은 미스율의 차이로 쟀습니다. 캐시 크기와 연관도를 바꿔 가며 돌린 결과를 서로 빼서 각 몫을 냅니다.

갈래	무엇으로 재나
compulsory	무한 캐시의 미스율
capacity	완전연관 캐시의 미스율 − 무한 캐시의 미스율
conflict	실제 캐시의 미스율 − 같은 크기 완전연관 캐시의 미스율

compulsory 미스

어떤 경우에도 나게 되어 있는 미스입니다. 무한 캐시, 그러니까 한 번 담은 블록을 결코 내보내지 않을 만큼 큰 캐시를 돌려도 미스율이 0이 되지 않습니다. 블록을 처음 참조하는 순간은 여전히 빗나가기 때문입니다. 그 무한 캐시의 미스율이 곧 compulsory 미스율입니다.

두 사람은 "어떤 경우에도"가 무조건은 아니라고 각주에 못 박습니다. 네 가지 가정 아래에서 그렇다는 뜻입니다. 블록 크기 고정 · LRU(Least Recently Used) 교체 · 프리페치 없음 · 비트 선택입니다. 가정이 바뀌면 이 몫도 바뀝니다.

capacity 미스

캐시 크기가 정해져 있어서 나는 미스입니다. 완전연관 캐시의 미스율에서 같은 참조열을 무한 캐시로 돌렸을 때의 미스율을 뺀 값이 capacity 미스율입니다.

완전연관 캐시는 어느 블록을 어느 자리에 놓아도 되는 캐시입니다. 배치의 제약이 없는데도 미스가 남는다면 남는 이유는 하나뿐입니다. 담을 자리 자체가 모자라 이미 담았던 블록을 내보냈다는 것입니다.

conflict 미스

자리 배치 때문에 나는 미스입니다. 두 사람은 이것을 set-conflict 미스라고 부릅니다. 활성 블록이 일부 집합에만 너무 많이 사상될 때 생긴다고 적습니다. 캐시 전체가 아니라 그 집합이 먼저 찬다는 뜻입니다.

실제 캐시의 미스율에서 같은 크기 완전연관 캐시의 미스율을 뺀 값이 conflict 미스율입니다. 크기를 그대로 두고 연관도만 올려도 줄어드는 몫이 이것입니다.

예시

미스를 세는 자리는 제품마다 이름이 다릅니다. 값과 필드 이름으로 봅니다.

nginx

$upstream_cache_status

응답 캐시에 접근한 상태가 이 변수에 담깁니다. 값은 MISS · BYPASS · EXPIRED · STALE · UPDATING · REVALIDATED · HIT 일곱 개입니다. 미스를 가리키는 값은 그중 MISS 입니다.

Redis

keyspace_hits
keyspace_misses

INFO 명령의 stats 절이 이 둘을 냅니다. keyspace_hits 는 메인 딕셔너리에서 키 조회에 성공한 횟수이고, keyspace_misses 는 실패한 횟수입니다. 키 하나를 찾는 조회가 미스의 단위입니다.

PostgreSQL

heap_blks_read
heap_blks_hit

pg_statio_all_tables 뷰의 컬럼입니다. heap_blks_read 는 이 테이블에서 디스크 블록을 읽은 횟수이고, heap_blks_hit 는 버퍼에서 맞은 횟수입니다. 미스를 따로 세는 칸이 없습니다. 디스크를 읽었다는 사실이 곧 버퍼에 없었다는 뜻이기 때문입니다. 사용자 테이블만 보려면 같은 컬럼을 가진 pg_statio_user_tables 를 씁니다.

perf_event_open

PERF_COUNT_HW_CACHE_MISSES

리눅스의 perf_event_open 시스템콜이 세는 하드웨어 이벤트입니다. 매뉴얼은 이것이 보통 마지막 레벨 캐시의 미스를 가리킨다고 적습니다. 그리고 PERF_COUNT_HW_CACHE_REFERENCES 와 같이 써서 캐시 미스율을 계산하는 용도라고 적습니다. 미스 횟수만으로는 비율이 나오지 않습니다. 참조 횟수를 같이 세야 미스율이 됩니다.

캐시 미스

상세

배경

갈래

compulsory 미스

capacity 미스

conflict 미스

예시

nginx

Redis

PostgreSQL

perf_event_open

관련 항목

미스가 나타나는 캐시 계층과 종류

미스가 걸쳐 있는 상위 기술 영역

미스와 히트를 함께 재는 값

미스율에 영향을 주는 성질

미스를 다루는 기법과 장치

미스가 몰릴 때 터지는 장애

무효화가 남기는 문제

미스를 세는 값을 내는 제품