FIFO Cache — 主要概念、キューアルゴリズムと仕組み

FIFO Cacheとは？

FIFO Cache（First In First Out Cache）は、要素を管理するためにキューを使用する固定サイズのキャッシュです。最初に追加された要素はキューの先頭に配置され、オーバーフローが発生したときに最初に削除されます。新しい要素は常に末尾に追加され、削除順序が追加順序と一致することが保証されます。

アクセスのたびに要素を並べ替えるLRUとは異なり、FIFOはgetリクエストで既存の要素の位置を変更しません。これにより、アルゴリズムは完全に決定論的になります。追加順序がわかれば、次にどの要素が追い出されるかを正確に予測できます。この予測可能性は、データを到着順に処理する必要があるリアルタイムシステムにとって重要です。

FIFO Cacheの実装は、いくつかのデータ構造で構築できます。最大パフォーマンスのための循環バッファ、柔軟性のためのリンクリスト、または組み込みキューを持たない言語のための2つのスタック（Two-Stack Queue）です。循環バッファは最良のキャッシュローカリティと最小限のオーバーヘッドを提供しますが、maxSizeのためのメモリの事前割り当てが必要です。

FIFO Cacheの基本操作

enqueue(value)操作は、キューの末尾に要素を追加します。サイズがmaxSizeに達した場合、追加の前に先頭の要素が削除されます。dequeue()操作は先頭の要素を削除して返します — 最も古い要素の強制的な取り出しのためです。peek()操作は削除せずに先頭の要素を返します — キューを変更せずに最も古い要素を表示するためです。

FIFO Cacheの仕組み

FIFOアルゴリズムは通常のキューの動作を模倣します：最初に入ったものが最初にサービスされます。キャッシングの文脈では、これはキャッシュに最も長く存在する要素が、その人気度に関係なく、スペースが必要になったときに削除されることを意味します。FIFOの追い出しポリシーはアクセス頻度を無視します。これはアルゴリズムの強みであり弱みでもあります。

循環バッファで実装する場合、head（キューの先頭のインデックス）とtail（末尾のインデックス）の2つのポインタが使用されます。enqueueでは、要素がtailインデックスに書き込まれ、tailがインクリメントされます。tailがバッファサイズに達すると、配列の先頭に折り返されます。tailがheadに追いつくと、キューは満杯で、headがシフトされます（追い出し）。循環バッファは動的メモリ割り当てを必要とせず、断片化を回避します。

FIFO Cacheは、一般的なワークロードに対して40%から60%のhit-ratioを示し、LIFOよりは高いですがLRUよりは低い値です。ただし、データアクセスが均一でホットスポットがないシナリオでは、FIFOは大幅に低い実装複雑性でLRUに匹敵する結果を示すことができます。メモリは効率的に使用されます。要素の並べ替えに追加のポインタは必要ありません。

キャッシュ汚染の問題

FIFOの主な欠点は、キャッシュ汚染に対する感受性です。二度と必要とされない大量のデータがキャッシュに追加されると、徐々にすべての有用な要素を追い出し、hit-ratioが急激に低下します。LRUはこの問題を部分的に解決します。頻繁に使用される要素は先頭に移動することで常にリフレッシュされ、1回限りのデータはより速く追い出されます。FIFOでは、1回限りのデータはキューの順序によって自然に追い出されるまでキャッシュに残ります。

FIFO、LRU、LIFOの比較

FIFO、LRU、LIFOの選択は、データアクセスパターンと動作の予測可能性の要件に依存します。LRUはほとんどのシナリオに最適で、FIFOは均一なアクセスを持つストリーミングデータに、LIFOはスタック構造に適しています。

FIFOは、処理順序が到着順序と一致する必要があるシナリオに最適です：データバッファリング、ロギング、イベント処理。LRUは不均等なアクセス（ユーザーデータ）のキャッシングに適しています。LIFOはスタックと元に戻す操作にのみ適用可能です。ほとんどのモバイルアプリケーションでは、LRUがデフォルトの選択肢ですが、厳格なメモリ制約や予測可能性の要件がある場合はFIFOが好ましい場合があります。

FIFO Cacheの使用例

FIFO Cacheは、追い出しの予測可能性やデータ処理の順序が重要なシナリオで使用されます。主な使用例を見てみましょう。

ストリーミングデータのバッファリング

オーディオとビデオの再生時、データは連続ストリームで到着し、一時的にバッファに保存されます。FIFO Cacheは、最初に受信したフラグメントが最初にデコードに送られることを保証します — これにより遅延のないスムーズな再生が保証されます。バッファサイズは、ストリームのビットレートと許容可能な遅延に基づいて選択されます：オーディオでは通常2〜5秒、ビデオでは10〜30秒です。データの並べ替え（LRUのような）が意味をなさないため、FIFOはこのようなシナリオに最適です。

ネットワークリクエストキュー

同時ネットワークリクエストの数を制限する場合、FIFO Cacheを使用して保留中のリクエストを保存できます。最初に追加されたリクエストが最初に実行され、アプリケーションの異なるコンポーネント間でネットワークリソースの公平な配分が保証されます。このアプローチは、OkHttp Dispatcherや同様のライブラリでコネクションプール管理に使用されています。

HTTPレスポンスのキャッシング

モバイルデバイス上のシンプルなHTTPレスポンスキャッシュは、多くの場合FIFOを使用します。リクエストへの応答は到着順に保存され、制限に達すると最も古いものが削除されます。LRUはユーザーシナリオでより良いhit-ratioを提供しますが、FIFOは実装がより簡単で、各応答の最終アクセス時間を保存する必要がありません。均一な負荷のAPIの場合、FIFOとLRUのhit-ratioの差は最小限です。

タッチイベント処理

モバイルアプリケーションでは、タッチイベントはジェスチャー処理の前に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]
    }
}

循環バッファは、maxSizeを法として循環的にインクリメントされるheadとtailのインデックスを使用します。size == maxSizeのとき、enqueueは最初にheadの要素（最も古いもの）を削除し、headをシフトしてから、tailに新しい要素を書き込みます。モジュラ演算は自動的にポインタを配列の先頭に折り返し、手動のデータコピーを排除します。

2つのスタックを使用したSwiftでの実装

Swiftでは、2つのスタックに基づくFIFOキュー（Two-Stack Queue）が便利な代替手段です。すべてのenqueue操作は最初のスタック（push）に行き、dequeue時に要素は逆順で2番目のスタックに転送されます — これにより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()
    }
}

2つのスタックは、enqueueとdequeueに対してならしO(1)の複雑性を提供します。追い出し時のoutStack.removeLast()は最も古い要素（最初に追加されたもの）を削除します。このアプローチはメモリの事前割り当てを必要としませんが、頻繁なスタックの反転時にガベージコレクタに追加の負荷をかける可能性があります。メモリが限られたモバイルアプリケーションでは、循環バッファの方がより好ましいままです。