3.4. Cache - 3.4.2 LFU Cache

CS - 3. Common Algorithms - 3.4. Cache - 3.4.2 LFU Cache

 

💡LFU Cache is a data structure that stores key-value pairs. It has a fixed size and when it is full, it removes the least frequently used key-value pair. It is a variation of the LRU Cache and is used in many applications such as caching web pages, caching database queries, and caching images.

LFU 캐시는 키-값 쌍을 저장하는 데이터 구조입니다. 크기가 고정되어 있으며, 크기가 가득 차면 사용 빈도가 가장 낮은 키-값 쌍을 제거합니다. LRU 캐시의 변형으로 웹 페이지 캐싱, 데이터베이스 쿼리 캐싱, 이미지 캐싱 등 많은 애플리케이션에서 사용됩니다.

 

LFU(Least Frequently Used) 캐시는 이름에서 알 수 있듯이 가장 적게 사용된 항목을 캐시에서 제거하는 전략을 사용하는 캐시입니다. 

이는 캐시의 크기가 제한되어 있고, 새로운 항목을 추가해야 할 때 공간이 부족

이 경우, LFU 캐시는 가장 적게 액세스된 항목을 제거하여 공간을 확보합니다.

 

In Python

LFU 캐시를 구현하는 방법은 다양합니다만, 이 글에서는 해시맵과 우선순위 큐를 사용하는 방법을 소개하겠습니다.

import collections
import heapq

class LFUCache:

    def __init__(self, capacity):
        self.capacity = capacity
        self.val_map = collections.defaultdict(int) # 값과 빈도
        self.freq_map = collections.defaultdict(list) # 값과 빈도 리스트
        self.min_freq = 0
        self.size = 0

    def get(self, key):
        if key in self.val_map:
            self.update(key)
            return self.val_map[key][0]
        else:
            return -1

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.val_map:
            self.update(key, value)
        else:
            if self.size == self.capacity:
                to_remove = self.freq_map[self.min_freq].pop(0)
                del self.val_map[to_remove]
                self.size -= 1
            self.val_map[key] = [value, 1]
            self.freq_map[1].append(key)
            self.min_freq = 1
            self.size += 1

    def update(self, key, new_val=None):
        value, freq = self.val_map[key]
        if new_val != None:
            value = new_val
        self.freq_map[freq].remove(key)
        if not self.freq_map[freq]:
            del self.freq_map[freq]
            if self.min_freq == freq:
                self.min_freq += 1
        self.val_map[key] = [value, freq+1]
        self.freq_map[freq+1].append(key)

이런식으로 LFU 캐쉬를 구성해볼수 있습니다.

 

정말 간단한 예시를 보여드리겠습니다.

예시 1

LFU 캐쉬의 용량을 2로 설정하였기에

1='A', 2='B', 3='C', 4='D'를 차례대로 넣으면 

나중에 key 1로 부르면 -1 로 없음을 보여줍니다.

근데 이 예시에는 최신의 데이터가 들어와서 오래된 것들을 제거하고 그자리에 최신의 데이터를 저장한 것인지, 즉 LRU 인지 LFU 인지 판단하기 어렵습니다.

 

예시 2

그래서 1='A' 를 가장 처음 많이 넣은뒤에 2='B', 3, 4 를 한번씩 넣고 1이 삭제 되는지 보면 됩니다.

결과값은 가장 다수인 1='A'는 남아있고 2='B'는 제거, 3,4 가 저장되어 있습니다.

 

 

활용

LFU 캐시는 특정 항목의 사용 빈도가 높은 경우에 유용하게 사용될 수 있습니다.

즉, 일부 항목이 자주 액세스되고, 그 항목들이 캐시에서 제거되는 것이 성능 저하를 초래할 수 있는 상황에서 LFU 캐시는 큰 도움이 됩니다.

 

1. 웹 페이지 캐시

- 특정 웹 페이지에 대한 요청이 빈번할 경우,

LFU 캐시 를 사용해 웹 페이지를 캐시에 유지, 빈도가 낮은 다른 웹페이지를 캐시에서 제거.

이런식으로 자주 액세스하는 웹 페이지 로드 시간을 줄입니다.

 

2. DB 쿼리 결과 캐싱

- 일부 쿼리의 결과가 자주 요청되는 경우,

쿼리 결과를 캐싱함으로써 빠르게 제공.

 

3.ML 모델 예측 결과 캐싱

- ML 모델에서 동일한 입력에 대한 예측을 자주 수행할 경우,

예측 결과를 캐싱하여 다시 계산하는 시간을 절약함.

 

 

문제점은

"Recently" 최근성을 고려하지 않는다는 점입니다.

3.4.1에서 LRU 에 대해서 다뤘습니다. LRU 캐시는 가장 최근에 사용된 캐시를 저장하는 알고리즘입니다. 

이에반해 3.4.2 LFU 는 예전에 자주 사용되었지만 현재는 거의 사용하지 않는 항목이 LFU 캐시에 계속 유지될 수 있는 단점이 있습니다.

 

이를 보완하기위해 LRU과 LFU를 결합한 LRU-LFU 캐시 전략을 사용하기도 합니다.

(  LRU-LFU 캐시 전략은 추후에 다루기)