Invalidate before Refresh completes still stores value

[boschb]

Maybe this has come up before, but this seems a bit odd. Here is my test.

@RunWith(JUnit4.class)
public final class AsyncLoadingCacheTest {
  private final AtomicLong counter = new AtomicLong(0);
  private final FakeTicker ticker = new FakeTicker();

  private ListenableFutureTask<Long> loadingTask;

  private final AsyncCacheLoader<String, Long> loader =
      (key, exec) ->
          // Fools the cache into thinking there is a future that's not immediately ready.
          // (The Cache has optimizations for this that we want to avoid)
          toCompletableFuture(loadingTask = ListenableFutureTask.create(counter::getAndIncrement));

  private final String key = AsyncLoadingCacheTest.class.getSimpleName();

  /** This ensures that any outstanding async loading is completed as well */
  private long loadGet(AsyncLoadingCache<String, Long> cache, String key)
      throws InterruptedException, ExecutionException {
    CompletableFuture<Long> future = cache.get(key);
    if (!loadingTask.isDone()) {
      loadingTask.run();
    }
    return future.get();
  }

  @Test
  public void invalidateDuringRefreshRemovalCheck() throws Exception {
    List<Long> removed = new ArrayList<>();
    AsyncLoadingCache<String, Long> cache =
        Caffeine.newBuilder()
            .ticker(ticker)
            .executor(TestingExecutors.sameThreadScheduledExecutor())
            .<String, Long>removalListener((key, value, reason) -> removed.add(value))
            .refreshAfterWrite(10, TimeUnit.NANOSECONDS)
            .buildAsync(loader);

    // Load so there is an initial value.
    assertThat(loadGet(cache, key)).isEqualTo(0);

    ticker.advance(11); // Refresh should fire on next access
    assertThat(cache.synchronous().getIfPresent(key)).isEqualTo(0L); // Old value

    cache.synchronous().invalidate(key); // Invalidate key entirely
    assertThat(cache.synchronous().getIfPresent(key)).isNull(); // No value in cache (good)
    loadingTask.run(); // Completes refresh

    // FIXME: java.lang.AssertionError: Not true that <1> is null
    assertThat(cache.synchronous().getIfPresent(key)).isNull(); // Value in cache (bad)

    // FIXME: Maybe?  This is what I wanted to actually test :)
    assertThat(removed).containsExactly(0L, 1L); // 1L was sent to removalListener anyways
  }
}

It would appear that a refresh that started before an invalidate takes precedence over the invalidate? What I really wanted to test was the removal listener, but I ran into this first.

I'm using Caffeine 2.5.3

Thanks again for your good work.

[ben-manes]

I do recall refreshing being mind bending, so off-hand I can't speak to it without more thought. I'd first look into the prior issues (where some discussion took place) and Guava's behavior.

When the refresh completes, the current code is...

compute(key, (k, currentValue) -> {
  if (currentValue == null) {
    return value;
  } else if ((currentValue == oldValue) && (node.getWriteTime() == refreshWriteTime)) {
    return value;
  }
  discard[0] = true;
  return currentValue;
}, /* recordMiss */ false, /* recordLoad */ false);

if (discard[0] && hasRemovalListener()) {
  notifyRemoval(key, value, RemovalCause.REPLACED);
}

Like you said, when currentValue == null it is inserted. When discarded, currently it is assumed to be due to a replacement. I presume you would want that the value to be discarded and notified as a EXPLICIT?

---

My initial guess would be due to how Caffeine#refreshAfterWrite is documented, specifially

The semantics of refreshes are specified in {@link LoadingCache#refresh}, and are performed by calling {@link CacheLoader#reload}.

In LoadingCache we state,

Loads a new value for the {@code key}, asynchronously. While the new value is loading the
previous value (if any) will continue to be returned by {@code get(key)} unless it is evicted.
If the new value is loaded successfully it will replace the previous value in the cache; if an
exception is thrown while refreshing the previous value will remain, and the exception will
be logged (using {@link java.util.logging.Logger}) and swallowed.

Caches loaded by a {@link CacheLoader} will call {@link CacheLoader#reload} if the cache
currently contains a value for the {@code key}, and {@link CacheLoader#load} otherwise. Loading is asynchronous by delegating to the default executor.

This is word-for-word (or nearly) the same as in Guava. Since a refresh of an absent entry will load the value and refreshAfterWrite is stated as having the same semantics, I believe the contract requires the current behavior.

@yrfselrahc is the expert in this regard, since he wrote Guava's. I think the arguments would be,

• Lower precedence to ensure the refreshed value is not stale, assuming the invalidate was after a system-of-record write.
• Higher precedence to not waste work, since the cost was paid and may have been due to a eviction.

In retrospect I would lean towards stronger consistency guarantees.

[boschb]

Yah ideally for my case it would remain not loaded and invalidated. Further I would love to see a removalListener get fired for this event too as otherwise there is no where (except a finalizer) to catch this value if it has a lifecycle that needs to be managed.

Either way it would make sense to have a work around I think. Something does feel like it's missing here.

[ben-manes]

It would be helpful if someone from the Guava team chipped in. (@kevinb9n @lowasser @yrfselrahc) since it would change drop-in compatibility if the specification was updated.

[ghost]

At first glance I would agree that the more correct behavior would be for refresh operations to be cancelled by concurrent writes or removals. That seems to be the only way to maintain linearizability.

[boschb]

Yes agreed, cancel might seem most appropriate in this case, and would certainly work for my case.

The more I thought about it the more I realize there is a big unanswered question:

Given the flow:
1.) Refresh Started
2.) Invalidate
3.) Refresh Completed
Is the refreshed value newer or older than the invalidate call? I don't think you can broadly say one or the other and that might be the crux of the confusion. There probably exists cases where either makes complete sense.

Regardless any action I can think of would be a major change to existing functionality as it is today so that is also an issue.

I think I've been able to code around this issue by maintaining a separate Set of keys that should be filled and then in the async loader operation check against this Set once the value materializes and return null instead of the discovered value if the key no longer exists. It's a bit hacky in my opinion but I think it's sound from a concurrent point of view.

[ben-manes]

Internally there is a writeTime, as shown in the code above. That resolves the ABA problem for refreshAfterWrite, as you mentioned.

Unfortunately, that is not the case for LoadingCache#refresh(key) as the timestamp may not be on the entry. It is only there if added by expireAfterWrite or refreshAfterWrite. Guava has a slightly easier time on this front due to forking the hash table, where the entry is special case replaced with a loading variant, so no timestamps are necessary. That means they could avoid an ABA concern. I think it could be okay if LoadingCache#refresh is allowed to have weaker semantics here.

I don't have a strong opinion of whether this is a major or minor version change, according to semver. If we discard with the EXPLICIT removal cause then it seems fairly minor, since it clarifies the JavaDoc specification. But I am hoping to work on 3.0 as a Java 9 release, so it could be punted to that if there is opposition.

[boschb]

If we can discard the loading/refreshed value with EXPLICIT that solves everything for me, but it is really your call as to whether this is acting in accordance with what the API should be. You are the expert for this one and I can adjust as necessary based on the outcome so long as things are deterministic.

[ben-manes]

I am working through this for v3 to flush where we can resolve these possibly backwards incompatible tickets. To resolve some other issues, a secondary mapping used for capturing the in-flight refreshes. This as the benefit of (1) not disabling expiration during a refresh, (2) matching Guava of doing nothing if an in-flight refresh was already in progress, (3) detecting the ABA problem of absent -> refresh start -> put -> invalidate -> refresh end where the refresh should be dropped as the mapping was modified.

I think this would solve your problems, but I'm hazy about this conversation. Also, I don't remember exactly our thoughts on EXPLICIT and if that still matters. Do you remember much here?

[ben-manes]

I ported your test into the v3 branch and it now passes. I haven't looked at what removal cause to use yet and I am unsure about that, so it is still REPLACED for the time being.

[boschb]

I don't remember my exact use case, as I've been on a new project for the last 3 years, but I think it's fair to say if the test passes it would be a good fix.

The case:
absent -> refresh start -> put -> invalidate -> refresh end
is the crux of the issue.

It is a design choice and a case could be made for either as we discovered... Maybe PUT and/or INVALIDATE should cause the refresh() future to be CANCELLED (now that we have a future for it), or at least the value not applied but still returned from refresh() which I think is what is now working.

[ben-manes]

The value wouldn't be applied to the cache now, but would you expect any user attached downstream chained actions on the returned refresh future to also observe it as cancelled?

[boschb]

Observing cancelled could be useful but then the question is now, should calling PUT cancel the actual refresh operation itself? This would could IO implications as well if done correctly. Might be good, might be troublesome. It's almost like you need a 3rd option, so maybe the caller needs to decide somehow. Maybe it's a flag we set on the cache when it's created even to give expected behavior. Dealers choice :)

[ben-manes]

So another quirk with cancelling is that for an AsyncLoadingCache the refresh might actually be an in-flight initial load. This made sense for that cache type since it stores futures, so it seemed wrong to have a it side-loaded when the entry is absent or in-flight. So in those cases we trigger a normal get and return that future from refresh(). We currently don't cancel an in-flight future if it was replaced or removed from the cache. Instead that can be done by users, e.g. using the asMap view to obtain the prior value.

Refresh is this odd special case where this and the #143 makes sense, but those choices might not in the general Map case. That makes me hesitate to diverge from the Map cases for uniformity, even though I agree that these alternative behaviors might make more sense or be less surprising. But being different is surprising itself, so I lean towards uniformity even though I'm not super confident that it is the right choice.

[ben-manes]

I strengthened this new behavior in the v3 branch. It will now more aggressively discard the in-flight refresh for any write to that entry, be it explicit or by eviction. This should provide a better guard against ABA problems.

If the entry was removed and the refresh discarded, then its removal cause is now EXPLICIT as there was no prior mapping.

When the future is discarded it is not canceled. There are a few reasons for this,

1. Most importantly, a dependent stage might write back into the cache. As the future is discarded under the cache's entry lock for proper atomicity, this could result in a recursive map operation if the stage runs on the caller's thread. This could be worked around by capturing the discarded in-flight future and canceling outside of the lock. The point is mostly that care must be taken if cancellation is desired.
2. CompletableFuture does not communicate cancelation to the running task, e.g. via an interrupt. It only serves to tell dependents and observes that the future failed. To actually stop the task, the user would need to set their own flag and query it similar to interruption. This is rarely done, so there is likely no performance benefit.
3. It is not clear what user expectations would be and how they might chain against the future.
4. Sometimes the discarded future was solely for refresh for an AsyncCache.
   a. When the entry is absent, then refresh(key) can simply call get(key) and populate the entry.
   b. When the entry is present but the future is in-flight, then refresh returns that one. This avoids redundant work.

4b) May be overly optimistic and perhaps the refresh should occur regardless. If the future is in-flight, data updated, and the explicit refresh(key) intends to reload it. That usually would be an invalidate(key), but doing so would incur a latency penalty if the stale value is considered usable enough to allow. In that case a new reload would be desired, but currently it would not occur and the in-flight future might materialize the stale data. What would be your expectation and how should this scenario be handled?

[ben-manes]

Released in 3.0