Selama bertahun-tahun, orang-orang yang terlibat dalam ilmu komputer dan teknik telah bekerja sangat keras dalam berbagai macam optimasi. Mengingat kita hidup di dunia dengan sumber daya yang terbatas, umat manusia selalu berupaya mencari cara untuk mengoptimalkan biaya dan mempercepat segalanya.
Dalam rekayasa perangkat lunak, menurut saya, pendekatan paling populer untuk peningkatan kinerja adalah caching. Meskipun ada berbagai macam penerapan caching, tergantung pada bidang rekayasa perangkat lunak, ide di balik caching cukup sederhana: menyimpan data yang sering dibutuhkan/digunakan dalam struktur/penyimpanan cepat sehingga dapat diambil dengan sangat cepat.
Faktanya, cache harus cepat dalam dua dimensi:
- Memastikan bahwa sebanyak mungkin permintaan file masuk ke sana (cache hit), bukan melalui jaringan atau ke memori utama (cache miss);
- Biaya tambahan dalam penggunaannya harus kecil: menguji keanggotaan dan memutuskan kapan harus mengganti file harus dilakukan secepat mungkin.
Dalam artikel ini kita akan fokus pada bagian kedua: mengambil pendekatan implementasi spesifik pada cache yang Paling Sedikit Sering Digunakan dan menjadikan pengujian keanggotaan dan algoritme penggusurannya berkinerja baik. Selain itu, kami juga akan membahas dasar-dasarnya dan mengeksplorasi manfaat skema caching tersebut.
Dasar
LFU adalah algoritma caching di mana item yang Paling Sedikit Sering Digunakan dalam cache dihapus setiap kali batas kapasitas cache tercapai. Ini berarti bahwa untuk setiap item dalam cache, kami harus melacak seberapa sering item tersebut digunakan. Setelah kapasitas cache terlampaui, algoritma penggusuran akan dijalankan yang harus mengambil dan mengakhiri (menghapus) item dari cache.
Jika Anda pernah mengimplementasikan cache LFU, Anda mungkin pernah mempertimbangkan untuk menggunakan struktur data min-heap karena menangani penyisipan, penghapusan, dan pembaruan dalam kompleksitas waktu logaritmik. Pada artikel ini, kita akan melihat pendekatan lain untuk menerapkannya.
Namun sebelum kita masuk ke implementasinya, mari kita lihat dalam kasus apa LFU lebih baik daripada alternatif lainnya.
Dimana LFU bersinar
Bayangkan cache aset di CDN, tempat aset di-cache berdasarkan pola penggunaan. Jadi, ketika pengguna meminta beberapa gambar untuk halaman web yang mereka minta, CDN ini akan menambahkannya ke cache agar pengguna lain bisa mendapatkannya lebih cepat.
Misalnya, salah satu gambar (aset) tersebut adalah logo situs web. Bisakah Anda bayangkan berapa kali dalam sehari logo Google diminta di semua produknya? Saya sangat ingin mengetahui angka tersebut, namun untuk saat ini, kita mungkin sepakat bahwa angka tersebut BESAR.
Cache aset tersebut adalah kasus penggunaan yang sempurna untuk cache LFU. Algoritme penggusuran cache LFU tidak akan pernah menghapus aset yang sering diakses. Faktanya, dalam cache seperti itu, logo Google akan disimpan dalam cache hampir selamanya. Sebaliknya, jika ada gambar yang akan diakses karena halaman arahan baru dari produk baru yang ada di halaman depan Reddit, Slashdot & Hackernews, setelah hype-storm berlalu, aset akan dikeluarkan lebih cepat karena aksesnya frekuensinya akan turun drastis, meski dalam beberapa hari terakhir sudah diakses berkali-kali.
Seperti yang mungkin sudah Anda sadari, pendekatan terhadap penggusuran cache ini sangat efisien jika pola akses objek yang di-cache tidak sering berubah. Meskipun cache LRU akan menghapus aset yang tidak dapat diakses baru-baru ini, pendekatan penggusuran LFU akan menghapus aset yang tidak diperlukan lagi setelah hype selesai.
Menerapkan cache LFU
Sekarang, mari kita bahas inti permasalahannya. Seperti yang kami katakan sebelumnya, daripada melihat min-heap sebagai kemungkinan struktur data yang akan mendukung cache LFU kami, kami akan melihat pendekatan yang lebih baik.
Faktanya, pada tahun 2010, sekelompok peneliti Prof. Ketan Shah, Anirban Mitra & Dhruv Matani menerbitkan makalah berjudul “Algoritma O(1) untuk mengimplementasikan skema penggusuran cache LFU” (Anda dapat memeriksanya di sini) di mana mereka menjelaskan implementasi cache LFU yang memiliki kompleksitas runtime O(1) untuk semua operasinya, yang meliputi penyisipan, akses, dan penghapusan (pengusiran).
Di sini, saya akan menunjukkan kepada Anda bagaimana kami dapat mengimplementasikan cache ini dan memandu Anda dalam penerapannya.
Struktur data
Tidak, itu bukan sejenis pohon merah-hitam Frankenstein. Faktanya, ini adalah dua daftar tertaut ganda dan tabel hash. Ya, itu saja.
Untuk dapat memahami dasar-dasar implementasi LFU ini, mari kita lihat linked list dan tabel hash sebagai grafik. Sebelum kita melihat grafik sebenarnya, kita perlu memahami bagaimana tabel hash dan daftar tertaut akan digunakan.
Tabel hash akan menyimpan semua item dengan kunci yang diproses melalui algoritma hashing (untuk tujuan kita, kita dapat membuatnya tetap sederhana) dan nilainya akan menjadi item sebenarnya:
Daftar tertaut sedikit lebih rumit. Yang pertama adalah “daftar frekuensi”, yang berisi semua frekuensi akses. Masing-masing node dalam daftar ini akan memiliki daftar item, yang berisi semua item yang telah diakses dengan frekuensi yang sesuai. Selain itu, setiap item dalam daftar item akan memiliki penunjuk ke leluhurnya dalam daftar frekuensi:
Jika kita melihat contoh grafis di atas, kita dapat melihat bahwa item A, B, C dan D telah diakses sebanyak 1 kali. Item E dan F telah diakses sebanyak 4 kali dan seterusnya. Garis biru adalah penunjuk yang dimiliki setiap item dalam daftar item terhadap leluhurnya dalam daftar frekuensi.
Jadi, apa yang akan terjadi jika item E diakses sekali lagi? Mari kita ikuti langkah-langkahnya: 1. Mengambil item dari tabel hash itu mudah (dan berskala dengan baik, O(1)) 2. Kita akan mengakses penunjuk frequencyParent item tersebut, yang darinya kita dapat memeriksa frekuensi berikutnya dalam daftar 3. Jika frekuensi baru hadir (misalnya 8), kami akan memasukkannya sebagai item pertama dari daftar item di bawah simpul frekuensi 8. 4. Jika frekuensi baru tidak ada, kami akan membuat node frekuensi 8 dan akan menambahkan E ke daftar itemnya
Itu dia. Frekuensi pengambilan item dan penyegaran item adalah O(1). Sebelum kita menerapkan algoritma akses, pertama-tama mari kita tentukan tipe dasar yang kita perlukan agar ini berfungsi.
Jenis
Seperti yang kami katakan sebelumnya, kita perlu memodelkan tipe-tipe yang diperlukan yang akan menjadi tulang punggung cache kita.
struct pertama akan menjadi CacheItem. Ini akan menjadi item sebenarnya yang akan disimpan dalam cache:
type CacheItem struct {
key string // Key of entry
value interface{} // Value of item
frequencyParent *list.Element // Pointer to parent in cacheList
}Ini berisi key yang dengannya kita dapat mencarinya di tabel hash, value yang merupakan item cache sebenarnya dan penunjuk frequencyParent ke penunjuk dalam daftar frekuensi.
struct berikutnya adalah FrequencyItem, yang mewakili setiap item dalam daftar frekuensi. Ini berisi satu set entri yang akan menjadi satu set CacheItem pointer. Kita akan menggunakan map untuk menyimpannya sehingga kita dapat memperlakukannya sebagai satu set, yang hanya berisi item unik:
type FrequencyItem struct {
entries map[*CacheItem]byte // Set of entries
freq int // Access frequency
}struct terakhir yang kita perlukan agar cache berjalan lancar adalah Cache itu sendiri:
type Cache struct {
bykey map[string]*CacheItem // Hashmap containing *CacheItems for O(1) access
freqs *list.List // Linked list of frequencies
capacity int // Max number of items
size int // Current size of cache
}Cache akan berisi peta hash, yang disebut bykey (penamaan berasal dari makalah yang ditautkan di atas), daftar frekuensi yang disebut freqs, kapasitas maksimum cache yang disebut capacity dan size dari cache yang mewakili jumlah item yang di-cache pada waktu tertentu momen.
Baru, atur & dapatkan
Mari kita lihat tiga fungsi pertama yang diperlukan agar cache kita berfungsi. Yang pertama adalah fungsi konstruktor kecil:
func New() *Cache {
cache := new(Cache)
cache.bykey = make(map[string]*CacheItem)
cache.freqs = list.New()
cache.size = 0
cache.capacity = 100
return &c
}Konstruktor New akan membuat struct Cache baru dan akan menyetel semua defaultnya. Jika Anda bertanya-tanya bagaimana list.New() bekerja: untuk daftar frekuensi, kami akan menggunakan paket container/list Go, yang berisi implementasi daftar tertaut yang rapi. Anda dapat memeriksa dokumentasinya untuk lebih jelasnya.
Fungsi kedua yang akan diimplementasikan pada Cache adalah fungsi Set:
func (cache *Cache) Set(key string, value interface{}) {
if item, ok := cache.bykey[key]; ok {
item.value = value
// Increment item access frequency here
} else {
item := new(CacheItem)
item.key = key
item.value = value
cache.bykey[key] = item
cache.size++
// Eviction, if needed
// Increment item access frequency
}
}Fungsi ini akan mengambil kunci cache dan nilai/item aktual yang akan di-cache sebagai argumen. Kemudian, ia memeriksa apakah item tersebut sudah di-cache atau belum. Jika di-cache, itu hanya akan memperbarui nilai pada item tersebut. Jika tidak, ia akan membuat CacheItem baru yang akan merangkum nilai sebenarnya, ia akan menetapkan key, ia akan menambahkan item ke tabel hash bykey dan akan menambah size cache.
Sekarang, di kedua cabang logis saya telah menambahkan beberapa komentar untuk bagian yang hilang: 1. Cache harus mengetahui cara meningkatkan frekuensi akses untuk aCacheItem, tetapi kami belum menerapkannya; 2. Cache harus mengetahui cara mengeluarkan item berdasarkan frekuensi akses jika size mencapai capacity.
Kami akan menyimpan komentar ini hingga kami mengimplementasikan fungsi increment dan evict.
Fungsi ketiga yang Cache akan terima adalah Get - mengakses item dengan kunci dari tabel hash dan mengembalikannya:
func (cache *Cache) Get(key string) interface{} {
if e, ok := cache.bykey[key]; ok {
// Increment acess frequency here
return e.value
}
return nil
}Tidak ada keajaiban di sini juga — kami memeriksa apakah tabel hash bykey berisi nilai dengan argumen key dan kami mengembalikannya jika ada. Jika tidak, kami mengembalikan nil. Di sini, seperti di Set, kita akan meninggalkan komentar placeholder di mana kita harus menambahkan pemanggilan fungsi kenaikan frekuensi setelah kita mengimplementasikannya.
Memperbarui frekuensi akses
Seperti yang telah kita lihat, dengan setiap tindakan akses ke cache, kita harus memperbarui frekuensi akses item yang diakses.
Mari kita lihat langkah-langkah yang harus diambil oleh fungsi Increment kita. Pertama, agar item tersebut kedaluwarsa, kita harus memutuskan apakah item ini sudah menjadi bagian dari tabel hash dan daftar frekuensi atau belum. Jika ya, kita harus mencari nilai frekuensi barunya dan posisi frekuensi berikutnya (node) dalam daftar frekuensi.
Kedua, kita harus mencari tahu apakah untuk frekuensi baru sudah ada node di daftar frekuensi atau belum. Jika ada, kita harus menambahkan item tersebut ke daftar entries dan menetapkan frekuensi akses barunya (yaitu frekuensi akses saat ini + 1). Jika tidak ada, kita harus membuat node frekuensi baru di daftar frekuensi (dan mengatur semua default yang masuk akal) dan kemudian menambahkan item ke daftar entries
Ketiga, setelah FrequencyParent terdeteksi, fungsi kita harus menyetel induk baru ke item yang sedang bertambah dan menambahkannya ke daftar induk entries.
Sebagai langkah terakhir, fungsi increment akan menghapus item dari entries node frekuensi lama (frequencyParent).
Berikut kode di Golang:
func (cache *Cache) increment(item *CacheItem) {
currentFrequency := item.frequencyParent
var nextFrequencyAmount int
var nextFrequency *list.Element
if currentFrequency == nil {
nextFrequencyAmount = 1
nextFrequency = cache.freqs.Front()
} else {
nextFrequencyAmount = currentFrequency.Value.(*FrequencyItem).freq + 1
nextFrequency = currentFrequency.Next()
}
if nextFrequency == nil || nextFrequency.Value.(*FrequencyItem).freq != nextFrequencyAmount {
newFrequencyItem := new(FrequencyItem)
newFrequencyItem.freq = nextFrequencyAmount
newFrequencyItem.entries = make(map[*CacheItem]byte)
if currentFrequency == nil {
nextFrequency = cache.freqs.PushFront(newFrequencyItem)
} else {
nextFrequency = cache.freqs.InsertAfter(newFrequencyItem, currentFrequency)
}
}
item.frequencyParent = nextFrequency
nextFrequency.Value.(*FrequencyItem).entries[item] = 1
if currentFrequency != nil {
cache.remove(currentFrequency, item)
}
}Mari kita merujuk kembali ke diagram asli daftar frekuensi dan entri kita dan menelusuri penambahan item E.
Langkah pertama yang akan diambil oleh fungsi increment kita adalah mengalokasikan pointer ke node 4 (yang frequencyParent) dan value-nya (yaitu 4). Karena node 4 ada dalam daftar, node berikutnya akan ditemukan dalam daftar frekuensi, yang dalam kasus kita adalah node 7.
Setelah diketahui bahwa frekuensi baru untuk node E seharusnya adalah 5 dan bukan 7, maka node frekuensi baru akan ditambahkan dalam daftar, antara node 4 dan 7:
Setelah node 5 ditambahkan ke daftar, fungsi akan menyetel nilai default yang diperlukan agar node dapat berfungsi dengan baik. Kemudian ia akan menyetel penunjuk E ke frequencyParent baru (node 5):
Sebagai langkah terakhir akan mengambil item, yang bertipe *CacheItem, dan akan menambahkannya ke daftar entries sambil menghapusnya dari daftar entries dari frequencyParent sebelumnya:
Mari kita lihat apa saja langkah-langkah untuk menghapus CacheItem dari daftar entries FrequencyItem.
Menghapus entri
Setelah kita mengetahui node dalam daftar yang ingin kita hapus, kita cukup menghapus item tersebut dari daftar entries dan juga menghapus FrequencyItem sepenuhnya dari daftar frekuensi jika entries menjadi kosong:
func (cache *Cache) Remove(listItem *list.Element, item *CacheItem) {
frequencyItem := listItem.Value.(*FrequencyItem)
delete(frequencyItem.entries, item)
if len(frequencyItem.entries) == 0 {
cache.freqs.Remove(listItem)
}
}Pengusiran
Bagian terakhir dari teka-teki ini adalah penggusuran, atau dengan kata lain, menghapus item yang paling jarang digunakan setelah cache mencapai kapasitas maksimumnya.
Kita harus tahu berapa banyak barang yang ingin kita usir. Biasanya cache kita memiliki batas rendah dan tinggi, jadi ketika batas tinggi tercapai kita akan menghapus item hingga batas rendah. Dalam kasus kita, kita akan mengeluarkan sejumlah item secara acak, yang akan dijadikan argumen oleh fungsi Evict.
Fungsi ini akan mulai “menelusuri” daftar frekuensi dari awal hingga akhir. Karena daftar frekuensi berada dalam urutan menaik, ia akan mulai menghapus entries dari node frekuensi pertama dan seterusnya, hingga ia menghapus item sebanyak nomor sembarang yang dimasukkan.
Jika node frekuensi tidak berisi entries karena penggusuran, fungsi Evict juga harus menghapus node frekuensi dari daftar frekuensi. Ini akan melakukannya dengan menjalankan fungsi Remove. Dengan begitu, penggusuran tidak meninggalkan sampah.
Berikut kode yang kami jelaskan di atas:
func (cache *Cache) Evict(count int) {
for i := 0; i < count; {
if item := cache.freqs.Front(); item != nil {
for entry, _ := range item.Value.(*FrequencyItem).entries {
if i < count {
delete(cache.bykey, entry.key)
cache.Remove(item, entry)
cache.size--
i++
}
}
}
}
}Kembali ke Atur dan Dapatkan
Di awal artikel ini kami mengimplementasikan fungsi Set dan Get. Satu hal yang belum kami miliki saat itu adalah fungsi Evict dan increment, sehingga kami dapat menggunakannya sebagaimana mestinya. Mari tambahkan doa mereka.
Meningkatkan frekuensi akses
Dalam fungsi Get, jika kita menemukan item di tabel hash bykey, kita perlu menaikkan frekuensi aksesnya sebelum kita melanjutkan untuk mengembalikan value-nya:
func (cache *Cache) Get(key string) interface{} {
if e, ok := cache.bykey[key]; ok {
cache.increment(e)
return e.value
}
return nil
}Dengan perubahan ini, Cache akan menambah frekuensi item tertentu sebelum kami mengembalikannya. Tapi, apakah kita melupakan sesuatu? Selain itu, fungsi Set membuat akses ke item yang di-cache ketika sebenarnya item tersebut di-cache. Artinya ketika suatu item di-cache, item tersebut akan segera ditambahkan ke daftar frekuensi, di bawah node dengan nilai 1:
func (cache *Cache) Set(key string, value interface{}) {
if item, ok := cache.bykey[key]; ok {
item.value = value
cache.increment(item)
} else {
item := new(CacheItem)
item.key = key
item.value = value
cache.bykey[key] = item
cache.size++
// Eviction, if needed
cache.increment(item)
}
}Penggusuran demi penambahan
Fungsi Set memungkinkan pengguna LFU Cache kami untuk menyimpan lebih banyak item di dalamnya. Komponen kunci dari setiap cache adalah ia harus mengetahui cara mengeluarkan item (mengosongkan ruang) ketika item baru ditambahkan ke cache. Untuk cache LFU, item yang paling jarang digunakan harus dihapus ketika cache sudah mencapai kapasitasnya.
Pertama mari tambahkan fungsi yang akan mengembalikan bool jika cache telah mencapai kapasitas maksimumnya:
func (cache *Cache) atCapacity() bool {
return cache.size >= cache.capacity
}Fungsinya sederhana: memeriksa apakah size saat ini dari Cache lebih besar atau sama dengan capacity.
Sekarang, mari kita gunakan ini dalam fungsi Set. Setelah kita memiliki set item baru di cache, kita harus memeriksa apakah cache telah mencapai kapasitasnya dan kemudian mengeluarkan sejumlah item darinya.
Untuk mempermudah, kami hanya akan menghapus 10 item setiap kali kami mencapai kapasitas maksimal:
func (cache *Cache) Set(key string, value interface{}) {
if item, ok := cache.bykey[key]; ok {
item.value = value
cache.increment(item)
} else {
item := new(CacheItem)
item.key = key
item.value = value
cache.bykey[key] = item
cache.size++
if cache.atCapacity() {
cache.Evict(10)
}
cache.increment(item)
}
}Dengan perubahan ini, jika suatu saat penambahan item mencapai kapasitas cache, cache akan mengeluarkan item yang paling jarang digunakan.
Jika Anda ingin melihat keseluruhan kode untuk artikel ini, Anda dapat melihat intinya.
LFU merupakan skema penggusuran yang menarik, apalagi jika dibandingkan dengan LRU, menurut saya karena sifatnya yang tidak konvensional. Meskipun penerapannya terbatas, algoritme dan struktur data pendukung yang dijelaskan dalam makalah yang digunakan dalam artikel ini sangat menarik karena kemampuan penskalaan dari pendekatan tersebut.
Jika kita meninjau kembali "makalah" yang kami sebutkan di awal artikel, kita akan melihat bahwa meskipun LFU bukanlah berita, namun secara tradisional diimplementasikan menggunakan min-heap, yang memiliki waktu logaritmik untuk penyisipan, pencarian, dan penghapusan. Menariknya dalam makalah ini, penulis menjelaskan bahwa pendekatan yang mereka usulkan memiliki kompleksitas waktu O(1) untuk setiap operasi (penyisipan, pencarian dan penghapusan) karena operasi didasarkan pada tabel hash. Selain itu, daftar tertaut tidak menambah kompleksitas waktu karena kami tidak melintasi daftar kapan pun - kami hanya menambah atau menghapus simpul di dalamnya jika diperlukan (yang merupakan operasi O(1)).
Sebagai penutup
Pada artikel ini, kita membahas dasar-dasar cache LFU. Kami menetapkan metrik kinerja yang paling penting (rasio untung-untungan, keanggotaan & kecepatan penggusuran). Kami melihat bahwa meskipun ini bukan skema caching yang paling banyak digunakan, skema ini pasti bisa sangat efektif dalam beberapa kasus penggunaan.
Kemudian kami melanjutkan penerapannya, menggunakan pendekatan yang skalanya cukup baik dalam hal kompleksitas waktu. Kami melihat kompleksitas penerapan algoritma penggusuran dan penambahan frekuensi. Pada akhirnya, kami mengeksplorasi lebih jauh bagaimana pendekatan yang kami gunakan untuk mengimplementasikannya dapat diperluas.
Awalnya diterbitkan di ieftimov.com pada 27 Februari 2019.
