preface
Redis (a) how to implement fixed size cache?
Java from zero handwriting implementation of Redis (2) Redis expire principle
Java from zero handwriting implementation redis (three) how to restart memory data is not lost?
Java from zero handwriting implementation redis (four) add listener
Java from zero handwriting redis (five) another way to implement expiration strategy
Java from zero handwriting implementation redis (six) AOF persistence principle detailed explanation and implementation
Java from scratch handwriting Redis (seven) LRU cache elimination strategy in detail
Java handwriting from scratch Redis (eight) naive LRU elimination algorithm performance optimization
In section 2, we implemented the expire expire function similar to that in Redis, but there was a problem that was not solved. The iteration was not random, causing each iteration to start from scratch and possibly causing many Keys to be “hungry”.
It can be recalled:
Java from zero handwriting implementation of Redis (2) Redis expire principle
Java from zero handwriting redis (five) another way to implement expiration strategy
In this section, we’ll implement an out-of-date randomness version and take a closer look at the subtleties of Redis.
Review of previous implementations
Before embarking on a new journey, let’s review the original implementation.
Expire 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 codeRedis timed task
process
If you want to know what is wrong with our process, compare it with redis’ scheduled cleaning task process.
Redis maintains a scheduled task internally, running 10 times per second by default (controlled by configuring Hz).
The logic of deleting expired keys in a scheduled task adopts an adaptive algorithm. Keys are reclaimed based on the expiration ratio of keys and the speed mode. The process is as follows:
The process that
1) The scheduled task randomly checks 20 keys in each database space and deletes the corresponding keys when they are found to be expired.
2) If a key that exceeds 25% of the number of checks expires, the recycle logic is looped until it falls below 25% or runs out of time, which is 25 milliseconds in slow mode.
3) If the logic of retrieving expired keys has timed out before, the task of retrieving expired keys will be run again in fast mode before Redis triggers an internal event. In fast mode, the timeout time is 1 millisecond and the task can only be run once within 2 seconds.
4) The internal deletion logic of fast and slow modes is the same, but the execution timeout time is different.
Ps: The fast and slow mode here is also cleverly designed, adjusting the corresponding task timeout time according to the proportion of expired information.
Randomness is also very important here, because it allows you to objectively clean up the expired information, rather than going through it from the beginning and making the subsequent data inaccessible.
We’re going to focus on randomly selecting this feature.
Go to the collection directly via Map#keys
Implementation approach
Leave the expireMap unchanged, convert keys directly to collection, and then fetch randomly.
This is one of the most popular answers on the Internet.
Java code implementation
Basic attributes
public class CacheExpireRandom<K.V> implements ICacheExpire<K.V> {
private static final Log log = LogFactory.getLog(CacheExpireRandom.class);
/** * Limit on the number of empties at a time *@since0.0.16 * /
private static final int COUNT_LIMIT = 100;
/** * expired map ** Space for time *@since0.0.16 * /
private final Map<K, Long> expireMap = new HashMap<>();
/** * Cache implementation *@since0.0.16 * /
private final ICache<K,V> cache;
/** * Whether to enable fast mode *@since0.0.16 * /
private volatile boolean fastMode = false;
/** * thread execution class *@since0.0.16 * /
private static final ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor();
public CacheExpireRandom(ICache<K, V> cache) {
this.cache = cache;
this.init();
}
/** * Initialize the task *@since0.0.16 * /
private void init(a) {
EXECUTOR_SERVICE.scheduleAtFixedRate(new ExpireThreadRandom(), 10.10, TimeUnit.SECONDS); }}Copy the codeTiming task
Here we are in line with Redis and support fastMode.
In fact, the logic of fastMode and slow mode is exactly the same, but the timeout time is different.
I have adjusted the timeout time according to my personal understanding, but the overall process remains the same.
/** ** Execute tasks regularly *@since0.0.16 * /
private class ExpireThreadRandom implements Runnable {
@Override
public void run(a) {
//1. Check whether it is empty
if(MapUtil.isEmpty(expireMap)) {
log.info("If the expireMap information is empty, skip this operation.");
return;
}
//2. Enable the fast mode
if(fastMode) {
expireKeys(10L);
}
//3. Slow mode
expireKeys(100L); }}Copy the codeExpiration information core implementation
When an execution expires, we first record the timeout period, which is used to interrupt execution.
FastMode =false is restored by default, and fastMode=true is set when execution times out.
/** * Expiration information *@paramTimeoutMills Timeout period *@since0.0.16 * /
private void expireKeys(final long timeoutMills) {
// set the timeout period to 100ms
final long timeLimit = System.currentTimeMillis() + timeoutMills;
/ / fastMode recovery
this.fastMode = false;
//2. Obtain the key for processing
int count = 0;
while (true) {
//2.1 Return judgment
if(count >= COUNT_LIMIT) {
log.info("The number of expired eliminations has reached the maximum: {}, the execution is complete.", COUNT_LIMIT);
return;
}
if(System.currentTimeMillis() >= timeLimit) {
this.fastMode = true;
log.info("Expiration time has reached, interrupt this execution, set fastMode=true;");
return;
}
//2.2 Random expiration
K key = getRandomKey();
Long expireAt = expireMap.get(key);
boolean expireFlag = expireKey(key, expireAt);
log.debug("Key: {} expired execution result {}", key, expireFlag);
//2.3 Information updatecount++; }}Copy the codeObtain expired keys randomly
/** * Get a random key *@returnRandomly returned keys *@since0.0.16 * /
private K getRandomKey(a) {
Random random = ThreadLocalRandom.current();
Set<K> keySet = expireMap.keySet();
List<K> list = new ArrayList<>(keySet);
int randomIndex = random.nextInt(list.size());
return list.get(randomIndex);
}
Copy the codeThis is the most common implementation method on the web, where all keys are directly converted to a list and an element is retrieved by Random.
Performance improvements
Methodological flaws
The getRandomKey() method is still too expensive to extract random information.
If the number of keys is very large, we create a list, which is time-consuming in itself and directly doubles the space complexity.
So it’s not clear why this one is the most common solution at night.
Optimize your thinking – avoid wasting space
The simplest idea is that we should avoid creating lists.
All we need is a random value based on size, which we can iterate over:
private K getRandomKey2(a) {
Random random = ThreadLocalRandom.current();
int randomIndex = random.nextInt(expireMap.size());
/ / traversal keys
Iterator<K> iterator = expireMap.keySet().iterator();
int count = 0;
while (iterator.hasNext()) {
K key = iterator.next();
if(count == randomIndex) {
return key;
}
count++;
}
// Normal logic does not go there
throw new CacheRuntimeException("Corresponding information does not exist.");
}
Copy the codeOptimization idea – Batch operation
The above method avoids the creation of a list, and also satisfies the condition of randomness.
However, it is also a slow process (O(N) time complexity) to iterate to random size values.
If we do it 100 times, the pessimistic case is 100 times O(N).
We can reduce time complexity by using the idea of batches, such as 100 at a time:
/** * Obtain multiple keys in batches *@paramSizeLimit sizeLimit *@returnRandomly returned keys *@since0.0.16 * /
private Set<K> getRandomKeyBatch(final int sizeLimit) {
Random random = ThreadLocalRandom.current();
int randomIndex = random.nextInt(expireMap.size());
/ / traversal keys
Iterator<K> iterator = expireMap.keySet().iterator();
int count = 0;
Set<K> keySet = new HashSet<>();
while (iterator.hasNext()) {
// Determine the size of the list
if(keySet.size() >= sizeLimit) {
return keySet;
}
K key = iterator.next();
// index is placed backwards.
if(count >= randomIndex) {
keySet.add(key);
}
count++;
}
// Normal logic does not go there
throw new CacheRuntimeException("Corresponding information does not exist.");
}
Copy the codeWe pass in a size limit for a list that can fetch more than one at a time.
Time complexity of -o (1)
At first, when I thought of randomness, my first idea was to make a redundant list to store keys at the same time, and then return keys randomly to solve the problem.
But for the list update, it is true that O(N) space complexity is more than the list part, which feels not worth it.
If you use the previous map to store bidirectional linked list nodes can also be solved, but relatively troublesome, the previous has also been implemented, here is not repeated.
In fact, the randomness here is a little bit inadequate
(1) For example, if the data is random, how to deal with it?
Of course, the current solution is direct count. Generally, when the amount of data is large, this probability is relatively low, and there is lazy deletion of the bottom pocket, so it does not matter much.
(2) Random information is very likely to expire
It is better to use our original map classification method based on expiration time, so that we can ensure that the expiration time of the information obtained is in our hands.
Of course, each method has its own advantages and disadvantages. It depends on how we choose according to the actual situation.
summary
At this point, an expire expiration function similar to Redis is basically implemented.
This is basically the end of the redis out-of-date implementation. Of course, there are many more optimizations, so please write your own in the comments section.
Open source address: github.com/houbb/cache
If you find this article helpful, please feel free to like it. Your encouragement, is my biggest motivation ~
Do not know what you have gained? Or have other more ideas, welcome to discuss with me in the comments section, looking forward to meeting your thinking.
The original address
Cache travel-09 – Implementation of redis expire from null Cache
The resources
JAVA randomly selects keys from the MAP
Selecting random key and value sets from a Map in Java