Java’da LRU Cache Uygulaması

Cache, daha hızlı erişim için verinin geçici olarak depolandığı bir alan olarak tanımlanabilir, uygulamaya göre bellekte, lokal diskte ya da network üzerinde başka bir depolama biriminde bulunabilir. Temel mantık veriye daha kısa sürede erişmektir. Yazılımlarımızda zaman zaman oluşturduğumuz nesneleri bellekte kendimizin oluşturacağı bir cache alanı üzerinde tutmak isteyebiliriz, bu nesneler oluşturulması, elde edilmesi pahalı (network üzerinden bir yerden alınan ya da oluşturulması bellek veya cpu olarak sistem kaynaklarını fazla kullanan) olarak kabul edebileceğimiz nesneledir, bir kere oluşturduktan sonra onlara sıkça erişecek isek bunları tekrar tekrar oluşturmak yerine bir cache üzerinde tutabilir ve daha hızlı erişebiliriz, tabi tek kriterimiz bu değil, cache dinamik bir alandır ve sürekli bir şeyler eklenir ya da çıkarılır, örneğin artık pek erişmeyeceğimiz bir nesnemizi bir süre sonra cache’ten atabiliriz, çünkü cache sınırlı bir alandır, yeniler geldikçe ihtiyaç duyulmayanlar çıkarılır ve yenilere yer açılır.

Cache’e ekleme-çıkarma işlemleri için kullanılan farklı algoritmalar (cache policy) mevcuttur, ben bunlardan bir tanesi olan LRU (least recently used) policy kullanmak istiyorum. Bunun gibi MRU (most recently used), SLRU (segmented LRU), LFU (least frequently used) v.s. gibi daha bir çok algoritma mevcuttur, tüm bu algoritmalar cache’e insert ve remove policy lerini tanımlarlar. LRU cache policy temelde basit bir mantığa dayalıdır, cache’e yeni bir insert yapılacağı zaman cache’teki en eski eleman cache’ten çıkarılır, hızlı bir yöntemdir.

Algoritma adımlarımızı oluşturalım, zaten burada tek bir case’imiz var o da  cache’ten bir nesnenin sorgulanması eğer bulunmuyorsa gidip ilgili kaynaktan nesnenin alınıp cache’e insert edilmesi, tabi eğer cache kapasitesi dolmuş ise cache’ten en uzak zamanda kullanılan (least recently) elemanın atılması şeklinde.

Biraz örneklersek, elimizde 3 tane nesnemizi alabilecek bir cache’imiz olsun

cache’in ilk hali (t = 0 anı)

 
 
 

t=1 anında id = 10 olan nesnemize (elde edilmesi pahalı olan) ihtiyaç oldu, hemen ilk olarak cache’ten sorgulanması gerek,cache’te herhangi bir nesne yok o halde id = 10 olan nesne oluşturulacak, nesne oluşturuldu ve hemen daha sonra ihtiyaç olursa hızlıca erişilebilsin diye cache’e eklendi

Nesne (id=10, t=1)
 
 

t=3 anında id = 11 olan nesneye ihtiyaç duyuldu, yine cache’te yok, oluşturuldu, cache kapasitesi yeterli, cache’e eklendi

Nesne (id=10, t=1)
Nesne (id=11, t=3)
 

t = 4 anında id = 10 olan nesneye ihtiyaç duyuldu, bu nesne cache’te mevcut, oradan alınıp kullanıldı, tabi t değeri güncellendi, çünkü erişme zamanı daha güncel

 

Nesne (id=10, t=4)
Nesne (id=11, t=3)
 

t = 5 anında id = 12 olan nesneye ihtiyaç duyuldu, yine cache’te yok, oluşturuldu, cache kapasitesi yeterli, cache’e eklendi

Nesne (id=10, t=4)
Nesne (id=11, t=3)
Nesne (id=12, t=5)

t = 7 anında id = 13 olan nesneye ihtiyaç duyuldu, nesne cache’te yok, bu nesne oluşturuldu ve cache’e eklenmesi gerek ancak cache kapasitesi dolu. LRU policy gereği en uzak zamanda kullanılan nesne cache’ten atılacak ve yeni nesne cache’e insert edilecek. id’si 11 olan nesnemiz en uzak zamanda kullanılmış, en eski nesnemiz, bu nesne cache’ten atılacak.

Nesne (id=10, t=4)
Nesne (id=13, t=7)
Nesne (id=12, t=5)

t = 8 anında id = 14 olan nesneye ihtiyaç duyuldu, nesne cache’te yok, nesne oluşturuldu ve cache’e insert edildi, tabi kapasiteden dolayı LRU policy ile bir nesne cache’ten atıldı.

Nesne (id=14, t=8)
Nesne (id=13, t=7)
Nesne (id=12, t=5)

 

Kısaca LRU algoritması ile cache’in kullanımını anlatmaya çalıştım, şimdi de java dilinde bu algoritmayı kullanan cache’imizi implement edelim. Öncelikle cache olarak kullanacağımız bir veri yapısına ihitiyacımız var, burada HashMap kullanmak mümkün, çünkü cache’ten eleman get etmek istediğimizde cache üzerinde search karmaşıklığı düşük olan bir veri yapısı kullanmak performans açısından olumlu olacaktır, HashMap için get/put karmaşası O(1) dir. Peki key-value çiftleri olarak veriyi tutan HashMap LRU cache implementasyonumuz için tek başına yeterli midir, değil çünkü şöyle bir yapı kurmaya çalışıyoruz, en son kullanılan eleman cache’in en sonuna atılsın eğer cache’ten bir eleman silinecekse (kapasite dolduğu için) hep en baştaki eleman silinsin. Bunu nasıl sağlayabiliriz, bunun için key lerin tutulduğu ayrı bir liste kullanabiliriz. Yani hangi elemanın least recently used olduğunu bir liste üzerinden takip ederken elemanın kendisini hashmap üzerinden takip ediyor olacağız.

Yani LinkedList bize kim en son erişildi bilgisini sağlarken HashMap ise bize cache’te olup olmadığı bilgisini sağlıyor olacak. Peki neden LinkedList, çünkü burada key’ler erişimlere göre sürekli olarak başa alınacak, yani insert yoğun işlemler gerçekleştirilecek, bunun için insert karmaşası düşük olan bir List seçilmesi daha uygun görünüyor, LinkedList için bu değer O(1) şeklindedir.

Şimdi LRU cache’imizi java dilinde generic olarak implement etmeye çalışalım. Programımızda bir cache sınıfımız ve bunu kullanan bir test sınıfımız bulunacak.

LRU cache sınıfımız için implementasyon :

package lrucache;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
public final class GenericLRUCache <K,V>
{
       /**cache'in max size'ı (eleman sayısı)*/
       int mCacheSize;
       /**key ler için liste*/
       private LinkedList<K> mKeyList;
       /**asıl nesneler için hash map*/
       private HashMap<K, V> mCacheTable;
       /**constructor, cache'in max size'ını parametre olarak almakta*/
       public GenericLRUCache(int cacheSize)
       {
             mCacheSize = cacheSize;
             mKeyList = new LinkedList<K>();
             mCacheTable = new HashMap<K, V>(mCacheSize);
       }
       /**
        * key'i verlen nesnenin cache'te olup olmadığına bakar
        * bulursa nesneyi döndürür, bulamazsa null döner
        * HashMap ten key'i sorgular, eğer yoksa null döner, eğer nesneyi bulursa
        * bu nesnenin key'ini gidip LinkList'te en sona alır, çünkü kapasite
        * aşıldığında cache'ten eleman atılacağı zaman her zaman LinkList'teki ilk
        * elemanı atacağız cache'te bulunan bir eleman cache hit olursa o eleman en
        * sona alınarak LRU gereği cache'te daha uzun kalması sağlanmakta
        */
    public V getCachedItem(K key)
    {
        V tmpItem;
        tmpItem = mCacheTable.get(key);
        if(tmpItem != null)
        {
             mKeyList.remove(key);
             mKeyList.addLast(key);
             return tmpItem;
        }
        return null;
    }
    /**
     * cache'teki ilk elemanı siler, bunun için LinkList'ten ilk elemanın key'ini
     * alır bu key ile HashMap'te bulunan elemanı siler, aynı zamanda bu key'i
     * LinkList'ten de siler
     */
    private void removeFirstItem()
    {
       if(mKeyList.getFirst() != null)
       {
             K key = mKeyList.getFirst();
             mKeyList.removeFirst();
             mCacheTable.remove(key);
       }
    }
    /**
     * cache'te bulunmayan bir elemanın insert edilmesi için kullanılır
     * eğer kapasite dolmuşsa cache'teki ilk eleman cache'ten atılır, çünkü
     * ilk eleman least recently used olan elemandır
     * yeni elemanın key'i LinkList'in en sonuna eklenir, aynı zamanda yeni eleman
     * key value pair olarak HashMap'e de eklenir
     */
    public void insertToCache(K key, V value)
    {
        if (mCacheTable.size() >= mCacheSize)
            removeFirstItem();
        if(!mCacheTable.containsKey(key))
        {
             mKeyList.addLast(key);
             mCacheTable.put(key, value);
        }
    }
    /**
     * debug amaçlıdır, cache'te o an bulunan tüm elemanları bir iterator yardımı
     * ile console'a print eder
     */
    public void printAll()
    {
       Iterator<V> iterator = mCacheTable.values().iterator();
       while(iterator.hasNext())
       {
             System.out.println(iterator.next().toString());
       }
    }
}

Bu cache sınıfımızda tutacağımız test nesnelerimiz ise kişisel bilgileri tutan bir sınıfın instance ları olsun. Çok gerçekçi bir örnek olmasa da kişisel bilgilerin oluşturulmasının pahalı olduğunu varsayalım, bir takım uzun query’ler sonucu oluşturulduklarını düşünelim, dolayısıyla sıkça eriştiğimiz bir takım kişisel bilgi nesnelerinin hızlıca erişebileceğimiz bir yerde olmasını istemekteyiz.

package lrucache;
public final class PersonInfo
{
       int mId;
       String mName;
       String mSurname;
       int mAge;
       String mAddress;
       public static String SysNewLine = System.getProperty("line.separator");
       public PersonInfo(int id, String name, String surname, int age, String address)
       {
             mId = id;
             mName = name;
             mSurname = surname;
             mAge = age;
             mAddress = address;
       }
       @Override
       public String toString()
       {
             StringBuilder sb = new StringBuilder();
             sb.append("Id = ");
             sb.append(mId);
             sb.append(",");
             sb.append("Name = ");
             sb.append(mName);
             sb.append(",");
             sb.append("Surname = ");
             sb.append(mSurname);
             sb.append(",");
             sb.append("Age = ");
             sb.append(mAge);
             sb.append(",");
             sb.append("Address = ");
             sb.append(mAddress);
             sb.append(SysNewLine);
             return sb.toString();
       }
}

Şimdi de tüm kodumuzu test edebileceğimiz bir test sınıfı oluşturalım.

package lrucache;
public final class TestLRUCache
{
       private final int CACHE_SIZE = 5;
       private GenericLRUCache<Integer,PersonInfo> mGenericLRUCache;
       public TestLRUCache()
       {
             mGenericLRUCache = new GenericLRUCache<Integer, PersonInfo>(CACHE_SIZE);
       }
       public void testRun()
       {
             PersonInfo p1 = new PersonInfo(1, "AAA", "BBB", 25, "CE");
             mGenericLRUCache.insertToCache(p1.mId, p1);
             PersonInfo p2 = new PersonInfo(2, "CCC", "DDD", 22, "AG");
             mGenericLRUCache.insertToCache(p2.mId, p2);
             PersonInfo p3 = new PersonInfo(3, "EEE", "FFF", 27, "HY");
             mGenericLRUCache.insertToCache(p3.mId, p3);
             PersonInfo p4 = new PersonInfo(4, "GGG", "HHH", 32, "LK");
             mGenericLRUCache.insertToCache(p4.mId, p4);
             PersonInfo p5 = new PersonInfo(5, "III", "JJJ", 29, "PL");
             mGenericLRUCache.insertToCache(p5.mId, p5);
             mGenericLRUCache.printAll();
             System.out.println(mGenericLRUCache.getCachedItem(3) == null ? null : mGenericLRUCache.getCachedItem(3).toString());
             System.out.println(mGenericLRUCache.getCachedItem(7) == null ? null : mGenericLRUCache.getCachedItem(7).toString());
             PersonInfo p6 = new PersonInfo(6, "KKK", "LLL", 30, "UN");
             mGenericLRUCache.insertToCache(p6.mId, p6);
             mGenericLRUCache.printAll();
       }
       public static void main(String[] args)
       {
             TestLRUCache testLRUCache = new TestLRUCache();
             testLRUCache.testRun();
       }
}

Program çıktılarına bir göz atarsak

Id = 1,Name = AAA,Surname = BBB,Age = 25,Address = CE

Id = 2,Name = CCC,Surname = DDD,Age = 22,Address = AG

Id = 3,Name = EEE,Surname = FFF,Age = 27,Address = HY

Id = 4,Name = GGG,Surname = HHH,Age = 32,Address = LK

Id = 5,Name = III,Surname = JJJ,Age = 29,Address = PL

Id = 3,Name = EEE,Surname = FFF,Age = 27,Address = HY

null

Id = 2,Name = CCC,Surname = DDD,Age = 22,Address = AG

Id = 3,Name = EEE,Surname = FFF,Age = 27,Address = HY

Id = 4,Name = GGG,Surname = HHH,Age = 32,Address = LK

Id = 5,Name = III,Surname = JJJ,Age = 29,Address = PL

Id = 6,Name = KKK,Surname = LLL,Age = 30,Address = UN

Önce 5 adet PersonInfo ekledik ve bunları print ettik, ardından cache’te olduğunu bildiğimiz bir elemana key kullanarak cache’ten eriştik, ardından cache’te bulunmayan bir elemana erişmek istedik, son olarak da kapasitesi dolu olan cache’imize yeni bir eleman insert ederek least recently used olan elemanın atılıp yerine son koyduğumuz elemanın cache’e insert olduğunu gördük.

Bu implementasyonda LRU yaklaşımının detaylarına inmeye çalıştım, java dilinde küçük bir implementasyon ile test etmiş olduk, cache policy’lerin her birinin avantaj ve dezavantajları vardır, LRU bahsettiğim gibi basit bir mantık üzerine kuruludur, en performanslı yaklaşımdır diyemeyiz, ancak bir çok yerde işimizi görebilir. Gerçeklediğimiz cache yapımızı java içerisinde hazır olarak gelen LinkedHashMap collection’ı ile de gerçeklemek mümkün, java bize bu konuda gerekli desteği hazır olarak sunmakta, LinkedHashMap’te removeEldestEntry metodunu override ederek LRU cache olarak kullanmak mümkün.

Hemen tüm veriler aynı kalacak şekilde LinkedHashMap kullanarak örneğimizi değiştirirsek

package lrucache;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map.Entry;
public final class TestLinkedHashMap
{
       private final int CACHE_SIZE = 5;
       private LinkedHashMap<Integer,PersonInfo> mCache;
       public TestLinkedHashMap()
       {
             mCache = new LinkedHashMap<Integer, PersonInfo>(CACHE_SIZE)
                           {
                                  @Override
                                  protected boolean removeEldestEntry(Entry<Integer, PersonInfo> eldest)
                                  {
                                         return size() > CACHE_SIZE;
                                  }
                           };
       }
       public void testRun()
       {
             PersonInfo p1 = new PersonInfo(1, "AAA", "BBB", 25, "CE");
             mCache.put(p1.mId, p1);
             PersonInfo p2 = new PersonInfo(2, "CCC", "DDD", 22, "AG");
             mCache.put(p2.mId, p2);
             PersonInfo p3 = new PersonInfo(3, "EEE", "FFF", 27, "HY");
             mCache.put(p3.mId, p3);
             PersonInfo p4 = new PersonInfo(4, "GGG", "HHH", 32, "LK");
             mCache.put(p4.mId, p4);
             PersonInfo p5 = new PersonInfo(5, "III", "JJJ", 29, "PL");
             mCache.put(p5.mId, p5);
             Iterator<PersonInfo> iterator = mCache.values().iterator();
             while(iterator.hasNext())
                    System.out.println(iterator.next().toString());
             System.out.println(mCache.get(3) == null ? null : mCache.get(3).toString());
             System.out.println(mCache.get(7) == null ? null : mCache.get(7).toString());
             PersonInfo p6 = new PersonInfo(6, "KKK", "LLL", 30, "UN");
             mCache.put(p6.mId, p6);
             iterator = mCache.values().iterator();
             while(iterator.hasNext())
                    System.out.println(iterator.next().toString());
       }
       public static void main(String[] args)
       {
             TestLinkedHashMap testLinkedHashMap = new TestLinkedHashMap();
             testLinkedHashMap.testRun();
       }
}

Id = 1,Name = AAA,Surname = BBB,Age = 25,Address = CE

Id = 2,Name = CCC,Surname = DDD,Age = 22,Address = AG

Id = 3,Name = EEE,Surname = FFF,Age = 27,Address = HY

Id = 4,Name = GGG,Surname = HHH,Age = 32,Address = LK

Id = 5,Name = III,Surname = JJJ,Age = 29,Address = PL

Id = 3,Name = EEE,Surname = FFF,Age = 27,Address = HY

null

Id = 2,Name = CCC,Surname = DDD,Age = 22,Address = AG

Id = 3,Name = EEE,Surname = FFF,Age = 27,Address = HY

Id = 4,Name = GGG,Surname = HHH,Age = 32,Address = LK

Id = 5,Name = III,Surname = JJJ,Age = 29,Address = PL

Id = 6,Name = KKK,Surname = LLL,Age = 30,Address = UN

Görüldüğü üzere LinkedHashMap de aynı çıktıyı üretti, cache ihtiyacı olan durumlarda ve LRU policy kullanılmak isteniyorsa LinkedHashMap çok rahat kullanılabilir.

No Comments

Post a Comment

Comment
Name
Email
Website