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 เป็นการแลกเปลี่ยนระหว่างการใช้หน่วยความจำและอัตราการเข้าถึง (เปอร์เซ็นต์ของการเข้าถึงที่สำเร็จ) ค่าทั่วไปสำหรับแอปพลิเคชันมือถือ: 10–20% ของหน่วยความจำที่มีสำหรับแคชรูปภาพ และ 50–200 รายการสำหรับแคชการตอบสนองเครือข่าย อัตราการเข้าถึง 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) เก็บค่าและการอ้างอิงไปยังโหนดก่อนหน้าและถัดไป โหนด sentinel head และ tail ช่วยลดความซับซ้อนของกรณีขอบ — ไม่จำเป็นต้องตรวจสอบ null เมื่อแทรกและลบ เมธอด get ย้ายโหนดที่พบไปที่หัว และ put ลบองค์ประกอบที่หางเมื่อล้น เมธอดแยกต่างหาก removeKeyByValue ค้นหาคีย์ในตารางแฮชโดยการอ้างอิงโหนดและลบออก

การใช้งาน LruCache ในตัวใน Android

Android SDK มีคลาส LruCache พร้อมใช้ในแพ็คเกจ android.util ซึ่งใช้อัลกอริทึม LRU โดยใช้ LinkedHashMap ในโหมด access-order คลาสนี้เป็น thread-safe รองรับการนับ hit/miss และให้ callback entryRemoved สำหรับการล้างทรัพยากรเมื่อขับไล่องค์ประกอบ ขนาดแคชถูกกำหนดในหน่วยตามอำเภอใจ (ไบต์ จำนวนองค์ประกอบ) — เพียงแค่แทนที่เมธอด sizeOf

LRU Cache เทียบกับ FIFO และ LIFO

ทั้งสามอัลกอริทึม — LRU, FIFO และ LIFO — แก้ปัญหาเดียวกัน: จำกัดการใช้หน่วยความจำโดยการขับไล่องค์ประกอบเมื่อล้น อย่างไรก็ตาม พวกมันใช้เกณฑ์ที่แตกต่างกันโดยพื้นฐานในการเลือกเหยื่อ ซึ่งกำหนดประสิทธิภาพในสถานการณ์ต่าง ๆ

FIFO ขับไล่องค์ประกอบที่เก่าที่สุดตามเวลาเพิ่ม โดยไม่คำนึงถึงความถี่ในการเข้าถึง สิ่งนี้อาจไม่มีประสิทธิภาพหากองค์ประกอบเก่ายังคงเกี่ยวข้อง LRU หลีกเลี่ยงข้อเสียเปรียบนี้โดยพิจารณารูปแบบการเข้าถึง LIFO ขับไล่องค์ประกอบที่เพิ่มล่าสุด — มีประโยชน์สำหรับสถานการณ์การเลิกทำ แต่ไม่เหมาะสำหรับการแคช เนื่องจากข้อมูลใหม่มักจำเป็นมากกว่าข้อมูลเก่า LRU ถือเป็นความสมดุลที่เหมาะสมที่สุดระหว่างความซับซ้อนในการใช้งานและอัตราการเข้าถึงสำหรับแอปพลิเคชันส่วนใหญ่

ตัวอย่างโค้ด 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 ในหน่วยกิโลไบต์ (rowBytes × height / 1024) เมื่อผลรวม sizeOf ขององค์ประกอบทั้งหมดเกิน cacheSize LruCache จะขับไล่ Bitmap ที่ไม่ได้ใช้ล่าสุดโดยอัตโนมัติ callback entryRemoved สามารถใช้เพื่อเรียก bitmap.recycle() — ปลดปล่อยหน่วยความจำก่อนการขับไล่

การใช้งาน LRU Cache ใน Swift

iOS ไม่มีคลาส LRU Cache ในตัว แต่สามารถใช้งานได้ง่ายโดยใช้ NSCache (ซึ่งใช้นโยบายการขับไล่ที่คล้ายกันแต่ไม่ได้บันทึกไว้) หรือผ่านการใช้งานแบบกำหนดเองโดยใช้ Dictionary + รายการเชื่อมโยงสองทิศทาง ดังที่แสดงด้านล่าง

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 แยกโหนดออกจากตำแหน่งปัจจุบันและแทรกที่หัวของรายการ เมื่อล้น หาง — องค์ประกอบที่ไม่ได้ใช้ล่าสุด — จะถูกลบออก สำหรับการใช้งานจริง แนะนำให้เพิ่มความปลอดภัยของเธรดผ่าน NSLock หรือคิว DispatchQueue