LRU Cache — nó là gì, thuật toán loại bỏ và cách hoạt động

LRU Cache là gì?

LRU Cache (Least Recently Used Cache) là một cấu trúc dữ liệu có kích thước cố định lưu trữ một số lượng phần tử giới hạn và tự động xóa những phần tử ít được truy cập nhất. Khi một ứng dụng yêu cầu một phần tử, nó di chuyển đến phần “mới” của bộ nhớ đệm, trong khi các phần tử không được sử dụng trong thời gian dài trượt về cuối và bị xóa khi đạt đến giới hạn.

Tên “Least Recently Used” mô tả chính sách loại bỏ: phần tử không được sử dụng lâu nhất trong số tất cả các phần tử được lưu trữ sẽ bị xóa. Điều này dựa trên giả định về tính cục bộ tham chiếu (locality of reference) — dữ liệu được yêu cầu gần đây có khả năng cao sẽ cần lại. Đây là lý do LRU được coi là một trong những chiến lược lưu đệm hiệu quả nhất cho hầu hết các ứng dụng.

Triển khai cổ điển của LRU Cache yêu cầu hai cấu trúc dữ liệu: một bảng băm để truy cập O(1) tới bất kỳ phần tử nào theo khóa và một danh sách liên kết đôi để theo dõi thứ tự sử dụng. Bảng băm lưu trữ các tham chiếu đến các nút danh sách, và danh sách duy trì thứ tự từ phần tử mới nhất (đầu) đến phần tử cũ nhất (đuôi).

Các thao tác cơ bản của LRU Cache

Thao tác get(key) kiểm tra xem khóa có tồn tại trong bảng băm không. Nếu phần tử được tìm thấy, nó di chuyển lên đầu danh sách (trở thành mới nhất) và giá trị của nó được trả về. Nếu không tìm thấy, null được trả về hoặc một ngoại lệ được ném ra. Thao tác put(key, value) chèn một phần tử mới: nếu khóa đã tồn tại, giá trị được cập nhật và phần tử di chuyển lên đầu. Nếu bộ nhớ đệm đầy, phần tử ở đuôi sẽ bị xóa trước khi chèn. Tất cả các thao tác được thực hiện trong thời gian hằng số O(1).

Cách LRU Cache hoạt động

Thuật toán LRU Cache dựa trên hai nguyên tắc: đếm truy cập theo thứ tự thời gian và cơ chế loại bỏ khi tràn. Mỗi phần tử được lưu trữ trong một nút của danh sách liên kết đôi, và các con trỏ đến các nút này được giữ trong bảng băm. Mỗi lần truy cập, phần tử được tách khỏi vị trí hiện tại và được chèn vào đầu danh sách.

Khi kích thước bộ nhớ đệm đạt giá trị tối đa (maxSize) và có yêu cầu chèn một phần tử mới, thuật toán sẽ xóa phần tử ở đuôi của danh sách liên kết đôi — đây là phần tử ít được sử dụng gần đây nhất. Sau khi xóa, không gian được giải phóng cho phần tử mới, được chèn vào đầu danh sách. Bảng băm được cập nhật tương ứng: khóa cũ bị xóa, khóa mới được thêm vào.

Một đặc điểm của LRU là độ nhạy cảm với các mẫu truy cập có lặp lại theo chu kỳ. Nếu ứng dụng truy cập định kỳ vào một tập dữ liệu lớn hơn kích thước bộ nhớ đệm, LRU có thể bị thrashing — thay thế phần tử thường xuyên khi mỗi yêu cầu mới loại bỏ yêu cầu trước đó. Trong các kịch bản như vậy, LFU (Least Frequently Used) hoặc các thuật toán thích ứng có thể hiệu quả hơn.

Kích thước bộ nhớ đệm và số liệu

Chọn kích thước LRU Cache là sự đánh đổi giữa tiêu thụ bộ nhớ và tỷ lệ hit (phần trăm truy cập thành công). Các giá trị điển hình cho ứng dụng di động: 10–20% bộ nhớ khả dụng cho bộ nhớ đệm hình ảnh và 50–200 mục cho bộ nhớ đệm phản hồi mạng. Tỷ lệ hit 80–95% được coi là tốt, khi bộ nhớ đệm biện minh cho chi phí bộ nhớ. Để giám sát, các bộ đếm hitCount và missCount được sử dụng, có sẵn trong triển khai LruCache trong Android.

Triển khai LRU Cache: HashMap + Doubly Linked List

Triển khai chuẩn của LRU Cache sử dụng kết hợp bảng băm và danh sách liên kết đôi. Bảng băm cung cấp truy cập O(1) tới bất kỳ nút nào theo khóa, trong khi danh sách liên kết đôi cho phép di chuyển nút lên đầu và xóa khỏi đuôi trong O(1). Quan trọng là danh sách được liên kết đôi: điều này cho phép tách một nút khỏi giữa danh sách mà không cần lặp qua tất cả các phần tử.

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

Trong triển khai, mỗi nút (Node) lưu trữ một giá trị và các tham chiếu đến nút trước và nút sau. Các nút sentinel head và tail đơn giản hóa các trường hợp biên — không cần kiểm tra null khi chèn và xóa. Phương thức get di chuyển nút được tìm thấy lên đầu, và put xóa phần tử ở đuôi khi tràn. Một phương thức riêng removeKeyByValue tìm khóa trong bảng băm theo tham chiếu nút và xóa nó.

Triển khai LruCache tích hợp trong Android

Android SDK cung cấp một lớp LruCache sẵn có trong gói android.util, triển khai thuật toán LRU sử dụng LinkedHashMap ở chế độ access-order. Lớp này an toàn luồng, hỗ trợ đếm hit/miss và cung cấp callback entryRemoved để dọn dẹp tài nguyên khi loại bỏ phần tử. Kích thước bộ nhớ đệm được đặt bằng đơn vị tùy ý (byte, số lượng phần tử) — chỉ cần ghi đè phương thức sizeOf.

LRU Cache so với FIFO và LIFO

Cả ba thuật toán — LRU, FIFO và LIFO — giải quyết cùng một vấn đề: giới hạn tiêu thụ bộ nhớ bằng cách loại bỏ phần tử khi tràn. Tuy nhiên, chúng sử dụng các tiêu chí khác nhau về cơ bản để chọn phần tử loại bỏ, điều này quyết định hiệu quả của chúng trong các kịch bản khác nhau.

FIFO loại bỏ phần tử cũ nhất theo thời gian chèn, bất kể tần suất truy cập. Điều này có thể không hiệu quả nếu một phần tử cũ vẫn còn liên quan. LRU tránh nhược điểm này bằng cách xem xét mẫu truy cập. LIFO loại bỏ phần tử được thêm gần đây nhất — hữu ích cho các kịch bản hoàn tác, nhưng không phù hợp cho lưu đệm vì dữ liệu mới thường cần thiết hơn dữ liệu cũ. LRU được coi là sự cân bằng tối ưu giữa độ phức tạp triển khai và tỷ lệ hit cho hầu hết các ứng dụng.

Ví dụ mã LRU Cache

Hãy xem xét việc sử dụng lớp LruCache tích hợp từ Android SDK để lưu đệm hình ảnh đã tải xuống. Ví dụ cho thấy khởi tạo bộ nhớ đệm ở mức 1/8 bộ nhớ khả dụng của ứng dụng, đây là khuyến nghị tiêu chuẩn của Google cho lưu đệm hình ảnh.

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

Phương thức sizeOf trả về kích thước phần tử trong cùng đơn vị với cacheSize. Ở đây, kích thước Bitmap tính bằng kilobyte được sử dụng (rowBytes × height / 1024). Khi tổng sizeOf của tất cả các phần tử vượt quá cacheSize, LruCache tự động loại bỏ các Bitmap ít được sử dụng gần đây nhất. Callback entryRemoved có thể được sử dụng để gọi bitmap.recycle() — giải phóng bộ nhớ trước khi loại bỏ.

Triển khai LRU Cache trong Swift

iOS không có lớp LRU Cache tích hợp, nhưng có thể dễ dàng triển khai bằng NSCache (sử dụng chính sách loại bỏ tương tự nhưng không được ghi chép) hoặc thông qua triển khai tùy chỉnh sử dụng Dictionary + Danh sách liên kết đôi, như được hiển thị bên dưới.

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

Trong triển khai Swift này, Node là một lớp nội bộ với các trường value, next và prev. Phương thức moveToHead tách một nút khỏi vị trí hiện tại và chèn nó vào đầu danh sách. Khi tràn, phần tử đuôi — phần tử ít được sử dụng gần đây nhất — bị xóa. Đối với môi trường sản xuất, nên thêm tính an toàn luồng thông qua NSLock hoặc hàng đợi DispatchQueue.