Add LRU cache service

[hinerm]

in #141 we stated the need for caching but not the method by which we would cache.

In the long term we should have a generalized LRU cache that we can use to enforce memory constraints but allow caching of items that end up being used frequently.

API considerations

• I would prefer that consumers do not have to manually release references when complete, but it would be nice if the cache could ensure certain items would be held in memory for a period of time. Maybe this is impossible though.. ?

Potential design:
give the cache an object and the way to re-generate the object when needed... cache stores both, returns an object that then accesses the object and knows how to re-create it if needed. This seems maybe too dangerous though..?

[ctrueden]

Instead of "held in memory for a period of time" it would be easier to code a feature like "held in memory until the thing is retrieved at least X times."

[IdealOutage]

I did a little research on this matter and in my opinion the easiest way to implement a simple LRU Cache would be to use a LinkedHashMap, even the JavaDoc states:

This kind of map is well-suited to building LRU caches.

The only thing we have to do is to overwrite the removeEldestEntry to eliminate the oldest entry when the size of the map is bigger than a previously specified maximum size.

    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return size() > maxSize;
    }

This cache wouldn't be concurrent, but this could be fixed using Collections.synchronizedMap.
90% of the other tips for implementing a cache in Java were "Use Google Guavas CacheBuilder"

But this still leaves the design decision open. Should the cache create the object if it isn't cached anymore, or should the programmer create the object himself if it isn't cached anymore? The first one would be more convenient, but in my opinion object creation isn't a task for a cache.

What do you think?

[dietzc]

I think this is not an "or". These are two different cache-types in my opinion. The first cache is a cache we would typically use in KNIME: "Hey, is the object still there? No? Ok, no worries we will take care about it". The second cache is what @hinerm does with the SCIFIOCellImg. So both are actually caches.

[hinerm]

90% of the other tips for implementing a cache in Java were "Use Google Guavas CacheBuilder"

For a cache data structure, CacheBuilder looks great; it has soft/weak refs and LRU eviction.

@ctrueden may have thoughts here but my assumption is that we won't want to include a guava dependency at the SJC level and would encapsulate the dependency in another (caching or guava-related) component. But SJC would host the CacheService interface.

I do want to clarify that this issue is about building a cache _Service_ and not a cache data structure. The service acts as a centralized bridge to a caching data structure(s). My thought was just to generalize the SCIFIOCellCache model to a pluggable caching system, where cache entries (the plugins) can choose how their object is stored (e.g. in a backup disk cache with SCIFIOCellImg) and know how to re-create their object if it has been evicted (whether by LRU or lost to GC).

[dietzc]

All right, if we can define a nice Service interface, then we can have our own implementation, based on whatever, of a LRUCacheService. From my point of view there should be a pure Cache which doesn't know how to recreate the object and maybe another (SmartCacheService or however you want to call it), which uses the pure Cache and additionally know how to recreate objects. Like that, we cover both use-cases without having redundant implementations.

Does this make sense?

[hinerm]

Well, multiple implementations of a given Service will override each other. The service can't know how to create objects, but Handler plugins to the service can. We could make a default low-priority plugin backed by CacheBuilder that returns null if the requested object's not found.

To me I think it's an advantage to keep everything in a centralized cache instead of having one smart and one not. Otherwise you would have to check each cache separately, and it becomes ambiguous what to evict when hitting memory constraints - right?

Quite possible that I'm misunderstanding something fundamental that's obvious to you and this design is bad. If so, please let me know. Or if it sounds like the cache service I'm describing won't meet your needs, can you explain your use case?

[dietzc]

Well, multiple implementations of a given Service will override each other.

Of course they will. What I suggest are two different interfaces for two different concepts. The first one is a Cache which doesn't know how to re-create the input, the second one is a Cache which knows hows to recreate the input. And if one wants, she can implement the second one wrapping the first one. Does this make sense?

I just don't see one unified Cache solution, because already just the two of us have different requirements to such a Cache (the two options described above).

[IdealOutage]

But why do we need two interfaces? To have a simple example, the two Caches should both have a get and a put, the rest is just implementation details.

public LRUCache extends Cache {
  private Map<K, V> cache;

  @Override
  public V get(K k){
    if(map.contains(k)) return map.get(k);
    return null;
  }
}

public SmartCache extends Cache {

  private LRUCache lruCache;
  private CreationStrategy creationStrategy;  

  @Override
  public V get(K k){
    V v = lruCache.get(k);
    if(v != null) return v;

    // otherwise create v from scratch
    return creationStrategy.create(k);
  }
}

[hinerm]

And if one wants, she can implement the second one wrapping the first one. Does this make sense?

Makes sense but I think can be simplified and more extensible if we use plugins to decide how things are stored/created.

I made a branch with a _very_ bare-bones CacheService to try and illustrate what I planned for this ticket.

The idea is that if something knows how to do fancy things with a given object to cache, it can. Even if not, everything is in a central cache.

Then you have plugins for individual data types which can decide if and how to recreate cached items.

Also, the CachePlugin could actually just be a ValueLoader so that the guava cache framework takes care of re-creating the value if needed.

Let me know if any of that is unclear, and in what ways it wouldn't meet your cache requirements.

[ctrueden]

my assumption is that we won't want to include a guava dependency at the SJC level and would encapsulate the dependency in another (caching or guava-related) component.

I am increasingly ambivalent. Guava brings a whole lot of richness to the table, and avoids reinventing many wheels. For example, did you know Guava has its own event bus?

For the time being, isolating the dependency elsewhere is probably the best move, to avoid disruption. But there may come a time when the dependency for SJC as a whole makes sense.

[IdealOutage]

@hinerm

I see one big problem with this idea, the CachePlugin will be evicted if the Cache is full. For example if we put("test", new CachePlugin("test")); into our Cache and want to retrieve the value later it could happen that cache.getIfPresent(key); will give us null if our value was evicted and then we can't recreate the value. We need to know what kind of Object we store for a given key, either we use get(String key, Class<V> valueClass) then we would be able to create a CachePlugin from the given class or we could make the CacheService generic so that it can only store one kind of object (would that even be possible? Can we create a generic CacheService if we use context.getService(CacheService.class)?) or something completely different.

A completely different topic, I would advice against is using weak values, since that would defeat the purpose of the cache imho. WeakReferences will be garbage collected as soon as the GC has the chance to do so, even if there is still room in our cache and we have plenty of free memory the objects will be evicted. I would suggest using soft values, since SoftReferences will only be garbage collected if we run out of memory or using a predefined fixed limit.