Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Enabling refresh enables values to be returned beyond expiration #282

Closed
spand opened this issue Nov 20, 2018 · 6 comments
Closed

Enabling refresh enables values to be returned beyond expiration #282

spand opened this issue Nov 20, 2018 · 6 comments

Comments

@spand
Copy link

@spand spand commented Nov 20, 2018

We have recently discovered some differences between our expectations and actual behavior in Caffeine that all seem to revolve around in flight loads or reloads. The first here seems like a clear bug.

expireAfterWrite documentation states:
"Expired entries may be counted in Cache.estimatedSize(), but will never be visible to read or write operations."
refreshAfterWrite documentation has no mention of expiration.

The following test cases document a violation of this in that adding a refresh policy one can observe expired values from the map. I would expect stale values to only be visible in the time span between refresh and expire times. The tests are in Kotlin but intent should be clear enough. The first test fails in the latest version 2.6.2 and document the problem. The second passes and is the same test but without the refresh policy.

@Test
fun `Stale value expires during refresh`(){
    val ticker = FakeTicker()
    val key = ""
    val initialValue = CompletableFuture.completedFuture("1")
    val refreshValue = CompletableFuture<String>()
    val futures = mutableListOf<CompletableFuture<String>>(
            initialValue,
            refreshValue
    )

    val cache = Caffeine.newBuilder()
            .ticker(ticker)
            .refreshAfterWrite(1, TimeUnit.MILLISECONDS)
            .expireAfterWrite(3, TimeUnit.MILLISECONDS)
            .buildAsync<String, String> { _, _ ->
                futures.removeAt(0)
            }
            .synchronous()

    assertThat(cache.get(key), present(equalTo("1")))
    ticker.advanceTime(2, TimeUnit.MILLISECONDS)// Expire initialValue

    // Trigger reload, assert stale
    assertThat(cache.get(key), present(equalTo("1")))

    // Move time beyond expire time
    ticker.advanceTime(5, TimeUnit.MILLISECONDS)
    assertThat(cache.get(key), present(!equalTo("1")))
}

@Test
fun `Value expires`(){
    val ticker = FakeTicker()
    val key = ""
    val initialValue = CompletableFuture.completedFuture("1")
    val refreshValue = CompletableFuture.completedFuture("2")
    val futures = mutableListOf<CompletableFuture<String>>(
            initialValue,
            refreshValue
    )

    val cache = Caffeine.newBuilder()
            .ticker(ticker)
            .expireAfterWrite(3, TimeUnit.MILLISECONDS)
            .buildAsync<String, String> { _, _ ->
                futures.removeAt(0)
            }
            .synchronous()

    assertThat(cache.get(key), present(equalTo("1")))
    ticker.advanceTime(2, TimeUnit.MILLISECONDS)

    assertThat(cache.get(key), present(equalTo("1")))

    // Move time beyond expire time
    ticker.advanceTime(5, TimeUnit.MILLISECONDS)
    assertThat(cache.get(key), present(!equalTo("1")))
}

class FakeTicker : Ticker {
    private var time = 0L

    fun advanceTime(increment: Long, unit: TimeUnit){
        time = Math.addExact(time, unit.toNanos(increment))
    }

    override fun read(): Long {
        return time
    }
}
@ben-manes
Copy link
Owner

@ben-manes ben-manes commented Nov 20, 2018

Unfortunately I don't know if there is a good solution here.

Guava forks the hash table, so it can use a custom Map.Entry that holds a future value when recomputing. This lets the current value and future value be encoded on the entry (but optimized out when unnecessary). This lets to detect if a refresh is in progress to avoid redundant calls.

Because we don't customize the hash map, we maintain encode to a value wrapper Node. Currently we use a CAS to change the expiration time for refresh to avoid redundant calls and update accordingly when the refresh completes (See BoundedLocalCache#refreshIfNeeded). I think we'd have to retain an extra field on the Node if refresh was supported, which adds to its memory overhead. Given the recent requests for variable refresh (#272, #261) we might have to do that. But it does feel wasteful and we'd want to find ways to minimize per-entry overhead where possible.

Currently its a trade-off that most load actions should be shorter than the expiration time, so that the optimization generally works. It's not perfect and requires finding a good balance between needs.

@spand
Copy link
Author

@spand spand commented Nov 21, 2018

That is fair. Skimming the code I thought it was an explicit choice looking at:

boolean hasExpired(Node<K, V> node, long now) {
    if (isComputingAsync(node)) {
      return false;
    }
...

or maybe handled just in time in get().

Could we instead (or until fixed, it seems you mention forking the hash table quite a lot in the issues) have this documented explicitly in the javadoc for the refreshAfterWrite?

@ben-manes
Copy link
Owner

@ben-manes ben-manes commented Nov 21, 2018

Yes, I'll update the JavaDoc in refreshAfterWrite for the time being. The isComputingAsync is for AsyncLoadingCache where the value is a future. There is hasExpired for validating with, in case the expired entries haven't been purged yet.

I think it's worth brainstorming possible fixes. I see a few options,

  1. Use a dedicated bit flag for whether a refresh is in progress, rather than extending the expiration time to disable refresh attempts. Ideally we would encode this to avoid extra state, such as by using the sign bit of the timestamp. Unfortunately nanoTime() allows negative times and overflow, so we'd need a new state field per entry. Due to alignment it might be free, but otherwise could add 32-bits per entry.
  2. Add a future reference per entry. That adds 32-64 bit ref to each and is usually null.
  3. Replace the Node with a decorated version holding the delegate and future. Then an instanceOf check is a fast flag. However, this requires updating the map, a blocking call for a read when it may be in an expensive compute. That breaks the assumption that reads can overlap with writes.
  4. Externalize the state, e.g. in to a Map<Node, CompletableFuture>. Then when past the refresh time, each get would have to do a membership check. The write into this state would be cheap because there wouldn't be any long running computations. The additional lookup per read isn't ideal, but probably a good tradeoff. We have be extra careful about reads racing with removal, that could result in a dangling entry being left in this map.

Guava's fork of the hash table lets it use an optimal mixture of 3 & 4, since the computations are futures within the Entry and don't block hash table operations. This also lets it detect redundant refresh calls, e.g. LoadingCache#refresh will no-op. We don't have a good mechanism for that currently, and forking was otherwise very problematic for Guava. Retaining the future has a slight benefit for supporting #143. So the plan will probably be to implement (4) to solve this flaw.

@Maaartinus
Copy link

@Maaartinus Maaartinus commented Nov 22, 2018

nanoTime() has nanosecond resolution, but a much worse precision. And even if it had a precision of a nanosecond, you can guarantee nothing even remotely close to it for the expiration. So I guess, you can steal the least significant bit (or two). The computational overhead for the needed bit fiddling is IMHO much lower than any alternative. The implementation overhead and risks should be pretty small, too, as it concerns a single field only, which is used in pretty few places.

@ben-manes
Copy link
Owner

@ben-manes ben-manes commented Jan 2, 2021

I am restarting efforts towards v3, now that some blockers were resolved. I really liked your idea @Maaartinus, but due to other behaviors using option (4) of an in-flight refresh map was necessary. This way the cache can return the future on a LoadingCache.refresh, drop redundant reloads like Guava does, and handle ABA problems when the mapping changes in ways we cannot currently detect. This map is lazily initialized and there are optimization guards to avoid incurring a memory & time penalty.

ben-manes added a commit that referenced this issue Jan 2, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in an undectectable way. The refresh future can
now be obtained from LoadingCache to chain operations against.

TODO: unit tests for these changes

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Jan 2, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in an undectectable way. The refresh future can
now be obtained from LoadingCache to chain operations against.

TODO: unit tests for these changes

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Jan 2, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in an undectectable way. The refresh future can
now be obtained from LoadingCache to chain operations against.

TODO: unit tests for these changes

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Jan 2, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in an undectectable way. The refresh future can
now be obtained from LoadingCache to chain operations against.

TODO: unit tests for these changes

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Jan 3, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Jan 3, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Jan 3, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Jan 4, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Jan 4, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Jan 4, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Jan 17, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 8, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 8, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 8, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 8, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 14, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 14, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 14, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 15, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 15, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 15, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 15, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 15, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
ben-manes added a commit that referenced this issue Feb 16, 2021
A mapping of in-flight refreshes is now maintained and lazily
initialized if not used. This allows the cache to ignore redundant
requests for reloads, like Guava does. It also removes disablement
of expiration during refresh and resolves an ABA problem if the
entry is modified in a previously undectectable way. The refresh
future can now be obtained from LoadingCache to chain operations
against.

fixes #143
fixes #193
fixes #236
fixes #282
fixes #322
fixed #373
fixes #467
@ben-manes ben-manes closed this in 551ade7 Feb 21, 2021
@ben-manes
Copy link
Owner

@ben-manes ben-manes commented Feb 21, 2021

Released in 3.0

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants