캐시

1. 캐시

---

캐시

• 컴퓨터를 구성하는 메모리는 다양한 종류가 있습니다.
• 대표적으로 RAM, SSD, HDD가 있습니다.
• SSD와 RAM의 차이는 무엇일까요? 간단하게 용량과 거리라고 생각하면 됩니다.
• RAM에 저장된 파일은 빠르게 탐색할 수 있지만 용량이 적습니다.
• SSD에는 파일을 많이 저장할 수 있지만 램보다는 느린 속도를 보입니다.
• 캐시메모리 역시 메모리의 종류 중 하나입니다. 정말 빠르지만 용량이 한정적이므로 관리가 중요합니다.

지역성

• 시간적 지역성: 한 번 접근한 데이터는 금방 또 접근할 가능성이 높다.
• 공간적 지역성: 한 번 접근한 데이터의 근처를 또 접근할 가능성이 높다.

캐시의 동작

• 앞서말한 지역성을 바탕으로 자주 쓰는 데이터를 빨리 꺼낼 수 있게 합니다.
• 캐시는 세 부분으로 나뉘는데, 오프셋, 인덱스, 태그로 이루어져있습니다.
• 속도와 용량에서 최대한 타협하다보니 인덱싱을 하는 데에 많은 기술이 녹아있습니다.
• 가령 32비트의 메모리 공간이 존재한다면 10비트는 인덱스에 사용됩니다.
• 하지만 10비트를 사용하더라도 인덱스가 중복될 위험이 있으며, 태그비트를 추가로 사용합니다.
• 데이터를 저장할 때 태그비트부터 확인한 다음 인덱스에 접근시켜 중복의 위험을 줄입니다.
• 최대한 빠르게, 하지만 너무 용량이 작아 쓸모없어지지는 않게 타협하는 것이 캐시의 핵심입니다.

캐시의 교체

• 자주 사용할 데이터를 예측하는 일은 어렵습니다.
• 하지만 자주 사용할 데이터만 재사용하고 나머지는 그때그때 탐색하는 것이 효율적입니다.
• 자주 사용할 데이터를 거르기 위해 주로 LRU방식을 많이 사용합니다.

2. LRU 캐시

---

LRU 캐시의 동작방식

• Least Recently Used 의 약자입니다.
• 우선순위를 두고 최근 접근한 데이터는 가장 높은 우선순위로 잔류합니다.
• 메모리가 꽉차면 잔류 우선순위가 가장 낮은 데이터부터 제거됩니다.

HashMap

• 해시맵은 자료의 추가, 삭제와 탐색속도가 O(1)로 빠른 자료구조입니다.
• 연결리스트는 탐색속도가 O(N)으로 해시맵이 LRU알고리즘에 어울리는 자료구조입니다.