preface
Redis (a) how to achieve a fixed size cache?
Java implements the principle of Redis expire from zero script
Java from zero handwritten implementation of Redis (three) memory data how to restart not lost?
Java from zero handwritten implementation of Redis (four) add listeners
We implemented several of the basic features of Redis earlier, but we mentioned another way of implementing them in the expire principle.
Write it down here, you can expand your thinking.
Previous implementations
The core idea
The original implementation is as follows:
Java implements the principle of Redis expire from zero script
https://mp.weixin.qq.com/s/BW…
insufficient
The previous design was very simple and followed the basic idea of putting out-of-date information in a Map and then iterating through it to clear it.
In order to avoid the single operation time is too long, similar to Redis, a single operation of 100 elements, directly return.
However, when it comes to timing tasks, there are actually two drawbacks:
(1) The selection of keys is not random enough, which may lead to that at the end of each cycle of 100, the ones that really need to expire are not traversal.
However, the randomness of map is more stupid, that is, the map keys are all converted to a set, and then returned through random.
The process of rotation is an O(n) traversal, so it was not implemented at first.
Another way is to trade space for time. When we store it, we store it in the list at the same time, and then return it to the list at random. This is a subsequent optimization.
(2) The traversal of keys may be mostly invalid.
Each time we traverse from front to back according to the keys, but we don’t care about the corresponding expiration time, which leads to a lot of invalid traversal.
This article mainly provides an implementation method with expiration time as the dimension, for reference only, because this method also has drawbacks.
Time-based traversal
Train of thought
Each time we put into an expired element, we sort the elements by expiration time, and the Keys for the same expiration time are grouped together.
Advantages: Timed traversal, if the time is less than the current time, you can directly return, greatly reducing the invalid traversal.
Disadvantage: Considering the problem of lazy deletion, you still need to store the map relationship with deleted information as the key, so the memory is basically doubled.
Basic attribute definition
We use TreeMap here to help us sort the expiration time. This collection will be explained in more detail later. I have looked at the JDK 1.8 source code, which is mainly implemented by red-black trees.
Public class CacheexpiResort <K,V bb0 implements ICacheexpire <K,V> {/** ** ** ** ** ** ** / private static final int LIMIT = 100; /** * Sort cache storage ** uses the cache processing sorted by time. * @since 0.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); }}); Private final map <K, Long BB0 expireMap = new HashMap<>(); /** * caches * @since 0.0.3 */ private final ICache<K, VDB cache; }When you put elements in
Each time you save a new element, put in both the sortMap and the expireMap.
@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 information sortMap.put(expireAt, keys); expireMap.put(key, expireAt); }Timed task execution
define
We define a timed task to be executed every 100ms.
/ * * * thread * @ since 0.0.3 * / private static final ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor(); public CacheExpireSort(ICache<K, V> cache) { this.cache = cache; this.init(); } / initialization tasks * * * * @ since 0.0.3 * / private void init () {EXECUTOR_SERVICE. ScheduleAtFixedRate (new ExpireThread (), 100, 100, TimeUnit.MILLISECONDS); }Perform a task
The source code is as follows:
Private class ExpireThread implements Runnable {@Override public void run() {//1. Override public void run() {//1. If (mapUtil.isEmpty (sortMap)) {return; } //2. Int count = 0; for(Map.Entry<Long, List<K>> entry : sortMap.entrySet()) { final Long expireAt = entry.getKey(); List<K> expireKeys = entry.getValue(); If (CollectionUtil.IsEmpty (ExpireKeys)) {sortMap.remove(ExpireAt); continue; } if(count >= LIMIT) { return; } long currentTime = System.currentTimeMillis(); if(currentTime >= expireAt) { Iterator<K> iterator = expireKeys.iterator(); while (iterator.hasNext()) { K key = iterator.next(); // first remove iterator.remove(); expireMap.remove(key); // Remove the cache from the cache, which can be later compensated by lazy removal; count++; }} else {return;} else {return; }}}}The key is the expiration time, and then you can compare it with the current time.
Delete expireMap/sortMap/cache
Lazy delete refresh
ExpireMap is used when a lazy delete refresh occurs.
Because sometimes there is only one key to refresh, if there is no expireMap mapping relationship, you may have to traversal the sortMap to find the corresponding expiration time.
It’s a question of time complexity versus space complexity.
@Override public void refreshExpire(Collection<K> keyList) { if(CollectionUtil.isEmpty(keyList)) { return; } // This is too costly to maintain two sets, subsequent optimization, temporarily not used. Final int expiResize = expiResize (); final int expiResize = expiResize (); If (expireSize <= keylist.size ()) {for(map.entry <K,Long> Entry: expireMap.entrySet()) { K key = entry.getKey(); // Expansion is handled directly, no longer exists in the collection. // This is an example of a set.removeExpireKey (); } } else { for(K key : keyList) { this.removeExpireKey(key); Private void removeExpireKey(final K key) {private void removeExpireKey(final K key) {private void removeExpireKey(final K key) {private void removeExpireKey(final K key) {private void removeExpireTime (final K key) {private void removeExpireTime (final K key) expireMap.get(key); if(expireTime ! = null) { final long currentTime = System.currentTimeMillis(); if(currentTime >= expireTime) { expireMap.remove(key); List<K> expireKeys = sortMap.get(expireTime); expireKeys.remove(key); sortMap.put(expireTime, expireKeys); }}}summary
There are many ways to achieve expiration. At present, the two schemes we provide have their own advantages and disadvantages, and I believe there will be a more excellent way.
Program = Data Structure + Algorithm
The reason why Redis has such excellent performance is actually inseparable from the rational use of its data structure and algorithm. The excellent framework is worth repeated learning and thinking.
The article mainly tells about the train of thought, the realization part because of the space limitation, did not post all out.
Open source address:
https://github.com/houbb/cache
If you found this article helpful, please feel free to join us in the comments collection
Your encouragement is my greatest motivation
