3.4. Cache - 3.4.1 LRU Cache

CS - 3. Common Algorithms - 3.4. Cache - 3.4.1 LRU Cache

 

 

3.4. Cache

 

💡Cache algorithms are used to manage the cache memory of a computer. Cache memory is a small amount of memory that is used to store data that is frequently accessed. This allows the computer to access the data faster than if it had to go to the main memory. Cache algorithms are used to determine which data should be stored in the cache memory and which data should be removed from the cache memory.

캐시 알고리즘은 컴퓨터의 캐시 메모리를 관리하는 데 사용됩니다. 캐시 메모리는 자주 액세스하는 데이터를 저장하는 데 사용되는 소량의 메모리입니다. 이를 통해 컴퓨터는 주 메모리로 이동해야 하는 경우보다 더 빠르게 데이터에 액세스할 수 있습니다. 캐시 알고리즘은 캐시 메모리에 저장해야 할 데이터와 캐시 메모리에서 제거해야 할 데이터를 결정하는 데 사용됩니다.

 

 

 

3.4. Cache - 3.4.1 LRU Cache

 

💡LRU cache is a cache that evicts the least recently used item first. It is a very common cache algorithm. It is used in many places, such as in the browser cache, the database cache, and the cache of the operating system.

LRU 캐시는 최근에 가장 적게 사용된 항목을 먼저 꺼내는 캐시입니다. 매우 일반적인 캐시 알고리즘입니다. 브라우저 캐시, 데이터베이스 캐시, 운영 체제의 캐시 등 여러 곳에서 사용됩니다.

 

 

LRU 은 " Least Recently Used"의 약자입니다.

 

LRU Cache는 "가장 최근에 사용되지 않은 데이터를 가장 먼저 제거하는" 캐시 알고리즘 입니다.

캐시는 데이터를 더 빠르게 접근할 수 있는 임시 저장소이며, LRU Cache는 캐시의 공간을 제한적으로 사용하면서도 가장 자주 사용되는 데이터에 대한 빠른 접근을 보장합니다.

 

LRU Cache의 작동 방식은 이렇습니다.

1. 데이터를 읽거나 쓸 때마다 해당 데이터를 캐시에 저장합니다.

이때 캐시는 고정된 크기를 가지고 있습니다.

2. 캐시가 가득 찬상태에서 새로운 데이터를 추가하려고 하면, 가장 오래 전에 사용된 데이터를 제거합니다.

반대로, 이미 캐시에 존재하는 데이터에 접근하면 해당 데이터를 가장 최근에 사용된 것으로 갱신합니다.

 

이런 과정을 통해 가장 최근에 사용되지 않은 데이터는 제거하고, 가장 최근에 사용된 데이터는 캐시에남게 됩니다.

 

 

In Python

파이썬에서 LRU Cache 를 구현하기 위해서는 collections 모듈의 OrderedDict를 사용할 수 있습니다.

OrderedDict는 항목이 추가된 순서를 기억합니다. 이 추가된 순서를 기억하는것이 LRU 캐쉬와 비슷한 특성입니다.

 

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        else:
            if len(self.cache) >= self.capacity:
                self.cache.popitem(last=False)
        self.cache[key] = value

위 코드에서 get() 함수는  key를 사용해 값을 검색하고, put() 함수는 새 값을 저장합니다.

만약 캐시가 이미 가득 찼다면, 가장 오래된 항목을 제거하고 새 항목을 저장합니다.

 

위의 함수는 정말 LRUCache 의 구현이고

 

참고)

OrderedDict의 활용을 알아보겠습니다. 

collections 모듈의 OrderedDict는 일반적인 딕셔너리는 키의 순서를 유지 하지 않지만, OrderedDict는 이를 가능하게 해서입니다.

위 코드를 실행시키면 항목들이 추가된 순서대로 출력됩니다.

 

 

 

활용

 

주로 LRU Cache 는 주로 DB나 웹페이지 캐싱에 활용됩니다.

데이터 접근 솏도를 향상시키고, 디스크나 네트워크 I/O을 줄여 시스템의 전반적인 성능을 향상시키는데 도움이 됩니다.

또, 빈번하게 접근하는 데이터를 메모리에 유지하여 응용 프로그램의 실행 속도를 높이는 데 사용됩니다.

 

예시로

웹 요청에 대한 응답을 캐싱하여 빠른 응답 시간을 제공하는 웹 서버를 구현한다고 해봅시다.

class WebServer:
    def __init__(self):
        self.cache = LRUCache(5)  # 최대 5개의 요청을 저장

    def handle_request(self, request):
        response = self.cache.get(request)
        if response == -1:  # 캐시에 응답이 없으면 새로 요청
            response = self.process_request(request)
            self.cache.put(request, response)  # 캐시에 응답을 저장
        return response

    def process_request(self, request):
        # 실제 요청을 처리하는 코드
        # 지금 이 예시에서는 단순히 요청을 반환하도록 합니다.
        return request

 

클래스는 요청을 처리하는 handle_request 메서드를 가지고 있습니다.

handle_request는 LRUCache에 요청에 대한 응답을 검색합니다.

캐시에 응답이 없으면 요청을 처리하고 캐시에 응답을 저장합니다.

따라서 동일한 요청이 재차 들어올 경우 캐싱한 상태이기 떄문에 빠르게 응답을 제공할 수 있습니다.