FIFO Cache — کلیدی تصورات، قطار الگورتھم اور یہ کیسے کام کرتا ہے

FIFO Cache کیا ہے؟

FIFO Cache (First In First Out Cache) ایک مقررہ سائز کا کیش ہے جو عناصر کے انتظام کے لیے قطار استعمال کرتا ہے۔ پہلا شامل کردہ عنصر قطار کے سر پر رکھا جاتا ہے اور بہاؤ کی صورت میں سب سے پہلے ہٹایا جائے گا۔ نئے عناصر ہمیشہ دم میں شامل کیے جاتے ہیں، اس بات کو یقینی بناتے ہوئے کہ ہٹانے کا ترتیب شامل کرنے کے ترتیب سے مطابقت رکھتا ہے۔

LRU کے برعکس، جو ہر رسائی پر عناصر کو دوبارہ ترتیب دیتا ہے، FIFO get درخواستوں پر موجودہ عناصر کی پوزیشن نہیں بدلتا۔ یہ الگورتھم کو مکمل طور پر تعیناتی بناتا ہے: شامل کرنے کا ترتیب جان کر، درست پیش گوئی کی جا سکتی ہے کہ اگلا کون سا عنصر ہٹایا جائے گا۔ یہ پیش گوئی ریئل ٹائم سسٹمز کے لیے اہم ہے جہاں ڈیٹا کو آمد کے ترتیب میں پروسیس کیا جانا چاہیے۔

FIFO Cache کا نفاذ کئی ڈیٹا ساختوں پر بنایا جا سکتا ہے: زیادہ سے زیادہ کارکردگی کے لیے سرکلر بفر، لچک کے لیے لنکڈ لسٹ، یا بغیر بلٹ ان قطار والی زبانوں کے لیے دو اسٹیک (ٹو-اسٹیک قطار)۔ سرکلر بفر بہترین کیش لوکلٹی اور کم سے کم اوور ہیڈ فراہم کرتا ہے، لیکن 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% تک hit-ratio ظاہر کرتا ہے، جو LIFO سے زیادہ ہے لیکن LRU سے کم ہے۔ تاہم، ایسے منظرناموں کے لیے جہاں ڈیٹا تک رسائی یکساں ہے اور کوئی گرم مقامات نہیں ہیں، FIFO نمایاں طور پر کم نفاذ کی پیچیدگی کے ساتھ LRU کے برابر نتائج دکھا سکتا ہے۔ میموری موثر طریقے سے استعمال ہوتی ہے: عناصر کی دوبارہ ترتیب کے لیے اضافی پوائنٹرز کی ضرورت نہیں ہے۔

کیش آلودگی کا مسئلہ

FIFO کا بنیادی نقص کیش آلودگی کے لیے حساسیت ہے۔ اگر کیش میں بڑی مقدار میں ڈیٹا شامل کیا جائے جس کی پھر کبھی ضرورت نہیں ہوگی، تو یہ دھیرے دھیرے تمام مفید عناصر کو ہٹا دے گا اور hit-ratio تیزی سے گر جائے گا۔ 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 صارف کے منظرناموں کے لیے بہتر hit-ratio دے گا، FIFO نفاذ میں آسان ہے اور ہر جواب کے لیے آخری رسائی کا وقت محفوظ کرنے کی ضرورت نہیں ہے۔ یکساں بوجھ والے API کے لیے، FIFO اور LRU کے درمیان hit-ratio میں فرق کم سے کم ہے۔

ٹچ ایونٹ پروسیسنگ

موبائل ایپلیکیشنز میں، ٹچ ایونٹس اشاروں کی پروسیسنگ سے پہلے FIFO قطار میں بفر کیے جاتے ہیں۔ ہر ایونٹ کو واقع ہونے کے ترتیب میں پروسیس کیا جانا چاہیے، ورنہ اشارہ غلط طریقے سے پہچانا جائے گا۔ سائز کی حد کے ساتھ FIFO Cache تیز سوائپ کے دوران بفر کے بہاؤ کو روکتا ہے، اگر ایپلیکیشن پروسیس نہ کر سکے تو قدیم ترین ایونٹس کو رد کر دیتا ہے۔

FIFO Cache کوڈ مثالیں

آئیے سرکلر بفر استعمال کرتے ہوئے Kotlin میں FIFO Cache کے نفاذ کو دیکھتے ہیں — موبائل آلات کے لیے سب سے زیادہ کارگر طریقہ۔

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

دو اسٹیک enqueue اور dequeue کے لیے معاوضہ شدہ O(1) پیچیدگی فراہم کرتے ہیں۔ ہٹانے کے دوران outStack.removeLast() قدیم ترین عنصر (پہلے شامل کردہ) کو ہٹاتا ہے۔ اس طریقہ کو میموری کی پیشگی تقسیم کی ضرورت نہیں ہے لیکن بار بار اسٹیک الٹنے کے دوران کچرا جمع کرنے والے پر اضافی بوجھ ڈال سکتا ہے۔ محدود میموری والی موبائل ایپلیکیشنز کے لیے، سرکلر بفر زیادہ ترجیحی رہتا ہے۔