Caffeine: Feature Request : Add a listener for whenever cache is updated by load/loadAll

[apragya]

Hi,

I have a use-case where I need to maintain several caches that basically store the same value, but have different keys. So, I want to update both caches whenever i actually get the data for one of them, and so want to be notified whenever a load was called. It's basically similar to the removalListener. Is there any particular reason why it's not support for updates and only removal.

Thanks.

[ben-manes]

Removals are special since they might be done automatically, e.g. size eviction. In those cases your code isn't in control, so you need a callback mechanism to handle any clean up work.

For inserts and updates, your code is in control so a listener isn't required. It might be a nice-to-have, but there is nothing stopping you from adding the call in the loader. That may even be preferable as more obvious code than thinking through how different abstractions interact (a common frustration with obtuse frameworks).

There is also the question of whether a listener should be called asynchronously (ordered or unordered) or synchronously. We have RemovalListener for asynchronous unordered, and CacheWriter for synchronous and therefore ordered. CacheWriter, though, doesn't get notified on a load/computation because that could cause surprising double work (e.g. loader: compute and insert a row into the db; writer: notified and updates the row with the same value).

Since we're then running into a lot of complexity of how things interact, with the need for a lot of variations, it begins to become messy. When messy, that increases the conceptual weight for users to learn the APIs and have a higher chance of making mistakes. So it is an abstraction that isn't necessary, doesn't provide a lot of simplicity for users, and does not promoting a best practice. Then it seems better for us not to provide it and recommend users do it themselves.

At least that's been the conclusion so far. What do you think?

[apragya]

To explain my use case more, I want to cache same value V, by multiple keys K1, K2 and K3. I was thinking of maintaining a separate cache per key, and a key mapper to derive each key from V and updating each of the cache's whenever any of the Keys are updated. (And its fine if these updates are eventually consistent for the different keys).
Or, another approach might be to use same cache with a generic key interface and store all of them in the same ConcurrentHashMap, but I'm worried it might cause more contention without much benefit otherwise.
So, having a listener would have just made my code more organized/clean.
But, I agree it can be done inside the load/laodAll . And I can understand the other implications and why it might not be a great idea for this to be exposed as part of the API.
Do you have any thoughts on what's a good approach of achieving the above?

[ben-manes]

I actually wrote the key mapper when I was first starting on caching, when doing a bunch of performance work. That was bundled into an internal caching framework, but is what got me hooked. My case was like yours, where the keys were unique components of the value (e.g. User=>uuid, email). I viewed it as a primary key and secondary indexes that lookup a unique table row.

At the time I started exploring how to fix concurrency problems with the synchronized LRU cache (ehcache), which got all these things started. I put some of the internal caching utilities on a wiki page, and thankfully saved those when Google Code shut down. The indexable data structure has aged poorly, given its 10 years old, but might offer some assistance in rolling your own.

It is a little noisy since I had to first introduce the concept of lock striping and an implementation, which was the basis for Guava's Striped (as was the Bloomfilter wiki page, the cache was integrated, etc). In the framework I used annotations to extract the keys auto-magically and then lookup by the POJO. I don't recall how I had it wired up for a load() function, which was done by the SelfPopulatingMap decorator. The secondary keys were kept outside of the cache to avoid confusing its maximum size constraint, and removed on the listener callback.

Might help, or not. Most of the code could disappear with better libraries today. It worked fairly well, but I haven't needed anything like it again.

[ben-manes]

@osklyar just asked this question on StackOverflow.

I realized you could avoid the secondary mapping due if the primary/secondary aspect of the keys can be determined by the Weigher and Expiry. In those cases, you can disable the policy (zero weight, infinite duration). However, you cannot perform a cache update within a computation/load as that is prohibited by the underlying ConcurrentHashMap. This would require asynchronously (CompletableFuture) populating the cache with the additional mappings.

[osklyar]

@ben-manes Very interesting that you mention the async aspect: the cache I am using is in fact an async wrapper around the Guava LoadingCache guaranteeing non-blocking and single loading on missing values completing all the completable futures on the loading and other gets upon completing the loading stage.

[ben-manes]

Is that homegrown? How does it compare to our AsyncLoadingCache?

[osklyar]

@ben-manes Yes, homegrown and conceptually similar, but with a very limited scope. Effectively it is a fairly minimal implementation of BiFunction<K, Supplier<V>, CompletableFuture<V>>, where Supplier<V> is the loader, backed by Guava LoadingCache. The only serious logic is making sure that loading occurs just once. For values already in the map futures are completed on the same thread. But thanks for pointing out, I will consider moving to caffeine instead :)

[apragya]

@ben-manes Thanks some helpful suggestions.

I actually like the idea of keeping the mappings separate as it makes things easier and explicit and no assumptions involved w.r.t size of the cache. (Our current implementation is a home-grown cache which keeps all mappings and I can see how it has lead to confusion, now that you say it)

However, i'm worried how do you achieve correctness, with a loading cache here. Since I don't really have a handle for putting the , I'm not sure if we could synchronize the indexMap and the cacheStore. I'm actually thinking a manual cache might make more sense for this purpose than a loading cache.

[ben-manes]

@osklyar For us, we store the CompletableFuture directly and remove it if it fails or computes to null. The quirk is then making the weigher and expiry async aware to disable them while in-flight, and then callback when complete for the evaluation. Since the future is handed out directly, if completed methods like thenRun will execute on the calling thread unless thenRunAsync is used instead. There's not too much logic on just once loading, merely a guard to ignore ForkJoinPool's attempts to rerun the completion handler if delayed.

[osklyar]

@ben-manes My initial implementation is storing a value holder with a CountDownLatch initialised to 1 and reset upon successful load, the exception if any and the value upon the load. All other get calls will wait for the latch within CompleteableFuture.supplyAsync if the value not there and will complete either with the value or exception. If the value is already in then they will complete immediately on the same thread.

In any case, I will work on this in the next days and will share the final solution here, either via a gist or a new repo, just for the sake of sharing findings on an interesting challenge.

[ben-manes]

@apragya I don't remember, except it was loading. Presumably there were two options,

1. Allow the loads to be non atomic if computing by secondary key, under the assumption that a cache was best effort.
2. Load the primary key based on the secondary key, thereby simplifying to a single loader function.

That caching framework had our local caches backed by memcached with a JMS topic for invalidation, so typically the cost of a local cache miss was quite low. It was also built on a model-driven architecture, so all the storage and other details were code generated from descriptor files (which had the annotation metadata). So all of the queries, table information, etc was known at compile time and the cache had figure things out from the type's details. It was a hairball framework that I had to work within, and probably led me to be strongly in favor of libraries over framework designs.

[ben-manes]

Thanks @osklyar! If you can, also consider giving Caffeine's version a shot.

[osklyar]

@ben-manes You've got here an amazing library, so I have already migrated some of out code off Guava. The following has been my best effort so far, still WIP, but roughly the general idea: https://github.com/teris-io/caffeinated
Would be grateful for any critic.

[ben-manes]

Thanks! I'm glad it's helpful.

It would be interesting to see a more real-world usage of keyMapper in your tests. If the simple case of (id, email, phone)=>User, then would the keyMapper be a SQL lookup to the ID? So on a full miss, you would expect two database calls (key=>PK, PK=>Value)? However, it looks like the value loader is by secondary key, e.g. email, so should keyMapper instead take the value to derive from instead of the secondary key? I'm curious if we can shrink it to one db lookup on a full miss, though I'm sure the cost is negligible. I'm also unsure if these API details are not be a big deal or might be confusing in your realworld code.

[osklyar]

Thanks for insightful comments. This is just the first (not quite finished) iteration so I will have a second and a third look at this and will come up with more realistic examples (tests).

[osklyar]

@ben-manes So here is one real-world example essentially implementing my actual use case in test, but in a simplified manner with some dummy DAOs. The DAOs times are unfortunately not negligible in our case, thus the explicit latencies in the DAO dummy impls: https://github.com/teris-io/caffeinated/blob/master/src/test/java/io/teris/caffeinated/SessionStoreExample.java

Exceptional pathways are still to be tested, but I also simplified the API a bit and introduced JavaDocs for clarity.

[ben-manes]

That does seem quite nice and usable. A few notes that may help.

1. For your tests, you might want to use Guava's FakeTicker to control time. Then you won't need the Thread.sleep to cause a delay or wait for expiration. If you inject the same ticker everywhere, including the cache builder, then you can control time in your tests.
2. CaffeinatedMultikeyCache#onRemoval will remove the various mappings. Since the listener is called asynchronously, you might have a load for the same key replacing it. For example due to a refresh (via refreshAfterWrite) to reload when stale but before its expired (to hide the latency). The safe way is to use conditional removal by an instance check, if possible (asMap().remove(key, oldValue). Since it is a cache this won't be a big deal, but its a race to be aware of.
3. A common API wisdom is to avoid multiple arguments of the same type if used for different purposes (e.g. setVisible(true, false) is unclear). Your two lambda expressions are like that, though much more obvious. A builder might not be much better, so mostly just FYI of the potential quirk.

On our side of not having an AsyncCache and having to fake it by throwing an exception in the loader - what are your thoughts? I didn't want to introduce the abstraction unnecessarily and did want to promote loading through the cache. Every once in a while a case like yours comes up, but its not seemed ugly enough to introduce the API. I did make sure enough was defined to do so, if users pushed for it, so I am glad it didn't block you.

[osklyar]

Thanks a lot for the insights. On (1), will check and integrate, even though the delays are not hurting yet for the prototype. On (2), well spotted, will investigate your solution, but need to integrate a fix in any case. On (3) yeah, not ideal, so I replaced the value loader by a BiFunction with main and derived keys; in my case I do not need it, but generally it won't harm there.

In fact, a more irritating API decision for me was the impossibility to construct a loading cache without a loader function in the builder. More often than not I tend to provide the loader to the get method using the closure state rather than passing a generic one in the builder. I probably would prefer the means to construct the cache without the loader and get an exception if no loader is provided to the get (or exceptionally completed future, see below). The example under discussion here is actually the one where there is no single loader that can be used for all keys.

Another slightly irritating API decision is to permit nullable CompletableFuture returns. I would rather prefer a future completed with null or completed exceptionally depending on the situation. Effectively I would prefer to deal with nulls in the callbacks rather than on the future interface directly in cases like getIfPresent().thenApply

[ben-manes]

In fact, a more irritating API decision for me was the impossibility to construct a loading cache without a loader function in the builder.

Thanks. I have seen multiple integrations have to do this workaround with a dummy loader. It seems to occur when building ones own cache abstraction where a single loader doesn't fit their scenario (e.g. Akka's http cache). I'm do think users reach too quickly for manual get/put calls, but I'm open to conceding on this and providing AsyncCache.

I probably would prefer the means to construct the cache without the loader and get an exception if no loader is provided to the get.

Oh, I wouldn't go that far. Perhaps sometimes a rarely used unimplemented method is okay, like Iterator's remove, where there are a variety of possible implementations. This is too central and since provided during construction, the consuming code might not know when its safe (e.g. JCache configures externally so runtime code must make assumptions). I do prefer Bloch's idea of the loading interface extending the manual API to make it very explicit.

would prefer to deal with nulls in the callbacks rather than on the future interface directly in cases like getIfPresent().thenApply

This is a quirky one. The preferred get won't return null because it will always try to compute. For most users, using getIfPresent outside of a test is a code smell. The null future means the mapping is absent in the cache, while a future holding null or an exception is a failed computation (which will be automatically removed). If we returned CompletableFuture<V>(null), you would not be able to discern between a missing value in the data store or simply not in the cache. That may be okay most of the time, but it conflates that only on that method and might frustrate someone who needs to know.

[ben-manes]

@apragya would the solution that @osklyar kindly put together help for your use-case?

[apragya]

@ben-manes, Let me know if i have misunderstood, however, what I understand from the API java-docs is that this implementation of multi-index cache relies on the assumption that there is a possible way to get a common Derived key from each of the secondarykeys/primarykey. Using this derived key it looks up the cache and loads a value based on Key, Derived Key
For my scenario, I would have to do a DB lookup (i.e call valueLaoder) to basically first get V from the secondary key and then derive the DK, so I already have the value for the actual cache now and it's not useful for me to make two Database calls (that would defeat the whole purpose of this).
I need a keymapper that works on V.

[ben-manes]

I agree that deriving the full set of keys from the value, but loading it from any secondary key, is ideal.

@osklyar would it make more sense to have an api like the following?

public CompletableFuture<User> getByUsername(String username) {
  return sessionStore
    .get(username, $ -> {
      return userDao.getByUsername(username);
    }, user -> {
      return ImmutableSet.of(
          user.getUsername(),
          user.getEmail(),
          user.getId());
    });
}

Perhaps your session example is odd because you won't store the password, so you can't derive the key from the value. I think @apragya would need a more general case like the above. Do you think your library could handle his scenario too?

[apragya]

@ben-manes
I am already implementing something for my use-case as I was in urgent need to have a solution.
However, I am using a synchronized loading cache for the main store and a concurrent Hashmap for maintaining keyToIndex mapping. I have been considering replacing it with a cache like osklar's code, (however a synchronous one).
However, i was confused on the fact that using 2 synchronous loading caches can be dangerous and can potentially lead to deadlocks if I'm updating inside one's load() method the other cache. Is that correct?

[ben-manes]

Oh, I'm glad you implemented something.

If the two caches are not circular then a deadlock cannot occur as there is no shared, global state. However, ConcurrentHashMap does not support computations that write into itself. As in map.compute(key, (k, v) -> map.put(1, 1)) will fail, but map.compute(key, (k, v) -> other.put(1, 1)) is okay.

[apragya]

Yes, even I was originally thinking that it should not be an issue, however, consider the simplified scenario:
Cache 1 (K, KeyIndex) - cache 1 is for maintaining mappings and has a loader like this

KeyIndex load(key K) {
     V = db.get(K);
     KeyIndex index = keyMapper.apply(V);
    cache2.put(index.getPK, V)
    return index;
}

Cache 2 (PK, Value) : cache 2 is the main store and maintains from PrimaryKey to Value and has a loader like this

V load(key PK) {
    V = db.get(PK);
   KeyIndex index = keyMapper.apply(V);
    index.getAllKeys().stream.forEach(k -> cache1.put(k, index);
    return V; 
}

Now, if a request simultaneously comes for a primaryKey Pk1 and its corresponding secondaryKey Sk1 and both started loading from database. Now since they both have obtained a write lock for Pk1 and Sk1 respectively and neither of them will release until load completes. But load cannot complete unless we update the other cache (so pk1's load would be blocked on obtaining write lock for sk1 and vice-versa).
This seems to me like a dead-lock situation. Am i missing something?

[ben-manes]

Yes, that is what I meant by circular. You have to have a strict ordering of locks.

Once the value is in the cache, you can of course put it into the other map outside of the computation. However you would then run into a race of compute=>evict=>addIndex. That can be solved, so you're right that things things require a lot of care.

[apragya]

Isn't async then the only good way to do it then outside the computation, because we cannot listen to load events?

If I do it inside my custom cache's get function, which in turn calls caffiene's get (and might call load), I wouldn't know if it was because of a cache miss or hit and might lead to wasteful index updates.

If I do it by getIfPresent(k) and then calling cache.get(k, { k -> getFromDB()}) and then selectively updating the other cache, I'm not really using the "loading nature" of the cache.

[apragya]

Also, really appreciate all your feedaback and reactivity to the questions :)
Your activity on the forums is really commendable . Thanks.

[ben-manes]

Yes, I think we're in agreement.

Please do note that Caffeine is not prescriptive. It is a fancy ConcurrentHashMap and you are very welcome to use the asMap view or do other things yourself. You don't have to use the loading apis if they are not helpful. In that way our rule is to make it easy to do the right things, but not block you from doing the hard ones.

Technically what you need is a lifecycle, as per-entry locks are not compossible. It has to be asynchronous to the computation, whether that all is done by one thread or delegated. If you think of it as a transaction, they recover by either restarting or aborting the work. You could have a PK=>tryLock and abort if another thread owns it. In that scenario, you can still return the loaded value to the caller but not bother to set any of the mappings if you lost the race.

Another thing to remember is as a cache, its okay to embrace the fuzzy nature of things as long as you abide by the contract. A wasteful index update is probably very cheap. An extra load on a rare race is okay, since you're absorbing most of them. If you abide by the contract and have correctness, then its okay to cheat somewhere else to make things fit together.

[ben-manes]

Oh, thank you too. This is the enjoyable part of the day when I get to to talk to smart people and learn from them. :-)

[apragya]

Yes, technically what i need is something like a "trylock" and this is what i was exactly thinking.
I'll see how i can work around and make it work. Thanks again.

[apragya]

@ben-manes
I think there is one more edge case which causes incorrectness that I recently discovered in my solution, if we maintain a KeyMapping relation in the secondaryKey Concurrent map.

Say we had a primaryKey pk, secondarykey k and value v and it got updated to pk, k', v' in the database.
(Now if my cache has the stale value v, it would have an index mapping of k to pk but no mapping exists for k')
If there are two simultaneous requests fired for reading k, and k', and what if load for k' was able to update the primaryCache to v'.

Since there is no locking done on reading secondary key, it could lead to reading the mapping as pk, even before old index was removed. So now for k, we could possibly return v'.

I am not even sure if this could be solved by obtaining a read-write lock while reading secondary key, as what i need is a locking on primarykey pk which I don't even have till i read this mapping.

Probably, I'm missing something but i can only think that the way to get around this is by keeping values in the other map as well instead of mappings (which has some other limitations)

[ben-manes]

To clarify my understanding of your dilemma:

This is a race due to the staleness of the cache, correct? For a duration the cache can return back the wrong value due to an old mapping. When the cache is informed (via expiration, update notification, etc) then the mappings are synchronized. There isn't a long-term data leak where the mapping is stuck in a bad state. Since PK is immutable over the lifetime of the value, it can be used to coordinate the internal consensus as the mappings are adjusted.

If so, then usually this falls into the case of being a benign race. There was a clear ownership of the secondary keys to the primary according to the value. When that ownership changes there would be some propagation delays, but small enough to not impact business logic. If strong consistency is required, then one interacts with the system-of-record directly. Then one runs into the different transaction isolation levels, which often run afoul to strictness expectations.

I probably misunderstood, so can you explain the danger of your scenario?

[apragya]

The problem is not with staleness of data. The problem is that when querying using a secondary key, I actually get an updated value which doesn't even have that as the secondary key.
I'll use your example/code snippets to explain it -
Initial record : pk, k ("abc") , v
Updated Record: pk, k' ("xyz") , v'.

Say request 1 for put(xyz, v'), has reached a point where it updated the actual cache store but has not updated the indexes. Now if a simultaneous 'get' comes for old k ("abc"), it can read the indexes becuase AFAIK, it doesn't check any lock status before reading the indexes or store.

Then it means it will read for k ("abc") the mapping to pk and the primary store has already been updated to pk -> v' (which actually contains "xyz"). So a query for a secondary key ("abc") the returned record has no trace of "abc"

public V get(Object key) {
    Index<K> index = indexes.get(key);
    return (index == null) ? null : store.get(index.getPrimary());
}

public V put(K key, V value) {
    Index<K> index = checkIndex(key, value);
    return put(index, value);
}

private V put(Index<K> index, V value) {
    K primary = index.getPrimary();
    lock.lock(primary);
    try {
        V old = store.put(primary, value);
        if (old == null) {
            addIndex(index);
        } else {
            updateIndex(indexes.get(primary), index);
        }
        return old;
    } finally {
        lock.unlock(primary);
    }
}

[ben-manes]

I think we might be coming to it with different expectations. I'm viewing it as a useful performance optimization for classic business logic, where the associations don't change very often (such as user lookups). In those cases the implementor opts in because they know the trade-offs and its a benign race. But perhaps you are looking at it from the author of more generic infrastructure, like a database, where users won't consider the tradeoff and need stronger guarantees.

The easy solution to this is to validate on the lookup and retry. The index and value can be tagged with a version number and compared. If a write causes the reader to see the newer version, then a retry loop should resolve it. Alternatively you could validate by recomputing the index from the retrieved value, though the memory savings probably wouldn't justify the penalty.

[apragya]

Yeah, I think that's right.
I did think about that as well, and it probably should solve it. However, I was debating as to should i add this complexity or rather go by another approach of just keeping the values in the second map (as there isn't really any increased memory footprint). It wouldn't need any atomic constraints like this one.

[ben-manes]

You're right. That's probably simpler without much a drawback.

[ben-manes]

@osklyar Introducing AsyncCache in #246.

Closing as I think there's nothing left for me to do here.