FIFO Cache — các khái niệm chính, thuật toán hàng đợi và cách hoạt động

FIFO Cache là gì?

FIFO Cache (First In First Out Cache) là bộ nhớ đệm kích thước cố định sử dụng hàng đợi để quản lý các phần tử. Phần tử đầu tiên được thêm vào được đặt ở đầu hàng đợi và sẽ là phần tử đầu tiên bị xóa khi tràn. Các phần tử mới luôn được thêm vào đuôi, đảm bảo thứ tự xóa khớp với thứ tự thêm vào.

Không giống LRU, sắp xếp lại các phần tử sau mỗi lần truy cập, FIFO không thay đổi vị trí của các phần tử hiện có trong các yêu cầu get. Điều này làm cho thuật toán hoàn toàn tất định: biết thứ tự thêm vào, có thể dự đoán chính xác phần tử nào sẽ bị xóa tiếp theo. Tính dự đoán được này rất quan trọng cho các hệ thống thời gian thực nơi dữ liệu phải được xử lý theo thứ tự đến.

Việc triển khai FIFO Cache có thể được xây dựng trên nhiều cấu trúc dữ liệu: bộ đệm vòng cho hiệu suất tối đa, danh sách liên kết cho tính linh hoạt, hoặc hai ngăn xếp (hàng đợi hai ngăn xếp) cho các ngôn ngữ không có hàng đợi tích hợp. Bộ đệm vòng cung cấp tính cục bộ bộ nhớ đệm tốt nhất và chi phí tối thiểu, nhưng yêu cầu cấp phát trước bộ nhớ cho maxSize.

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

Thao tác enqueue(value) thêm một phần tử vào đuôi hàng đợi. Nếu kích thước đạt maxSize, phần tử ở đầu sẽ bị xóa trước khi thêm. Thao tác dequeue() xóa và trả về phần tử ở đầu — để trích xuất bắt buộc phần tử cũ nhất. Thao tác peek() trả về phần tử đầu mà không xóa — để xem phần tử cũ nhất mà không thay đổi hàng đợi.

Cách FIFO Cache hoạt động

Thuật toán FIFO mô phỏng hành vi của hàng đợi thông thường: ai đến trước được phục vụ trước. Trong bối cảnh bộ nhớ đệm, điều này có nghĩa là phần tử đã ở trong bộ nhớ đệm lâu nhất sẽ bị xóa khi cần không gian — bất kể mức độ phổ biến của nó. Chính sách loại bỏ của FIFO bỏ qua tần suất truy cập, đây vừa là điểm mạnh vừa là điểm yếu của thuật toán.

Khi triển khai qua bộ đệm vòng, hai con trỏ được sử dụng: head (chỉ mục đầu hàng đợi) và tail (chỉ mục đuôi). Khi enqueue, phần tử được ghi tại chỉ mục tail và tail được tăng lên. Nếu tail đạt kích thước bộ đệm, nó quay vòng về đầu mảng. Nếu tail đuổi kịp head, hàng đợi đã đầy và head được dịch chuyển (loại bỏ). Bộ đệm vòng không yêu cầu cấp phát bộ nhớ động và tránh phân mảnh.

FIFO Cache cho thấy hit-ratio từ 40% đến 60% cho các khối lượng công việc điển hình, cao hơn LIFO nhưng thấp hơn LRU. Tuy nhiên, đối với các kịch bản truy cập dữ liệu đồng đều và không có điểm nóng, FIFO có thể cho kết quả tương đương LRU với độ phức tạp triển khai thấp hơn đáng kể. Bộ nhớ được sử dụng hiệu quả: không cần con trỏ bổ sung cho việc sắp xếp lại phần tử.

Vấn đề ô nhiễm bộ nhớ đệm

Nhược điểm chính của FIFO là dễ bị ô nhiễm bộ nhớ đệm. Nếu một lượng lớn dữ liệu sẽ không bao giờ cần dùng lại được thêm vào bộ nhớ đệm, chúng sẽ dần dần loại bỏ tất cả các phần tử hữu ích và hit-ratio sẽ giảm mạnh. LRU giải quyết một phần vấn đề này vì các phần tử được sử dụng thường xuyên được làm mới liên tục bằng cách di chuyển lên đầu, trong khi dữ liệu sử dụng một lần bị loại bỏ nhanh hơn. Trong FIFO, dữ liệu sử dụng một lần ở lại bộ nhớ đệm cho đến khi bị loại bỏ tự nhiên theo thứ tự hàng đợi.

So sánh FIFO, LRU và LIFO

Việc lựa chọn giữa FIFO, LRU và LIFO phụ thuộc vào mẫu truy cập dữ liệu và yêu cầu về khả năng dự đoán hành vi. LRU tối ưu cho hầu hết các kịch bản, FIFO cho dữ liệu luồng với truy cập đồng đều và LIFO cho cấu trúc ngăn xếp.

FIFO lý tưởng cho các kịch bản nơi thứ tự xử lý phải khớp với thứ tự đến: đệm dữ liệu, ghi nhật ký, xử lý sự kiện. LRU tốt hơn cho bộ nhớ đệm với truy cập không đồng đều (dữ liệu người dùng). LIFO chỉ áp dụng cho ngăn xếp và Hoàn tác. Đối với hầu hết các ứng dụng di động, LRU vẫn là lựa chọn mặc định, nhưng FIFO có thể được ưu tiên hơn dưới các ràng buộc bộ nhớ nghiêm ngặt hoặc yêu cầu về khả năng dự đoán.

FIFO Cache được sử dụng ở đâu

FIFO Cache được ứng dụng trong các kịch bản nơi khả năng dự đoán loại bỏ hoặc thứ tự xử lý dữ liệu quan trọng. Hãy xem xét các trường hợp sử dụng chính.

Đệm dữ liệu luồng

Khi phát âm thanh và video, dữ liệu đến dưới dạng luồng liên tục và được lưu trữ tạm thời trong bộ đệm. FIFO Cache đảm bảo các đoạn đầu tiên nhận được sẽ được gửi đi giải mã đầu tiên — điều này đảm bảo phát lại mượt mà không bị chậm trễ. Kích thước bộ đệm được chọn dựa trên tốc độ bit của luồng và độ trễ chấp nhận được: thường 2–5 giây cho âm thanh, 10–30 giây cho video. FIFO lý tưởng cho các kịch bản như vậy vì việc sắp xếp lại dữ liệu (như trong LRU) là vô nghĩa.

Hàng đợi yêu cầu mạng

Khi giới hạn số lượng yêu cầu mạng đồng thời, FIFO Cache có thể được sử dụng để lưu trữ các yêu cầu đang chờ. Yêu cầu được thêm đầu tiên sẽ được thực thi đầu tiên, đảm bảo phân phối công bằng tài nguyên mạng giữa các thành phần khác nhau của ứng dụng. Cách tiếp cận này được sử dụng trong OkHttp Dispatcher và các thư viện tương tự để quản lý nhóm kết nối.

Lưu trữ phản hồi HTTP

Bộ nhớ đệm phản hồi HTTP đơn giản trên thiết bị di động thường sử dụng FIFO. Phản hồi cho các yêu cầu được lưu trữ theo thứ tự đến và khi đạt giới hạn, những phản hồi cũ nhất sẽ bị xóa. Mặc dù LRU sẽ mang lại hit-ratio tốt hơn cho các kịch bản người dùng, FIFO đơn giản hơn để triển khai và không yêu cầu lưu trữ thời gian truy cập cuối cùng cho mỗi phản hồi. Đối với API có tải đồng đều, sự khác biệt về hit-ratio giữa FIFO và LRU là tối thiểu.

Xử lý sự kiện cảm ứng

Trong các ứng dụng di động, sự kiện cảm ứng được lưu trong bộ đệm FIFO trước khi xử lý cử chỉ. Mỗi sự kiện phải được xử lý theo thứ tự xảy ra, nếu không cử chỉ sẽ được nhận dạng sai. FIFO Cache có giới hạn kích thước ngăn tràn bộ đệm khi vuốt nhanh, loại bỏ các sự kiện cũ nhất nếu ứng dụng không thể xử lý kịp.

Ví dụ mã FIFO Cache

Hãy xem xét triển khai FIFO Cache trong Kotlin sử dụng bộ đệm vòng — cách tiếp cận hiệu suất nhất cho thiết bị di động.

class FifoCache<V>(
    private val maxSize: Int
) {
    private val buffer = arrayOfNulls<V>(maxSize)
    private var head = 0
    private var tail = 0
    private var size = 0

    fun enqueue(value: V) {
        if (size == maxSize) {
            // xóa phần tử cũ nhất
            buffer[head] = null
            head = (head + 1) % maxSize
            size--
        }
        buffer[tail] = value
        tail = (tail + 1) % maxSize
        size++
    }

    fun dequeue(): V? {
        if (size == 0) return null
        val result = buffer[head]
        buffer[head] = null
        head = (head + 1) % maxSize
        size--
        return result
    }

    fun peek(): V? {
        return buffer[head]
    }
}

Bộ đệm vòng sử dụng các chỉ mục head và tail tăng dần theo chu kỳ modulo maxSize. Khi size == maxSize, enqueue trước tiên xóa phần tử tại head (cũ nhất), dịch chuyển head, sau đó ghi phần tử mới tại tail. Số học mô-đun tự động quay vòng con trỏ về đầu mảng, loại bỏ việc sao chép dữ liệu thủ công.

Triển khai Swift qua hai ngăn xếp

Trong Swift, một giải pháp thay thế thuận tiện là hàng đợi FIFO dựa trên hai ngăn xếp (hàng đợi hai ngăn xếp). Tất cả các thao tác enqueue đi vào ngăn xếp đầu tiên (push) và khi dequeue, các phần tử được chuyển sang ngăn xếp thứ hai theo thứ tự ngược lại — làm cho dequeue trở thành O(1) trung bình.

struct FifoCache<Value> {
    private let maxSize: Int
    private var inStack = [Value]()
    private var outStack = [Value]()

    mutating func enqueue(value: Value) {
        if inStack.count + outStack.count >= maxSize {
            if outStack.isEmpty {
                outStack = inStack.reversed()
                inStack.removeAll()
            }
            outStack.removeLast()
        }
        inStack.append(value)
    }

    mutating func dequeue() -> Value? {
        if outStack.isEmpty {
            outStack = inStack.reversed()
            inStack.removeAll()
        }
        return outStack.popLast()
    }
}

Hai ngăn xếp cung cấp độ phức tạp khấu hao O(1) cho enqueue và dequeue. outStack.removeLast() khi loại bỏ sẽ xóa phần tử cũ nhất (được thêm đầu tiên). Cách tiếp cận này không yêu cầu cấp phát trước bộ nhớ nhưng có thể tạo ra tải bổ sung lên bộ thu gom rác trong quá trình đảo ngược ngăn xếp thường xuyên. Đối với các ứng dụng di động có bộ nhớ hạn chế, bộ đệm vòng vẫn được ưu tiên hơn.