Laksanakan Cache LRU dalam Go

Jadi anda memerlukan cache kecil dan tidak boleh membenarkan contoh Redis atau memcached. Mari lihat perkara yang diperlukan untuk melaksanakannya dalam Go. Untuk keseronokan, kami akan menjadikannya menggunakan generik supaya ia boleh digunakan semula dalam projek kami.

Cache LRU secara amnya mempunyai kapasiti tetap dan dasar pelepasan yang paling mudah: keluarkan elemen yang mempunyai masa paling lama sejak ia diakses. Cache lru mudah akan melaksanakan antara muka berikut:

type LRUCache[T any] interface {
    Get(key string) (value T, found bool)
    Put(key string, value T)
    Keys() []string
    Remove(key string) bool
    Clear()
    Capacity() int
    Len() int
}

Kami tahu cache akan menyimpan item data sebagai entri yang dikunci oleh beberapa nilai. Itu bunyi seperti peta. Bagaimana pula dengan melaksanakan dasar pelepasan? Salah satu cara untuk melakukan ini adalah dengan menyimpan harta timeAccessed bersama setiap item. Sesuatu seperti:

type cacheEntry[T any] struct {
  Data T
  LastAccessed time.time
}

Namun, mari kita fikirkan tentang prestasi, kita mahu dapat mencari kunci cache serta memasukkan dan mengusir yang paling lama, jika perlu, secepat mungkin.

Menggunakan peta, yang merupakan jadual cincang, akan memberikan kami prestasi yang cukup pantas untuk carian. Bagaimana pula dengan mencari entri tertua? Jika struct cache anda kelihatan seperti:

type LRUCache[T any] {
  capacity int
  keyMap map[string]cacheEntry[T]
}

Kami semestinya perlu mengulangi peta untuk mencari yang tertua apabila tiba masanya untuk mengusir entri.

Kami memerlukan cara untuk menyimpan entri dengan cara yang cekap membolehkan kami menyimpan senarai entri cache yang diisih. Adalah lebih baik kita tidak perlu menggunakan rutin isihan.

Senarai pautan berganda ialah cara yang baik untuk melakukan ini dan kami tidak perlu menyimpan masa akses dalam entri melainkan kami benar-benar menginginkannya. Jadi, katakan kita mempunyai senarai terpaut yang melaksanakan perkara berikut bersama-sama dengan struct nodnya:

type DoubleLinkedList[T any] interface {
    Head() *DoubleNode[T]
    Tail() *DoubleNode[T]
    // Append inserts new item at tail
    Append(data T) *DoubleNode[T]
    // Push appends new item at head
    Push(data T) *DoubleNode[T]
    Remove(node *DoubleNode[T]) *DoubleNode[T]
    RemoveTail() *DoubleNode[T]
    MoveToHead(node *DoubleNode[T])
}
type DoubleNode[T any] struct {
    Data T
    Prev *DoubleNode[T]
    Next *DoubleNode[T]
}

Struktur cache kini boleh kelihatan seperti:

type lruCache[T any] struct {
    capacity int
    keyMap   map[string]*DoubleNode[lruCacheEntry[T]]
    list     DoubleLinkedList[lruCacheEntry[T]]
}

Struktur kemasukan cache ialah:

type lruCacheEntry[T any] struct {
    key   string
    value T
}

Secara realistik, anda mungkin akan menggunakan antara muka untuk kunci cache. Saya menggunakan rentetan untuk memastikan kod mudah.

Dalam pelaksanaan di sini, entri yang paling baru diakses dalam cache akan berada di kepala dan yang paling kurang digunakan baru-baru ini akan berada di ekor. Jadi, apabila tiba masanya untuk mengusir, kami hanya mengalih keluar elemen ekor senarai terpaut.

Melaksanakan fungsi Get() adalah mudah:

func (l *lruCache[T]) Get(key string) (value T, found bool) {
    if node, ok := l.keyMap[key]; ok {
        l.list.MoveToHead(node)
        return node.Data.value, ok
    }
    var zero T
    return zero, false
}

Get hanya perlu mendapatkan semula entri peta untuk kunci, kemudian alihkan nod ke kepala senarai kerana ia kini 'yang paling baru digunakan'.

Fungsi Put() ialah tempat kami akan mengendalikan pengusiran jika perlu:

func (l *lruCache[T]) Put(key string, value T) {
    if node, ok := l.keyMap[key]; ok {
        node.Data = lruCacheEntry[T]{
            key:   key,
            value: value,
        }
        // move the element to the most recent position
        l.list.MoveToHead(node)
    } else {
        // insert the new element at the head
        newNode := l.list.Push(lruCacheEntry[T]{
            key:   key,
            value: value,
        })
        l.keyMap[key] = newNode
    }
    // is eviction necessary
    if len(l.keyMap) > l.capacity {
        nodeRemoved := l.list.RemoveTail()
        delete(l.keyMap, nodeRemoved.Data.key)
    }
}

Untuk Put(), kami mula-mula menyemak sama ada sudah ada nilai untuk kunci yang diberikan. Jika ya, kemudian kemas kini nilai dan alihkan nod ke kepala senarai. Jika tidak, kami mencipta entri cache baharu, menambahnya pada senarai sebagai kepala, dan menambahnya pada peta kami.

Akhir sekali, jangan lupa untuk menyemak kapasiti. Jika entri baharu meletakkan kami melebihi kapasiti, kami mengusir entri tertua yang merupakan ekor senarai dan memadamkan entri daripada peta kami.

Perhatikan bahawa menyimpan kunci sebagai sebahagian daripada entri cache membolehkan kami memadamkan kunci dengan pantas daripada peta. Jika kami hanya menyimpan data dalam entri cache, maka kami perlu mengulangi peta untuk mencarinya.

Cache ini kehilangan sesuatu yang kritikal untuk apl berbilang benang. Tiada penyegerakan. Secara realistik, cache akan diakses oleh berbilang benang. Penyegerakan ialah topik yang rumit. Untuk pelaksanaan kami, kami boleh menambah mutex pada struct cache:

type lruCache[T any] struct {
    capacity int
    keyMap   map[string]DoubleNode[lruCacheEntry[T]]
    list     DoubleLinkedList[lruCacheEntry[T]]
    mutex    sync.RWMutex
}

kemudian tambah yang berikut pada permulaan setiap fungsi.

    l.mutex.Lock()
    defer l.mutex.Unlock()

Perhatikan bahawa kami menggunakan kunci baca/tulis. Sesetengah fungsi tidak mengubah struktur cache, jadi kita boleh menggunakan kaedah kunci baca yang disediakan, contohnya fungsi Len():

func (l *lruCache[T]) Len() int {
    l.mutex.RLock()
    defer l.mutex.RUnlock()
    return len(l.keyMap)
}

Perhatikan bahawa strategi penyegerakan yang dipilih di sini mungkin rosak jika terdapat sejumlah besar urutan yang cuba mengakses cache. Ia adalah topik yang rumit yang boleh menjadi satu siri siaran itu sendiri.

Lihat pelaksanaan penuh dalam repositori yang diberikan dalam pautan di bawah.

Apakah yang anda akan lakukan berbeza untuk melaksanakan cache? Bagaimanakah anda menangani penyegerakan? Saya berminat untuk mendengar pendapat anda tentang perkara ini. Tiada penyelesaian tunggal untuk perkara ini jadi letakkan komen anda di bawah.

Terima kasih!

Kod untuk siaran ini dan semua siaran dalam siri ini boleh didapati di sini

Atas ialah kandungan terperinci Laksanakan Cache LRU dalam Go. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!