LRU Cache

Giới thiệu

Vào một ngày đẹp trời, bạn nảy ra ý tưởng là sẽ làm bánh để tặng người yêu, à không, 1 người bạn thân 😂. Vì vậy bạn quyết định đi đến nhà hàng, gặp ông đầu bếp mà bạn quen, hỏi ông ta về công thức làm món bánh mà bạn ưa thích. Lúc này, ông đầu bếp sẽ đi lấy cuốn sách công thức làm bánh được đặt ở trên kệ sách. Sau đó ông ta đặt cuốn sách lên bàn và tìm đúng công thức mà bạn cần, rồi chụp hình lại và đưa cho bạn. Cuối cùng thì cuốn sách sẽ được đặt lại vào kệ sách, ở đúng cái chỗ mà nó được lấy ra.

Ngày qua ngày, ông đầu bếp bắt đầu nhận ra càng có nhiều người cần đến công thức làm bánh của mình. Vì vậy ông ta quyết định đặt luôn cuốn sách trên bàn mà không cần phải đặt lại vào kệ nữa. Như vậy thì sẽ tiết kiệm thời gian của ông hơn. Nhưng ngoài công thức làm bánh ra, ông còn có sách về công thức làm sữa chua, cocktail, … và còn nhiều công thức khác nữa 😅. Cái bàn của ông thì nó không được to, chỉ đủ để 3 cuốn sách mà thôi. Vì vậy, ông chỉ có thể bày ra 3 cuốn sách có công thức mà thường được yêu cầu nhất mà thôi.

Vâng câu chuyện trên chỉ là 1 câu chuyện mà tôi bịa ra 😄. Nhưng mà nó có liên quan gì đến chủ đề của bài viết nhỉ? Thực ra là có đấy. Trong câu chuyện trên, tôi đã đề cập đến cái kệ sách, cái bàn, và ông đầu bếp. Trong kiến trúc của máy tính cũng như vậy: ông đầu bếp chính là cpu của máy tính, cái bàn chính là memory, còn cái kệ sách chính là disk. Data trên memory sẽ được truy xuất nhanh hơn đối với những data truy xuất từ disk. Nhưng mà bởi vì memory có kích thước nhỏ hơn rất nhiều so với disk, nên memory chỉ có thể cache lại những data thường được truy xuất mà thôi. Và để làm được điều này, Chúng ta sẽ cần 1 thuật toán có tên gọi là LRU (Least Recently Used) Cache.

LRU cache được mô tả với kịch bản như sau

• Trong disk lưu giữ 4 công thức làm bánh: chocolate, vanilla, strawberry, pound.

• Đâu tiên, 1 user request công thức làm bánh chocolate. server đọc data từ disk, lưu vào cache, sau đó trả kết quả về cho user.

• Tiếp theo, 1 user khác request công thức làm bánh vanilla.

• Lúc này, công thức chocolate được đẩy lùi xuống phía sau trong cache. Công thức vanilla trở thành data được truy xuất mới nhất.
• Sau đó, công thức làm bánh strawberry được request.

• Và thêm 1 lần cho chocolate.

• Và vì chocolate đã có trên cache rồi, nên server không cần phải đọc disk nữa. Lúc này chocolate sẽ được đưa lên vị trí đầu tiên, trở thành data được truy xuất mới nhất.
• Tiếp đến, 1 user khác request công thức làm bánh pound.

• Hiện tại thì cache đã đầy, nên cần phải loại bỏ 1 data (được truy xuất ít nhất) là vanilla, và lúc này pound được đưa vào vị trí đầu tiên (được truy xuất mới nhất).

Có rất nhiều thuật toán khác để giải quyết cho bài toán full cache. Trong bài viết này, chúng ta tập trung vào LRU bởi vì nó trường được sử dụng trong coding interview.

LRU cache sử dụng 2 cấu trúc dữ liệu là

• Double linked list: ghi nhận về mức độ truy xuất thường xuyên của các data

• Hash map: ghi nhận việc data đã được lưu vào cache hay chưa

  Nếu không dùng map, chúng ta vẫn có thể kiểm tra cache đã có data hay chưa, thông qua việc duyệt các phần tử bên trong double linked list với độ phức tạp là O(n). Tuy nhiên nếu dùng map, độ phức tạp sẽ chỉ còn là O(1)

Code 1 chút cho vui nào 😋

package lib;

public class Node<T> {

  private T data;
  private Node<T> next;
  private Node<T> previous;

  public Node(T data) { this.data = data; }

  public T getData() { return data; }

  public Node<T> getNext() { return next; }

  public void setNext(Node<T> next) { this.next = next; }

  public boolean hasNext() { return next != null; }

  public Node<T> getPrevious() { return previous; }

  public void setPrevious(Node previous) { this.previous = previous; }

  public boolean hasPrevious() { return previous != null; }
}

package lib;

public class DoubleLinkedList<T> {

  private Node<T> first;
  private Node<T> last;
  private int size;

  public DoubleLinkedList() {
    this.size = 0;
  }

  public void addFirst(Node<T> newNode) {
    if (size == 0) {
      first = last = newNode;
    } else {
      newNode.setNext(first);
      first.setPrevious(newNode);
      first = newNode;
    }
    size++;
  }

  public void removeFirst() {
    Node<T> nextNode = last.getNext();
    last.setNext(null);
    last = nextNode;
    last.setPrevious(null);
  }

  public Node<T> getFirst() {
    return first;
  }

  public Node<T> getLast() {
    return last;
  }

  public void removeLast() {
    Node<T> previousNode = last.getPrevious();
    last.setPrevious(null);
    last = previousNode;
    last.setNext(null);
  }

  public void remove(Node<T> node) {
    if (node == first) {
      removeFirst();
    } else if (node == last) {
      removeLast();
    } else {
      Node<T> previousNode = node.getPrevious();
      Node<T> nextNode = node.getNext();

      node.setPrevious(null);
      node.setNext(null);

      previousNode.setNext(nextNode);
      nextNode.setPrevious(previousNode);
    }
  }
}

package lru;

import java.util.HashMap;
import java.util.Map;
import lib.DoubleLinkedList;
import lib.Node;

public class LRUCache {

  private int capacity;
  private Map<String, Node<String>> map;
  private DoubleLinkedList<String> queue;

  public LRUCache(int capacity) {
    this.capacity = capacity;
    this.queue = new DoubleLinkedList<>();
    this.map = new HashMap<>();
  }

  public void put(String value) {
    if (map.containsKey(value)) {
      renew(value);
    } else {
      addNew(value);
    }
  }

  private void addNew(String value) {
    if (map.size() >= capacity) {
      map.remove(queue.getLast().getData());
      queue.removeLast();
    }

    Node<String> newNode = new Node<>(value);

    queue.addFirst(newNode);
    map.put(value, newNode);
  }

  private void renew(String value) {
    Node<String> node = map.get(value);
    queue.remove(node);
    queue.addFirst(node);
  }

  public void displayQueue() {
    Node<String> node = queue.getLast();
    if (node != null) {
      System.out.print(node.getData());
      while (node.hasPrevious()) {
        node = node.getPrevious();
        System.out.print(" -> " + node.getData());
      }
      System.out.println();
    }
  }
}

import lru.LRUCache;

public class Main {
  public static void main(String[] args) {
    LRUCache cache = new LRUCache(3);

    addToCache(cache, "chocolate");
    addToCache(cache, "vanilla");
    addToCache(cache, "strawberry");
    addToCache(cache, "chocolate");
    addToCache(cache, "pound");
  }

  private static void addToCache(LRUCache cache, String value) {
    cache.put(value);
    cache.displayQueue();
  }
}

Kết quả chạy code

chocolate
chocolate -> vanilla
chocolate -> vanilla -> strawberry
vanilla -> strawberry -> chocolate
strawberry -> chocolate -> pound

Cám ơn các bạn đã đọc bài viết. Nếu có câu hỏi, hoặc các bạn biết những thuật toán hay được sử dụng trong coding interview, đừng ngần ngại chia sẻ nhé. 😁

Tham khảo: https://www.interviewcake.com/concept/java/lru-cache