FIFO Cache — əsas anlayışlar, növbə alqoritmi və işləmə prinsipi

FIFO Cache nədir?

FIFO Cache (First In First Out Cache) — elementləri idarə etmək üçün növbədən istifadə edən sabit ölçülü keşdir. İlk əlavə edilən element növbənin başında yerləşir və daşma zamanı ilk silinən olacaq. Yeni elementlər həmişə quyruğa əlavə edilir, bu da sıradan çıxarma ardıcıllığının əlavə etmə ardıcıllığı ilə üst-üstə düşməsini təmin edir.

Hər müraciətdə elementləri yenidən sıralayan LRU-dan fərqli olaraq, FIFO get əməliyyatlarında mövcud elementlərin yerini dəyişmir. Bu, alqoritmi tam deterministik edir: əlavə etmə ardıcıllığını bilərək, hansı elementin növbəti sıradan çıxarılacağını dəqiq proqnozlaşdırmaq olar. Belə proqnozlaşdırıla bilmə, məlumatların daxil olma ardıcıllığında emalını təmin etmək tələb olunan real vaxt sistemləri üçün kritikdir.

FIFO Cache-in reallaşdırılması bir neçə məlumat strukturu üzərində qurula bilər: maksimum performans üçün dairəvi bufer (circular buffer), çeviklik üçün əlaqəli siyahı və ya daxili növbəsi olmayan dillər üçün iki yığın (Two-Stack Queue). Dairəvi bufer ən yaxşı keş-lokallığı və minimal yük təmin edir, lakin maxSize üçün əvvəlcədən yaddaş ayrılması tələb edir.

FIFO Cache-in əsas əməliyyatları

enqueue(value) əməliyyatı elementi növbənin quyruğuna əlavə edir. Ölçü maxSize-a çatdıqda, əlavə etmədən əvvəl başdan olan element silinir. dequeue() əməliyyatı ən köhnə elementi məcburi çıxarmaq üçün başdakı elementi silir və qaytarır. peek() əməliyyatı növbəni dəyişmədən ən köhnə elementə baxmaq üçün başdakı elementi silmədən qaytarır.

FIFO Cache necə işləyir

FIFO alqoritmi adi növbənin davranışını təqlid edir: birinci daxil olan birinci xidmət alır. Keşləşdirmə kontekstində bu o deməkdir ki, keşdə ən uzun qalmış element yer çatışmazlığında silinəcək — nə qədər tələb olunmasından asılı olmayaraq. Sıradan çıxarma siyasəti FIFO müraciət tezliyini nəzərə almır, bu da alqoritmin həm güclü, həm də zəif tərəfidir.

Dairəvi bufer vasitəsilə reallaşdırmada iki göstərici istifadə olunur: head (növbənin baş indeksi) və tail (quyruq indeksi). enqueue zamanı element tail indeksi altında yazılır və tail artırılır. Tail bufer ölçüsünə çatdıqda, massivin əvvəlinə sarınır. Tail head-ə çatarsa — növbə doludur və head sürüşdürülür (sıradan çıxarma). Dairəvi bufer dinamik yaddaş ayrılması tələb etmir və fraqmentasiyanın qarşısını alır.

FIFO Cache tipik yüklər üçün 40% -dən 60% -ə qədər hit-ratio nümayiş etdirir ki, bu da LIFO-dan yüksək, lakin LRU-dan aşağıdır. Bununla belə, məlumatlara girişin bərabər olduğu və isti nöqtələrin olmadığı ssenarilərdə FIFO, əhəmiyyətli dərəcədə aşağı reallaşdırma mürəkkəbliyi ilə LRU ilə müqayisə edilə bilən nəticələr göstərə bilər. Yaddaş səmərəli istifadə olunur: elementlərin yerlərinin dəyişdirilməsi üçün əlavə göstəricilər tələb olunmur.

Keş çirklənməsi problemi

FIFO-nun əsas çatışmazlığı keş çirklənməsinə (cache pollution) həssaslığıdır. Əgər keşə bir daha lazım olmayacaq böyük həcmdə məlumat əlavə edilərsə, onlar tədricən bütün faydalı elementləri sıradan çıxaracaq və hit-ratio kəskin düşəcək. LRU bu problemi qismən həll edir, çünki tez-tez istifadə olunan elementlər başa daşınmaqla daim təzələnəcək, birdəfəlik elementlər isə daha tez sıradan çıxarılacaq. FIFO-da birdəfəlik məlumatlar növbənin təbii qaydasında sıradan çıxarılana qədər keşdə qalır.

FIFO, LRU və LIFO müqayisəsi

FIFO, LRU və LIFO arasında seçim məlumatlara giriş nümunəsindən və davranışın proqnozlaşdırıla bilməsi tələblərindən asılıdır. LRU əksər ssenarilər üçün optimaldır, FIFO — bərabər girişli axın məlumatları üçün, LIFO — yığın strukturları üçün.

FIFO emal ardıcıllığının daxil olma ardıcıllığı ilə üst-üstə düşməli olduğu ssenarilər üçün idealdır: məlumat buferləşdirilməsi, jurnal salma, hadisələrin emalı. LRU qeyri-bərabər girişli keşləşdirmə üçün daha yaxşıdır (istifadəçi məlumatları). LIFO yalnız yığınlar və Geri Qaytarma əməliyyatları üçün tətbiq olunur. Əksər mobil tətbiqlər üçün LRU standart seçim olaraq qalır, lakin FIFO ciddi yaddaş məhdudiyyətləri və ya proqnozlaşdırıla bilmə tələbləri olduqda daha üstün ola bilər.

FIFO Cache harada tətbiq olunur

FIFO Cache sıradan çıxarmanın proqnozlaşdırıla bilməsi və ya məlumat emalı ardıcıllığının əhəmiyyətli olduğu ssenarilərdə tətbiq tapır. Əsas istifadə hallarını nəzərdən keçirək.

Axın məlumatlarının buferləşdirilməsi

Audio və video oxutma zamanı məlumatlar fasiləsiz axınla gəlir və müvəqqəti olaraq buferdə saxlanılır. FIFO Cache ilk qəbul edilmiş fraqmentlərin dekodlaşdırmaya ilk göndəriləcəyini təmin edir — bu, gecikməsiz hamar oxutmanı təmin edir. Bufer ölçüsü axının bitrate və icazə verilən gecikmə əsasında seçilir: audio üçün tipik 2–5 saniyə, video üçün — 10–30 saniyə. FIFO bu cür ssenarilər üçün idealdır, çünki məlumatların yenidən sıralanması (LRU-da olduğu kimi) mənasızdır.

Şəbəkə sorğu növbələri

Eyni vaxtda şəbəkə sorğularının sayı məhdudlaşdırıldıqda, FIFO Cache gözləyən sorğuları saxlamaq üçün istifadə edilə bilər. İlk əlavə edilmiş sorğu ilk icra olunacaq, bu da tətbiqin müxtəlif komponentləri arasında şəbəkə resurslarının ədalətli bölüşdürülməsini təmin edir. Bu yanaşma OkHttp Dispatcher və oxşar kitabxanalarda bağlantı hovuzunun idarə edilməsi üçün istifadə olunur.

HTTP cavablarının keşləşdirilməsi

Mobil cihazlarda sadə HTTP cavab keşləri tez-tez FIFO istifadə edir. Sorğulara cavablar daxil olma ardıcıllığında saxlanılır, limitə çatdıqda isə ən köhnələr silinir. LRU istifadəçi ssenariləri üçün daha yaxşı hit-ratio versə də, FIFO reallaşdırmada daha sadədir və hər cavab üçün son giriş vaxtının saxlanmasını tələb etmir. Vahid yükü olan API-lər üçün FIFO və LRU arasında hit-ratio fərqi minimaldır.

Sensor hadisələrinin emalı

Mobil tətbiqlərdə toxunma hadisələri (touch events) jest emalından əvvəl FIFO növbəsində buferləşdirilir. Hər bir hadisə yaranma ardıcıllığında emal edilməlidir, əks halda jest səhv tanınacaq. FIFO Cache ölçü məhdudiyyəti ilə sürətli sürüşdürmələr zamanı buferin daşmasının qarşısını alır, tətbiq emal edə bilmədikdə ən köhnə hadisələri rədd edir.

FIFO Cache kod nümunələri

Mobil cihazlar üçün ən məhsuldar yanaşma olan dairəvi buferdən istifadə edərək Kotlin dilində FIFO Cache reallaşdırılmasını nəzərdən keçirək.

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) {
            // ən köhnə elementi çıxar
            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]
    }
}

Dairəvi bufer head və tail indekslərindən istifadə edir, onlar maxSize moduluna görə tsiklik olaraq artırılır. size == maxSize olduqda, enqueue əvvəlcə head altındakı elementi (ən köhnə) silir, head-i sürüşdürür, sonra isə yeni elementi tail altına yazır. Modul hesabı göstəriciləri avtomatik olaraq massivin əvvəlinə sarır, məlumatların əl ilə kopyalanmasını aradan qaldırır.

Swift-də iki yığın vasitəsilə reallaşdırma

Swift-də rahat alternativ — iki yığına əsaslanan FIFO növbəsidir (Two-Stack Queue). Bütün enqueue əməliyyatları birinci yığına push edilir, dequeue zamanı isə elementlər tərs qaydada ikinci yığına köçürülür — beləliklə dequeue əməliyyatı orta hesabla O(1) olur.

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

İki yığın enqueue və dequeue üçün amortizasiya olunmuş O(1) mürəkkəbliyi təmin edir. outStack.removeLast() sıradan çıxarma zamanı ən köhnə elementi (ilk əlavə edilən) silir. Bu yanaşma əvvəlcədən yaddaş ayrılması tələb etmir, lakin tez-tez yığın tərs çevirmələrində zibil yığana əlavə yük yarada bilər. Məhdud yaddaşlı mobil tətbiqlər üçün dairəvi bufer daha üstün olaraq qalır.