FIFO Cache — المفاهيم الأساسية، خوارزمية الطابور وكيفية العمل

ما هو FIFO Cache؟

FIFO Cache (First In First Out Cache) هو مخزن مؤقت بحجم ثابت يستخدم طابوراً لإدارة العناصر. العنصر الأول المضافة يوضع في رأس الطابور وسيكون أول عنصر يُحذف عند حدوث تجاوز. تُضاف العناصر الجديدة دائماً إلى الذيل، مما يضمن أن ترتيب الحذف يطابق ترتيب الإضافة.

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

يمكن بناء تنفيذ FIFO Cache على عدة هياكل بيانات: مخزن مؤقت دائري (circular buffer) للأداء الأقصى، قائمة مرتبطة للمرونة، أو مكدسين (طابور ذو مكدسين) للغات التي لا تحتوي على طابور مدمج. يوفر المخزن المؤقت الدائري أفضل موقعية تخزين مؤقت وأقل حمولة إضافية، لكنه يتطلب تخصيصاً مسبقاً للذاكرة بحجم maxSize.

العمليات الأساسية لـ FIFO Cache

عملية enqueue(value) تُضيف عنصراً إلى ذيل الطابور. إذا وصل الحجم إلى maxSize، يُحذف العنصر من الرأس قبل الإضافة. عملية dequeue() تحذف وتعيد العنصر من الرأس — للاستخراج الإجباري للعنصر الأقدم. عملية peek() تعيد العنصر من الرأس دون حذف — لعرض العنصر الأقدم دون تعديل الطابور.

كيف يعمل FIFO Cache

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

عند التنفيذ عبر مخزن مؤقت دائري، يُستخدم مؤشران: head (مؤشر رأس الطابور) و tail (مؤشر الذيل). عند enqueue، يُكتب العنصر عند مؤشر tail، ويزداد tail. إذا وصل tail إلى حجم المخزن المؤقت، فإنه يلتف إلى بداية المصفوفة. إذا لحق tail بـ head، فهذا يعني أن الطابور ممتلئ، وينتقل head (حذف). المخزن المؤقت الدائري لا يتطلب تخصيصاً ديناميكياً للذاكرة ويتجنب التجزئة.

يظهر FIFO Cache نسبة إصابة (hit-ratio) تتراوح بين 40% و 60% للأحمال النمطية، وهي أعلى من LIFO ولكن أقل من LRU. ومع ذلك، في السيناريوهات حيث يكون الوصول إلى البيانات موحداً ولا توجد نقاط ساخنة، يمكن أن يُظهر FIFO نتائج مماثلة لـ LRU مع تعقيد تنفيذ أقل بكثير. تُستخدم الذاكرة بكفاءة: لا حاجة لمؤشرات إضافية لإعادة ترتيب العناصر.

مشكلة تلويث المخزن المؤقت

العيب الرئيسي لـ FIFO هو قابلية التعرض لتلويث المخزن المؤقت. إذا أُضيفت كمية كبيرة من البيانات التي لن تُستخدم مرة أخرى إلى المخزن المؤقت، فستحذف تدريجياً جميع العناصر المفيدة، وستنخفض نسبة الإصابة بشكل حاد. يحل 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

دعنا نلقي نظرة على تنفيذ FIFO Cache في Kotlin باستخدام مخزن مؤقت دائري — الأسلوب الأكثر أداءً للأجهزة المحمولة.

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 قائم على مكدسين (طابور ذو مكدسين). جميع عمليات 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()
    }
}

يوفر المكدسان تعقيداً مطفياً O(1) لـ enqueue و dequeue. outStack.removeLast() أثناء الحذف يزيل العنصر الأقدم (أول مضافة). هذا النهج لا يتطلب تخصيصاً مسبقاً للذاكرة ولكنه قد يخلق حمولة إضافية على جامع القمامة أثناء الانعكاسات المتكررة للمكدس. لتطبيقات المحمول ذات الذاكرة المحدودة، يبقى المخزن المؤقت الدائري أكثر تفضيلاً.