FIFO Cache — แนวคิดหลัก อัลกอริทึมคิว และวิธีการทำงาน

FIFO Cache คืออะไร?

FIFO Cache (First In First Out Cache) คือแคชขนาดคงที่ที่ใช้คิวในการจัดการอิลิเมนต์ อิลิเมนต์แรกที่ถูกเพิ่มจะถูกวางที่หัวของคิวและจะเป็นอันแรกที่ถูกลบเมื่อเกิดการล้น อิลิเมนต์ใหม่จะถูกเพิ่มที่ส่วนท้ายเสมอ เพื่อให้ลำดับการลบตรงกับลำดับการเพิ่ม

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

การนำ FIFO Cache ไปใช้สามารถสร้างขึ้นบนโครงสร้างข้อมูลหลายแบบ: บัฟเฟอร์วงรอบเพื่อประสิทธิภาพสูงสุด, รายการเชื่อมโยงเพื่อความยืดหยุ่น, หรือสองสแต็ก (คิวสองสแต็ก) สำหรับภาษาที่ไม่มีคิวในตัว บัฟเฟอร์วงรอบให้ ความใกล้ชิดของแคช ที่ดีที่สุดและค่าใช้จ่ายน้อยที่สุด แต่ต้องมีการจัดสรรหน่วยความจำล่วงหน้าสำหรับ maxSize

การดำเนินการพื้นฐานของ FIFO Cache

การดำเนินการ enqueue(value) เพิ่มอิลิเมนต์ที่ส่วนท้ายของคิว หากขนาดถึง maxSize อิลิเมนต์ที่หัวจะถูกลบก่อนการเพิ่ม การดำเนินการ dequeue() จะลบและส่งคืนอิลิเมนต์ที่หัว — เพื่อการดึงอิลิเมนต์ที่เก่าที่สุดออกมาอย่างบังคับ การดำเนินการ peek() จะส่งคืนอิลิเมนต์ที่หัวโดยไม่ต้องลบ — เพื่อดูอิลิเมนต์ที่เก่าที่สุดโดยไม่เปลี่ยนแปลงคิว

FIFO Cache ทำงานอย่างไร

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

เมื่อนำไปใช้ผ่านบัฟเฟอร์วงรอบ จะใช้ตัวชี้สองตัว: head (ดัชนีหัวคิว) และ tail (ดัชนีท้ายคิว) เมื่อ enqueue อิลิเมนต์จะถูกเขียนที่ดัชนี tail และ tail จะเพิ่มขึ้น หาก tail ถึงขนาดของบัฟเฟอร์ มันจะวนกลับไปที่จุดเริ่มต้นของอาร์เรย์ หาก tail ตามทัน head แสดงว่าคิวเต็มและ head จะถูกเลื่อน (การแทนที่) บัฟเฟอร์วงรอบ ไม่ต้องการการจัดสรรหน่วยความจำแบบไดนามิกและหลีกเลี่ยงการแยกส่วน

FIFO Cache แสดง hit-ratio ตั้งแต่ 40% ถึง 60% สำหรับโหลดงานทั่วไป ซึ่งสูงกว่า LIFO แต่ต่ำกว่า LRU อย่างไรก็ตาม สำหรับสถานการณ์ที่การเข้าถึงข้อมูลสม่ำเสมอและไม่มีจุดร้อน FIFO สามารถแสดงผลลัพธ์ที่เทียบเคียงได้กับ LRU ด้วยความซับซ้อนในการนำไปใช้ที่ต่ำกว่าอย่างมาก หน่วยความจำ ถูกใช้อย่างมีประสิทธิภาพ: ไม่จำเป็นต้องมีตัวชี้เพิ่มเติมสำหรับการจัดลำดับอิลิเมนต์ใหม่

ปัญหามลพิษของแคช

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

การเปรียบเทียบ FIFO, LRU และ LIFO

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

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

FIFO Cache ใช้ที่ไหน

FIFO Cache ถูกใช้ในสถานการณ์ที่ความสามารถในการทำนายการแทนที่หรือลำดับการประมวลผลข้อมูลมีความสำคัญ เรามาดูกรณีการใช้งานหลักกัน

การบัฟเฟอร์ข้อมูลสตรีม

เมื่อเล่นเสียงและวิดีโอ ข้อมูลจะมาในสตรีมต่อเนื่องและถูกเก็บไว้ชั่วคราวในบัฟเฟอร์ FIFO Cache ช่วยให้แน่ใจว่าแฟรกเมนต์แรกที่ได้รับจะถูกส่งไปถอดรหัสก่อน — ซึ่งรับประกันการเล่นที่ราบรื่นโดยไม่มีความล่าช้า ขนาดบัฟเฟอร์ ถูกเลือกตามบิตเรตของสตรีมและความล่าช้าที่ยอมรับได้: โดยทั่วไป 2–5 วินาทีสำหรับเสียง 10–30 วินาทีสำหรับวิดีโอ FIFO เหมาะสำหรับสถานการณ์ดังกล่าวเพราะการจัดลำดับข้อมูลใหม่ (เช่นใน LRU) ไม่มีความหมาย

คิวคำขอเครือข่าย

เมื่อจำกัดจำนวนคำขอเครือข่ายพร้อมกัน FIFO Cache สามารถใช้เก็บคำขอที่รออยู่ คำขอแรกที่ถูกเพิ่มจะถูกดำเนินการก่อน ซึ่งช่วยให้มั่นใจถึง การกระจายทรัพยากรเครือข่ายอย่างยุติธรรมระหว่างส่วนประกอบต่างๆ ของแอปพลิเคชัน วิธีการนี้ใช้ใน OkHttp Dispatcher และไลบรารีที่คล้ายกันสำหรับการจัดการพูลการเชื่อมต่อ

การแคชคำตอบ HTTP

แคชคำตอบ HTTP แบบง่ายบนอุปกรณ์มือถือมักใช้ FIFO คำตอบต่อคำขอจะถูกเก็บตามลำดับที่มาถึง และเมื่อถึงขีดจำกัด คำตอบที่เก่าที่สุดจะถูกลบ แม้ว่า LRU จะให้ hit-ratio ที่ดีกว่าสำหรับสถานการณ์ผู้ใช้ FIFO ง่ายกว่าในการนำไปใช้และไม่ต้องการเก็บ เวลาที่เข้าถึงล่าสุด สำหรับแต่ละคำตอบ สำหรับ API ที่มีโหลดสม่ำเสมอ ความแตกต่างของ hit-ratio ระหว่าง FIFO และ LRU นั้นน้อยมาก

การประมวลผลเหตุการณ์สัมผัส

ในแอปพลิเคชันมือถือ เหตุการณ์สัมผัสจะถูกบัฟเฟอร์ในคิว FIFO ก่อนการประมวลผลท่าทาง แต่ละเหตุการณ์ต้องถูกประมวลผลตามลำดับที่เกิดขึ้น มิฉะนั้นท่าทางจะถูกจดจำไม่ถูกต้อง FIFO Cache ที่มีขีดจำกัดขนาดป้องกันบัฟเฟอร์ล้นระหว่างการปัดอย่างรวดเร็ว โดยละทิ้งเหตุการณ์ที่เก่าที่สุดหากแอปพลิเคชันไม่สามารถประมวลผลทัน

ตัวอย่างโค้ด FIFO Cache

มาดูการนำ FIFO Cache ไปใช้ใน Kotlin โดยใช้บัฟเฟอร์วงรอบ — วิธีการที่มีประสิทธิภาพที่สุดสำหรับอุปกรณ์มือถือ

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

บัฟเฟอร์วงรอบใช้ดัชนี head และ tail ที่เพิ่มขึ้นแบบวงจรด้วยโมดูโล maxSize เมื่อ size == maxSize enqueue จะลบอิลิเมนต์ที่ head (เก่าที่สุด) ก่อน เลื่อน head จากนั้นเขียนอิลิเมนต์ใหม่ที่ tail เลขคณิตแบบโมดูลาร์จะวนตัวชี้กลับไปยังจุดเริ่มต้นของอาร์เรย์โดยอัตโนมัติ ไม่ต้องคัดลอกข้อมูลด้วยตนเอง

การนำไปใช้ใน Swift ผ่านสองสแต็ก

ใน Swift ทางเลือกที่สะดวกคือคิว FIFO บนพื้นฐานของสองสแต็ก (คิวสองสแต็ก) การดำเนินการ 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() ระหว่างการแทนที่จะลบอิลิเมนต์ที่เก่าที่สุด (อันแรกที่ถูกเพิ่ม) วิธีการนี้ไม่ต้องการการจัดสรรหน่วยความจำล่วงหน้า แต่อาจสร้างภาระเพิ่มเติมบนตัวเก็บขยะระหว่างการกลับสแต็กบ่อยๆ สำหรับแอปพลิเคชันมือถือที่มีหน่วยความจำจำกัด บัฟเฟอร์วงรอบยังคงเป็นที่ต้องการมากกว่า