FIFO Cache — مفاهیم کلیدی، الگوریتم صف و نحوه کار

FIFO Cache چیست؟

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

بر خلاف LRU که عناصر را در هر دسترسی مرتب می‌کند، FIFO موقعیت عناصر موجود را در عملیات get تغییر نمی‌دهد. این الگوریتم را کاملاً قطعی می‌کند: با دانستن ترتیب اضافه شدن، می‌توان دقیقاً پیش‌بینی کرد که کدام عنصر بعدی حذف خواهد شد. چنین قابلیت پیش‌بینی برای سیستم‌های بلادرنگ که نیاز به تضمین پردازش داده‌ها به ترتیب ورود دارند، حیاتی است.

پیاده‌سازی FIFO Cache می‌تواند بر روی چندین ساختار داده ساخته شود: بافر حلقوی (circular buffer) برای حداکثر عملکرد، لیست پیوندی برای انعطاف‌پذیری یا دو پشته (Two-Stack Queue) برای زبان‌های بدون صف داخلی. بافر حلقوی بهترین محلیت کش و حداقل سربار را فراهم می‌کند، اما نیاز به تخصیص حافظه قبلی برای maxSize دارد.

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

عملیات enqueue(value) عنصر را به انتهای صف اضافه می‌کند. اگر اندازه به maxSize رسیده باشد، قبل از اضافه کردن، عنصر از ابتدا حذف می‌شود. عملیات dequeue() عنصر ابتدا را برای استخراج اجباری قدیمی‌ترین عنصر حذف و برمی‌گرداند. عملیات peek() عنصر ابتدا را بدون حذف برمی‌گرداند — برای مشاهده قدیمی‌ترین عنصر بدون تغییر صف.

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

الگوریتم FIFO رفتار یک صف معمولی را شبیه‌سازی می‌کند: اولین وارد شده، اولین خدمت دریافت می‌کند. در زمینه کش‌کردن، این به این معنی است که عنصری که بیشترین زمان را در کش گذرانده، در صورت کمبود فضا حذف خواهد شد — صرف نظر از اینکه چقدر مورد نیاز است. سیاست حذف FIFO تعداد دفعات دسترسی را نادیده می‌گیرد، که هم نقطه قوت و هم ضعف الگوریتم است.

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

FIFO Cache نسبت ضربه 40% تا 60% را برای بارهای معمولی نشان می‌دهد که بالاتر از LIFO اما پایین‌تر از LRU است. با این حال، برای سناریوهایی که دسترسی به داده یکنواخت است و نقاط داغ وجود ندارد، FIFO می‌تواند نتایج قابل مقایسه با LRU را با پیچیدگی پیاده‌سازی بسیار کمتر نشان دهد. حافظه به طور مؤثر مصرف می‌شود: نیازی به اشاره‌گرهای اضافی برای جابجایی عناصر نیست.

مشکل آلودگی کش

نقص اصلی FIFO — آسیب‌پذیری در برابر آلودگی کش (cache pollution). اگر حجم زیادی از داده‌هایی که هرگز دوباره نیاز نخواهند شد به کش اضافه شود، آنها به تدریج تمام عناصر مفید را حذف می‌کنند و نسبت ضربه به شدت کاهش می‌یابد. 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 حداقل است.

پردازش رویدادهای لمسی

در برنامه‌های موبایل، رویدادهای لمسی (touch events) قبل از پردازش ژست در صف 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 استفاده می‌کند که به صورت چرخه‌ای modulo maxSize افزایش می‌یابند. وقتی size == maxSize، enqueue ابتدا عنصر زیر head (قدیمی‌ترین) را حذف می‌کند، head را جابجا می‌کند و سپس عنصر جدید را زیر tail می‌نویسد. حساب پیمانه‌ای به طور خودکار اشاره‌گرها را به ابتدای آرایه برمی‌گرداند و کپی دستی داده را حذف می‌کند.

پیاده‌سازی در Swift با دو پشته

در Swift یک جایگزین راحت — صف FIFO مبتنی بر دو پشته (Two-Stack Queue). تمام 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() هنگام حذف، قدیمی‌ترین عنصر (اولین اضافه شده) را حذف می‌کند. این رویکرد نیاز به تخصیص حافظه قبلی ندارد، اما می‌تواند بار اضافی بر زباله‌روب در معکوس‌سازی‌های مکرر پشته ایجاد کند. برای برنامه‌های موبایل با حافظه محدود، بافر حلقوی همچنان ترجیح داده می‌شود.