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

Background Refresh / Refresh Ahead Policy #34

Open
cruftex opened this issue Jan 25, 2016 · 13 comments
Open

Background Refresh / Refresh Ahead Policy #34

cruftex opened this issue Jan 25, 2016 · 13 comments
Labels
Milestone

Comments

@cruftex
Copy link
Member

cruftex commented Jan 25, 2016

Current semantic

When enabling background refresh with CacheBuilder.refreshAhead(true):

The old value will be returned by the cache, although it is expired, and will be replaced by the new value, once the loader is finished. In the case there are not enough threads available to start the loading, the entry will expire immediately and the next get() request will trigger the load.

Once refreshed, the entry is in a trail period. If it is not accessed until the next expiry, no refresh will be done and the entry expires regularly.

Analysis

We have indication from our applications, that this is not working well in all scenarios. Example:

  • expiry time is 5 minutes
  • entry is accessed every 30 minutes on average
  • Load has 3s latency

This means the second load is mostly useless and the cache has always a miss, when the entry is accessed by the application.

How long the refreshing is done should be separated from the normal expiry duration. Especially at nighttime the access frequency gets lower. Administrators should be able to decide between:

  • minimize user latency, which means more refreshing
  • minimize the memory footprint and loader calls, which means more latency for the user
Todo
  • in-depth analysis of current cache scenarios
  • what parameters make sense?
  • what is the best behavior for backgroundRefresh(true), for the ease of use principle we want to have a setting which is a good fit for most of the time

Any more thoughts?

@cruftex cruftex added this to the V1 milestone Jan 25, 2016
@cruftex cruftex modified the milestones: v1.2, v1 May 18, 2016
@cruftex cruftex modified the milestones: v1.2, v1.4 Jul 3, 2018
@cruftex cruftex modified the milestones: v1.4, v2 Aug 21, 2019
@chrisbeach
Copy link

In my use case, I need the background refresh to happen repeatedly. Stopping after a single refresh really isn't useful.

@cruftex
Copy link
Member Author

cruftex commented Mar 17, 2020

The background refresh, as its implemented now, only stops after a single refresh if the data is not requested within the expiry period after the refresh.

Can you explain your use case in more detail? How big is the active data set, that needs to be refreshed constantly? How does it change over time? What is the expiry time?

@chrisbeach
Copy link

Can you explain your use case in more detail? How big is the active data set, that needs to be refreshed constantly? How does it change over time? What is the expiry time?

My use cache is an authentication token cache, with a business requirement that the tokens expire after a few minutes (such that an employee whose system access is deactivated will no longer be able to authenticate with our system). We’ll probably only cache a few hundred tokens, maximum, and it’s very rare that the data will change.

Loading our authentication tokens takes a second, so we’d like to pro-actively refresh the tokens upon cache expiry.

With this refresh in place, when a user accesses our system (perhaps once a day), they will not face a one second delay as their token will be present in the cache.

@cybuch
Copy link

cybuch commented Jul 13, 2021

Hey, I need the background refresh to happen repeatedly just as in Chris case.

In my case I cache offers for clients and for me it's big performance gain to have more 'fresh' offers in cache than to fetch offers from external source on cache miss. Each offer is cached for about 5 minutes and we keep about 30k of them. In combination with bulk loaders there's less stress on external resource than without cache or with cache that expires unused entries. Sometimes offers have to be removed from the cache, because we got fixed size caches, but LRU is good enough. Even removing the oldest entry would make sense here and would be easy to implement.

@cruftex
Copy link
Member Author

cruftex commented Aug 11, 2021

Here is an idea about a refresh policy:

    class RefreshPolicy<K, V> {
      /**
       * Called when the entry would expire and removed from the cached because
       * the previously refreshed entry was not accessed.
       *
       * @return true if entry should be refreshed again
       */
      boolean checkForAnotherRefresh(CacheEntry<K, V>, RefreshContext ctx);
    }

    class RefreshContext {
      long getLastModificationTime();
      long getLastAccessTime();
      int getRefreshCountSinceLastAccess();
    }

@cruftex
Copy link
Member Author

cruftex commented Sep 7, 2021

Should be merged with #172. If we change to another mechanism to track the access, we could also recognize a second access after the initial load. This enables the possibility to do no refresh if the value was never accessed a second time.

@cruftex
Copy link
Member Author

cruftex commented Sep 7, 2021

Another idea:

class RefreshPolicy<K, V> {

  int requiredAccessTimesUntilNextExpiry(CacheEntry<K, V>, RefreshContext ctx);
  
}

class RefreshContext {
  boolean initialLoad();
  long getExpiryTime();
  long getModificationTime();
  long getLastKnownAccessTime();
  int getRefreshCountSinceLastAccess();
}

The method is executed when a value is first loaded or refreshed after the loader and expiry policy.
The number returned determines how many cache hits to the value are needed for a refresh to happen when the entry would otherwise expire. E.g. a zero means a refresh happens all the time, or a one means at least one request is required for another refresh to happen.

It is counter intuitive but intentional that the policy is not evaluating an access count but returning the required number of hits. This way we only need to keep count until the requirement is met, thus, items that are requested very often have no additional overhead in the critical cache hit path.

Examples

Current behavior:

  int requiredAccessTimesUntilNextExpiry(CacheEntry<K, V>, RefreshContext ctx) {
     return ctx.initialLoad ? 0 : 1;
  }

Require at least one access until next expiry / refresh.

  int requiredAccessTimesUntilNextExpiry(CacheEntry<K, V>, RefreshContext ctx) {
     return 1;
  }

Keep refreshing until not accessed for 12 hours:

  int requiredAccessTimesUntilNextExpiry(CacheEntry<K, V>, RefreshContext ctx) {
     return (ctx.getModificationTime() - ctx.getLastKnownAccessTime()) < TimeUnit.HOURS.toMillis(12) ? 0 : 1;
  }

Require that the value is accessed at least 5 times per minute:

  int requiredAccessTimesUntilNextExpiry(CacheEntry<K, V>, RefreshContext ctx) {
     return (int) (ctx.getExpiryTime() - ctx.getModificationTime()) / 60000.0 * 5;
  }

@cruftex
Copy link
Member Author

cruftex commented Nov 1, 2021

@denghongcai ping. Maybe you like to check and comment on the last idea.

@denghongcai
Copy link

denghongcai commented Nov 24, 2021

back to year 2018, i use a ugly method to deal with my scenario

private Cache < HelloGetParams, HelloCacheEntry > cache = new Cache2kBuilder < HelloGetParams, HelloCacheEntry > () {}
    .name("Hello-cache")
    .entryCapacity(2048)
    .enableJmx(true)
    .expireAfterWrite(4, TimeUnit.MINUTES)
    .keepDataAfterExpired(true)
    .loader(new AdvancedCacheLoader < HelloGetParams, HelloCacheEntry > () {
        @Override
        public HelloCacheEntry load(HelloGetParams HelloGetParams, long currentTime,
            CacheEntry < HelloGetParams, HelloCacheEntry > currentEntry)
        throws Exception {
            if (currentEntry != null && currentEntry.getValue() != null) {
                // return stale data and background refresh
                if (currentTime <
                    currentEntry.getValue().getExpireTimeSinceEpoch() + MAX_STALE_TIME) {
                    refreshTaskManager.runInBackground(HelloGetParams, () - > {
                        try {
                            HelloCacheEntry cacheEntry = buildHelloCacheEntry(HelloGetParams);
                            cacheEntry.setExpireTimeSinceEpoch(
                                currentTime + cacheEntry.getCacheDuration().toMillis());
                            cache.put(HelloGetParams, cacheEntry);
                        } catch (Exception e) {
                            HelloErrorLogger.error(this.getClass().getSimpleName(), e);
                        }
                    });
                    return currentEntry.getValue();
                }
            }
            HelloCacheEntry cacheEntry = buildHelloCacheEntry(HelloGetParams);
            cacheEntry.setExpireTimeSinceEpoch(currentTime + cacheEntry.getCacheDuration().toMillis());
            return cacheEntry;
        }
    })
    .expiryPolicy((HelloGetParams, cacheEntry, loadTime, oldEntry) - > {
        if (cacheEntry == null) {
            return ExpiryTimeValues.NO_CACHE;
        }

        return loadTime + cacheEntry.getCacheDuration().toMillis();
    })
    .build();

my idea is set two timepoint:

  1. refreshTime
  2. expireTime

refreshTime < expireTime
if access after refreshTime and before expireTime, do background refresh. if after expireTime, do a load. instead of check a entry access times during cache period.

@cruftex
Copy link
Member Author

cruftex commented Nov 24, 2021

@denghongcai thanks for sharing!

In cache2k the expiry time is the time when an entry needs to be refreshed. Its identical. In old versions of cache2k I there was a RefreshPolicy and not a ExpiryPolicy and refreshing was the default not expiry. I changed it later, so it is less confusing for people coming from other cache products. However, our typical approach is to set an expiry time according to the business rules, and then just enable refreshAhead additionally if that helps with response times. The design idea is, that the refresh ahead configuration always comes on top of the normal expiry configuration and is optional.

In your logic you like to refresh the entry before its expiry, or, in other words, before it must be reloaded.
That leads us to two different notions of "refresh ahead":

  • refresh ahead of expiry
  • refresh ahead of potential next access, when expired

My line of thinking was more the second idea. Now I realize that there might be different interpretations.

The first concept is what Guava and Caffeine implement. That leads into other problems. Now a policy is missing if you want to have variable refresh times, see: ben-manes/caffeine#504
In general there are pros and cons of both ideas of thinking.

In cache2k, if refresh ahead is enabled, would return expired entries while the load is ongoing (if sharp expiry is enabled, then a parallel request would block). An explicit control how long a stale/expired entry can be served is missing.

I will somehow try to incorporate all these thoughts into the further enhancements.

@denghongcai: If you have time, can you share a few more details? I'd like to make sure we don't have an XY-Problem by just focusing on technical properties.

What is the allowed stale time or how much ahead of expiry would you typically do the refresh?
How long does a refresh take? What are the actual business requirements you try to implement (e.g.
data may not be older than....)?

cruftex added a commit that referenced this issue Mar 24, 2022
cruftex added a commit that referenced this issue Apr 11, 2022
… to a different access detection scheme, which keeps entry visible.
@javalover123
Copy link

Great job, thanks very much!
Auto refresh need RefreshAheadPolicy#requiredHits return 0, but default return 1(means no auto refresh), can change to 0?

javalover123 added a commit to javalover123/cache2k that referenced this issue Jun 17, 2022
@cruftex
Copy link
Member Author

cruftex commented Jun 17, 2022

@javalover123:
The feature is still work in progress, I have still around 30 code sections I need to investigate, correct and test, so the that the policy is working correctly. I am on a recreational break and back on it in July. When it is worth trying I will make a alpha release.

Auto refresh need RefreshAheadPolicy#requiredHits return 0, but default return 1(means no auto refresh), can change to 0?

The default policy would require at least one access for a refresh to happen. If you set it to 0 the refresh will happen always, even if nobody needs the value any more. So, setting it to 0 in general is not advised and probably not what most people want. However, this is the simple default policy. You can set you own policy via the Cache2kBuilder.refreshAheadPolicy.

It will also be possible to construct quite smart policies. E.g. refresh after 5 minutes and keep refreshing for a maximum of 2h if nothing was accessed.

@denghongcai
Copy link

denghongcai commented Jun 20, 2022

Sorry for my delay.

What is the allowed stale time or how much ahead of expiry would you typically do the refresh?

typically, less than a minute

How long does a refresh take?

it depends, typically less than ten seconds. i think it's not a major problem here.

What are the actual business requirements you try to implement (e.g.
data may not be older than....)?

data must be always fresh if it is warm. we had a DataGateway to server http request, it read a expensive config from somewhere then use it to get/parse/edit from backend service. you can image it like a GraphQL Gateway instead of it's a heavy operation on get GraphQL-ish DSL.

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

No branches or pull requests

5 participants