LRU Cache — چیست، الگوریتم حذف و چگونه کار می‌کند

LRU Cache چیست؟

LRU Cache (Least Recently Used Cache) — ساختار داده‌ای با اندازه ثابت است که تعداد محدودی عنصر را ذخیره می‌کند و به طور خودکار آنهایی را که کمترین دسترسی را داشته‌اند حذف می‌کند. وقتی برنامه عنصری را درخواست می‌کند، آن به بخش «تازه» کش منتقل می‌شود و عناصری که مدت‌ها استفاده نشده‌اند به سمت انتها حرکت کرده و با رسیدن به حد مجاز حذف می‌شوند.

نام «Least Recently Used» سیاست حذف را توصیف می‌کند: عنصری که طولانی‌ترین زمان در میان همه عناصر ذخیره شده استفاده نشده باشد حذف می‌شود. این بر اساس فرض محلی‌ت مراجعات (locality of reference) است — داده‌هایی که اخیراً درخواست شده‌اند با احتمال بالایی دوباره نیاز خواهند شد. به همین دلیل LRU یکی از مؤثرترین استراتژی‌های کش‌کردن برای اکثر برنامه‌ها محسوب می‌شود.

پیاده‌سازی کلاسیک LRU Cache به دو ساختار داده نیاز دارد: جدول هش برای دسترسی O(1) به هر عنصر با کلید و لیست پیوندی دوطرفه برای ردیابی ترتیب استفاده. جدول هش ارجاعات به گره‌های لیست را ذخیره می‌کند و لیست ترتیب را از جدیدترین عنصر (سر) تا قدیمی‌ترین (دنباله) حفظ می‌کند.

عملیات اصلی LRU Cache

عملیات get(key) وجود کلید را در جدول هش بررسی می‌کند. اگر عنصر پیدا شود، به سر لیست منتقل می‌شود (جدیدترین می‌شود) و مقدار آن برگردانده می‌شود. اگر پیدا نشود — null برگردانده می‌شود یا استثنا پرتاب می‌شود. عملیات put(key, value) عنصر جدیدی درج می‌کند: اگر کلید وجود داشته باشد — مقدار به‌روزرسانی شده و عنصر به سر منتقل می‌شود. اگر کش پر باشد، قبل از درج، عنصر دنباله لیست حذف می‌شود. همه عملیات در زمان ثابت O(1) انجام می‌شوند.

LRU Cache چگونه کار می‌کند

الگوریتم LRU Cache بر دو اصل استوار است: شمارنده دسترسی به ترتیب زمان و مکانیک حذف در سرریز. هر عنصر در یک گره از لیست پیوندی دوطرفه ذخیره می‌شود و اشاره‌گرهایی به این گره‌ها در جدول هش قرار دارند. در هر دسترسی به عنصر، آن از موقعیت فعلی جدا شده و به ابتدای لیست وارد می‌شود.

وقتی اندازه کش به حداکثر مقدار (maxSize) می‌رسد و درخواست درج عنصر جدید دریافت می‌شود، الگوریتم عنصر دنباله لیست پیوندی دوطرفه را حذف می‌کند — این همان عنصری است که طولانی‌ترین زمان استفاده نشده است. پس از حذف، فضا برای عنصر جدید آزاد شده و آن به سر لیست وارد می‌شود. جدول هش نیز به‌روزرسانی می‌شود: کلید قدیمی حذف و کلید جدید اضافه می‌شود.

ویژگی LRU — عدم حساسیت به الگوهای دسترسی با تکرار چرخه‌ای. اگر برنامه دوره‌ای به مجموعه داده‌ای بزرگ‌تر از اندازه کش دسترسی پیدا کند، LRU ممکن است از thrashing رنج ببرد — تعویض مکرر عناصر که هر درخواست جدید درخواست قبلی را حذف می‌کند. در چنین سناریوهایی، LFU (Least Frequently Used) یا الگوریتم‌های تطبیقی ممکن است مؤثرتر باشند.

اندازه کش و معیارها

انتخاب اندازه LRU Cache سازش بین مصرف حافظه و hit-ratio (درصد دسترسی‌های موفق) است. مقادیر معمول برای برنامه‌های موبایل: 10–20٪ از حافظه موجود برای کش تصاویر و 50–200 ورودی برای کش پاسخ‌های شبکه. Hit-ratio 80–95٪ شاخص خوبی در نظر گرفته می‌شود که در آن کش هزینه حافظه را توجیه می‌کند. برای پایش از شمارنده‌های hitCount و missCount استفاده می‌شود که در پیاده‌سازی LruCache در اندروید موجود هستند.

پیاده‌سازی 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 کلید را در جدول هش با ارجاع به گره پیدا کرده و حذف می‌کند.

پیاده‌سازی داخلی LruCache در اندروید

Android SDK کلاس آماده LruCache را در بسته android.util ارائه می‌دهد که الگوریتم LRU را با استفاده از LinkedHashMap در حالت access-order پیاده‌سازی می‌کند. کلاس thread-safe است، شمارش hit/miss را پشتیبانی می‌کند و همچنین callback entryRemoved را برای آزادسازی منابع هنگام حذف عنصر فراهم می‌کند. اندازه کش در واحدهای دلخواه (بایت، تعداد عناصر) تنظیم می‌شود — کافی است متد sizeOf را override کنید.

LRU Cache در مقابل FIFO و LIFO

هر سه الگوریتم — LRU، FIFO و LIFO — یک مسئله را حل می‌کنند: محدود کردن مصرف حافظه با حذف عناصر در سرریز. با این حال آنها از معیارهای اساساً متفاوتی برای انتخاب قربانی استفاده می‌کنند که کارایی آنها را در سناریوهای مختلف تعیین می‌کند.

FIFO قدیمی‌ترین عنصر را بر اساس زمان اضافه شدن حذف می‌کند، صرف نظر از اینکه چقدر به آن دسترسی شده است. این می‌تواند ناکارآمد باشد اگر عنصر قدیمی هنوز معتبر باشد. LRU از این نقص با در نظر گرفتن الگوی دسترسی جلوگیری می‌کند. LIFO عنصر تازه اضافه شده را حذف می‌کند — برای سناریوهای undo مفید است اما برای کش‌کردن نامناسب است زیرا داده‌های جدید اغلب بیشتر از داده‌های قدیمی نیاز می‌شوند. LRU تعادل بهینه بین پیچیدگی پیاده‌سازی و hit-ratio برای اکثر برنامه‌ها محسوب می‌شود.

نمونه کد LRU Cache

استفاده از کلاس داخلی LruCache از Android SDK برای کش‌کردن تصاویر بارگذاری شده را بررسی می‌کنیم. مثال راه‌اندازی کش با 1/8 حافظه موجود برنامه را نشان می‌دهد که توصیه استاندارد گوگل برای کش تصاویر است.

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‌ها را حذف می‌کند. از callback entryRemoved می‌توان برای فراخوانی bitmap.recycle() استفاده کرد — آزادسازی حافظه قبل از حذف.

پیاده‌سازی LRU Cache در Swift

iOS کلاس داخلی LRU Cache ندارد، اما می‌توان آن را به راحتی از طریق NSCache (که از سیاست حذف مشابه اما مستند نشده استفاده می‌کند) یا از طریق پیاده‌سازی شخصی بر اساس Dictionary + Doubly Linked List پیاده‌سازی کرد، همانطور که در زیر نشان داده شده است.

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 گره را از موقعیت فعلی جدا کرده و به ابتدای لیست وارد می‌کند. در سرریز، tail — کمترین استفاده شده‌ترین عنصر — حذف می‌شود. برای نسخه تولید، توصیه می‌شود امنیت نخ را از طریق NSLock یا صف DispatchQueue اضافه کنید.