LRU Cache

En Az Yakın Zamanda Kullanılan Önbellek

Türkçe karşılığı: LRU önbellek
Okunuşu: el ar yu keş

Günlük kullanımda çoğunlukla İngilizcesi tercih edilir.

Güncellendi 3 Ekim 20262 dk okuma

Kısaca

LRU (least recently used) cache, sabit sayıda öğe tutar ve dolunca en uzun süredir kullanılmayanı atar; son kullanılan verinin yine gerekeceğini varsayar.

LRU cache nedir?

Önbellekler tasarım gereği küçüktür; bu yüzden dolduklarında bir tahliye (eviction) politikasına ihtiyaç duyarlar. LRU, yakınlığın geleceği öngördüğünü varsayar: bir saniye önce okunan bir şeyin, bir saattir dokunulmamış bir şeyden tekrar okunma olasılığı daha yüksektir. Her öğe okunduğunda ya da yazıldığında en son kullanılan olur; yer gerektiğinde de en az yakın zamanda kullanılan öğe çıkarılır.

Klasik gerçekleştirim, hem aramaları hem güncellemeleri O(1) yapmak için iki yapıyı birleştirir. Bir hash map bir öğeyi anahtarıyla anında bulur, çift yönlü bir bağlı liste de öğeleri kullanım sırasına göre tutar: bir öğeyi başa taşımak da sondaki öğeyi çıkarmak da sabit süreli işaretçi değişiklikleridir. Bu tasarım iyi bilinen bir mülakat sorusudur.

LRU her yerdedir. Python onu functools.lru_cache dekoratörü olarak sunar, Java'nın LinkedHashMap'i bir LRU olarak yapılandırılabilir, Redis anahtarları yaklaşık bir LRU politikasıyla çıkarabilir; işletim sistemleri ve CPU'lar da hangi bellek sayfalarını ve önbellek satırlarını tutacaklarına LRU benzeri kurallarla karar verir.

Sık yapılan bir yanlış, LRU'nun her zaman en iyi politika olduğunu düşünmektir. Büyük bir veri kümesinin tek seferlik bir taraması gerçekten popüler öğelerin hepsini dışarı itebilir; bazı öğelerin sürekli popüler olduğu iş yükleri de LFU (least frequently used) ya da yakınlık ile sıklığı birleştiren daha yeni politikalarla daha iyi sonuç verebilir. Seçmenin yolu, gerçek trafikte isabet oranını ölçmektir.

Önemli noktalar

LRU cache dolduğunda en uzun süredir kullanılmayan öğeyi çıkarır.
Yakın zamanda kullanılan verinin yakında yine gerekeceğini varsayar.
Bir hash map ile çift yönlü bağlı liste O(1) get ve put sağlar.
Python'un lru_cache'i, Java'nın LinkedHashMap'i ve Redis LRU tahliyesi sunar.
Büyük taramalar onu boşaltabilir; bazı iş yüklerine LFU ve karma politikalar daha iyi uyar.

Örnek

O(1) işlemli bir LRU cache (Python)python

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = OrderedDict()        # a hash map that remembers order

    def get(self, key):
        if key not in self.items:
            return None
        self.items.move_to_end(key)       # now the most recently used
        return self.items[key]

    def put(self, key, value):
        self.items[key] = value
        self.items.move_to_end(key)
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)   # evict the least recently used

cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2); cache.get("a"); cache.put("c", 3)
print(list(cache.items))   # ['a', 'c']: "b" was evicted

Sık sorulan sorular

LRU cache nasıl gerçekleştirilir?

Genellikle anahtarlardan çift yönlü bir bağlı listenin düğümlerine giden bir hash map ile. Liste öğeleri kullanım sırasına göre tutar; böylece bir öğeyi başa taşımak da en eskisini çıkarmak da O(1) olur.

LRU ile LFU arasındaki fark nedir?

LRU en az yakın zamanda kullanılan öğeyi çıkarır. LFU ise genel olarak en az sıklıkla kullanılan öğeyi çıkarır. LRU değişen kalıplara hızla uyum sağlar; LFU sürekli popüler olan öğeleri daha iyi korur.

Python'un lru_cache'i ne yapar?

functools.lru_cache, bir fonksiyonun sonuçlarını argümanlarına göre hatırlayan (memoize eden), belirli sayıda sonucu tutan ve dolduğunda en az yakın zamanda kullanılanı çıkaran bir dekoratördür.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin