Cache management and usage of Guava Cache

Preface

The Guava project contains several core libraries that are widely relied on by Google's Java project, Guava Cache is one of the core libraries of Guava, Guava Cache is a full-memory local cache implementation that provides a thread-safe implementation. Overall, Guava cache is the best choice for local caching, which is easy to use and has good performance. Today we're going to talk about Guava Cache.

GuavaCache data structure

Guava Cache inherits the design idea of ConcurrentHashMap and uses fine-grained locks in the form of multiple segments to ensure thread safety and support high concurrency scenarios. Cache is similar to Map, it is a collection of stored key-value pairs, but it also needs to handle algorithmic logic such as expire and dynamic load, and requires some additional information to implement these operations. In this regard, according to the object-oriented idea, it is necessary to encapsulate the association between methods and data.

It should be noted that:

• The number of valid queues in each segment (not counting abandoned queues) may be more than one, and the queue is used to implement the LRU cache reclamation algorithm, and when the data exceeds the set maximum value, the LRU algorithm is used to remove it.
• 中的ReferenceEntry[i]用于 key-value,ReferenceEntry是对一个 对节点的 象, 的key 在 WeakReference 用内, value 在 WeakReference SoftReference 用内
• Each ReferenceEntry array item is a ReferenceEntry chain that automatically loads the entry node into the cache structure.
• Multiple segments do not disturb each other and can be executed concurrently
• Each segment only needs to expand its own segment, regardless of other segments
• On the premise of ensuring the cache hit rate, set the initialization capacity and concurrency level parameters according to the time and space dimensions as needed

time

Harvest strategy

There are three types of data reclamation strategies for Guava cache, which are divided into weak reference-based reclamation policies, capacity-based reclamation policies, and time-based reclamation policies

1. Citation-based recycling

By using weakly referenced keys, or weakly referenced values, or soft-referenced values, Guava Cache can set the cache to allow garbage collection:

CacheBuilder.weakKeys() uses weak reference storage keys. Cached items can be garbage collected when the key has no other (strong or soft) references. Because garbage collection only relies on identities (==), caches that use weak reference keys compare keys with == instead of equals.

CacheBuilder.weakValues() stores values with weak references. When there are no other (strong or soft) references to the value, the cached item can be garbage collected. Because garbage collection only relies on identities (==), caches that use weak reference values compare values with == instead of equals. CacheBuilder.softValues() stores values with a soft reference. Soft references are only collected in order of the least recent global use when they are needed in response to memory needs. Given the performance impact of using soft references, we generally recommend using a more predictive cache size limit (see below, based on capacity reclamation). Caches that use soft-reference values also compare values with == instead of equals.

2. Based on the capacity reclamation strategy

maximumSize(long) can set the maximum size of the cache. The cache will attempt to reclaim cache items that have not been used recently, or that are not used frequently. Warning: The cache may perform reclamation before the capacity reaches the limit, typically when the cache size is approaching the limit.

In addition, if different cached items have different "weights" and cached items have different memory usages, you need to use CacheBuilder.weigher(Weigher) to specify a weight calculation function and CacheBuilder.maxmumWeight(long) to set the total weight. As with maximumSize, it is important to note that the cache is also recycled when the total weight is approximated. In addition, the weight of cached items is calculated at the time of creation and does not change after that.

3. Based on the time recovery strategy

Guava Cache has three ways to clean or refresh cached data based on time:

expireAfterAccess: Cached items are recycled when they are not read or written within a specified period of time.

This cache is recycled in the same order as size-based recycling. When the data stored in the cache reaches the expiration time and is not read or written, the data will be reclaimed, and if the data is in the state of being read and written, the data will not be recycled, which may lead to dirty data reads.

expireAfterWrite: Cached items are recycled if they are not updated within a specified period of time.

Use expireAfterWrite to invalidate the cache for a specified amount of time after each update, and then reload the cache. In concurrent scenarios, Guava cache will strictly limit only one loading operation, which will well prevent a large number of requests from penetrating to the backend at the moment of cache invalidation, causing an avalanche effect.

However, by analyzing the source code, Guava Cache locks when there is only one loading operation, and in the concurrency scenario, other requests must be blocked and wait for this loading operation to complete. Moreover, after the loading is completed, the other requesting threads will obtain the lock one by one to determine whether it has been loaded, and each thread must take turns to go through a process of "obtaining the lock, obtaining the value, and releasing the lock", which will lead to an increase in the amount of requests abandoned by the system, and at the same time, there will be peaks and troughs in the performance of QPS (when the request hits the cache, the service QPS will rise instantaneously, and the QPS will decrease instantaneously when the cache timeliness is cached).

refreshAfterWrite: How long after the last update operation on the cached item will be refreshed.

The feature of refreshAfterWrite is that in the process of refreshing, only one reload operation is strictly restricted, and other queries return the old value first, which can effectively reduce the blocking caused by waiting and lock contention, so refreshAfterWrite will have better performance than expireAfterWrite. However, it also has a drawback, because it does not strictly guarantee that all queries will get new values after the specified time is reached. Guava Cache does not use additional threads for scheduled cleanup and loading, but relies on query requests. When querying, compare the time of the last update, if the set time is exceeded, one thread will be selected for loading or refreshing. Therefore, if refreshAfterWrite is used, in the case of low throughput, such as instantaneous concurrency after no query for a long time, the request does not wait for the cache to be loaded but directly returns the old value in the cache, which may be the data from a long time ago, which will cause problems in some time-sensitive scenarios.

It can be seen that the two methods of refreshAfterWrite and expireAfterWrite have their own advantages and disadvantages, and each has its own use scenarios. In the Spring Festival project of the gold coin mall, we used guava cache for some scenarios of instantaneous traffic peaks for the first time in the project, and found a compromise solution in refreshAfterWrite and expireAfterWrite, such as the product information of the mall, control the cache to refresh every 3s, if there is no access for more than 5s, then let the cache be invalidated, and the old value will not be obtained the next time you visit. Instead, you have to wait for the new value to load.

source

code analysis

By tracing the source code of the get method of LoadingCache (the following source code is guava 18.0 version), it is found that the following core methods will be called in the end, and the source code is posted below:

com.google.common.cache.LocalCache.Segment.get方法：

@Nullable

V get(Object key, int hash) {

try{

if (this.count != 0) {

now = this.map.ticker.read();

LocalCache.ReferenceEntry e =getLiveEntry(key, hash, now);

if (e == null) {

Object localObject1 = null;

return localObject1;

}

Object value =e.getValueReference().get();

if (value != null) {

recordRead(e, now);

Object localObject2 =scheduleRefresh(e, e.getKey(), hash, value, now, this.map.defaultLoader);

return localObject2;

}

trydrainDequeues.);

}

long now = null;

return now; } finally { postReadCleanup();

}

}

The get method of this buffer determines whether there is a survival value, first find out whether there is an entry in the LocalCache that has not been recycled, and there is no expired entry, if it is found, and refreshAfterWrite is configured in the CacheBuilder, and the current time interval has been operated with this event, then reload the value, otherwise, directly return the original value. If it expires, the value is null, and whether the data in the queue needs to be refreshed based on refreshAfterWrite.

Judging from the segment code, when getting, it is to judge the expiration first, and then judge the refresh, so we can set refreshAfterWrite to 3s and expireAfterWrite to 5s when actually using, when the access is frequent, the cached data will be pre-refreshed every 3 seconds, and when the ground throughput, when there is no access for more than 5s, the cached data will expire and invalidate. The next access will update the data in the cache.

下面看看com.google.common.cache.LocalCache.Segment.scheduleRefresh方法：

VscheduleRefresh(LocalCache.ReferenceEntry<K, V> entry, K key, int hash, V oldValue, long now, CacheLoader<? super K, V> loader)

{

if((this.map.refreshes())&& (now - entry.getWriteTime() > this.map.refreshNanos) &&(!( entry.getValueReference().isLoading())))

{

Object newValue = refresh(key, hash,loader, true);

if (newValue != null) {

return newValue;

}

}

returnoldValue;

}

Determine whether refresh is required, the cache time has expired, and the current non-loading state, if so, perform the refresh operation and return a new value, otherwise directly return the oldValue in the cache.

Let's take a closer look at the refresh method called in scheduleRefresh, and the source code is as follows

@Nullable

V refresh(K key, int hash, CacheLoader<? super K, V> loader, boolean checkTime)

{

LocalCache.LoadingValueReference loadingValueReference =insertLoadingValueReference(key, hash, checkTime);

if(loadingValueReference == null) {

returnnull;

}

ListenableFuture result = loadAsync(key, hash, loadingValueReference,loader);

if(result.isDone())

try {

return Uninterruptibles.getUninterruptibly(result);

}

catch (Throwable t)

{

}

returnnull;

}

Insert loadingValueReference to indicate that the value is being loaded, and other requests will determine whether to refresh or return the old value based on this. insertLoadingValueReference locks to ensure that only 1 refresh penetrates the backend. Due to space limitations, I will not expand on it here. However, the range of locking here is smaller than that of load, in the process of expire->load, once all GET knows to expire, they need to get the lock until they get the new value, and the range of blocking will be from expire to load to the new value; In the process of refresh-> reload, once get finds that it needs to refresh, it will first determine whether there is loading, then obtain the lock, and then reload after releasing the lock, the blocking range is only the new and set operations of a small object of insertLoadingValueReference, which is almost negligible, so this is one of the reasons why it was said that refresh is more efficient than expire.

At this point, we know the difference between refresh and expire: refresh executes reload, and after expire, it re-executes load, just like initialization.

下面看看com.google.common.cache.LocalCache.Segment.lockedGetOrLoad方法：

V lockedGetOrLoad(K key, int hash, CacheLoader<? super K, V> loader) throws ExecutionException

{

LocalCache.ValueReference valueReference = null;

LocalCache.LoadingValueReference loadingValueReference = null;

booleancreateNewEntry = true;

lock();

LocalCache.ReferenceEntry e;

try

{

long now = this.map.ticker.read();

preWriteCleanup(now);

int newCount = this.count - 1;

AtomicReferenceArray table = this.table;

int index = hash & table.length() - 1;

LocalCache.ReferenceEntry first =(LocalCache.ReferenceEntry)table.get(index);

for (e = first; e != null; e = e.getNext()) {

Object entryKey = e.getKey();

if ((e.getHash() != hash) || (entryKey == null) || (! (this.map.keyEquivalence.equivalent(key,entryKey))))

continue;

valueReference =e.getValueReference();

if (valueReference.isLoading()) {

createNewEntry = false; break;

}

Object value = valueReference.get();

if (value == null) {

enqueueNotification(entryKey, hash,valueReference, RemovalCause.COLLECTED);

} elseif (this.map.isExpired(e,now))

{

enqueueNotification(entryKey, hash,valueReference, RemovalCause.EXPIRED);

} else {

recordLockedRead(e, now);

this.statsCounter.recordHits(1);

Object localObject2 = value;

return localObject2;

}

this.writeQueue.remove(e);

this.accessQueue.remove(e);

this.count = newCount;

break;

}

if (createNewEntry) {

loadingValueReference = new LocalCache.LoadingValueReference();

if (e == null) {

e = newEntry(key, hash, first);

b.setValueReference(loadingValueReference);

table.set(index, e);

} else {

b.setValueReference(loadingValueReference);

}

}

} finally{

unlock();

postWriteCleanup();

}

if(createNewEntry)

{

try

{

synchronized (e) {

Object localObject1 = loadSync(key,hash, loadingValueReference, loader);

this.statsCounter.recordMisses(1); return localObject1; } } finally { this.statsCounter.recordMisses(1);

}

}

returnwaitForLoadingValue(e, key, valueReference);

}

There are 7 steps.

1. Get a lock

2.获得key对应的valueReference

3. Determine whether the cached value is loading, if loading, the load operation will not be carried out (by setting createNewEntry to false), and the new value will be obtained later.

4. If it is not loading, check whether there is already a new value (loaded by other requests), and if so, return the new value

5. Prepare loading and set it to loadingValueReference. loadingValueReference will cause other requests to find that they are loding in step 3.

6. Release the lock.

7. If load is really needed, then load the operation.

Through analysis, it is found that there will only be one load operation, and the other GET will be blocked first.

build

proposals

To sum up, in the process of daily use of Guava Cache, we recommend that you use the following methods to manage cache policies, and the specific code is as follows:

private LoadingCache<String,Optional< Object >> demoCahce = CacheBuilder.newBuilder()

.expireAfterWrite(5, TimeUnit.SECONDS).maximumSize(500).recordStats()

.refreshAfterWrite(3, TimeUnit.SECONDS)

.build(new CacheLoader<String, Optional<Object>>(){

@Override

public Optional<Object> load(String key) throws Exception {

return Optional.fromNullable(takeAwardService.getHornNotice());

}

});

In terms of cache initialization and management, it is recommended to set the time reclamation policy and the capacity reclamation policy at the same time to carry out the cache management strategy, use expireAfterWrite to manage the expiration time of the data in the cache, and use the refreshAfterWrite method to complete the pre-update operation of the cached data, which not only solves the cache penetration problem caused by using expireAfterWrite alone. It also solves the problem that the data is too old caused by only using refreshAfterWrite, and uses maximumSize to limit the capacity of the buffer, so that the cache is efficiently managed in terms of time and space.

Author: Gu Xin

Source-WeChat public account: 58 wireless technology

Source: https://mp.weixin.qq.com/s/vi8Y-u-uZc6V357yqwVH1g