LRU Cache — その概要、エビクションアルゴリズム、仕組み

LRU Cacheとは？

LRU Cache（Least Recently Used Cache）は、固定サイズのデータ構造で、限られた数の要素を保存し、アクセス頻度が最も低いものを自動的に削除します。アプリケーションが要素を要求すると、その要素はキャッシュの“新しい”部分に移動し、長期間使用されていない要素は末尾に移動して、制限に達すると削除されます。

“Least Recently Used”という名前は追い出しポリシーを説明しています：保存されているすべての要素の中で最も長く使用されていない要素が削除されます。これは参照の局所性（locality of reference）の仮定に基づいています — 最近要求されたデータは再び必要になる可能性が非常に高いです。これがLRUがほとんどのアプリケーションにとって最も効果的なキャッシング戦略の1つと考えられる理由です。

古典的なLRU Cacheの実装には2つのデータ構造が必要です：キーによる任意の要素へのO(1)アクセスのためのハッシュテーブルと、使用順序を追跡するための二重リンクリストです。ハッシュテーブルはリストノードへの参照を保存し、リストは最も新しい要素（先頭）から最も古い要素（末尾）までの順序を維持します。

LRU Cacheの基本操作

get(key)操作は、キーがハッシュテーブルに存在するか確認します。要素が見つかった場合、リストの先頭に移動し（最新になり）、その値が返されます。見つからない場合、nullが返されるか例外がスローされます。put(key, value)操作は新しい要素を挿入します：キーが既に存在する場合、値が更新され要素は先頭に移動します。キャッシュが満杯の場合、挿入前に末尾の要素が削除されます。すべての操作は定数時間O(1)で実行されます。

LRU Cacheの仕組み

LRU Cacheアルゴリズムは2つの原理に基づいています：時間順アクセスカウントとオーバーフロー時の追い出しメカニズムです。各要素は二重リンクリストのノードに保存され、これらのノードへのポインタはハッシュテーブルに保持されます。アクセスのたびに、要素は現在の位置から切り離され、リストの先頭に挿入されます。

キャッシュサイズが最大値（maxSize）に達し、新しい要素の挿入要求が来ると、アルゴリズムは二重リンクリストの末尾要素を削除します — これが最も最近使用されていない要素です。削除後、新しい要素のためのスペースが解放され、リストの先頭に挿入されます。ハッシュテーブルはそれに応じて更新されます：古いキーが削除され、新しいキーが追加されます。

LRUの特徴は、周期的な繰り返しを持つアクセスパターンに対する感度です。アプリケーションがキャッシュサイズよりも大きなデータセットに定期的にアクセスする場合、LRUはスラッシング（新しい要求が毎回前の要素を追い出す頻繁な要素置換）に悩まされる可能性があります。このようなシナリオでは、LFU（Least Frequently Used）または適応的アルゴリズムがより効果的です。

キャッシュサイズとメトリクス

LRU Cacheのサイズ選択は、メモリ消費とヒット率（成功したアクセスの割合）のトレードオフです。モバイルアプリケーションの一般的な値：画像キャッシュには利用可能メモリの10～20%、ネットワーク応答キャッシュには50～200エントリ。ヒット率80～95%は良好と見なされ、キャッシュがメモリコストを正当化します。監視には、AndroidのLruCache実装で利用可能なhitCountおよびmissCountカウンタが使用されます。

LRU Cacheの実装：HashMap + Doubly Linked List

標準的なLRU Cacheの実装は、ハッシュテーブルと二重リンクリストの組み合わせを使用します。ハッシュテーブルはキーによる任意のノードへのO(1)アクセスを提供し、二重リンクリストはO(1)でのノードの先頭への移動と末尾からの削除を可能にします。重要なのは、リストが二重リンクであることです：これにより、すべての要素を反復処理することなく、リストの途中からノードを切り離すことができます。

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

実装では、各ノード（Node）は値と前後のノードへの参照を保存します。番兵ノードheadとtailはエッジケースを簡素化します — 挿入と削除時にnullをチェックする必要がありません。getメソッドは見つかったノードを先頭に移動し、putはオーバーフロー時に末尾要素を削除します。別のメソッドremoveKeyByValueはノード参照によってハッシュテーブル内のキーを見つけて削除します。

Androidにおける組み込みLruCache実装

Android SDKはandroid.utilパッケージに既製のLruCacheクラスを提供しており、access-orderモードでLinkedHashMapを使用してLRUアルゴリズムを実装しています。このクラスはスレッドセーフで、hit/missカウントをサポートし、要素追い出し時のリソースクリーンアップのためのentryRemovedコールバックを提供します。キャッシュサイズは任意の単位（バイト、要素数）で設定されます — sizeOfメソッドをオーバーライドするだけです。

LRU Cache vs FIFOおよびLIFO

3つのアルゴリズム — LRU、FIFO、LIFO — は同じ問題を解決します：オーバーフロー時に要素を追い出してメモリ消費を制限します。しかし、それらは犠牲者を選択するための根本的に異なる基準を使用しており、それが異なるシナリオでの効果を決定します。

FIFOは挿入時間に基づいて最も古い要素を追い出し、アクセス頻度に関係なく行います。古い要素がまだ関連性がある場合、これは非効率的です。LRUはアクセスパターンを考慮することでこの欠点を回避します。LIFOは最も最近追加された要素を追い出します — 元に戻すシナリオには有用ですが、新しいデータが古いデータよりも必要なことが多いため、キャッシングには不適切です。LRUは、ほとんどのアプリケーションにおいて実装の複雑さとヒット率の最適なバランスと考えられています。

LRU Cacheのコード例

ダウンロードした画像をキャッシュするために、Android SDKの組み込みLruCacheクラスの使用を考えてみましょう。この例では、アプリケーションの利用可能メモリの1/8にキャッシュを初期化する方法を示しています。これはGoogleの標準的な画像キャッシュ推奨事項です。

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

sizeOfメソッドは、cacheSizeが指定されているのと同じ単位で要素のサイズを返します。ここではキロバイト単位のBitmapサイズが使用されています（rowBytes × height / 1024）。全要素のsizeOfの合計がcacheSizeを超えると、LruCacheは自動的に最も最近使用されていないBitmapを追い出します。entryRemovedコールバックはbitmap.recycle()を呼び出すために使用できます — 追い出し前にメモリを解放します。

SwiftでのLRU Cache実装

iOSには組み込みのLRU Cacheクラスはありませんが、NSCache（同様だが文書化されていない追い出しポリシーを使用）またはDictionary + 二重リンクリストによるカスタム実装を使用して簡単に実装できます。以下に示します。

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

このSwift実装では、Nodeはvalue、next、prevフィールドを持つ内部クラスです。moveToHeadメソッドはノードを現在の位置から切り離してリストの先頭に挿入します。オーバーフロー時には、末尾（最も最近使用されていない要素）が削除されます。本番環境では、NSLockまたはDispatchQueueによるスレッドセーフの追加が推奨されます。