메모리 계층과 캐싱 뽀개기

Eddy·2022년 7월 16일

library

거대한 도서관을 생각해보자.

이 도서관은 수십만권의 책을 보관하고 있다. 수백년 된 고서부터 신간까지. 이 많은 책은 다 어떤 방식으로 보관하고 있을까?

뭐... 책꽂이에 꽂아놓겠지.

쉽게 생각하면 그렇다. 하지만 자세히 들여다보면 더 복잡한 시스템이 있다.

사람들이 자주 찾는 책이나 신간은 입구 근처, 눈에 잘 띄는 곳에 배치한다. 책표지가 잘 보이도록 꺼내놓거나 눕혀놓는다.

사람들이 잘 찾지 않는 책이나 오래된 책도 있다. 이런 책들은 일반 서가가 아닌 별도 서고에 집어넣는다. 서고는 많은 책을 효율적으로 저장할 수 있는 구조다. 정말 큰 도서관은 보통 사람들이 들어갈 수 없는 서고가 수십개씩 있는 경우도 있다.

(출처: 이데일리)

디지털 데이터도 마찬가지다. 컴퓨터의 저장 공간도 여러 방식의 층으로 나뉘어있다.

CPU 레지스터는 현재 실행 중인 명령어, 데이터 등을 저장한다. 엄청나게 빨리 데이터를 가져올 수 있다.

그 다음엔 작지만 빠른 캐시 메모리가 있다. 캐시 메모리는 비교적 느린 메인 메모리와 프로세서 사이 중간 다리 역할을 한다.

메인 메모리는 그것보다 더 느린 디스크나 원격 서버의 중간 저장소 역할을 한다.

(출처: 컴퓨터 시스템)

모든 컴퓨팅 시스템은 이런 '메모리 계층'을 가진다. 메모리 계층이 생기는 근본 이유는 2가지다.

저장 매체의 가격, 성능 간 트레이드 오프
프로그램이 가지는 지역성(Locality)

이 2가지에 대해서는 뒤에 좀 더 자세히 설명하자.

잠깐, 우리가 왜 이걸 알아야 하는데?

프로그래머가 메모리 계층에 대해 알아야 하는 이유. 프로그램의 성능을 이해하려면 메모리 계층을 알아야 하기 때문이다.

메모리 계층 구조는 프로그램 성능을 좌지우지한다. 프로그램이 사용하는 데이터가 어떤 층에 저장돼있냐, 여기에 따라서 프로그램 성능은 수십배에서 수천만배까지 차이가 난다.

시간이 흐르면서 CPU의 계산 속도와 메모리 접근 속도는 모두 향상되고 있다.

하지만 메모리 접근 속도는 CPU 계산 속도만큼 빠르게 증가하진 않는다. 따라서 메모리에서 데이터를 '가져오는 시간'은 전체 프로그램 실행 시간을 크게 좌우한다.

메모리 계층을 잘 알아야 프로그램의 성능을 이해할 수 있다.

이 글을 끝까지 읽고나면 메모리 계층과 캐싱이 무엇인지 알게 될 것이다. 메모리 접근 속도의 원리를 이해하는 개발자가 될 수 있다!

1. 저장 매체

첫번째, 저장 매체 기술.

컴퓨터에는 데이터를 저장하고 유지한 공간이 필요하다. 데이터는 0과 1의 비트로 어딘가에 저장된다. 이 정보를 저장하기 위해 컴퓨터는 다양한 방식을 쓴다.

가장 중요한 3개 카테고리만 알아보자. RAM, ROM, 디스크다.

1. RAM

Random Access Memory.

임의 접근(Random Access)은 처음 들으면 무슨 소린지 잘 이해가 안 된다. 랜덤하게 메모리에 접근한다는 뜻은 아니다. 어떤 랜덤한 위치가 주어질 때, 그 위치로 즉시 이동해서 값을 읽을 수 있다는 뜻이다. 덕분에 RAM은 데이터 접근이 빠르다.

반대로 '순차 접근'이 있다. 순차 접근은 어떤 위치가 주어지면, 차례차례 일정한 순서를 거쳐서 해당 위치를 찾아가야 한다.

RAM의 중요한 특징은 '휘발성'이다. 전원이 꺼지면 RAM에 저장된 데이터는 날아간다.

RAM도 2가지 종류가 있다.

Static RAM (SRAM)

(wikipedia)

가장 빠르고 비싼 메모리다. 메모리계의 포르쉐다.

컴퓨터에서는 CPU 내부에 있는 캐시 메모리에 사용된다.

SRAM은 6개의 트랜지스터로 만든 '플립플롭' 회로에 하나의 비트를 저장한다. 트랜지스터가 6개 사용되기 때문에 밀도를 높이거나, 가격을 낮추기가 어렵다.

비싼 대신 빠르고, 안정적이다. SRAM은 '전기가 들어오는' 동안에는 외부 방해에도 끄떡없고, 기록한 비트값이 안정적으로 유지된다. 'Static' RAM인 이유다.

그렇다면 끄떡있는 녀석도 있겠지? 그게 바로...

Dynamic RAM (DRAM)

흔히 '그 컴퓨터 램 몇 기가야?' 할 때 말하는 바로 그 램이 DRAM이다. 보통 4-32GB 정도 용량이다.

DRAM은 캐시 메모리보다 용량이 더 큰 주 기억 장치 (메인 메모리)에 사용되는 저장 매체다. 컴퓨터의 가장 핵심 부품 중 하나.

참고로 우리나라 시가총액 1,2위 기업인 삼성전자와 SK하이닉스의 주력 상품이 바로 이 DRAM이다. 전세계 DRAM의 70-80%는 메이드 인 코리아. DRAM은 한국 최대의 수출품이다.

(wikipedia)

DRAM에 많은 양의 데이터가 들어가는 이유는 뭘까? DRAM은 '캐파시터(Capacitor)'라는 아주 작은 상자에 전자를 담는다. 트랜지스터 1개를 사용해 캐파시터의 뚜껑을 덮고 상태를 유지한다. 캐파시터에 전자가 있으면 1, 아니면 0으로 비트를 표현한다.

캐파시터는 매우 작고, 트랜지스터를 하나만 사용한다. 밀도를 매우 높일 수 있다. 가격도 SRAM보다 저렴하다.

하지만 이 캐파시터의 전자가 시간이 지나면 새어나간다. 시간이 지나면 값이 사라진다. 마치 모래 위에 쓴 글씨처럼. 이게 문제다.

안정적인 SRAM과 다르다고 해서, 'Dynamic RAM'이라는 이름이 붙었다.

DRAM은 방전되어 내용이 사라지기 전에 충전을 다시 해줘야 한다. DRAM의 전자가 유지되는 시간은 10-100ms 정도다. 0.01초에서 0.1초만 지나면 내용이 사라진다.

아니, 그런 걸 쓸 수가 있나?

라는 생각이 들지만, 우리의 시간과 컴퓨터의 시간은 다르기 때문에 괜찮다.
컴퓨터의 클락 사이클은 나노 세컨드다. 계속 충전해가면서 쓰면 된다.

(중간 요약) SRAM과 DRAM
빠르고 안정적이지만, 비싸서 조금밖에 못쓰는 게 SRAM.
덜 빠르고 불안정하지만, 싸서 많이 쓸 수 있는 게 DRAM.

2. ROM

ROM은 RAM과 달리 전원이 꺼져서 내용이 사라지지 않는 메모리다. RAM만큼 데이터를 빠르게 가져올 수는 없다. 하지만 전원이 꺼져도 정보를 저장해주는 믿을 수 있는 친구다.

어떻게 전기가 공급되지 않아도 정보를 저장할 수 있을까?

최초의 'ROM'은 천공 카드라고 한다. 시험 볼 때 쓰던 OMR 카드 같이 생겼다. 여기에 구멍을 뚫어 비트를 표시한다. 물론 손으로 일일이 구멍을 뚫는 건 매우 비효율적이었다.

점점 더 효율적인 ROM들이 등장했다. 프로그래밍이 가능한 PROM, 쓴 데이터를 지울 수 있는 EPROM, 전기로 작동하는 EEPROM 등.

플래시 메모리

Flash
(electrorules)

플래시 메모리는 EEPROM의 일종이자 가장 중요한 ROM 기술이다. 1980년대 일본 도시바에서 개발했다.

플래시 메모리는 비휘발성인데도 속도가 빠르고, 내구성이 강하고, 전력도 적게 쓴다.

우리가 사용하는 USB 드라이브, 디지털 카메라, 스마트폰, 노트북, 다 이 플래시 메모리를 사용한다.

3. 디스크 드라이브

윈도우를 써봤다면, '내 컴퓨터' 안에 C 드라이브, D 드라이브를 본적이 있을 거다. 이게 바로 디스크 드라이브다.

C-drive

디스크는 앞에 나온 저장 매체보다 훨씬 느리다. 얼마나 느리냐면... DRAM보다 수십만배 느리다.

대신 디스크는 전원이 꺼져도 데이터가 사라지지 않는다. 무엇보다 엄청나게 많은 용량을 저장할 수 있다.
DRAM은 보통 커야 수십 GB인 반면, 디스크는 수천 GB다.

자주 꺼내기는 힘들지만, 많은 양이 들어가는 창고 느낌이랄까? 그래서 디스크는 컴퓨터에서 '보조 기억 장치' 역할을 한다.

디스크 드라이브에는 전통적인 하드 디스크 드라이브(HDD)와 솔리드 스테이트 드라이브(SSD)가 있다.

하드 디스크 드라이브 (HDD)

LP판을 본 적이 있는가?

vinyl

LP판을 보면 판에 미세한 홈이 파여있다. 이 홈들이 음악 데이터를 저장한다.

턴테이블에 LP를 올리면, 바늘이 홈을 읽어서 음악을 재생한다.

HDD도 같다. 플래터라고 부르는 원판이 있다. 이 원판에 자성(Magnetic)으로 데이터를 기록하도록 돼있다.

이 원판은 모터로 빠르게 회전한다. 그 위에 헤드라는 녀석이 데이터를 읽고 쓴다.

HDD

물리적 속도에 한계가 있다. 데이터가 저장된 위치로 헤드가 이동하는 시간이 필요하다. 접근 속도가 느리다.

반면에 기록 밀도는 매우 높다. 많은 양의 데이터가 들어간다. 용량당 가격도 무지 싸다.

(참고) '하드' 디스크인 이유는, 플로피 디스크라는 (지금은 안 쓰이는) 저장 매체와 구분하기 위해서였다. 플로피 디스크는 구부러지는 '소프트한' 재질이었기 때문.

솔리드 스테이트 디스크 (SSD)

SSD는 최근 새롭게 떠오르는 기술이다. 하드 디스크보다 훨씬 더 빠르고, 내구성도 좋다.

SSD가 어떻게 그렇게 빠를 수 있냐?

위에서 말했던 플래시 메모리를 사용한다.

기계식 디스크 대신 플래시 메모리 여러개를 담아 디스크로 패키징했다. 보조 기억 장치로 쓰인다는 점은 같지만, HDD와는 사실 구현이 전혀 다르다.

물리적 회전 없이 전자적 방식으로 데이터를 읽고 쓴다. 움직이는 부품이 없으니 소음도 없다. 전력 소모나 내구성도 좋다. 접근 속도도 훨씬 빠르다.

가격 면에서 아직 하드 디스크보다 비싸다는 게 유일한 흠이다. 그러나 SSD가격은 빠르게 싸지고 있고, 이 차이는 거의 줄어들고 있다.

휴대성이 중요한 디바이스에서는 완전히 하드 디스크를 대체했다.

4. 저장 매체에서 중요한 점

여기까지 주요 저장 매체 기술을 알아봤다.

가장 중요한 시사점 2가지만 꼽아보겠다.
다 안 읽고 스크롤 내렸어도, 이 2가지만 기억하면 된다.

1) 저장 매체의 가격과 성능은 반비례 관계다.

(semiengineering.com)

'용량당 가격'과 '성능'은 반비례한다.

SRAM - DRAM - SSD - HDD 로 갈 수록, 가격은 싸지고 용량은 늘어나지만, 반대로 접근 속도가 느려진다.

SRAM은 HDD보다 수백만배 빠르다. 용량은 수십만배 적다.

우리는 데이터를 많이 저장하는 것도 필요하고, 빠른 것도 중요하다. 각 저장 매체는 다 명확한 장단점이 존재한다.

2) 저장 매체 성능은 프로그램 성능을 결정하는 열쇠다.

'컴퓨터 시스템' 책을 보면 1985년부터 2015년까지 메모리와 CPU 성능 변화를 비교한 표가 나온다.

<저장 매체 성능 변화>

<CPU 성능 변화>

30년 전과 비교해볼때,
SRAM의 접근 속도는 100배 빨라졌다.
DRAM의 접근 속도는 10배 빨라졌다.
DISK의 접근 속도는 25배 빨라졌다.

하지만 CPU의 실질 속도 (사이클 타임)은 2000배 증가했다.

무어의 법칙이라고 들어본 적이 있겠지? 반도체 칩에 집적할 수 있는 트랜지스터의 숫자가 적어도 매 18개월마다 두 배씩 증가한다는 법칙이다. CPU 속도는 이 법칙에 맞춰 지난 30년간 엄청난 속도로 발전했다.

하지만 메모리의 접근 속도는 그렇게 많이 빨라지지 않았다.

물론 저장 매체의 '가격'은 빠르게 떨어지고 있다. 하지만 속도 측면에서는 메모리-프로세서의 차이가 벌어지고 있다.

따라서 전체 프로그램의 속도를 향상시키기 위해서 '메모리 접근 속도'를 높이는 게 중요하다. 메모리에서 값을 가져와서, CPU가 계산을 하는 게 컴퓨터의 일이다.

'저장 매체의 트레이드 오프'를 고려하면서도 '메모리 접근 속도'를 높이려면 어떻게 해야할까?

다음에 나올 '지역성' 원리가 중요한 이유다.

2. 지역성

우리는 익숙한 것에 계속 손이 가는 경향이 있다.

옷도 입던 스타일과 비슷한 옷이 편하다.
음식도 자주 먹던 음식을 많이 찾는다.

프로그램도 데이터를 찾을 때 비슷한 경향이 있다. (물론 프로그램에 취향은 없겠지만)

최근에 찾은 데이터나, 최근에 찾은 데이터 근처의 데이터를 많이 참조한다.

이걸 지역성(Locality)라고 한다.

아주 단순하지만, 프로그램이 보편적으로 가지는 속성이다. 그리고 매우 중요하다. 하드웨어, 소프트웨어의 설계에 어마어마한 영향을 끼치기 때문이다.

시간 지역성

최근에 참조된 메모리 위치를 다시 참조할 가능성이 높다.

이 경향을 시간 지역성이라고 한다.

뒤집어 말하면, 동일한 변수를 반복적으로 참조하는 프로그램은 시간 지역성이 있다.

공간 지역성

최근에 참조한 메모리 위치 '근처의' 메모리를 다시 참조할 가능성이 높다.

이건 공간적인 개념이라 공간 지역성이라고 한다.

메모리 주소를 차례차례 참조하는 프로그램은 공간 지역성이 있다. 이를 테면 배열의 순회를 돈다든지.

지역성이 있는 코드

컴퓨팅 시스템은 프로그램이 '지역성이 있다'는 가정 하에 최적화를 한다.

하드웨어, 운영체제, 어플리케이션, 웹에 이르기까지 컴퓨팅 시스템의 모든 레벨은 지역성을 활용한다.

최근에 사용한 데이터, 최근에 사용한 위치 근처의 데이터를 빨리 접근할 수 있도록 임시 보관소 (캐시)에 저장해둔다.

지역성이 높은 코드는 캐시를 더 많이 활용한다. 그 결과 실행 속도가 빨라진다.

어떤 코드가 지역성이 있는 코드일까?

같은 변수를 반복적으로 참조하는 코드.
연속 저장된 데이터를 차례차례 참조하는 코드. (순차 참조)
이런 코드가 지역성이 높다.

순차 참조 패턴을 보이는 코드 중에서도, 참조의 간격이 작을수록 좋은 지역성을 가진 코드다.

예를 들어, 배열의 인덱스를 +1 하는 루프문, +3 씩 도는 루프문이 있다고 하자. +1 루프문이 +3 루프문보다 지역성이 좋다.

// 1번
for (i = 0; i < columns; i += 1) {
  for (j = 0; j < rows; j += 1) {
    **arr[j][i] ***= 2
  }
}

// 2번
for (i = 0; i < columns; i += 1) {
  for (j = 0; j < rows; j += 1) {
    **arr[i][j]** *= 2
  }
}

차이를 발견했는가?

아주 조그만 차이 같지만, 1번에서는 j가 행, i가 열이다. 2번에서는 i가 행, j가 열이다.

1번은 [0,0] -> [1,0] -> [2,0] -> [1,1] 순으로 같은 열(column)의 위치부터 참조한다.
2번은 [0,0] -> [0,1] -> [0,2] -> [1,0] 순으로 같은 행(row)를 차례로 참조한다.

배열은 메모리 상에 연속적인 형태로 저장된다. 배열의 인덱스와 메모리 위치를 단순화해본다면 이 순서다.

(0,0) | (0,1) | (0,2) | (1,0) | (1,1) | (1,2) | (2,0) | (2,1) | (2,2)

2번 루프는 차례대로 +1 씩 돈다. 1번 루프는 위치상 +3씩 계속 점프한다.

따라서 2번이 더 지역성이 좋은 코드다.

이런 식으로 어떤 코드가 지역성이 있는지 없는지 대략적인 감을 잡을 수 있으면 좋다.
예시를 하나 더 보면서 감을 잡아보자.

퀵 정렬이 빠른 이유

합병 정렬 (Merge Sort), 힙 정렬 (Heap Sort), 퀵 정렬(Quick Sort). 빠른 정렬 3총사는 모두 시간 복잡도가 O(N log N)이다.

실제 실행 속도는 퀵 정렬이 가장 빠르다고 알려져있다. '퀵' 정렬인 이유다.

그 이유 중 하나가 바로 '지역성'이다. 퀵 정렬 구현 코드가 힙 정렬이나 머지 정렬보다 지역성이 높기 때문이다.

퀵 정렬은 피벗을 고르고, 파티셔닝하는 과정의 반복이다. 이 과정에서 같은 피벗 위치나, 좁은 범위의 변수를 반복 참조한다.

반면 힙 정렬은 이진 트리에서 부모/자식 노드에 접근하기 위해 계속해서 '곱하기 2' '나누기 2'를 해서 인덱스를 참조한다.

머지 정렬은 아예 새로운 메모리 위치에 배열을 만든다.

따라서 퀵 정렬이 메모리 계층 전반에서 훨씬 더 캐시를 많이 활용한다. 메모리 접근 속도가 줄어드니 성능이 빠르다.

애니메이션으로 보면 이 셋의 차이를 좀 더 직관적으로 이해할 수 있다.

합병 정렬을 시각화한 애니메이션이다.

merge

힙 정렬을 시각화한 애니메이션이다.

heap

퀵 정렬을 시각화한 애니메이션이다.
위의 2가지 정렬보다 훨씬 더 고정된, 좁은 범위의 참조가 많이 일어난다.

quick

(출처: Sorting Algorithm Visualization)

지역성과 캐시의 활용이 얼마나 성능에 영향을 미치는지 실감할 수 있다.

3. 메모리 계층과 캐시

챕터 1과 챕터 2에서 뭘 배웠나?

2가지로 요약해볼 수 있다.

1. 하드웨어의 특성: 저장 매체의 가격-성능 트레이드오프
-> 빠를수록 비싸다.

2. 소프트웨어의 특성: 프로그램의 지역성
-> 이미 참조한 위치나 그 근처를 계속 참조한다.

이 2가지 근본 특성이 조합되어, 메모리 계층이 생긴다.

메모리 계층 피라미드

메모리 계층을 피라미드로 표현한 그림이다.

위로 갈수록 작고 빠르고 비싸다.
아래로 갈수록 크고 느리고 싸다.

(출처: 컴퓨터 시스템)

* CPU 레지스터
맨 위에는 레지스터가 있다. 겨우 몇십-몇백 바이트 정도밖에 저장할 수 없다. 프로세서가 즉각 접근할 수 있다. 겨우 1 클락 사이클 밖에 걸리지 않는다. 나노세컨드 (10억분의 1초) 수준에서 가져올 수 있다.

* CPU 캐시
CPU 안에는 SRAM을 사용한 캐시들이 있다. 이 캐시들도 계층별로 나뉜다. CPU 안에는 L1, 캐시와 L2, L3 캐시가 있다. 각각은 아래 계층의 메모리보다 빠르게 데이터를 가져올 수 있는 캐시로 이뤄진다. 실제 CPU를 보면 캐시가 많은 면적을 차지한다.

* 메인 메모리
DRAM으로 만들어진 메모리가 있다. 데이터를 가져오는 데 수백 클락 사이클 정도가 걸린다.

* 보조 기억 장치 (디스크)
크기는 매우 크지만, 매우 느린 디스크 저장 공간이 있다.
이 계층에 캐싱을 해두면, 외부 서버에 갔다오지 않고도 데이터를 불러올 수 있다.
메인 메모리 캐시와 다르게 앱을 껐다 켜도 유지가 된다.

* 원격 서버
같은 기기는 아니지만, 네트워크를 통해 연결된 원격 저장소가 있다. 흔히 HTTP를 통해 데이터를 가져오는 외부 서버다.
대체로 로컬 디바이스보다 훨씬 더 큰 용량이 크다. 대신 네트워크를 거쳐서 가져와야하므로 당연히 훨씬 더 느리다.

원격 서버에서 데이터를 가져오는 애플리케이션은, 대부분 디스크나 메인 메모리에 데이터를 캐싱한다. 원격 웹서버의 데이터를 가져오는 데는 시간이 오래걸리기 때문이다.

예를 들어, 웹 브라우저는 용량이 큰 이미지 등을 브라우저에 캐싱해 놓는다. 이런 캐시 관리 웹 브라우저와 HTTP의 중요한 기능 중 하나다.

캐시 (Cache)

여기서 잠깐, 캐시라는 용어에 대해 짚고 넘어가자.

'캐시'란 더 크고 느린 저장 공간에 있는 데이터를 임시 저장해두는 장소다.
캐시에 데이터를 저장해두는 것을 캐싱이라고 한다.

캐시는 현대 컴퓨팅 시스템 어디든지 있다. CPU 칩, 분산 파일 시스템, 월드 와이드 웹... 어디를 봐도 캐싱을 사용하지 않는 곳이 없다. 그만큼 중요하다.

사실, 이 캐싱은 우리 일상 생활에서도 정말 흔하다.

신발을 생각해보자.

자주 안 신는 신발은 신발장에 넣어두고, 자주 쓰는 신발은 항상 현관에 나와있다. 왜냐하면 필요할 때 빨리 신을 수 있으니까. '신발'이 데이터라면 '현관'은 캐시다.

(현관도 캐시다. 출처:한겨레)

흔히 CPU에 있는 캐시 메모리든, 웹 브라우저에 저장되는 캐시든 모두 '캐시'라고 퉁쳐서 부른다. 캐시가 특정한 저장 매체를 가리킨다는 느낌이 든다.

하지만 CPU의 캐시 메모리는 'CPU 안에서 캐시 역할을 하는 저장 장치'라는 뜻이다. '캐시' 자체는 특정한 하드웨어를 가리키지 않는다.

캐시는 더 보편적이고 추상적인 '역할'이다. 캐시라는 이름을 쓰기도 하고 안 쓰기도 하지만, 따져보면 결국 모든 계층이 캐시 역할을 한다.

메모리 계층의 본질이 바로 캐싱이다. 각 레벨의 저장 공간이 다음 레벨의 캐시 역할을 한다.

꼭 저 계층에 표시돼있지 않아도, 우리가 필요하면 얼마든지 중간에 임시 저장소를 만들 수 있다. 그것도 캐시다.

빨라지는 프로세서 속도에 맞춰서, 메모리 속도를 높이기 위해 컴퓨터 공학은 이 메모리 계층을 계속해서 발전시켜야했다. 캐시의 캐시, 그 캐시의 캐시를 만드는 방식으로.

대부분의 애플리케이션이 자체적으로 캐시를 활용한다. 이 캐시의 성능과 용량을 효과적인 수준으로 유지하기 위해서는 '캐시 관리'를 해야한다. '캐시 관리'도 프로그래머가 잘 알아야 하는 주제다.

(참고) 캐싱을 제공하고 돈 버는 회사: CDN

네트워크 상에서 캐싱은 중요하다. 인터넷 사용자들은 점점 더 용량이 큰 이미지, 영상, 게임을 많이 소비하고 있다. 이런 콘텐츠를 빠르고 효율적으로 제공하기 위해 캐싱은 필수다.

콘텐츠 소비자 근처에 캐시 역할을 하는 별도 서버가 필요하다. 거리가 짧으면 그만큼 더 빨리 데이터를 보내줄 수 있기 때문이다. 이런 캐시 서버를 제공하는 서비스를 Content Deilvery Network (CDN)이라고 한다. 잘 알려져있지 않지만 인터넷 인프라의 매우 중요한 축을 담당한다. 전세계 CDN 시장은 10조원이 넘는 크기다.

미국에 있는 유튜브 서버에서 한국에 있는 내 스마트폰으로 영상을 전송한다고 해보자. 이 영상 데이터는 해저 케이블을 타고 태평양을 건너 이런 저런 인프라를 거친다.

하지만 유튜브가 한국인이 자주 찾는 영상을 한국에 있는 서버에 복사해둔다면? 네트워크 사용량도 적고 훨씬 더 빠르게 전송해줄 수 있다. 네트워크 병목이나 원서버의 부하도 줄여준다. 글로벌 서비스를 하는 회사 입장에서는 큰 메리트다. CDN은 전세계에 데이터 센터를 확보하고, 서비스 회사들에게 이런 인프라를 빌려주는 대신 돈을 버는 구조다.

4. 캐시 관리

캐시의 관리는 실제로 캐시를 구현한 각 계층이 담당한다. 관리 방법 또한 구현에 따라서 다르다. 보편적인 몇 개 개념만 살펴보자.

캐시의 성능

만약에 찾는 데이터가 캐시에 있으면, 캐시 히트다. 캐시에서 바로 데이터를 읽어올 수 있다.
반대로 원하는 데이터가 캐시에 없으면 캐시 미스다. 아래 계층으로 넘어가 데이터를 찾아와야 한다.

전체 참조에서 캐시 히트의 비율을 적중률(Hit Ratio)라고 한다. (반대는 Miss Ratio.)

캐시의 성능은 주로 '적중률(Hit ratio)'로 표현한다.

캐시 성능과 용량의 트레이드 오프

캐시 용량이 크면 적중률이 올라간다. 캐싱을 해둘 수 있는 데이터가 많아지기 때문이다.

하지만 캐시는 접근 속도가 빠른 대신 용량이 작다고 했다. 어디까지나 임시 저장소이고, 원본 데이터의 일부만 들어간다.

캐시 용량이 다 차면, 필요없는 캐시를 지워준다.

다시 말해 캐시 데이터는 언제든지 삭제될 수 있다. 말 그대로 임시 보관소이기 때문.

캐시 교체 알고리즘

그렇다면 캐시 용량이 꽉 찼을 때 어떤 데이터부터 삭제해야할까?

캐시 교체(Cache Replacement) 혹은 캐시 퇴거(Cache eviction)라고 부르며, 이걸 결정하는 알고리즘이 캐시 교체 알고리즘이다.

각 메모리 계층별로 다양한 캐시 교체 알고리즘이 사용된다. 구현과 성능이 다 다르다.

하지만 결국 어떤 데이터를 더 우선순위에 둘 건지를 결정하는 알고리즘이라는 점에서는 다 비슷하다. 대표적인 3가지만 알아보자.

1. FIFO(First in First Out)

가장 먼저 들어간 데이터를 교체.
가장 간단하지만, 지역성을 바탕으로 앞으로 참조될 가능성을 고려하지 않아서 캐시 성능이 떨어진다.

2. LFU(Least Frequently Used)

가장 사용 횟수가 적은 데이터를 교체한다.
캐시에 저장을 했는데 '다른 데이터보다 참조하는 횟수가 낮다면, 앞으로도 자주 안 쓰이겠지.' 라고 가정한다.
최근에 저장한 데이터는 참조 횟수가 적기 때문에 교체 가능성이 높은데, 지역성 관점에서는 참조될 가능성이 높기 때문에 이 부분에서는 비효율이 발생할 수 있다.

3. LRU(Least Recently Used)

가장 오랫동안 사용되지 않은 데이터를 교체한다.
LFU와 미묘하게 다르다. 오랫동안 쓰지 않은 데이터가 앞으로도 안 쓰일거라고 가정한다.
시간적 지역성을 가장 잘 반영해서 성능이 높다.
LRU를 구현하기 위해서는 캐시에 저장된 데이터가 사용될 때마다 시간 순서를 기록해야 한다. 여기에 드는 오버헤드가 다른 알고리즘보다 크다.
애플리케이션에서 LRU 캐시를 구현할 때는 Hash Table과 Doubly Linked list를 같이 쓰는데, 코딩 테스트에 자주 나오는 문제이기도 하다.