LRU Cache — τι είναι, αλγόριθμος εκτόπισης και πώς λειτουργεί

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

LRU Cache (Least Recently Used Cache) — μια δομή δεδομένων σταθερού μεγέθους που αποθηκεύει περιορισμένο αριθμό στοιχείων και διαγράφει αυτόματα αυτά που έχουν προσπελαστεί λιγότερο συχνά. Όταν η εφαρμογή ζητά ένα στοιχείο, μετακινείται στο «φρέσκο» μέρος της κρυφής μνήμης και τα στοιχεία που δεν έχουν χρησιμοποιηθεί για μεγάλο χρονικό διάστημα μετατοπίζονται προς το τέλος και διαγράφονται όταν επιτευχθεί το όριο.

Η ονομασία «Least Recently Used» περιγράφει την πολιτική εκτόπισης: διαγράφεται το στοιχείο που δεν χρησιμοποιήθηκε για το μεγαλύτερο χρονικό διάστημα μεταξύ όλων των αποθηκευμένων. Αυτό βασίζεται στην υπόθεση της τοπικότητας αναφορών (locality of reference) — τα δεδομένα που ζητήθηκαν πρόσφατα είναι πολύ πιθανό να χρειαστούν ξανά. Γι' αυτό το LRU θεωρείται μία από τις πιο αποτελεσματικές στρατηγικές προσωρινής αποθήκευσης για τις περισσότερες εφαρμογές.

Η κλασική υλοποίηση του LRU Cache απαιτεί δύο δομές δεδομένων: έναν πίνακα κατακερματισμού για πρόσβαση O(1) σε οποιοδήποτε στοιχείο μέσω κλειδιού και μια διπλά συνδεδεμένη λίστα για την παρακολούθηση της σειράς χρήσης. Ο πίνακας κατακερματισμού αποθηκεύει αναφορές στους κόμβους της λίστας και η λίστα διατηρεί τη σειρά από το νεότερο στοιχείο (κεφαλή) έως το παλαιότερο (ουρά).

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

Η λειτουργία get(key) ελέγχει την παρουσία του κλειδιού στον πίνακα κατακερματισμού. Αν το στοιχείο βρεθεί, μετακινείται στην κεφαλή της λίστας (γίνεται το νεότερο) και επιστρέφεται η τιμή του. Αν δεν βρεθεί — επιστρέφεται null ή ρίχνεται εξαίρεση. Η λειτουργία put(key, value) εισάγει ένα νέο στοιχείο: αν το κλειδί υπάρχει ήδη — η τιμή ενημερώνεται και το στοιχείο μετακινείται στην κεφαλή. Αν η κρυφή μνήμη είναι γεμάτη, πριν από την εισαγωγή διαγράφεται το στοιχείο της ουράς. Όλες οι λειτουργίες εκτελούνται σε σταθερό χρόνο O(1).

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

Ο αλγόριθμος LRU Cache βασίζεται σε δύο αρχές: έναν μετρητή προσβάσεων σε χρονική σειρά και τον μηχανισμό εκτόπισης κατά την υπερχείλιση. Κάθε στοιχείο αποθηκεύεται σε έναν κόμβο της διπλά συνδεδεμένης λίστας και οι δείκτες σε αυτούς τους κόμβους — στον πίνακα κατακερματισμού. Σε κάθε πρόσβαση στο στοιχείο, αποσυνδέεται από την τρέχουσα θέση και εισάγεται στην αρχή της λίστας.

Όταν το μέγεθος της κρυφής μνήμης φτάσει τη μέγιστη τιμή (maxSize) και έρθει αίτημα για εισαγωγή νέου στοιχείου, ο αλγόριθμος διαγράφει το στοιχείο της ουράς της διπλά συνδεδεμένης λίστας — αυτό είναι το λιγότερο πρόσφατα χρησιμοποιημένο στοιχείο. Μετά τη διαγραφή, ελευθερώνεται χώρος για το νέο στοιχείο, το οποίο εισάγεται στην κεφαλή της λίστας. Ο πίνακας κατακερματισμού ενημερώνεται: το παλιό κλειδί διαγράφεται, το νέο προστίθεται.

Χαρακτηριστικό του LRU — η μη ευαισθησία σε πρότυπα πρόσβασης με κυκλική επανάληψη. Αν η εφαρμογή έχει περιοδική πρόσβαση σε σύνολο δεδομένων μεγαλύτερο από το μέγεθος της κρυφής μνήμης, το LRU μπορεί να υποφέρει από thrashing — συχνή αντικατάσταση στοιχείων όπου κάθε νέο αίτημα εκτοπίζει το προηγούμενο. Σε τέτοια σενάρια, τα LFU (Least Frequently Used) ή προσαρμοστικοί αλγόριθμοι μπορεί να είναι πιο αποτελεσματικά.

Μέγεθος κρυφής μνήμης και μετρήσεις

Η επιλογή μεγέθους LRU Cache είναι ένας συμβιβασμός μεταξύ κατανάλωσης μνήμης και hit-ratio (ποσοστού επιτυχημένων προσβάσεων). Τυπικές τιμές για εφαρμογές κινητών: 10–20% της διαθέσιμης μνήμης για κρυφή μνήμη εικόνων και 50–200 εγγραφές για κρυφή μνήμη αποκρίσεων δικτύου. Hit-ratio 80–95% θεωρείται καλός δείκτης, όπου η κρυφή μνήμη δικαιολογεί το κόστος μνήμης. Για παρακολούθηση χρησιμοποιούνται οι μετρητές hitCount και missCount, διαθέσιμοι στην υλοποίηση LruCache στο Android.

Υλοποίηση LRU Cache: HashMap + Doubly Linked List

Η κανονική υλοποίηση του LRU Cache χρησιμοποιεί συνδυασμό πίνακα κατακερματισμού και διπλά συνδεδεμένης λίστας. Ο πίνακας κατακερματισμού παρέχει πρόσβαση σε οποιονδήποτε κόμβο μέσω κλειδιού σε O(1) και η διπλά συνδεδεμένη λίστα — μετακίνηση κόμβου στην κεφαλή και διαγραφή από την ουρά σε O(1). Είναι σημαντικό η λίστα να είναι ακριβώς διπλά συνδεδεμένη: αυτό επιτρέπει την αποσύνδεση ενός κόμβου από τη μέση της λίστας χωρίς διάσχιση όλων των στοιχείων.

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

Στην υλοποίηση, κάθε κόμβος (Node) αποθηκεύει την τιμή και αναφορές στον προηγούμενο και επόμενο κόμβο. Οι κόμβοι-φρουροί head και tail απλοποιούν τις οριακές περιπτώσεις — δεν χρειάζονται έλεγχοι null κατά την εισαγωγή και διαγραφή. Η μέθοδος get μετακινεί τον κόμβο που βρέθηκε στην κεφαλή και η put κατά την υπερχείλιση διαγράφει το στοιχείο της ουράς. Μια ξεχωριστή μέθοδος removeKeyByValue βρίσκει το κλειδί στον πίνακα κατακερματισμού μέσω αναφοράς στον κόμβο και το διαγράφει.

Ενσωματωμένη υλοποίηση LruCache στο Android

Το Android SDK παρέχει την έτοιμη κλάση LruCache στο πακέτο android.util, η οποία υλοποιεί τον αλγόριθμο LRU χρησιμοποιώντας LinkedHashMap σε λειτουργία access-order. Η κλάση είναι thread-safe, υποστηρίζει μέτρηση hit/miss και παρέχει callback entryRemoved για απελευθέρωση πόρων κατά την εκτόπιση ενός στοιχείου. Το μέγεθος της κρυφής μνήμης ρυθμίζεται σε αυθαίρετες μονάδες (bytes, αριθμός στοιχείων) — αρκεί να παρακαμφθεί η μέθοδος sizeOf.

LRU Cache vs FIFO και LIFO

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

FIFO εκτοπίζει το παλαιότερο στοιχείο βάσει χρόνου προσθήκης, ανεξάρτητα από το πόσο συχνά προσπελάστηκε. Αυτό μπορεί να είναι αναποτελεσματικό αν το παλιό στοιχείο είναι ακόμα σχετικό. Το LRU αποφεύγει αυτό το μειονέκτημα λαμβάνοντας υπόψη το πρότυπο πρόσβασης. LIFO εκτοπίζει το φρεσκοπροστεθέν στοιχείο — χρήσιμο για σενάρια undo, αλλά ακατάλληλο για προσωρινή αποθήκευση, καθώς τα νέα δεδομένα είναι συχνά πιο απαραίτητα από τα παλιά. Το LRU θεωρείται η βέλτιστη ισορροπία μεταξύ πολυπλοκότητας υλοποίησης και hit-ratio για τις περισσότερες εφαρμογές.

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

Ας εξετάσουμε τη χρήση της ενσωματωμένης κλάσης LruCache από το Android SDK για προσωρινή αποθήκευση φορτωμένων εικόνων. Το παράδειγμα δείχνει την αρχικοποίηση της κρυφής μνήμης στο 1/8 της διαθέσιμης μνήμης της εφαρμογής, που είναι η τυπική σύσταση της Google για κρυφή μνήμη εικόνων.

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

Η μέθοδος sizeOf επιστρέφει το μέγεθος του στοιχείου στις ίδιες μονάδες με το cacheSize. Εδώ χρησιμοποιείται το μέγεθος Bitmap σε kilobytes (rowBytes × height / 1024). Όταν το άθροισμα sizeOf όλων των στοιχείων υπερβαίνει το cacheSize, το LruCache εκτοπίζει αυτόματα τα λιγότερο πρόσφατα χρησιμοποιημένα Bitmap. Το callback entryRemoved μπορεί να χρησιμοποιηθεί για κλήση bitmap.recycle() — απελευθέρωση μνήμης πριν από την εκτόπιση.

Υλοποίηση LRU Cache σε Swift

Το iOS δεν διαθέτει ενσωματωμένη κλάση LRU Cache, αλλά μπορεί εύκολα να υλοποιηθεί μέσω NSCache (το οποίο χρησιμοποιεί παρόμοια αλλά μη τεκμηριωμένη πολιτική εκτόπισης) ή μέσω δικής σας υλοποίησης βασισμένης σε Dictionary + Doubly Linked List, όπως φαίνεται παρακάτω.

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

Σε αυτήν την υλοποίηση Swift, ο Node είναι μια εσωτερική κλάση με πεδία value, next και prev. Η μέθοδος moveToHead αποσυνδέει τον κόμβο από την τρέχουσα θέση και τον εισάγει στην αρχή της λίστας. Κατά την υπερχείλιση, το tail — το λιγότερο πρόσφατα χρησιμοποιημένο στοιχείο — διαγράφεται. Για έκδοση παραγωγής, συνιστάται η προσθήκη ασφάλειας νημάτων μέσω NSLock ή ουράς DispatchQueue.