[WEEK07] 정글 5기 - 캐시(발표를 위한 정리)

캐시	- 캐시는 데이터나 값을 미리 복사해 놓은 임시 장소이다. - 캐시에 데이터를 미리 복사해 놓으면, 계산이나 접근 시간 없이 더 빠른 속도로 데이터에 접근할 수 있다.
캐시 교체 정책	- 캐시는 모든 데이터를 담을 수 없기 떄문에, 캐시의 크기가 제한되고 그에 따라 캐시가 대체되어야 한다. - 어떤 파일을 버리고 새로운 캐시를 저장할 것인 결정하는 것이 캐시 교체 알고리즘이다.

 

캐시 교체 정책

Random	- 교체될 데이터 임의로 설정 - 오버헤드가 적다.
FIFO	- First-In, First-Out - 가장 먼저 캐시에 저장된 항목을 삭제한다. - 자주 사용되는 데이터가 삭제될 수 있다.
LFU	- Least Frequently Used - 사용 횟수가 가장 적은 데이터 교체 - 최근에 저장된 데이터가 교체될 우려가 있다.
LRU	- Least Recently Used - 가장 오랫동안 사용되지 않은 페이지 교체 - time stamping에 의한 오버헤드 존재
MRU	- Most Recently Used - 가장 최근에 사용된 항목을 삭제

 

LRU(Least Recently Used)
- 많은 운영체제가 사용하고 있는 알고리즘으로 가장 좋은 캐시 교체 알고리즘으로 평가되고 있다. - LRU를 해석하면 "가장 최근에 사용된" 이라는 뜻으로 "메모리에 남아 있는 캐시 중 가장 오래동안 사용되지 않은 캐시를 새로운 캐시로 교체" 한다. - LRU를 구현하기 위해서는 n개의 크기를 가지는 DoublyLinkedList(or Queue)와 이를 추적하기 위한 n의 크기를 가지는 HashMap이 필요하다.
동작 방식	Doubly LinkedList - 데이터가 새로 추가되면 Head에 추가되고, Tail에 가까울수록 오래 사용되지 않은 캐시이다. - 크기가 부족하면 Tail의 캐시를 지우고 Head에 새로운 캐시를 붙여 저장한다. - LRU에서는 맨 앞에 있는 캐시를 지우고, 맨 뒤에 추가하는 동작만 구현되면 되므로 탐색에 대한 시간 복잡도가 O(1)이 된다. HashMap - HashMap 자체는 Key와 Value로 구성되어 캐시와 달리 교체에 대한 별도의 정책이 없다. - 해싱(Hashing)을 사용하기 떄문에 데이터의 검색이 빠르다. - 키가 중복저장되지 않으므로, LRU에서 실제 데이터를 캐시에서 불러오는데 시간 복잡도가 O(1)이 된다.
Cache Hit & Cache Miss	- Cache Hit : 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우 - Cache Miss : 참조하고자 하는 메모리가 캐시에 존재하지 않을 경우

 

LFU(Least Frequently Used)

- LFU를 번역하면 "가장 자주 사용되지 않음" 이라는 뜻을 가진다. - 해석 그래로 "가장 적은 횟수를 참조하는 페이지를 교체한다" - Queue로 구현 가능하며, 각 캐시마다 참조횟수를 알아야 하므로 각 캐시마다 카운터(counter)가 필요하다.

 

캐시 동기화

캐시 읽기 전략

Cache Aside	1. 캐시에 데이터가 있는지 확인 2. 데이터가 존재하면 (Cache Hit) 해당 캐시 데이터를 반환 3. 데이터가 존재하지 않으면 (Cache Miss) 애플리케이션에서 DB에 데이터 요청 후 캐시에 저장하고 데이터를 반환 - 애플리케이션에서 가장 일반적으로 사용되는 캐시 전략 - 주로 읽기 작업이 많은 애플리케이션에 적합하다. - 캐시가 최신 데이터를 가지고 있는지 동기화가 중요하다.
Read Through	1. 캐시에 데이터 요청 2. 캐시는 데이터가 있으면 (Cache Hit) 바로 반환 3. 데이터가 없다는 (Cache Miss) 캐시가 DB에서 데이터를 조회한 후에 캐시에 저장 후 반환 - Cache Aside와 비슷하지만 데이터 동기화를 라이브러리 또는 캐시 제공자에게 위임하는 방식이라는 차이점
Thundering Herd	- 캐시 읽기 전략에서는 공통적으로 캐시 확인 → DB 확인 순서로 이어지는데 이 과정에서 캐시에 데이터가 있으면 DB 확인을 생략하는 것으로 성능을 향상시킨다. - 캐시에 데이터를 미리 세팅해두는 Cache Warm up 작업을 하거나 첫 요청이 캐시이 캐시 갱신될 때까지 기다린 후에 이후 요청은 전부 캐시에서 반환하게 할 수 있다 - Cache Warm up 작업을 할 때 어떤 데이터를 넣느냐에 따라 마찬가지로 Cache Miss가 발생할 수 있기 떄문에 자주 들어올만한 데이터의 예측이 중요하다.

 

캐시 쓰기 전략

Write Around	- 캐시를 갱신하지 않음 1. 데이터 추가/업데이트 요청이 들어오면 DB에만 데이터 반영 2. 쓰기 작업에서 캐시를 건들지 않고 읽기 작업 시 Cache Miss가 발생하면 업데이트 - Cache가 갱신된지 얼마 안된 경우에는 캐시 Expire 처리 되기 전까지 계속 DB와 다른 데이터를 갖고 있다는 단점이 있다. - 만약 업데이트 이후 바로 조회되지 않을 것이라는 확신이 있다면 캐시를 초기화하여 Cache Miss를 유도하는 방법으로 보완할 수 있다.
Write Through	- 캐시를 바로 갱신 1. 캐시에 데이터를 추가하거나 업데이트 2. 캐시가 DB에 동기식으로 데이터 갱신 3. 캐시 데이터를 반환 - 동기화까지 완료한 후에 데이터를 반환하기 때문에 캐시를 항상 최신 상태로 유지할 수 있다는 장점 - 캐시 및 DB를 동기식으로 갱신한 후에 최종 데이터 반환이 발생하기 때문에 전반적으로 느려질 수 있다.
Write Back (Write Behind)	- 캐시를 모아서 나중에 갱신 1. 캐시에 데이터를 추가하거나 업데이트 2. 캐시 데이터 반환 3. 캐시에 있던 데이터를 이후에 별도 서비스(이벤트 큐 등)를 통해 DB에 업데이트 - 캐시와 DB 동기화를 비동기로 하는 방법이며 동기화 과정이 생략되기 때문에 쓰기 작업이 많은 경우에 적합 - 캐시에서 일정 시간 또는 일정량의 데이터를 모아놓았다가 한번에 DB에 업데이트하기 때문에 쓰기 비용을 절약할 수 있다. - 다른 캐시 전략에 비해 구현하기 복잡한 편이며 캐시에서 DB로 데이터를 업데이트 하기 전에 장애 발생 시 데이터 유실
Refresh Ahead	- 자주 사용되는 데이터를 캐시 만료 전에 미리 TTL (Expire time)을 갱신한다. - 캐시 미스 발생을 최소화할 수 있지만 Warm Up 작업과 마찬가지로 자주 사용되는 데이터를 잘 예측해야 한다.

 

참조

https://hstory0208.tistory.com/entry/%EC%BA%90%EC%8B%9C-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-LRU-LFU