FIFO Cache — βασικές έννοιες, αλγόριθμος ουράς και πώς λειτουργεί

Τι είναι το FIFO Cache;

FIFO Cache (First In First Out Cache) — προσωρινή μνήμη σταθερού μεγέθους που χρησιμοποιεί ουρά για τη διαχείριση στοιχείων. Το πρώτο στοιχείο που προστέθηκε βρίσκεται στην κεφαλή της ουράς και θα αφαιρεθεί πρώτο κατά την υπερχείλιση. Νέα στοιχεία προστίθενται πάντα στο τέλος, διασφαλίζοντας ότι η σειρά αποβολής συμπίπτει με τη σειρά προσθήκης.

Σε αντίθεση με το LRU, που αναδιατάσσει τα στοιχεία σε κάθε πρόσβαση, το FIFO δεν αλλάζει τη θέση των υπαρχόντων στοιχείων στις λειτουργίες get. Αυτό καθιστά τον αλγόριθμο πλήρως ντετερμινιστικό: γνωρίζοντας τη σειρά προσθήκης, μπορεί να προβλεφθεί με ακρίβεια ποιο στοιχείο θα αποβληθεί επόμενο. Αυτή η προβλεψιμότητα είναι κρίσιμη για συστήματα πραγματικού χρόνου όπου πρέπει να διασφαλίζεται η επεξεργασία δεδομένων με τη σειρά άφιξης.

Η υλοποίηση του FIFO Cache μπορεί να βασιστεί σε πολλές δομές δεδομένων: κυκλικό buffer (circular buffer) για μέγιστη απόδοση, συνδεδεμένη λίστα για ευελιξία ή δύο στοίβες (Two-Stack Queue) για γλώσσες χωρίς ενσωματωμένη ουρά. Ο κυκλικός buffer παρέχει την καλύτερη τοπικότητα προσωρινής μνήμης και ελάχιστο πρόσθετο κόστος, αλλά απαιτεί προκαταβολική εκχώρηση μνήμης για maxSize.

Βασικές λειτουργίες του FIFO Cache

Η λειτουργία enqueue(value) προσθέτει ένα στοιχείο στο τέλος της ουράς. Εάν το μέγεθος έχει φτάσει το maxSize, πριν από την προσθήκη αφαιρείται το στοιχείο από την αρχή. Η λειτουργία dequeue() αφαιρεί και επιστρέφει το στοιχείο από την αρχή — για υποχρεωτική εξαγωγή του παλαιότερου στοιχείου. Η λειτουργία peek() επιστρέφει το στοιχείο της κεφαλής χωρίς αφαίρεση — για προβολή του παλαιότερου στοιχείου χωρίς αλλαγή της ουράς.

Πώς λειτουργεί το FIFO Cache

Ο αλγόριθμος FIFO μιμείται τη συμπεριφορά μιας συνηθισμένης ουράς: πρώτος εισερχόμενος, πρώτος εξυπηρετούμενος. Στο πλαίσιο της προσωρινής αποθήκευσης, αυτό σημαίνει ότι το στοιχείο που έχει μείνει περισσότερο στην προσωρινή μνήμη θα αφαιρεθεί σε περίπτωση έλλειψης χώρου — ανεξάρτητα από το πόσο ζητούμενο είναι. Η πολιτική αποβολής FIFO αγνοεί τη συχνότητα πρόσβασης, που είναι ταυτόχρονα δυνατό και αδύνατο σημείο του αλγορίθμου.

Στην υλοποίηση με κυκλικό buffer χρησιμοποιούνται δύο δείκτες: head (δείκτης κεφαλής της ουράς) και tail (δείκτης τέλους). Κατά την enqueue, το στοιχείο εγγράφεται στον δείκτη tail και το tail αυξάνεται. Εάν το tail φτάσει το μέγεθος του buffer, τυλίγεται πίσω στην αρχή του πίνακα. Εάν το tail φτάσει το head — η ουρά είναι γεμάτη και το head μετακινείται (αποβολή). Ο κυκλικός buffer δεν απαιτεί δυναμική εκχώρηση μνήμης και αποφεύγει τον κατακερματισμό.

Το FIFO Cache εμφανίζει hit-ratio από 40% έως 60% για τυπικά φορτία, που είναι υψηλότερο από το LIFO αλλά χαμηλότερο από το LRU. Ωστόσο, για σενάρια όπου η πρόσβαση σε δεδομένα είναι ομοιόμορφη και δεν υπάρχουν καυτά σημεία, το FIFO μπορεί να δείξει αποτελέσματα συγκρίσιμα με το LRU με σημαντικά χαμηλότερη πολυπλοκότητα υλοποίησης. Η μνήμη χρησιμοποιείται αποτελεσματικά: δεν απαιτούνται πρόσθετοι δείκτες για την αναδιάταξη στοιχείων.

Το πρόβλημα της ρύπανσης της προσωρινής μνήμης

Το κύριο μειονέκτημα του FIFO — η ευπάθεια στη ρύπανση της προσωρινής μνήμης (cache pollution). Εάν προστεθεί μεγάλος όγκος δεδομένων που δεν θα χρειαστούν ποτέ ξανά στην προσωρινή μνήμη, θα αφαιρέσουν σταδιακά όλα τα χρήσιμα στοιχεία και το hit-ratio θα πέσει απότομα. Το LRU λύνει εν μέρει αυτό το πρόβλημα, καθώς τα συχνά χρησιμοποιούμενα στοιχεία ανανεώνονται συνεχώς μεταφερόμενα στην κεφαλή, ενώ τα εφάπαξ αποβάλλονται ταχύτερα. Στο FIFO, τα εφάπαξ δεδομένα παραμένουν στην προσωρινή μνήμη μέχρι να αποβληθούν με τη φυσική σειρά της ουράς.

Σύγκριση FIFO, LRU και LIFO

Η επιλογή μεταξύ FIFO, LRU και LIFO εξαρτάται από το μοτίβο πρόσβασης δεδομένων και τις απαιτήσεις προβλεψιμότητας συμπεριφοράς. Το LRU είναι βέλτιστο για τα περισσότερα σενάρια, το FIFO — για ροές δεδομένων με ομοιόμορφη πρόσβαση, το LIFO — για δομές στοίβας.

FIFO είναι ιδανικό για σενάρια όπου η σειρά επεξεργασίας πρέπει να συμπίπτει με τη σειρά άφιξης: προσωρινή αποθήκευση δεδομένων, καταγραφή, επεξεργασία συμβάντων. LRU είναι καλύτερο για προσωρινή αποθήκευση με ανομοιόμορφη πρόσβαση (δεδομένα χρήστη). LIFO εφαρμόζεται μόνο για στοίβες και λειτουργίες Αναίρεσης. Για τις περισσότερες εφαρμογές κινητών, το LRU παραμένει η προεπιλεγμένη επιλογή, αλλά το FIFO μπορεί να είναι προτιμότερο σε αυστηρούς περιορισμούς μνήμης ή απαιτήσεις προβλεψιμότητας.

Πού εφαρμόζεται το FIFO Cache

Το FIFO Cache βρίσκει εφαρμογή σε σενάρια όπου η προβλεψιμότητα αποβολής ή η σειρά επεξεργασίας δεδομένων έχει σημασία. Ας εξετάσουμε τις κύριες περιπτώσεις χρήσης.

Προσωρινή αποθήκευση ροών δεδομένων

Κατά την αναπαραγωγή ήχου και βίντεο, τα δεδομένα φτάνουν σε συνεχή ροή και αποθηκεύονται προσωρινά σε ένα buffer. Το FIFO Cache διασφαλίζει ότι τα πρώτα ληφθέντα τμήματα θα σταλούν πρώτα για αποκωδικοποίηση — αυτό εγγυάται ομαλή αναπαραγωγή χωρίς καθυστερήσεις. Το μέγεθος του buffer επιλέγεται βάσει του bitrate της ροής και της επιτρεπόμενης καθυστέρησης: για ήχο συνήθως 2–5 δευτερόλεπτα, για βίντεο — 10–30 δευτερόλεπτα. Το FIFO είναι ιδανικό για τέτοια σενάρια, καθώς η αναδιάταξη δεδομένων (όπως στο LRU) δεν έχει νόημα.

Ουρές αιτημάτων δικτύου

Κατά τον περιορισμό του αριθμού ταυτόχρονων αιτημάτων δικτύου, το FIFO Cache μπορεί να χρησιμοποιηθεί για την αποθήκευση αιτημάτων σε αναμονή. Το πρώτο προστιθέμενο αίτημα θα εκτελεστεί πρώτο, διασφαλίζοντας δίκαιη κατανομή των πόρων δικτύου μεταξύ διαφορετικών στοιχείων της εφαρμογής. Αυτή η προσέγγιση χρησιμοποιείται στο OkHttp Dispatcher και παρόμοιες βιβλιοθήκες για τη διαχείριση της δεξαμενής συνδέσεων.

Προσωρινή αποθήκευση αποκρίσεων HTTP

Οι απλές προσωρινές μνήμες αποκρίσεων HTTP σε κινητές συσκευές χρησιμοποιούν συχνά FIFO. Οι αποκρίσεις σε αιτήματα αποθηκεύονται με τη σειρά άφιξης και κατά την επίτευξη του ορίου αφαιρούνται οι παλαιότερες. Αν και το LRU θα έδινε καλύτερο hit-ratio για σενάρια χρήστη, το FIFO είναι απλούστερο στην υλοποίηση και δεν απαιτεί αποθήκευση του χρόνου τελευταίας πρόσβασης για κάθε απόκριση. Για API με ομοιόμορφο φορτίο, η διαφορά hit-ratio μεταξύ FIFO και LRU είναι ελάχιστη.

Επεξεργασία γεγονότων αφής

Σε εφαρμογές κινητών, τα γεγονότα αφής (touch events) αποθηκεύονται προσωρινά σε μια ουρά FIFO πριν από την αναγνώριση χειρονομιών. Κάθε γεγονός πρέπει να υποβληθεί σε επεξεργασία με τη σειρά εμφάνισης, διαφορετικά η χειρονομία θα αναγνωριστεί λανθασμένα. Το FIFO Cache με περιορισμό μεγέθους αποτρέπει την υπερχείλιση του buffer σε γρήγορες σύρσεις, απορρίπτοντας τα παλαιότερα γεγονότα εάν η εφαρμογή δεν προλαβαίνει να τα επεξεργαστεί.

Παραδείγματα κώδικα FIFO Cache

Ας εξετάσουμε την υλοποίηση του FIFO Cache σε Kotlin με χρήση κυκλικού buffer — της πιο αποδοτικής προσέγγισης για κινητές συσκευές.

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]
    }
}

Ο κυκλικός buffer χρησιμοποιεί δείκτες head και tail, οι οποίοι αυξάνονται κυκλικά modulo maxSize. Όταν size == maxSize, η enqueue πρώτα αφαιρεί το στοιχείο στο head (παλαιότερο), μετακινεί το head και στη συνέχεια γράφει το νέο στοιχείο στο tail. Η αριθμητική modulo τυλίγει αυτόματα τους δείκτες πίσω στην αρχή του πίνακα, εξαλείφοντας τη μη αυτόματη αντιγραφή δεδομένων.

Υλοποίηση σε 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() κατά την αποβολή αφαιρεί το παλαιότερο στοιχείο (το πρώτο που προστέθηκε). Αυτή η προσέγγιση δεν απαιτεί προκαταβολική εκχώρηση μνήμης, αλλά μπορεί να δημιουργήσει πρόσθετο φορτίο στον συλλέκτη σκουπιδιών σε συχνές αντιστροφές στοίβας. Για εφαρμογές κινητών με περιορισμένη μνήμη, ο κυκλικός buffer παραμένει προτιμότερος.