Cache

[JoisFe]

• 캐시 히트, 캐시 미스, 캐시 매핑 이란 무엇일까요?
• 교체 정책 (교체 알고리즘) 종류와 각각 설명
• 캐싱을 하면 효율적인 경우와 그렇지 않은 경우 비교

[JoisFe]

Cache (캐시)

• 자주 사용하는 데이터나 값을 미리 복사해 놓는 임시 장소

• 캐시는 저장 공간이 작고 비싼 대신 성능이 빠름 (CPU의 메모리 I/O 도중 생기는 병목 현상 #32 참고)

Cache Hit

• 찾는 데이터가 Cache 메모리에 존재하는 경우

Cache Miss

• 찾는 데이터가 Cache 메모리에 존재하지 않는 경우

Cache Mapping

• cache 설정시 자주 사용하는 데이터를 cache에 설정해야 함
• Cache Hit를 높이기 위해 지역성 기반으로 설정을 함

1. Direct Mapping (직접 매핑)

• 메모리의 특정 블록을 특정 캐시에만 매핑

장점

• 단순하고 구현이 쉬움
• 점근속도 빠름

단점

• 교체자 자주 일어남 -> Hit Rate 가 낮음
• 특정 동일한 캐시 블록에 매핑되는 다른 메모리 블록을 번갈아 참조 시 블록 충돌이 발생 -> Hit Rate 낮음
• ==> 캐시 메모리가 대용량인 경우에 사용

2. Associative Mapping (연관 매핑)

• 순서를 일치시키지 않고 관련있는 cache와 메모리를 매핑하여 메모리의 컨텐츠가 cache의 어느 위치에도 올라갈 수 있음

장점

• Hit Rate 가 직접 매핑 보다 높음

단점

• 원하는 데이터를 찾는데 Direct Mapping 보다 오래 걸림

3. Set Associative Mapping (집합 연관 매핑)

• 연관 매핑 + 직접 매핑 방식
• 순서를 일치시키고, 저장 But 일정 그룹을 두어 그 그룹 내에서는 연관 매핑하는 방식

장단점

• 직접매핑, 연관매핑의 장점을 모두 가지나 각각의 장점보다는 효과가 떨어질 수 있음

Cache Locality (캐시 지역성)

1. Temporal Locality (시간적 지연성)

• 최근에 참조된 주소의 내용은 곧 다음에 다시 참조된다는 특성

2. Spatial Locality (공간적 지역성)

• 기억장치 내에 서로 인접하게 저장되어 있는 데이터들이 연속적으로 access 될 가능성이 높다는 특성

Q) 교체 정책(교체 알고리즘) 종류와 각각 설명

1. Random

• 교체될 페이지 랜덤으로 선정

장점

• 구현이 간단
• 교체될 페이지를 찾는 (계산) 오버헤드가 적게 발생됨

단점

• 사용 빈도나 시간에 대한 고려가 없음 -> 효율적이지 않음

2. FIFO (First In First Out)

• 캐시 내 오래 있었던 페이지 교체

장점

• 구현이 간단 (queue)
• 오래된 데이터를 제거하므로 새로운 데이터를 계속 받을 수 있음

단점

• 사용 빈도나 최근 사용 여부를 고려하지 않아 자주 사용하는 데이터 교체가 발생할 수 있음

3. LFU (Least Frequently Used)

• 사용 횟수가 가장 적은 페이지 교체

장점

• 사용 빈도가 적은 데이터 제거하므로 자주 사용하는 데이터가 캐시에 오래 유지됨

단점

• 빈도 계산을 위해서 추가적인 메모리 필요, 계산 비용 필요 (오버헤드 발생)
• 최근 사용되지 않는 데이터가 높은 빈도를 가질 경우 부적절한 교체 발생 가능

4. LRU (Least Recently Used)

• 가장 오랫동안 사용되지 않은 페이지 교체

장점

• 가장 오래 사용되지 않은 데이터 제거하므로 자주 사용되거나 최근에 사용된 데이터가 캐시에 유지됨

단점

• 구현이 복잡, 계산 비용 발생 (오버헤드)
• 캐시가 클수록 관리 오버헤드 증가

5. NUR (Not Used Recently)

• 최근 사용되지 않은 페이지 교체
  • 참조 비트와 수정 비트로 미사용 페이지 교체

장점

• LRU 에 비해 구현 간단, 계산 비용 낮음
• 최근 사용된 데이터오 그렇지 않은 데이터를 효율적으로 구분

단점

• 최근 사용 여부를 기반하므로 전체적인 사용 빈도를 고려하지 않아 전체적으로 자주 사용하는 페이지 교체가능성 존재

6. Optimal

• 향후 가장 참조되지 않을 페이지 교체

장점

• 교체할 데이터 미리 예측하므로 최적의 캐시 효율 제공

단점

• 미래를 예측해야하므로 현실적으로 구현이 불가능함

참고

• https://velog.io/@tyjk8997/%EC%BA%90%EC%8B%9C%EC%99%80-%EA%B6%81%EA%B8%88%ED%95%9C%EC%A0%90
• https://velog.io/@lob3767/%EC%BA%90%EC%8B%9C%EC%9D%98-%EC%A7%80%EC%97%AD%EC%84%B1Cache-Locality
• https://kimtaehyun98.tistory.com/48

[Tokwasp]

❓ 캐시 히트, 캐시 미스, 캐시 매핑 이란 무엇일까요?

🌱 [ Cache ] : 빠른 장치와 느린 장치의 속도 차이를 줄이기 위해 사용되는 임시 저장소

• 캐시 히트 : 캐시에서 원하는 데이터가 있을 경우
• 캐시 미스 : 데이터를 찾지 못하고 메모리에서 찾는 경우

🌱 [ 캐시의 지역성 ]

• 자주 사용 데이터를 기반으로 캐시를 설정 할수 있다. 자주 사용 하는 데이터의 근거를 지역성 이라고 한다.

[ 시간적 지역성 ] : 최근에 사용한 데이터를 다시 사용 하려는 특성

• for문 변수 i에 대해 계속된 접근

[ 공간적 지역성 ] : 최근에 사용한 데이터에 가까운 공간에 접근하는 특성

long total = 0;
long startTime = System.currentTimeMillis();
for(int i = 0; i < ROW_COUNT; i++){
     for(int j = 0; j < COL_COUNT; j++){
         total += arr[i][j];
     }
}

[ 실험 ] 연속 할당 된 arr[row][col], 연속 할당 되지 않은 arr[col][row] 조회 성능

total += arr[i][j]; / total += arr[j][i];

🌱 [ 캐시 매핑 ]

• 가상 메모리 주소를 메모리 관리 장치를 통해 번역하여 물리 주소로 변환 해준다.
• 물리 주소에 데이터가 있는지 확인 하는데 캐시에 데이터를 저장하는 방식에 따라 다르게 해석 한다.

[ 직접 매핑 ] : 메인 메모리와 동일한 배열로 매핑하는 방법

• 구현이 간단하고 탐색이 쉽다.
• 하지만 적중률이 낮다는 단점이 있다.

출처 : https://brightstarit.tistory.com/15

[ 연관 매핑 ] : 캐시 데이터는 메인 메모리 순서와는 관련이 없다.

• 관련된 캐시를 전부 뒤져서 태그가 같은 데이터를 확인 해야 한다.
• 복잡한 회로를 가지는 단점이 있지만 적중률이 높다.
  

🌱 [ 교체 정책 ]

FIFO ( First In First Out )

• 큐와 같이 가장 먼저 들어간 데이터를 교체
• 구현은 간단 하지만 교체가 잦을수 있다.

LFU ( Least Frequently Used )

• 사용 횟수가 가장 적은 데이터 교체
• 교체 대상이 여러개 일 경우 LRU를 따른다.
• 초반에 집중적으로 쓰이고 이후 쓰이지 않는 데이터가 존재 할수 있다.

LRU (Least Recently Used )

• 가장 오랫동안 사용되지 않은 데이터 교체
• 가장 구현이 간단하고 보편적이다.

[ LRU ]

• 새로 캐싱 되거나 Hit 되는 데이터는 Tail로 가장 오래 사용 하지 않은 데이터는 head로 보낸다.
• 캐시 용량이 부족하면 head를 지우고 tail에 새로운 캐시를 붙인다.

[jay200333]

❓ 캐시 히트, 캐시 미스, 캐시 매핑이란 무엇일까요?

✅ 답변
캐시 : 빠른 장치와 느린 장치 사이의 속도를 줄이기 위해 사용되는 임시 저장소

😁 장점

• 빠른 응답 속도 : 캐시된 데이터를 사용하면 원래 데이터를 가져오는 것보다 훨씬 빠르게 응답 가능
• 효율적인 자원 사용 : 캐시를 사용하여 반복적으로 불러오는 데이터를 줄일 수 있어, 시스템 자원의 효율성을 높일 수 있다.
• 높은 가용성 : 캐시는 데이터를 저장하고 빠르게 반환하므로, 시스템 장애 발생 시 임시적으로 데이터를 대체할 수 있어 가용성이 높아짐

😫 단점

• 메모리 사용량 : 캐시된 데이터를 메모리에 저장해야 하므로, 메모리 사용량이 높아짐
• 데이터 불일치 : 원본 데이터가 변경되면 캐시된 데이터와 일치하지 않을 수 있다. 업데이트 해야함
• 적중률 문제 : 캐시의 적중률이 낮으면 원래 데이터를 가져오는데 시간이 걸려, 성능 저하 발생할 수 있음

📌 특징

• 데이터 접근 시간 단축, 데이터를 재계산하는 시간 절약
• 캐시 설정 시 자주 사용되는 데이터를 기준으로 하는데 이 때 지역성의 원리를 따름
  • 시간 지역성 : 최근 사용한 데이터에 다시 접근하는 경향
  • 공간 지역성 : 최근 접근한 데이터 주변 공간에 접근하는 경향

---

캐시 히트 : 캐시에서 원하는 데이터를 찾음(hit)

캐시 미스 : 캐시에서 원하는 데이터를 찾지 못해 메모리에서 데이터를 가져와야 함

캐시 매핑

• 직접 매핑
  • 메모리의 특정 블록이 특정 캐시 라인에만 매핑
  • 탐색이 빠르지만 스와핑이 자주 발생
• 연관 매핑
  • 메모리의 어떤 내용도 캐시의 어떤 위치에도 매핑 가능
  • 스와핑이 적지만 캐시의 모든 블록을 탐색해야 하므로 속도가 느림
• 집합 연관 매핑
  • 직접 매핑의 탐색 효율성과 연관 매핑의 스와핑 감소 장점을 결합
  • 집합을 형성하고 해당 집합 내에는 어떠한 블록도 들어올 수 있음(메모리 블록 그룹이 하나의 집합을 공유)

---

❓ 교체 정책 종류

✅ 답변

FIFO

• Queue와 같이 가장 먼저 들어간 데이터를 교체
• 구현은 간단하지만 교체가 잦을 수 있음

LFU(Least Frequently Used) [횟수]

• 사용 횟수가 가장 적은 데이터 교체
• 교체 대상이 여럿이면 LRU를 따름
• 최근에 적재된 데이터가 교체될 가능성이 있음
• 초반에 집중적으로 쓰이고 이후 쓰이지 않는 데이터가 존재할 수 있음

LRU(Least Recently Used) [시간]

• 가장 오랫동안 사용되지 않은 데이터 교체
• 가장 구현이 간단하고 보편적인 방식

[LRU 동작 방식]
-> 이중연결리스트

• 새로 캐싱되거나 Hit 하는 데이터는 tail로
• 가장 오래 사용되지 않은 데이터는 head로
  • 새로 캐싱되거나 Hit 되는 데이터가 tail로 계속 이동하기 때문에 가장 오래 사용되지 않은 데이터는 head가 됨
• 캐시 용량이 부족하면 head의 캐시를 지우고 tail에 새로운 캐시를 붙여서 저장
• 새로 캐싱되거나 head의 데이터가 삭제되는 경우 시간복잡도 O(1)

Hit 되는 데이터를 탐색해야 하는 경우 O(n)의 시간복잡도 발생

이중연결리스트에 해시맵을 추가해서 문제점 보완 가능

딕셔너리에서 Key 들이 이중연결리스트의 각 노드들, 즉 캐시데이터를 가리키게 한다면 탐색 시 O(1) 의 시간복잡도로 개선 가능

---

❓ 캐싱을 하면 효율적인 경우와 비효율적인 경우

✅ 답변

캐싱 : 데이터를 미리 저장하여 나중에 더 빠르게 접근할 수 있도록 하는 기술

효율적인 경우

• 빈번히 접근하는 데이터를 사용하는 경우
• 비용이 큰 데이터 조회하는 경우(데이터 생성 비용이 높은 경우)
• 상대적으로 불변하는 데이터를 사용하는 경우
• 네트워크 지연을 줄이고 싶은 경우(로컬 캐싱을 통해 접근 속도 높임)

비효율적인 경우

• 캐싱된 데이터가 적중률이 낮은 경우
• 원래 데이터 소스가 무거운 경우
• 데이터가 자주 변경되는 경우
• 데이터가 매 요청마다 갱신될 필요가 없는 경우
• 데이터가 자주 접근되고 한 번 이상 필요한 경우