FIFO 缓存 — 关键概念、队列算法及工作原理

什么是 FIFO Cache？

FIFO Cache（First In First Out Cache）— 一种固定大小的缓存，使用队列管理元素。第一个添加的元素位于队列头部，溢出时将被第一个删除。新元素始终添加到尾部，确保淘汰顺序与添加顺序一致。

与在每次访问时重新排序元素的 LRU 不同，FIFO 在 get 操作中不改变现有元素的位置。这使算法完全确定性：知道添加顺序，就可以精确预测哪个元素将被下一个淘汰。这种可预测性对于实时系统至关重要，因为需要保证按到达顺序处理数据。

FIFO Cache 的实现可以基于多种数据结构：环形缓冲区（circular buffer）提供最大性能和最小开销，链表提供灵活性，双栈实现（Two-Stack Queue）适用于没有内置队列的语言。环形缓冲区提供最佳的缓存局部性和最小开销，但需要为 maxSize 预先分配内存。

FIFO Cache 的基本操作

enqueue(value) 操作将元素添加到队列尾部。如果大小已达到 maxSize，添加前会删除头部的元素。dequeue() 操作删除并返回头部的元素 — 用于强制获取最旧的元素。peek() 操作返回头部元素但不删除 — 用于在不改变队列的情况下查看最旧的元素。

FIFO Cache 如何工作

FIFO 算法模拟普通队列的行为：先进先出。在缓存的上下文中，这意味着在缓存中停留时间最长的元素将在空间不足时被删除 — 无论它被需要多少。淘汰策略 FIFO 忽略访问频率，这既是算法的优点也是缺点。

通过环形缓冲区实现时，使用两个指针：head（队列头部索引）和 tail（尾部索引）。enqueue 时，元素写入 tail 索引，然后 tail 增加。如果 tail 达到缓冲区大小，它会绕回到数组开头。如果 tail 追上 head — 队列已满，head 向前移动（淘汰）。环形缓冲区不需要动态内存分配并避免碎片化。

FIFO Cache 在典型负载下显示 40% 至 60% 的命中率，高于 LIFO 但低于 LRU。然而，在数据访问均匀且没有热点的场景中，FIFO 可以在实现复杂度显著降低的情况下展示与 LRU 相当的结果。内存使用效率高：不需要额外的指针来重新排列元素。

缓存污染问题

FIFO 的主要缺点 — 容易受到缓存污染（cache pollution）的影响。如果大量永远不再需要的数据添加到缓存中，它们将逐渐淘汰所有有用的元素，命中率将急剧下降。LRU 部分解决了这个问题，因为频繁使用的元素通过移动到头部而不断刷新，而一次性元素更快地被淘汰。在 FIFO 中，一次性数据在队列的自然顺序中淘汰前一直保留在缓存中。

FIFO、LRU 和 LIFO 比较

在 FIFO、LRU 和 LIFO 之间的选择取决于数据访问模式和行为可预测性的要求。LRU 对大多数场景是最优的，FIFO 适用于均匀访问的流数据，LIFO 适用于栈结构。

FIFO 适用于处理顺序必须与到达顺序一致的场景：数据缓冲、日志记录、事件处理。LRU 更适合不均匀访问的缓存（用户数据）。LIFO 仅适用于栈和撤销操作。对于大多数移动应用，LRU 仍然是默认选择，但在严格的内存限制或可预测性要求下，FIFO 可能更可取。

FIFO Cache 的应用场景

FIFO Cache 用于淘汰可预测性或数据处理顺序重要的场景。让我们看看主要用例。

流数据缓冲

在音频和视频播放期间，数据以连续流的形式到达并临时存储在缓冲区中。FIFO Cache 确保最先接收的片段最先发送到解码器 — 这保证了无延迟的流畅播放。缓冲区大小根据流的比特率和允许的延迟选择：音频通常为 2–5 秒，视频为 10–30 秒。FIFO 非常适合此类场景，因为重新排序数据（如在 LRU 中）没有意义。

网络请求队列

在限制并发网络请求数量时，FIFO Cache 可用于存储等待中的请求。第一个添加的请求将首先执行，确保应用程序不同组件之间网络资源的公平分配。这种方法用于 OkHttp Dispatcher 和类似库来管理连接池。

HTTP 响应缓存

移动设备上的简单 HTTP 响应缓存通常使用 FIFO。请求的响应按到达顺序存储，达到限制时删除最旧的。虽然 LRU 在用户场景中提供更好的命中率，但 FIFO 实现更简单，且不需要为每个响应存储最后访问时间。对于均匀负载的 API，FIFO 和 LRU 之间的命中率差异很小。

触摸事件处理

在移动应用中，触摸事件在手势识别前被缓冲到 FIFO 队列中。每个事件必须按发生顺序处理，否则手势将被错误识别。FIFO Cache 通过大小限制防止快速滑动时缓冲区溢出，在应用无法及时处理时丢弃最旧的事件。

FIFO Cache 代码示例

让我们看看在 Kotlin 中使用环形缓冲区实现 FIFO Cache — 这是移动设备最高效的方法。

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) {
            // 淘汰最旧元素
            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]
    }
}

环形缓冲区使用 head 和 tail 索引，它们以 maxSize 为模循环递增。当 size == maxSize 时，enqueue 首先删除 head 处的元素（最旧的），移动 head，然后将新元素写入 tail。模算术自动将指针绕回到数组开头，消除了手动数据复制。

在 Swift 中通过双栈实现

在 Swift 中，一个方便的替代方案 — 基于双栈的 FIFO 队列（Two-Stack Queue）。所有 enqueue 操作都在第一个栈中执行（push），而 dequeue 时元素按相反顺序转移到第二个栈 — 这样 dequeue 操作平均变为 O(1)。

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()
    }
}

双栈为 enqueue 和 dequeue 提供均摊 O(1) 复杂度。outStack.removeLast() 在淘汰时删除最旧的元素（第一个添加的）。这种方法不需要预先分配内存，但频繁的栈反转可能会给垃圾收集器带来额外负担。对于内存有限的移动应用，环形缓冲区仍然更可取。