Problem Solving Practice - Redis cache.put Hangs

The Issue
After deployed the change: Multi Tiered Caching - Using in-process EhCache in front of Distributed Redis to test environment (with some other change and someone did some change in the server like restart), we found out that cache.put hangs when save data to redis.

Troubleshooting Process
First we tried to reproduce the issue in my local setup, it always works. But we can easily reproduce it in test environment.

This mde me think this maybe something related with the test environment.

Then I used kill -8 processId to generate several thread dumps when reproduce the issue in test machine. I found out some suspect:
"ajp-nio-8009-exec-10" #91 daemon prio=5 os_prio=0 tid=0x00007f49c400a800 nid=0x75db waiting on condition [0x00007f495333e000]
   java.lang.Thread.State: TIMED_WAITING (sleeping)
at java.lang.Thread.sleep(Native Method)
at  RedisCache$RedisCachePutCallback(RedisCache$AbstractRedisCacheCallback).waitForLock(RedisConnection) line: 600
RedisCache$RedisCachePutCallback(RedisCache$AbstractRedisCacheCallback).doInRedis(RedisConnection) line: 564
at org.springframework.data.redis.core.RedisTemplate.execute(RedisTemplate.java:207)
at org.springframework.data.redis.core.RedisTemplate.execute(RedisTemplate.java:169)
at org.springframework.data.redis.core.RedisTemplate.execute(RedisTemplate.java:157)
at org.springframework.data.redis.cache.RedisCache.put(RedisCache.java:226)
at org.springframework.data.redis.cache.RedisCache.put(RedisCache.java:194)
at com.lifelong.example.MultiTieredCache.lambda$put$40(MultiTieredCache.java:130)
at com.lifelong.example.MultiTieredCache$$Lambda$18/1283186866.accept(Unknown Source)
at java.util.ArrayList.forEach(ArrayList.java:1249)
at com.lifelong.example.MultiTieredCache.put(MultiTieredCache.java:128)
at org.springframework.cache.interceptor.AbstractCacheInvoker.doPut(AbstractCacheInvoker.java:85)
at org.springframework.cache.interceptor.CacheAspectSupport$CachePutRequest.apply(CacheAspectSupport.java:784)
at org.springframework.cache.interceptor.CacheAspectSupport.execute(CacheAspectSupport.java:417)
at org.springframework.cache.interceptor.CacheAspectSupport.execute(CacheAspectSupport.java:327)
at org.springframework.cache.interceptor.CacheInterceptor.invoke(CacheInterceptor.java:61)

Check the code at RedisCache$AbstractRedisCacheCallback to understand how it works:
for operations like put/putIfAbsent/evict/clear, @cacheable with sync =true(RedisWriteThroughCallback), it check whether there is a key like cacheName~lock in redis, if exist, it will wait until it's gone.

This lock is created and deleted for @Cacheable with sync =true in RedisWriteThroughCallback which calls lock and unlock methods.

This made me check the settings in redis: after created the tunnel to redis, ran command: key cacheName~lock, I found out that it's indeed there.

Now everything make sense:
- we did set sync=true and run performance test, then restarted the server and removed it. The cacheName~lock was left there may be due to server restart. Due to the cacheName~lock, now all resid update api would not work.

After removed cacheName~lock in redis, everything works fine.

Take away
- When use some feature (@Cacheable(sync=true) in this case), know how it's implemented.

Multi Tiered Caching - Using in-process Cache in front of Distributed Cache

Why Multi Tiered Caching?
  To improve application's performance, we usually cache data in distributed cache like redis/memcached or in-process cache like EhCache. 

  Each have its own strengths and weaknesses:
  In-Process Cache is faster but it's hard to maintain consistency and can't store a lot of data; This can be easily solved when using a distributed cache, but it's slower due to network latency and serialization and deserialization.

  In some cases, we may want to use both: mainly use a distributed cache to cache data, but also cache data that is small and doesn't change often (or at all) such as configuration in in-process cache.

The Implementation

  Spring uses CacheManager to determine which cache implementation to use.

  We define our own MultiTieredCacheManager and MultiTieredCache like below.

public class MultiTieredCacheManager extends AbstractCacheManager {
    private final List<CacheManager> cacheManagers;
    /**
     * @param cacheManagers - the order matters, when fetch data, it will check the first one if not
     *        there, will check the second one, then back-fill the first one
     */
    public MultiTieredCacheManager(final List<CacheManager> cacheManagers) {
        this.cacheManagers = cacheManagers;
    }
    @Override
    protected Collection<? extends Cache> loadCaches() {
        return new ArrayList<>();
    }
    @Override
    protected Cache getMissingCache(final String name) {
        return new MultiTieredCache(name, cacheManagers);
    }
}

public class MultiTieredCache implements Cache {
    private static final Logger logger = LoggerFactory.getLogger(MultiTieredCache.class);

    private final List<Cache> caches = new ArrayList<>();
    private final String name;

    public MultiTieredCache(final String name, @Nonnull final List<CacheManager> cacheManagers) {
        this.name = name;
        for (final CacheManager cacheManager : cacheManagers) {
            caches.add(cacheManager.getCache(name));
        }
    }

    @Override
    public ValueWrapper get(final Object key) {
        ValueWrapper result = null;
        final List<Cache> cachesWithoutKey = new ArrayList<>();
        for (final Cache cache : caches) {
            result = cache.get(key);
            if (result != null) {
                break;
            } else {
                cachesWithoutKey.add(cache);
            }
        }
        if (result != null) {
            for (final Cache cache : cachesWithoutKey) {
                cache.put(key, result.get());
            }
        }
        return result;
    }

    @Override
    public <T> T get(final Object key, final Class<T> type) {
        T result = null;
        final List<Cache> noThisKeyCaches = new ArrayList<>();
        for (final Cache cache : caches) {
            result = cache.get(key, type);
            if (result != null) {
                break;
            } else {
                noThisKeyCaches.add(cache);
            }
        }
        if (result != null) {
            for (final Cache cache : noThisKeyCaches) {
                cache.put(key, result);
            }
        }

        return result;
    }
    // called when set sync = true in @Cacheable
    public <T> T get(final Object key, final Callable<T> valueLoader) {
        T result = null;
        for (final Cache cache : caches) {
            result = cache.get(key, valueLoader);
            if (result != null) {
                break;
            }
        }
        return result;
    }
    @Override
    public void put(final Object key, final Object value) {
        caches.forEach(cache -> cache.put(key, value));
    }
    @Override
    public void evict(final Object key) {
        caches.forEach(cache -> cache.evict(key));
    }
    @Override
    public void clear() {
        caches.forEach(cache -> cache.clear());
    }
    @Override
    public String getName() {
        return name;
    }
    @Override
    public Object getNativeCache() {
        return this;
    }
}

@Configuration
@EnableCaching
public class CacheConfig extends CachingConfigurerSupport {
  @Bean
  @Primary
  public CacheManager cacheManager(EhCacheCacheManager ehCacheCacheManager, RedisCacheManager redisCacheManager) {
      if (!cacheEnabled) {
          return new NoOpCacheManager();
      }
      // Be careful when make change - the order matters
      ArrayList<CacheManager> cacheManagers = new ArrayList<>();
      if (ehCacheEnabled) {
          cacheManagers.add(ehCacheCacheManager);
      }
      if (redisCacheEnabled) {
          cacheManagers.add(redisCacheManager);
      }
      return new MultiTieredCacheManager(cacheManagers);
  }

  @Bean(name = EH_CACHE_CACHE_MANAGER)
  public EhCacheCacheManager ehCacheCacheManager() {
      final EhCacheManagerFactoryBean ehCacheManagerFactoryBean = new EhCacheManagerFactoryBean();
      ehCacheManagerFactoryBean.setConfigLocation(new ClassPathResource("ehcache.xml"));
      ehCacheManagerFactoryBean.setShared(true);
      ehCacheManagerFactoryBean.afterPropertiesSet();

      final EhCacheManagerWrapper ehCacheManagerWrapper = new EhCacheManagerWrapper();
      ehCacheManagerWrapper.setCacheManager(ehCacheManagerFactoryBean.getObject());
      return ehCacheManagerWrapper;
  }

  @Bean(name = "redisCacheManager")
  public RedisCacheManager redisCacheManager(final RedisTemplate<String, Object> redisTemplate) {
      final RedisCacheManager redisCacheManager =
              new RedisCacheManager(redisTemplate, Collections.<String>emptyList(), true);
      redisCacheManager.setDefaultExpiration(DEFAULT_CACHE_EXPIRE_TIME_IN_SECOND);
      redisCacheManager.setExpires(expires);
      redisCacheManager.setLoadRemoteCachesOnStartup(true);
      return redisCacheManager;
  }
}

Misc
  Others things we can do when use multi (tiered) cache in CacheManager:

- We can use cache name prefix to determine which cache to use.
- We can add logic to only cache some kinds of data in specific cache.

TODO
- able to use only Distributed Cache or only in-process Cache

Caching Data in Spring Using Redis

The Scenario
We would like to cache Cassandra data to Redis for better read performance.

Cache Configuration
To make data in Redis more readable and easy for troubleshooting and debugging, we use GenericJackson2JsonRedisSerializer to serialize value as Json data in Redis, use StringRedisSerializer to serialize key.

To make GenericJackson2JsonRedisSerializer work, we also configure objectMapper to store type info: objectMapper.enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL, JsonTypeInfo.As.PROPERTY); 
- as we need store class info. 
- The data would be like: {\"@class\":\"com....Configuration\",\"name\":\"configA\",\"value\":\"805\"}

We also configure objectMapper: configure(SerializationFeature.FAIL_ON_EMPTY_BEANS, false).
- As when there Cassandra, we want to cache this info to redis. So later we can return from redis cache, and no need to read from database again.
- Spring-cache stores org.springframework.cache.support.NullValue in this case, its json data is {}. We need configure ObjectMapper to return empty object with no properties. - By default it throws exception:
org.springframework.data.redis.serializer.SerializationException: Could not write JSON: No serializer found for class org.springframework.cache.support.NullValue and no properties discovered to create BeanSerializer (to avoid exception, disable SerializationFeature.FAIL_ON_EMPTY_BEANS); nested exception is com.fasterxml.jackson.databind.JsonMappingException: No serializer found for class org.springframework.cache.support.NullValue and no properties discovered to create BeanSerializer (to avoid exception, disable SerializationFeature.FAIL_ON_EMPTY_BEANS) 

We configured cacheManager to store null value.
- We use the configuration-driven approach and have a lot of configurations; We define default configuration values in property files. In the code, it first read from db and if null then read from property files. This makes us want to cache null value.

We also use SpEL to set different TTL for different cache.
redis.expires={configData:XSeconds, userSession: YSeconds}

@Configuration
@EnableCaching
public class RedisCacheConfig extends CachingConfigurerSupport {
    @Value("${redis.hostname}")
    String redisHostname;
    @Value("${redis.port}")
    int redisPort;
    @Value("#{${redis.expires}}")
    private Map<String, Long> expires;
    @Bean
    public JedisConnectionFactory redisConnectionFactory() {
        final JedisConnectionFactory redisConnectionFactory = new JedisConnectionFactory();
        redisConnectionFactory.setHostName(redisHostname);
        redisConnectionFactory.setPort(redisPort);
        redisConnectionFactory.setUsePool(true);
        return redisConnectionFactory;
    }
    @Bean("redisTemplate")
    public RedisTemplate<String, Object> genricJacksonRedisTemplate(final JedisConnectionFactory cf) {
        final RedisTemplate<String, Object> redisTemplate = new RedisTemplate<>();
        redisTemplate.setKeySerializer(new StringRedisSerializer());
        redisTemplate.setHashKeySerializer(new StringRedisSerializer());
        redisTemplate.setValueSerializer(new GenericJackson2JsonRedisSerializer(createRedisObjectmapper()));
        redisTemplate.setHashValueSerializer(new GenericJackson2JsonRedisSerializer(objectMapper));
        redisTemplate.setConnectionFactory(cf);
        return redisTemplate;
    }
    @Bean
    public CacheManager cacheManager(final RedisTemplate<String, Object> redisTemplate) {
        final RedisCacheManager cacheManager =
                new RedisCacheManager(redisTemplate, Collections.<String>emptyList(), true);
        cacheManager.setDefaultExpiration(86400);
        cacheManager.setExpires(expires);
        cacheManager.setLoadRemoteCachesOnStartup(true);
        return cacheManager;
    }

    public static ObjectMapper createRedisObjectmapper() {
        final SimpleDateFormat sdf = new SimpleDateFormat(DEFAULT_DATE_FORMAT, Locale.ROOT);
        sdf.setTimeZone(TimeZone.getTimeZone("UTC"));
        final SimpleModule dateModule = (new SimpleModule()).addDeserializer(Date.class, new JsonDateDeserializer());
        return new ObjectMapper()
                .enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL,JsonTypeInfo.As.PROPERTY)//\\
                .registerModule(dateModule).setDateFormat(sdf)
                .configure(DeserializationFeature.ACCEPT_SINGLE_VALUE_AS_ARRAY, true)
                .configure(DeserializationFeature.UNWRAP_SINGLE_VALUE_ARRAYS, true)
                .configure(DeserializationFeature.FAIL_ON_IGNORED_PROPERTIES, false)
                .configure(DeserializationFeature.FAIL_ON_INVALID_SUBTYPE, false)
                .configure(DeserializationFeature.FAIL_ON_NULL_FOR_PRIMITIVES, false)
                .configure(DeserializationFeature.FAIL_ON_NUMBERS_FOR_ENUMS, false)
                .configure(DeserializationFeature.FAIL_ON_READING_DUP_TREE_KEY, false)
                .configure(DeserializationFeature.FAIL_ON_UNKNOWN_PROPERTIES, false)
                .configure(DeserializationFeature.FAIL_ON_UNRESOLVED_OBJECT_IDS, false)
                .configure(SerializationFeature.FAIL_ON_EMPTY_BEANS, false) //\\
                .setSerializationInclusion(JsonInclude.Include.NON_NULL)
                .setVisibility(PropertyAccessor.ALL, JsonAutoDetect.Visibility.ANY);
    }
}

Cache CassandraRepository

@Repository
@CacheConfig(cacheNames = Util.CACHE_CONFIG)
public interface ConfigurationDao extends CassandraRepository<Configuration> {
    @Query("Select * from configuration where name=?0")
    @Cacheable
    Configuration findByName(String name);

    @Query("Delete from configuration where name=?0")
    @CacheEvict
    void delete(String name);

    @Override
    @CacheEvict(key = "#p0.name")
    void delete(Configuration config);

    /*
     * Check https://docs.spring.io/spring/docs/current/spring-framework-reference/html/cache.html
     * about what #p0 means
     */
    @Override
    @SuppressWarnings("unchecked")
    @CachePut(key = "#p0.name")
    Configuration save(Configuration config);

    /*
     * This API doesn't work very well with cache - as spring cache doesn't support put or evict
     * multiple keys. Call save(Configuration config) in a loop instead.
     */
    @Override
    @CacheEvict(allEntries = true)
    @Deprecated
    <S extends Configuration> Iterable<S> save(Iterable<S> configs);

    /*
     * This API doesn't work very well with cache - as spring cache doesn't support put or evict
     * multiple keys. Call delete(Configuration config) in a loop instead.
     */
    @Override
    @CacheEvict(allEntries = true)
    @Deprecated
    void delete(Iterable<? extends Configuration> configs);
}

Admin API to Manage Cache 
We inject CacheManager to add or evict data from Redis.
But to scan all keys in a cache(like: cofig), I need to use stringRedisTemplate.opsForZSet() to get keys of the cache:
- as the value in the cache (config), its value is a list of string keys. So here I need use StringRedisTemplate to read it.

After get the keys, I use redisTemplate.opsForValue().multiGet to get their values.

- I will update this post if I find some better ways to do this. 

public class CacheResource {
    private static final String REDIS_CACHE_SUFFIX_KEYS = "~keys";
    @Autowired
    @Qualifier("redisTemplate")
    RedisTemplate<String, Object> redisTemplate;

    @Autowired
    @Qualifier("stringRedisTemplate")
    StringRedisTemplate stringRedisTemplate;

    @Autowired
    private CacheManager cacheManager;

    /**
     * If sessionId is not null, return its associated user info.<br>
     * It also returns other cached data: they are small data.
     *
     * @return
     */
    @GetMapping(produces = MediaType.APPLICATION_JSON_VALUE, path = "/cache")
    public Map<String, Object> get(@RequestParam("sessionIds") final String sessionIds,
            @RequestParam(name = "getConfig", defaultValue = "false") final boolean getConfig) {
        final Map<String, Object> resultMap = new HashMap<>();
        if (getConfig) {
            final Set<String> configKeys =
                    stringRedisTemplate.opsForZSet().range(Util.CACHE_CONFIG_DAO + REDIS_CACHE_SUFFIX_KEYS, 0, -1);
            final List<Object> objects = redisTemplate.opsForValue().multiGet(configKeys);
            resultMap.put(Util.CACHE_CONFIG + REDIS_CACHE_SUFFIX_KEYS, objects);
        }
        if (StringUtils.isNotBlank(sessionIds)) {
            final Map<String, Object> sessionIdToUsers = new HashMap<>();
            final Long totalUserCount = stringRedisTemplate.opsForZSet().size(Util.CACHE_USER + REDIS_CACHE_SUFFIX_KEYS);
            sessionIdToUsers.put("totalUserCount", totalUserCount);
            final ArrayList<String> sessionIdList = Lists.newArrayList(Util.COMMA_SPLITTER.split(sessionIds));
            final List<Object> sessionIDValues = redisTemplate.opsForValue().multiGet(sessionIdList);
            for (int i = 0; i < sessionIdList.size(); i++) {
                sessionIdToUsers.put(sessionIdList.get(i), sessionIDValues.get(i));
            }
            resultMap.put(Util.CACHE_USER + REDIS_CACHE_SUFFIX_KEYS, sessionIdToUsers);
        }
        return resultMap;
    }

    @DeleteMapping("/cache")
    public void clear(@RequestParam("removeSessionIds") final String removeSessionIds,
            @RequestParam(name = "clearSessions", defaultValue = "false") final boolean clearSessions,
            @RequestParam(name = "clearConfig", defaultValue = "false") final boolean clearConfig) {
        if (clearConfig) {
            final Cache configCache = getConfigCache();
            configCache.clear();
        }
        final Cache userCache = getUserCache();
        if (clearSessions) {
            userCache.clear();
        } else if (StringUtils.isNotBlank(removeSessionIds)) {
            final ArrayList<String> sessionIdList = Lists.newArrayList(Util.COMMA_SPLITTER.split(removeSessionIds));
            for (final String sessionId : sessionIdList) {
                userCache.evict(sessionId);
            }
        }
    }

    /**
     * Only handle client() data - as other caches such as configuration we can use server side api
     * to update them
     */
    @PutMapping("/cache")
    public void addOrupdate(...) {
        if (newUserSessions == null) {
            return;
        }
        final Cache userCache = getUserCache();
        // userCache.put to add key, value
    }

    private Cache getConfigCache() {
        return cacheManager.getCache(Util.CACHE_CONFIG_DAO);
    }

    private Cache getUserCache() {
        return cacheManager.getCache(Util.CACHE_USER);
    }
}

StringRedisTemplate

@Bean("stringRedisTemplate")
public StringRedisTemplate stringRedisTemplate(final JedisConnectionFactory cf, final ObjectMapper objectMapper) {
    final StringRedisTemplate redisTemplate = new StringRedisTemplate();
    redisTemplate.setConnectionFactory(cf);
    return redisTemplate;
}

Misc
- If you want to disable cache in some env, use NoOpCacheManager.
- When debug, check code:
CacheAspectSupport.execute
SpringCacheAnnotationParser.parseCacheAnnotations

Spring @Cacheable Not Working - How to Troubleshoot and Solve it

The Scenario
Spring cache abstraction annotation is easy to add cache abilty to the application: Just define CacheManager in confutation,  then use annotations: @Cacheable, @CachePut, @CacheEvict to use and maintain the cache.

But what to do if the cache annotation seems doesn't work?

How we know cache doesn't work?
Logging
We can change the log level to print database query in the log. For Cassandra, we can change log level of com.datastax.driver.core.RequestHandler to TRACE. 
Debug
We can set a breakpoint at CacheAspectSupport.execute.
If cache works, when we call a method annotated with cache annotation,  it will not directly call  the method, instead it will be intercepted and hit the breakpoint.
Test

Possible Root Causes
1. The class using cache annotation inited too early
This usually happens when we use @Cache annotated classes in configuration or AOP class.

Spring first creates configuration and AOP class which then cause beans of @Cache annotated classes created before cache config is correctly setup. This makes these beans created without handling @Cache.

Please check Bean X of type Y is not eligible for getting processed by all BeanPostProcessors for detailed explanation

How to troubleshoot
Add a breakpoint at the default constructor of the bean (add one if not exist), then from the stack trace we can figure out why and which bean (or configuration class) causes this bean to be created.

Using @Lazy or ObjectFactory or other approaches to break the eager dependency, restart and check again util the cached method works as expected.

Also check whether there is log like: Bean of type is not eligible for getting processed by all BeanPostProcessors (for example: not eligible for auto-proxying)

2. Calling cached method in same class
Solutions:
- Using self inject or applicationContext.getBean then use the bean to call cached method
- Using @Scope(proxyMode = ScopedProxyMode.TARGET_CLASS)

Simple Cache Implementation in Java

LRU Cache: Using LinkedHashMap
Java LinkedHashMap and LinkedHashSet maintains the order of insertion or access. By default it's the insertion order, we can change it using the constructor: LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder).
Setting accessOrder to true would make LinkedHashMap sort elements according to the order of access.

LinkedHashMap maintains an extra doubled linked list to maintain the element order: Entry<K,V> header; The header is like a sentinel element, its after points to the oldest element.

LinkedHashMap.removeEldestEntry(Map.Entry<K,V> eldest) allow us to specify whether to remove the oldest one.

class LRUCacheMap<K, V> extends LinkedHashMap<K, V> {
  private static final long serialVersionUID = 1L;
  private int capacity;
  public LRUCacheMap(int capacity) {
    this.capacity = capacity;
  }
  @Override
  protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
    return size() > capacity;
  }
}

LRU Cache: Using LinkedHashSet
1. Overwrite add method in LinkedHashSet
When implement a hash based LRU cache, we can extend LinkedHashSet, then overwrite its add method: when current size is equal or larger than MAX_SIZE, use the iterator to remove the first element, than add the new item.

class LRUCacheSet<E> extends LinkedHashSet<E> {
  private static final long serialVersionUID = 1L;
  private int capacity;
  public LRUCacheSet(int capacity) {
    this.capacity = capacity;
  }
  @Override
  public boolean add(E e) {
    if (size() >= capacity) {
      // here, we can do anything.
      // 1. LRU cache, delete the eldest one(the first one) then add the new
      // item.
      Iterator<E> it = this.iterator();
      it.next();
      it.remove();

      // 2. We can do nothing, just return false: this will discard the new
      // item.
      // return false;
    }
    return super.add(e);
  }
}

2. Using LinkedHashMap to implement LRUCacheSet via Collections.newSetFromMap
HashSet actually uses a HashMap as the backend. Collections.newSetFromMap (introduced in JDK6) allow us to construct a set backed by the specified map. The resulting set displays the same ordering, concurrency, and performance characteristics as the backing map.

So we can use the previous LRUCacheMap as the backing map.

lruCache = Collections.newSetFromMap(new LRUCacheMap<Integer, Boolean>(
    MAX_SIZE));
for (int i = 0; i < 10; i++) {
  lruCache.add(i);
}
Assert.assertArrayEquals(new Integer[] { 5, 6, 7, 8, 9 },
      lruCache.toArray());

More about Collections.newSetFromMap
There are many HashMap implementations that doesn't have a corresponding Set implementation: such as ConcurrentHashMap, WeakHashMap, IdentityHashMap. 
Now we can easily create hash instances that work same as ConcurrentHashMap,ConcurrentSkipListMap, WeakHashMap:
Set<Object> concurrenthashset = Collections.newSetFromMap(new ConcurrentHashMap<Object, Boolean>());
Set<Object> weakHashSet = Collections.newSetFromMap(new WeakHashMap<Object, Boolean>());

Using Guava CacheBuilder
Google Guava is a very useful library, and it's most likely that it's already included in our project. Guava provides a CacheBuilder which allows us to build a custom cache with different features combination.

LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder()
.maximumSize(1000).expireAfterWrite(10, TimeUnit.MINUTES)
.removalListener(MY_LISTENER)
.build(
 new CacheLoader<Key, Graph>() {
   public Graph load(Key key) throws AnyException {
     return createExpensiveGraph(key);
   }
});

Resources
LinkedHashMap's hidden (?) features
Handy But Hidden: Collections.newSetFromMap()
Guava CacheBuilder