[CS] LRU캐시 개념, 구현 방법

캐시의 개념

---

캐시(Cache)는 자료나 데이터를 임시 저장하는 공간을 가리킵니다. 메모리 접근에 드는 시간을 절약하고자 메모리 데이터의 일부를 속도가 빠른 캐시 메모리에 저장합니다.

캐시에 있는 데이터는 주메모리에 접근하는 시간을 절약할 수 있으므로 성능 향상을 가져옵니다. 하지만 공간이 한정적이기 때문에 자주 사용하는 데이터를 캐시에 넣는 것이 성능에 중요합니다. 이렇게 어떻게 하면 제일 효율적인 방법으로 캐시의 데이터를 넣고 뺄지 관리하는 데는 FIFO, LFU, LRU  등의 알고리즘이 있습니다.

 

캐시 hit와 캐시 miss

---

CPU가 데이터를 요청했을 때, 캐시 메모리가 해당 데이터를 가지고 있다면 캐시 hit라고 부르고, 데이터가 없어서 주메모리(RAM)에서 가져와야 한다면 캐시 miss라고 부릅니다. 이때 전체 캐시 적중률은 캐시 hit 횟수 / 전체 요청 횟수로 계산됩니다. 캐시 적중률이 높을수록 데이터에 더 빠르게 접근할 수 있어 성능이 향상됩니다. 따라서 위에 설명드린 알고리즘들은 결국 캐시 적중률을 높이기 위한 방법들입니다.

 

LRU 알고리즘

---

LRU는 Least Recently Used 의 약자로서 캐시 메모리에 데이터를  저장할 때 캐시가 꽉 차면 가장 오래 사용하지 않은 데이터를 삭제(교체)하는 기법입니다. 가장 최근에 사용되지 않은 데이터는 이후에도 사용하지 않을 가능성이 크다는 전제를 가지고 있습니다. LRU 알고리즘을 구현하기 위해서는 저장된 캐시 데이터 중에 가장 최근에 사용되지 않은 데이터가 무엇인가를 알고 있어야 합니다.

 

LRU 알고리즘 구현방법 1 : 이중 연결리스트(Doubly linked list) 활용

---

연결리스트 자료구조를 활용하면 리스트에서 노드를 O(1)의 시간으로 삽입, 삭제할 수 있습니다. 찾고자 하는 데이터가 캐시에 존재하는지 확인하기 위해 연결 리스트를 순회해서 데이터를 검색하는데, 다음 3가지 경우가 있습니다.

1) 캐시에 찾고자 하는 데이터가 있는 상황
해당 데이터를 연결리스트의 처음 위치로 이동합니다. 

2) 캐시에 찾고자 하는 데이터가 없고, 캐시 메모리가 꽉 차지 않은 상황
데이터를 리스트에 삽입하면 됩니다.

3) 데이터가 없고 캐시 메모리가 꽉 찬 상황
리스트의 마지막 원소를 제거한 뒤에 찾고자 하는 데이터를 리스트에 삽입합니다. 이때 데이터는 메모리에서 찾은 후 삽입하게 됩니다.

이제 각 데이터가 0 ~ 7번 주소에 들어있고, LRU 캐시를 위한 연결리스트의 길이가 3인 상황을 가정해보겠습니다. 
1 -> 3 -> 5 -> 3 -> 6 -> 5 -> 7 -> 2 -> 7 순서로 데이터를 검색한다고 임의로 가정할 때, 다음과 같은 순서로 캐시 접근이 발생합니다. 

찾는 데이터가 없다면 연결리스트에 데이터를 넣고, 넣을 때 연결리스트 용량이 꽉 차 있으면 마지막 노드를 제거한 뒤에 삽입하게 됩니다. 찾는 데이터가 있다면 해당 데이터를 리스트의 첫 번째 위치로 가져옵니다.

이런 구조일 때 캐시에 데이터를 삽입하고 삭제할 때는 전후 노드의 연결관계만 조정하면 되므로 O(1)의 시간이 걸립니다. 하지만 데이터를 캐시 메모리에서 찾을 때는 전체 연결리스트를 순회해야 하므로 O(N)의 시간이 걸립니다. 이는 연결리스트의 시간 복잡도와 동일합니다.

JAVA 코드로 이중 연결리스트를 통한 LRU 캐시를 구현해보면 다음과 같습니다.

Main.java

// Main.java
public class Main {
    public static void main(String[] args) {
 
      String data[] = {"Mercury", "Venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"}; // 0 ~ 7번 메모리에 저장된 데이터 값. data는 주메모리(RAM)상 영역이라고 가정
       MyLRU lru = new MyLRU(data); // 이중연결리스트를 통한 LRU 캐시 객체 생성
 
       lru.search(1); // 1번 주소의 데이터를 탐색
       lru.printList(); // 현재 이중 연결리스트의 구조 프린트
       lru.search(3);
       lru.printList();
       lru.search(5);
       lru.printList();
       lru.search(3);
       lru.printList();
       lru.search(6);
       lru.printList();
       lru.search(5);
       lru.printList();
       lru.search(7);
       lru.printList();
       lru.search(2);
       lru.printList();
       lru.search(7);
       lru.printList();
 
    }
}

Node.java

// Node.java
public class Node {
    private final int address; // 주메모리 상에서의 주소
    private final String data; // 데이터 값
    private Node prev; // 이전 노드
    private Node next; // 다음 노드
 
    public Node(int address, String data) {
        this.address = address;
        this.data = data;
    }
 
    public int getAddress() {
        return address;
    }
 
    public String getData() {
        return data;
    }
 
    public Node getPrev() {
        return prev;
    }
 
    public void setPrev(Node prev) {
        this.prev = prev;
    }
 
    public Node getNext() {
        return next;
    }
 
    public void setNext(Node next) {
        this.next = next;
    }
 
    public String toString() {
        String p = prev != null ? Integer.toString(prev.getAddress()) : "null";
        String n = next != null ? Integer.toString(next.getAddress()) : "null";
        return "{" +
                "address=" + address +
                ", data='" + data + '\'' +
                ", prev=" + p +
                ", next=" + n +
                '}';
    }
}
 

MyLRU.java

public class MyLRU {
    private int capacity; // 연결리스트의 크기
    private String ram[]; // 주메모리 영역
    private static int DEFAULT_CAPACITY = 3;
    private Node header; // 리스트 헤드
    private Node tail; // 리스트 테일
    private int size; // 연결리스트 크기
 
    public MyLRU(String[] ram) {
        this(ram, DEFAULT_CAPACITY);
    }
 
    public MyLRU(String[] ram, int capacity) {
 
        this.ram = ram;
        this.capacity = capacity;
        this.size = 0;
    }
 
    private boolean add(Node newNode) { // 연결리스트에 노드 삽입
        if (size == 0) { // 연결리스트가 비어있다면 노드 단순 노두 삽입
            header = newNode;
            tail = newNode;
        } else if (size < capacity) { // 연결리스트가 꽉 차이지 않다면
            newNode.setPrev(null); // 삽입할 노드의 다음 노드에 header 연결
            newNode.setNext(header);
            header.setPrev(newNode); // header를 삽입할 노드로
            header = newNode;
        } else { // 리스트가 꽉 차 있다면
            remove(tail); // tail 제거
            newNode.setPrev(null); // 노드 삽입 (이전 과정과 동일)
            newNode.setNext(header);
            header.setPrev(newNode);
            header = newNode;
        }
        size += 1;
        return true;
    }
 
    public Node search(int address) { // 데이터 탐색
        if (size == 0) { // 리스트가 비어있다면 노드 삽입후 반환
            Node node = new Node(address, findData(address));
            add(node);
            return header;
        }
        else {
            Node temp = header;
            while (temp != null) { // 연결리스트에서 찾고자 하는 데이터 순차 탐색
                if (temp.getAddress() == address) { // 데이터를 찾으면
                    remove(temp); // 연결리스트 앞으로 노드 이동
                    add(temp); /
                    return temp;
                }
                temp = temp.getNext();
            }
        }
        // 노드를 찾지 못했을 때(Cache Miss)
        Node node = new Node(address, findData(address)); // 노드 생성후 추가
        add(node);
        return node;
    }
 
    private void remove(Node node) { // 노드 삭제
        Node prev = node.getPrev();
        Node next = node.getNext();
        if (prev != null) {
            prev.setNext(next); // 이전노드의 다음 노드를 현재 노드의 다음 노드로
            if (next != null) {
                next.setPrev(prev); // 다음노드의 이전 노드를 현재 노드의 이전 노드로
            }
            if (node == tail) { // 삭제할 노드가 tail이 이었다면 이전 node를 tail로 만들기 
                tail = prev;
            }
        }
        size -=1;
    }
 
    private String findData(int address) { // 노드를 만들 때 직접 주메모리에 접근해서 데이터 찾기 (메모리에 접근하므로 시간 오래걸리는 작업)
        return ram[address];
    }
 
    private boolean isFull() { return size == capacity;} // 리스트가 꽉 차있는 상태인지
 
    public void printList() { // 연결리스트 
        Node temp = header;
        while (temp.getNext() != null) {
            System.out.print(temp.toString() + " -> ");
            temp = temp.getNext();
        }
        System.out.println(temp.toString());
    }
}
 

코드를 실행해보면 다음과 같이 출력됩니다.

연결리스트에서 노드 순서가 위의 그림과 같음을 확인할 수 있습니다.

 

LRU 알고리즘 구현 방법 2 : 이중 연결리스트(Doubly linked list) + Hash Map 활용

---

위의 방법은 캐시에서 자료를 찾을 때 O(N)의 시간이 걸린다는 단점이 있었습니다. 이번에는 Hash 자료구조를 활용해서 탐색 시간을 개선해 보겠습니다. Hash 자료구조는 탐색, 삽입, 삭제가 최선의 경우 O(1)의 시간입니다.
따라서 LRU 알고리즘에 따라 데이터가 다 찼을 때 삭제할 노드를 찾기 위해서 이중 연결리스트 구조를 활용하고, 연결리스트에 위치한 노드에 바로 접근하기 위해 Hash 자료구조를 사용하면 삽입, 삭제, 탐색이 O(1)의 시간에 가능합니다.
하지만 Hash 자료구조를 사용하면 값을 저장할 추가적인 캐시 메모리 공간이 필요하며, 해시 함수의 성능에 따라 O(N)으로 탐색 시간이 늘어날 수 도 있습니다.

해시함수에 의해 key(메모리주소)에 따른 value(Cache에서 해당 Node의 주소) 바로 접근 가능

코드로 구성을 하면 MyLRU 클래스에 Hash맵을 추가하고 add 메서드에서 Hashmap에 put 하는 로직을, serach 메서드에서 Hashmap의 get을 통해 노드를 찾는 로직을, remove 메서드에서 Hashmap의 노드를 remove 하는 로직을 추가하면 됩니다.

MyLRU.java

import java.util.HashMap;
import java.util.Map;
 
public class MyLRU {
    private int capacity;
    private String ram[];
    private Map<Integer, Node> hashmap; // 해시맵 변수 추가
    private static int DEFAULT_CAPACITY = 3;
    private Node header;
    private Node tail;
    private int size;
 
    public MyLRU(String[] ram) {
        this(ram, DEFAULT_CAPACITY);
    }
 
    public MyLRU(String[] ram, int capacity) {
        this.ram = ram;
        this.hashmap = new HashMap<>(); // 해시맵 객체 할당
        this.capacity = capacity;
        this.size = 0;
    }
 
    private boolean add(Node newNode) {
        if (size == 0) {
            header = newNode;
            tail = newNode;
        } else if (size < capacity) {
            newNode.setPrev(null);
            newNode.setNext(header);
            header.setPrev(newNode);
            header = newNode;
        } else {
            remove(tail);
            newNode.setPrev(null);
            newNode.setNext(header);
            header.setPrev(newNode);
            header = newNode;
        }
       hashmap.put(newNode.getAddress(), newNode); // 해시맵에 노드 추가
        size += 1;
        return true;
    }
 
    public Node search(int address) {
        if (size == 0) {
            Node node = new Node(address, findData(address));
            add(node);
            return header;
        }
        else if(hashmap.get(address) != null){
            Node target = hashmap.get(address); // 해시맵에서 노드 바로 접근
            remove(target);
            add(target);
            return target;
        }
        // 노드를 찾지 못했을 때(Cache Miss)
        Node node = new Node(address, findData(address));
        add(node);
        return node;
    }
 
    private void remove(Node node) {
        Node prev = node.getPrev();
        Node next = node.getNext();
        if (prev != null) {
            prev.setNext(next);
            if (next != null) {
                next.setPrev(prev);
            }
            if (node == tail) {
                tail = prev;
            }
        }
       hashmap.remove(node.getAddress()); // 해시맵에서 노드 삭제
        size -=1;
    }
 
    private String findData(int address) {
        return ram[address];
    }
 
    private boolean isFull() { return size == capacity;}
 
    public void printList() {
        Node temp = header;
        while (temp.getNext() != null) {
            System.out.print(temp.toString() + " -> ");
            temp = temp.getNext();
        }
        System.out.println(temp.toString());
    }
}
 

주석 작성한 부분이 Hashmap 관련 코드이며, 이외의 코드는 search 메서드에서 연결리스트를 순차 탐색하던 로직이 없어진 것 말고는 변동이 없습니다.

이와 같이 두 자료구조를 활용하여 LRU 캐시를 구현해봤습니다.
글을 쓰고 다르게 구현할 수 있는 방법을 찾아보니 대부분 연결리스트 + 해시로 구현하신 것 같았습니다.
또 자바에서는 LinkedHashMap이라는 자료구조를 지원해서 제가 연결리스트와 해시를 각각 구현한 것을 합쳐서 사용할 수 있다는 사실을 알게 됐습니다. LinkedHashMap 사용 방법은 링크를 올려놓겠습니다.

LinkedHashMap (Java Platform SE 8 )

 

다르게 LRU 캐시를 구현하는 좋은 방법이 있다면 댓글로 공유 부탁드립니다. 감사합니다!