Algoritma cache

Algoritma Cache adalah algoritma yang digunakan untuk mengelola cache atau sekelompok data. Ketika cache penuh, algoritma ini memutuskan item mana yang harus dihapus dari cache. Kata hit rate menggambarkan seberapa sering sebuah permintaan dapat dilayani dari cache. Istilah latency menggambarkan berapa lama item yang di-cache dapat diperoleh. Aloritma cache adalah trade-off antara hit-rate dan latency.

Algoritma caching yang paling efisien adalah selalu membuang informasi yang tidak akan dibutuhkan untuk waktu yang lama di masa depan. Hasil optimal ini disebut sebagai algoritma optimal Belady atau algoritma peramal. Karena secara umum tidak mungkin untuk memprediksi seberapa jauh di masa depan informasi yang akan dibutuhkan, hal ini secara umum tidak dapat diimplementasikan dalam praktek. Minimum praktis dapat dihitung hanya setelah eksperimen, dan seseorang dapat membandingkan keefektifan algoritma cache yang sebenarnya dipilih dengan minimum optimal.
Least Recently Used (LRU): menghapus item yang paling jarang digunakan terlebih dahulu. Algoritma ini membutuhkan pelacakan apa yang digunakan kapan. Ini mahal jika seseorang ingin memastikan algoritma selalu membuang item yang paling baru digunakan. Implementasi umum dari teknik ini membutuhkan untuk menyimpan "bit umur" untuk baris cache dan melacak baris cache "Least Recently Used" berdasarkan bit umur. Dalam implementasi tersebut, setiap kali sebuah cache-line digunakan, umur dari semua cache-line lainnya berubah. LRU sebenarnya adalah keluarga algoritma caching dengan anggota-anggota termasuk: 2Q oleh Theodore Johnson dan Dennis Shasha dan LRU/K oleh Pat O'Neil, Betty O'Neil dan Gerhard Weikum.
Paling Baru Digunakan (MRU): Algoritma ini menghapus item yang paling baru digunakan terlebih dahulu. Mekanisme caching ini biasanya digunakan untuk cache memori database.
Pseudo-LRU (PLRU): Ada kasus-kasus tertentu di mana LRU sangat sulit untuk diimplementasikan. Dalam kasus seperti itu mungkin cukup untuk mengetahui bahwa dalam kebanyakan kasus, salah satu item yang paling baru digunakan akan dihapus. Algoritma PLRU dapat digunakan di sana, karena hanya membutuhkan satu bit per item cache untuk bekerja.

Asosiatif set 2 arah: untuk cache CPU berkecepatan tinggi di mana bahkan PLRU terlalu lambat. Alamat item baru digunakan untuk menghitung satu dari dua lokasi yang mungkin dalam cache di mana item tersebut diperbolehkan untuk pergi. LRU dari keduanya dibuang. Hal ini membutuhkan satu bit per pasangan baris cache, untuk mengindikasikan yang mana dari keduanya yang paling baru digunakan.
Cache yang dipetakan langsung: untuk cache CPU berkecepatan tertinggi di mana bahkan cache asosiatif set 2 arah terlalu lambat. Alamat dari item baru digunakan untuk menghitung satu lokasi di cache dimana item tersebut diperbolehkan untuk masuk. Apapun yang ada di sana sebelumnya akan dibuang.
Paling jarang digunakan (LFU): LFU menghitung seberapa sering suatu item dibutuhkan. Barang-barang yang paling jarang digunakan akan dibuang terlebih dahulu.
Adaptive Replacement Cache (ARC): secara konstan menyeimbangkan antara LRU dan LFU, untuk meningkatkan hasil gabungan.
Algoritma caching Multi Queue (MQ): (oleh Y. Zhou J.F. Philbin dan Kai Li).

Hal-hal lain yang perlu dipertimbangkan:

Item dengan biaya yang berbeda: simpan item yang mahal untuk didapatkan, misalnya yang membutuhkan waktu lama untuk mendapatkannya.
Item yang memakan lebih banyak cache: Jika item memiliki ukuran yang berbeda, cache mungkin ingin membuang item yang besar untuk menyimpan beberapa item yang lebih kecil.
Item yang kedaluwarsa seiring dengan waktu: Beberapa cache menyimpan informasi yang kedaluwarsa (misalnya cache berita, cache DNS, atau cache browser web). Komputer mungkin membuang item karena item tersebut kadaluarsa. Tergantung pada ukuran cache, algoritma caching lebih lanjut untuk membuang item mungkin diperlukan.

Berbagai algoritma juga ada untuk menjaga koherensi cache. Ini hanya berlaku untuk situasi dimana beberapa cache independen digunakan untuk data yang sama (misalnya beberapa server database yang mengupdate file data bersama).

Lokasi memori mana yang bisa di-cache oleh lokasi cache yang mana

Pertanyaan dan Jawaban

T: Apa yang dimaksud dengan Algoritma Cache?

J: Algoritma Cache adalah algoritma yang digunakan untuk mengelola cache atau kelompok data. Algoritma ini memutuskan item mana yang harus dihapus dari cache ketika cache sudah penuh.

T: Apa yang dimaksud dengan hit rate?

J: Hit rate menggambarkan seberapa sering permintaan dapat dilayani dari cache.

T: Apa yang digambarkan oleh latensi?

J: Latency menggambarkan berapa lama item yang di-cache dapat diperoleh.

T: Apa yang dimaksud dengan algoritma optimal Belady?

J: Algoritma optimal Belady, juga dikenal sebagai algoritma peramal, adalah algoritma caching yang efisien yang selalu membuang informasi yang tidak akan dibutuhkan untuk waktu yang lama di masa depan. Hasil ini secara umum tidak dapat diimplementasikan dalam praktek karena memerlukan prediksi apa yang akan dibutuhkan jauh ke masa depan.

T: Bagaimana cara kerja Least Recently Used (LRU)?

J: LRU menghapus item yang paling baru digunakan terlebih dahulu dan membutuhkan pelacakan apa yang digunakan kapan dengan menggunakan "age bits" untuk setiap cache-line dan melacak mana yang paling baru digunakan berdasarkan age-bits. Setiap kali sebuah baris-cache digunakan, semua usia baris-cache lainnya diubah sesuai dengan itu.

T: Bagaimana cara kerja Most Recently Used (MRU)?

J: MRU menghapus item yang paling baru digunakan terlebih dahulu dan mekanisme cache ini biasanya digunakan untuk cache memori database.

T: Algoritma apa lagi yang ada untuk mempertahankan koherensi cache?

J; Ada berbagai algoritma untuk menjaga koherensi cache ketika beberapa cache independen digunakan untuk data bersama, seperti beberapa server database yang memperbarui satu file data bersama.