preface
We have initially implemented our cache in implementing a fixed size cache from the Zero handwriting Cache framework (1).
In this section, let’s take a look at implementing something like the expire expiration feature in Redis.
Expiration is a very useful feature. For example, I want to put my login information into Redis and expire after 30 minutes. Or the accumulated information of a day is stored in Redis and automatically cleared at dawn every day.
Code implementation
interface
Let’s first define the interface.
There are two main things: one is when it expires, and the other is when it expires.
public interface ICache<K.V> extends Map<K.V> {
/** * set expiration time * (1) If the key does not exist, do nothing. * (2) Temporarily do not provide a new key to specify the expiration time, will break the original method. What does * * do: * Similar to redis * (1) lazy delete. * When the following method is executed, delete it if it expires. * {@linkICache#get(Object)} get * {@linkICache#values()} get all values * {@linkICache#entrySet()} get all the details * * [data inconsistencies] * call other methods, which may not get the result expected by the user, because the EXPIRE information may not have been updated in time. * such as * {@linkICache#isEmpty()} isEmpty * {@linkICache#size()} The current size * also causes problems with size() as an expiration condition. * * Solution: Consider adding refresh and other methods, regardless of consistency for now. * For practical use, we care more about K/V information. * * (2) Scheduled Deletion * Starts a scheduled task. A key of a specified size is randomly selected each time to determine whether the key is expired. * Similar to Redis, consider setting the timeout for simplicity, with frequency inversely proportional to the timeout. * * Other extensibility considerations: * Later considerations provide atomic operations to ensure transactionality. Don't think about it for the moment. * TTL is used as the benchmark for comparison by default, so we don't want to support LastAccessTime's elimination policy for now. It adds complexity. * This method can be left unchanged if the lastAccessTime expiration is added. * *@param key key
* @paramTimeInMills Expires after milliseconds *@return this
* @since0.0.3 * /
ICache<K, V> expire(final K key, final long timeInMills);
/** * expires at the specified time *@param key key
* @paramTimeInMills timestamp *@return this
* @since0.0.3 * /
ICache<K, V> expireAt(final K key, final long timeInMills);
}
Copy the codeCode implementation
To facilitate processing, we will calculate how long after expiration. Turn two problems into the same problem, the question of when to expire.
The core code, again, looks at the cacheExpire interface.
@Override
public ICache<K, V> expire(K key, long timeInMills) {
long expireTime = System.currentTimeMillis() + timeInMills;
return this.expireAt(key, expireTime);
}
@Override
public ICache<K, V> expireAt(K key, long timeInMills) {
this.cacheExpire.expire(key, timeInMills);
return this;
}
Copy the codeCache expiration
In order to facilitate future expansion, the processing of expiration is defined as an interface for flexible replacement.
interface
Expire (final K key, final long expireAt); That’s where we call our method.
RefershExpire is an inert deletion and is only considered when a refresh is required, as we will explain later.
public interface ICacheExpire<K.V> {
/** * Specifies expiration information *@param key key
* @paramWhen does expireAt expire *@since0.0.3 * /
void expire(final K key, final long expireAt);
/** * Lazy delete keys * that need to be processed@param keyList keys
* @since0.0.3 * /
void refreshExpire(final Collection<K> keyList);
}
Copy the codeExpire implementation principle
In fact, the actual idea of expiration is relatively simple: we can start a scheduled task, for example, do rotation training every second, to delete expired information.
Storage of expiration information
/** * expired map ** Space for time *@since0.0.3 * /
private final Map<K, Long> expireMap = new HashMap<>();
@Override
public void expire(K key, long expireAt) {
expireMap.put(key, expireAt);
}
Copy the codeWe define a map where key is the information to expire and value stores the expiration time.
Polling to clean up
We always clean 100ms at a time, and at most 100 at a time.
/** * Limit on the number of empties at a time *@since0.0.3 * /
private static final int LIMIT = 100;
/** * Cache implementation *@since0.0.3 * /
private final ICache<K,V> cache;
/** * thread execution class *@since0.0.3 * /
private static final ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor();
public CacheExpire(ICache<K, V> cache) {
this.cache = cache;
this.init();
}
/** * Initialize the task *@since0.0.3 * /
private void init(a) {
EXECUTOR_SERVICE.scheduleAtFixedRate(new ExpireThread(), 100.100, TimeUnit.MILLISECONDS);
}
Copy the codeA single thread is defined to perform the cleanup task.
Empty the task
This is very simple: iterate over the expiration data, determine the corresponding time, and if it has expired, perform the empty operation.
To avoid a long execution time, a maximum of 100 entries can be processed.
/** ** Execute tasks regularly *@since0.0.3 * /
private class ExpireThread implements Runnable {
@Override
public void run(a) {
//1. Check whether it is empty
if(MapUtil.isEmpty(expireMap)) {
return;
}
//2. Obtain the key for processing
int count = 0;
for(Map.Entry<K, Long> entry : expireMap.entrySet()) {
if(count >= LIMIT) {
return; } expireKey(entry); count++; }}}/** * Perform expiration operation *@paramEntry details *@since0.0.3 * /
private void expireKey(Map.Entry<K, Long> entry) {
final K key = entry.getKey();
final Long expireAt = entry.getValue();
// Delete logical processing
long currentTime = System.currentTimeMillis();
if(currentTime >= expireAt) {
expireMap.remove(key);
// Then remove the cache, which can be compensated by lazy deletioncache.remove(key); }}Copy the codeClean up the optimization idea
If there are not many application scenarios that are out of date, then regular rotation training really doesn’t mean much.
For example, 99% of our tasks are clearing data in the wee hours of the morning. No matter how much polling we do during the day, it’s a waste of resources.
Is there a way to quickly determine if there are expired elements that need to be disposed of?
The answer is yes, it is a sorted MAP.
Another way to think about it is to make the expiration time as the key, and put the information that needs to expire at the same time in a list as the value.
Then sort the expiration time, polling can quickly determine whether there is expiration information.
public class CacheExpireSort<K.V> implements ICacheExpire<K.V> {
/** * Limit on the number of empties at a time *@since0.0.3 * /
private static final int LIMIT = 100;
/** * Sort cache storage ** uses cache processing that sorts by time. *@since0.0.3 * /
private final Map<Long, List<K>> sortMap = new TreeMap<>(new Comparator<Long>() {
@Override
public int compare(Long o1, Long o2) {
return (int) (o1-o2); }});/** * expired map ** Space for time *@since0.0.3 * /
private final Map<K, Long> expireMap = new HashMap<>();
/** * Cache implementation *@since0.0.3 * /
private final ICache<K,V> cache;
/** * thread execution class *@since0.0.3 * /
private static final ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor();
public CacheExpireSort(ICache<K, V> cache) {
this.cache = cache;
this.init();
}
/** * Initialize the task *@since0.0.3 * /
private void init(a) {
EXECUTOR_SERVICE.scheduleAtFixedRate(new ExpireThread(), 1.1, TimeUnit.SECONDS);
}
/** ** Execute tasks regularly *@since0.0.3 * /
private class ExpireThread implements Runnable {
@Override
public void run(a) {
//1. Check whether it is empty
if(MapUtil.isEmpty(sortMap)) {
return;
}
//2. Obtain the key for processing
int count = 0;
for(Map.Entry<Long, List<K>> entry : sortMap.entrySet()) {
final Long expireAt = entry.getKey();
List<K> expireKeys = entry.getValue();
// Check whether the queue is empty
if(CollectionUtil.isEmpty(expireKeys)) {
sortMap.remove(expireAt);
continue;
}
if(count >= LIMIT) {
return;
}
// Delete logical processing
long currentTime = System.currentTimeMillis();
if(currentTime >= expireAt) {
Iterator<K> iterator = expireKeys.iterator();
while (iterator.hasNext()) {
K key = iterator.next();
// Remove itself first
iterator.remove();
expireMap.remove(key);
// Then remove the cache, which can be compensated by lazy deletioncache.remove(key); count++; }}else {
// Skip directly, no expired information
return; }}}}@Override
public void expire(K key, long expireAt) {
List<K> keys = sortMap.get(expireAt);
if(keys == null) {
keys = new ArrayList<>();
}
keys.add(key);
// Set the corresponding informationsortMap.put(expireAt, keys); expireMap.put(key, expireAt); }}Copy the codeThis seems to be feasible and reduces the pressure of polling.
In fact, the use of space in exchange for time, I think it can be improved later, this method should be good performance.
However, I did not adopt this scheme, mainly considering the problem of lazy deletion, which would be troublesome. I will continue to improve this scheme in the future.
Lazy to delete
Cause of occurrence
Similar to Redis, we adopt the scheme of periodic deletion, but there is a problem: the data may not be cleaned in time.
So when we query, we might get dirty data.
So some people think, when we care about some data, only do the corresponding deletion judgment operation on the data, so that the pressure will be much less.
It’s kind of a compromise.
Methods that require lazy deletion
This is usually a variety of query methods, such as when we get the value of the key
@Override
@SuppressWarnings("unchecked")
public V get(Object key) {
//1. Refresh all expiration information
K genericKey = (K) key;
this.cacheExpire.refreshExpire(Collections.singletonList(genericKey));
return map.get(key);
}
Copy the codeLet’s do a data refresh before we get it.
Implementation of refresh
The implementation principle is also very simple, is a loop, and then delete.
A small optimization has been added: select a small number for the outer loop.
The time complexity of the cyclic set is O(n), and the time complexity of map.get() is O(1);
@Override
public void refreshExpire(Collection<K> keyList) {
if(CollectionUtil.isEmpty(keyList)) {
return;
}
// Determine the size, small as the outer loop. Keys that have expired are usually smaller.
if(keyList.size() <= expireMap.size()) {
for(K key : keyList) { expireKey(key); }}else {
for(Map.Entry<K, Long> entry : expireMap.entrySet()) {
this.expireKey(entry); }}}Copy the codetest
Once the above code is written, we can verify it.
ICache<String, String> cache = CacheBs.<String,String>newInstance()
.size(3)
.build();
cache.put("1"."1");
cache.put("2"."2");
cache.expire("1".10);
Assert.assertEquals(2, cache.size());
TimeUnit.MILLISECONDS.sleep(50);
Assert.assertEquals(1, cache.size());
System.out.println(cache.keySet());
Copy the codeThe results were in line with our expectations.
summary
At this point, an expire expiration function similar to Redis is basically implemented.
Of course, there are still many optimizations.
For example, to facilitate the subsequent addition of various listeners, I adjusted all the places that needed to be refreshed to use bytecode + annotations instead of adding a refresh method to every method that needed to be refreshed.
In the next section, we’ll learn how to implement various listeners together.
If it helps you, please click on it
Your encouragement, is my biggest motivation ~
The original address
Cache travel-09 – Implementation of redis expire from null Cache