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 إدخال لذاكرة تخزين استجابات الشبكة المؤقتة. نسبة نجاح 80–95% تُعتبر جيدة، حيث تبرر ذاكرة التخزين المؤقت تكاليف الذاكرة. للمراقبة، تُستخدم عدّادات hitCount و missCount المتوفرة في تنفيذ LruCache في Android.

تنفيذ LRU Cache: HashMap + قائمة مرتبطة مضاعفة

يستخدم التنفيذ المعياري لـ 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 لنظام Android فئة LruCache جاهزة في حزمة android.util، والتي تنفذ خوارزمية LRU باستخدام LinkedHashMap في وضع access-order. الفئة آمنة للخيوط، وتدعم عدّ hit/miss، وتوفر رد الاتصال entryRemoved لتنظيف الموارد عند إخلاء عنصر. يُحدد حجم ذاكرة التخزين المؤقت بوحدات عشوائية (بايتات، عدد عناصر) — يكفي إعادة تعريف أسلوب sizeOf.

LRU Cache مقابل FIFO و LIFO

تحل الخوارزميات الثلاث — LRU و FIFO و LIFO — نفس المشكلة: تحديد استهلاك الذاكرة عن طريق إخلاء العناصر عند التجاوز. لكنها تستخدم معايير مختلفة جوهريًا لاختيار الضحية، مما يحدد فعاليتها في السيناريوهات المختلفة.

FIFO يخلو أقدم عنصر بوقت الإدراج، بغض النظر عن عدد مرات الوصول إليه. قد يكون هذا غير فعال إذا كان العنصر القديم لا يزال ذا صلة. يتجنب LRU هذا العيب من خلال مراعاة نمط الوصول. LIFO يخلو العنصر المُضاف مؤخرًا — مفيد لسيناريوهات التراجع، لكنه غير مناسب للتخزين المؤقت، لأن البيانات الجديدة غالبًا ما تكون أكثر احتياجًا من القديمة. يُعتبر LRU التوازن الأمثل بين تعقيد التنفيذ ونسبة النجاح لمعظم التطبيقات.

أمثلة كود LRU Cache

لننظر في استخدام الفئة المدمجة LruCache من SDK لنظام Android لتخزين الصور المُنزَّلة مؤقتًا. يوضح المثال تهيئة ذاكرة تخزين مؤقت بحجم 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 تلقائيًا أقل Bitmaps استخدامًا مؤخرًا. يمكن استخدام رد الاتصال entryRemoved لاستدعاء bitmap.recycle() — لتحرير الذاكرة قبل الإخلاء.

تنفيذ LRU Cache في Swift

لا يحتوي 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.