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

Question

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

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

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

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

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

Answer 1

Использовать одновременную хэш-карту Java

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);

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

Answer 2

Как насчет этого 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 с ключом, чтобы получить экземпляр, соответствующий этому ключу. Здесь - пример того, как он используется.

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

Answer 3

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

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

Answer 4

Как насчет кэша, описанного в разделе 5.6 Практический параллелизм , Брайан Гетц ? Обрисовано в общих чертах здесь .

Используются только классы из пакета 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);
          }
        }
     }
  }
}