Eviction Nedir? LRU algoritması nasıl çalışmaktadır?

Bilgisayar ve çalışma mantığı düşünüldüğünde akla ilk gelen konulardan birisi olan cache, kendi bünyesinde çeşitli özelliklere, politikalara ve stratejilere sahiptir. Bu stratejilerinden önemli olanların başını çeken ise eviction’dur. Cache eviction, sağlıklı bir cache altyapısı ve memory’yi verimli kullanabilmek için olmazsa olmazlardandır. Bu bağlamda birlikte eviction nedir ve nasıl bir özelliktir birlikte inceleyeceğiz.

Dilerseniz eviction’a geçmeden önce kısaca cache’in ne olduğundan bahsedelim.

Cache nedir?

Cache, temel itibariyle sık kullanıldığı düşünülen verilerin veya operasyon çıktılarının disk yerine hafızadan(memory) getirilerek daha hızlı cevaplar alınmasını sağlayan performans, hız ve maliyet anlamında getirileri olan bir yazılım bileşenidir.

Eviction nedir?

Cache’in hafızada çalışmasına bağlı olarak eviction, cache sisteminin bir nevi sağlığının korunabilmesi için hafıza limiti geçildiğinde onun içerisinde yer alan gereksiz olduğu ve ileride üzerinde işlem yapılacağının düşünülmediği verilerin temizlenmesini sağlayan bir süreçtir.

Verilerin temizlenerek yerine yenilerinin alınmasını sağlayan sürecin çalışma mantığını düzenleyen universal düzeyde çeşitli policyler ve algoritmalar yer aldığı gibi ihtiyaç ve use case’lere göre de çeşitli davranışlar configure edilebilmektedir.

Eviction özelliği Redis gibi veri yapı sunucularında da aktif olarak kullanılmaktadır. Özellikle redis’in sahip olduğu veri yığınını kontrol altında tutarak yeni gelen verilere yol açabilmesi için bu stratejiyi aktif şekilde kullanması gerekmektedir. Biz de bu yazımızda eviction işleminin örneklendirilmesini redis üzerinden yapacağız.

Eviction işleminin gerçekleşebilmesi için en temel gerekliliklerden bir tanesi verileri tutan yapımızın en yüksek sahip olabileceği değerin belirlenmesidir. Bu redis özelinde manuel tanımlanması gereken bir değer iken diğer daha kapsamlı memory yönetim yapılarında otomatik şekilde gerçekleşen süreçlerle de karşılaşabiliriz.

Bir diğer gerekliliğimiz ise artık sunucunun daha fazla veriyi aynı anda içerisinde bulunduramayacağı bir ortamın oluşması yani hafızanın dolması gerekmektedir. Bu durumda sunucumuz artık taşacak ve yeni gelen verileri alabilmek için tuttuğu verilerden bazılarını silmek durumunda kalacaktır. Silmek zorunluluğu karşısında da en kritik dönüm noktalarından birisi de bu verilerden hangisinin gönderilmek zorunda olduğudur.

LRU algoritması nasıl çalışır?

Şimdi süreci tekrar adım adım gözden geçirelim.

• Veri sunucumuz veya yapımız sahip olabileceği maksimum değere kadar veriye sahip olmuş durumdadır
• Tam bu durumda içeride yer alan verilerden içeriye alınması gereken veri boyutu kadar bir kısmı gönderilmek zorundadır
• Gönderilmesi gereken verinin seçilmesi gerekmektedir. Bu seçim işlemi için de birçok algoritma, policy ve strateji yer almaktadır.

LRU ve LFU gibi policyler bu işlem için hâli hazırda yer alan universal algoritmalardır. Bunların da kullanım senaryolarına göre çeşitli config edilebilen seçenekleri vardır.

Bu algoritmalardan en popüler kullanılanı ise LRU’dur. LRU’nun açılımını kullanım alanına göre iki şekilde yapabiliriz.

• least recently used (en son kullanılan)
• least recently updated (en son update olan)

Kullanım türüne göre en ilk kullanılan veya en ilk update olan veri silinmek için adaylardır. Bu bağlamda yeni bir veri geldiğinde ve yapımız OOM (out of memory) durumuna geçtiğinde silinecek verilerimizi seçerken en ilk kullanılan (yani kullanımından büyük ihtimalle diğer verilere göre daha uzun süre geçmiş) verileri daha öncelikli tutarak onların silinmesini sağlar.

Örneğin 4 slotluk alana sahip bir memory’e sahip olduğumuzu düşünelim. Bu slotlara sırasıyla;

• 9, 8, 2, 5

rakamları yerleşiyor. Ardından 4 rakamının hafızaya eklenmesi için bir talebin geliyor. Bu durumda sizce hangi slottaki veri yerini kaybeder?

Slotlara soldan yerleşildiğini düşünürsek ilk yerleşen bir diğer deyişle en ilk kullanılan 9 rakamının bulunduğu slot temizlenir ve yerine 4 rakamı konur.

Slotlarımızın yeni görüntüsü;

• 4, 8, 2, 5 

şeklinde olacaktır.

Gördüğünüz gibi yeni verinin kaybını engellemek için policy gereği gelecekte en az ihtiyaç duyacağımızı düşündüğümüz veriyi silerek yerine yeni verinin yerleşmesini sağladık. Bu davranış ile cache işlemleri yapan hemen hemen her yapıda karşılaşmamız mümkündür.

Bu yazımızda eviction nedir üzerine odaklanırken cache, eviction’un en popüler algoritmalarından biri olan LRU’yuna da değindik. Yazı hakkında yorumlarınızı iletebilirsiniz. Dilerseniz hafızanın geri verilmesi: garbage collector başlıklı yazımıza da göz atabilirsiniz.

Kaynaklar

https://www.geeksforgeeks.org/program-for-least-recently-used-lru-page-replacement-algorithm/