[Programmers] 캐시 알고리즘이란 + [1차] 캐시 - JavaScript

Joosi_Cool·2023년 2월 10일

1차 캐시 2단계 JavaScript LRU알고리즘 programmers 캐시

Programmers

목록 보기

17/98

캐시란?

이 문제를 풀기 위해서는 기본적으로 캐시에 대한 개념을 알아야한다.
이에 대한 모든 것을 알기엔 너무 무겁기 때문에 이번 블로깅에서는 캐시와 관련된 JS문제를 풀기 위해 알아야 하는 개념에 대해 간단하게 알아보도록 하자.

캐시란, 요청에 대한 응답의 복사본을 한 곳에 저장해놓고 있다가 이에 대한 요청이 들어오면, 서버에 요청하지 않고 저장해둔 복사본을 보내는 방식이다.

한곳에 두고 저장해둔다라.... 왜?

백엔드에서 많이 쓰는 방식인데, 보통 원본 데이터가 있는 원본서버라는 곳이 존재한다. 이 브라우저에서 데이터에 대한 요청이 있을 시 이 원본서버에 가서 데이터를 가져온다. 하지만 서버로 가는 행위는 우리가 생각하는 것보다 꽤 많은 시간과 자원이 든다. 매 요청시마다 이를 원본서버에서 가져오는 것은 비효율적이다 라는 말이다. 그래서 나온 것이 캐시 이다.
캐시는 원본서버로 가기 전에 캐시 메모리 라는 공간을 파두고, 여기서 데이터를 찾아준다. 이 덕분에 사용자들은 더 빠르게 데이터를 받아 볼 수 있다.

그렇다면 이런 생각이 들것이다. 그러면 그냥 원본서버 쓰지말고, 캐시에다가 데이터를 전부 몰아놓고 쓰면 되는거 아니야? 이 캐시라는 것의 치명적인 단점이 한정적인 크기 이다.
그렇다면 이 한정적인 크기 안에 어떤 데이터를 넣어야 효율적으로 동작할 수 있을지, 이것에 핵심이 된다. 이때 나온것이 캐시 알고리즘 이다.

캐시 알고리즘

캐시 알고리즘은 캐시 교체 정책이라고도 불린다. 이 알고리즘 종류에는 LRU, LFU, FIFO 등 여러개가 있지만 이번 블로깅에서는 LRU에 대해 다루어 볼 것이다. 실제로 LRU가 가장 많이 쓰인다.

LRU(Least Recently Used)

LRU란, Least Recently Used의 줄임말로 가장 덜 최근꺼를 사용한다는 말이다. 이게 무슨 말인가? 캐시는 크기가 한정적이기 때문에, 데이터가 들어왔을때 크기가 남아있으면 그냥 넣으면 된다. 하지만 새로운 데이터가 들어왔는데, 공간이 꽉 찼다면? 어떤 걸 제거해줘야 한다. 이때 가장 덜 최근꺼를 삭제시킨다는 말이다.

LRU는 캐시메모리에서 사용된지 가장 오래된 데이터를 지우는 방식이다.
이는 구현이 쉽고, 가장 보편적인 방법이다.
여기서 하나 알아야 하는 용어가 있다. 바로 HIT 과 MISS 이다.
1) HIT은 캐시 메모리 안에 있는 데이터를 요청시에 이를 부르는 말이다.
2) MISS는 캐시 메모리 안에 없는 데이터를 요청시에 이를 부르는 말이다.

알고리즘 구현 방법

( 여기서 tail은 캐시 메모리에 마지막 부분을 말하며, 이쪽에 있을수록 최근것에 해당한다. )

데이터 요청이 들어온다.

캐시에 없는 새로운 데이터이고, 캐시에 공간이 비어져있다면 원본서버에서 데이터를 가져오면서 이를 캐시에 저장해준다. ( MISS )

데이터가 캐시에 있는 데이터라면 캐시에서 이를 보내주고, 데이터를 가장 tail로 보낸다. ( HIT )

캐시에 없는 새로운 데이터이면서, 공간이 꽉 차있다면 가장 마지막에 쓰인 데이터를 지우고, 방금 요청한 캐시를 tail에 둔다. ( MISS )

JS 알고리즘 코드

그렇다면 이를 이용하여 알고리즘 구현을 직접해보자

const cache_size = 5;
const cache_memory = new Array(cache_size).fill(null);


const request = [3,4,6,7,1,3,5,2,1];


request.forEach((element)=>{
    const idx  = cache_memory.indexOf(element);
    //캐시에 없는데이터라면
    if(idx === -1){
        // 공간이 비어져있다면 데이터를 캐시에 저장
        if(cache_memory.length<cache_size){
            cache_memory.push(element);
        }
        else{
            //꽉 차있다면 제일 앞에 있는거 빼주고 데이터 캐시에 저장
            cache_memory.shift();
            cache_memory.push(element);
        }
    }
    //캐시에 있는 데이터라면, 그 부분을 tail로 이동
    else{
        cache_memory.splice(idx,1);
        cache_memory.push(element);  
    }
})

자 이제 문제를 풀 준비가 어느정도 됐을 것이라고 생각한다. 이제 문제를 한번 봐보자.

문제설명

설계 과정

설계는 앞에 했던 LRU 설계 과정과 동일하지만 몇개 추가했다.
HIT일때, answer+=1;
MISS일때, answer+=5;
또한 크기가 0일 시에 앞에 하나를 저장하고 있어서 Seoul. Seoul 이러식으로 된다면 6으로 출력되는 예외가 있었다. 그래서 이 부분만 예외처리를 진행했다.

풀이 코드

function solution(cacheSize, cities) {
    var answer = 0;
    const cache_size = cacheSize;
    const cache_memory = new Array(cache_size).fill(null);
    if(cacheSize===0){
        return cities.length*5;
    }
    cities.forEach((element)=>{
        element = element.toLowerCase();
    const idx  = cache_memory.indexOf(element);
    //캐시에 없는데이터라면(HIT)
    if(idx === -1){
        answer+=5;
        // 공간이 비어져있다면 데이터를 캐시에 저장
        if(cache_memory.length<cache_size){
            cache_memory.push(element);
        }
        else{
            //꽉 차있다면 제일 앞에 있는거 빼주고 데이터 캐시에 저장
            cache_memory.shift();
            cache_memory.push(element);
        }
    }
    //캐시에 있는 데이터라면, 그 부분을 tail로 이동 (MISS)
    else{
        answer+=1;
        cache_memory.splice(idx,1);
        cache_memory.push(element);  
    }
})  
    return answer;
}