Лучший способ реализовать кеш LRU

Ответ 1

Если вам нужен кеш LRU, самым простым в Java является LinkedHashMap. Поведение по умолчанию - FIFO, но вы можете изменить его на "порядок доступа", который делает его кеш LRU.

public static <K,V> Map<K,V> lruCache(final int maxSize) {
    return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    };
}

Примечание. Я использую конструктор который изменяет коллекцию с самого нового первого до самого последнего, используемого в первую очередь.

Из Javadoc

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)
Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode.
Parameters:
initialCapacity - the initial capacity
loadFactor - the load factor
accessOrder - the ordering mode - true for access-order, false for insertion-order

Когда accessOrder true, LinkedHashMap повторно упорядочивает порядок карты всякий раз, когда вы получаете() запись, которая не является последней.

Таким образом, самая старая запись является наименее используемой.

Ответ 2

Обычно кэши LRU представлены как структуры LIFO - одна очередь элементов. Если тот, который предоставлен вашим стандартом, не позволяет удалять объекты из середины, например, чтобы поместить их сверху, тогда вам, возможно, придется сворачивать свои собственные.

Ответ 3

Учитывая, что кеш позволяет одновременный доступ, проблема хорошего дизайна кеша LRU сводится к:

a) Можем ли мы избежать использования мьютекса при обновлении двух структур (структура кэша и структура LRU).

b) Будет ли операция чтения (получения) кеша требовать mutex?

Более подробно: скажем, если мы реализуем это с помощью java.util.concurrent.ConcuurentHashMap(структура кэша) и java.util.concurrent.ConcurrentLinkedQueue(структура LRU)

a) Блокировка обеих этих структур при редактировании - addEntry(), removeEntry(), evictEntries() и т.д.

b) Вышеупомянутое может, вероятно, проходить как медленные операции записи, но проблема даже для операции чтения (получения), нам нужно применить блокировку для обеих структур. Потому что get будет означать перенос записи перед очередью для стратегии LRU. (Предполагая, что записи удалены из конца очереди).

Используя эффективные параллельные структуры, такие как ConcurrentHashMap, и подождите ConcurrentLinkedQueue, а затем блокируя их, теряет всю цель.

Я реализовал кеш LRU с тем же подходом, однако структура LRU была обновлена ​​асинхронно, устраняя необходимость использования любого мьютекса при доступе к этим структурам. LRU является внутренней деталью Cache и может быть реализована любым способом, не затрагивая пользователей кеша.

Позже я также прочитал о ConcurrentLinkedHashMap

https://code.google.com/p/concurrentlinkedhashmap/

И обнаружил, что он также пытается сделать то же самое. Не используется эта структура, но, возможно, она может быть хорошей.

Ответ 4

Я хотел бы расширить некоторые из этих предложений с помощью двух возможных реализаций. Один небезопасный поток и тот, который может быть.

Вот простейшая версия с unit test, которая показывает, что она работает.

Сначала неконкурентная версия:

import java.util.LinkedHashMap;
import java.util.Map;

public class LruSimpleCache<K, V> implements LruCache <K, V>{

    Map<K, V> map = new LinkedHashMap (  );


    public LruSimpleCache (final int limit) {
           map = new LinkedHashMap <K, V> (16, 0.75f, true) {
               @Override
               protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
                   return super.size() > limit;
               }
           };
    }
    @Override
    public void put ( K key, V value ) {
        map.put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map.get(key);
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        V value =  map.get ( key );
        if (value!=null) {
            map.remove ( key );
            map.put(key, value);
        }
        return value;
    }

    @Override
    public void remove ( K key ) {
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }


}

Истинный флаг будет отслеживать доступ к get и puts. См. JavaDocs. RemoveEdelstEntry без истинного флага для конструктора просто реализует кеш FIFO (см. Примечания ниже на FIFO и removeEldestEntry).

Вот тест, который доказывает, что он работает как кеш LRU:

public class LruSimpleTest {

    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleCache<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        if ( !ok ) die ();

    }

Теперь для параллельной версии...

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class LruSimpleConcurrentCache<K, V> implements LruCache<K, V> {

    final CacheMap<K, V>[] cacheRegions;


    private static class CacheMap<K, V> extends LinkedHashMap<K, V> {
        private final ReadWriteLock readWriteLock;
        private final int limit;

        CacheMap ( final int limit, boolean fair ) {
            super ( 16, 0.75f, true );
            this.limit = limit;
            readWriteLock = new ReentrantReadWriteLock ( fair );

        }

        protected boolean removeEldestEntry ( final Map.Entry<K, V> eldest ) {
            return super.size () > limit;
        }


        @Override
        public V put ( K key, V value ) {
            readWriteLock.writeLock ().lock ();

            V old;
            try {

                old = super.put ( key, value );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return old;

        }


        @Override
        public V get ( Object key ) {
            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.get ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;
        }

        @Override
        public V remove ( Object key ) {

            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.remove ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public V getSilent ( K key ) {
            readWriteLock.writeLock ().lock ();

            V value;

            try {

                value = this.get ( key );
                if ( value != null ) {
                    this.remove ( key );
                    this.put ( key, value );
                }
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public int size () {
            readWriteLock.readLock ().lock ();
            int size = -1;
            try {
                size = super.size ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return size;
        }

        public String toString () {
            readWriteLock.readLock ().lock ();
            String str;
            try {
                str = super.toString ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return str;
        }


    }

    public LruSimpleConcurrentCache ( final int limit, boolean fair ) {
        int cores = Runtime.getRuntime ().availableProcessors ();
        int stripeSize = cores < 2 ? 4 : cores * 2;
        cacheRegions = new CacheMap[ stripeSize ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) {

        cacheRegions = new CacheMap[ concurrency ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    private int stripeIndex ( K key ) {
        int hashCode = key.hashCode () * 31;
        return hashCode % ( cacheRegions.length );
    }

    private CacheMap<K, V> map ( K key ) {
        return cacheRegions[ stripeIndex ( key ) ];
    }

    @Override
    public void put ( K key, V value ) {

        map ( key ).put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map ( key ).get ( key );
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        return map ( key ).getSilent ( key );

    }

    @Override
    public void remove ( K key ) {
        map ( key ).remove ( key );
    }

    @Override
    public int size () {
        int size = 0;
        for ( CacheMap<K, V> cache : cacheRegions ) {
            size += cache.size ();
        }
        return size;
    }

    public String toString () {

        StringBuilder builder = new StringBuilder ();
        for ( CacheMap<K, V> cache : cacheRegions ) {
            builder.append ( cache.toString () ).append ( '\n' );
        }

        return builder.toString ();
    }


}

Вы можете понять, почему я сначала закрываю неконкурентную версию. Вышеупомянутые попытки создать некоторые полосы для уменьшения блокировки. Таким образом, мы хешируем ключ, а затем просматриваем этот хэш, чтобы найти фактический кеш. Это делает размер ограничения более предположениями/приблизительными предположениями в пределах достаточной суммы ошибок в зависимости от того, насколько хорошо распространен алгоритм хеширования ключей.

Ответ 5

Проблема:

Создайте кеш LRU и сохраните объект Employee Max = 5 объектов и узнайте, кто входит в систему первым и после....

package com.test.example.dto;

import java.sql.Timestamp;
/**
 * 
 * @author Vaq[email protected]
 *
 */
public class Employee implements Comparable<Employee> {
    private int     id;
    private String  name;
    private int     age;
    private Timestamp loginTime ;

public int getId() {
    return id;
}

public void setId(int id) {
    this.id = id;
}

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

public int getAge() {
    return age;
}

public void setAge(int age) {
    this.age = age;
}

public Timestamp getLoginTime() {
    return loginTime;
}

public void setLoginTime(Timestamp loginTime) {
    this.loginTime = loginTime;
}

@Override
public String toString() {
    return "Employee [id=" + id + ", name=" + name + ", age=" + age + ", loginTime=" + loginTime + "]";
}

Employee(){}

public Employee(int id, String name, int age, Timestamp loginTime) {
    super();
    this.id = id;
    this.name = name;
    this.age = age;
    this.loginTime = loginTime;
}

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + age;
    result = prime * result + id;
    result = prime * result + ((loginTime == null) ? 0 : loginTime.hashCode());
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null) return false;
    if (getClass() != obj.getClass()) return false;
    Employee other = (Employee) obj;
    if (age != other.age) return false;
    if (id != other.id) return false;
    if (loginTime == null) {
        if (other.loginTime != null) return false;
    } else if (!loginTime.equals(other.loginTime)) return false;
    if (name == null) {
        if (other.name != null) return false;
    } else if (!name.equals(other.name)) return false;
    return true;
}

@Override
public int compareTo(Employee emp) {
    if (emp.getLoginTime().before( this.loginTime) ){
        return 1;
    } else if (emp.getLoginTime().after(this.loginTime)) {
        return -1;
    }
    return 0;
}


}

LRUObjectCacheExample

package com.test.example;

import java.sql.Timestamp;
import java.util.Calendar;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import com.test.example.dto.Employee;
/**
 * 
 * @author [email protected]
 *
 */
public class LRUObjectCacheExample {


    LinkedHashMap<Employee, Boolean>    lruCacheLinkedQueue;

public LRUObjectCacheExample(int capacity) {
    lruCacheLinkedQueue = new LinkedHashMap<Employee, Boolean>(capacity, 1.0f, true) {
        /**
         * 
         */
        private static final long   serialVersionUID    = 1L;

        @Override
        protected boolean removeEldestEntry(
                //calling map entry method
                Map.Entry<Employee, Boolean> eldest) {
            return this.size() > capacity;
        }
    };
}

void addDataIntoCache(Employee employee) {
    lruCacheLinkedQueue.put(employee, true);
    displayLRUQueue();
}

boolean checkIfDataPresentIntoLRUCaache(int data) {
    return lruCacheLinkedQueue.get(data) != null;
}

 void deletePageNo(int data) {
    if (lruCacheLinkedQueue.get(data) != null){
            lruCacheLinkedQueue.remove(data);
    }
    displayLRUQueue();
}

 void displayLRUQueue() {
    System.out.print("-------------------------------------------------------"+"\n");
    System.out.print("Data into LRU Cache : ");
    for (Entry<Employee, Boolean> mapEntry : lruCacheLinkedQueue.entrySet()) {
        System.out.print("[" + mapEntry.getKey() + "]");
    }
    System.out.println("");
}

public static void main(String args[]) {
    Employee employee1 = new Employee(1,"Shahbaz",29, getCurrentTimeStamp());
    Employee employee2 = new Employee(2,"Amit",35,getCurrentTimeStamp());
    Employee employee3 = new Employee(3,"viquar",36,getCurrentTimeStamp());
    Employee employee4 = new Employee(4,"Sunny",20,getCurrentTimeStamp());
    Employee employee5 = new Employee(5,"sachin",28,getCurrentTimeStamp());
    Employee employee6 = new Employee(6,"Sneha",25,getCurrentTimeStamp());
    Employee employee7 = new Employee(7,"chantan",19,getCurrentTimeStamp());
    Employee employee8 = new Employee(8,"nitin",22,getCurrentTimeStamp());
    Employee employee9 = new Employee(9,"sanuj",31,getCurrentTimeStamp());
    //
    LRUObjectCacheExample lru = new LRUObjectCacheExample(5);
    lru.addDataIntoCache(employee5);//sachin
    lru.addDataIntoCache(employee4);//Sunny
    lru.addDataIntoCache(employee3);//viquar
    lru.addDataIntoCache(employee2);//Amit
    lru.addDataIntoCache(employee1);//Shahbaz -----capacity reached
    //
        lru.addDataIntoCache(employee6);/Sneha
        lru.addDataIntoCache(employee7);//chantan
        lru.addDataIntoCache(employee8);//nitin
        lru.addDataIntoCache(employee9);//sanuj
        //
        lru.deletePageNo(3);
        lru.deletePageNo(4);

    }
    private static Timestamp getCurrentTimeStamp(){
        return new java.sql.Timestamp(Calendar.getInstance().getTime().getTime());
    }

}

Результаты:

**Data into LRU Cache :** 
[Employee [id=1, name=Shahbaz, age=29, loginTime=2015-10-15 18:47:28.1
[Employee [id=6, name=Sneha, age=25, loginTime=2015-10-15 18:47:28.125
[Employee [id=7, name=chantan, age=19, loginTime=2015-10-15 18:47:28.125
[Employee [id=8, name=nitin, age=22, loginTime=2015-10-15 18:47:28.125
[Employee [id=9, name=sanuj, age=31, loginTime=2015-10-15 18:47:28.125

Ответ 6

LinkedHashMap позволяет переопределить функцию removeEldestEntry, так что всякий раз, когда выполняется put, вы можете указать, следует ли удалять самую старую запись или нет, что позволяет реализовать LRU.

myLRUCache = new LinkedHashMap<Long,String>() {
protected boolean removeEldestEntry(Map.Entry eldest) 
{ 
if(this.size()>1000)
    return true;
  else
      return false;
}
}; 

Ответ 7

Для доступа O (1) нам нужна хэш-таблица и для поддержания порядка мы можем использовать DLL. Basic algo - из номера страницы мы можем перейти в DLL node с помощью хеш-таблицы. Если страница существует, мы можем переместить node в голову DLL, иначе вставьте node в DLL и хеш-таблицу. Если размер DLL заполнен, мы можем удалить последний использованный node из хвоста.

Вот реализация, основанная на двусвязном списке и unordered_map в С++.

#include <iostream>
#include <unordered_map>
#include <utility>

using namespace std;

// List nodeclass
class Node
{
    public:
    int data;
    Node* next;
    Node* prev;
};

//Doubly Linked list
class DLList
{
    public:

    DLList()
    {
        head = NULL;
        tail = NULL;
        count = 0;
    }

    ~DLList() {}

    Node* addNode(int val);
    void print();
    void removeTail();
    void moveToHead(Node* node);

    int size()
    {
        return count;
    }

    private:
    Node* head;
    Node* tail;
    int count;
};

// Function to add a node to the list

Node* DLList::addNode(int val)
{
    Node* temp = new Node();

    temp->data = val;
    temp->next = NULL;
    temp->prev = NULL;

    if ( tail == NULL )
    {
        tail = temp;
        head = temp;
    }
    else
    {
        head->prev = temp;
        temp->next = head;
        head = temp;
    }

    count++;

    return temp;
}

void DLList::moveToHead(Node* node)
{
    if (head == node)
        return;

    node->prev->next = node->next;

    if (node->next != NULL)
    {
        node->next->prev = node->prev;
    }
    else
    {
        tail = node->prev;
    }
        node->next = head;
        node->prev = NULL;
        head->prev = node;
        head = node;
}

void DLList::removeTail()
{
    count--;

    if (head == tail)
    {
        delete head;
        head = NULL;
        tail = NULL;
    }
    else
    {
        Node* del = tail;
        tail = del->prev;
        tail->next = NULL;
        delete del;
    }
}

void DLList::print()
{
    Node* temp = head;

    int ctr = 0;

    while ( (temp != NULL) && (ctr++ != 25) )
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

class LRUCache
{
    public:
        LRUCache(int aCacheSize);
        void fetchPage(int pageNumber);

    private:
        int cacheSize;
        DLList dlist;
        unordered_map< int, Node* > directAccess;
};

    LRUCache::LRUCache(int aCacheSize):cacheSize(aCacheSize) { }

    void LRUCache::fetchPage(int pageNumber)
    {
        unordered_map< int, Node* >::const_iterator it = directAccess.find(pageNumber);

        if (it != directAccess.end())
        {
            dlist.moveToHead( (Node*)it->second);
        }
        else
        {
            if (dlist.size() == cacheSize-1)
               dlist.removeTail();

            Node* node = dlist.addNode(pageNumber);

            directAccess.insert(pair< int, Node* >(pageNumber,node));
        }

        dlist.print();
    }

    int main()
    {
        LRUCache lruCache(10);

        lruCache.fetchPage(5);
        lruCache.fetchPage(7);
        lruCache.fetchPage(15);
        lruCache.fetchPage(34);
        lruCache.fetchPage(23);
        lruCache.fetchPage(21);
        lruCache.fetchPage(7);
        lruCache.fetchPage(32);
        lruCache.fetchPage(34);
        lruCache.fetchPage(35);
        lruCache.fetchPage(15);
        lruCache.fetchPage(37);
        lruCache.fetchPage(17);
        lruCache.fetchPage(28);
        lruCache.fetchPage(16);

        return 0;
}

Ответ 8

Расширение ответа Питера Лоури

Метод removeEldestEntry(java.util.Map.Entry) может быть переопределен, чтобы наложить политику для автоматического удаления устаревших сопоставлений при добавлении новых сопоставлений на карту.

Таким образом, поведение FIFO LinkedHashMap может быть переопределено, чтобы сделать LRU

public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private int cacheSize;

    public LRUCache(int cacheSize) {
        super(cacheSize * 4 / 3, 0.75f, true);
        this.cacheSize = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() >= cacheSize;
    }

    public static void main(String args[]) {
        LRUCache<Integer, Integer> lruCache = new LRUCache<>(5);

        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.put(1, 4);
        lruCache.put(2, 5);
        lruCache.put(7, 6);

        System.out.println(lruCache.keySet());

        lruCache.put(1, 4);
        lruCache.put(2, 5);

        System.out.println(lruCache.keySet());
    }
} 

Ответ 9

class LRU {
    Map<String, Integer> ageMap = new HashMap<String, Integer>();
    int age = 1;

    void addElementWithAge(String element) {

        ageMap.put(element, age);
        age++;

    }

    String getLeastRecent(Map<String, Integer> ageMap) {
        Integer oldestAge = (Integer) ageMap.values().toArray()[0];
        String element = null;
        for (Entry<String, Integer> entry : ageMap.entrySet()) {
            if (oldestAge >= entry.getValue()) {
                oldestAge = entry.getValue();
                element = entry.getKey();
            }
        }
        return element;
    }

    public static void main(String args[]) {
        LRU obj = new LRU();
        obj.addElementWithAge("M1");
        obj.addElementWithAge("M2");
        obj.addElementWithAge("M3");
        obj.addElementWithAge("M4");
        obj.addElementWithAge("M1");
    }

}