[Redis] LFU, LRU 알고리즘

LRU

LRU (Least Recently Used) 알고리즘은 사용한지 가장 오래된 데이터부터 삭제하는 알고리즘.

• 모든 키를 대상으로 LRU 알고리즘을 적용하여 키 삭제 가능
• 만료 기간이 설정된 키를 대상으로 LRU 알고리즘 적용하여 키 삭제 가능

데이터를 Head~Tail로 쫘르륵 나열하고,
사용하면 해당 데이터를 Head에 옮긴다.
만약 메모리 최대 사용량까지 사용하고 있을 때, 새 데이터가 들어오면
기존 Tail에 있던 데이터가 삭제된다.

LFU

LFU(Least Frequently Used) 알고리즘은 사용 빈도수가 가장 적은 데이터부터 삭제하는 알고리즘으로, 최근에 사용한 데이터라도 자주 사용되지 않는다면 제거 대상이 가능하다.

• 모든 키를 대상으로 LFU 알고리즘 적용하여 키 삭제 가능
• 만료 기간이 설정된 키를 대상으로 LFU 알고리즘 적용하여 키 삭제 가능

각 데이터는 사용된 횟수를 카운트하는 노드에 연결되어있다.
데이터가 사용되면 해당 데이터 카운트가 하나 증가하고,
메모리 최대 사용량까지 사용하고 있을 경우 새로운 데이터가 들어오면 카운트가 가장 적은 데이터가 삭제된다.

참고

• https://chagokx2.tistory.com/102