FIFO Cache — asosiy tushunchalar, navbat algoritmi va qanday ishlaydi

FIFO Cache nima?

FIFO Cache (First In First Out Cache) — elementlarni boshqarish uchun navbatdan foydalanadigan sobit o'lchamli keshlar. Birinchi qo'shilgan element navbatning boshida joylashadi va to'lib ketganda birinchi bo'lib o'chiriladi. Yangi elementlar har doim oxiriga qo'shiladi va chiqarib tashlash tartibi qo'shish tartibi bilan mos kelishini kafolatlaydi.

Har bir murojaatda elementlarni qayta tartibga soluvchi LRU dan farqli o'laroq, FIFO get operatsiyalarida mavjud elementlarning o'rnini o'zgartirmaydi. Bu algoritmni to'liq deterministik qiladi: qo'shish tartibini bilgan holda, qaysi element keyingi chiqarib tashlanishini aniq bashorat qilish mumkin. Bunday bashorat qilish qobiliyati ma'lumotlarni kelish tartibida qayta ishlashni kafolatlash kerak bo'lgan real vaqt tizimlari uchun juda muhimdir.

FIFO Cache ni amalga oshirish bir nechta ma'lumot tuzilmalariga asoslanishi mumkin: maksimal samaradorlik uchun aylanma bufer (circular buffer), moslashuvchanlik uchun bog'langan ro'yxat yoki o'rnatilgan navbati bo'lmagan tillar uchun ikkita stek (Two-Stack Queue). Aylanma bufer eng yaxshi kesh-mahalliyligini va minimal qo'shimcha yukni ta'minlaydi, lekin maxSize uchun oldindan xotira ajratishni talab qiladi.

FIFO Cachening asosiy operatsiyalari

enqueue(value) operatsiyasi elementni navbatning oxiriga qo'shadi. Agar o'lcham maxSize ga yetgan bo'lsa, qo'shishdan oldin boshidagi element o'chiriladi. dequeue() operatsiyasi eng eski elementni majburiy olish uchun boshidagi elementni o'chiradi va qaytaradi. peek() operatsiyasi navbatni o'zgartirmasdan eng eski elementni ko'rish uchun boshidagi elementni o'chirmasdan qaytaradi.

FIFO Cache qanday ishlaydi

FIFO algoritmi oddiy navbatning xatti-harakatini taqlid qiladi: birinchi kirgan birinchi xizmat oladi. Keshlashtirish kontekstida bu keshta eng uzoq qolgan element joy yetishmasligida o'chirilishini anglatadi — qanchalik talab qilinishidan qat'iy nazar. Chiqarib tashlash siyosati FIFO murojaat chastotasini e'tiborsiz qoldiradi, bu algoritmning ham kuchli, ham zaif tomonidir.

Aylanma bufer orqali amalga oshirishda ikkita ko'rsatkich ishlatiladi: head (navbat boshining indeksi) va tail (oxirining indeksi). enqueue paytida element tail indeksi ostida yoziladi va tail oshiriladi. Agar tail bufer o'lchamiga yetsa, u massiv boshiga o'raladi. Agar tail head ga yetsa — navbat to'la va head siljitiladi (chiqarib tashlash). Aylanma bufer dinamik xotira ajratishni talab qilmaydi va fragmentatsiyaning oldini oladi.

FIFO Cache odatiy yuklamalar uchun 40% dan 60% gacha hit-ratio ko'rsatadi, bu LIFO dan yuqori, ammo LRU dan past. Biroq, ma'lumotlarga kirish bir tekis va issiq nuqtalar bo'lmagan stsenariylarda FIFO, sezilarli darajada kam amalga oshirish murakkabligi bilan LRU bilan solishtirish mumkin bo'lgan natijalarni ko'rsatishi mumkin. Xotira samarali ishlatiladi: elementlarni joyini o'zgartirish uchun qo'shimcha ko'rsatkichlar kerak emas.

Kesh ifloslanishi muammosi

FIFO ning asosiy kamchiligi — kesh ifloslanishiga (cache pollution) moyilligi. Agar kesha boshqa hech qachon kerak bo'lmaydigan katta hajmdagi ma'lumotlar qo'shilsa, ular asta-sekin barcha foydali elementlarni chiqarib tashlaydi va hit-ratio keskin tushadi. LRU bu muammoni qisman hal qiladi, chunki tez-tez ishlatiladigan elementlar boshiga ko'chirish orqali doimo yangilanadi, bir martaliklar esa tezroq chiqarib tashlanadi. FIFO da bir martalik ma'lumotlar navbatning tabiiy tartibida chiqarib tashlanmaguncha keshta qoladi.

FIFO, LRU va LIFO taqqoslanishi

FIFO, LRU va LIFO o'rtasidagi tanlov ma'lumotlarga kirish naqshiga va xatti-harakatni bashorat qilish talablariga bog'liq. LRU ko'pchilik stsenariylar uchun optimal, FIFO — bir tekis kirishga ega oqim ma'lumotlari uchun, LIFO — stek tuzilmalari uchun.

FIFO qayta ishlash tartibi kelish tartibi bilan mos kelishi kerak bo'lgan stsenariylar uchun ideal: ma'lumotlarni buferlash, loglash, hodisalarni qayta ishlash. LRU notekis kirish bilan keshlashtirish uchun yaxshiroq (foydalanuvchi ma'lumotlari). LIFO faqat steklar va Bekor qilish operatsiyalari uchun qo'llaniladi. Aksariyat mobil ilovalar uchun LRU standart tanlov bo'lib qoladi, ammo FIFO qattiq xotira cheklovlari yoki bashorat qilish talablari mavjud bo'lganda afzal bo'lishi mumkin.

FIFO Cache qayerda qo'llaniladi

FIFO Cache chiqarib tashlashni bashorat qilish yoki ma'lumotlarni qayta ishlash tartibi muhim bo'lgan stsenariylarda qo'llaniladi. Asosiy foydalanish holatlarini ko'rib chiqaylik.

Oqim ma'lumotlarini buferlash

Audio va video ijro etishda ma'lumotlar uzluksiz oqim bilan keladi va vaqtincha buferda saqlanadi. FIFO Cache birinchi qabul qilingan fragmentlarni dekodlashga birinchi jo'natilishini ta'minlaydi — bu kechikishlarsiz silliq ijro etishni kafolatlaydi. Bufer o'lchami oqimning bitreyti va ruxsat etilgan kechikish asosida tanlanadi: audio uchun odatda 2–5 soniya, video uchun — 10–30 soniya. FIFO bunday stsenariylar uchun idealdir, chunki ma'lumotlarni qayta tartibga solish (LRU dagi kabi) ma'noga ega emas.

Tarmoq so'rov navbatlari

Bir vaqtning o'zida tarmoq so'rovlari soni cheklanganida, FIFO Cache kutayotgan so'rovlarni saqlash uchun ishlatilishi mumkin. Birinchi qo'shilgan so'rov birinchi bajariladi, bu ilovaning turli komponentlari o'rtasida tarmoq resurslarining adolatli taqsimlanishini ta'minlaydi. Ushbu yondashuv OkHttp Dispatcher va shunga o'xshash kutubxonalarda ulanishlar hovuzini boshqarish uchun qo'llaniladi.

HTTP javoblarini keshlashtirish

Mobil qurilmalarda oddiy HTTP javob keshlari ko'pincha FIFO dan foydalanadi. So'rovlarga javoblar kelish tartibida saqlanadi va chegaraga yetganda eng eskilari o'chiriladi. LRU foydalanuvchi stsenariylari uchun yaxshiroq hit-ratio bergan bo'lsa-da, FIFO amalga oshirishda soddaroq va har bir javob uchun oxirgi kirish vaqtini saqlashni talab qilmaydi. Bir xil yuklamali API lar uchun FIFO va LRU o'rtasidagi hit-ratio farqi minimaldir.

Teginish hodisalarini qayta ishlash

Mobil ilovalarda teginish hodisalari (touch events) jestlarni tanib olishdan oldin FIFO navbatida buferlanadi. Har bir hodisa yuzaga kelish tartibida qayta ishlanishi kerak, aks holda jest noto'g'ri tanib olinadi. FIFO Cache o'lcham cheklovi bilan tez surishlar paytida buferning to'lib ketishining oldini oladi, agar ilova ularni qayta ishlashga ulgurmasa, eng eski hodisalarni rad etadi.

FIFO Cache kod namunalari

Mobil qurilmalar uchun eng samarali yondashuv — aylanma buferdan foydalangan holda Kotlin tilida FIFO Cache ni amalga oshirishni ko'rib chiqaylik.

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) {
            // eng eski elementni olib tashla
            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]
    }
}

Aylanma bufer head va tail indekslaridan foydalanadi, ular maxSize moduli bo'yicha tsiklik ravishda oshiriladi. size == maxSize bo'lganda, enqueue avval head ostidagi elementni (eng eski) o'chiradi, head ni siljitadi, so'ngra yangi elementni tail ostiga yozadi. Modulli arifmetika ko'rsatkichlarni avtomatik ravishda massiv boshiga o'raydi, ma'lumotlarni qo'lda nusxalashni istisno qiladi.

Swift da ikki stek orqali amalga oshirish

Swift da qulay alternativ — ikki stekga asoslangan FIFO navbati (Two-Stack Queue). Barcha enqueue birinchi stekka push qilinadi, dequeue paytida esa elementlar teskari tartibda ikkinchi stekka o'tkaziladi — shunday qilib dequeue operatsiyasi o'rtacha O(1) ga aylanadi.

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

Ikki stek enqueue va dequeue uchun amortizatsiyalangan O(1) murakkabligini ta'minlaydi. outStack.removeLast() chiqarib tashlashda eng eski elementni (birinchi qo'shilgan) o'chiradi. Ushbu yondashuv oldindan xotira ajratishni talab qilmaydi, ammo tez-tez stekni teskari o'girishda axlat yig'uvchiga qo'shimcha yuk yaratishi mumkin. Cheklangan xotiraga ega mobil ilovalar uchun aylanma bufer afzalroq bo'lib qoladi.