Многопоточный объект → карта кэша объектов в Java?

Question

Я хочу коллекции в Java, которая:

• отображает произвольные Object с до Object с (не String или иначе ограничены ключи только)
• будет использоваться в качестве кэша; если ключ не находится в кэше, значение будет вычислено (это не должно быть встроено в коллекцию)
• будет доступны из нескольких потоков одновременно
• никогда не были элементы удалены из него
• должен быть очень эффективный для чтения (кеш-хит); не обязательно эффективно писать (ошибка кэша)

Это нормально, если кеш пропускает одновременно в нескольких потоках, вызывают избыточные вычисления; типичным случаем является то, что кеш в основном заполняется одним потоком сначала.

A Блок вокруг небезопасной хеш-таблицы не соответствует критерию эффективности чтения. Потоковые локальные кэши будут простыми, но означают, что новые потоки дороги, поскольку у них есть полные копии кеша.

Предпочитаются встроенные модули Java 1.5 или один или несколько классов, которые мы можем скопировать в наш проект, лицензированный MIT, а не большие внешние библиотеки.

Answer 1

Используйте Java HashMap параллельный

ConcurrentHashMap<object, object> table; 

public object getFromCache(object key) 
{ 
    value = table.get(key); 

    if (value == null) 
    { 
     //key isn't a key into this table, ie. it's not in the cache 
     value = calculateValueForKey(key) 
     object fromCache = table.putIfAbsent(key, value); 
    } 

    return value; 
} 

/** 
* This calculates a new value to put into the cache 
*/ 
public abstract object calculateValueForKey(object key); 

нотабене Это больше не является общим решением для многопоточного кэширования, поскольку он полагается на заявленный факт, что объекты неизменяемы, и, следовательно, эквивалентность объектов не имеет значения.

Answer 2

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

Используйте локальную переменную потока (java.lang.ThreadLocal), которая содержит хэш-таблицу для потоков, используемую как кеш первого уровня. Если ключ не найден в этой таблице, синхронизированный доступ выполняется для кэша второго уровня, который является -access-хэш-файлом, общим для всех потоков. Таким образом, вычисление значения кэша выполняется только один раз, и оно распределяется между всеми потоками, но каждый поток имеет локальную копию сопоставления от ключей к значениям, поэтому существует некоторая стоимость памяти (но меньше, чем наличие независимые кэши для каждой нити), но чтение является эффективным.

Answer 3

Как насчет кеша, описанного в разделе 5.6 из Concurrency In Practice, на Brian Goetz? Очерчен here.

Он использует только классы из пакета java.util.concurrent.

Связанная статья создает кеш и описывает слабые стороны каждой версии, пока окончательная версия не станет эффективным кешем, в котором только один параллельный поток будет вычислять отсутствующий элемент.

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

import java.util.concurrent.*; 

public class Memoizer<A, V> implements Computable<A, V> { 
    private final ConcurrentMap<A, Future<V>> cache 
     = new ConcurrentHashMap<A, Future<V>>(); 
    private final Computable<A, V> c; 
    public Memoizer(Computable<A, V> c) { this.c = c; } 
    public V compute(final A arg) throws InterruptedException { 
     while (true) { 
      Future<V> f = cache.get(arg); 
      if (f == null) { 
       Callable<V> eval = new Callable<V>() { 
        public V call() throws InterruptedException { 
         return c.compute(arg); 
        } 
       }; 
       FutureTask<V> ft = new FutureTask<V>(eval); 
       f = cache.putIfAbsent(arg, ft); 
       if (f == null) { 
        f = ft; 
        ft.run(); 
       } 
      } 
      try { 
       return f.get(); 
      } catch (CancellationException e) { 
       cache.remove(arg, f); 
      } catch (ExecutionException e) { 
      // Kabutz: this is my addition to the code... 
      try { 
      throw e.getCause(); 
      } catch (RuntimeException ex) { 
       throw ex; 
      } catch (Error ex) { 
       throw ex; 
      } catch (Throwable t) { 
       throw new IllegalStateException("Not unchecked", t); 
      } 
     } 
    } 
    } 
} 

Answer 4

Как насчет чего-то подобного SingletonCache класс из одного из моих проектов?

public abstract class SingletonCache<K, V> { 

    private final ConcurrentMap<K, V> cache = new ConcurrentHashMap<K, V>(); 

    public V get(K key) { 
     V value = cache.get(key); 
     if (value == null) { 
      cache.putIfAbsent(key, newInstance(key)); 
      value = cache.get(key); 
     } 
     return value; 
    } 

    protected abstract V newInstance(K key); 
} 

Чтобы его использовать, вы расширить и реализовать newInstance метод, который создает новое значение в случае промаха кэша. Затем вызовите метод get с ключом, чтобы получить экземпляр, соответствующий этому ключу. Here - пример того, как он используется.

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